Application-oriented flow control: fundamentals, algorithms and fairness

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: Steven H. Low , David E. Lapsley, Optimization flow control—I: basic algorithm and convergence, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.861-874, Dec. 1999 [doi>10.1109/90.811451]
• 6: Jeonghoon Mo , Jean Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.556-567, Oct. 2000 [doi>10.1109/90.879343]
• 7: Haïkel Yaïche , Ravi R. Mazumdar , Catherine Rosenberg, A game theoretic framework for bandwidth allocation and pricing in broadband networks, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.667-678, Oct. 2000 [doi>10.1109/90.879352]
• 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: Richard J. La , Venkat Anantharam, Utility-based rate control in the Internet for elastic traffic, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 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: Wei-Hua Wang , Marimuthu Palaniswami , Steven H. Low, Optimal flow control and routing in multi-path networks, Performance Evaluation, v.52 n.2-3, p.119-132, April 2003 [doi>10.1016/S0166-5316(02)00176-1]
• 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: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 19: Peter Marbach, Priority service and max-min fairness, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.733-746, October 2003 [doi>10.1109/TNET.2003.818196]
• 20: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 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: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 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: Steven H. Low, A duality model of TCP and queue management algorithms, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.525-536, August 2003 [doi>10.1109/TNET.2003.815297]
• 25: Dimitri Bertsekas , Robert Gallager, Data networks (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 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: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Design, Management

Keywords:
congestion control, quality of service, real-time application, resource allocation, utility max-min fairness, utility proportional fairness