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.

One of the most compelling long term problems facing the IP and emerging 0S1 Internet is growth, At the same time, policy routing-the ability of a packet source to determine the type of path its packets will take, or the ability of a transit network to restrict usage-is increasingly required.A hierarchical addressing format reflecting the hierarchical backbone structure reduces routing overhead, but restricts paths to the backbones implied by the address, thus limiting policy and reducing robustness.To overcome this restriction, yet keep the efficiency of hierarchical addressing, this paper proposes the use of multiple addresses.In this scheme, directory service would return multiple addresses, and the host would choose the ones appropriate for its policies, any of which could be used during a connection, as network conditions deem appropriate.This paper establishes a framework for the new technique by exploring the fundamentals of routing and addressing, describes the new technique, and discusses its role as a policy mechanism.

The author explores algorithms where resource-starved nodes can still function to their fullest useful capacity without creating loops. One such algorithm is efficient compared to standard SPF-style algorithms. In nearly all cases, the paths found using the algorithm are the shortest possible for the given insufficient resources.>

Landmark Routing is a set of algorithms for routing in communications networks of arbitrary size. Landmark Routing is based on a new type of hierarchy, the Landmark Hierarchy. The Landmark Hierarchy exhibits path lengths and routing table sizes similar to those found in the traditional area or cluster hierarchy. The Landmark Hierarchy, however, is easier to dynamically configure using a distributed algorithm. It can therefore be used as the basis for algorithms that dynamically configure the hierarchy on the fly, thus allowing for very large, dynamic networks. This paper describes the Landmark Hierarchy, analyzes it, and compares it with the area hierarchy.