Abstract

<p><a href="http://www.osa-jon.org/virtual_issue.cfm?vid=7">Feature Issue on Optical Ethernet (OE)</a></p>Ethernet networks rely on the so-called spanning-tree protocol (IEEE 802.1d) to break cycles, thereby avoiding the possibility of infinitely circulating packets and deadlocks. This protocol imposes a severe penalty on the performance and scalability of large gigabit Ethernet backbones since it makes inefficient use of fibers and may lead to bottlenecks. We propose a significantly more scalable cycle-breaking approach based on the theory of turn prohibition. Specifically, we introduce, analyze, and evaluate an algorithm called tree-based turn prohibition (TBTP). We show that this polynomial-time algorithm maintains backward compatibility with the IEEE 802.1d standard and never prohibits more than half the turns in the network for any given graph and any given spanning tree. We further introduce a distributed version of the algorithm that nodes in the network can run asynchronously. Through extensive simulations on a variety of graph topologies, we show that the TBTP algorithm can lead to an order of magnitude improvement over the spanning-tree protocol with respect to throughput and end-of-end delay metrics. In addition, we propose and evaluate heuristics to determine the replacement order of legacy switches that results in the fastest performance improvement.

© 2006 Optical Society of America

PDF Article

References

  • View by:
  • |
  • |
  • |

  1. H. Frazier and H. Johnson, "Gigabit Ethernet: from 100to1,000 Mbps," IEEE Inter. Comput. 3(1), 24-31 (1999).
  2. H. Frazier, "The 802.3z gigabit Ethernet standard," IEEE Netw. 12(3), 6-7 (1998).
  3. D. Clark, "Are ATM, gigabit Ethernet ready for prime time?" IEEE Comput. 31(5), 11-13 (1998).
  4. W. Noureddine and F. Tobagi, "Selective backpressure in switched Ethernet LANs," in Global Telecommunications Conference (IEEE, 1999), pp. 1256-1263.
  5. R. Perlman, Interconnections (Addison-Wesley, 2000).
  6. M. Karol, S. Golestani, and D. Lee, "Prevention of deadlocks and livelocks in lossless backpressured packet networks," in Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE, 2000), pp. 1333-1342.
  7. J. Duato, "A necessary and sufficient condition for deadlock-free routing in cut-through and store-and-forward networks," IEEE Trans. Parallel Distrib. Syst. 7, 841-854 (1996).
  8. M. Soha and R. Perlman, "Comparison of two LAN bridge approaches," IEEE Netw. 2(1), 37-48 (1988).
  9. "Metro Ethernet networks--a technical overview," Metro Ethernet Forum White Paper, 2002-2004. Available online at http://www.metroethernetforum.org/.
  10. L. Bosack and C. Hedrick, "Problems in large LANs," IEEE Netw. 2(1), 52-56 (1988).
  11. G. Ibanez, A. Garcia, and A. Azcorra, "Alternative multiple spanning tree protocols (AMSTP) for optical Ethernet backbones," in 29th Annual IEEE International Conference on Local Computer Networks (IEEE, 2004), pp. 744-751.
  12. S. Sharma, K. Gopalan, S. Nanda, and T. C. Chiueh, "Viking: a multi-spanning-tree Ethernet architecture for metropolitan area and cluster networks," in Twenty-third Annual Joint Conference of the IEEE Computer and Communications Society (IEEE, 2004), pp. 2283-2294.
  13. D. Starobinski, M. Karpovsky, and L. Zakrevski, "Application of network calculus to general topologies using turn-prohibition," IEEE/ACM Trans. Netw. 11, 411-421 (2003).
  14. L. Levitin and M. Karpovsky, "Deadlock prevention in networks modeled as weighted graphs," in Proceedings of Eighth International Conference on Information Networks, Systems and Technologies, ICINSAT 2002 (2002), pp. 482-487.
  15. C. Glass and L. Ni, "The turn model for adaptive routing," J. ACM 41, 874-902 (1994).
  16. M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, and T. L. Rodeheffer, "Autonet: a high-speed, self-configuring local area network using point-to-point links," IEEE J. Sel. Areas Commun. 9, 1318-1335 (1991).
  17. R. Perlman, "An algorithm for distributed computation of a spanning tree in an extended LAN," in Proceedings of Ninth ACM Data Communications Symposium (ACM Press, 1985), pp. 44-53 .
  18. A. Myers, T. Ng, and H. Zhang, "Rethinking the service model: scaling Ethernet to a million nodes," in Proceedings of HotNets III (ACM Press, 2004).
  19. J. Hart, "Extending the IEEE 802.1 MAC bridge standard to remote bridges," IEEE Netw. 2(1), 10-15 (1988).
  20. R. Perlman, W. Hawe, and A. Lauck, "Utilization of redundant links in bridged networks," U.S. patent 5,150,360 (22 September 1992).
  21. K. Lui, W. C. Lee, and K. Nahrstedt, "STAR: a transparent spanning tree bridge protocol with alternate routing," ACM SIGCOMM Comput. Commun. Rev. 32(3), 33-46 (2002).
  22. T. L. Rodeheffer, C. Thekkath, and D. Anderson, "SmartBridge: a scalable bridge architecture," in Proceedings of ACM SIGCOMM 2000 (ACM Press, 2000), pp. 205-216.
  23. F. de Pellegrini, D. Starobinski, M. Karpovsky, and L. Levitin, "Scalable cycle-breaking algorithms for gigabit Ethernet backbones," in 29th Annual IEEE International Conference on Local Computer Networks (IEEE, 2004), pp.2175-2184.
  24. J. Echague, M. Prieto, J. Villadangos, and V. Cholvi, "A distributed algorithm to provide QoS by avoiding cycles in routes," Lect. Notes Comput. Sci. 3266, 224-236 (2004).
  25. T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms (McGraw-Hill, 1990).
  26. M. Fidler and G. Einhoff, "Routing in turn-prohibition based feed-forward networks," Lect. Notes Comput. Sci. 3042, 1168-1179 (2004).
  27. The Network Simulator-ns-2 is available online at http://www.isi.edu/nsnam/ns/.
  28. Boston University Representative Topology Generator-BRITE is available online at http://www.cs.bu.edu/brite/.
  29. A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science 286, 509-512 (1999).

