IEN 189 ISSUES IN INTERNETTING PART 4: ROUTING Eric C. Rosen Bolt Beranek and Newman Inc. June 1981 IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen ISSUES IN INTERNETTING PART 4: ROUTING 4. Routing This is the fourth in a series of papers that discuss the issues involved in designing an internet. Familiarity with the previous papers (IENs 184, 187, and 188) is presupposed. The topic of the present paper is routing. We will discuss the issues involved in choosing a routing algorithm for the internet, and we will propose a particular algorithm. The algorithm we propose will be based on the routing algorithm currently operating in the ARPANET, called "SPF routing." This algorithm is described in [1] and [2], which interested readers will certainly want to look at. Although we will try to make this paper relatively self-contained, we will of course focus our discussion on those aspects of the algorithm which might have to be modified to work in the internet. Any discussion of the proper routing algorithm to use in a particular Network Structure must begin with a consideration of just what characteristics we want the routing algorithm to have. That is, we must decide in advance just what we want the routing algorithm to do. Everyone will agree that the routing algorithm ought to be able to deliver data from an arbitrary source Switch to an arbitrary destination Switch, as long as there is a - 1 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen physical path between them. Or at least, the routing algorithm should make the probability of being able to do this arbitrarily high. However, this is a very minimal criterion (as indicated by the fact that everyone would agree to it). There are many other requirements we must place on the routing algorithm if we intend to design a robust and high performance Network Structure. We will present some requirements and some possible routing algorithms which fulfill the requirements to a greater or lesser degree. We hope that by the end of this paper, we will have made a case that our proposed routing algorithm does a better job of meeting more of the desired requirements than does any other that we know of. 4.1 Flexibility and Topological Changes One extremely important, though little noticed, feature that we should require of a routing algorithm is that it enable us to make arbitrary changes in the topology of the Network Structure, without the need to make manual changes in the internal tables of the Switches. This is a capability that has always existed in the ARPANET. IMPs can be added, removed, or moved around arbitrarily, and the routing algorithm automatically adapts to the new topology without any manual intervention. This seems simple enough, but it does place some significant constraints on the nature of the routing algorithm. For example, it immediately rules out fixed routing. By "fixed routing," we refer to any - 2 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen scheme where a set of routes to each destination Switch is "compiled into" each Switch. In fixed routing schemes, there is generally a "primary route", to be used when the Network Structure is not suffering from any outages, and a set of alternate or secondary routes to be used if some component of the primary route should fail. We know of one network which does use this sort of fixed routing, and as a result, they are forced to adhere to a very strict rule which allows them to add or remove Switches only once every six months. Certainly, we would not want to build such a restriction into the internet. Fixed routing also prohibits certain important day-to-day operational procedures that are often used in the ARPANET. For example, it is quite common, when an IMP is brought down for preventive maintenance, to "splice" that IMP out of the network by wiring together two of its modems. This causes two IMPs that ordinarily have a common neighbor to suddenly become direct neighbors of each other. (A similar function can also be performed by the telephone company, in case the power to the modems is shut off, or if the site cannot be reached.) This ability to preserve network bandwidth even when a site is down is quite important to robust network performance. Yet it is very difficult, if not impossible, to do this if the network has a fixed routing algorithm. It is not yet clear to what extent such day-to-day "firefighting" techniques will be applicable in the internet, but it certainly does not seem wise to design an - 3 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen internet routing algorithm which would be too inflexible to permit the use of such techniques. Another very useful capability which is difficult to combine with fixed routing is the ability to create arbitrarily configured test networks in the lab, and then to connect them to the real network. This is something that is done quite often in the ARPANET, usually for the purposes of testing out new software, and we will definitely need this capability in the internet in order to test out new gateway software (as well as to test out patches and bug fixes to the old). It is also worth noting that implementing a scheme of fixed routing with a primary route and alternates to be used in case of outages is not nearly as trivial as it may seem. Remember that it is not enough for each individual Switch, when its Pathway to a particular neighbor fails, to pick an alternate neighbor as its next hop to some destination. Rather, any outage requires ALL the Switches to pick alternates in a COORDINATED MANNER, so that the routing produced by the use of the alternate paths is loop-free. This is quite a difficult problem, and if there are a large number of Switches and Pathways, any combination of which could fail, this means that a very large number of alternate paths must be maintained, requiring a consequently large amount of table space. - 4 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen We will not be giving much serious consideration to the use of fixed routing in the internet. We mention it largely for the sake of completeness, and because there is a natural tendency, which we wish to oppose, to suppose that fixed routing must be simpler, cheaper and more reliable than dynamic routing. This tendency ignores the day-to-day operational problems involved in the use of fixed routing, as well as the difficult technical problems involved the the creation of fixed routing tables. Preserving maximum flexibility to make topological changes requires the Switches to be able to determine, dynamically, just who their neighbors are. (Remember that two Switches of a Network Structure are neighbors if and only if they are connected by a Pathway, i.e., by a communications path containing no intermediate Switch of the same Network Structure.) In the ARPANET, each IMP is initialized to know how many modem interfaces it has, and does not determine that dynamically. However, initialization only tells the IMP how many interfaces it has; it does not tell the IMP who its neighbor is over each interface. The IMPs determine who their neighbors are dynamically, via the line up/down protocol, and a line between two IMPs cannot come up unless and until each of the IMPs knows the identity of the other. The situation in the present Catenet gateways is quite different. Each gateway has a table of potential neighbors - 5 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen "assembled in." When a gateway comes up, it attempts to communicate (via a special gateway neighbor protocol) with each of the gateways in its pre-assembled neighbor table. Two gateways are considered neighbors only if this communication is successful. Gateways will also consider themselves neighbors of other gateways that communicate with them according to the gateway neighbor protocol, even if the other gateway is not in the pre-assembled neighbor table. This means that two gateways, G1 and G2, cannot become neighbors unless either G1 is in G2's pre-assembled neighbor table, or G2 is in G1's pre-assembled neighbor table. Of course, in a real operational environment, it is very important to ensure that site-dependent information is not assembled or compiled in. Rather, it must be separately loadable (over the network itself) by the Network Control Center, or whatever equivalent organization we create for operating the internet. In fact, site-dependent information ought to be preserved over reload of site-independent information, and vice versa. (This discipline is followed in the ARPANET.) Designing the gateways according to this discipline is a very non-trivial task, which must be planned for by the gateway designers at the earliest stage of gateway design. Otherwise, we will build for ourselves a very difficult set of unnecessary operational problems. - 6 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen However, it is not a very good idea to have a fixed table of neighbors in each Switch, even if this table is separately loadable. This just does not give us the flexibility we desire for making arbitrary topological changes. If there has not yet been any difficulty with the Catenet's current scheme, that is probably because of the small number of gateways and component networks in the current internet environment. As the number of gateways increases, the need to have them dynamically determine who their neighbors are becomes increasingly more important. However, having gateways discover (dynamically) who their neighbors are is a more difficult problem than having IMPs discover who their neighbors are. The interfaces on the IMPs function as point-to-point lines, so there can be at most one other IMP on the other end of a line, and any data sent out that line can be expected to reach just that IMP. Therefore it is not very hard for an IMP to discover which IMP is at the other end. An IMP simply sends its identity (a unique number which it reads from its hardware configuration cards) down the line in a message, and if the line is operational, the message must reach the IMP on the other end. For two gateways connected by a packet-switching network, the problem is more complicated, because, unlike telephone circuits, a packet-switching network is not a point-to-point line with a relatively transparent interface. In order for one gateway to identify itself to another, it must be able to address the other, using the Access - 7 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen Protocol of the packet-switching network which serves as the Pathway between them. This seems to mean that for a gateway to be able to send its identity to a neighbor, it must already know the neighbor's name. This seems like Catch-22 -- there is no way to determine dynamically who your neighbor is, unless you can address him, but there is no way to address him unless you already know who he is. This problem can be made more tractable through the cooperation of the packet-switching networks underlying the Pathways which connect the gateways. A packet-switching network could recognize that certain of its own components (which might be either Switches or Hosts within its own Network Structure) are also Switches within a Network Structure which is one level higher in a hierarchy. For example, in the ARPANET, there might be some special protocol (call it the "gateway discovery protocol"), carried out on the host-IMP level, by which certain hosts identify themselves as internet gateways. Whenever a gateway connected to a particular IMP comes up or goes down, this information could be broadcast to all other IMPs. Whenever a gateway comes up, the IMP it is connected to could tell it which of the other hosts are internet gateways. In this way, the IMPs could keep the gateways informed as to which other gateways are up or down at any particular time. This sort of scheme eliminates the need for the gateways to know in advance who their neighbors might be, and moves the responsibility for keeping - 8 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen track of the gateways and their up/down status to the packet-switching network itself, which is better equipped to carry out this responsibility. Such a scheme would not be very difficult, in principle, to build into the ARPANET. Information about gateways could be subsumed into the routing information. That is, an IMP connected to a gateway could represent the gateway as a stub node, and report on it as such in its ordinary routing updates. (Of course, this is only feasible if the number of gateways is relatively small when compared to the number of IMPs. Otherwise the additional overhead this would add to the ARPANET's internal routing algorithm would make the scheme infeasible. However, it does seem likely that the number of gateways on the ARPANET will always be much smaller than the number of IMPs.) This scheme would automatically cause the information about the gateways to be broadcast to all IMPs as part of the routing updates. (See section 4.5 for a description of the routing update procedure.) Each IMP which is connected directly to a gateway could forward information about other gateways to its own gateway as the information is received. The most difficult problem might be to get enough "security" in the gateway-to-IMP protocol so that only real gateways could declare themselves to be gateways. (Some of the issues involved in preventing a host from "fooling" the network into thinking it is a different host than it really is are discussed in IEN 183. See the discussion of LAD messages. - 9 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen However, that note does not consider the real issue of security that arises here.) This scheme for having gateways dynamically discover their neighbors through the cooperation of the networks underlying the internal Pathways of the internet is an important step towards the solution of the "flying gateway" problem. The flying gateway problem is the following. Suppose that N is a packet-switching network which is one of the component networks of the internet. Now suppose that due to some sort of emergency or natural disaster, N becomes partitioned into two "pieces", call them N1 and N2, and that this partition is expected to last for a significant amount of time. If H1 is a Host in N1, and H2 is a Host in N2, then H1 and H2 will no longer be able to communicate through the network N. (Of course, H1 and H2 might still be able to communicate though the internet, if there is an internet gateway on N1 and an internet gateway on N2, and a route between these two gateways other than the "direct" route via N. In fact, the addressing scheme proposed in IEN 188 will automatically cause traffic from H1 to H2 to be delivered over this alternate route, AS LONG AS H1 SUBMITS THIS TRAFFIC TO ONE OF THE INTERNET GATEWAYS CONNECTED TO N1, RATHER THAN TRYING TO SEND IT DIRECTLY TO H2 OVER THE NETWORK N.) However, in some cases, there may be no such alternate route, or else its characteristics might be unsatisfactory. In addition, it must be remembered that the partition of network N might actually result in the partition of - 10 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen the internet itself, so that some pairs of Hosts which ordinarily communicate over the internet can no longer reach each other. In such cases, it might be desirable, at the level of the internet, to treat N1 and N2 as separate component networks, and to place an internet gateway between them so that internet traffic can flow from N1 to N2. One possible scenario is for this new gateway to be an airborne packet radio, hence the name "flying gateway." If a flying gateway can be connected to both N1 and N2, and if the network N has a gateway discovery protocol of the sort we have been advocating, then the flying gateway need merely come up on N1 and N2, declaring itself to be an internet gateway. The gateway discovery protocol run in the network pieces N1 and N2 will cause the other internet gateways in N1 and N2 to become aware that they have a new neighbor, the flying gateway. Once the gateways in N1 and N2 become aware of their new neighbor, it automatically begins to participate in the routing algorithm (see section 4.5 for details of the routing updating algorithm that brings this about), and routing automatically begins to use the flying gateway for store-and-forwarding internet traffic. Thus any partition of the internet is automatically brought to an end. In addition to using the flying gateway as a transit or intermediate gateway for internet traffic, it may also be desirable to use it as a destination Switch in the internet. - 11 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen That is, it may be desirable to allow the other internet Switches (gateways) to use the flying gateway as the address to which they route traffic for Hosts in N1 or N2. This is slightly more complicated than simply using the flying gateway as an intermediate Switch. The logical-to-physical address translation tables in the gateways (we are assuming the addressing scheme proposed in IEN 188) will not, in general, map any Host logical addresses into the address of the flying gateway, which after all is not ordinarily on the internet. However, as long as the flying gateway indicates that it is a special, flying, gateway, and as long as this information is made known to all the other gateways, this problem is simple enough to solve. If F is a flying gateway, and G is an ordinary gateway, and F and G are neighbors, then any logical address which maps to G but cannot currently be reached through any ordinary gateway should be mapped to F. (As we shall see, the routing algorithm we propose makes available to each Switch all information about which pairs of Switches are neighbors.) Attempting to reach the destination Host via the flying gateway F will either be successful, or else should result in the return of a DNA message, which would indicate that the Host cannot be reached from the flying gateway either. The only remaining problem is for the flying gateway itself to determine which of the two pieces of the partitioned network contain some particular Host for which it is the destination Switch. Any data for destination Host H which - 12 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen arrives at Switch F can potentially be sent to either piece of the partitioned network. The situation is no different than the problem of how an ordinary gateway, which has two Pathways to a particular Host, one of which is non-operational, decides which one to use. Note that the individual Hosts do not need to be aware at all of the existence of the flying gateway, since the logical addressing scheme automatically finds the right physical address. Of course, for this mechanism to be at all effective, there must be a robust and efficient Host-Switch up/down protocol, which works through the cooperation of the network underlying the Pathway between Host and Switch. Unfortunately, not every component network of an internet can be expected to cooperate this way in a "gateway discovery protocol." In fact, if two Switches of the internet Network Structure are connected by a Pathway which is itself an internet, rather than a single packet-switching network, then this sort of cooperation in the "gateway discovery protocol" might be extremely difficult if not impossible. It seems though to be quite important to get the communications media which underlie the Pathways to participate in such a protocol, for that significantly increases both the reliability and the flexibility of the internetting scheme. It does not seem possible for Switches which are connected by uncooperative Pathways to determine dynamically who their neighbors are. In such cases, we may then have to live with hand-built neighbor tables (as in the - 13 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen present Catenet), and a protocol which the Switches attempt to carry out with their neighbors to see which potential neighbors are really reachable. Networks which do not provide a gateway discovery protocol, however, cannot be patched together with a flying gateway if they should partition. Even for Switches which are connected by cooperative Pathways, it is desirable to have a protocol which the Switches attempt to run with each one of their neighbors, to see whether they really can send and receive data to or from each neighbor. Suppose, for example, that two Switches are connected by a Pathway which is a very congested network. In such a network, the messages which are used to tell the internet Switches who their "neighbors" are might well be flowing, even though the congestion prevents ordinary (user) data from flowing. This is not at all unlikely, if the gateway discovery protocol makes use of the network's routing updates, which would probably be of much higher priority than ordinary data packets. Since we don't want to use this Pathway for internet traffic unless it can carry data, some independent means of determining this may be needed. The situation is somewhat more complicated if the Pathway is a packet-switching network with different "acceptance classes", so that only certain classes of traffic are accepted at any given time, depending perhaps on the internal loading conditions of the network. If a Pathway is only accepting a certain sub-class of data traffic, any internet Switches which are connected to that - 14 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen Pathway must be able to determine which classes are being accepted (presumably the network underlying the Pathway will inform the Switches as to any access restrictions), and this information will have to be fed back into the internet routing algorithm, so that traffic which cannot be placed on a certain Pathway is not routed there nonetheless. The reader will doubtless have noticed that these considerations, of determining who one's neighbors are, and of determining whether the Pathway to each neighbor is operational, are quite similar to the considerations adduced in IEN 187 in the discussion of Pathway up/down protocols to be run between a Host and a Switch. What we have been discussing is really an inter-Switch Pathway up/down protocol. The gateway discovery protocol corresponds to what we called a "low-level up/down protocol", and the type of protocol discussed in the previous paragraph corresponds to what we called the "higher-level up/down protocol." 4.2 Why We Cannot Require Optimality What else would we like the routing algorithm to do, besides giving us the maximum flexibility to make topological changes? Generally, we tend to feel that a really good routing algorithm should optimize something, delay or throughput, for example. However, true optimality is really not possible. If we are given a complete description of a network, including its topological - 15 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen structure, and the capacities and speeds of all its lines and Switches, and if we are also given the traffic requirement (as a Switch-Switch traffic matrix which tells us how much traffic each Switch will originate which is destined for each other Switch), and if the packet inter-arrival rates and sizes vary according to certain specific probabilistic distributions, and if the traffic is in a steady-state condition, it is just a mathematical problem to devise a set of routing tables for the Switches which will minimize the network average delay. Applied mathematicians have devoted a great deal of effort to devising algorithms to produce this optimal solution. There are a large number of problems with attempting to use this sort of "optimal routing algorithm" as the operational routing algorithm of a network: 1) Packet arrival rates and sizes do not necessarily vary according to the probabilistic distributions which are assumed by optimal routing algorithms. 2) Optimal routing algorithms are ALWAYS based on mathematical models of the relationship between delay and throughput which are not supported by empirical data. 3) Actual traffic requirements are quite variable, and may not really approach a steady-state for a long enough period of time to enable true optimization. Traffic requirements are also generally unknown, and difficult to predict or measure. - 16 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen 4) Most algorithms to compute the optimal routes are real number crunchers, and require large floating point computers. These algorithms would have to be run in a central location, producing routing tables for all Switches, and then distributing them somehow (centralized routing), with consequent problems of robustness and overhead. 5) There are distributed optimizing algorithms (e.g., Gallager's algorithm), but they are not implementable. That is, the proofs of these algorithms make assumptions which could not be made to hold in the real software and real hardware of a real network. Hence the algorithms would not be expected to give optimal results (or even anything close to optimal) in real networks. Furthermore, such algorithms seem to rely on updating protocols which are insufficiently robust in the operational environment. These algorithms also seem to contain parameters whose precise settings are quite important to proper performance, but whose most appropriate values are unknown and quite difficult to determine. We realize that these rather brusque comments may make it seem like we are giving short shrift to the consideration of optimizing algorithms. We have made these comments simply in - 17 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen order to state our reasons for not giving further consideration to such algorithms. Arguing in support of these reasons, however, would require another paper. Another problem with optimal routing algorithms which is more specific to the internet environment has to do with the requirement that the capacities of the network components be known. With telephone circuits as the "links", it is possible to assign a fixed capacity and fixed propagation and transmission delays to each link. With packet-switching networks as the "links", it is doubtful that this even makes sense. If two gateways are connected by the ARPANET, there is no number we can assign as the capacity of the "link" connecting the gateways! The amount of throughput that can be sent between two gateways via the ARPANET is a highly variable quantity, with dependencies on hundreds of other things going on within the ARPANET. It is hard enough to get a handle on just what other things the throughput of a given connection depends on; we certainly can't express this dependency as a function, or assign numerical values to the "capacity." This seems to mean that currently known optimal routing algorithms are really quite useless within the context of the internet. Of course, they are not too useful even in individual networks, when considered as the operational routing algorithm of the network. They are, however, sometimes useful as a benchmark to which the operational routing algorithms can be compared. That is, it is a meaningful question to ask, - 18 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen "how close does SPF routing in the ARPANET come to optimal?", where "optimal" is defined as the result produced by some optimal algorithm, run off-line. Within the context of the internet, it is difficult even to give meaning to this question. There is no mathematical model of the internet to which we can appeal. This also raises an interesting question about the design of the internet topology, i.e., where to place the gateways and how best to interconnect them. The usual mathematical techniques for trying to optimize network topological design also assume some fixed assignment of capacity to the links; it's not obvious how such techniques can be extended to the internet. 4.3 Some Issues in SPF Routing Even if we give up the quest for optimal routing, there are still a number of substantive things we can require of a routing algorithm. For example, we would like to have some form of distributed routing, rather than centralized routing, simply for reasons of robustness. ("Distributed routing" refers to any routing scheme in which each Switch computes its own routing table.) What this means basically is an algorithm based more or less on the routing algorithm of the ARPANET, i.e., an algorithm which runs in each Switch and computes the shortest path to each other Switch, based upon (dynamically determined) knowledge of the connectivity of the internet Network Structure, and an assignment of "length" to each Pathway that connects two - 19 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen Switches. Routing algorithms of this sort can be characterized by three separable components: (a) the algorithm used to compute the shortest path, given the assignment of lengths to Pathways, (b) the algorithm used to assign a length to a given Pathway, and (c) the protocol used by the Switches for sharing routing information. The most efficient shortest path algorithm that we know of is the SPF algorithm of the ARPANET [1,3] (which is basically just a modification of Dijkstra's shortest path algorithm), and we propose to base an internet routing algorithm on this. There are other algorithms for performing a shortest path computation, but the SPF algorithm seems to dominate them. One possible alternative to SPF would be something based on the distributed computation of the original ARPANET routing algorithm (which is the basis for the current Catenet routing), but we have studied that algorithm at great length and in great detail and it is inferior to SPF in a large variety of ways [3]. There are many other shortest path algorithms (such as Floyd's algorithm, or the algorithm advocated by Perlman in IEN 120), but the efficiency of these algorithms does not compare with that of SPF. We will not consider the issue of choosing a shortest path algorithm any further. In the ARPANET, the "length" assigned to a line is just the average per-packet delay over that line during a preceding period - 20 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen of ten seconds. The current Catenet routing algorithm assigns a length of 1 to each Pathway, irrespective of the delay. Other possible assignments of lengths to Pathways are also possible. We will recommend the use of measured delay as the best metric for the internet routing algorithm to use, and we argue for this proposal in sections 4.3.1 and 4.3.3. Section 4.3.2 covers the related topic of "load splitting." (One purpose of that section is to show that the two topics are indeed related, and in ways more subtle than generally realized.) In section 4.4, we discuss some of the issues in the design of an algorithm to measure the delays. In the ARPANET, a routing update generated by an IMP A specifies the average per-packet delay on each of A's outgoing lines. Every update generated by an IMP is sent to every other IMP in the network, not just to the neighboring IMPs, as in the Catenet routing algorithm. This updating protocol, and its applicability to the internet, are discussed in section 4.5. Although a routing scheme can be divided into a number of separable components, it is important to keep in mind that the ultimate characteristics of the routing scheme will result from the combination of the components. A routing scheme must be judged as a whole. The reader should try to focus throughout on how the components work together, and resist the temptation to judge each component separately. - 21 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen 4.3.1 Min-Hop Routing (Why Not to Use it) The simplest routing scheme which is based on having each Switch compute its shortest path to each other Switch is "min-hop" routing. In min-hop routing, all Pathways are assigned unit length, so that the shortest path between two Switches is just that path which has fewer Pathways than any other. (Generally, ties are broken arbitrarily.) This sort of routing is used in the current Catenet, where traffic is routed through the fewest possible number of intermediate networks (or equivalently, through the fewest number of intermediate gateways.) This form of routing is quite simple, and does not require us to worry about anything as complicated as detecting changes in load or delay in remote components of the Network Structure. Such changing conditions within the Network Structure have no effect at all on the routing. This form of routing can be done with the minimal amount of overhead (in terms of the need to send routing updates from Switch to Switch). Updates need to be sent only when the Pathways go down or come up. Any algorithm which attempts to be more responsive to changing conditions in the Network Structure than min-hop routing still needs these up/down updates, plus more besides. Min-hop routing is definitely what one would use if one wanted to put in a "quick and dirty" routing algorithm, and put off worrying about complexities until some unspecified later time. It is also possible to argue for min-hop routing in the internet on more principled grounds, as follows: - 22 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen "In general, it is not unreasonable to expect that the more component networks an internet packet goes through, the less likely it is to get to its destination, and the longer its delay is likely to be, if it does reach its destination. We might expect that the number of component networks a message goes through would generally correlate fairly high with the delay of the message, and would generally correlate fairly low with the obtainable throughput of a host-host transfer." Unfortunately, this sort of reasoning is only valid when applied to a Network Structure consisting of homogeneous Pathways, which have similar characteristics with respect to delay, throughput, and reliability. This is rather unlikely to be the case in the internet, whose distinguishing characteristic is the heterogeneity of its Pathways. Where the Pathways of a Network Structure have widely varying characteristics, delay and throughput are not very likely to correlate well simply with the number of hops. It is true that the delay-oriented routing of the ARPANET generally gives the min-hop paths. (Remember, though, that the ARPANET, unlike the internet, has generally homogeneous Pathways.) Min-hop routing is all right for the "normal" case, where there are no areas of congestion in the network or internet, no areas where the delay is unusually high compared to other areas. Routing, however, is no different from other computer system applications, in that a scheme that works well only in the normal case just is not robust enough to be satisfactory. (Think of a magnetic tape driver which works in the normal case, where no tape errors are encountered, but which - 23 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen crashes the system in the presence of "unusual" events, like errors on the tape. Such a driver may be acceptable if one accesses one tape a month, but not if one needs to read or write ten tapes a day. The analogy is that min-hop routing may perform acceptably in an experimental network with little traffic, but is much less likely to be acceptable in a heavily loaded operational network.) It is extremely common for some area of the network to be much more congested than another, so that traffic flows which traverse a particular area experience a very much longer delay (and lower throughput) than traffic flows which avoid that area. Significant imbalances in load cause significant reductions in the correlation between hop-count and performance. Such imbalances may not be present in a network initially, but if the ARPANET experience is any indication, imbalances start to occur with increasing frequency as network utilization grows. If the routing algorithm cannot account for such imbalances, network performance problems will start to occur with ever-increasing frequency as the network gains more users. This was our experience with the original ARPANET routing algorithm. For all its widely publicized faults, it provided generally acceptable performance as long as the network was very lightly utilized, but its failures became more and more evident as the ARPANET shifted from a research prototype to a communications utility. If we expect our network or internet to be heavily used by real users who are sending real data that they really need for their - 24 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen applications, OUR ROUTING ALGORITHM WILL HAVE TO BE ROBUST ENOUGH TO DETECT EXCEPTIONAL CONDITIONS AND TO ROUTE THE TRAFFIC IN SUCH A WAY AS TO MINIMIZE THE EFFECT OF THE EXCEPTIONAL CONDITIONS. IF AREAS OF THE NETWORK BECOME CONGESTED OR EXPERIENCE UNUSUALLY LONG DELAYS, THEN WE HAVE TO BE ABLE TO ROUTE THE TRAFFIC AROUND THESE AREAS, instead of blindly sending traffic into congested areas. At a certain level of congestion, sending traffic into a congested area is like sending it into a black hole; the traffic will never leave the area to progress to its destination. Sending traffic into a congested area also induces a feedback effect, causing the congestion to spread farther than it otherwise would, and making it that much less likely that the congestion will dissipate. Any routing algorithm which cannot take this into account will not be robust enough to survive in a real operational environment. Min-hop routing also has another disadvantage which is more specific to the internet environment. Let N1, N2, and N3 be three networks, and suppose we have to get some traffic from N1 to N3 by using N2 as a transit network. Let G12 be a gateway connecting N1 and N2, let G23 be a gateway connecting N2 and N3, and let G2X be a gateway which connects N2 to some other unspecified network. If we use min-hop routing, then any traffic which must go from G12 to G23 must go "directly", through network N2, without stopping at G2X, because the path G12-G2X-G23 has one more hop than the path G12-G23. Perhaps this doesn't seem like - 25 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen much of a restriction; why would one want to have traffic stop at the intermediate gateway G2X when it could go directly from G12 to G23? Actually, two possible reasons come to mind immediately. The first reason has to do with the possible effects of the network's end-end protocol. In the ARPANET, for example, a source host is allowed to send only 8 messages to a given destination host before receiving the RFNM for the first of the 8 messages. Hence the throughput obtainable on a host-host connection is inversely related to the amount of time it takes to get a RFNM from the destination host to the source host. It follows that higher throughputs are obtainable between hosts that are "near" each other than between hosts that are "far" from each other. It is also possible that G12 and G2X will be near to each other, and that G2X and G23 will be near to each other, but that G12 and G23 will be far from each other. So the throughput obtainable in a transfer between G12 and G23 may be less than that obtainable in a transfer between G12 and G2X, and less than that obtainable in a transfer between G2X and G23. It follows that the throughput obtainable between G12 and G23 via G2X may be higher than the throughput obtainable between G12 and G23 directly. Basically, by using an additional gateway hop, the ninth message from G12 can be put into the network while the first message is still in transit from G2X to G23, while without the intermediate hop, this is not possible. Of course, the best solution to this sort of problem would be to fix the end-end - 26 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen protocol so that it does not impose this sort of restriction. Our present point, however, is that our routing algorithm should not rule out the possibility of this sort of strategy. Note that by using an intermediate gateway hop, we might not only increase throughput, but also decrease the delay (since a ninth message would not be blocked as long.) (It is interesting to think about whether this sort of strategy might not be useful entirely within the ARPANET.) Another possible scenario in which an intermediate gateway hop might be useful occurs if the intermediate gateway is multi-homed. It is possible that an intermediate gateway will be homed to two IMPs which are distant from each other within the network. If so, the intermediate gateway may be used as an "expressway" around a congested area of the network. If we replace the intermediate gateway G2X with two gateways G24 and G42, we also have the possibility of sending traffic from N1 through G12 into N2 to G24 through N4 to G42 into N2 to G23 and thence into the destination network N3. This is akin to the oft-discussed expressway problem, but cannot be handled within the framework of min-hop routing. Of course, it might be very difficult to take account of such factors, but one would not want to have a routing scheme which makes it absolutely impossible. - 27 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen Still another disadvantage of min-hop routing in the Catenet is the following. The current Catenet routing algorithm, when faced with three gateways on the same network, considers the three to be equidistant. However, the delay and throughput obtainable from gateway A to gateway B may be very much different than the throughput obtainable from gateway A to gateway C. In a large distributed network like the ARPANET, some pairs of hosts are connected by high-performance paths, and some by low-performance paths (either because they are separated by many hops, or because the path between them is under-trunked, etc.) Allowing the routing algorithm to be sensitive to this could potentially have a large impact on the internet performance. There may not be any network that actually uses min-hop routing, except for the Catenet. There are, however, networks that use a variant of it, which we might call "fixed cost" routing. In fixed cost routing, each Pathway is still assigned a constant length, but not all Pathways are assigned the same length, and some Pathways have a length which is not equal to 1. In a scheme like this, one attempts to assign values of length so that slow-speed lines appear longer than high-speed lines, reliable lines appear shorter than unreliable ones, and lines with high propagation delays appear longer than lines with low propagation delays. This sort of routing is used in DATAPAC and in DECNET. Both those network architectures have routing algorithms based on the original ARPANET routing algorithm. The - 28 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen designers of those architectures apparently realized that min-hop routing is not very satisfactory if the links are not of relatively homogeneous quality, but were probably wary of the problems that the ARPANET's original algorithm had in adapting to changing traffic conditions. They avoided these problems by not adapting at all to changing traffic conditions. Of course, this is the weakness in fixed cost routing. It may be better than min-hop routing in a lightly loaded Network Structure with heterogeneous Pathways, but in a heavily loaded Network Structure with unbalanced load it really is no better than min-hop routing, and will still send traffic right into congested areas. We have been emphasizing the claim that routing ought to be able to detect congestion and route traffic around it. Some may wonder whether we are confusing the proper functions of routing with the proper functions of congestion control. That is not the case. Congestion control schemes generally try to limit the amount of traffic entering a network so as to prevent or to reduce the overloading of some resource or of the whole network. When congestion actually exists in the network, however, it is the job of routing to try to send traffic around the congested areas; otherwise the routing actually causes the congestion to increase. Of course, one might attempt to design the routing algorithm under the assumption that there will be a congestion control scheme that will make congestion impossible. However, such a design could not be very robust. If we want to build a - 29 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen robust Network Structure which will continue to operate under a variety of unforeseen conditions, then we want each software module or protocol to be designed with the assumption that the other modules or protocols will be less than optimal. The resulting system will be much less prone to system-wide failure than one which is designed so that no part of it will work at all unless every part of it works perfectly. Although we will not be discussing explicitly, in this paper, any schemes for controlling the amount of traffic which is input to the internet, that doesn't mean that we can ignore the way in which the routing algorithm affects and is affected by the existence of congestion. Particular problems related to overload of network resources should be discussed in whatever context they arise in, without worrying about whether the problem is properly called "congestion control" or "routing." There is in general no way of telling in advance whether the best solution to a particular problem is a routing solution or a congestion control solution, and putting labels on the problems just restricts our thinking. 4.3.2 Load Splitting Routing in the ARPANET has always been "single-path routing." We mean by this that at any given moment, the ARPANET's routing algorithm provides only a single path between each pair of IMPs. All traffic which enters the network at some particular time, originating at IMP A and destined for IMP B, - 30 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen will travel over the same path. Actually, this statement is somewhat oversimplified, since there might be a change of routes while some traffic is already in transit. The point, however, is that at any given time, each source or intermediate IMP will send all traffic for a particular destination IMP to a unique neighbor; it cannot split the traffic among several neighbors. Routing in the Catenet is currently somewhat different. Suppose gateway A has two neighbors, B and C, and has some traffic to send to gateway E. The routing algorithm run in A assigns a distance value to the path to gateway E via neighbor B and a distance value to the path to E via neighbor C. If the distance from A to E via B is the same as the distance from A to E via C, then gateway A will alternate between use of B and C when sending traffic to E. That is, A makes simultaneous use of two distinct paths to E. Such a scheme would be somewhat more difficult to put into SPF routing, because in SPF routing, no assignment of distance values from A to E via each of the two neighbors is generated. Rather, only one path is computed, via one of the neighbors, and only the distance on that one path is known. Distance on other paths is not computed by the SPF algorithm. (On the other hand, the SPF algorithm generates the entire path, so that each Switch knows which other Switches its traffic will be routed through on the way to the destination. The original ARPANET algorithm does not do this, but only tells each Switch which of its neighbors to use when sending traffic to the destination.) - 31 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen What is the significance of this? It seems to be commonly regarded as obvious that multi-path routing, or load splitting, is an important advantage, so that routing algorithms that permit it are better than routing algorithms that do not. However, when one asks advocates of multi-path routing why it is better than single-path routing, a very common answer seems to be, "Multi-path routing is better because it provides multiple paths." This sort of answer is rather superficial. Multiple-path routing is NOT a goal in and of itself; IT IS IMPORTANT ONLY INSOFAR AS IT SERVES SOME MORE FUNDAMENTAL GOAL. If a multi-path routing algorithm results in smaller delays or larger throughput than some other algorithm, then that is a good reason for favoring it over the other algorithm. Now, it is certainly true that any routing algorithm which OPTIMIZES network delay or throughput will be a multiple-path algorithm. THE CONVERSE, HOWEVER, IS NOT TRUE. A routing algorithm which provides multiple paths does not necessarily optimize delay or throughput. In fact, merely because a routing algorithm provides multiple paths, it does not follow that it provides better performance in any respect than some other routing algorithm which provides only a single path between a pair of Switches. An algorithm which provides a single good path may be far superior to an algorithm which provides several poor ones. To see this, let's look at some possible effects of the load splitting in the Catenet routing algorithm. Let A, B, C, D, and - 32 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen E be five gateways, and suppose that there are two possible paths from A to E, namely ABDE and ACDE. The Catenet routing algorithm would regard these two paths as equidistant, since that algorithm regards two paths as equidistant if they contain the same number of intermediate gateways. Therefore gateway A would perform load splitting on its traffic to E, sending half of the traffic to neighbor B and half to neighbor C. Does this provide more throughput than the use of a single one of these paths? Not necessarily. If the bottleneck on the paths from A to E is the Pathway DE, then the use of these two paths provides no more throughput than the use of either one alone. In fact, if DE is the bottleneck, the use of the two paths will probably result in lower throughput than the use of a single path. The use of several paths increases the likelihood of the packets from A to E arriving out of order at the destination host. Yet as more packets arrive out of order, more TCP resources are needed to handle them, and the TCP just has that much more work to do. TCP buffers that are occupied by out-of-order packets cannot be "allocated" for receiving more packets, so acknowledgments must be delayed, and windows must be kept smaller. The result of all this will be higher delays and lower throughputs. This was probably not the intention of load splitting, but is a likely consequence of it. Suppose there really are two independent paths from A to E which are "equidistant", say ABDE and ACFE. Even here, sending - 33 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen half the packets on each path may only degrade performance. To see this, suppose each of the Pathways AB, BD, DE, AC, and CF has a capacity of 50 kbps, but that link FE has a capacity of 10 kbps. Suppose also that we want to send 50 kbps of traffic from A to E. If we alternate packets between these two paths, by trying to send 25 kbps of traffic each way, we will be able to get at most 35 kbps of traffic through to the destination, and we will cause severe congestion on link FE (which will probably result in its being able to carry even less than the rated 10 kbps, further lowering the network throughput.) Had we used only the single path ABCD, we would have been able to pass more traffic. Again, we see a situation where the use of load splitting can reduce throughput and increase delay. This sort of problem might at first appear to be too unlikely to be worth worrying about. However, it has already occurred in the Catenet, and has caused a significant problem. In fact, in the Catenet's actual problem, half of the traffic was sent on a path whose capacity was sufficient to handle all the traffic, and the other half of the traffic was sent on a path whose capacity was essentially zero (because a network partition made the destination host unreachable on that path). In this case, load splitting resulted in the throughput being cut in half, as half the traffic was routed down a black hole! The problem was "solved" by eliminating one of the two possible paths, thereby eliminating the possibility of load splitting. - 34 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen However, this does not seem like a proper way to deal with this problem in the general case. The Catenet's load splitting has been defended from this latter objection as follows: "If there were no load splitting, maybe all the traffic would have been sent into the black hole, not just half." This is less a defense than a sad commentary on the state of the Catenet routing; to accept this sort of defense is just to give up entirely on the problem of internet routing. Someone may reply to our first criticism of load splitting by saying "maybe the bottlenecks will be Pathways AB and AC, rather than DE, in which case the use of two paths does increase the throughput." This reply is correct, but not very important. The sort of load splitting done in the Catenet might, by pure chance, increase throughput in some particular case. The point though is that it is no more likely to increase throughput than to decrease it. Certainly there is no reason to suppose that the cases in which it might help are any more likely to occur than the cases in which it hurts. In our experience with the ARPANET, schemes that seem a priori as likely to hurt as to help always end up hurting more than helping. (In networking, Murphy's law is more than just a joke.) Choosing equidistant paths for load splitting will generally result in paths which are only small variants of each other (if it results in any paths at all, since there are not necessarily several equidistant paths between a - 35 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen pair of Switches), and there is no reason to suppose that the bottleneck will not be common to each path. Even if we do get two paths which do not share a bottleneck, unless we try explicitly to apportion the flows to the relative capacities of the two paths (rather than just dividing the traffic 50-50), we will not, in general, gain any increase in throughput. In chapter 4 of [6], we actually devised a multiple-path routing scheme, based on SPF, whose purpose was to maximize throughput. In this scheme, we make sure that any set of simultaneously used paths between two Switches are "bottleneck-disjoint", (i.e., they don't share a bottleneck), so that we know that we can get more throughput by use of several paths. We also devised a flow apportionment scheme which attempts to match flows (or parts of flows) to the available capacity of each path. Anyone interested in seeing what it really takes to do multi-path routing should look at that chapter. The scheme proposed there is quite complex, however, and it is not obvious that it will work. Some simulation work will eventually be done on it. Until that sort of algorithm is much better understood, it would not be very wise to use the internet to experiment with it. It will be difficult enough to adapt a well-understood and much-used routing algorithm (like that currently in the ARPANET) to the internet environment. The internet is certainly not a place for experimenting with new and untried routing algorithms. - 36 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen Although it is quite difficult to design a multi-path routing procedure that results in significant improvements of delay or throughput over single-path routing, there are other reasons for requiring multiple paths between a pair of Switches that are more easily dealt with. For example, we may be required to have different paths between a pair of internet gateways because of ACCESS CONTROL RESTRICTIONS. That is, certain classes of packets may not be allowed to traverse certain classes of networks, so that different routes would be required for the different classes of traffic. We may also decide that different types of service that may be requested by the user should travel over different paths, even if the source and destination gateways are the same for the different traffic classes (e.g., maybe we don't want to use multi-hop satellite networks for interactive traffic.) This is easily handled within the framework of SPF routing. Remember that the SPF algorithm produces the shortest path to a destination, based on an assignment of lengths to the Pathways. Rather than simply assigning a unique length to each Pathway, we can assign a set of lengths, indexed by traffic classes. We can then produce a set of routing tables, indexed by traffic type, such that the routing table for a given traffic type contains the "shortest" path, based on the length assignments for that traffic type. For example, if traffic class C is not permitted to traverse Pathway P, the length of P, indexed by C, can be set to infinity. This ensures that that - 37 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen Pathway will not be part of any path found in the routing tables indexed by C. We even have the flexibility to assign to P a length which, while not infinite, is much larger than the length of any other Pathway. In this case, that Pathway will be used for traffic of class C only if EVERY path to the destination includes it (i.e., only if it can't be avoided). This sort of load splitting might be quite important in the internet, and is also quite simple to handle. 4.3.3 Delay vs. Throughput In the ARPANET, each IMP measures the average delay per packet on each of its outgoing lines. This average delay is assigned as the "length" of the line, and shortest paths are computed on that basis. We have studied the performance of this algorithm a great deal [5]. It tends to use min-hop routes under conditions of light or of uniform load. However, it does seem to take account quite well of the varying delays that are produced by lines of different transmission or propagation delay characteristics. Since congestion causes large increases in the delays, congestion is generally detected by the routing algorithm, and traffic really is routed around congested areas when that is possible. While we cannot claim that our routing algorithm gives the optimal delay, the characteristics that it does have seem to be the characteristics that we would really like to see in any robust, operational network, and particularly - 38 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen in the internet. The routing tends to be stable on what are intuitively the best paths, except when exceptional conditions arise which make it clear that some other path is likely to provide better performance. It is this sort of routing which we propose for the internet. Before discussing further the use of delay-oriented routing in the internet, we would like to briefly consider the issue of throughput-oriented routing. In the previous section, we argued against the use of multi-path routing as a means of optimizing throughput, largely on the grounds that doing it right is extremely difficult (much more so than one might at first think), that the ways of doing it right are quite poorly understood, and that the internet is not a good testing ground for new and untried algorithms. However, one often hears that there are high throughput applications (bulk traffic) for which delay doesn't matter, and one may wonder whether there is not some kind of single-path routing which is more appropriate for such applications than is delay-oriented routing. One scheme that is very commonly suggested is that of routing traffic on the path of maximum excess capacity, instead of on the path of least delay. Given an algorithm for determining the amount of excess capacity on each Pathway (which could be quite difficult to design for the internet environment -- how do we know what the excess capacity of a packet-switching network is?), it is no - 39 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen difficult matter to modify the SPF algorithm to produce the paths of maximum excess capacity. However, it would not be a good idea to use the resultant routes for bulk traffic. For one thing, we must understand that such a routing algorithm would not maximize total network throughput. (By "maximizing total network throughput", we mean maximizing the amount of traffic that the network can handle.) Suppose, for example, we wanted to send 40 kbps of traffic, and had the choice of using a one-hop path with excess capacity of 50 kbps, or a 10-hop path, each of whose links had an excess capacity of 100 kbps (so that the total composite path has an excess capacity of 100 kbps). By using the shorter path, we use up a total of 40 kbps of network capacity, capacity which is now unavailable for other traffic. By using the longer path (which is the path of maximum excess capacity), we use up a total of 10x40 kbps (40 kbps per hop), thereby using up a total of 400 kbps which is no longer available for other traffic. In terms of maximizing the total network throughput, we do better by using the one-hop path, rather than the path of maximum excess capacity. Maybe we are less interested in maximizing total network throughput than in finding a path for some particular traffic flow which has enough capacity to handle the required throughput of that flow. We still would not want to use the path of maximum excess capacity, for that path might have a delay which is much too long. Although we often hear that certain classes of traffic - 40 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen (e.g., file transfer) care only about throughput, not delay, this is really a gross oversimplification. In file transfer, we don't care how long it takes for the first packet to reach its destination, AS LONG AS ALL THE FOLLOWING PACKETS FOLLOW IMMEDIATELY, WITH NO DELAYS BETWEEN THE ARRIVALS OF SUCCESSIVE PACKETS. Of course, if there are long delays between the packets of a file transfer, the throughput will be very low. Hence it is not quite true to say that file transfers and the like are unconcerned with delay. If higher level protocols like TCP are being used, then routing over a path of long delay will certainly result in lower throughput. The reason is as follows. A TCP sender will only send a certain amount of data, until he fills the window specified by the TCP receiver. The size of the window is very likely to depend on such network-independent things as the amount of resources (e.g., buffers) in the destination host. If the path between source and destination host is very long, then the sending TCP will fill the window, and then have to wait, idly, for some period of time while his data gets to the destination, and while the message indicating the re-opening of the window is transmitted from the receiving TCP. Since this network-imposed long delay causes the sending TCP to have to be idle for some period of time, it holds down the throughput. So it seems that all things considered, simply routing high-throughput application traffic on the path of maximum excess capacity is unlikely to actually result in high throughput. - 41 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen If we really wanted to do single-path throughput-oriented routing, we would need something like the following. We would want to route traffic on the shortest path (i.e., the path of least delay) which does not contain any components whose available capacity is too small to handle the needed throughput. This would prevent us from choosing a path with arbitrarily long delays, or a path with too little capacity. Unfortunately, it is almost impossible to find out either what throughput is needed by an application, or to find out just what the capacity of particular components of the internet is. We might want to consider some strategy such as not sending batch traffic on paths which include components which are very heavily loaded. This is fertile ground for experimentation. Our present point, however, is that the delay-oriented SPF routing of the ARPANET already provides the basic structure that we need to accommodate this sort of strategy. If we knew that we wanted bulk traffic to avoid certain Pathways (e.g., Pathways with too little bandwidth), we could have SPF routing compute the shortest routes that did not include those Pathways, by using the "indexed length" scheme described in section 4.3.2. There is no need to consider different sorts of routing schemes. 4.3.4 Knowing the "Whole Picture" The use of the SPF algorithm requires that every Switch know the complete topology of the Network Structure. That is, every - 42 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen Switch must know of all the other Switches, must know which Switches are "directly connected" to which other Switches, and must know the "length" of each Pathway. This is not to say that this information is "compiled in", or even loaded in manually. Rather, it is determined dynamically, in real-time, through interpretation of the routing updates (see section 4.5). It is this uniform global knowledge of the topology and the Pathway lengths that enables each Switch to run a shortest path algorithm, while producing routes which are consistent with the routes produced by other Switches, so that routing loops do not form. The SPF algorithm does not merely tell a Switch to which of its neighbors it should send packets for destination D. Rather, it computes the entire path to the destination Switch. However, when a packet is routed, it does not carry with it the identity of the entire route, as computed by its source Switch. Each Switch just forwards the packet to the next "hop" along its route. The fact that all Switches have the same information about the topology is what ensures that this routing will be free of loops. Since each Switch performs its routing based on a complete picture of the topology of the Network Structure, we can call this sort of routing scheme a "whole picture" scheme. In this section, we will compare "whole picture" schemes with some other schemes which do not require the Switches to have uniform global knowledge of the topology. We argue that "whole picture" schemes are always superior. - 43 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen The original ARPANET routing scheme, and the current Catenet routing scheme, are not "whole picture" schemes. In these routing schemes, no Switch need have any knowledge of the topology, other than who its own immediate neighbors are, and the lengths of the Pathways to its immediate neighbors. These algorithms function as follows. When a Switch first comes up, it forms a hypothesis as to the best neighbor to which to send data for each possible destination Switch. This initial hypothesis is based only on its own local information about the lengths of the Pathways to its neighbors. It then informs its immediate neighbors of its hypotheses, and is informed of their hypotheses. It then forms a new hypothesis, based on its own local information AND the hypotheses communicated to it by its neighbors. It then exchanges hypotheses with its neighbors again, and again, and again, until its own hypotheses are in complete agreement with those of its neighbors, at which point stability is reached. To see the difference between this sort of routing scheme and the "whole picture" scheme, consider the following situation. Suppose we have 100 people in a room, sitting in chairs which are properly lined up so that we can talk of each person's having two immediate neighbors. We also have a picture of an object, and our goal is to have ALL the people agree on the identity of the depicted object. Now we have a choice of two different procedures for bringing this about: - 44 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen Procedure 1: Cut the diagram into 100 pieces, and give one piece to each person. Each person is now allowed to look at his one piece, and then form a hypothesis as to what is depicted in the full picture. Then each person can exchange hypotheses only with his immediate neighbors. Then each person can form a new hypothesis and exchange that with his immediate neighbors. The procedure terminates when all 100 people agree on what is depicted. Procedure 2: Make 100 Xerox copies of the diagram, and distribute the copies to each person. If we really think it is important for each person to know what is depicted in the picture, then we will certainly follow procedure 2, which will make the whole picture immediately available to all participants. Procedure 1 would only be useful as a party game. It would be quite amusing to see all the ridiculous hypotheses that are formed before all participants converge to the correct one, IF they ever do manage to converge. Even if they do converge, it might take quite a long time. We must remember that different people form hypotheses at different rates, and can communicate them at different rates. Some people may simply refuse to talk to certain neighbors at all. If one's left-hand neighbor has formed a good hypothesis, but one's right-hand neighbor has not, one's own hypothesis is likely to be thrown off the track, which in turn is likely to mislead one's left-hand neighbor into a poorer hypothesis during the next "iteration." This is not a very optimal procedure for bringing about convergence of opinion. - 45 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen However, this situation is really too simple and straightforward to be truly analogous to routing. To improve the analogy, we must suppose that the picture is constantly changing, even as the people are still forming hypotheses. In procedure 2, this change is accounted for by simultaneously giving each participant a new copy of the picture. In procedure 1, changes in the picture are accounted for as follows: if the part of the picture originally given to person P has changed, then give him the corresponding piece of the same picture; he can now use this piece when forming his hypotheses, and should forget about the previous piece. When the procedures are thus modified to take account of changes in the picture, the situation described is more analogous to routing, and the advantages of procedure 2 over procedure 1 are even more pronounced. The ARPANET's current routing algorithm is similar to procedure 2, since the whole picture is made available to each Switch. The ARPANET's original routing algorithm, and the Catenet's current one, are more similar to procedure 1; perhaps they should be called "jigsaw puzzle" algorithms. All of the problems of procedure 1 have their analogies in those routing algorithms. It should be obvious that in terms of responsiveness, accuracy, and consistency, whole picture algorithms are superior to jigsaw puzzle algorithms. Many of the problems of the original ARPANET routing algorithm, such as looping and very slow response to topological change, can be attributed to its "jigsaw puzzle" nature. - 46 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen Even if one agrees that we ought to avoid "jigsaw puzzle" algorithms, one might still claim that we need not have a "whole picture" algorithm. One might wish to argue that a given Switch needs to know only the topology of a "region" which contains it. This region would be larger than a single Switch, but smaller than the set of all Switches. A region would also be geographically contiguous, so that if two Switches are in the same region, then there is a path between them which is entirely within the region. Then traffic which does not need to leave a region to get from its source to its destination is in effect routed by a "whole picture" scheme. Traffic which must leave the region, however, does not have its whole route preplanned. Switches within one region will know only how to get traffic out of the region. Other Switches in the next region will know how to get the traffic through that region, etc. It seems, one might argue, that this sort of regionalized routing scheme ought to be possible. After all, consider the analogy with ordinary road travel. If one wants to travel from Boston to Los Angeles, one need not preplan the entire route. One can just head in the general direction of Los Angeles, with no need to know anything about the roads which are close to Los Angeles until one actually gets close. A similar scheme ought to work with data. One problem, however, with the suggested analogy, is that it does not even hold in the case of ordinary automobile travel. If one were planning an automobile trip to LA, one would want to - 47 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen know about any record-setting blizzards in the midwest long before one actually approached the midwest. One would want to know about the status of Mt. St. Helen's volcano long before one approaches Oregon. One might try not to be passing through Chicago at rush hour. Avoiding any of these potential disaster areas could require quite a bit of advance planning. Of course, the amount of advance planning that one performs when travelling is a matter of personality; some people are more adventurous than others, and might actually enjoy a disaster or two along the way. Users of a data communications utility, however, whatever personality traits they may have, generally do not want their data to be sent on an adventure. Rather, they want their data to be treated with a conservatism and caution which require considerable preplanning. In any case, the analogy between the road system and a data communications network is very misleading because of the very rich interconnectivity of the road system. No matter how many problems an automobile driver encounters as he approaches Los Angeles, he still has a large number of choice points, in that he can take any number of relatively short detours around problem areas. In data networks, however, the connectivity is much less rich, and the closer the data gets to its destination, the fewer choice points there are. With a sufficiently sparse connectivity, the entire path could even be determined by the very first routing choice that is made, so that no detours around - 48 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen problem areas are possible once the "trip" begins. The situation is as if someone drove from Boston to Nevada, then found that all roads from Nevada to California were closed, and that he then had to drive all the way back to Boston to start on a new route to California. This sort of sub-optimality is inherent to any regionalized routing scheme for data communications networks. In fact, the situation could be even worse. If Switches in Boston know nothing about what is happening between Nevada and California, then data for California which arrives at Nevada and then is sent back from Nevada to Boston for alternate routing will just loop back to Nevada. The data will be stuck in an infinite loop, never reaching its destination. In IEN 179, Danny Cohen proposes a regional routing scheme like this, apparently not realizing that it suffers from loops. His proposal also includes a form of hierarchical addressing which is closely bound up with routing, so that a Switch in Boston might not even be able to distinguish data for Nevada from data for California. That is, in Cohen's scheme, data for Nevada and data for California would be indistinguishable at the Boston Switches; all such data would appear to be addressed to Nevada. Only the Switches at Nevada would look further down the address hierarchy to determine whether the data needs further forwarding to California. Any such scheme is hopelessly loop-prone, except in a Network Structure whose connectivity is extraordinarily rich, much more so than the Catenet's will ever be. - 49 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen It might seem like these objections would also have to apply to the internet, since a gateway does not know all about IMPs and packet radios and SIMPs, etc., in the component networks. However, the looping problem is avoided in the internet since it is organized in a strict hierarchy of Network Structures. Switches in one Network Structure need not know anything about Switches in any other Network Structure, but they must have complete information (Whole Picture) about Switches in the same Network Structure. All (source or intermediate) Switches in a particular Network Structure always route data to a Switch in that same Network Structure. This imposition of strict hierarchy prevents looping, as long as the lower levels of hierarchy are controlled by the higher levels. In the internet, this means that, e.g., if a gateway hands a packet to an ARPANET IMP for delivery to an ARPANET Host or to another internet gateway, the ARPANET is required to deliver the packet as specified by the gateway, or to say why not. It must not simply pass the packet back to the gateway, or a loop will form. (This sort of looping has been frequently noticed between IMPs and port expanders.) This does not imply that an ARPANET IMP cannot pass a packet to an internet gateway for delivery (through an "expressway network") to another ARPANET IMP, but only that once an internet gateway decides to send a packet into the ARPANET, the ARPANET must get that packet to the intended destination, or else inform the gateway that it cannot do so. - 50 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen It is also important to note that the hierarchical levels in the internet tend to be "horizontal", rather than "vertical". That is, in an internet spanning North America, there would be internet gateways located all across the continent, as well as IMPs and packet radios and PSATs located throughout the continent. This is quite different from regionalization, in which Switches which are close geographically are in a common region. This distinction is very important if we are to avoid such problems as looping. Although building the internet as a strict hierarchy of Network Structures avoids the problems of looping, there is always some degree of sub-optimality introduced whenever the topological knowledge of the Switches is restricted in any way, even if the restriction is just to Switches within the same Network Structure. This is a point to which we return in section 4.6, where we discuss some of the basic limitations of internetting. 4.4 Measuring Pathway Delay One of the most basic problems in devising a scheme to do delay-oriented routing is to figure out a way to determine the delay. In the ARPANET, the delay measurement algorithm is quite straightforward. When a packet arrives at an IMP, it is stamped with its arrival time. When it is transmitted to the next IMP, it is stamped with the time of transmission. ARPANET packets are - 51 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen buffered in an IMP until acknowledged by the next IMP; if a packet has to be retransmitted, its transmission time stamp is overwritten with the time of latest transmission. When the packet is acknowledged by the receiving IMP, the arrival time is subtracted from the transmission time, yielding the total time the packet spent in the IMP. The propagation delay (i.e., the speed of light delay along the phone line from one IMP to the next) is then added in to compute the total amount of time it took to get the packet from one IMP to the next. There are three important aspects of this delay measurement algorithm: 1) It is necessary to measure the amount time each packet spends within the Switch. This should be as easy to apply to a gateway as to an IMP. 2) It is necessary to determine how long it takes a packet to travel from one Switch to another over the Pathway connecting them. If the Pathway is a telephone line, as in the ARPANET, this is just the propagation delay, and is a constant which can be separately measured and then stored in a table. On the other hand, if the Pathway is a packet-switching network, or even an internet, this is much more difficult to determine, and is certainly no constant. 3) There must be some way to account for packets that don't get through, or don't get through immediately, due either - 52 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen to errors or to congestion. In the ARPANET, if a packet doesn't get through on its first IMP-IMP transmission, and has to be retransmitted 200 ms. later, this 200 ms. gets added into the packet's delay. This is a very important feature, since it enables the delay measurement to reflect the effect of congestion or of a very flakey line. But unless the gateways run a reliable transmission protocol among themselves, it will be difficult to make sure that our delay measurement really reflects these factors. If we are trying to send data through a network which is dropping most of the data we send it, we want to make sure that our delay measurement routines produce a high value of delay, so that traffic will tend to be routed around this very flakey and unreliable Pathway. (Remember that if too much traffic is dropped, some (higher) level of protocol will have to do a lot of retransmissions, resulting in very high delays and low throughputs.) The problem of how to measure delay is more tractable in the case of AREA ROUTING than in the more general internet case. Recall that by "area routing," we mean a sort of internet all of whose component networks are basically identical (see IEN 184). For example, we might at some future time decide to divide the ARPANET into areas, connected by gateways, so that the ARPANET itself turns into a hierarchical network. If we decide to use - 53 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen the same routing algorithm at the high level (i.e., among the intra-ARPANET gateways) as we use at the lower level (i.e., among the individual IMPs in a particular area), then the gateways could obtain the delay measurement information directly from the routing updates sent by the individual IMPs. That is, the lower level routing algorithm could provide information to the gateways enabling them to deduce their delay to other gateways. If the gateways are also ordinary IMPs, this information is automatically available. If the gateways are hosts on the low level ARPANET, a special protocol would have to be developed to enable the IMPs to transmit the routing updates to the gateways they are connected to (though this wouldn't be much different from the protocol that IMPs now use to transmit routing updates to their neighboring IMPs). Of course, if we were to implement a scheme like this, we would still want to make the ARPANET appear as a single Pathway (with no intermediate Switches) at the level of the Network Structure of the Catenet. That is, the Catenet would be a third hierarchical layer over the two hierarchical levels of the ARPANET, which would be transparent to it. In the more general internet case, we cannot rely on the component networks to provide us with the sort of delay information we would like to use for the internet routing algorithm; the internet Switches will have to have some way of gathering this information themselves. In general, it will not be possible for a Switch to measure the one-way delay from itself - 54 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen to its neighbors. (We wouldn't want to rely on the radio clocks that are now beginning to be deployed at the gateways; while these might be useful for doing measurements, we wouldn't want the reliability of the entire operational internet system to depend on a radio broadcast over which we have no control.) It is possible, however, to measure round-trip delay between each pair of neighboring gateways. In the ARPANET, for example, round-trip time is easily measured by keeping track of when a message is sent to a neighboring gateway, and then noting the time when the RFNM is received. One-way delay would be approximated by dividing the round-trip delay in half. It is certainly true that the round-trip delay is not, in general, exactly twice the one-way delay. However, it seems like a good enough approximation to use in the internet routing algorithm. All we really require is that it be roughly proportional to the one-way delay, in that both one-way and round-trip delays tend to rise and fall together, and that congestion in the Pathway (component network) tends to make both increase. Of course, before designing the precise delay measurement scheme that we would want to use in the internet, we would have to run a series of tests and experiments to see which of several possible delay measurement algorithms gives us the results we want. This would be similar to the extensive testing of the ARPANET's delay measurement algorithm that is documented in [4]. - 55 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen Unfortunately, there are many networks which do not return anything like RFNMs that could be used to gauge even the round-trip delay. (Many networks, e.g., SATNET and the forthcoming wideband network, do not even tell you whether you are sending traffic to a host which is down.) So we will need a gateway-gateway protocol in which gateways receiving data from other (neighboring) gateways send back replies which can be used for timing. This does not mean that every packet sent from one gateway to another must be acknowledged by the receiving gateway. Rather, we would propose something like the following. Suppose we have, as part of the gateway-gateway protocol, a bit that a sending gateway can set which requires the receiving gateway to acknowledge the packet. The sending gateway can have a random number generator, which lets it select packets at random in which to set this bit. These packets will have their round-trip delay measured, and will constitute a random (and hopefully a representative) sample. The packets need not be buffered in the sending gateway pending acknowledgment, but they will need to have unique identifiers so they can be kept track of. The round-trip delay of each packet is then easily determined when the acknowledge is received. (This probably implies though that gateways will have to run a protocol with their neighbors when they first come up in order to synchronize sequence numbers to use for identifying packets uniquely.) There will also have to - 56 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen be a time-out, so that a packet which is not acknowledged within a certain amount of time (perhaps dependent on the expected delay of the packet, based on previous measurements) will be considered to have been lost on the Pathway between gateways (or in the receiving gateway). Packets which have been lost should be assigned a very high delay, so that the routing algorithm assigns a very high delay to Pathways which lose a lot of packets. This will tend to cause internet traffic to avoid such Pathways. There doesn't seem to be any problem in principle with a scheme like this, but we will probably need to do some statistical analysis in order to determine the best random sampling technique, and to figure out how many packets we might need to keep track of during some period of time (i.e., how big a table do we need to keep track of packets which are awaiting acknowledgments?). This sort of random sampling can also be used as part of a Pathway up/down protocol. If a certain percentage of the sampled packets do not get through, it might be good to assume that the Pathway is not of sufficient quality to be operational, and should appear to be down as far as the internet routing algorithm is concerned. In the absence of real data traffic, we could run the up/down protocol with randomly generated test packets. Randomly generated test traffic or randomly sampled data traffic will give us a better result than periodic test traffic, since measurements based on random sampling are less likely to be correlated with other network phenomena.) - 57 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen After we compute the delay for individual packets, we still face the following two questions: 1) The delay which the routing algorithm assigns to a particular Pathway will be a function of the measured delays of the individual packets sent on that Pathway. But what function should it be? 2) Once a Switch determines the delay on the Pathways emanating from itself, it must inform all other Switches of these values (in routing updates). What protocol should it use for disseminating these updates? The second question will be discussed in section 4.5. The remainder of this section will deal with the first question. After measuring the delays of individual packets, the individual delays must be put through some sort of smoothing function before they can be used as input to the routing algorithm. For example, in the ARPANET, we take the average, every 10 seconds, of the delays experienced by all the packets traversing a particular line in the previous 10 seconds. This average is used as input to the routing algorithm (i.e., it is assigned as the "length" of the line when the shortest-path computation is run.) We didn't choose this smoothing function at random; we chose it because it meets certain desiderata. Our real purpose in measuring delay on a particular line is to enable - 58 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen us to predict the delay that will be seen by packets which are routed over that line in the future. Knowing the average delay during some period in the past is of no value except insofar as it enables us to make predictions about the future. We found in the ARPANET that for a given level of traffic, the delays experienced by the individual packets would vary quite a bit, but the delay when averaged over 10 seconds stayed relatively constant. (It is interesting that everyone who does measurements of individual packet delay always discovers this large variance, and always expresses great surprise. This "surprising" result is so often re-discovered that it should cease to be a surprise.) When designing the delay measurement routines for the ARPANET, we investigated some other smoothing functions (everyone seems to have his own favorite), but none gave more reasonable results than the simple average we adopted (which is not a running average, but rather starts over again from scratch every 10 seconds). We also tried averaging periods of less than 10 seconds, but found what we regarded as too much variation, even when the traffic load was stable. Note that if we take an average every 10 seconds, we cannot react to a change of conditions in less than 10 seconds, and we are often criticized by people who claim that it is important for routing to be able to react more quickly. Our reply, however, is simply that it takes 10 seconds to be able to detect a significant change in delay. Averages taken over smaller periods - 59 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen show too much variation under constant load to be useful in predicting the future delay, and hence are not useful in routing. In other words, averages taken over smaller periods give spurious results, "detecting" changes when in fact there are none. We want to change routing in response to real changes in network conditions, but not in response to the normal range of stochastic variations in delay. Any change in routing made on the basis of a shorter-term average is at least as likely to be harmful as to be helpful. That is, if we attempt to make routing changes based on delay data which is not sufficiently smoothed, we are really making changes at random, since we have left too much random variation in the delay data. And it seems that a good routing algorithm should not make changes at random. Of course, it would be nice if we could make routing changes instantaneously based on instantaneously detected changes in real network conditions, but this is not possible simply because there is no instantaneous way of detecting important changes in network conditions. It is important to realize, however, that the measurement periods in the various IMPs are not synchronized. Although a given IMP generates updates no more often than every 10 seconds, some IMP or other is generating an update about every 500 milliseconds. Mathematical analysis indicates that synchronized measurement and updating periods should be avoided, since they give worst case performance [4]. - 60 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen There are other important reasons for not making routing changes too often. During the lifetime of a single packet in the network, we want the routing to be relatively constant, so that the packet can get to its destination without having to take too many detours. If we changed the routing every millisecond, for example, a single packet in transit though the network would experience many routing changes while in transit, which would probably cause it to have a longer delay than necessary. The rate at which we change routing should be low relative to the average transit time of a packet through the network. Another reason for not making routing changes too frequently has to do with the time it takes routing updates to travel around the network. We want to make sure that the information carried in a routing update is not totally obsolete by the time the update is received. This implies that the smoothing interval for delay measurements has to be long relative to the time it takes updates to traverse the network. In the ARPANET, 10 seconds is much longer than the amount of time it takes to get updates around, or the amount of time a packet spends in transit in the network. We chose 10 seconds as the averaging interval because it seemed to be the shortest period that was long enough to give us a reasonable amount of smoothing. If we think that in the internet, however, average transit times might be measured in the tens of seconds, we may have to make our smoothing interval considerably longer than 10 - 61 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen seconds, perhaps as long as a minute. This could seriously limit the responsiveness of the routing algorithm to changing network conditions. However, there is nothing we can do about this. THE LONGER IT TAKES PACKETS TO TRAVEL AROUND A NETWORK, THE LESS RESPONSIVE THE ROUTING ALGORITHM OF THAT NETWORK CAN BE, for the simple reason that it will just take longer to disseminate the information needed for routing around the network. The transit time of a network places an upper limit on the responsiveness of that network's routing algorithm. Any attempt to exceed this upper limit (with kludges or heuristics) will just be futile, and will result only in unstable and mysterious behavior on the part of the routing algorithm, reducing, rather than increasing, performance. This is not to say that each Switch must generate routing updates as often as every 10 seconds. If there is no change in delay from one 10-second period to another, then there is no reason to generate an update. Or if there is a change, but it is not "significant", then there is no reason to generate an update. In the ARPANET, a delay change is considered to be significant if it exceeds a certain (parameterized) threshold. We devised a scheme wherein the threshold decreases with time, so that a very large change is always "significant", but a small change is significant only if it persists for a long time. Of course, routing updates must be generated not only in response to measured changes in delay, but also if a line goes down or comes up. - 62 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen We would expect that the details of the delay measurement and smoothing algorithms will have to be different in the internet than in the ARPANET, but the principles outlined above would seem to apply in the internet environment also. WE WILL HAVE TO DO SOME CAREFUL EXAMINATION OF THE DELAY-THROUGHPUT CHARACTERISTICS OF EACH OF THE INDIVIDUAL NETWORKS THAT ARE USED AS PATHWAYS IN THE INTERNET, and it may be that somewhat different smoothing algorithms will have to be used for the different kinds of Pathways. However, there doesn't seem to be any problem in principle with doing this sort of delay measurement. An interesting issue arises if a given pair of gateways is connected by two or more distinct Pathways. For example, two gateways might both be connected to ARPANET and SATNET, so that each can be reached from the other by either of those two networks. Or, a gateway might be multi-homed on the ARPANET, so that it has two distinct access lines over which it can reach all the other ARPANET gateways. In such cases, do we want to separately report the delay on each of the distinct Pathways, or do we want (at the level of routing) to represent the connection between each pair of gateways as a single, unique line, whose delay is some function of the delay of the distinct Pathways which really exist? This issue is a generalization of an issue we have been looking at in the context of the ARPANET, which we call "parallel trunking." In parallel trunking, a single pair of - 63 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen IMPs is connected by two or more trunks, and the same issue of how to represent them in routing (as individual trunks, or as a single, composite, trunk) arises. When the trunks are telephone lines, the problem is relatively easy to deal with. Routing can treat them as a single trunk, with a delay which is the average delay of all packets sent over the composite trunk. The actual decision as to which particular component trunk to use for transmitting a particular packet can be made locally, by the IMP to which the parallel trunks are connected; there is no need for routing to play a role in this decision. In the case where the parallel trunks are of comparable lengths (so that there is not much difference in the propagation delays), the trunks can serve a common queue according to the standard FIFO single-queue multiple-server discipline. If the trunks are more heterogeneous, say one is a terrestrial line and one is a satellite line, a somewhat more complex queuing discipline is required. We would like to avoid using the satellite line until the load is such that if only the terrestrial line were used, packets would experience a delay comparable to that they experience over the satellite line. With this sort of queuing discipline, packets sent to the composite line experience a delay which is independent of the particular component (land-line or satellite line) that they use. That is, no packet is forced to suffer the quarter-second satellite delay unless the terrestrial line is so backed up that the delay for - 64 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen packets sent over it is comparable to the delay of packets sent over the satellite line. This sort of scheme seems to ensure the best delay performance for the composite trunk. (Actually, the mathematics of queuing theory suggests that a smaller average delay for the composite trunk might be achieved by starting to use the satellite line sooner. That is, a somewhat smaller average delay might be achievable if a few packets are given a much longer delay by being forced over the satellite line sooner than they would be with the queuing discipline we suggested. Considerations of fairness would seem to rule that out, however; how would you like it if your data got a much higher delay so that someone else's could get a slightly smaller one? In addition, the queuing discipline we suggested would seem to produce a smaller variance in delays, thereby making the measured average delay on the composite trunk a better predictor of future performance, and the better we can predict future performance, the better performance our routing algorithm can provide.) Basically, there is no reason for routing to be aware that a particular line consists of several parallel components rather than a single component, because, if the argument above is right, any decision as to which component to use can be best made locally, at the IMP from which the parallel lines emanate. That is, the global routing algorithm cannot really make effective use of information about which lines consist of parallel components, and should not be burdened with information that it cannot use. - 65 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen This is good, since the SPF algorithm cannot really handle parallel lines between a pair of Switches except by representing them as a single line. (A careful study of the algorithm would show that much of the algorithm's space and time efficiency would be sacrificed if it had to be modified to handle parallel trunks as separate trunks. Since this efficiency is the main thing that recommends the SPF algorithm over other shortest-path algorithms, we must be sure that we don't destroy the effectiveness of the algorithm by making poorly thought-out changes to it.) In the internet environment, however, we have a more complex problem with parallel trunks than in the ARPANET. The scheme we outlined for using parallel trunks in the ARPANET depends on our being able to know when the load on the composite trunk is such that exclusive use of the faster component would cause delays that are just as high as we get when we use the slower component. This is not difficult to know if the components are phone lines of one sort or another, since the relation between load and delay is pretty well-defined if we know the length of the lines and their capacity. If the components of a parallel "trunk" are really packet-switching networks, however, it is much harder to figure out which components are slow and which are fast, and it is hard to figure out when the load on the fast component is such that we have to start using the slow one. It seems that by separately measuring the delays obtained over the "parallel trunks" in the internet case, we ought to be - 66 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen able to devise some algorithm for splitting the traffic among the parallel components in a way which gives reasonable delay/throughput performance. However, we don't yet have a solution to this problem, which we will put aside for the present. Whatever scheme we eventually decide on, however, should be compatible with treating the parallel components as a single line at the level of routing. Of course, if we decide to have different routes for different traffic types (say, excluding satellite networks for interactive traffic, but using them for batch traffic), then the problem is eased somewhat since we partially solve the problem a priori. There would still be no need to represent the parallel lines as separate lines. Rather, we would represent them as a single line, with different delay characteristics for different traffic types. 4.5 Routing Updates 4.5.1 Overhead Everyone seems to be in agreement that the overhead due to routing updates should be kept low. At least, no one seems to advocate that the overhead should be made high. Unfortunately, "apple pie" pronouncements like this aren't much help in actually designing a routing scheme. In evaluating a routing algorithm from the perspective of overhead, one must understand the way in which overhead is traded off against functionality. - 67 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen One advantage of the SPF routing algorithm is that it provides a lot of handles that can be used to control overhead. In SPF routing, a routing update generated by a particular Switch identifies each neighbor of that Switch, and gives the delay over the Pathway to that Switch. Thus the size of an update generated by a particular Switch is proportional to the number of neighbors that the Switch has, generally a fairly small number (no more than 5 in the ARPANET, and probably of a similar magnitude in the internet). In the current Catenet routing algorithm, the size of the routing updates is a function of the total number of gateways (or equivalently, of the total number of component networks), a number which can increase by a great deal over the years. In the SPF algorithm, the size of the updates is a function of the connectivity of the internet, which could not increase anywhere near as much or as rapidly as the number of gateways. (In the two years that SPF has been running in the ARPANET, the number of IMPs has increased by a third, with another similar increase expected in the next several months, while the connectivity, and hence the average update size, has remained relatively constant.) This is important, since we wouldn't want to get ourselves into a situation where the update size eventually becomes so big (due to network growth) that we can no longer fit a whole update into a single packet (a situation that was imminent during the last days of the original ARPANET routing algorithm.) In the internet, the - 68 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen maximum size of an update packet is constrained by the component network which has the smallest maximum packet size. It seems likely that any component network whose packets are large enough to carry the enormous TCP and IP headers should have no trouble carrying the routing updates. The amount of overhead due to routing updates is not only a function of the update size, but also of the rate at which updates are generated. In the ARPANET, since each IMP averages the delay on its outgoing lines over a period of 10 seconds, changes in delay on the lines emanating from a particular IMP cannot occur, by definition, more often than once every 10 seconds. In addition to generating updates when the delay changes, updates must also be generated when lines go down or come up. In the ARPANET, a line which goes down cannot come up for at least 60 seconds. So in an IMP with 5 neighbors, the most updates that can be generated in a minute is 11 (due to each of the lines either going down or coming up during the minute, for 5, and a delay change every 10 seconds, for 6). It is important to note that this is the maximum rate at which updates can be generated, not the average rate. Since IMPs need not generate routing updates unless they have a "significant change" in delay to report, the average rate can be much lower. In the ARPANET, the average rate for generating updates is actually about one per IMP per 40 seconds. This is a very limited amount of overhead. Of course, the overhead will increase as the number of IMPs - 69 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen increases, because there are just more IMPs to generate updates. However, the amount of overhead is always under our control, since we can always alter the averaging interval, or the threshold of significant change in delay, to force updates to be generated less frequently and thereby to reduce overhead. These same principles apply to the internet also, so it doesn't seem as if we will be generating enormous amounts of routing overhead. There are some things we might want to do which would tend to make the routing updates longer than so far indicated. For example, if we defined several priorities of traffic at the internet level, and mapped these priorities to different priorities of some particular component network, we might want to separately measure the delay across that network for each priority. We might also want to compute a separate set of routes across the internet for each priority. If we adopted some such scheme, we would need to report in each update several different delays for each Pathway, indexed by priority. These indexed delays could then be used for computing a set of routing tables indexed by priority, allowing traffic of different priorities to use different routes. Of course, this would lengthen the updates, adding more overhead. Part of the decision as to whether to adopt such a scheme would involve an evaluation of the trade-offs between the cost of this increased overhead and the benefit of the expected improvement in performance. The issues, however, are clear, and there are enough handles controlling the - 70 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen amount of overhead so that we can put into effect any decision we make. It is important to understand that the number of routing updates generated by a single internet event (such as the outage of a gateway access line) is much less with SPF routing than with the current Catenet routing algorithm. In SPF routing, a given event causes the generation of ONE routing update, which must then be sent to every gateway (thereby giving each gateway an up-to-date copy of the "whole picture"). On the other hand, in the current Catenet routing algorithm, a single internet event causes a flurry of updates, as all gateways send and receive updates repeatedly to and from each neighbor, until the routing tables stabilize and the process settles down. This can take quite a long time and quite a few updates, particularly if the number of gateways is large. In addition, in an internet with a large number of gateways, the updates for the current Catenet routing algorithm are very much larger than the SPF updates would be. It is clear that the routing overhead due to a single network event would be much less with SPF than it currently is. However, if we plan to send routing updates when delay changes, as opposed to just when a gateway access line comes up or goes down (as at present), then we will be generating updates in response to more network events. This tends to drive the overhead up. Again, the trade-offs are - 71 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen relatively clear here; the amount of overhead simply trades off against the responsiveness of the routing algorithm to changing network conditions. The decision as to how to draw this trade-off can be made as a policy decision, and can be changed if performance considerations warrant it. The situation with the current Catenet routing algorithm is quite different, since the amount of overhead that it generates is almost impossible to compute. In that algorithm, the number of routing updates generated in response to a particular event depends on the order in which the updates are processed by the individual gateways, something that is essentially random and hence hard to predict. The SPF algorithm has no such dependency. The need for hysteresis in the Pathway up/down protocol run between neighboring gateways is worth emphasizing. If connections between neighboring gateways are allowed to come up and go down with great frequency, causing a constant flurry of routing changes, packets in transit will bounce around a lot. Putting a limit on the frequency with which a gateway-gateway connection can change state is needed not only to limit the amount of overhead generated, but also to give some stability to the routing. It is worth noting that the ARPANET, although providing hysteresis in its own line up/down protocol, does not provide any hysteresis in host up/downs. Hosts are allowed to go down and come up repeatedly many times a minute, and this does - 72 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen result in problems, causing congestion and instability. Hysteresis in the gateway's Pathway up/down protocol will have to be ensured explicitly; we cannot rely on the ordinary host access protocol of the component networks to do the right thing. That is, if a network interface goes down, we must keep it down for a period of time, even if the network itself allows the interface to come back up immediately. 4.5.2 Protocol We turn now to the problem of how to disseminate the routing updates around the Network Structure. Remember that the updates generated by a particular Switch will contain information about the delays to the neighbors of that Switch. When a Switch generates an update, it must broadcast that update to ALL other Switches. As a result, every single Switch will know the values of delay between every single pair of neighboring Switches. It is then straightforward to have each Switch run a shortest-path algorithm which determines the shortest path from itself to each other Switch. The basic idea is for each Switch to know the entire topology of the Network Structure, so that the shortest paths can be determined by a localized shortest path algorithm, with no need for a distributed computation. In the ARPANET, the IMPs do not start out with any knowledge of the topology. They determine who their own neighbors are, and they reconstruct the rest of the topology from the routing updates they receive. - 73 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen It is possible to prove that, as long as all Switches have the same information about the topology and the delays, then they will produce routes which are consistent and loop-free. (That is, the situation in which Switch A thinks its best path to B is through C, and C thinks its best path to B is through A, can never arise.) However, if some routing updates somehow get lost before being received by every single Switch, then there is no guarantee of consistent loop-free routing. In fact, if routing updates get lost, so that different Switches have different information about the topology or the delays, we would expect long-term routing loops to arise, possibly making the Network Structure useless for some period of time. So the protocol used to broadcast the routing updates needs the highest possible reliability. Of course, it will always take some amount of time for an update to be broadcast around the Network Structure, and during that time, some Switches will have received it and some not. This means there will always be a transient period when routing loops might arise. So another aim of the routing updating protocol must be to keep this transient period as short as possible. In the ARPANET, we have an updating protocol which seems to provide these characteristics of extremely high reliability and low delay. Some of its aspects adapt readily to the internet, but others are more difficult to adapt. In what follows, we first describe the ARPANET's routing updating protocol, and then discuss its applicability to the internet. - 74 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen Suppose IMP A has to generate a routing update, either because of some "significant" change in the measured delay, or because of a line up/down state change. Each update generated by A has a sequence number, which is incremented by 1 for each new update. (In the ARPANET, we use 6-bit sequence numbers, which wrap around after 63.) After creating the update, IMP A sends it to each of its neighbors. The update is transmitted as a packet of extremely high priority; only the packets used in the line up/down protocol are of higher priority. We use the notation "A(n)" to refer to the update generated by IMP A with sequence number n. Now let's look at what happens when a copy of update A(n) is received by an IMP B. (IMP B is intended to be an arbitrary IMP somewhere in the network, possibly identical to A or to one of A's neighbors, but not necessarily so.) If B has never received an update from A before, it "accepts" A(n), by which we mean that it (a) remembers in its tables that the most recent update it has seen from A is A(n) (i.e., the sequence number n, the list of neighbors of A, and the delays from A to each neighbor are stored in B's tables), (b) it forwards A(n) to each of its neighbors, including the one from which it was received, and (c) the SPF algorithm is run to produce a new set of paths, given the new delay and topology information contained in A(n). If B has received an update from A before, it determines whether A(n) is more recent than the update it has already seen, and "accepts" it (as just defined) if it is; - 75 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen otherwise it simply discards A(n). The determination as to whether A(n) is more recent than some previously received update A(m) is made by a sequence number comparison (which, of course, must account for the fact that sequence numbers can wrap around); A(n) is not considered to be more recent than itself. If one thinks a bit about this inductive definition of the protocol, one sees that each IMP in the network will receive every update which is generated by any IMP, and further that it will generally receive a copy of each update on each of its lines. This means of broadcasting an update from one IMP to all other IMPs is called "flooding." It is highly reliable, since updates cannot be lost in the network due to IMP crashes or partitions. If there is any path at all between two IMPs, flooding will get the update from one to the other. (Of course, if there is no path at all from A to B, then updates cannot get from one IMP to the other. However, this is not a problem, since if traffic from A cannot even reach B, then it cannot use B's outgoing lines, so there is no need for A to know the delays of B's outgoing lines in this case. In saying that flooding prevents updates from getting lost due to network partitions, we are thinking of the case where an update is in transit from A to B when a partition forms, such that A and B are in the same partition segment, but the update is in a segment which is now isolated from either A or B. Flooding ensures delivery in this situation.) - 76 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen Flooding also ensures that an update travels over the shortest (in terms of delay) possible path. Basically, every possible path is attempted, so the update necessarily gets through first on the shortest path, by definition. In addition, this means of transmitting routing updates does not depend in any way on the routing algorithm itself. Since routing updates are sent out all lines, there is no need to look in the routing tables to decide where to send the routing update. The transmission of routing updates is independent of routing, which eliminates the possibility of certain sorts of disastrous negative feedback. One might think that a protocol which sends a copy of every update on every line creates a tremendous amount of overhead. In the ARPANET, however, the average update packet size is 176 bits, and the average number of updates sent on each line (in each direction) is less than 2 per second, for an average overhead of less than 1% of a 50 kbps line. And this is with almost 75 IMPs generating updates. Of course, a protocol like flooding is only as reliable as are the individual point-to-point transmissions from IMP to neighboring IMP. We ensure reliability at this level with a positive acknowledgment retransmission scheme. Note, however, that no explicit acknowledgments are required. If IMP X sends update A(n) to neighboring IMP Y, and then X receives from Y an - 77 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen update A(m), where A(m) is at least as recent as A(n), we consider that Y has acknowledged X's transmission of A(n). Since an IMP which accepts an update sends it to all neighbors, including the one from which it was received, in general, if X sends A(n) to Y, Y will send A(n) back to X, thereby furnishing the acknowledgment. We say "in general", since there is a little further twist. As another reliability feature, we make each update carry complete information, and forbid the carrying of incremental information in updates. That is, each and every update generated by an IMP A contains all the latest information about A's neighbors and its delay to them, so that each update can be fully understood in isolation from any that have gone before. This means that if update A(n+1) is received and processed by some IMP B, then the prior update A(n) is superfluous and can just be discarded by B. In particular, if IMP X sends A(n) to neighboring IMP Y while at the same time Y is sending A(n+1) to X, then X can interpret the receipt of A(n+1) from Y as an acknowledgment of the receipt of A(n); that is, X no longer has to worry about retransmitting A(n), since that update is no longer needed by Y. If no "acknowledgment" for an update is received from a particular neighbor within a specified amount of time, the update is retransmitted. Of course, it must be specially marked as a retransmission, so that the neighboring IMP will always "acknowledge" it (by echoing it back), even if the neighbor has seen it before. This is needed to handle the case - 78 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen where the update got through the first time, but the acknowledgment did not. It should also be noted that all the information in a routing update must be stored in each IMP's tables in order to run the SPF computation. This means that if it is necessary to retransmit an update to a particular neighbor, the update packet can be re-created from the tables; it is not necessary to buffer the original update packet pending acknowledgment. We must remember that if congestion forms in some part of the network, we want routing to be able to adapt in a way which can route traffic around the congestion. For this to have any hope of working, we must be sure that ROUTING UPDATES WILL BE ABLE TO FLOW FREELY, EVEN IF CONGESTION IS BLOCKING THE FLOW OF DATA PACKETS. Therefore, routing updates in the ARPANET are not sent by the ordinary IMP-IMP protocol, which provides only 8 logical channels between a pair of IMPs. That would be disastrous, since congestion often causes all 8 logical channels to fill up and remain filled for some time, blocking further data transmission between the IMPs. Transmission of routing updates must be done in a way that is not subject to this sort of protocol blocking during periods of congestion. (This sort of "out-of-band" signalling was quite easy to put into the ARPANET. However, it is worth noting that such protocols as HDLC make no explicit provision for out-of-band signalling, and it seems that many networks are being built in which the routing updates will - 79 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen not be able to flow when the network gets congested. Designers of such networks will no doubt be quite surprised when they discover what is inevitable, namely that their routing algorithms break down completely in the face of congestion.) We also want to be sure that we have enough buffers available for holding routing updates, and that we process them at a relatively high CPU priority. There is one more twist to the updating protocol, having to do with network partitions. A network partition is a situation in which there are two IMPs in the network between which there is no communications path. Network partitions, in this sense, may be as simple as the case in which some IMP is down (an IMP which is down has no communications path to any other IMP), or as complex as the case in which four line outages result in partitioning the network into two groups of 40 IMPs. When a partition ends, we have to be sure that the two (or more) segments do not get logically rejoined until routing updates from all IMPs in each segment get to all the IMPs in the other segments. That is, data packets must not be routed from one segment to the other until all IMPs in each segment have exchanged routing updates with all IMPs in the other segments. Otherwise, routing loops are sure to form. We must also remember that the sequence numbers of IMPs in one segment may have wrapped around several times during the duration of the partition. Therefore we must ensure that IMPs in one segment do not apply - 80 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen the usual sequence number comparison to updates from IMPs in the other segment. We have dealt with these problems by adding the following three time-outs to the updating protocol: 1) MAXIMUM INTERVAL BETWEEN UPDATES: Every IMP is required to generate at least one update every minute, whether or not there has been any change in delay or line state. 2) MAXIMUM UPDATE LIFETIME: If an IMP B has not received any updates generated by IMP A for a whole minute, then B will "accept" the next update it sees that was generated by A, regardless of the sequence number. 3) WAITING PERIOD: When a line is ready to come up, it is held in a special "waiting" state for a minute. While in the waiting state, no data can be sent on the line. However, routing updates are passed over the line in the normal way, as if the line were up. Since the ending of a partition is always coincident with some line's coming up, these three features ensure that a partition cannot end until a full exchange of routing information takes place. They also ensure (given the facts that there is a 6-bit sequence number space and that IMPs can generate at most 11 updates per minute) that sequence numbers of updates generated after the end of the partition are not compared with sequence numbers of updates generated before the partition occurred. - 81 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen The general idea of flooding the updates seems as important in the internet as in the ARPANET. In general, we can expect the internet to be subject to many more mysterious outages and disturbances than is the ARPANET, and the reliability and speed of flooding will be essential if an internet routing algorithm is to have any hope of working. The issue of overhead may be somewhat worrisome, though. If an IMP has to send each of 4 neighbors a copy of each update, it is just a matter of sending a copy of a small packet on each of 4 wideband lines. On the other hand, if a gateway has to send a copy of each update to each neighbor, this may mean that it has to send 4 copies into a single network, over a single network interface. This may be somewhat more disruptive. Of course, this problem only exists on networks which do not have group addressing. If a network allows the gateways to be addressed as a group, then each gateway needs only to place one copy of each update into the network, and the network will take responsibility for delivering it to each other gateway. (This might result in each gateway's receiving back its own copy of the update, since the sending gateway will also be part of the group, but that is no problem. As long as the gateway can identify itself as the transmitter, it can just throw away any updates which it transmitted to itself.) This idea of sending the updates to all neighbors on a particular network by using group addressing fits in well with an idea expounded in section 4.1, namely the idea that a network should be able to - 82 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen tell which of its hosts are gateways, and should inform the other gateways when a new gateway come up. This same mechanism could be used by the network to augment its group addressing mechanism, to allow the group definition to change dynamically and automatically as the set of gateways connected to it changes. Unfortunately, few networks seem to have group addressing. Even SATNET has only a primitive group addressing feature, although it seems odd to have a broadcast network without full group addressing capabilities. (Group addressing is much more complex on a distributed network like ARPANET than on a broadcast network.) Perhaps as further internet development proceeds, more of the component networks will add group addressing, in order to make their use of the internet more robust and efficient. Retransmission of routing updates on a gateway-to-neighboring-gateway basis, based on the scheme in the ARPANET, also seems to offer no problems in principle. However, the retransmission time-outs might have to be carefully chosen, and tuned to the characteristics of the network connecting the sending and receiving gateways. The retransmission time has to be somewhat longer than the average round-trip delay in that network, and this may vary considerably from network to network. In principle, however, this is no different from the ARPANET, where the retransmission timers for routing updates vary according to the propagation delay of the phone line connecting two IMPs. - 83 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen There is a bit of a subtle problem that we discovered in the ARPANET, having to do with the scheme of using the updates themselves as acknowledgments. Suppose Switch A has two neighbors, B and C. A receives a copy of update u from B, and queues it for transmission to C. However, while u is still on the queue to C, A receives a copy of u from C. If A had already sent u to C, this copy from C would have served as A's acknowledgment that C had received the update. But now, with u on the queue to C, if we are not careful, A will send u to C after having received a copy of u from C. When C gets this copy of u from A it will not accept it (since it has already seen a copy of u and sent that copy on to A), which will cause A to retransmit u to C, resulting in an unnecessary retransmission. In the ARPANET, we deal with this problem by turning on the retransmission timer as soon as an update is received, rather than when it is sent. That way, an update which is still queued for transmission when its "acknowledgment" is received will still get transmitted unnecessarily, but the retransmission timer gets shut off, causing only one, rather than two, unnecessary transmissions. A more logical scheme would be to check the transmission queue to a Switch whenever an update is received from that Switch. If a copy of the same update that was just received is queued for transmission, it should just be removed from the queue. This would prevent any unnecessary transmissions. In the ARPANET, a few unnecessary transmissions - 84 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen don't really matter, but in the internet, if we really want to keep the overhead low, it is probably worthwhile trying to get this just right. We must remember that network access protocols may limit the number of packets we can get into the network during some period, which makes it all the more important to avoid sending unnecessary packets. Suppose we find that for some reason or other, it is taking a very long time to get updates from some gateway to one of its neighbors. This would show up as an excessive number of retransmissions of updates. In such a case, we would probably have to consider that particular gateway-gateway Pathway to be down, irrespective of what our ordinary Pathway up/down protocol tells us. Remember that in order to ensure consistent and loop-free routing, we must get the updates around the internet as rapidly as possible. If updates cannot travel sufficiently rapidly on some Pathway, then we just cannot use that Pathway at all for transit within the internet. Attempting to keep that Pathway up for transit can result in relatively long-term routing loops, which could in turn cause a degradation in network performance which swamps the degradation caused by not using that Pathway at all. Especially disastrous would be a situation in which ordinary data packets could pass, but routing updates, for some reason, could not. It is hard to know what might cause such a situation (perhaps a bug in the component network that we are using as a Pathway), but it is certainly something we need to - 85 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen protect against. (Note, however, that even if we declare some gateway-gateway Pathway down, it does not follow that the network underlying that Pathway cannot be used as a terminus network, to which data for Hosts can be sent and from which data from Hosts can be received. Even if some network is not usable for providing a Pathway between two gateways on it, it may still be useful for providing a Pathway between the gateways and some set of Hosts.) We have emphasized the need to transmit routing updates as "out-of-band" signals, which bypass the ordinary communications protocols (such as the IMP-IMP protocol in the ARPANET), so that when congestion forms which causes those protocols to block, the routing updates can still flow. That is, we would like to have a protocol which is both non-blocking and non-refusing. This may be quite difficult to achieve in the internet environment, where sending an update from gateway to gateway requires us to use whatever network access protocol is provided by the Pathway network. Here our most difficult problem might be with the ARPANET's 1822 protocol, which can cause blocking of the network interface for tens of seconds. We really can't delay sending a routing update for 15 seconds or so while the IMP is blocking, so whenever this happens we would have to declare the pathway down. In the ARPANET, we have two ways of trying to deal with this. One way would be to send all packets into the ARPANET as - 86 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen datagrams, which cannot cause blocking. Another way would be to use the standard virtual circuit interface, but to obey the flow control restrictions of the ARPANET (i.e., to control the number of outstanding messages between a pair of hosts), and to avoid the use of multi-packet messages (which can cause blocking if the destination IMP is short of buffers, as ARPANET IMPs chronically are). There are other situations in which blocking can occur, but they all involve a shortage of resources at the source IMP, and in such cases declaring the Pathway to be down is probably the right thing to do. We do not want to be forced into declaring Pathways down simply because we have ignored some protocol restriction, but it seems much more sensible to declare a Pathway down if, say, the IMP to which a gateway is attached is too congested to provide reliable service for internet packets. It is important to note that whatever restrictions we apply to our use of the network access protocol apply not only to routing updates, but also to all messages sent into the ARPANET from the gateway. It would do no good, for example, to send in routing updates as datagrams, while using non-datagrams for other packets, since this would allow the other packets to block the routing updates. At this point, it is not quite clear just what the best scheme would be. The use of datagrams enables us to get around the sometimes time-consuming but often unnecessary resequencing which the ARPANET performs before delivering packets to the destination host (it is neither necessary nor desirable - 87 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen for the ARPANET to resequence routing updates before delivering them to a gateway), but it also reduces the reliability of transmission through the ARPANET, and it is not obvious how this trades off. For each network which we intend to use as a component of the internet, we will have to carefully study the details of its network access protocol, and possibly do some experiments to see how the various details of network access affect the performance, in terms of delay, throughput, and reliability of the network. Only by careful attention to the details of network access on each particular network, and by continuing measurements and instrumentation in the gateways to see if we are getting the expected performance from the component networks, can we hope to make the routing updating protocol quick and reliable enough to ensure consistent and loop-free routing throughput the internet. There are a few general principles we might appeal to, such as making routing updates be the highest priority traffic that we send into the component networks. However, it is difficult to be sure a priori what effect even so straightforward a principle might have. It's not hard to imagine a poorly designed network in which low priority packets receive better performance than high priority ones, under certain circumstances. To make the internet robust, we need to be able to detect such situations (and to gather enough evidence, via measurements, to enable us to point the finger convincingly), and we cannot simply assume that a component network will perform as advertised. - 88 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen If we might digress a little, the considerations of the preceding paragraphs raise an interesting issue with respect to the use of fragmentation in the gateways. We raised the possibility of not using multi-packet ARPANET messages, and such a strategy would doubtless require more fragmentation than is presently done. Fragmentation in the gateways has long been thought of as a necessary evil, necessary because some networks have a smaller maximum packet size than others. If a gateway receives a packet from network A which is too large to fit into network B, then the gateway must either fragment it or drop it on the floor. However, perhaps fragmentation is sometimes useful as an optimization procedure. That is, some network may have a suitably large maximum packet size so that fragmentation is, strictly speaking, unnecessary. Nevertheless, the network might actually perform better if given smaller packets, so that fragmentation provides better performance. We see this in some current Catenet problems. It seems that the BBN-gateway between ARPANET and SATNET often receives packets from SATNET which are 2000 bits long, or twice the size of an ARPANET packet. The gateway then presents these messages to the ARPANET as two-packet messages. As it happens, two-packet messages generally give the lowest possible throughput on the ARPANET (a consequence of the limited buffer space at the destination IMPs and the fact that the ARPANET assumes that all multi-packet messages will contain 8 packets); the gateway could probably obtain better performance - 89 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen from the ARPANET by fragmenting the two-packet message into two single-packet messages. Of course, the situation is a bit more complicated in general than this may make it seem. If messages are being sent from a source host through SATNET and then through ARPANET to a destination host, best performance might well be achieved by sending the messages as 2000-bit messages through SATNET, then fragmenting them and sending them as 1000-bit messages through ARPANET. However, what if the messages must go beyond ARPANET, through another network, which handles 2000-bit messages more efficiently than 1000-bit messages? This sort of strategy, if useful at all, is best done in combination with the hop-by-hop fragmentation/reassembly scheme suggested in IEN 187. The part of the routing updating protocol which deals with recovery from partitions (including the degenerate case of initialization when a Switch comes up) is somewhat more tricky to apply to the internet environment. In the ARPANET, we have a number of one-minute timers. Each IMP must generate an update at least once per minute; a line that is ready to come up must participate in the updating protocol for a minute before being declared up; and an update that has been held for a minute in an IMP, with no later update from that update's source IMP having been seen, is regarded as "old", in the sense that its sequence number is no longer considered when the IMP is deciding whether the next update it sees (from the same source) is acceptable. In attempting to adapt these procedures to the internet, we must - 90 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen take notice of the way in which these timers interact with each other and with other features of the internet. Consider, for example, the length of the maximum update lifetime, which determines how long an update's sequence number remains valid for the purposes of judging the acceptability of the next update. There are two restrictions on the length of this timer: 1) A Switch A should not time out an update whose source Switch is B unless there really is a partition which destroys the communication path between A and B (remember, this includes the degenerate case of a partition where B simply goes down). This means that the time-out period must be greater than the sum of the maximum interval between updates PLUS the maximum amount of time that an update from B could take to get to A. 2) The sequence numbering scheme used for the updates must be such that the sequence numbers cannot wrap around in a period of time which is less than the maximum update life-time. In the ARPANET, the sequence numbers cannot wrap in less than a few minutes, each IMP generates an update at least once per minute, and the time to get that update to all other IMPs is negligible when compared to a minute, so a maximum update lifetime of one minute is fine. In the internet, however, we could not expect to measure transit times in the hundreds of - 91 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen milliseconds; tens of seconds would be more like it. So even if we forced each gateway to generate at least one update per minute, we would still need a maximum update lifetime of several minutes. And the longer our maximum update lifetime, the larger our sequence number space must be (to prevent wrap-around), which means additional overhead (memory and bandwidth) to represent the sequence numbers. A similar constraint applies to the "waiting period". The purpose of the waiting period is to ensure that when a gateway-gateway Pathway is ready to come up, it is not permitted to carry data until an update from each other gateway traverses it. Clearly, for this to have the proper effect, the waiting period must be longer than the sum of the maximum transit time plus the maximum interval between the generation of updates from a single gateway. We would probably also have to set this to several minutes. This does have a serious operational consequence, namely that no outage will persist for less than several minutes. This can be an inconvenience, lengthening the time it takes to put out a new software release to all the gateways, for example, and possibly affecting the MTTR statistics, but it is something we just have to live with. Note, by the way, that as long as the waiting period is at least as long as the maximum update lifetime, a gateway that restarts after a failure (or a reload) can start generating updates with sequence number 0, irrespective of what sequence numbers it was - 92 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen using before, since all its prior updates will have timed out (if the timers are set right). 4.6 Limitations of Internetting This discussion of routing in the internet points out some of the inherent limits of internetting. Good performance requires the use of a routing updating procedure which broadcasts the updates in a very reliable and quick manner. Anything that delays the routing updates, or makes their transmission less than reliable, will lengthen the amount of time during which different Switches have a different "picture" of the Network Structure, which in turn will degrade performance. We believe that the updating protocol we developed for the ARPANET solves these problems in the context of the ARPANET. It seems clear, however, that broadcasting routing updates in the internet is just going to be slower and less reliable than it is in the ARPANET. Although the same principles seem to apply in both cases, the characteristics of the internet Pathways are not sufficiently stable to ensure the speed and reliability that we really would like to have. It is going to be very hard to ensure that we can get our routing updates through the various component networks of the internet in a timely and reliable manner, and it may be hard to get the component networks to handle the internet routing updates with enough priority to prevent them from being blocked due to congestion. This is going to place a limit on internet - 93 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen performance which we cannot avoid no matter what architecture we choose. The only way to eliminate this sort of problem would be to have the component networks themselves give special treatment to internet control packets, such as routing updates. Currently, the component networks of the internet treat internet control packets as mere data. We have suggested that in some cases, it is impossible to meet certain of our goals without special help from the underlying networks. For example, in our discussion of the "gateway discovery protocol", we argued that preserving the maximum flexibility for making topological changes in the internet requires cooperation from the underlying networks. This point can be generalized, though. The more cooperation we can get from the underlying networks, the better we can make our internet routing algorithm perform, and the better we can make the internet perform. We would recommend therefore that serious consideration be given to modifying the component networks of the Catenet to maximize their cooperation with the internet. Even if the component networks of the internet cooperate to the fullest, there is another problem which may limit the responsiveness of the internet routing algorithm. If there are very long transit times across the internet, much longer than we ever see in individual networks like the ARPANET, then the responsiveness of routing is necessarily held down. This factor - 94 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen will place a natural restriction on the growth of the internet. At a certain point, it will become just too big to be treated as a single Network Structure, so that further growth would make routing too non-responsive to provide good service. That is, eventually we reach a point of diminishing returns, where adding more Switches, or even adding more levels of hierarchy, begins to significantly degrade service throughout the internet by making the routing algorithm too non-responsive. It is important to understand that the notion of "big" here has nothing to do with the number of Switches, but rather with the transit time across the internet. If there are two Hosts which cannot, for reasons like this, be placed on the same internet, it may still be possible for them to communicate, though at a somewhat reduced level of efficiency. Each of the Hosts would have to be on some internet, but not necessarily on the same one. Suppose, for example, that there are two different internets, internet A and internet B, which cannot be combined into one larger internet because the resultant internet would be too large to permit a reasonably responsive routing algorithm. However, it is still possible for each internet to model the other one as an Access Pathway. Suppose that Host H1 on internet A needs to communicate with Host H2 on internet B. Then if a Switch SA of internet A can be connected to a Switch SB of internet B, the internet A can represent Host H2 as being homed to its Switch SA, via a Pathway (of whose - 95 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen internal structure it is unaware) which is actually internet B. A corresponding mapping can be made in the other direction, permitting full-duplex communication. However, neither internet could use the other as an internal (i.e., Switch-Switch) Pathway, or the resulting configuration would be insufficiently responsive. (This may seem akin to the regionalization against which we argued in section 4.3.4. However, since neither internet uses the other as an internal Pathway, there are no problems of looping.) Naturally, just as Hosts on a common network can expect to get more efficient communications than can Hosts which must communicate over an internet, Hosts on a common internet will get more efficient communications than will hosts on different internets. There are other reasons besides non-responsiveness which may make it imperative to have separate internets which cannot use each other as internal Pathways. For example, two internets might cover the same "territory," geographically speaking, but may be under the control of two different organizations, or may use essentially different algorithms or protocols. In fact, several different internets might even cover the same set of Hosts, and consist of the same set of component packet-switching networks. (It is important to remember that it is the set of gateways which constitute the internet, not the set of component networks. Imagine if every ARPA-controlled network had a Brand X gateway and a Brand Y gateway. Then there would be two separate - 96 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen internets, Brand X and Brand Y, which are logically rather than physically separate.) Our procedure of having each internet regard the other as an Access Pathway to a set of Hosts, but not as an Internal Pathway, allows communication among Hosts on the different internets, without introducing problems of looping, and while preserving the maintainability of the individual internets. Of course if the two internets have different access protocols, then the Switches of one or the other internet (or both) must be prepared to translate from one protocol to the other, but that is a simpler problem than the ones we have been dealing with. - 97 - IEN 189 Bolt Beranek and Newman Inc. Eric C. Rosen REFERENCES 1. J.M. McQuillan, I. Richer, E.C. Rosen, "The New Routing Algorithm for the ARPANET," IEEE TRANSACTIONS ON COMMUNICATIONS, May 1980. 2. E.C. Rosen, "The Updating Protocol of ARPANET's New Routing Algorithm," COMPUTER NETWORKS, February 1980. 3. J.M McQuillan, I. Richer, E.C. Rosen, ARPANET ROUTING ALGORITHM IMPROVEMENTS: FIRST SEMIANNUAL TECHNICAL REPORT, BBN Report No. 3803, April 1978. 4. J.M. McQuillan, I. Richer, E.C. Rosen, D.P. Bertsekas, ARPANET ROUTING ALGORITHM IMPROVEMENTS: SECOND SEMIANNUAL TECHNICAL REPORT, BBN Report No. 3940, October 1978. 5. E.C. Rosen, J.G. Herman, I. Richer, J.M. McQuillan, ARPANET ROUTING ALGORITHM IMPROVEMENTS: THIRD SEMIANNUAL TECHNICAL REPORT, BBN Report No. 4088, March 1979. 6. E.C. Rosen, J. Mayersohn, P.J. Sevcik, G.J. Williams, R. Attar, ARPANET ROUTING ALGORITHM IMPROVEMENTS: VOLUME 1, BBN Report No. 4473, August 1980. - 98 -