Logarithmic delay for N × N packet switches under the crossbar constraint

ABSTRACT

We consider the fundamental delay bounds for scheduling packets in an N × N packet switch operating under the crossbar constraint. Algorithms that make scheduling decisions without considering queue backlog are shown to incur an average delay of at leastO(N). We then prove that O(log(N)) delay is achievable with a simple frame based algorithm that uses queue backlog information. This is the best known delay bound for packet switches, and is the first analytical proof that sublinear delay is achievable in a packet switch with random inputs.

REFERENCES

• 1: [1] M. J. Neely and E. Modiano, "Logarithmic delay for n × n packet switches," in Proc. IEEE Workshop High Performance Switching Routing, 2004, pp. 3-9.
• 2: [2] C.-S. Chang, W.-J. Chen, and H.-Y. Huang, "Birkhoff-Von Neumann input buffered crossbar switches," in Proc. IEEE INFOCOM, 2000, pp. 1614-1623.
• 3: [3] C.-S. Chang, D.-S. Lee, and C.-Y. Yue, "Providing guaranteed rate services in the load balanced Birkhoff-Von Neumann switchies," in Proc. IEEE INFOCOM, 2003, pp. 1622-1632.
• 4: Emilio Leonardi , Marco Mellia , Fabio Neri , Marco Ajmone Marsan, On the stability of input-queued switches with speed-up, IEEE/ACM Transactions on Networking (TON), v.9 n.1, p.104-118, Feb., 2001 [doi>10.1109/90.909028]
• 5: [5] C. E. Koksal, "Providing quality of service over electronic and optical switches," Ph.D. dissertation, Lab. Inf. Decision Syst. (LIDS), Massachusetts Inst. Technol., Cambridge, 2002.
• 6: [6] M. Andrews and M. Vojnović, "Scheduling reserved traffic in input-queued switches: New delay bounds via probabilistic techniques," in Proc. IEEE INFOCOM, 2003, pp. 764-774.
• 7: [7] N. McKeown, V. Anantharam, and J. Walrand, "Achieving 100% throughput in an input-queued switch," in Proc. IEEE INFOCOM, 1996, pp. 296-302.
• 8: [8] L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936-1948, Dec. 1992.
• 9: [9] 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 Proc. IEEE INFOCOM, 2001, pp. 1095-1103.
• 10: Marco Ajmone Marsan , Andrea Bianco , Paolo Giaccone , Emilio Leonardi , Fabio Neri, Multicast traffic in input-queued switches: optimal scheduling and maximum throughput, IEEE/ACM Transactions on Networking (TON), v.11 n.3, p.465-477, June 2003 [doi>10.1109/TNET.2003.813048]
• 11: [11] M. Gamvrili and D. N. Serpanos, "Multicast schedulers for ATM switches with multiple input queues," in Proc. ISSPIT, 2004, pp. 377-380.
• 12: [12] S.-T. Chuang, A. Goel, N. McKeown, and B. Prabhakar, "Matching output queueing with a combined input output queued switch," in Proc. IEEE INFOCOM, 1998, pp. 1169-1178.
• 13: [13] S. Sarkar, "Optimum scheduling and memory management in input queued switches with finite buffer space," in Proc. IEEE INFOCOM, 2003, pp. 1373-1383.
• 14: 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]
• 15: [15] M. Andrews and L. Zhang, "Achieving stability in networks of input-queued switches," in Proc. IEEE INFOCOM, 2001, pp. 1673-1679.
• 16: [16] M. J. Neely, J. Sun, and E. Modiano, "Delay and complexity tradeoffs for routing and power allocation in a wireless network," presented at the Allerton Conference on Communication, Control, and Computing, Monticello, IL, 2002.
• 17: [17] S. Iyer and N. McKeown, "Maximum size matchings and input queued switches," presented at the 40th Annu. Allerton Conference on Communication, Control, and Computing, Monticello, IL, 2002.
• 18: [18] I. Gopal, D. Coppersmith, and C. K. Wong, "Minimizing packet waiting time in a multibeam satellite system," IEEE Trans. Commun., vol. COM-30, pp. 305-316, Feb. 1982.
• 19: [19] M. A. Bonuccelli, I. Gopal, and C. K. Wong, "Incremental time-slot assignment in SS/TDMA satellite systems," IEEE Trans. Commun., vol. 39, no. 7, pp. 1147-1156, Jul. 1991.
• 20: [20] M. J. Neely, E. Modiano, and C. E. Rohrs, "Tradeoffs in delay guarantees and computation complexity for n × n packet switches," presented at the Conference on Information Sciences and Systems, Princeton, NJ, 2002.
• 21: [21] D. Shah and M. Kopikare, "Delay bounds for approximate maximum weight matching algorithms for input queued switches," in Proc. IEEE INFOCOM, 2002, pp. 1024-1031.
• 22: [22] G. Birkhoff, "Tres observaciones sobre el algebra lineal," Univ. Nac. Tucumán Rev. Ser. A, vol. 5, pp. 147-151, 1946.
• 23: [23] J. von Neumann, "A certain zero-sum two-person game equivalent to the optimal assignment problem," Contributions Theory Games, vol. 2, pp. 5-12, 1953.
• 24: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 25: [25] P. Humblet, "Determinism minimizes waiting time," MIT LIDS, Camridge, Tech. Rep. P-1207, 1982.
• 26: David Gamarnik, Stability of adaptive and non-adaptive packet routing policies in adversarial queueing networks, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.206-214, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301306]
• 27: [27] M. Hall Jr., Combinatorial Theory. Waltham, MA: Blaisedell, 1969.
• 28: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 29: [29] J. Hopcroft and R. Karp, "An n^5/2 algorithm for maximum matchings in bipartite graphs," SIAM J. Comput., pp. 225-231, Dec. 1973.
• 30: [30] M. J. Neely and E. Modiano, "Logarithmic delay for n × n packet switches," USC CSI, Los Angeles, Tech. Rep. CSI-04-01, 2004.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

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

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

General Terms:
Algorithms, Design, Management

Keywords:
optimal control, scheduling, stochastic queueing analysis