AN OVERVIEW OF THE NEW ROUTING ALGORITHM FOR THE ARPANET John M. McQuillan Ira Richer Eric C. Rosen Bolt Beranek and Newman Inc. Cambridge, MA (Originally published in: Proc. Sixth Data Communications Symposium, November, 1979) Summary* The original routing algorithm of the ARPANET, in service for over a decade, has recently been removed from the ARPANET and replaced with a new and different algorithm. Although the new algorithm, like the old, is a distributed, adaptive routing algorithm, it is not similar to the old in any other important respect. In the new algorithm, each node maintains a data base describing the delay on each network line. A shortest- path computation is run in each node which explicitly computes the minimum-delay paths (based on the delay entries in the data base) from that node to all other nodes in the network. The average delay on each network line is measured periodically by the nodes attached to the lines. These measured delays are broadcast to all network nodes, so that all nodes use the same data base for performing their shortest-path computations. The new routing algorithm was extensively tested on the ARPANET before being released. This paper describes the algorithm and summarizes the results of these tests. Introduction The last decade has seen the design, implementation, and operation of several routing algorithms for distributed networks of computers. The first such algorithm, the original routing algorithm for the ARPANET, has served remarkably well considering * This research was sponsored by the Defense Advanced Research Projects Agency under ARPA Order No. 3941, and by the Defense Communications Agency (OoD), Contract No. MDA903-78-C- 0129, monitored by DSSW. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either express or implied, of the Defense Advanced Research Projects Agency, the Defense Communications Agency, or the United States Government how long ago (in the history of packet switching) it was conceived. This paper describes the new routing algorithm we installed recently in the ARPANET. Readers not familiar with our earlier activities may consult [1] for a survey of the ARPANET design decisions, including the previous routing algorithm, readers interested in a survey of routing algorithms for other computer networks and current research in the area may consult [2]. A distributed, adaptive routing scheme typically has a number of separate components, including (1) a measurement process for determining pertinent network characteristics, (2) a protocol for disseminating information about these characteristics, and (3) a calculation to determine how traffic should be routed. A routing "algorithm" or "procedure" is not specified until all these components are defined. In the present paper we discuss these components of the new ARPANET algorithm. We begin with a brief outline of the shortcomings of the original algorithm and then provide a description of the new procedure. The algorithm has undergone extensive testing in the ARPANET under operational conditions; the final section gives a summary of the test results. The present paper is a summary of our conclusions only; for more complete descriptions of our research findings, see our internal reports on this project [3, 4, 5]. Problems with the Original Algorithm The original ARPANET routing algorithm and the new version both attempt to route packets along paths of least delay. The total path is not determined in advance; rather, each node decides which line to use in forwarding the packet to the next node. In the original approach, each node maintained a table of estimated delay to each other node, and sent its table to all adjacent nodes every 128 as. When node I received the ACM SIGCOMM -54- Computer Communication Reviewtable from an adjacent node J. it would first measure the delay from itself to J. (We will shortly discuss the procedure used for measuring the delay.) Then it would compute its delay via J to all other nodes by adding to each entry in J's table its own delay to J. Once a table was received from all adjacent nodes, node I could easily determine which adjacent node would result in the shortest delay to each destination node in the network. In recent years we began to observe a number of problems with the original ARPANET routing algorithm [6] and have come to the conclusion that a complete redesign was the only way to solve some of them. In particular, we decided that a new algorithm was necessary to solve the following problems: - Although the exchange of routing tables consumed only a small fraction of line bandwidth, the packets containing the tables were long, and the periodic transmission and processing of such long, high-priority packets can adversely affect the flow of network traffic [7]. Moreover, since the updates contain an entry for each network node, the routing packets would become corresponding larger (or more frequent) as the ARPANET grows to 100 or more nodes, thereby exacerbating the problem. - The route calculation is performed in a distributed manner, with each node basing its calculation on local information together with calculations made previously at every other node. With such a scheme, it is difficult to ensure that routes used by different nodes are consistent, - The rate of exchange of routing tables and the distributed nature of the calculations causes a dilemma: the network is too slow in adapting to congestion and to important topology changes, yet it can respond too quickly (and perhaps inaccurately) to minor changes. The delay measurement Procedure of the old ARPANET routing algorithm is quite simple. Periodically, an IMP counts the number of packets queued for transmission on its lines and adds a constant to these counts; the resulting number is the "length" of the line for purposes of routing. This delay measurement procedure has three serious