2004 (2)

J. Echague, M. Prieto, J. Villadangos, and V. Cholvi, "A distributed algorithm to provide QoS by avoiding cycles in routes," Lect. Notes Comput. Sci. 3266, 224-236 (2004).

M. Fidler and G. Einhoff, "Routing in turn-prohibition based feed-forward networks," Lect. Notes Comput. Sci. 3042, 1168-1179 (2004).

2003 (1)

D. Starobinski, M. Karpovsky, and L. Zakrevski, "Application of network calculus to general topologies using turn-prohibition," IEEE/ACM Trans. Netw. 11, 411-421 (2003).

2002 (1)

K. Lui, W. C. Lee, and K. Nahrstedt, "STAR: a transparent spanning tree bridge protocol with alternate routing," ACM SIGCOMM Comput. Commun. Rev. 32(3), 33-46 (2002).

1999 (2)

A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science 286, 509-512 (1999).

H. Frazier and H. Johnson, "Gigabit Ethernet: from 100to1,000 Mbps," IEEE Inter. Comput. 3(1), 24-31 (1999).

1998 (2)

H. Frazier, "The 802.3z gigabit Ethernet standard," IEEE Netw. 12(3), 6-7 (1998).

D. Clark, "Are ATM, gigabit Ethernet ready for prime time?" IEEE Comput. 31(5), 11-13 (1998).

1996 (1)

J. Duato, "A necessary and sufficient condition for deadlock-free routing in cut-through and store-and-forward networks," IEEE Trans. Parallel Distrib. Syst. 7, 841-854 (1996).

1994 (1)

C. Glass and L. Ni, "The turn model for adaptive routing," J. ACM 41, 874-902 (1994).

1991 (1)

M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, and T. L. Rodeheffer, "Autonet: a high-speed, self-configuring local area network using point-to-point links," IEEE J. Sel. Areas Commun. 9, 1318-1335 (1991).

1988 (3)

J. Hart, "Extending the IEEE 802.1 MAC bridge standard to remote bridges," IEEE Netw. 2(1), 10-15 (1988).

M. Soha and R. Perlman, "Comparison of two LAN bridge approaches," IEEE Netw. 2(1), 37-48 (1988).

L. Bosack and C. Hedrick, "Problems in large LANs," IEEE Netw. 2(1), 52-56 (1988).

Albert, R.

A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science 286, 509-512 (1999).

Anderson, D.

T. L. Rodeheffer, C. Thekkath, and D. Anderson, "SmartBridge: a scalable bridge architecture," in Proceedings of ACM SIGCOMM 2000 (ACM Press, 2000), pp. 205-216.

Azcorra, A.

