This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
27th International Conference on Distributed Computing Systems (ICDCS '07)
Scheduling to Minimize theWorst-Case Loss Rate
Toronto, Canada
June 25-June 27
ISBN: 0-7695-2837-3
Mahmoud Elhaddad, University of Pittsburgh
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.
Citation:
Mahmoud Elhaddad, Hammad Iqbal, Taieb Znati, Rami Melhem, "Scheduling to Minimize theWorst-Case Loss Rate," icdcs, pp.48, 27th International Conference on Distributed Computing Systems (ICDCS '07), 2007
Usage of this product signifies your acceptance of the Terms of Use.