P. F. Tsuchiya
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.
- Callon, R. and Lauer, G. (June 1985), "Hierarchical Routing for Packet Radio Networks," Report No. 5945, SRNTN No. 31, Cambridge, MA: BBN Laboratories Incorporated.Google Scholar
- 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.Google ScholarCross Ref
- Gaxcia-Luna-Aceves, J. I. (1987), "A New Minimum- Hop Routing Algorithm," Proceedings IEEE Infocom '87, pp. 170-180.Google Scholar
- Hagouel, J. (1983), "Issues in Routing for Large and Dynamic Networks," Phl). Thesis, Columbia University. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Khanna, A. and S0eger, $. (January 1986), "Large Network Routing Study. Design Documem," Report No. 6119, Cambridge, MA: BBN Communications Corporation.Google Scholar
- Kleinrock, L. and Kamoun, F. (1977), "Hierarchical Routing for Large Networks: Performance Evaluation and Optimization," Computer Networks, Vol. 1, pp. 155-174.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Mullander, S. J. and Vitanyi, P. M. B. (August 1985), "Distributed Matchmaking for Processes in Computer Networks," Proceedings Fourth Conference on Principles of Distributed Computing, Minaki, Ontario. Google ScholarDigital Library
- Perlman, R. (1985), "Hierarchical Networks and the Subnetwork Partition Problem," Computer Networks and ISDN Systems 9, North-Holland, pp. 297-303.Google ScholarCross Ref
- Shacham, N. (November 1985), "Hierarchical Routing in Large, Dynamic Ground Radio Networks," Menlo Park, CA: SRI International.Google Scholar
- Sparta Incorporated, (April 1986), "Design and Analysis for Area Routing in Large Networks," McLean, VA: Sparta Incorporated.Google Scholar
- $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.Google Scholar
- Sunshine, C. (April 1981), "Addressing Problems in Multi-network Systems," Intemet Engineering Note (raN) ~78.Google Scholar
- Tajibnapis, W. D. (July 1977), "A Correctness Proof of a Topology Information Maintenance Protocol for Distributed Computer Networks," Communications of the ACM, Vol. 20, No. 7, pp.477-485. Google ScholarDigital Library
- Tsuchiya, P. F. (June 1987a), "The Landmark Hierarchy: Description and Analysis," MTR-87W00152, McLean, VA: The MITRE Corporation.Google Scholar
- Tsuchiya, P. F. (September 1987b), "Landmark Routing: Architecture, Algorithms, and issues," MTR-87W00174, McLean, VA: The MITRE Corporation.Google Scholar
- Westcott I. and Lauer, G. (1984), "Hierarchical Routing for Very Large Networks," Cambridge, MA: Bolt Beranek and Newman Incorporated.Google Scholar
Index Terms
- The landmark hierarchy: a new hierarchy for routing in very large networks
Recommendations
The landmark hierarchy: a new hierarchy for routing in very large networks
SIGCOMM '88: Symposium proceedings on Communications architectures and protocolsLandmark 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 ...
The viewserver hierarchy for interdomain routing: protocols and evaluation
We present an interdomain routing protocol based on a new hierarchy, referred to as the viewserver hierarchy. The protocol satisfies policy and type of service (ToS) constraints, adapts to dynamic topology changes including failures that partition ...
The landmark hierarchy: A new hierarchy for routing in very large networks
Innovations in Internetworking
Comments