article

Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control

Authors:

Atilla Eryilmaz,

R. SrikantAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 15, Issue 6

Pages 1333 - 1344

https://doi.org/10.1109/TNET.2007.897944

Published: 01 December 2007 Publication History

Abstract

We consider the problem of allocating resources (time slots, frequency, power, etc.) at a base station to many competing flows, where each flow is intended for a different receiver. The channel conditions may be time-varying and different for different receivers. It is well-known that appropriately chosen queue-length based policies are throughput-optimal while other policies based on the estimation of channel statistics can be used to allocate resources fairly (such as proportional fairness) among competing users. In this paper, we show that a combination of queue-length-based scheduling at the base station and congestion control implemented either at the base station or at the end users can lead to fair resource allocation and queue-length stability.

References

[1]

{1} R. Agrawal, A. Bedekar, R. J. La, and V. Subramanian, "Class and channel condition based weighted proportionally fair scheduler," in Proc. Int. Teletraffic Congr., 2001, pp. 553-65.

[2]

{2} T. Alpcan and T. Basar, "A utility-based congestion control scheme for internet-style networks with delay," presented at the IEEE INFOCOM, San Francisco, CA, 2003.

[3]

{3} M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, R. Vijayakumar, and P. Whiting, "Providing quality of service over a shared wireless link," IEEE Commun. Mag., Feb. 2001.

[4]

{4} M. Armony and N. Bambos, Queueing Dynamics and Maximal Throughput Scheduling in Switched Processing Systems Stanford Univ., Technical Report Netlab-2001-09/01.

[5]

{5} S. Asmussen, Applied Probability and Queues. New York: Springer-Verlag, 2003.

[6]

{6} D. Bertsekas, Nonlinear Programming. Belmont, MA: Athena Scientific, 1995.

[7]

{7} D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice Hall, 1987.

[8]

{8} S. C. Borst, "User-level performance of channel-aware scheduling algorithms in wireless data networks," in Proc. IEEE INFOCOM, 2003.

[9]

{9} S. C. Borst and P. A. Whiting, "Dynamic rate control algorithms for HDR throughput optimization," in Proc. IEEE INFOCOM, 2001, pp. 976-985.

[10]

{10} R. Buche and H. J. Kushner, "Control of mobile communication systems with time-varying channels via stability methods," IEEE Trans. Autom. Contr., vol. 49, no. 11, pp. 1954-1962, Nov. 2004.

[11]

{11} A. Eryilmaz, "Efficient and Fair Scheduling for Wireless Networks," Ph.D. dissertation, Univ. of Illinois, Urbana-Champaign, Aug. 2005.

[12]

{12} A. Eryilmaz, R. Srikant, and J. Perkins, "Stable scheduling policies for fading wireless channels," in Proc. IEEE Int. Symp. Information Theory, 2003.

[13]

{13} A. Eryilmaz, R. Srikant, and J. R. Perkins, "Stable scheduling policies for fading wireless channels," IEEE/ACM Trans. Networking, vol. 13, pp. 411-425, Apr. 2005.

[14]

{14} R. J. Gibbens and F. P. Kelly, "Resource pricing and the evolution of congestion control," Automatica, vol. 35, pp. 1969-1985, 1999.

[15]

{15} A. Jalali, R. Padovani, and R. Pankaj, "Data throughput of CDMA-HDR: A high efficiency-high data rate personal communication system," in Proc. IEEE Vehicular Technology Conf., May 2000, pp. 1854-1858.

[16]

{16} F. P. Kelly, "Charging and rate control for elastic traffic," Eur. Trans. Telecommun., vol. 8, pp. 33-37, 1997.

[17]

{17} F. P. Kelly, A. Maulloo, and D. Tan, "Rate control in communication networks: Shadow prices, proportional fairness and stability," J. Oper. Res. Soc., vol. 49, pp. 237-252, 1998.

[18]

{18} H. Khalil, Nonlinear Systems, 2nd ed. Upper Saddle River, NJ: Prentice Hall, 1996.

[19]

{19} S. Kunniyur and R. Srikant, "Analysis and design of an adaptive virtual queue algorithm for active queue management," in Proc. ACM SIGCOMM , San Diego, CA, Aug. 2001, pp. 123-134.

[20]

{20} S. Kunniyur and R. Srikant, "A time-scale decomposition approach to adaptive ECN marking," IEEE Trans. Autom. Contr., vol. 47, no. 6, pp. 882-894, June 2002.

[21]

