Packet-mode emulation of output-queued switches

ABSTRACT

Most common network protocols (e.g., the Internet Protocol) work with variable size packets, whereas contemporary switches still operate with fixed size cells, which are easier to transmit and buffer. This necessitates packet segmentation and reassembly modules, resulting in significant computation and communication overhead that might be too costly as switches become faster and bigger. It is therefore imperative to investigate an alternative mode of scheduling, in which packets are scheduled contiguously over the switch fabric.This paper investigates the cost of packet-mode scheduling for the combined input output queued (CIOQ) switch architecture.We devise frame-based schedulers that allow a packetmode CIOQ switch with small speedup to mimic an ideal output-queued switch with bounded relative queuing delay. The schedulers are pipelined and are based on matrix decomposition.Our schedulers demonstrate a trade-off between the switch speedup and the relative queuing delay incurred while mimicking an output-queued switch. When the switch is allowed to incur high relative queuing delay, a speedup arbitrarily close to 2 suffices to mimic an ideal output-queued switch. This implies that packet-mode scheduling does not require higher speedup than a cell-based scheduler. The relative queuing delay can be significantly reduced with just a doubling of the speedup. We further show that it is impossible to achieve zero relative queuing delay (that is, a perfect emulation), regardless of the switch speedup.Finally, we show that a speedup arbitrarily close to 1 suffices to mimic an output-queued switch with a bounded buffer size.

REFERENCES

