Scalable inter-domain routing architecture

ABSTRACT

As internets grow, both in size and in the diversity of routing requirements, providing inter-domain routing that can accommodate both of these factors becomes increasingly crucial. We propose a scalable inter-domain routing architecture consisting of two major components: source-demand routing (SDR) and node routing (NR). The NR component pre-computes and installs routes that are shared by a significant number of sources. These generic routes are commonly used and warrant wide propagation. The SDR component provides on-demand computation and installation of specialized routes that are not shared by enough sources to justify computation by NR. The potentially large number of different specialized routes, combined with their sparse utilization, make them too costly to support with the NR mechanism. Together NR and SDR address the issue of scaling to global internet sizes without restricting the availability of a diverse set of routes. Routing will adapt naturally over time to changing traffic patterns and new services by shifting computation and installation of particular types of routes between the two components. To complement earlier discussions of SDR design choices [3], this paper evaluates the algorithmic design choices for the NR component in terms of scalability and functionality. In addition, we discuss mechanisms for improving the scaling properties of link-state SDR, and for integrating the two components of the architecture.

REFERENCES

• 1: "Intermediate System to Intermediate System Intra-Domain Routing Exchange Protocol", ANSI X3S3.3/87-150R.
• 2: Lougheed, K., Rekhter, Y., "A Border Gateway Protocol 3 (BGP-3)", Internet RFC 1267, SRI Network Information Center, October 1991.
• 3: L. Breslau , D. Estrin, Design of inter-administrative domain routing protocols, Proceedings of the ACM symposium on Communications architectures & protocols, p.231-241, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 4: Clark, D., "Policy Routing in Internetworks" Journal of Internetworking Research and Experience, Vol. 1, pp. 35-52, 1990.
• 5: Dijkstra, E., "A Note on Two Problems in Connection with Graphs", Numer. Math., Vol. 1, 1959, pp. 269-271.
• 6: "Inter-Domain Intermediate Systems Routing", Draft Technical Report ECMA TR/ISR, ECMA/TC32-TG 10/89/56, May 1989.
• 7: E. Rosen, "Exterior Gateway Protocol (EGP)" Internet RFC 827, SRI Network information Center, October 1982.
• 8: Estrin, D., "Policy Requirements for Inter Administrative Domain Routing", Internet RFC 1125, SRI Network Information Center, November 1989.
• 9: Estrin, D., Breslau, L., and Zhang, L., "Protocol Mechanisms for Adaptive Routing in Global Multimedia Internets", University of Southern California, Computer Science Department Technical Report, CS-SYS-91-04, November 1991.
• 10: Charles Hedrick, "Routing Information Protocol", Internet RFC 1058, SRI Network Information Center, June 1988.
• 11: Steenstrup, M., "inter-Domain Policy Routing Protocol Specification and Usage: Version 1", Internet Draft, February 1991.
• 12: "Intermediate System to Intermediate System inter-domain Routeing Exchange Protocol", ISO/IEC/JTC1/SC6 CD10747.
• 13: "Information Processing Systems - Telecommunications and Information Exchange between Systems - Intermediate System to Intermediate System Intra-Domain Routing Exchange Protocol for use in Conjunction with the protocol for providing the Connectionless-mode Network Service (ISO 8473)", ISO/IEC 10589.
• 14: Jaffee, J., Moss, F., "A Responsive Distributed Routing Algorithm for Computer Networks", IEEE Transactions on Communications, July 1982.
• 15: Little, M., "Goals and Functional Requirements for Inter-Autonomous System Routing", internet RFC 1126, SRI Network Information Center, October 1989.
• 16: Oran, D., "Expert's Paper: The Relationship between Addressing and Routeing", ISO/JTC1/SC6/WG2, 1989.
• 17: J. Moy, "The Open Shortest Path First (osrr) Specification", Internet RFC 1131, SRI Network Information Center, October 1989.
• 18: Rekhter, Y., "IDRP protocol analysis: storage complexity", IBM Research Report RC17298(~76515), October 1991.
• 19: K. G. Shin , M.-S. Chen, Performance analysis of distributed routing strategies free of ping-pong type looping, IEEE Transactions on Computers, v.36 n.2, p.129-137, Feb. 1987 [doi>10.1109/TC.1987.1676875]
• 20: Topolcic, C., "Experimental Internet Stream Protocol, version 2 (ST II)", Internet RFC 1190, October 1990.
• 21: Zaumen, W., Garcia-Luna-Aceves, J., "Dynamics of Link State and Loop-free Distance-Vector Routing Algorithms", ACM Sigcomm '91, Zurich, Switzerland, Sept. 1991.
• 22: Lixia Zhang, VirtualClock: a new traffic control algorithm for packet-switched networks, ACM Transactions on Computer Systems (TOCS), v.9 n.2, p.101-124, May 1991 [doi>10.1145/103720.103721]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      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

General Terms:
Design