dcrocker@engr.ub.COM.UUCP (03/31/87)
In article <8703250201.AA06443@flash.bellcore.com> karn@FLASH.BELLCORE.COM (Phil R. Karn) writes: >... In "unlayered virtual circuit" networks, connection >state information is kept not only in the end-point switches, but also in >every intermediate switch along the path. >... Because of this, a node or link failure ANYWHERE along the >connection path causes an X.25 VC reset, not just failures at the end nodes. > >Only in "layered VC" networks such as the DDN (where datagrams are used >internally) can intermediate node and link failures occur without resetting >virtual circuits. ... Don't know how much this will contribute to the discussion, but you pushed one of my buttons: There are two issues often treated as one: Virtual Circuit vs. Datagram underlying architecture, and Robust vs. Fragile handling of major network anomolies. It is common for VC-oriented nets to be relatively more Fragile than the DG-oriented ones, but that definitely is not necessary. It has more to do with certain economies that are perceived by the implementors. X.25 vendors are excellent examples of the VC/Fragile orientation. By virtue of being very cost-conscious, they pay very close attention to such things as packet-handling "efficiencies" and buffer management. The handling efficiency question walks them down the path of internal VC orientation. (Common belief: The processing overhead to forward a packet in a VC-oriented system is lower than in a DG-oriented one.) The buffer management question makes them give up a buffer as soon as the "next" hop has acknowledged it. That is, the only copy of the data exists at the latest node to have accepted it. If that node goes down, the copy is lost. Your note used the term "end to end reliability". That is exactly the issue. The sending node must hold onto a copy of the data until the receiving node acknowledges deliverying it to the destination host. If it does this, than an internal X.25 Reset (for example) could be transparently recovered from, by re-routing the circuit automatically. A few years ago, I tried to get Databit (Siemens) to modify their X.25 packet switches to permit holding on to the packet at the sending node, until a final ack was received. They were not willing to consume buffers for that long. By the same token, BBN could modify their switches NOT to hold on to packets at the source PSN. At that point, a number of problems internal to the net would become highly visible to users. Dave
AFDDN.TCP-IP@GUNTER-ADAM.ARPA.UUCP (03/31/87)
I'm in the same boat with Dave; VC versus datagram is one of my buttons. I'm much more familiar with the BBN way of doing things than with PDNs. I can see where PDNs would want to have very tight control over everything going on in the network. Tightly binding resources in a single virtual path through the network does let you know what resources are going where and for how long. I think it also tends to stabilize network delays around some median which might be nice. You can also establish stable (fixed) routing. Some nets I believe have a single route source that has global knowledge of the network and returns routes to the net nodes for every connection request. The disadvantage I see is that every VC will use up a given amount of net resources whether data is actually being transmitted across the VC or not. In the cases where static routing is downloaded from a central site, the survivability of the network as a whole is only as good as that of the central site. BBN gets around these two disadvantages at a cost. The Milnet for instance is gettingvery large, very fast. I don't know the formula for computing the amount of bandwidth required for the internal routing updates, but I would suspect it would go up exponentially with the number of nodes(and connectivity of them). If anybody knows the numbers I'd like to have them. The current limit of 256 nodes on one network has already been reached for Milnet. They nodes aren't installed and operational yet, but the addresses have been allocated to future nodes. And even with the size of the backbone, there are nodes with 12-18 hosts connected or slated for connection. Maybe we need "butter" switches? Darrel B. -------
haas%utah-gr@CS.UTAH.EDU.UUCP (04/01/87)
In article <8703312012.AA25019@ucbvax.Berkeley.EDU>, AFDDN.TCP-IP@GUNTER-ADAM.ARPA writes: > Tightly binding resources in a single virtual path through the > network does let you know what resources are going where and for how long... True, this was a major motivation for Telenet's conversion to VC internals. > Some nets I believe have a single route source that has global knowledge of > the network and returns routes to the net nodes for every connection > request. The earliest version of Tymnet used something like this. The system did not scale up, not so much because of the reliability problem but because of the enormous amount of traffic to and from the Master User Directory. This approach is no longer used. > The disadvantage I see is that every VC will use up a given amount of net > resources whether data is actually being transmitted across the VC or not. Only a small table entry is used. This is in practice less costly than the communications resources used to convey a complete address in every packet. > In the cases where static routing is downloaded from a central site, the > survivability of the network as a whole is only as good as that of the > central site. True. Tymnet went to four regional sites for routing information, which helps with robustness and distributes the traffic a little more evenly. Telenet assigns net addresses geographically, and each TCO routes based on the implicit geographic information in the Call Request packet. Thus each TCO can make routing decisions independently of any central source of routing information. This is very robust. Cheers -- Walt
tsuchiya@GATEWAY.MITRE.ORG.UUCP (04/02/87)
> BBN gets around these two disadvantages at a cost. The Milnet for instance > is gettingvery large, very fast. I don't know the formula for computing the > amount of bandwidth required for the internal routing updates, but I would > suspect it would go up exponentially with the number of nodes(and connectivity > of them). If anybody knows the numbers I'd like to have them. BBN C-30 based networks use an efficient flooding scheme to send routing updates. Each update crosses each link twice, the second time as a robust acknowledgement. Link overhead is therefore linear with the number of nodes. Better still, the algorithm they use to compute routes when a change is received performs on the order of the average hop length of all paths, estimated at log N/log(c-1) where N is number of nodes and c is connectiviey. See paper by John McQuillan, Ira Richer, and Eric Rosen, "The New Routing Algorithm for the ARPANET," IEEE Transactions on Communications, Vol. COM-28, No. 5, May 1980. Paul Tsuchiya tsuchiya@gateway.mitre.org The MITRE Corp. tsuchiya@mitre-gateway.arpa
AFDDN.TCP-IP@GUNTER-ADAM.ARPA.UUCP (04/02/87)
Paul, On the C/30 algorithm, I believe there are two occurences which can generate an update. One is the expiration of some timer which I've been told is 30 secs. I seem to remember at one time the limit being around 15 secs. The other occurence is in the case where a link is determined to be down. I made the assumption that as the total number of nodes and the connectivity increases then the probability of link problems goes up. Would it increase linearly? Would be an interesting study. I've always thought an interesting experiment would be to first determine an estimated time for a routing update to propagate through the network. Then determine the time required for the Line Up-down Protocol to determine a link is has either just went up or down and then generate the update. Now place a few unscrupulous individuals goegraphically widespread across the network on several interswitch links. Let these individual interupt the link at time T0 and then restore it at T0 + routing propagation time - LUP decision time. How much bandwidth could you forcibly use up with internal routing updates? Ciao, Darrel -------
malis@CC5.BBN.COM.UUCP (04/04/87)
Darrel, I'm afraid your experiment wouldn't cause much as much routing traffic as you think. Your details on the PSN routing algorithm were a bit wrong. First, there are three things that can cause a routing update to be generated: a link going up or down, the delay to a neighbor PSN changing more than a certain threshold, or the expiration of 50 seconds from the last time the PSN generated an update. Second, a PSN can generate an update at most every 10 seconds, no matter how much is changing in the network. Third, when a link goes down, it takes 60 seconds to bring it back up (this ensures that if a PSN was isolated from the network, it cannot bring up its links until it has received at least one routing update from every other PSN in the network; otherwise, its routing database would be incomplete). The estimated time for a routing update to propagate through the network is simply the network "diameter" (the minimum-hop path between the two most logically distant PSNs in the network) times the average propagation delay across the links. Flooding routing updates gets the highest priority in the PSN, so intra-PSN delays are usually negligible. Since routing updates cannot be generated at a greater rate than every 10 seconds by each PSN and at least every 50 seconds, it is easy to calculate the minimum, average, and maximum number of routing updates per minute on a network. And since the line up/down protocol keeps links down for at least 60 seconds, manually making links go up or down will probably not produce any more updates than you would have had anyway. Andy