skip to main content
article

Application-oriented flow control: fundamentals, algorithms and fairness

Published: 01 December 2006 Publication History

Abstract

This paper is concerned with flow control and resource allocation problems in computer networks in which real-time applications may have hard quality of service (QoS) requirements. Recent optimal flow control approaches are unable to deal with these problems since QoS utility functions generally do not satisfy the strict concavity condition in real-time applications. For elastic traffic, we show that bandwidth allocations using the existing optimal flow control strategy can be quite unfair. If we consider different QoS requirements among network users, it may be undesirable to allocate bandwidth simply according to the traditional max-min fairness or proportional fairness. Instead, a network should have the ability to allocate bandwidth resources to various users, addressing their real utility requirements. For these reasons, this paper proposes a new distributed flow control algorithm for multiservice networks, where the application's utility is only assumed to be continuously increasing over the available bandwidth. In this, we show that the algorithm converges, and that at convergence, the utility achieved by each application is well balanced in a proportionally (or max-min) fair manner.

References

[1]
{1} S. Shenker, "Fundamental design issues for the future Internet," IEEE J. Sel. Areas Commun., vol. 13, no. 7, pp. 1176-1188, Sep. 1995.
[2]
{2} F. P. Kelly, "Charging and rate control for elastic traffic," Eur. Trans. Telecommun., vol. 8, pp. 33-37, Jan. 1997.
[3]
{3} F. P. Kelly, A. Maulloo, and D. Tan, "Rate control for communication networks: shadow prices, proportional fairness and stability," J. Oper. Res. Soc., vol. 49, pp. 237-252, Mar. 1998.
[4]
{4} R. J. Gibbens and F. P. Kelly, "Resource pricing and the evolution of congestion control," Automatica, vol. 35, pp. 1969-1985, Dec. 1999.
[5]
{5} S. H. Low and D. E. Lapsley, "Optimal flow control, I: basic algorithm and convergence," IEEE/ACM Trans. Netw., vol. 7, no. 6, pp. 861-874, Dec. 1999.
[6]
{6} J. Mo and J. Walrand, "Fair end-to-end window-based congestion control," IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 556-567, Oct. 2000.
[7]
{7} H. Yaiche, R. R. Mazumber, and C. Rosenberg, "A game theoretic framework for bandwidth allocation and pricing in broadband networks," IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 667-678, Oct. 2000.
[8]
{8} S. H. Low, F. Paganini, and J. C. Doyle, "Internet congestion control," IEEE Contr. Syst. Mag., vol. 22, no. 1, pp. 28-43, Feb. 2002.
[9]
{9} R. La and V. Anantharam, "Utility-based rate control in the Internet for elastic traffic," IEEE/ACM Trans. Netw., vol. 10, no. 2, pp. 272-286, Apr. 2002.
[10]
{10} E. Altman, T. Basar, and R. Srikant, "Nash equilibria for combined flow control and routing in networks: asymptotic behavior for a large number of users," IEEE Trans. Autom. Contr., vol. 47, no. 6, pp. 917-930, Jun. 2002.
[11]
{11} T. Alpcan and T. Basar, "Distributed algorithms for Nash equilibria of flow control games," in Annals of Dynamic Games, A. Nowak, Ed. Cambridge, MA: Birkhauser, 2003.
[12]
{12} T. Alpcan and T. Basar, "A utility-based congestion control scheme for Internet-style networks with delay," in Proc. IEEE INFOCOM 2003, pp. 2039-2048.
[13]
{13} F. P. Kelly, "Fairness and stability of end-to-end congestion control," Eur. J. Contr., vol. 9, pp. 149-165, 2003.
[14]
{14} K. Kar, S. Sarkar, and L. Tassiulas, "Optimization-based rate control for multipath sessions," Inst. Syst. Res., Univ. Maryland, Baltimore, MD, Tech. Rep. 2001-1, 2001.
[15]
{15} W. H. Wang, M. Palaniswami, and S. H. Low, "Optimal flow control and routing in multiple paths networks," Perform. Eval., vol. 52, no. 2-3, pp. 119-132, 2003.
[16]
{16} K. Kar, S. Sarkar, and L. Tassiulas, "A scalable low-overhead rate control algorithm for multirate multicast sessions," IEEE J. Sel. Areas Commun., vol. 20, no. 8, pp. 1541-1557, Oct. 2002.
[17]
{17} W. H. Wang, M. Palaniswami, and S. H. Low, "Necessary and sufficient conditions of optimal flow control in multirate multicast networks," Proc. Inst. Electr. Eng.--Commun., vol. 150, pp. 385-390, Oct. 2003.
[18]
{18} D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice-Hall, 1992.
[19]
{19} P. Marbach, "Priority service and max-min fairness," IEEE/ACM Trans. Netw., vol. 11, no. 10, pp. 733-746, Oct. 2003.
[20]
{20} V. Jacobson and M. J. Karels, "Congestion avoidance and control," in Proc. ACM SIGCOMM'88, Aug. 1988, pp. 314-329.
[21]
{21} L. S. Brakmo and L. L. Peterson, "TCP Vegas: end to end congestion avoidance on a global Internet," IEEE J. Sel. Areas Commun., vol. 13, no. 8, pp. 1465-1480, Oct. 1995.
[22]
{22} S. Floyd and V. Jacobson, "Random early detection gateways for congestion avoidance," IEEE/ACM Trans. Netw., vol. 1, no. 4, pp. 397-413, Aug. 1993.
[23]
{23} S. Athuraliya, S. H. Low, V. H. Li, and Q. Yin, "REM: active queue management," IEEE Network, vol. 15, no. 3, pp. 48-53, May-Jun. 2001.
[24]
{24} S. H. Low, "A duality model of TCP and queue management algorithms," IEEE/ACM Trans. Netw., vol. 11, no. 4, pp. 525-536, Aug. 2003.
[25]
{25} D. Bertsekas and R. Gallager, Data Networks, 2 ed. Englewood Cliffs, NJ: Prentice-Hall, 1992.
[26]
{26} T. Bially, B. Gold, and S. Seneff, "A technique for adaptive voice flow control in integrated packet networks," IEEE Trans. Commun., vol. 28, no. 3, pp. 325-333, Mar. 1980.
[27]
{27} F. Kishino, K. Manabe, Y. Hayashi, and H. Yasuda, "Variable bit-rate coding of video signals for ATM networks," IEEE J. Sel. Areas Commun., vol. 7, no. 5, pp. 801-806, Jun. 1989.
[28]
{28} Z. Cao and E. W. Zegura, "Utility max-min: an application-oriented bandwidth allocation scheme," in Proc. IEEE INFOCOM'99, pp. 793-801.
[29]
{29} W. H. Wang, "Optimal flow control in packet switched networks," Ph.D. dissertation, Univ. Melbourne, Victoria, Australia, Apr. 2003.
[30]
{30} W. Rudin, Principles of Mathematical Analysis, 3rd ed. New York: McGraw-Hall, 1976.
[31]
{31} D. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation . Englewood Cliffs, NJ: Prentice-Hall, 1989.

