A routing architecture for very large networks undergoing rapid reconfiguration

ABSTRACT

A routing architecture is described for very large communications networks with greater than 10,000 routing nodes and 100,000 end nodes. This architecture, called the Traveler Architecture, is designed to be independent of network configuration and to be robust even under conditions of rapid reconfiguration. Traveler is an extension of the ISO routing protocols. The Traveler architecture is designed to work with traffic characteristic of existing large networks, such as the Internet. While Traveler does not require a particular routing algorithm, it is designed to work in conjunction with families of distributed routing algorithms. Because Traveler is based on the paradigm of a human traveler, it attempts to use non-deterministic and heuristic methods rather than purely algorithmic methods to determine high quality routes between two points. Traveler builds on the Landmark and Area routing architectures.

REFERENCES

• 1: Ross Callon. A comparison of "Link State" and "Distance Vector" routing algorithms. Technical Report IDEA 0002-00, SRI-NIC, November 1987.
• 2: Cheung-Wing Chan and Tak-Shing P Yum. An algorithm for detecting and resolving store-and-forward deadlocks in packet switched networks. IEEE Transactions on Communications, 35(8), August 1987.
• 3: J. Joaquin Garcia-Luna-Aceves. A new minimum-hop routing algorithm. In Proceedings of the IEEE International Conference on Communications, 1987.
• 4: H. Garcia-Molina, B. Kogan, and N. Lynch. Reliable broadcast in networks with nonprogrammable servers. In Proc. 8th Intl. Conf. on Distributed Computing Systems, pages 428- 438, June 1988.
• 5: J. L. Hammond and J. D. Spragins. Rapidly reconfiguring computer communication networks-definition and major issues. In Proceedings of the IEEE International Conference on Communications, 1987.
• 6: Accredited Standards Committee X3S3.3- Information Processing Systems-Data Communications-Intermediate System to Intermediate System Intra-Domain Routing Exchange Protocol, November 1987. X3S3.3/87- 150R.
• 7: Information Processing Systems - Open Systems Interconnection - Basic Reference Model.
• 8: ISO International Standard 8648 - Information Processing Systems - Telecommunications and Information Exchange between Systems - Internal Organization of the Network Layer.
• 9: ISO International Standard 9542 - Information Processing Systems - Telecommunications and Information Exchange Between Systems - End System to Intermediate System Routing Exchange Protocol for Use in Conjunction with the Protocol for Providing the Connectionless-mode Network Service (ISO 8473), 1988.
• 10: P. Jain , S. S. Lam, Specification and verification of collusion-free broadcast networks, Symposium proceedings on Communications architectures and protocols, p.282-291, August 16-18, 1988, Stanford, California, United States
• 11: L. Kleinrock and F. Kamoun. Hierarchical routing for large networks: Performance evaluation and optimization. Computer Networks, 1, 1977.
• 12: J. McQuillan. The new routing algorithm for the ARPANET. IEEE Transactions on Communications , May 1980.
• 13: Sridhar Narasimhan , Hasan Pirkul , Prabuddha De, Route selection in backbone data communication networks, Computer Networks and ISDN Systems, v.15 n.2, p.121-133, Feb. 1988 [doi>10.1016/0169-7552(88)90048-7]
• 14: Radia Perlman. Fault-Tolerant broadcast of routing information. Computer Networks, December 1983.
• 15: Radia Perlman. Hierarchical networks and the subnetwork partition problem. Computer Networks and ISDN Systems, 9:297-303, 1985.
• 16: T. G. Robertazzi and P. E. Sarachik. Self-organizing communication networks. IEEE Communications Magazine, 24(1):28-33, January 1986.
• 17: M. S. Sloman and X. Andriopoulos. A routing algorithm for interconnected local area networks. Computer Networks and ISDN Systems, 9:109-130, 1985.
• 18: Donald M Topkis. A k shortest path algorithm for adaptive routing in communications networks. IEEE Transactions on Communications, 36(7):855-859, July 1988.
• 19: Paul F. Tsuchiya. Landmark routing: Description and analysis. Technical Report MTR- 87WOO152, The Mitre Corporation, June 1987.
• 20: P. F. Tsuchiya, The landmark hierarchy: a new hierarchy for routing in very large networks, Symposium proceedings on Communications architectures and protocols, p.35-42, August 16-18, 1988, Stanford, California, United States
• 21: Paul F. Tsuchiya. Landmark routing: Architecture, algorithms, and issues. Technical Report MTR-87WOO174, The Mitre Corporation, May 1988.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Open Systems Interconnection reference model (OSI)

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Design, Performance