skip to main content
article

Capacity management and equilibrium for proportional QoS

Published: 01 October 2008 Publication History

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, and W. Weiss, "An architecture for differentiated services," RFC 2475, 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. Bennett, K. Benson, J. Boudec, W. Courtney, S. Davari, V. Firoiu, and D. Stiliadis, "An expedited forwarding PHB (per-hop behavior)," RFC 3246, 2001.
[4]
J. Heinanen, F. Baker, W. Weiss, and J. Wroclawski, "Assured forwarding PHB group," RFC 2597, 1999.
[5]
C. Courcoubetis and R. Weber, Pricing Communication Networks: Economics, Technology and Modelling. New York: Wiley, 2003.
[6]
Internetworking Technologies Handbook 2005, Cisco documentation.
[7]
C. Dovrolis, D. Stiliadis, and P. Ramanathan, "Proportional differentiated services: Delay differentiation and packet scheduling," IEEE/ACM Trans. Networking, vol. 10, no. 1, pp. 12-26, Feb. 2002.
[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]
A. M. Odlyzko, "Paris metro pricing for the internet," in Proc. ACM Conf. Electron. Commerce, 1999, pp. 140-147.
[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]
H. Mendelson and S. Whang, "Optimal incentive-compatible priority pricing for the M/M/1 queue," Oper. Res., vol. 38, no. 5, pp. 870-883, 1990.
[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]
A. Orda, R. Rom, and N. Shimkin, "Competitive routing in multi-user environments," IEEE/ACM Trans. Netw., vol. 1, no. 5, pp. 510-521, Oct. 1993.
[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]
D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice-Hall, 1992.
[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]
L. Kleinrock, Queueing Systems. New York: Wiley, 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]
S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, U.K.: Cambridge Univ. Press, 2003.
[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.

Cited By

View all
  • (2018)Loss-based proportional fairness in multihop wireless networksWireless Networks10.1007/s11276-013-0644-320:5(805-816)Online publication date: 29-Dec-2018
  • (2007)A survey of uniqueness results for selfish routingProceedings of the 1st EuroFGI international conference on Network control and optimization10.5555/1762948.1762952(33-42)Online publication date: 5-Jun-2007

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 5
October 2008
238 pages

Publisher

IEEE Press

Publication History

Published: 01 October 2008
Revised: 06 March 2007
Received: 21 June 2006
Published in TON Volume 16, Issue 5

Author Tags

  1. Nash equillibirum
  2. capacity allocation
  3. differentiated services
  4. proportional QoS
  5. selfish routing

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2018)Loss-based proportional fairness in multihop wireless networksWireless Networks10.1007/s11276-013-0644-320:5(805-816)Online publication date: 29-Dec-2018
  • (2007)A survey of uniqueness results for selfish routingProceedings of the 1st EuroFGI international conference on Network control and optimization10.5555/1762948.1762952(33-42)Online publication date: 5-Jun-2007

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