Understanding and mitigating the effects of count to infinity in Ethernet networks

ABSTRACT

Ethernet's high performance, low cost, and ubiquity have made it the dominant networking technology for many application domains. Unfortunately, its distributed forwarding topology computation protocol-the Rapid Spanning Tree Pro-tocol (RSTP)-is known to suffer from a classic count-to-infinity problem. However, the cause and implications of this problem are neither documented nor understood. This paper has three main contributions. First, we identify the exact conditions under which the count-to-infinity problem manifests itself, and we characterize its effect on forwarding topology convergence. Second, we have discovered that a forwarding loop can form during count to infinity, and we provide a detailed explanation. Third, we propose a simple and effective solution called RSTP with Epochs. This solution guarantees that the forwarding topology converges in at most one round-trip time across the network and eliminates the possibility of a count-to-infinity induced forwarding loop.

REFERENCES

• 1: "Spanning tree protocol problems and related design considerations," Cisco Systems, Inc. [Online]. Available: http://www.cisco.com/warp/ public/473/16.html
• 2: E. W. Dijkstra and C. S. Scholten, "Termination detection for diffusing computations," Inform. Process. Lett., vol. 11, no. 1, pp. 14-14, Aug. 1980.
• 3: K. Elmeleegy, "RSTP With Epochs simulator," 2007 [Online]. Avail-able: http://www.cs.rice.edu/~kdiaa/ethernet/
• 4: K. Elmeleegy, A. L. Cox, and T. S. E. Ng, "On count-to-infinity induced forwarding loops in Ethernet networks," in Proc. IEEE INFOCOM 2006, Barcelona, Spain, Apr. 2006, 13 pp.
• 5: Khaled Elmeleegy , Alan L. Cox , T. S. Eugene Ng, Etherfuse: an ethernet watchdog, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 6: R. García , J. Duato , F. Silla, LSOM: A Link State Protocol Over Mac Addresses for Metropolitan Backbones Using Optical Ethernet Switches, Proceedings of the Second IEEE International Symposium on Network Computing and Applications, p.315, April 16-18, 2003
• 7: J. J. Garcia-Lunes-Aceves, Loop-free routing using diffusing computations, IEEE/ACM Transactions on Networking (TON), v.1 n.1, p.130-141, Feb. 1993 [doi>10.1109/90.222913]
• 8: J. M. Jaffe and F. H. Moss, "A responsive distributed routing algo-rithm for computer networks," IEEE Trans. Commun., vol. 30, no. 7, pp. 1758-1762, Jul. 1982.
• 9: LAN/MAN Standards Committee of the IEEE Computer Society. IEEE Standard for Local and Metropolitan Area Networks: Media Access Control (MAC) Bridges, 802.1D, 2004.
• 10: P. M. Merlin and A. Segall, "A failsafe distributed routing protocol," IEEE/ACM Trans. Networking, vol. 27, no. 9, pp. 1280-1287, Sep. 1979.
• 11: A. Myers, T. S. E. Ng, and H. Zhang, "Rethinking the service model: Scaling Ethernet to a million nodes," in Proc. 3rd Workshop on Hot Topics in Networks (HotNets-III), San Diego, CA, Nov. 2004.
• 12: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 13: R. Perlman, "Rbridges: Transparent routing," in Proc. IEEE IN-FOCOM, 2004, vol. 2, pp. 1211-1218.
• 14: S. Ray, R. A. Guerin, and R. Sofia, "Distributed path computation without transient loops: An intermediate variables approach," in Proc. 20th Int. Teletraffic Congr. Plenary (ITC 20), Ottawa, Canada, Jun. 2007.
• 15: Thomas L. Rodeheffer , Chandramohan A. Thekkath , Darrell C. Anderson, SmartBridge: a scalable bridge architecture, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.205-216, August 28-September 01, 2000, Stockholm, Sweden

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

          Nouns: Ethernet

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology; Store and forward networks
      C.2.2 Network Protocols
          Subjects: Routing protocols

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

General Terms:
Algorithms, Design, Management

Keywords:
ethernet, reliability, spanning tree protocols