{21} H. J. Kushner and P. A. Whiting, "Convergence of proportional-fair sharing algorithms under general conditions," IEEE Trans. Wireless Commun., vol. 3, pp. 1250-1259, Jul. 2004.

[22]

{22} A. Lakshmikantha, C. Beck, and R. Srikant, "Robustness of real and virtual queue based active queue management schemes," IEEE/ACM Trans. Networking, vol. 13, no. 1, pp. 81-93, Feb. 2005.

[23]

{23} R. Leelahakriengkrai and R. Agrawal, "Scheduling in multimedia wireless networks," in Proc. ITC, 2001.

[24]

{24} X. Lin and N. Shroff, "The multi-path utility maximization problem," presented at the Allerton Conf. Communications, Control and Computing, Monticello, IL, Oct. 2003.

[25]

{25} X. Liu, E. Chong, and N. Shroff, "Opportunistic transmission scheduling with resource-sharing constraints in wireless networks," IEEE J. Sel. Areas Commun., vol. 19, no. 10, pp. 2053-2064, Oct. 2001.

[26]

{26} Y. Liu and E. Knightly, "Opportunistic fair scheduling over multiple wireless channels," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003.

[27]

{27} S. H. Low and D. E. Lapsley, "Optimization flow control, I: Basic algorithm and convergence," IEEE/ACM Trans. Networking, pp. 861-875, Dec. 1999.

[28]

{28} M. J. Neely, E. Modiano, and C. E. Rohrs, "Dynamic power allocation and routing for time varying wireless networks," presented at the IEEE INFOCOM, 2003.

[29]

{29} J. R. Norris, Markov Chains. Cambridge, U.K.: Cambridge Univ. Press, 1997.

[30]

{30} F. Paganini, "A global stability result in network flow control," Syst. Contr. Lett., vol. 46, no. 3, pp. 153-163, 2002.

[31]

{31} A. G. Pakes, "Some conditions on the ergodicity and recurrence of Markov chains," Oper. Res., p. 17, 1969.

[32]

{32} S. Shakkottai, R. Srikant, and A. Stolyar, "Pathwise optimality of the exponential scheduling rule for wireless channels," Adv. Appl. Probabil. , vol. 36, pp. 1021-1045, 2004.

[33]

{33} S. Shakkottai and A. Stolyar, "Scheduling for multiple flows sharing a time-varying channel: The exponential rule," in Translations of the AMS, ser. 2. :, 2002, vol. 207, a volume in memory of F. Karpelevich.

[34]

{34} R. Srikant, The Mathematics of Internet Congestion Control. London: Birkhauser, 2004.

[35]

{35} A. Stolyar, "Maximizing queueing network utility subject to stability: Greedy primal-dual algorithm," Queueing Syst., vol. 50, no. 4, pp. 401-457, 2005.

[36]

{36} V. Subramanian and R. Agrawal, "A stochastic approximation analysis of channel condition aware wireless scheduling algorithms," in Proc. INFORMS Telecommunications Conf., 2002.

[37]

{37} L. Tassiulas, "Scheduling and performance limits of networks with constantly varying topology," IEEE Trans. Inf. Theory, pp. 1067-1073, May 1997.

[38]

{38} L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Trans. Autom. Contr., pp. 1936-1948, Dec. 1992.

[39]

{39} D. N. Tse, "Multi-user diversity and proportional fairness," U.S. patent 6,449,490.

[40]

{40} P. Viswanath, D. Tse, and R. Laroia, "Opportunistic beamforming using dumb antennas," IEEE Trans. Inf. Theory, vol. 48, no. 6, pp. 1277-1294, Jun. 2002.

[41]

{41} W.-H. Wang, M. Palaniswami, and S. H. Low, "Optimal flow control and routing in multi-path networks," Perform. Eval., pp. 119-132, 2003.

[42]

{42} J. T.Wen and M. Arcak, "A unifying passivity framework for network flow control," in Proc. IEEE INFOCOM, 2003.

[43]

{43} H. Yaiche, R. R. Mazumdar, and C. Rosenberg, "A game-theoretic framework for bandwidth allocation and pricing in broadband networks," IEEE/ACM Trans. Networking, vol. 8, no. 5, pp. 667-678, Oct. 2000.

[44]

{44} A. Eryilmaz, R. Srikant, and J. Perkins, "Stable scheduling policies for fading wireless channels," IEEE/ACM Trans. Networking, vol. 13, no. 2, pp. 411-424, Apr. 2005.