G. Ibanez, A. Garcia, and A. Azcorra, "Alternative multiple spanning tree protocols (AMSTP) for optical Ethernet backbones," in 29th Annual IEEE International Conference on Local Computer Networks (IEEE, 2004), pp. 744-751.

Barabási, A.-L.

A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science 286, 509-512 (1999).

Birrell, A. D.

M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, and T. L. Rodeheffer, "Autonet: a high-speed, self-configuring local area network using point-to-point links," IEEE J. Sel. Areas Commun. 9, 1318-1335 (1991).

Bosack, L.

L. Bosack and C. Hedrick, "Problems in large LANs," IEEE Netw. 2(1), 52-56 (1988).

Burrows, M.

M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, and T. L. Rodeheffer, "Autonet: a high-speed, self-configuring local area network using point-to-point links," IEEE J. Sel. Areas Commun. 9, 1318-1335 (1991).

Chiueh, T. C.

S. Sharma, K. Gopalan, S. Nanda, and T. C. Chiueh, "Viking: a multi-spanning-tree Ethernet architecture for metropolitan area and cluster networks," in Twenty-third Annual Joint Conference of the IEEE Computer and Communications Society (IEEE, 2004), pp. 2283-2294.

Cholvi, V.

J. Echague, M. Prieto, J. Villadangos, and V. Cholvi, "A distributed algorithm to provide QoS by avoiding cycles in routes," Lect. Notes Comput. Sci. 3266, 224-236 (2004).

Clark, D.

D. Clark, "Are ATM, gigabit Ethernet ready for prime time?" IEEE Comput. 31(5), 11-13 (1998).

Cormen, T.

T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms (McGraw-Hill, 1990).

de Pellegrini, F.

F. de Pellegrini, D. Starobinski, M. Karpovsky, and L. Levitin, "Scalable cycle-breaking algorithms for gigabit Ethernet backbones," in 29th Annual IEEE International Conference on Local Computer Networks (IEEE, 2004), pp.2175-2184.

Duato, J.

J. Duato, "A necessary and sufficient condition for deadlock-free routing in cut-through and store-and-forward networks," IEEE Trans. Parallel Distrib. Syst. 7, 841-854 (1996).

Echague, J.

J. Echague, M. Prieto, J. Villadangos, and V. Cholvi, "A distributed algorithm to provide QoS by avoiding cycles in routes," Lect. Notes Comput. Sci. 3266, 224-236 (2004).

Einhoff, G.

M. Fidler and G. Einhoff, "Routing in turn-prohibition based feed-forward networks," Lect. Notes Comput. Sci. 3042, 1168-1179 (2004).

Fidler, M.

M. Fidler and G. Einhoff, "Routing in turn-prohibition based feed-forward networks," Lect. Notes Comput. Sci. 3042, 1168-1179 (2004).

Frazier, H.

H. Frazier and H. Johnson, "Gigabit Ethernet: from 100to1,000 Mbps," IEEE Inter. Comput. 3(1), 24-31 (1999).

H. Frazier, "The 802.3z gigabit Ethernet standard," IEEE Netw. 12(3), 6-7 (1998).

Garcia, A.

G. Ibanez, A. Garcia, and A. Azcorra, "Alternative multiple spanning tree protocols (AMSTP) for optical Ethernet backbones," in 29th Annual IEEE International Conference on Local Computer Networks (IEEE, 2004), pp. 744-751.

Glass, C.

C. Glass and L. Ni, "The turn model for adaptive routing," J. ACM 41, 874-902 (1994).

Golestani, S.

M. Karol, S. Golestani, and D. Lee, "Prevention of deadlocks and livelocks in lossless backpressured packet networks," in Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE, 2000), pp. 1333-1342.

Gopalan, K.

S. Sharma, K. Gopalan, S. Nanda, and T. C. Chiueh, "Viking: a multi-spanning-tree Ethernet architecture for metropolitan area and cluster networks," in Twenty-third Annual Joint Conference of the IEEE Computer and Communications Society (IEEE, 2004), pp. 2283-2294.

Hart, J.

J. Hart, "Extending the IEEE 802.1 MAC bridge standard to remote bridges," IEEE Netw. 2(1), 10-15 (1988).

Hawe, W.

R. Perlman, W. Hawe, and A. Lauck, "Utilization of redundant links in bridged networks," U.S. patent 5,150,360 (22 September 1992).

Hedrick, C.

L. Bosack and C. Hedrick, "Problems in large LANs," IEEE Netw. 2(1), 52-56 (1988).

