Node weighted scheduling

ABSTRACT

This paper proposes a new class of online policies for scheduling in input-buffered crossbar switches. Given an initial configuration of packets at the input buffers, these policies drain all packets in the system in the minimal amount of time provided that there are no further arrivals. These policies are also throughput optimal for a large class of arrival processes which satisfy strong-law of large numbers. We show that it is possible for policies in our class to be throughput optimal even if they are not constrained to be maximal in every time slot.

Most algorithms for switch scheduling take an edge based approach; in contrast, we focus on scheduling (a large enough set of) the most congested ports. This alternate approach allows for lower-complexity algorithms, and also requires a non-standard technique to prove throughput-optimality. One algorithm in our class, Maximum Vertex-weighted Matching (MVM) has worst-case complexity similar to Max-size Matching, and in simulations shows slightly better delay performance than Max-(edge)weighted-Matching (MWM).

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: Andrew Brzezinski , Gil Zussman , Eytan Modiano, Enabling distributed throughput maximization in wireless mesh networks: a partitioning approach, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161094]
• 3: Chang, C.-S., Chen, W.-J., and Huang, H.-Y. On service guarantees for input buffered crossbar switches: A capacity decomposition approach by Birkhoff and Von Neumann. In IEEE Infocom (2000).
• 4: Dai, J., and Prabhakar, B. The throughput of data switches with and without speedup. In IEEE Infocom (March 2000).
• 5: Dai, J. G. On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. Annals of Applied Probability 5 (1995), 49--77.
• 6: Dimakis, A., and Walrand, J. Sufficient conditions for stability of longest-queue-first scheduling: Second-order properties using fluid limits. Advances in Applied Probability 38, 2 (2006), 505--521.
• 7: Anja Feldmann , Nils Kammenhuber , Olaf Maennel , Bruce Maggs , Roberto De Prisco , Ravi Sundaram, A methodology for estimating interdomain web traffic demand, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028833]
• 8: Leonidas Georgiadis , Michael J. Neely , Leandros Tassiulas, Resource allocation and cross-layer control in wireless networks, Foundations and Trends® in Networking, v.1 n.1, p.1-144, April 2006 [doi>10.1561/1300000001]
• 9: Hoffman, A., and Kuhn, H. Systems of distinct representatives and linear programming. The American Mathematical Monthly 63 (1956).
• 10: Iyer, S., and McKeown, N. Maximum size matching and input queued switches. In Proceedings of the 40th Annual Allerton Conference on Communication, Control and Computing (2002).
• 11: Joo, C., Lin, X., and Shroff, N. B. Performance limits of greedy maximal matching in multi-hop wireless networks. In IEEE CDC (2007).
• 12: Joo, C., Lin, X., and Shroff, N. B. Understanding the capacity region of greedy maximal scheduling algorithm in multi-hop wireless networks. In IEEE INFOCOM (2008).
• 13: Karp, R., and Hopcroft, J. An $n^5/2$ algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing 2 (1973).
• 14: Keslassy, I., and McKeown, N. Analysis of scheduling algorithms that provide 100% throughput in input-queued switches. In Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing (October 2001).
• 15: Keslassy, I., Zhang-Shen, R., and McKeown, N. Maximum size matching is unstable for any packet switch. IEEE Communications Letters 7 (October 2003).
• 16: 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]
• 17: M. Hall, J. Distinct representatives of subsets. Bulletin of the American Mathematical Society 54 (1948).
• 18: McKeown, N., Anantharam, V., and Walrand, J. Achieving 100% throughput in an input-queued switch. In IEEE Infocom (March 1996).
• 19: Mekkittikul, A., and McKeown, N. Practical scheduling algorithm to achieve 100% throughput in input-queued switches. In IEEE Infocom (April 1998).
• 20: 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]
• 21: Neely, M. J., Modiano, E., and Rohrs, C. E. Tradeoffs in delay guarantees and computation complexity for nxn packet switches. In Proc. of Conf. on Information Sciences and Systems (CISS) (2002).
• 22: 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]
• 23: Neely, M. J., Sun, J., and Modiano, E. Delay and complexity tradeoffs for routing and power allocation in a wireless network. In Proc. of Allerton Conf. on Communication, Control, and Computing (2002).
• 24: Perfect, H., and Pym, J. An extension of Banach's mapping theorem, with applications to problems concerning common representatives. Proceedings of the Cambridge Philosophical Society (Mathematical and Physical Sciences) 62 (1966).
• 25: Shah, D. Maximal matching scheduling is good enough. In IEEE Globecom (2003).
• 26: Devavrat Shah , Paolo Giaccone , Balaji Prabhakar, Efficient Randomized Algorithms for Input-Queued Switch Scheduling, IEEE Micro, v.22 n.1, p.10-18, January 2002 [doi>10.1109/40.988685]
• 27: Shah, D., and Wischik, D. Optimal scheduling algorithms for input-queued switches. In INFOCOM (2006).
• 28: Stolyar, A. L. Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Annals of Applied Probability Vol.14, No.1 (2004), pp.1--53.
• 29: Tassiulas, L. Scheduling and performance limits of networks with constantly changing topology. IEEE Trans. Inform. Theory 43 (1997), 1067--1073.
• 30: Tassiulas, L., and Ephremides, A. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Aut. Contr.37 37, 12 (1992), 1936--1948.
• 31: 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.6 Internetworking
          Subjects: Routers

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Performance attributes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Performance, Theory

Keywords:
bipartite matching, fluid limits, scheduling, switch