• 1: Eitan Altman , Zhen Liu , Rhonda Righter, SCHEDULING OF AN INPUT-QUEUED SWITCH TO ACHIEVE MAXIMAL THROUGHPUT, Probability in the Engineering and Informational Sciences, v.14 n.3, p.327-334, July 2000 [doi>10.1017/S0269964800143049]
• 2: A. Bianco, P. Giaccone, E. Leonardi, and F. Neri. A framework for differential frame-based matching algorithms in input-queued switches. In IEEE INFOCOM, 2004.
• 3: G. Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucuman Rev. S er. A, 5:147--151, 1946.
• 4: C.S. Chang, D.S. Lee, and Y.S. Jou. Load balanced Birkhoff-von Neumann switches, part I: one-stage buffering. Computer Communications, 25:611--622, 2002.
• 5: A. Charny, P. Krishna, N. S. Patel, and R.J. Simcoe. Algorithms for providing bandwidth and delay guarantees in iput-buffered crossbars with speedup. In Sixth IEEE/IFIP International Workshop on Quality of Service, pages 235--244, 1998.
• 6: S. Chuang, A. Goel, N. McKeown, and B. Prabhakar. Matching output queueing with a combined input output queued switch. In IEEE INFOCOM, pages 1169--1178, 1999.
• 7: S. Chuang, S. Iyer, and N. McKeown. Practical algorithms for performance guarantees in buffered crossbars. In IEEE INFOCOM, 2005.
• 8: Cisco Systems, Inc. Cisco 12000 Series Gigabit Switch Routers. Available online at: http://www.cisco.com/warp/public/cc/pd/rt/12000/prodlit/gsrov.pdf.
• 9: L. Dulmage and I. Halperin. On a theorem of Frobenius-Konig and J. von Neumann's game of hide and seek. Trans. Roy. Soc. Canada III, 49:23--29, 1955.
• 10: Y. Ganjali, A. Keshavarzian, and D. Shah. Input queued switches: cell switching vs. packet switching. In INFOCOM 2003, volume 3, pages 1651--1658, March 2003.
• 11: Paolo Giaccone , Emilio Leonardi , Balaji Prabhakar , Devavrat Shah, Delay bounds for combined input-output switches with low speedup, Performance Evaluation, v.55 n.1-2, p.113-128, January 2004 [doi>10.1016/S0166-5316(03)00103-2]
• 12: Dan Guez , Alex Kesselman , Adi Rosén, Packet-mode policies for input-queued switches, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007927]
• 13: A. Hung, ATM Input-Buffered Switches with the Guaranteed-Rate Property, Proceedings of the Third IEEE Symposium on Computers & Communications, p.331, June 30-July 02, 1998
• 14: S. Iyer and N. McKeown. Making parallel packet switches practical. In IEEE INFOCOM, pages 1680--1687, 2001.
• 15: K. Kar, T. Lakshman, D. Stiliadis, and L. Tassiulas. Reduced complexity input buffered switches. In HOT Interconnects, pages 13--20, 2000.
• 16: I. Keslassy, M. Kodialam, T.V. Lakshman, and D. Stiliadis. On guaranteed smooth scheduling for input-queued switches. In IEEE INFOCOM, 2003.
• 17: L. Kleinrock. Queueing Systems, Volume II. John Wiley&Sons, 1975.
• 18: P. Krishna, N. S. Patel, A. Charny, and R.J. Simcoe. On the speedup required for work-conserving crossbar switches. IEEE Journal on Selected Areas in Communications, 17(6):1057--1066, June 1999.
• 19: X. Li and M. Hamdi. On scheduling optical packet switches with reconfiguration delay. IEEE Journal on Selected Areas in Communications, 21(7):1156--1164, 2003.
• 20: Y. Li, S. Panwar, and H.J. Chao. Exhaustive service matching algorithms for input queued switches. In IEEE Workshop on High Performance Switching and Routing, pages 253--258, 2004.
• 21: Marco Ajmone Marsan , Andrea Bianco , Paolo Giaccone , Emilio Leonardi , Fabio Neri, Packet-mode scheduling in input-queued cell-based switches, IEEE/ACM Transactions on Networking (TON), v.10 n.5, p.666-678, October 2002 [doi>10.1109/TNET.2002.803939]
• 22: N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand. Achieving 100% throughput in an input-queued switch. IEEE Transactions on Communications, 47(8):1260--1267, August 1999.
• 23: The National Laboratory for Applied Network Research. WAN packet size distribution. Available online at: http://www.nlanr.net/NA/Learn/packetsizes.html.
• 24: 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
• 25: B. Prabhakar and N. McKowen. On the speedup required for combined input and output queued switching. Automatica, 35(12):1909--1920, December 1999.
• 26: R. Sinha, C. Papadopoulos, and J. Heidemann. Internet Packet Size Distributions: Some Observations, 2005. Available online at: http://netweb.usc.edu/~rsinha/pkt-sizes/
• 27: D.C. Stephens and H. Zhang. Implementing distributed packet fair queueing in a scalable architecture. In IEEE INFOCOM, pages 282--290, 1998.
• 28: I. Stoica and H. Zhang. Exact emulation of an output queueing switch by a combined input output queueing switch. In Sixth IEEE/IFIP International Workshop on Quality of Service, pages 218--224, 1998.
• 29: Brian Towles , William J. Dally, Guaranteed scheduling for switches with configuration overhead, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.835-847, October 2003 [doi>10.1109/TNET.2003.818190]
• 30: J. Turner. Strong performance guarantees for asynchronous crossbar schedulers. In IEEE INFOCOM, 2006. To appear.
• 31: Unisphere Solutions, Inc. ERX-700/1400, Edge Routing Switch. Available online at: http://www.juniper.net/techpubs/software/erx/erx130/ product overview.pdf.
• 32: J. von Neumann. A certain zero-sum two-person game equivalent to the optimal assignment problem. Contributions to the Theory of Games, 2:5--12, 1953.
• 33: Timothy Weller , Bruce Hajek, Scheduling nonuniform traffic in a packet-switching system with small propagation delay, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.813-823, Dec. 1997 [doi>10.1109/90.650141]

INDEX TERMS

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

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout; Sequencing and scheduling

General Terms:
Algorithms, Performance, Theory

Keywords:
CIOQ switch, output-queued, packet switching, packet-mode scheduling, queuing delay, switch emulation