Ibanez, G.

G. Ibanez, A. Garcia, and A. Azcorra, "Alternative multiple spanning tree protocols (AMSTP) for optical Ethernet backbones," in 29th Annual IEEE International Conference on Local Computer Networks (IEEE, 2004), pp. 744-751.

Johnson, H.

H. Frazier and H. Johnson, "Gigabit Ethernet: from 100to1,000 Mbps," IEEE Inter. Comput. 3(1), 24-31 (1999).

Karol, M.

M. Karol, S. Golestani, and D. Lee, "Prevention of deadlocks and livelocks in lossless backpressured packet networks," in Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE, 2000), pp. 1333-1342.

Karpovsky, M.

D. Starobinski, M. Karpovsky, and L. Zakrevski, "Application of network calculus to general topologies using turn-prohibition," IEEE/ACM Trans. Netw. 11, 411-421 (2003).

L. Levitin and M. Karpovsky, "Deadlock prevention in networks modeled as weighted graphs," in Proceedings of Eighth International Conference on Information Networks, Systems and Technologies, ICINSAT 2002 (2002), pp. 482-487.

F. de Pellegrini, D. Starobinski, M. Karpovsky, and L. Levitin, "Scalable cycle-breaking algorithms for gigabit Ethernet backbones," in 29th Annual IEEE International Conference on Local Computer Networks (IEEE, 2004), pp.2175-2184.

Lauck, A.

R. Perlman, W. Hawe, and A. Lauck, "Utilization of redundant links in bridged networks," U.S. patent 5,150,360 (22 September 1992).

Lee, D.

M. Karol, S. Golestani, and D. Lee, "Prevention of deadlocks and livelocks in lossless backpressured packet networks," in Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE, 2000), pp. 1333-1342.

Lee, W. C.

K. Lui, W. C. Lee, and K. Nahrstedt, "STAR: a transparent spanning tree bridge protocol with alternate routing," ACM SIGCOMM Comput. Commun. Rev. 32(3), 33-46 (2002).

Leiserson, C.

T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms (McGraw-Hill, 1990).

Levitin, L.

F. de Pellegrini, D. Starobinski, M. Karpovsky, and L. Levitin, "Scalable cycle-breaking algorithms for gigabit Ethernet backbones," in 29th Annual IEEE International Conference on Local Computer Networks (IEEE, 2004), pp.2175-2184.

L. Levitin and M. Karpovsky, "Deadlock prevention in networks modeled as weighted graphs," in Proceedings of Eighth International Conference on Information Networks, Systems and Technologies, ICINSAT 2002 (2002), pp. 482-487.

Lui, K.

K. Lui, W. C. Lee, and K. Nahrstedt, "STAR: a transparent spanning tree bridge protocol with alternate routing," ACM SIGCOMM Comput. Commun. Rev. 32(3), 33-46 (2002).

Murray, H.

M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, and T. L. Rodeheffer, "Autonet: a high-speed, self-configuring local area network using point-to-point links," IEEE J. Sel. Areas Commun. 9, 1318-1335 (1991).

Myers, A.

A. Myers, T. Ng, and H. Zhang, "Rethinking the service model: scaling Ethernet to a million nodes," in Proceedings of HotNets III (ACM Press, 2004).

Nahrstedt, K.

K. Lui, W. C. Lee, and K. Nahrstedt, "STAR: a transparent spanning tree bridge protocol with alternate routing," ACM SIGCOMM Comput. Commun. Rev. 32(3), 33-46 (2002).

Nanda, S.

S. Sharma, K. Gopalan, S. Nanda, and T. C. Chiueh, "Viking: a multi-spanning-tree Ethernet architecture for metropolitan area and cluster networks," in Twenty-third Annual Joint Conference of the IEEE Computer and Communications Society (IEEE, 2004), pp. 2283-2294.

Needham, R. M.

M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, and T. L. Rodeheffer, "Autonet: a high-speed, self-configuring local area network using point-to-point links," IEEE J. Sel. Areas Commun. 9, 1318-1335 (1991).

Ng, T.

A. Myers, T. Ng, and H. Zhang, "Rethinking the service model: scaling Ethernet to a million nodes," in Proceedings of HotNets III (ACM Press, 2004).

Ni, L.

C. Glass and L. Ni, "The turn model for adaptive routing," J. ACM 41, 874-902 (1994).

Noureddine, W.

