### 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 language | English (US) |
---|---|

Title of host publication | STOC'07 |

Subtitle of host publication | Proceedings of the 39th Annual ACM Symposium on Theory of Computing |

Pages | 145-154 |

Number of pages | 10 |

DOIs | |

State | Published - Oct 30 2007 |

Externally published | Yes |

Event | STOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 11 2007 → Jun 13 2007 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | STOC'07: 39th Annual ACM Symposium on Theory of Computing |
---|---|

Country | United States |

City | San Diego, CA |

Period | 6/11/07 → 6/13/07 |

### Fingerprint

### Keywords

- Routing
- Scheduling
- Stability

### ASJC Scopus subject areas

- Software

### Cite this

*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