Low-latency scheduling in large switches

ABSTRACT

Scheduling in large switches is challenging. Arbiters must operate at high rates to keep up with the high switching rates demanded by multi-gigabit-per-second link rates and short cells. Low-latency requirements of some applications also challenge the design of schedulers. In this paper, we propose the Parallel Wrapped Wave Front Arbiter with Fast Scheduler (PWWFA-FS). We analyze its performance, present simulation results, discuss its implementation, and show how this scheme can provide low latency under light load while scaling to large switches with multi-terabit-per-second throughput and hundreds of ports.

REFERENCES

• 1: Thomas E. Anderson , Susan S. Owicki , James B. Saxe , Charles P. Thacker, High-speed switch scheduling for local-area networks, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.319-352, Nov. 1993 [doi>10.1145/161541.161736]
• 2: H. J. Chao and J.-S.Park, "Centralized Contention Resolution Schemes for a Large-Capacity Optical ATM switch", Proc. IEEE ATM Workshop'97, Fairfax, VA, May 1998.
• 3: R. Drost, R. D. Hopkins, and I. Sutherland, "Proximity Communication", IEEE Custom Integrated Circuits Conference, pp. 469--472, Sep. 2003.
• 4: H. Eberle, A. Chow, B. Coates, J. Cunningham, R. Drost, J. Ebergen, S. Fairbanks, J. Gainsley, N. Gura, R. Ho, D. Hopkins, A. Krishnamoorthy, J. Lexau, W. Olesinski, J. Schauer, and T. Ono, "Multi-terabit Switch Fabrics Enabled by Proximity Communication", Symposium on High Performance Chips (Hot Chips'07), Stanford, CA, August 19--21, 2007.
• 5: I. Elhanany, and X. Li, "A Scalable Frame-based Multi-crosspoint Packet Switching Architecture", High Performance Switching and Routing Conference (HPSR'07), Brooklyn, New York, May 30-June 1, 2007.
• 6: Nick McKeown, The iSLIP scheduling algorithm for input-queued switches, IEEE/ACM Transactions on Networking (TON), v.7 n.2, p.188-201, April 1999 [doi>10.1109/90.769767]
• 7: C. Minkenberg, I. Iliadis and F. Abel, "Low-latency Pipelined Crossbar Arbitration", IEEE Global Telecommunications Conference 2004 (GLOBECOM '04), vol. 2, pp. 1174--1179, Nov. 2004.
• 8: E. Oki, R. Rojas-Cessa, and H. J. Chao, "A Pipeline-Based Maximal-Sized Matching Scheme for High-Speed Input-Buffered Switches", IEICE Transactions on Communications, vol. E85-B, no. 7, pp. 1302--1311, July 2002.
• 9: W. Olesinski, H. Eberle, and N. Gura, "PWWFA: Parallel Wave Front Arbiter for Large Switches", High Performance Switching and Routing Conference (HPSR'07), Brooklyn, NY, May 30-June 1, 2007.
• 10: Y. Tamir , H. C. Chi, Symmetric Crossbar Arbiters for VLSI Communication Switches, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.13-27, January 1993 [doi>10.1109/71.205650]
• 11: Y. Tian, X. Tu, L. Wen, K. Wang, and Y. Liu, "PPAwFE: a Novel High Speed Crossbar Scheduling Algorithm", Proceedings of the 2005 International Conference on Communications, Circuits and Systems, vol.1, pp. 673--677, May 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
arbiter, low latency, scheduling, switching