W. Noureddine and F. Tobagi, "Selective backpressure in switched Ethernet LANs," in Global Telecommunications Conference (IEEE, 1999), pp. 1256-1263.

Perlman, R.

M. Soha and R. Perlman, "Comparison of two LAN bridge approaches," IEEE Netw. 2(1), 37-48 (1988).

R. Perlman, Interconnections (Addison-Wesley, 2000).

R. Perlman, "An algorithm for distributed computation of a spanning tree in an extended LAN," in Proceedings of Ninth ACM Data Communications Symposium (ACM Press, 1985), pp. 44-53 .

R. Perlman, W. Hawe, and A. Lauck, "Utilization of redundant links in bridged networks," U.S. patent 5,150,360 (22 September 1992).

Prieto, M.

J. Echague, M. Prieto, J. Villadangos, and V. Cholvi, "A distributed algorithm to provide QoS by avoiding cycles in routes," Lect. Notes Comput. Sci. 3266, 224-236 (2004).

Rivest, R.

T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms (McGraw-Hill, 1990).

Rodeheffer, T. L.

M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, and T. L. Rodeheffer, "Autonet: a high-speed, self-configuring local area network using point-to-point links," IEEE J. Sel. Areas Commun. 9, 1318-1335 (1991).

T. L. Rodeheffer, C. Thekkath, and D. Anderson, "SmartBridge: a scalable bridge architecture," in Proceedings of ACM SIGCOMM 2000 (ACM Press, 2000), pp. 205-216.

Schroeder, M. D.

M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, and T. L. Rodeheffer, "Autonet: a high-speed, self-configuring local area network using point-to-point links," IEEE J. Sel. Areas Commun. 9, 1318-1335 (1991).

Sharma, S.

S. Sharma, K. Gopalan, S. Nanda, and T. C. Chiueh, "Viking: a multi-spanning-tree Ethernet architecture for metropolitan area and cluster networks," in Twenty-third Annual Joint Conference of the IEEE Computer and Communications Society (IEEE, 2004), pp. 2283-2294.

Soha, M.

M. Soha and R. Perlman, "Comparison of two LAN bridge approaches," IEEE Netw. 2(1), 37-48 (1988).

Starobinski, D.

D. Starobinski, M. Karpovsky, and L. Zakrevski, "Application of network calculus to general topologies using turn-prohibition," IEEE/ACM Trans. Netw. 11, 411-421 (2003).

F. de Pellegrini, D. Starobinski, M. Karpovsky, and L. Levitin, "Scalable cycle-breaking algorithms for gigabit Ethernet backbones," in 29th Annual IEEE International Conference on Local Computer Networks (IEEE, 2004), pp.2175-2184.

Thekkath, C.

T. L. Rodeheffer, C. Thekkath, and D. Anderson, "SmartBridge: a scalable bridge architecture," in Proceedings of ACM SIGCOMM 2000 (ACM Press, 2000), pp. 205-216.

Tobagi, F.

W. Noureddine and F. Tobagi, "Selective backpressure in switched Ethernet LANs," in Global Telecommunications Conference (IEEE, 1999), pp. 1256-1263.

Villadangos, J.

J. Echague, M. Prieto, J. Villadangos, and V. Cholvi, "A distributed algorithm to provide QoS by avoiding cycles in routes," Lect. Notes Comput. Sci. 3266, 224-236 (2004).

Zakrevski, L.

D. Starobinski, M. Karpovsky, and L. Zakrevski, "Application of network calculus to general topologies using turn-prohibition," IEEE/ACM Trans. Netw. 11, 411-421 (2003).

Zhang, H.

A. Myers, T. Ng, and H. Zhang, "Rethinking the service model: scaling Ethernet to a million nodes," in Proceedings of HotNets III (ACM Press, 2004).

ACM SIGCOMM Comput. Commun. Rev. (1)

K. Lui, W. C. Lee, and K. Nahrstedt, "STAR: a transparent spanning tree bridge protocol with alternate routing," ACM SIGCOMM Comput. Commun. Rev. 32(3), 33-46 (2002).

IEEE Comput. (1)

D. Clark, "Are ATM, gigabit Ethernet ready for prime time?" IEEE Comput. 31(5), 11-13 (1998).

IEEE Netw. (2)

M. Soha and R. Perlman, "Comparison of two LAN bridge approaches," IEEE Netw. 2(1), 37-48 (1988).

J. Hart, "Extending the IEEE 802.1 MAC bridge standard to remote bridges," IEEE Netw. 2(1), 10-15 (1988).

