Capacity management and equilibrium for proportional QoS

ABSTRACT

Differentiated services architectures are scalable solutions for providing class-based Quality of Service (QoS) over packet switched networks. While qualitative attributes of the offered service classes are often well defined, the actual differentiation between classes is left as an open issue. We address here the proportional QoS model, which aims at maintaining pre-defined ratios between the service class delays (or related congestion measures). In particular, we consider capacity assignment among service classes as the means for attaining this design objective.

Starting with a detailed analysis for the single hop model, we first obtain the required capacity assignment for fixed flow rates. We then analyze the scheme under a reactive scenario, in which self-optimizing users may choose their service class in response to capacity modifications. We demonstrate the existence and uniqueness of the equilibrium in which the required ratios are maintained, and address the efficient computation of the optimal capacities. We further provide dynamic schemes for capacity adjustment, and consider the incorporation of pricing and congestion control to enforce absolute performance bounds on top of the proportional ones. Finally, we extend our basic results to networks with general topology.

REFERENCES

• 1: S. Blake , D. Black , M. Carlson , E. Davies , Z. Wang , W. Weiss, An Architecture for Differentiated Service, RFC Editor, 1998
• 2: X. Xiao and L. M. Ni, "Internet QoS: A big picture," IEEE Network, vol. 36, no. 11, pp. 8-18, Nov. 1999.
• 3: B. Davie , A. Charny , J. C. R. Bennet , K. Benson , J. Y. Le Boudec , W. Courtney , S. Davari , V. Firoiu , D. Stiliadis, An Expedited Forwarding PHB (Per-Hop Behavior), RFC Editor, 2002
• 4: J. Heinanen , F. Baker , W. Weiss , J. Wroclawski, Assured Forwarding PHB Group, RFC Editor, 1999
• 5: Costas Courcoubetis , Richard Weber, Pricing Communication Networks: Economics, Technology and Modelling (Wiley Interscience Series in Systems and Optimization), John Wiley & Sons, 2003
• 6: Internetworking Technologies Handbook 2005, Cisco documentation.
• 7: Constantinos Dovrolis , Dimitrios Stiliadis , Parameswaran Ramanathan, Proportional differentiated services: delay differentiation and packet scheduling, IEEE/ACM Transactions on Networking (TON), v.10 n.1, p.12-26, February 2002 [doi>10.1109/90.986503]
• 8: C. Li, S. Tsao, M. Chen, Y. Sun, and Y. Huang, "Proportional delay differentiation service based on weighted fair queuing," in Proc. 9th Int. Conf. Comput. Commun. Netw., 2000, pp. 418-423.
• 9: A. Demers, S. Keshav, and S. Shenker, "Analysis and simulation of a fair queuing algorithm," J. Internetw.: Res. Exp., vol. 1, no. 6, pp. 3-26, 1990.
• 10: Y. C. C. Qiao, M. Hamdi, and D. Tsang, "Proportional differentiation: A scalable QoS approach," IEEE Commun. Mag., vol. 41, no. 6, pp. 52-58, 2003.
• 11: Andrew Odlyzko, Paris metro pricing for the internet, Proceedings of the 1st ACM conference on Electronic commerce, p.140-147, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337030]
• 12: M. Mandjes, "Pricing strategies under heterogeneous service requirements," in Proc. IEEE INFOCOM, 2003, pp. 1210-1220.
• 13: Y. Hayel, D. Ros, and B. Tuffin, "Less-than-best-effort services: Pricing and scheduling," in Proc. IEEE INFOCOM, 2004, pp. 66-75.
• 14: Haim Mendelson , Seungjin Whang, Optimal incentive-compatible priority pricing for the M/M/1 queue, Operations Research, v.38 n.5, p.870-883, Sep./Oct. 1990 [doi>10.1287/opre.38.5.870]
• 15: E. Altman and L. Wynter, "Equilibrium, games, and pricing in transportation and telecommunications networks," Netw. Spacial Econ., vol. 4, no. 1, pp. 7-21, 2004.
• 16: Ariel Orda , Raphael Rom , Nahum Shimkin, Competitive routing in multiuser communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.510-521, Oct. 1993 [doi>10.1109/90.251910]
• 17: Y. A. Korilis, A. A. Lazar, and A. Orda, "Architecting noncooperative networks," IEEE J. Sel. Areas Commun., vol. 13, no. 7, pp. 1241-1251, Jul. 1995.
• 18: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 19: M. Katevenis, S. Sidiropoulos, and C. Courcoubetis, "Weighted round-robin cell multiplexing in a general-purpose ATM switch chip," IEEE J. Sel. Areas Commun., vol. 9, no. 8, pp. 1265-1279, Oct. 1991.
• 20: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 21: 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.
• 22: M. Patriksson, "Algorithms for computing traffic equilibria," Netw. Spacial Econ., vol. 4, no. 1, pp. 23-38, 2004.
• 23: I. Menache and N. Shimkin, "Capacity management and equilibrium for proportional QoS," Dept. Elect. Eng., Technion, Haifa, Israel, 2006, Tech. Rep. CCIT No. 575.
• 24: C. H. Papadimitriou, "Recent developments in equilibria algorithms," in Proc. WINE, 2005, pp. 1-2.
• 25: D. Fudenberg and J. Tirole, Game Theory. Cambridge, MA: MIT Press, 1991.
• 26: R. Mazumdar, L. Mason, and C. Douligeris, "Fairness in network optimal flow control: Optimality of product forms," IEEE Trans. Commun., vol. 39, no. 5, pp. 775-782, May 1991.
• 27: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 28: R. D. Luce and H. Raiffa, Games and Decisions. New York: Wiley, 1957.
• 29: G. Debreu, "A social equilibrium existence theorem," Proc. Nat. Acad. Sci., vol. 38, no. 10, pp. 886-893, 1952.
• 30: J. B. Rosen, "Existence and uniqueness of equilibrium points for concave n-person games," Econometrica, vol. 33, no. 3, pp. 520-534, 1965.
• 31: T. Basar and G. J. Olsder, Dynamic Noncooperative Game Theory. New York: Academic, 1995.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.4 System Management
          Subjects: Quality assurance

General Terms:
Algorithms, Design, Management, Performance

Keywords:
Nash equillibirum, capacity allocation, differentiated services, proportional QoS, selfish routing