Internet routing

ABSTRACT

Comprising an estimated 60,000 hosts, the DARPA Internet is the largest existing internet. This paper traces the routing information protocols used by Internet gateways to build routing tables that define the paths datagrams traverse as they travel between end systems. We articulate the weaknesses and limitations of the most commonly used routing protocols, including RIP, GGP, and HELLO and examine how the protocols interact with each other and with EGP. Finally, we trace the evolution of routing as the Internet has grown from a single backbone (ARPANET) to its present inclusion of the ARPANET, Milnet, and NSFnet cross-country networks.

REFERENCES

• Atl89: Steve Atlas. Bolt, Beranek, and Newman Inc., Private communication, February 1989.
• BG87: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• Bra88: Hans-Werner Braun. The NSFNET Routing Architecture. DARPA Networking Information Center, RFC 1093, May 1988.
• BSTM80: David R. Boggs, John F. Schoch, Edward A. Taft, and Robert M. Metcalfe. Pup: an Internetwork Architecture. IEEE Transactions on Computers, COM-28(4):612-623, April 1980.
• Com88: Douglas Comer, Internetworking with TCP/IP: principles, protocols, and architecture, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• Fed88: Mark S. Fedor. GATED: A Multi-Routing Protocol Daemon for UNIX. In Proceedings of the 1988 Summer USENIX Conference, pages 20-24, Winter 1988.
• FH88: Mark Fedor and Jefrey C. Honig. Man page for gated. Cornell Theory Center, Cornell University, Ithaca NY 14853-5201, May 1988.
• Hed88: Charles Hedrick. Routing Information Protocol. DARPA Networking information Center, RFC 1058, June 1988.
• HHS83: Robert Hinden, jack Haverty, and Alan Sheltzer. The DARPA Internet: interconnecting heterogeneous computer networks with gateways. Computer, 16(9):38-48, September 1983.
• HS82: Robert Hinden and Alan Sheltzer. DARPA Internet Gateway. DARPA Networking Information Center, RFC 823, September 1982.
• JBH78: Irwin Mark Jacobs, Richard Binder, and Estil V. Hoversten. General Purpose Packet Satellite Networks. Proceedings of the IEEE, 66(11):1448- 1467, November 1978.
• JLF*86: Dennis M Jennings, Lawrence H. Landweber, Ira H. Fuchs, David J. Farber, and W. Richards Adrion. Computer Networking for Scientists. Science; 231:943-950, February 1986.
• Kir84: Paul Kirton. EGP Gateway under Berkeley UNIX 4.2. DARPA Networking Information Center, RFC 911, August 1984.
• MB87: D. L. Mills , H. Braun, The NSFNET backbone network, Proceedings of the ACM workshop on Frontiers in computer communications technology, p.191-196, August 11-13, 1987, Stowe, Vermont, United States
• MFR78: John M. McQuillan, Gilbert Falk, and Ira Richer. A Review of the Development and Performance of the ARPANET Routing Algorithm. IEEE Transactions on Computers, COM-26(12):1082- 1811, December 1978.
• MilS3: David L. Mills. DCN local-network protocols. DARPA Networking Information Center, RFC 891, December 1983.
• Mil84: David L. Mills. Exterior Gateway Protocol Formal Specification. DARPA Networking Information Center, RFC 904, April 1984.
• Mil86: David L. Mills. Autonomous Conferations. DARPA Networking Information Center, RFC 975, February 1986.
• MRR78: John M. McQuillan, Ira Richer, and Eric C. Rosen. ARPANET Rouling Algorithm Improvements First Semiannual Technical Report. Technical Report 3803, Bolt Beranek and Newman Inc., April 1978.
• MRR80: John M. McQuillan, Ira Richer, and Eric C. Rosen. The New Routing Algorithm for the ARPANET. iEEE Traasactions oa Computers, COM-28(5):711-719, May 1980.
• MW77: John M. McQuillen and D. C. Walden. The ARPANET Design Decisions. Computer Networks, 1(5), September 1977.
• Pos80: Jonathon Postel. Internetwork Protocol Approaches. IEEE Transactions on Computers, COM- 28(4):605-611, April 1980.
• Pos81: jonathon B. Postel. Internet Control Message Protocol. DARPA Networking Information Center, RFC 792, September 1981.
• QSP85: John S. Quarterman , Abraham Silberschatz , James L. Peterson, 4.2BSD and 4.3BSD as examples of the UNIX system, ACM Computing Surveys (CSUR), v.17 n.4, p.379-418, Dec. 1985 [doi>10.1145/6041.6043]
• Rek88a: J Rekhter. EGP and Policy Based Routing in the New NSFNET Backbone. DARPA Networking Information Center, RFC 1092, March 1988.
• Rek88b: J Rekhter. The NSFNET Backbone SPF based Interior Gateway Protocol. DARPA Networking Information Center, RFC 1058, June 1988.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.1 Data Communications Devices
          Subjects: Processors**

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

          Nouns: Internet; ARPANET
      C.2.2 Network Protocols
          Subjects: Protocol architecture (OSI model)

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS

      Nouns: DARPA

General Terms:
Algorithms, Design