Input-queued switches with logarithmic delay: necessary conditions and a reconfigurable scheduling algorithm

ABSTRACT

Typically, a scheduling algorithm for an n x n packet switch with a crossbar as the data fabric divides time into slots, each of duration t_p sufficient to transmit a packet. If a scheduling round requires t_r > t_p time, then the switch can transmit multiple packets, up to s = ⌊t_r/t_p⌋, between each mapped input-output pair under the current mapping. If s = 1, there exists a frame-based scheduling algorithm with Θ(log n) delay. For uniform random traffic, we establish that the delay is Ω(n) for any s > 1, hence, s = 1 is the only case where a Θ(log n) delay is achievable.

Given the importance of achieving a low s, it is imperative to develop extremely fast scheduling algorithms (that reduce t_r) on a mesh-based structure (corresponding to the crossbar topology of the switch). We present results for a fast scheduling algorithm that runs on a mesh-of-trees topology that can be overlaid on the crossbar switching fabric.

REFERENCES

• 1: H. Jonathan Chao , Bin Liu, High Performance Switches and Routers, Wiley-IEEE Press, 2007
• 2: C. Fraleigh, S. Moon, B. Lyles, C. Cotton, M. Khan, D. Moll, R. Rockell, T. Seely, and S. C. Diot. Packet-level traffic measurements from the sprint ip backbone. Network, IEEE, 17(6):6--16, December 2003.
• 3: S. Iyer and N. McKeown. Maximum size matchings and input queued switches. In 40th Annual Allerton Conf. on Communication, Control, and Computing, 2002.
• 4: Pierre Kelsen, An optimal parallel algorithm for maximal matching, Information Processing Letters, v.52 n.4, p.223-228, Nov. 25, 1994 [doi>10.1016/0020-0190(94)90130-9]
• 5: E. Leonardi, M. Mellia, F. Neri, and M. A. Marsan. Bounds on average delays and queue size averages and variances in input-queued cell-based switches. In IEEE INFOCOM, 2001.
• 6: X. Li and I. Elhanany. Stability of frame-based maximal weight matching algorithms with reconfiguration delays. In Workshop on High Performance Switching and Routing, May 2005.
• 7: 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]
• 8: Saad Mneimneh , Vishal Sharma , Kai-Yeung Siu, Switching using parallel input-output queued switches with no speedup, IEEE/ACM Transactions on Networking (TON), v.10 n.5, p.653-665, October 2002 [doi>10.1109/TNET.2002.803919]
• 9: Michael J. Neely , Eytan Modiano , Yuan-Sheng Cheng, Logarithmic delay for N × N packet switches under the crossbar constraint, IEEE/ACM Transactions on Networking (TON), v.15 n.3, p.657-668, June 2007 [doi>10.1109/TNET.2007.893876]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

General Terms:
Algorithms, Theory

Keywords:
distributed scheduling algorithm, input-queued switch, mesh-of-trees, parallel bipartite matching, reconfigurable mesh