Topology aggregation for hierarchical routing in ATM networks

Abstract

This paper provides a tutorial for topology arregation in large hierarchical communication networks. Specifically, it examines some issues of topology aggregation for hierarchical PNNI Routing in ATM networks, presents a complex node representation, and provides some guidelines for topology aggregation. There are two main reasons for topology aggregation. First, topology information must be compressed to avoid excessive complexity in topology adevertisement. Second, the internal topology of a network may have to be hidden for security reasons. A desirable topology aggregation method must adequately represent the topology of a given network for efficient routing and netowrk resource allocation, using a compact advertised topology.

References

1. {1} Doug Dykeman (Editor), "PNNI Draft Specification," ATM Forum, Contribution 94- 0471 (latest version), March 1995.
2. {2} Kumar Sivarajan & Whay Lee, "Issues in the Aggregation of Link State Parameters in Hierarchical PNNI Networks," ATM Forum, Contribution 94-0646, July 1994.
3. {3} Whay Lee & Ted Tedijanto, "Proposed Baseline Text for Topology Aggregation in PNNI Routing," ATM Forum, 94-1154, November/December 1994.
4. {4} Whay Lee, "Some Guidelines for PNNI Topology Aggregation," ATM Forum, 95- 0153, February 1995.
5. {5} Joel Halpern & Ross Callon, "Link and Node Metrics," ATM Forum, Contribution 94-0590, July 1994.
6. {6} Vasant Sahay, Jonathan Davar, & Farokh Deboo, "Metrics for Representing Internal Topology of a Logical Group Node," ATM Forum, 94-0449, May 1994.
7. {7} Ted Tedijanto & Whay Lee, "Proposed Baseline Text for Link State Parameters and Update Protocol," ATM Forum, 94-0645, July 1994.
8. {8} Whay Lee, "Classification of Link State Parameters," ATM Forum, 94-0672, July 1994.
9. {9} Whay Lee, "Classification of Nodal State Parameters," ATM Forum, 95-0134, February 1995.
10. {10} David Peleg & Eli Upfal, "A Trade-Off between Space and Efficiency for Routing Tables," Journal of the ACM, Vol. 36, No. 3, pp. 510-530, July 1989.
11. {11} Ingo Althofer, Gautam Das, David Dobkin, Deborah Joseph, & Jose Soares, "On Sparse Spanners of Weighted Graphs," Discrete Computational Geometry, Vol. 9, pp. 81-100, 1993.
12. {12} Whay Lee, "Complexity of Metric Aggregation," ATM Forum, 95-0200, February 1995.
13. {13} David Peleg & Alejandro A. Schaffer, "Graph Spanners," Journal of Graph Theory, Vol. 13, No. 1, pp. 99-116, 1989.
14. {14} Baruch Awerbuch, "Complexity of Network Synchronization," Journal of the ACM, Vol. 32, No. 4, pp. 804-823, 1985.
15. {15} Whay Lee & Joel Halpern, "Cell Loss Ratio -- Link Attribute or Link Metric?" ATM Forum, 95-0133, February 1995.
16. {16} Whay Lee, "A Minimal Spanning Connectivity Method for Link State Aggregation," ATM Forum, 94-0673, July 1994.
17. {17} Whay Lee, "Spanning Tree Method for Link State Aggregation in Large Communication Networks," IEEE INFOCOM '95, April 1995.
18. {18} Whay Lee, "Topology Aggregation in PNNI Routing," ATM Forum, 94-0874, September 1994.
19. {19} Whay Lee & Michael Hluchyj, "Multi-Criteria Routing subject to Resource and Performance Constraints," ATM Forum, 94-0280, March 1994.
20. {20} Joel Halpern, "Nodal Metrics with Pairwise Values," ATM Forum, 94-0862, September 1994.
21. {21} Ethan Spiegel, "Representation of Node Parameters Using Exceptions," ATM Forum, 94-0907, September 1994.
22. {22} Joel Halpern, "Allocating Resources in Transit Peer Groups," ATM Forum, 95-0100, February 1995.
23. {23} Whay Lee & Ted Tedijanto, "Topology Aggregation and Path Selection in PNNI Routing," ATM Forum, 94-1155, November 1994.

Index Terms

• Networks

  • Network properties

    • Network structure

  • Network services

    • In-network processing

  • Network types

    • Wired access networks

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems