Super-fast delay tradeoffs for utility optimal fair scheduling in wireless networks
- 31 July 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 24 (8), 1489-1501
- https://doi.org/10.1109/jsac.2006.879357
Abstract
We consider the fundamental delay tradeoffs for utility optimal scheduling in a general network with time-varying channels. A network controller acts on randomly arriving data and makes flow control, routing, and resource allocation decisions to maximize a fairness metric based on a concave utility function of network throughput. A simple set of algorithms are constructed that yield total utility within O(1/V) of the utility-optimal operating point, for any control parameter V>0, with a corresponding end-to-end network delay that grows only logarithmically in V. This is the first algorithm to achieve such "super-fast" performance. Furthermore, we show that this is the best utility-delay tradeoff possible. This work demonstrates that the problem of maximizing throughput utility in a data network is fundamentally different than related problems of minimizing average power expenditure, as these latter problems cannot achieve such performance tradeoffsKeywords
This publication has 30 references indexed in Scilit:
- Throughput and Fairness Guarantees Through Maximal Scheduling in Wireless NetworksIEEE Transactions on Information Theory, 2008
- Energy optimal control for time-varying wireless networksIEEE Transactions on Information Theory, 2006
- Optimal Energy and Delay Tradeoffs for Multi-User Wireless DownlinksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Joint Asynchronous Congestion Control and Distributed Scheduling for Multi-Hop Wireless NetworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Fair resource allocation in wireless networks using queue-length-based scheduling and congestion controlPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- The impact of imperfect scheduling on cross-layer rate control in wireless networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual AlgorithmQueueing Systems, 2005
- Resource Allocation and Cross-Layer Control in Wireless NetworksFoundations and Trends® in Networking, 2005
- Rate control for communication networks: shadow prices, proportional fairness and stabilityJournal of the Operational Research Society, 1998
- Charging and rate control for elastic trafficEuropean Transactions on Telecommunications, 1997