Cited By

Kanoria YQian P(2024)Blind Dynamic Resource Allocation in Closed Networks via Mirror BackpressureManagement Science10.1287/mnsc.2023.493470:8(5445-5462)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1287/mnsc.2023.4934
Panayiotou TEllinas G(2024)Balancing Efficiency and Fairness in Resource Allocation for Optical NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2023.330442621:1(389-401)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TNSM.2023.3304426
Ji JRen XCai LZhu K(2024)Downlink Scheduler for Delay Guaranteed Services Using Deep Reinforcement LearningIEEE Transactions on Mobile Computing10.1109/TMC.2023.327669723:4(3376-3390)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TMC.2023.3276697
Show More Cited By

Index Terms

Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control
1. Networks
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Proportional fair throughput allocation in multirate IEEE 802.11e wireless LANs

Under heterogeneous radio conditions, Wireless LAN stations may use different modulation schemes, leading to a heterogeneity of bit rates. In such a situation, 802.11 DCF allocates the same throughput to all stations independently of their transmitting ...
Fair End-to-End Session Rates in Multihop Wireless Networks

This paper considers a proportional fairness of end-to-end session rates in a multihop wireless network through the rate control framework. In multihop wireless networks, there are two classes of rate control problem. One focuses in optimizing the ...
Joint congestion control, routing, and MAC for stability and fairness in wireless networks

In this paper, we describe and analyze a joint scheduling, routing and congestion control mechanism for wireless networks, that asymptotically guarantees stability of the buffers and fair allocation of the network resources. The queue-lengths serve as ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 15, Issue 6

December 2007

400 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2007

Published in TON Volume 15, Issue 6

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

61
Total Citations
View Citations
830
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kanoria YQian P(2024)Blind Dynamic Resource Allocation in Closed Networks via Mirror BackpressureManagement Science10.1287/mnsc.2023.493470:8(5445-5462)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1287/mnsc.2023.4934
Panayiotou TEllinas G(2024)Balancing Efficiency and Fairness in Resource Allocation for Optical NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2023.330442621:1(389-401)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TNSM.2023.3304426
Ji JRen XCai LZhu K(2024)Downlink Scheduler for Delay Guaranteed Services Using Deep Reinforcement LearningIEEE Transactions on Mobile Computing10.1109/TMC.2023.327669723:4(3376-3390)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1109/TMC.2023.3276697
Nguyen VVu TNguyen NNguyen DJuntti MLuong NHoang DNguyen DChatzinotas S(2024)Network-Aided Intelligent Traffic Steering in 6G O-RAN: A Multi-Layer Optimization FrameworkIEEE Journal on Selected Areas in Communications10.1109/JSAC.2023.333618342:2(389-405)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/JSAC.2023.3336183
Neely M(2020)A Converse Result on Convergence Time for Opportunistic Wireless SchedulingIEEE INFOCOM 2020 - IEEE Conference on Computer Communications10.1109/INFOCOM41043.2020.9155488(40-48)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1109/INFOCOM41043.2020.9155488
Lima VEisen MRibeiro A(2020)Learning Constrained Resource Allocation Policies in Wireless Control Systems2020 59th IEEE Conference on Decision and Control (CDC)10.1109/CDC42340.2020.9303805(2615-2621)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.1109/CDC42340.2020.9303805
Kharat PKulkarni M(2019)Congestion controlling schemes for high-speed data networksJournal of High Speed Networks10.3233/JHS-19060225:1(41-60)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.3233/JHS-190602
Yang CPedarsani RAvestimehr A(2019)Timely-Throughput Optimal Coded Computing over Cloud NetworksProceedings of the Twentieth ACM International Symposium on Mobile Ad Hoc Networking and Computing10.1145/3323679.3326528(301-310)Online publication date: 2-Jul-2019
https://dl.acm.org/doi/10.1145/3323679.3326528
Eisen MZhang CChamon LLee DRibeiro A(2019)Learning Optimal Resource Allocations in Wireless SystemsIEEE Transactions on Signal Processing10.1109/TSP.2019.290890667:10(2775-2790)Online publication date: 23-Apr-2019
https://dl.acm.org/doi/10.1109/TSP.2019.2908906
Yang CPedarsani RAvestimehr A(2019)Communication-Aware Scheduling of Serial Tasks for Dispersed ComputingIEEE/ACM Transactions on Networking10.1109/TNET.2019.291955327:4(1330-1343)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2919553
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents