Pitfalls in the design of distributed routing algorithms

ABSTRACT

The bridge algorithm adopted by the IEEE 802.1 committee for interconnecting 802 LANs requires the topology of the Extended LAN to be a Spanning Tree. A distributed algorithm to compute a spanning tree dynamically has already been published [1], and adopted by the IEEE 802.1 committee [2]. In this paper, however, we describe an alternative distributed algorithm to compute a spanning tree. This algorithm, variants of which have been implemented, initially appears simpler than the IEEE 802.1 algorithm; we show, however, that it has subtle failure modes that makes it unattractive in practice. We also show that some failure modes of the Spanning Tree Algorithm introduced in this paper are characteristic of a broader class of distributed graph algorithms. Such algorithms potentially examine all possible path combinations between a source and destination in a graph. Thus, they suffer from exponential message overhead in topologies that have an exponential number of paths between source and destination. Attempts to fix this problem lead to extra complexity (in terms of CPU, bandwidth, memory) when compared to other algorithms. We briefly describe a second example belonging to this class, and propose that designers avoid such algorithms if restricting the topology or scale of the network is unacceptable.

REFERENCES

• 1: Radia Perlman, An algorithm for distributed computation of a spanningtree in an extended LAN, Proceedings of the ninth symposium on Data communications, p.44-53, September 1985, Whistler Moutain, British Columbia, Canada
• 2: "MAC Bridges,~ Draft IEEE Standard 802.1: Part D Rev C, IEEE 802.1 Document Number iEEE-802.87 1.563, Aug 1987.
• 3: F. Backes, "Transparent Bridges for Interconnection of IEEE 802 LANS,' IEEE Network, vol 2, No. 1, January 1988.
• 4: D.A. Pitt, "Source Routing for Bridged LANs,' IEEE Network, vol 2, No. 1, January 1988.
• 5: D.R. Boggs, J.F.Shoch, E.A. Taft, and R.M. Metcalfe, "PUP: An Internetwork Architecture," IEEE Transactions on Communications, April 1980.
• 6: C. Sunshine , D. Kaufman , G. Ennis , K. Biba, Interconnection of broadband local area networks, Proceedings of the eighth symposium on Data communications, p.25-32, October 03-06, 1983, North Falmouth, Massachusetts, United States
• 7: Radia Perlman, Incorporation of multiaccess links into a routing protocol, Proceedings of the eighth symposium on Data communications, p.85-94, October 03-06, 1983, North Falmouth, Massachusetts, United States
• 8: N. Strole, ~A Local Communications Network Based on Interconnected Token-Access Rings: A Tutorial," IBM J. Res. Develop, Vol 27, No 5, Sept., 1983.
• 9: Eric C. Rosen, Vulnerabilities of network control protocols: an example, ACM SIGCOMM Computer Communication Review, v.11 n.3, p.10-16, July 1981 [doi>10.1145/1015591.1015592]
• 10: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 11: J.M. McQuillan, I. Richer, E.C. Rosen, ~The New Routing Algorithm for the Arpanetf IEEE Transactions on Communications, vol com-28, no. 5, May 1980.
• 12: M. Soha and R. Perlman, ~Comparison of two LAN Bridge Approaches~~ IEEE Network, vol 2, No. 1, January 1988.

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:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Theory