Projective cone scheduling (PCS) algorithms for packet switches of maximal throughput

ABSTRACT

We study the (generalized) packet switch scheduling problem, where service configurations are dynamically chosen in response to queue backlogs, so as to maximize the throughput without any knowledge of the long term traffic load. Service configurations and traffic traces are arbitrary.

First, we identify a rich class of throughput-optimal linear controls, which choose the service configuration S maximizing the projection 〈S,BX〉 when the backlog is X. The matrix B is arbitrarily fixed in the class of positive-definite, symmetric matrices with negative or zero off-diagonal elements. In contrast, positive off-diagonal elements may drive the system unstable, even for subcritical loads. The associated rich Euclidian geometry of projective cones is explored (hence the name projective cone scheduling PCS). The maximum-weight-matching (MWM) rule is seen to be a special case, where B is the identity matrix.

Second, we extend the class of throughput maximizing controls by identifying a tracking condition which allows applying PCS with any bounded time-lag without compromising throughput. It enables asynchronous or delayed PCS implementations and various examples are discussed.

REFERENCES

• 1: M. Armony and N. Bambos, "Queueing networks with interacting service resources," in Proc. 1999 Allerton Conf., 1999, pp. 42-51.
• 2: Mor Armony , Nicholas Bambos, Queueing Dynamics and Maximal Throughput Scheduling in Switched Processing Systems, Queueing Systems: Theory and Applications, v.44 n.3, p.209-252, July 2003 [doi>10.1023/A:1024714024248]
• 3: N. Bambos and J. Walrand, "Maximal throughput for stability of a class of parallel processing systems," in Proc. IEEE Conf. Decision and Control , 1990, pp. 161-166.
• 4: N. Bambos and J. Walrand, "Scheduling and stability aspects of a general class of parallel processing systems," Adv. Appl. Probabil., vol. 25, pp. 176-202, 1993.
• 5: J. G. Dai , Wuqin Lin, Maximum Pressure Policies in Stochastic Processing Networks, Operations Research, v.53 n.2, p.197-218, March 2005 [doi>10.1287/opre.1040.0170]
• 6: J. G. Dai and P. Prabhakar, "The throughput of data switches with and without speedup," in Proc. IEEE INFOCOM, 2000, pp. 556-564.
• 7: P. Giaccone, B. Prabhakar, and D. Shah, "Randomized scheduling algorithms for high-aggregate bandwidth switches," IEEE J. Sel. Areas Commun., vol. 21, no. 4, pp. 546-559, May 2003.
• 8: B. Korte and J. Vygen, Combinatorial Optimization--Theory and Algorithms , 2 ed. New York: Springer Verlag, 2001.
• 9: E. Leonardi, M. Mellia, M. Ajmone Marsan, and F. Neri, "Joint optimal scheduling and routing for maximum network throughput," in Proc. IEEE INFOCOM, 2005, vol. 2, pp. 819-830.
• 10: E. Leonardi, M. Mellia, M. Ajmone Marsan, and F. Neri, "On the throughput achievable by isolated and interconnected input-queueing switches under multiclass traffic," in Proc. IEEE INFOCOM, 2002, vol. 3, pp. 1605-1614.
• 11: M. Ajmone Marsan, P. Giaccone, E. Leonardi, and F. Neri, "On the stability of local scheduling policies in networks of packet switches with input queues," IEEE J. Sel. Areas Commun., vol. 21, no. 4, pp. 642-655, May, 2003.
• 12: M. Ajmone Marsan, E. Leonardi, M. Mellia, and F. Neri, "On the stability of isolated and interconnected input-queueing switches under multiclass traffic," IEEE Trans. Inf. Theory, vol. 51, no. 3, pp. 1167-1174, Mar. 2005.
• 13: N. McKeown, A. Mekkittikul, 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.
• 14: M. J. Neely, E. Modiano, and C. E. Rohrs, "Tradeoffs in delay packet switches," in Proc. Conf. Inf. Sci. Syst., 2002, vol. 11, pp. 138-152.
• 15: M. J. Neely, E. Modiano, and C. E. Rohrs, "Dynamic power allocation and routing for time varying wireless networks," IEEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 89-103, Jan. 2005.
• 16: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 17: T. R. A. Ratiu and J. Marsden, Manifolds, Tensor Analysis, and Applications . Reading, MA: Addison-Wesley, 1983.
• 18: K. Ross and N. Bambos, "Projective cone schedules in queueing structures; geometry of packet scheduling in communication network switches," in Proc. Allerton Conf. Communication, Control and Computing, 2002, pp. 626-635.
• 19: K. Ross and N. Bambos, "Projective processing schedules in queueing structures; applications to packet scheduling in communication network switches," Stanford Univ. Eng. Library, Tech. Rep. NETLAB-2002-05/01, 2002.
• 20: K. Ross and N. Bambos, "Local search scheduling algorithms for maximal throughput in packet switches," in Proc. IEEE INFOCOM, 2004, vol. 2, pp. 1158-1169.
• 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: A. Stolyar, "Maxweight scheduling in a generalized switch: State and workload minimization in heavy traffic," Ann. Appl. Probabil., vol. 14, no. 1, pp. 1-53, 2004.
• 23: L. Tassiulas, "Adaptive back-pressure congestion control based on local information," IEEE Trans. Automat. Contr., vol. 40, no. 2, pp. 236-250, Feb. 1995.
• 24: L. Tassiulas, "Linear complexity algorithms for maximum throughput in radio networks and input queued switches," in Proc. IEEE INFOCOM , 1998, pp. 533-539.
• 25: L. Tassiulas and P. P. Bhattacharya, "Allocation of interdependent resources for maximal throughput," Stoch. Models, vol. 16, no. 1, 1999.
• 26: L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Trans. Automat. Contr., vol. 37, no. 12, pp. 1936-1948, Dec. 1992.

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.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

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

General Terms:
Algorithms, Design, Performance

Keywords:
cone scheduling, maximal throughput, packet switch, queueing network, stability