Cited By

View all
  • (2022)Astute Video Transmission for Geographically Dispersed Devices in Visual IoT SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2020.300974521:2(448-464)Online publication date: 1-Feb-2022
  • (2021)Risk Optimization for Revenue-Driven Wireless Video Broadcasting Systems: A Copula-Based FrameworkIEEE Transactions on Multimedia10.1109/TMM.2020.300261223(1757-1771)Online publication date: 1-Jan-2021
  • (2020)Profit Maximization for Sponsored Data in Wireless Video Transmission SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2019.291687219:8(1928-1942)Online publication date: 1-Jul-2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 14, Issue 6
December 2006
247 pages

Publisher

IEEE Press

Publication History

Published: 01 December 2006
Published in TON Volume 14, Issue 6

Author Tags

  1. congestion control
  2. quality of service
  3. real-time application
  4. resource allocation
  5. utility max-min fairness
  6. utility proportional fairness

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)2
Reflects downloads up to 09 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Astute Video Transmission for Geographically Dispersed Devices in Visual IoT SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2020.300974521:2(448-464)Online publication date: 1-Feb-2022
  • (2021)Risk Optimization for Revenue-Driven Wireless Video Broadcasting Systems: A Copula-Based FrameworkIEEE Transactions on Multimedia10.1109/TMM.2020.300261223(1757-1771)Online publication date: 1-Jan-2021
  • (2020)Profit Maximization for Sponsored Data in Wireless Video Transmission SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2019.291687219:8(1928-1942)Online publication date: 1-Jul-2020
  • (2019)Utility-Fair Wireless Resource Allocation for Heterogeneous Users2019 IEEE 30th Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)10.1109/PIMRC.2019.8904175(1-5)Online publication date: 8-Sep-2019
  • (2017)Fault-Aware Resource Allocation for Heterogeneous Data Sources with Multipath RoutingScientific Programming10.1155/2017/97495812017Online publication date: 1-Jan-2017
  • (2017)Fault Activity Aware Service Delivery in Wireless Sensor Networks for Smart CitiesWireless Communications & Mobile Computing10.1155/2017/93946132017Online publication date: 1-Jan-2017
  • (2017)Network Utility Maximization-Based Congestion Control Over Wireless Networks: A Survey and Potential DirectivesIEEE Communications Surveys & Tutorials10.1109/COMST.2016.261948519:2(1173-1200)Online publication date: 2-Jun-2017
  • (2017)UFallocMobile Networks and Applications10.1007/s11036-016-0739-z22:2(161-173)Online publication date: 1-Apr-2017
  • (2017)Priority Service Provisioning and Max---Min FairnessJournal of Network and Systems Management10.1007/s10922-016-9395-725:2(397-415)Online publication date: 1-Apr-2017
  • (2016)Cache-Friendly Streaming Bitrate Adaptation by Congestion Feedback in ICNProceedings of the 3rd ACM Conference on Information-Centric Networking10.1145/2984356.2984362(71-76)Online publication date: 26-Sep-2016
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media