TY - GEN
T1 - Scheduling to minimize the worst-case loss rate
AU - Elhaddad, Mahmoud
AU - Iqbal, Hammad
AU - Znati, Taieb
AU - Melhem, Rami
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=34848823133&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34848823133&partnerID=8YFLogxK
U2 - 10.1109/ICDCS.2007.135
DO - 10.1109/ICDCS.2007.135
M3 - Conference contribution
AN - SCOPUS:34848823133
SN - 0769528376
SN - 9780769528373
T3 - Proceedings - International Conference on Distributed Computing Systems
BT - 27th International Conference on Distributed Computing Systems, ICDCS'07
T2 - 27th International Conference on Distributed Computing Systems, ICDCS'07
Y2 - 25 June 2007 through 27 June 2007
ER -