On guaranteed smooth switching for buffered crossbar switches

ABSTRACT

Scalability considerations drive the evolution of switch design from output queueing to input queueing and further to combined input and crosspoint queueing (CICQ). However, CICQ switches with credit-based flow control face new challenges of scalability and predictability. In this paper, we propose a novel approach of rate-based smoothed switching, and design a CICQ switch called the smoothed buffered crossbar or sBUX. First, the concept of smoothness is developed from two complementary perspectives of covering and spacing, which, commonly known as fairness and jitter, are unified in the same model. Second, a smoothed multiplexer sMUX is designed that allocates bandwidth among competing flows sharing a link and guarantees almost ideal smoothness for each flow. Third, the buffered crossbar sBUX is designed that uses the scheduler sMUX at each input and output, and a two-cell buffer at each crosspoint. It is proved that sBUX guarantees 100% throughput for real-time services and almost ideal smoothness for each flow. Fourth, an on-line bandwidth regulator is designed that periodically estimates bandwidth demand and generates admissible allocations, which enables sBUX to support best-effort services. Simulation shows almost 100% throughput and multi-microsecond average delay. In particular, neither credit-based flow control nor speedup is used, and arbitrary fabric-internal latency is allowed between line cards and the switch core, simplifying the switch implementation.

REFERENCES

