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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (302 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing table of contents

San Diego, California, USA

SESSION: Session 3B table of contents

Pages: 145 - 154

Year of Publication: 2007

ISBN:978-1-59593-631-8

Authors

Matthew Andrews	Bell Laboratories, Murray Hill, NJ
Kyomin Jung	MIT, Cambridge, MA
Alexander Stolyar	Bell Laboratories, Murray Hill, NJ

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 93, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1250790.1250813 What is a DOI?

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/ε²)). 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	William Aiello , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Adaptive packet routing for bursty adversarial traffic, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.359-368, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276788]
	2	M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, R. Vijayakumar, and P. Whiting. CDMA data QoS scheduling on the forward link with variable channel conditions. Bell Labs Technical Memorandum, April 2000.
	3	M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, R. Vijayakumar, and P. Whiting. Providing quality of service over a shared wireless link. IEEE Communications Magazine, February 2001.
	4	Matthew Andrews , Lisa Zhang, Scheduling Over a Time-Varying User-Dependent Channel with Applications to High Speed Wireless Data, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.293-302, November 16-19, 2002
	5	Elliot Anshelevich , David Kempe , Jon Kleinberg, Stability of load balancing algorithms in dynamic adversarial systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509968]
	6	P. Berenbrink , A. Brinkmann , C. Scheideler, Simple Routing Strategies for Adversarial Systems, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.158, October 14-17, 2001
	7	B. Awerbuch and T. Leighton. A simple local-control approximation algorithm for multicommodity flow. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pages 459--468, 1993.
	8	Baruch Awerbuch , Tom Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.487-496, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195238]
	9	D. Bienstock , G. Iyengar, Solving fractional packing problems in O^ast(1/ε) iterations, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007382]
	10	A. Eryilmaz and R. Srikant. Fair resource allocation in wireless networks using queue-length based scheduling and congestion control. In Proceedings of IEEE INFOCOM '05, Miami, FL, March 2005.
	11	Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
	12	M. Goemans. Lecture notes on linear programming.
	13	Philip Klein , Serge Plotkin , Clifford Stein , Eva Tardos, Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts, SIAM Journal on Computing, v.23 n.3, p.466-487, June 1994 [doi>10.1137/S0097539792241175]
	14	Philip N. Klein , Neal E. Young, On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.320-327, June 09-11, 1999
	15	N.W. McKeown, V. Anantharam, and J. Walrand. Achieving 100% throughput in an input-queued switch. In Proceedings of IEEE INFOCOM '96, pages 296 -- 302, San Francisco, CA, March 1996.
	16	S. Muthukrishnan , Rajmohan Rajaraman, An adversarial model for distributed dynamic load balancing, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.47-54, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277669]
	17	M. Neely, E. Modiano, and C. Li. Fairness and optimal stochastic control for heterogeneous networks. In Proceedings of IEEE INFOCOM '05, Miami, FL, March 2005.
	18	M. Neely, E. Modiano, and C. Rohrs. Power and server allocation in a multi-beam satellite with time varying channels. In Proceedings of IEEE INFOCOM '02, New York, NY, June 2002.
	19	Alexander L. Stolyar, Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm, Queueing Systems: Theory and Applications, v.50 n.4, p.401-457, August 2005 [doi>10.1007/s11134-005-1450-0]
	20	L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37(12):1936 -- 1948, December 1992.
	21	L. Tassiulas and A. Ephremides. Dynamic server allocation to parallel queues with randomly varying connectivity. IEEE Transactions on Information Theory, 30:466 -- 478, 1993.