Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads

Matthew Andrews, Kyomin Jung, Alexander Stolyar

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

Abstract

We study the stability of the max-weight protocol for combined routingand scheduling in communication networks. Previous work has shownthat this protocol is stable for adversarial multicommodity trafficin subcritically loaded static networks and for single-commoditytraffic in critically loaded dynamic networks. We show: The max-weight protocol is stable for adversarial multicommodity traffic in adversarial dynamic networks whenever the network is subcriticallyloaded. The max-weight protocol is stable for fixed multicommodity trafficin fixed networks even if the network is critically loaded. The latter result has implications for the running time of themax-weight protocol when it is used to solve multicommodity flowproblems. In particular, for a fixed problem instance we show thatif the value of the optimum solution is known, the max-weight protocolfinds a flow that is within a (1-)-factor of optimal in time O(1/) (improving the previous bound of O(1/ 2)). If thevalue of the optimum solution is not known, we show how to apply themax-weight algorithm in a binary search procedure that runs in O(1/) time.

Original languageEnglish (US)
Title of host publicationSTOC'07
Subtitle of host publicationProceedings of the 39th Annual ACM Symposium on Theory of Computing
Pages145-154
Number of pages10
DOIs
StatePublished - Oct 30 2007
Externally publishedYes
EventSTOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 11 2007Jun 13 2007

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

OtherSTOC'07: 39th Annual ACM Symposium on Theory of Computing
CountryUnited States
CitySan Diego, CA
Period6/11/076/13/07

    Fingerprint

Keywords

  • Routing
  • Scheduling
  • Stability

ASJC Scopus subject areas

  • Software

Cite this

Andrews, M., Jung, K., & Stolyar, A. (2007). Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads. In STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (pp. 145-154). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1250790.1250813