IEEE Inter. Comput. (1)

H. Frazier and H. Johnson, "Gigabit Ethernet: from 100to1,000 Mbps," IEEE Inter. Comput. 3(1), 24-31 (1999).

IEEE J. Sel. Areas Commun. (1)

M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, and T. L. Rodeheffer, "Autonet: a high-speed, self-configuring local area network using point-to-point links," IEEE J. Sel. Areas Commun. 9, 1318-1335 (1991).

IEEE Netw. (2)

L. Bosack and C. Hedrick, "Problems in large LANs," IEEE Netw. 2(1), 52-56 (1988).

H. Frazier, "The 802.3z gigabit Ethernet standard," IEEE Netw. 12(3), 6-7 (1998).

IEEE Trans. Parallel Distrib. Syst. (1)

J. Duato, "A necessary and sufficient condition for deadlock-free routing in cut-through and store-and-forward networks," IEEE Trans. Parallel Distrib. Syst. 7, 841-854 (1996).

IEEE/ACM Trans. Netw. (1)

D. Starobinski, M. Karpovsky, and L. Zakrevski, "Application of network calculus to general topologies using turn-prohibition," IEEE/ACM Trans. Netw. 11, 411-421 (2003).

J. ACM (1)

C. Glass and L. Ni, "The turn model for adaptive routing," J. ACM 41, 874-902 (1994).

Lect. Notes Comput. Sci. (2)

J. Echague, M. Prieto, J. Villadangos, and V. Cholvi, "A distributed algorithm to provide QoS by avoiding cycles in routes," Lect. Notes Comput. Sci. 3266, 224-236 (2004).

M. Fidler and G. Einhoff, "Routing in turn-prohibition based feed-forward networks," Lect. Notes Comput. Sci. 3042, 1168-1179 (2004).

Science (1)

A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science 286, 509-512 (1999).

Other (15)

The Network Simulator-ns-2 is available online at http://www.isi.edu/nsnam/ns/.

Boston University Representative Topology Generator-BRITE is available online at http://www.cs.bu.edu/brite/.

T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms (McGraw-Hill, 1990).

R. Perlman, W. Hawe, and A. Lauck, "Utilization of redundant links in bridged networks," U.S. patent 5,150,360 (22 September 1992).

T. L. Rodeheffer, C. Thekkath, and D. Anderson, "SmartBridge: a scalable bridge architecture," in Proceedings of ACM SIGCOMM 2000 (ACM Press, 2000), pp. 205-216.

F. de Pellegrini, D. Starobinski, M. Karpovsky, and L. Levitin, "Scalable cycle-breaking algorithms for gigabit Ethernet backbones," in 29th Annual IEEE International Conference on Local Computer Networks (IEEE, 2004), pp.2175-2184.

R. Perlman, "An algorithm for distributed computation of a spanning tree in an extended LAN," in Proceedings of Ninth ACM Data Communications Symposium (ACM Press, 1985), pp. 44-53 .

A. Myers, T. Ng, and H. Zhang, "Rethinking the service model: scaling Ethernet to a million nodes," in Proceedings of HotNets III (ACM Press, 2004).

L. Levitin and M. Karpovsky, "Deadlock prevention in networks modeled as weighted graphs," in Proceedings of Eighth International Conference on Information Networks, Systems and Technologies, ICINSAT 2002 (2002), pp. 482-487.

G. Ibanez, A. Garcia, and A. Azcorra, "Alternative multiple spanning tree protocols (AMSTP) for optical Ethernet backbones," in 29th Annual IEEE International Conference on Local Computer Networks (IEEE, 2004), pp. 744-751.

S. Sharma, K. Gopalan, S. Nanda, and T. C. Chiueh, "Viking: a multi-spanning-tree Ethernet architecture for metropolitan area and cluster networks," in Twenty-third Annual Joint Conference of the IEEE Computer and Communications Society (IEEE, 2004), pp. 2283-2294.

"Metro Ethernet networks--a technical overview," Metro Ethernet Forum White Paper, 2002-2004. Available online at http://www.metroethernetforum.org/.

W. Noureddine and F. Tobagi, "Selective backpressure in switched Ethernet LANs," in Global Telecommunications Conference (IEEE, 1999), pp. 1256-1263.

R. Perlman, Interconnections (Addison-Wesley, 2000).

M. Karol, S. Golestani, and D. Lee, "Prevention of deadlocks and livelocks in lossless backpressured packet networks," in Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE, 2000), pp. 1333-1342.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.