Rate and delay guarantees provided by Clos packet switches with load balancing

Abstract

The size of a single-hop cross-bar fabric is still limited by the technology, and the fabrics available on the market do not exceed the terabit capacity. A multihop fabric such as Clos network provides the higher capacity by using the smaller switching elements (SE). When the traffic load is balanced over the switches in a middle stage, all the traffic would get through the fabric, as long as the switch outputs are not overloaded. However, the delay that packets experience through the Clos switch depends on the granularity of flows that are balanced. We examine the maximum fabric utilization under which a tolerable delay is provided for various load balancing algorithms, and derive the general formula for this utilization in terms of the number of flows that are balanced. We show that the algorithms which balance flows with sufficiently coarse granularity provide both high fabric utilization and delay guarantees to the most sensitive applications. Since no admission control should be performed within the switch, the fast traffic-pattern changes can be accommodated in the proposed scalable architecture.

References

1. {1} T. E. Anderson, S. S. Owicki, J. B. Saxe, and C. P. Thacker, "High-speed switch scheduling for local-area networks," ACM Trans. Comput. Syst., vol. 11, no. 4, pp. 319-352, Nov. 1993.
2. {2} T. Chaney, J. A. Fingerhut, M. Flucke, and J. S. Turner, "Design of a gigabit ATM switch," Proc. IEEE INFOCOM 1997, vol. 1, pp. 2-11.
3. {3} C. S. Chang, D. S. Lee, and C. M. Lien, "Load balanced Birkhoff-von Neumann switches, part II: Multi-stage buffering," Comput. Commun., vol. 25, pp. 623-634, 2002.
4. {4} C. S. Chang, D. S. Lee, and C. Y. Yue, "Providing guaranteed rate service in the load balanced Birkhoff-von Neumann switches," in Proc. IEEE INFOCOM, 2003, pp. 1622-1632.
5. {5} H. J. Chao, "Saturn: A terabit packet switch using dual round-robin," in Proc. IEEE GLOBECOM, 2000, pp. 487-495.
6. {6} C. Clos, "Astudy of non-blocking switching networks," Bell Syst. Tech. J., vol. 32, pp. 406-424, 1953.
7. {7} J. Hui, Switching and Traffic Theory for Integrated Broadband Networks . Boston, MA: Kluwer Academic, 1990.
8. {8} F. K. Hwang, The Mathematical Theory of Nonblocking Switching Networks . Singapore: World Scientific, 1998.
9. {9} S. Iyer and N. McKeown, "Analysis of the parallel packet switch architecture," IEEE/ACM Trans. Networking, vol. 11, no. 2, pp. 314-324, Apr. 2003.
10. {10} I. Keslassy, S. T. Chuang, K. Yu, D. Miller, M. Horowitz, O. Solgaard, and N. McKeown, "Scaling Internet routers using optics," in Proc. ACM SIGCOMM, 2003.
11. {11} T. McDermott and T. Brewer, "Large-scale IP router using a high-speed optical switch element," OSA J. Opt. Netw. pp. 229-241, Jul. 2003 {Online}. Available: www.osa-jon.org
12. {12} W. Kabacinski, C. T. Lea, and G. Xue, "50th anniversary of Clos networks," IEEE Commun. Mag., vol. 41, no. 10, pp. 26-64, Oct. 2003.
13. {13} N. McKeown et al., "The tiny tera: A packet switch core," IEEE Micro, vol. 17, no. 1, pp. 26-33, Jan.-Feb. 1997.
14. {14} E. Oki, Z. Jing, R. Rojas-Cessa, and H. J. Chao, "Concurrent round-robin-based dispatching schemes for Clos-network switches," IEEE/ACM Trans. Networking, vol. 10, no. 6, pp. 830-844, Dec. 2002.
15. {15} A. Smiljanic, "Flexible bandwidth allocation in terabit packet switches," in Proc. IEEE Conf. High Performance Switching and Routing, Jun. 2000, pp. 233-241.
16. {16} A. Smiljanic, "Flexible bandwidth allocation in high-capacity packet switches," IEEE/ACM Trans. Networking, vol. 10, no. 2, pp. 287-293, Apr. 2002.
17. {17} A. Smiljanic, "Scheduling of multicast traffic in high-capacity packet switches," in Proc. IEICE/IEEE Workshop on High-Performance Switching and Routing, May 2002, pp. 29-33.
18. {18} A. Smiljanic, "Scheduling of multicast traffic in high-capacity packet switches," IEEE Commun. Mag., vol. 40, no. 11, pp. 72-77, Nov. 2002.
19. {19} A. Smiljanic, "Bandwidth reservations by maximal matching algorithms," IEEE Commun. Lett., vol. 8, no. 3, pp. 177-179, Mar. 2004.
20. {20} A. Smiljanic, "Performance of load balancing algorithms in Clos packet switches," in Proc. IEEE Workshop on High Performance Switching and Routing, Apr. 2004, pp. 304-308.
21. {21} A. Smiljanic, "Performance of load balancing algorithms in Clos packet switches," in Invited Presentation at Stanford Workshop on Load-Balancing, May 2004.
22. {22} A. Smiljanic, "Load balancing mechanisms in Clos packet switches," in Proc. IEEE Int. Conf. Commun. (ICC), Jun. 2004, pp. 2251-2255.
23. {23} A. Smiljanic, "High performance routers," in Invited Paper at Joint Optoelectronic and Communication Conference and International Conference on Optical Internet, Yokohama, Japan, Jul. 2004.
24. {24} A. Smiljanic, "Terabit switching algorithms," in Invited Paper at SPIE Asian Pacific Optical Communication Conference, Beijing, China, Nov. 2004.
25. {25} A. Smiljanic and M. Petrovic, "Speedup of Clos packet switches that provide delay guarantees," in IEEE Workshop on High Performance Switching and Routing, Hong Kong, China, May 2005.
26. {26} Y. Tamir and H. C. Chi, "Symmetric crossbar arbiters for VLSI communication switches," IEEE Trans. Parallel Distrib. Syst., vol. 4, no. 1, pp. 13-27, Jan. 1993.
27. {27} J. S. Turner, "An optimal nonblocking multicast virtual circuit switch," in Proc. IEEE INFOCOM, 1994, pp. 298-305.

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

    • Availability

    • Maintainability and maintenance

    • Reliability

• General and reference

  • Cross-computing tools and techniques

    • Performance

    • Reliability

• Networks

  • Network components

    • Intermediate nodes

      • Routers

  • Network protocols

    • Transport protocols

  • Network types

    • Public Internet