The landmark hierarchy: a new hierarchy for routing in very large networks

ABSTRACT

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.

REFERENCES

• 1: Callon, R. and Lauer, G. (June 1985), "Hierarchical Routing for Packet Radio Networks," Report No. 5945, SRNTN No. 31, Cambridge, MA: BBN Laboratories Incorporated.
• 2: Cegrell, T. (June 1975), "A Routing Procedure for the Tidas Message-Switching Network," IEE Trans. on Communications, VoL COM-23, No. 6, pp. 575-585.
• 3: Gaxcia-Luna-Aceves, J. I. (1987), "A New Minimum- Hop Routing Algorithm," Proceedings IEEE Infocom '87, pp. 170-180.
• 4: Jacob Hagouel, Issues in routing for large and dynamic networks, 1983
• 5: Jaffe, J. M. aad:Moss, F;H~(Yuly 1982), "A Responsive Distributed RoutingAIgoritlim for Computer Networks," 1EEE Trans. on Communications, COM-30, No. 7, pp. 1758-1762.
• 6: Khanna, A. and S0eger, $. (January 1986), "Large Network Routing Study. Design Documem," Report No. 6119, Cambridge, MA: BBN Communications Corporation.
• 7: Kleinrock, L. and Kamoun, F. (1977), "Hierarchical Routing for Large Networks: Performance Evaluation and Optimization," Computer Networks, Vol. 1, pp. 155-174.
• 8: Kleinrock, L. and Kamoun F. (November 1979), "Stochastic Performance Evaluation of Hierarchical Rouiing for Large Networks," Computer Networks, Vol. 3, No. 5, pp. 387-353.
• 9: Kleinrock, L. and Kamoun, F. (1980), "Optimal Clustering Structures for Hierarchical Topological Design of Large Computer Networks," Computer Networks, Vol. 10, No. 3, pp. 221-248.
• 10: McQuillan, J. M., Richer, I., Rosen, E. C. (April 1978) "ARPANET Routing Algorithm Improvements First Semiannual Technical Report," Bolt Beranek and Newman Inc., Report No. 3803.
• 11: Sape J. Mullender , Paul M. B. Vitányi, Distributed match-making for processes in computer networks (preliminary version), Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.261-271, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323620]
• 12: Perlman, R. (1985), "Hierarchical Networks and the Subnetwork Partition Problem," Computer Networks and ISDN Systems 9, North-Holland, pp. 297-303.
• 13: Shacham, N. (November 1985), "Hierarchical Routing in Large, Dynamic Ground Radio Networks," Menlo Park, CA: SRI International.
• 14: Sparta Incorporated, (April 1986), "Design and Analysis for Area Routing in Large Networks," McLean, VA: Sparta Incorporated.
• 15: $tine, R. H. Jr. and Tsuchiya, P. F. (March 1987), "Assured Destination Binding: A Technique for Dynamic Address Binding," MTR-87W00050, McLean, VA: The MITRE Corporation.
• 16: Sunshine, C. (April 1981), "Addressing Problems in Multi-network Systems," Intemet Engineering Note (raN) ~78.
• 17: William D. Tajibnapis, A correctness proof of a topology information maintenance protocol for a distributed computer network, Communications of the ACM, v.20 n.7, p.477-485, July 1977 [doi>10.1145/359636.359701]
• 18: Tsuchiya, P. F. (June 1987a), "The Landmark Hierarchy: Description and Analysis," MTR-87W00152, McLean, VA: The MITRE Corporation.
• 19: Tsuchiya, P. F. (September 1987b), "Landmark Routing: Architecture, Algorithms, and issues," MTR-87W00174, McLean, VA: The MITRE Corporation.
• 20: Westcott I. and Lauer, G. (1984), "Hierarchical Routing for Very Large Networks," Cambridge, MA: Bolt Beranek and Newman Incorporated.

INDEX TERMS

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

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Performance