Internet routing over large public data networks using shortcuts

ABSTRACT

With the emergence of large switched public data networks that are well-suited to connectionless internets, for instance SMDS, it is possible that larger and larger numbers of internet users will get their connectivity from large public data networks whose native protocols are not the same as the user's internet protocol. This results in a routing problem that has not yet been addressed. That is, large numbers of routers (potentially tens of thousands) must be able to find direct routes to each other in a robust and efficient way. This paper describes a solution to the problem, called shortcut routing, that incorporates 1) a sparse graph of logical connectivity between routers, 2) hierarchical addressing among the public data network subscribers, and 3) the use of “entry router” information in packets to allow routers to find one hop “shortcuts” across the multi-hop logical graph.

REFERENCES

• Apl: Sidhu, G.S. et. al., "Inside AppleTalk", Addison Wesley, Reading, Massachusetts, 1989.
• LR: Lougheed, K., Rekhter, Y., "Border Gateway Protocol (BGP)", RFC-I163, USC/Information Sciences Institute, June 1990.
• Dec: Carl Malamud, Analyzing DECnet/OSI Phase V, Van Nostrand Reinhold Co., New York, NY, 1991
• Ro: Rosen, E.C., "Exterior Gateway Protocol (EGP)", RFC-827, USC/Information Sciences Institute, October 1982.
• Ipx: Carl Malamud, Analyzing NOVELL Networks, John Wiley & Sons, Inc., New York, NY, 1991
• KK: Kamoun, F., Kleinrock, L., "Hierarchical Routing for Large Networks", Computer Networks 1 (1977), North-Holland Publishing Co.
• OSI1: International Organization for Standardization ISO10589, "Intermediate System to Intermediate System Intra-Domain routeing exchange protocol for use in Conjunction with the Protocol for providing the Connectionless-mode Network Service (ISO 8473)"
• OSI2: International Organization for Standardization iSO8348, Addendum 2, "Network Layer Addressing"
• OSI3: International Organization for Standardization ISO8473, "Protocol for providing the Connectionless-mode Network Service"
• OSI4: International Organization for Standardization CD10747~ "Protocol for Exchange of Interdomain Routeing Information among Intermediate Systems to Support Forwarding of ISO 8473 PDUs"
• OSPF: Moy, J., "OSPF Specification", RFC-1131, USC/ Information Sciences Institute, October 1989.
• Pax: Paxson, V., "Measurements and Models of Wide Area TCP Conversations", LBL-30840, Lawrence Berkeley Laboratory, Berkeley, CA, USA, May 1991
• Pos: Postel, J.B., "DoD Standard internet Protocol", RFC-760, USC/Information Sciences Institute, January 1980.
• Sch: Mischa K. Schwartz, Computer Communications Network Design and Analysis, Prentice Hall PTR, Upper Saddle River, NJ, 1977
• TL: Tsuchiya, P., Lawrence, J., "iP Routing and Discovery over SMDS", IETF Internet Draft, available via Anonymous FTP at nnsc.nsf, net, fiI e in t e rne t-d ra fts/d raft- i et f- i pl pdnshortcutrouting-00.txt.

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.1 Network Architecture and Design
          Subjects: Packet-switching networks
          Nouns: ARPANET

  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:
Algorithms, Design