Scheduling to minimize the worst-case loss rate

Mahmoud Elhaddad, Hammad Iqbal, Taieb Znati, Rami Melhem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish
Title of host publication27th International Conference on Distributed Computing Systems, ICDCS'07
DOIs
Publication statusPublished - 2007
Externally publishedYes
Event27th International Conference on Distributed Computing Systems, ICDCS'07 - Toronto, ON, Canada
Duration: Jun 25 2007Jun 27 2007

Publication series

NameProceedings - International Conference on Distributed Computing Systems

Conference

Conference27th International Conference on Distributed Computing Systems, ICDCS'07
Country/TerritoryCanada
CityToronto, ON
Period6/25/076/27/07

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Scheduling to minimize the worst-case loss rate'. Together they form a unique fingerprint.

Cite this