June 25, 2007 to June 27, 2007
Hammad Iqbal , University of Pittsburgh
Taieb Znati , University of Pittsburgh
Rami Melhem , University of Pittsburgh
We study link scheduling in networks with small router buffers, with the goal of minimizing the guaranteed packet loss rate bound for each ingress-egress traffic aggregate (connection). Given a link scheduling algorithm (a service discipline and a packet drop policy), the guaranteed loss rate for a connection is the loss rate under worst-case routing and bandwidth allocations for competing traffic. Under simplifying assumptions, we show that a local min-max fairness property with respect to apportioning loss events among the connections sharing each link, and a condition on the correlation of scheduling decisions at different links are two necessary and (together) sufficient conditions for optimality in the minimization problem. Based on these conditions, we introduce a randomized link-scheduling algorithm called Rolling Priority where packet scheduling at each link relies exclusively on local information. We show that RP satisfies both conditions and is therefore optimal.
Hammad Iqbal, Taieb Znati, Rami Melhem, "Scheduling to Minimize theWorst-Case Loss Rate", ICDCS, 2007, 27th International Conference on Distributed Computing Systems (ICDCS '07), 27th International Conference on Distributed Computing Systems (ICDCS '07) 2007, pp. 48, doi:10.1109/ICDCS.2007.135