PROJECTIVE CONE SCHEDULES IN QUEUEING STRUCTURES; Geometry of Packet Scheduling in Communication Network Switches1

摘要

We consider a processing system having several queues, where X_q is the workload in queue q. At any point in time, the system can be set to one of several service configurations, which form a set S. When the system is set to service configuration/vector S ∈ S, queue q receives service at rate S_q. It has been known [2, 3, 4] that - under very general traffic traces - the schedule, which chooses the service vector S maximizing the inner product (S, AX) = ∑_q S_qα_ X_q when the workload vector is X, provides the highest possible throughput under any fixed diagonal matrix A = diag{α_q} with positive entries. That is, it stabilizes the system under the maximum possible traffic load, for very general traffic traces.In this paper, the above result is substantially extended. It is shown that throughput maximization is achieved by any schedule, which chooses a service vector S ∈ S that maximizes the inner product(S, BX) = ∑, ∑, S_pB_(pq)X_q (0.1)p qwhen the workload vector is X, for any fixed matrix B = {B_(pq)} that is positive-definite, has negative or zero off-diagonal elements, and is symmetric. In the context of input-queued packet switches for communication networks, which are special applications of the model studied here, the result substantially extends the popular Maximum Weight Matching (MWM) algorithms for packet/cell scheduling [10, 9]. We examine some practical implications of the extended new algorithms and their scalable implementations.