• 1: François Abel , Cyriel Minkenberg , Ronald P. Luijten , Mitchell Gusat , Ilias Iliadis, 10 A Four-Terabit Packet Switch Supporting Long Round-Trip Times, IEEE Micro, v.23 n.1, p.10-24, January 2003 [doi>10.1109/MM.2003.1179894]
• 2: M. Ajmone-Marsan, P. Giaccone, E. Leonardi, and F. Neri, "Local scheduling policies in networks of packet switches with input queues," in Proc. IEEE INFOCOM, 2003.
• 3: 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]
• 4: H. Balakrishnan, S. Devadas, D. Ehlert, and Arvind, "Rate guarantees and overload protection in input-queued switches," in Proc. IEEE IN-FOCOM , Mar. 2004.
• 5: C.-S. Chang, W.-J. Chen, and H.-Y. Huang, "Birkhoff-von Neumann input buffered crossbar switches," in Proc. IEEE INFOCOM, 2000.
• 6: C.-S. Chang, D.-S. Lee, and Y.-S. Jou, "Load balanced Birkhoffvon Neumann switches," Comput. Commun., vol. 25, pp. 611-634, 2002.
• 7: H. J. Chao, "Saturn: A terabit packet switch using dual round-robin," IEEE Commun. Mag., vol. 38, no. 12, pp. 78-84, 2000.
• 8: F. M. Chiussi and A. Francini, "Scalable electronic packet switches," IEEE J. Sel. Areas Commun., vol. 21, no. 4, pp. 486-500, May 2003.
• 9: N. Chrysos and M. Katevenis, "Scheduling in non-blocking buffered three-stage switching fabrics," in Proc. IEEE INFOCOM, 2006.
• 10: S.-T. Chuang, A. Goel, N. McKeown, and B. Prabhakar, "Matching output queueing with a combined input/output-queued switch," IEEE J. Sel. Areas Commun., vol. 17, no. 6, pp. 1030-1039, 1999.
• 11: S.-T. Chuang, S. Iyer, and N. McKeown, "Practical algorithms for performance guarantees in buffered crossbars," in Proc. IEEE INFOCOM, 2005.
• 12: J. G. Dai and B. Prabhakar, "The throughput of data switches with and without speedup," in Proc. IEEE INFOCOM, 2000, pp. 556-564.
• 13: Q. Duan and J. N. Daigle, "Resource allocation for quality of service provision in buffered crossbar switches," in Proc. 11th ICCCN, Oct. 2002, pp. 509-513.
• 14: P. Giaccone, E. Leonardi, and D. Shah, "On the maximal throughput of networks with finite buffers and its application to buffered crossbar," in Proc. IEEE INFOCOM, 2005.
• 15: T. Inukai, "An efficient SS/TDMA time slot assignment algorithm," IEEE Trans. Commun., vol. 27, no. 10, pp. 1449-1455, Oct. 1979.
• 16: K. G. I. Harteros, "Fast parallel comparison circuits for scheduling," Inst. Comput. Sci., FORTH, Heraklion, Crete, Greece, Tech. Rep. FORTH-ICS/TR-304.
• 17: M. Hosaagrahara and H. Sethu, "Max-min fair scheduling in inputqueued switches," IEEE Trans. Parallel Distrib. Syst., in press. DOI: 10.1109/TPDS.2007.70746.
• 18: Joseph Yu Hui, Switching and Traffic Theory for Integrated Broadband Networks, Kluwer Academic Publishers, Norwell, MA, 1990
• 19: T. Javidi, R. B. Magil, and T. Hrabik, "A high-throughput scheduling algorithm for a buffered crossbar switch fabric," in Proc. IEEE ICC, Jun. 2001, pp. 1586-1591.
• 20: M. Katevenis, G. Passas, D. Simos, I. Papaefstathiou, and N. Chrysos, "Variable packet size buffered crossbar (CICQ) switches," in Proc. IEEE ICC, Jun. 2004.
• 21: I. Keslassy, M. Kodialam, T. V. Lakshman, and D. Siliadis, "On guaranteed smooth scheduling for input-queued switches," in Proc. IEEE INFOCOM, 2003.
• 22: P. Krishna, N. S. Patel, A. Charny, and R. J. Simcoe, "On the speedup required for work-conserving crossbar switches," IEEE J. Sel. Areas Commun., vol. 17, no. 6, pp. 1057-1066, Jun. 1999.
• 23: H. T. Kung and R. Morris, "Credit-based flow control for ATM networks," IEEE Network, pp. 40-48, Mar./Apr. 1995.
• 24: Emilio Leonardi , Marco Mellia , Fabio Neri , Marco Ajmone Marsan, Bounds on delays and queue lengths in input-queued cell switches, Journal of the ACM (JACM), v.50 n.4, p.520-550, July 2003 [doi>10.1145/792538.792544]
• 25: Y. Li, S. Panwar, and H. J. Chao, "On the performance of a dual round-robin switch," in Proc. IEEE INFOCOM, 2001, pp. 1688-1697.
• 26: R. B. Magil, C. E. Rohrs, and R. L. Stevenson, "Outputqueued switch emulation by fabrics with limited memory," IEEE J. Sel. Areas Commun., vol. 21, no. 4, pp. 606-615, May 2003.
• 27: Nicholas William McKeown, Scheduling algorithms for input-queued cell switches, University of California at Berkeley, Berkeley, CA, 1996
• 28: N. W. McKeown, V. Anantharam, and J. Walrand, "Achieving 100% throughput in an input-queued switch," IEEE Trans. Commun., vol. 47, no. 8, pp. 1260-1267, Aug. 1999.
• 29: L. Mhamdi and M. Hamdi, "CBF: A high-performance scheduling algorithm for buffered crossbar switches," in Proc. HPSR, Jun. 2003, pp. 67-72.
• 30: C. Minkenberg, "Work-conservingness of CIOQ packet switches with limited output buffers," IEEE Commun. Lett., vol. 6, no. 10, pp. 452-454, Oct. 2002.
• 31: Cyriel Minkenberg , Ronald P. Luijten , François Abel , Wolfgang Denzel , Mitchell Gusat, Current issues in packet switch design, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.119-124, January 2003 [doi>10.1145/774763.774782]
• 32: C. Minkenberg, "Performance of i-SLIP scheduling with large round-trip latency," in Proc. HPSR, 2003, pp. 49-54.
• 33: M. Nabeshima, "Performance evaluation of a combined input- and crosspoint-queued switch," IEICE Trans. Commun., vol. E83-B, no. 3, pp. 737-741, Mar. 2000.
• 34: Deng Pan , Yuanyuan Yang, Localized asynchronous packet scheduling for buffered crossbar switches, Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, December 03-05, 2006, San Jose, California, USA [doi>10.1145/1185347.1185368]
• 35: Prashanth Pappu , Jonathan Turner , Ken Wong, Work-conserving distributed schedulers for Terabit routers, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 36: T. Rodeheffer and J. B. Saxe, "Smooth scheduling in a cell-based switching network," Digital Systems Research Ctr., Palo Alto, CA, SRC Research Report 150, Feb. 1998.
• 37: R. Rojas-Cessa, E. Oki, Z. Jing, and H. Chao, "CIXB-1: Combined input-one-cell-crosspoint buffered switch," in Proc. IEEE HPSR, 2001, pp. 324-329.
• 38: R. Rojas-Cessa, E. Oki, and H. J. Chao, "On the combined input-crosspoint buffered switch with round-robin arbitration," IEEE Trans. Commun., vol. 53, no. 11, pp. 1945-1951, Nov. 2005.
• 39: D. N. Serpanos and P. I. Antoniadis, "FIRM: A class of distributed scheduling algorithms for high-speed atm switches with multiple input queues," in Proc. IEEE INFOCOM, 2000, pp. 548-555.
• 40: D. C. Stephens and H. Zhang, "Implementing dsitributed packet fair queueing in a scalable switch architecture," in Proc. IEEE INFOCOM, 1998, pp. 282-290.
• 41: John A. Stankovic , Krithi Ramamritham , Marco Spuri, Deadline Scheduling for Real-Time Systems: Edf and Related Algorithms, Kluwer Academic Publishers, Norwell, MA, 1998
• 42: J. Turner, "Strong performance guarantees for asynchronous crossbar schedulers," in Proc. IEEE INFOCOM, 2006.
• 43: K. Yoshigoe and K. J. Christensen, "An evolution to crossbar switches with virtual output queueing and buffered cross points," IEEE Network, pp. 48-56, Sep./Oct. 2003.
• 44: H. Zhang, "Service disciplines for guaranteed performance service in packet-switching networks," Proc. IEEE, vol. 83, no. 10, pp. 1374-1396, Oct. 1995.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM)

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance

Keywords:
buffered crossbar, scheduling, smoothness, switches