Non-convex optimization and rate control for multi-class services in the Internet

ABSTRACT

In this paper, we investigate the problem of distributively allocating transmission data rates to users in the Internet. We allow users to have concave as well as sigmoidal utility functions as appropriate for different applications. In the literature, for simplicity, most works have dealt only with the concave utility function. However, we show that applying rate control algorithms developed for concave utility functions in a more realistic setting (with both concave and sigmoidal types of utility functions) could lead to instability and high network congestion. We show that a pricing-based mechanism that solves the dual formulation can be developed based on the theory of subdifferentials with the property that the prices "self-regulate" the users to access the resources based on the net utility. We discuss convergence issues and show that an algorithm can be developed that is efficient in the sense of achieving the global optimum when there are many users.

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, no. 1, pp. 33-37, Jan. 1997.
• 3: {3} F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, "Rate control in communication networks: Shadow prices, proportional fairness, and stability," J. Oper. Res. Soc., vol. 49, no. 3, pp. 237-252, Mar. 1998.
• 4: 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]
• 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: {6} S. Athuraliya and S. H. Low. Optimization Flow Control, II: Implementation. {Online}. Available: http://netlab.caltech.edu.
• 7: {7} S. Kunniyur and R. Srikant, "End-to-end congestion control schemes: Utility function, random losses, and ECN marks," in Proc. IEEE INFOCOM, vol. 3, 2000, pp. 1323-1332.
• 8: 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
• 9: {9} K. Kar, S. Sarkar, and L. Tassiulas, "A simple rate control algorithm for max total user utility," in Proc. IEEE INFOCOM, vol. 1, Apr. 2001, pp. 133-141.
• 10: {10} J.-W. Lee, R. R. Mazumdar, and N. B. Shroff, "Non-convexity issues for Internet rate control with multi-class services: Stability and optimality," in Proc. IEEE INFOCOM, vol. 1, Mar. 2004, pp. 24-34.
• 11: {11} S. Stidham. Pricing and Congestion Management in a Network with Heterogeneous Users. {Online}. Available: http://www.or.unc.edu/~sandy
• 12: {12} J.-W. Lee, R. R. Mazumdar, and N. B. Shroff, "Downlink power allocation for multi-class CDMA wireless networks," in Proc. IEEE INFOCOM , vol. 3, 2002, pp. 1480-1489.
• 13: Jang-Won Lee , Ravi R. Mazumdar , Ness B. Shroff, Downlink power allocation for multi-class wireless systems, IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.854-867, August 2005 [doi>10.1109/TNET.2005.852888]
• 14: N. Z. Shor , Krzysztof C. Kiwiel , Andrzej Ruszcayǹski, Minimization methods for non-differentiable functions, Springer-Verlag New York, Inc., New York, NY, 1985
• 15: {15} M. Minoux, Mathematical Programming: Theory and Algorithms . New York: Wiley, 1986.
• 16: {16} D. P. Bertsekas, Nonlinear Programming. Belmont, MA: Athena Scientific, 1999.
• 17: {17} K. Kar, S. Sarkar, and L. Tassiulas, "Optimization based rate control for multirate multicast sessions," in Proc. IEEE INFOCOM, vol. 1, 2001, pp. 123-132.
• 18: Dongyu Qiu , Ness B. Shroff, Queueing properties of feedback flow control systems, IEEE/ACM Transactions on Networking (TON), v.13 n.1, p.57-68, February 2005 [doi>10.1109/TNET.2004.842218]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.0 General
          Subjects: Economics

General Terms:
Algorithms, Design, Economics, Measurement, Theory

Keywords:
internet, non-concave utility function, non-convex optimization, rate control