Node weighted scheduling
Gagan Raj Gupta, Sujay Sanghavi, Ness B. Shroff · 2009
This paper proposes a new class of online policies for scheduling in input-buffered crossbar switches. For a system with arrivals, our policies achieve the optimal throughput, with very weak assumptions on the arrival process. For a system without arrivals, our policies drain all packets in the system in the minimal amount of time (providing an online alternative to the batch approach based on Birkhoff-VonNeumann decompositions). Policies in our class are not constrained to be work conserving in every time slot; it may be possible to add edges to the schedule. 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 better delay performance than Max-(edge)weighted-Matching (MWM).