@inproceedings{d2bdb5a4b79e4aafb9567fc97455472c,

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

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.",

keywords = "Routing, Scheduling, Stability",

author = "Matthew Andrews and Kyomin Jung and Alexander Stolyar",

year = "2007",

month = oct,

day = "30",

doi = "10.1145/1250790.1250813",

language = "English (US)",

isbn = "1595936319",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

pages = "145--154",

booktitle = "STOC'07",

note = "STOC'07: 39th Annual ACM Symposium on Theory of Computing ; Conference date: 11-06-2007 Through 13-06-2007",

}