Non-linear game models for large-scale network bandwidth management

Springer Science and Business Media LLC - Tập 7 - Trang 421-444 - 2006
Dalia Fayek1, George Kesidis2, Anthony Vannelli3
1School of Engineering, University of Guelph, Guelph
2Electrical Engineering, The Pennsylvania State University, University Park
3Electrical and Computer Engineering Dept., University of Waterloo, Waterloo

Tóm tắt

The design of dynamic Label-Switched Paths (LSP’s) in MultiProtocol Label Switched (MPLS) networks is an NP-hard optimization problem. An LSP is a logical path between two nodes in the network. This path has a pre-reserved amount of bandwidth that defines its size. The LSP design problem consists of determining the number of these logical links and configuring the physical path and the size of each LSP. This paper presents an optimization model based on game theory. In this approach, connection requests are modeled as competitive players in a noncooperative game context. The transport network bandwidth constitutes the resource for which optimization is sought. The outcome of this optimization is a set of LSPs upon which the competing connections are routed.

Tài liệu tham khảo

Ahn S, Tsang RP, Tong S, Du DHC (1994) Virtual path layout design on ATM networks. In: Proceedings of IEEE INFOCOM’94, pp 192–200 Almendral LL, Fernandez JA, Cholvi V, Sanjuan MAF (2004) Oblivious router policies and Nash equilibrium. In: International symposium on computers communication volume 2, pp 736–741 Anandalingam K, Nam G (1997) Conflict and cooperation in designing international telecommunication networks. J. Oper. Res. Soc. 48(6):600–611 Aneroussis NG, Lazar AA (1996) Virtual path control for ATM networks with call level quality of service guarantees. In: Proceedings of IEEE INFOCOM’96 Aresti A, Ninan BM, Devetsikiotis M (2004) Resource allocation games in connection-oriented networks under imperfect information. In: IEEE international conference on communications (ICC), pp 1060–1064 Awduche D, Rekhter Y (2001) MultiProtocol lambda switching: Combining MPLS traffic engineering control with optical crossconnects. IEEE Communications Magazine 39(3):111–116 Awduche D et al. (2000) RSVP-TE: Extensions to RSVP for LSP Tunnels. Internet Draft draft-ietf-mpls-rsvp-lsp-tunnel-07.txt Aydemir M, Viniotis Y (1996) Deterministic algorithm for VP assignment in ATM networks. Comput Commun 19:1036–1050 Başar TJ, an Olsder G (1995) Dynamic Noncooperative Game Theory. Academic press Blefari-Melazzi N, Femminella M, Reali G (2000) Dynamic bandwidth allocation in a circuit-switched network: provision of deterministic and statistical QoS guarantees. In: INFOCOM Brockmeyer E, Halstrom HL, Jensen A (1948) The life and Works of A. K. Erlang. Academy of Technical Sciences, Copenhagen. Campos-Nanez E, Patek SD (2003) On-line tuning of prices for network services. In: IEEE INFOCOM volume 2, pp 1231–1241 Chlamtac I, Faragó A, Zhang T (1993) How to establish and utilize virtual paths in ATM Networks. In: Proceedings of IEEE ICC’93, pp 1368–1372 Courcoubetis C, Dimakis A, Reiman M (2001) Providing bandwidth guarantees over a best-effort network: call-admission and pricing. In: INFOCOM Fayek D (2001) Hierarchical virtual paths allocation in large-scale ATM networks using noncooperative game models. Ph.D. thesis, Electrical and Computer Engineering, University of Waterloo Fayek D, Kesidis G, Vannelli A (1999) Hierarchical virtual path allocation in larg-scale ATM networks using noncooperative game models. In: Canadian Conference on Broadband Research (CCBR) Ottawa, pp 222–233 Gerstel O, Cidon I, Zaks S (1996) The layout of virtual paths in ATM networks. IEEE/ACM Trans Netw 4(6):873–884 Ghizzi M, Cerutti I, Castoldi P, Fumagalli A (2004) Performance of label stacking capable MPLS reconfigurable networks. In: IEEE workshop on local and metropolitan area networks, pp 129–132 Gibbons A (1985) Algorithmic graph theory. Cambridge University Press Goyal S, Bellur U (2005) Mapping application QoS to network configurations for MPLS networks. In: Consumer Communications and Networking Conference, CCNC pp 562–564 Hadama H, Kawamura R, Izaki T, Tokizawa T (1994) Direct virtual path configuration in large-scale ATM networks. In: Proceedings of IEEE INFOCOM’94, pp 201–207 Holmström K (1999) TOMLAB User’s Guide http://www.ima.mdh.se/tom Hussain I (2004) Overview of MPLS technology and traffic engineering applications. In: Internation conference on networking and communication, ICNN Jin Y, Kesidis G (2003) Nash equilibria of a generic networking game with applications to circuit-switched networks. In: INFOCOM, pp 1242–1249 Jin Y, Kesidis G (2005) Dynamics of usage-priced communication networks: the case of a single bottleneck resource. IEEE Transactions on Networking Jones DR, Perttunen CD, Stuckman BE (1993) Lipschitzian optimization without the Lipschitz constant. J Optim Theory Appl 79(1):157–181 Joshi MC, Bose RK (1985) Some topics in nonlinear functional analysis. John Wiley, New York Kelly FP (1991) Loss networks. The ann Appl Prob 1(3):319–378 Korilis YA, Lazar AA, Orda A (1997a) Achieving network optima using stackelberg routing strategies. IEEE/ACM Trans Netw 5(1) 161–173 Korilis YA, Varvarigou TA, Ahuja SR (1997b) Incentive-compatible pricing strategies in noncooperative networks. In: INFOCOM Lazar AA, Orda A, Pendarakis DE (1995) Virtual path bandwidth allocation in multi-user networks. In: Proceedings of IEEE INFOCOM’95, pp 312–320 Lee GM, Choi JK (2001) A study of flow-based traffic admission control algorithm in the ATM-based MPLS network. In: 15th International conference on information networking, pp 213– 218 Lim JY, Chae KJ (2001) Differentiated link based QoS routing algorithms for multimedia traffic in MPLS networks. In: Information networking, pp 587–592 Lin F, Cheng K-T (1993) Virtual path assignment and virtual circuit routing in ATM Networks. In: GLOBECOM’93, pp 436–441 Liu Y, Simaan MA (2005) Noninferior nash strategies for routing control in parallel-link communication networks. In: IEEE consumer communications and networking conference, CCNC, pp 510– 514 Marbukh V (2001) Minimum regret approach to network management under uncertainty with application to connection admission control and routing. In: Internation conference on networking (ICN), pp 309– 318 Marbukh V, Moayeri N (1999) A framework for throughput and stability analysis of a DS-CDMA network. In: IEEE-VTC, pp 596–600 Medrano MS, Trindade MB, De Chaves NSA, Fernandez MD, Filho HJM (2004) An optimization model for MPLS networks. In: IEEE International symposium on telecommunications network strategy and planning, pp 285–290 Messerli EJ (1972) Proof of a convexity property of the Erlang B formula. Bell Syst Technol J 51(4):951–953 Rosen E, Viswanathan A, Callon R (2001) Multi-protocol label switching architecture. IETF RFC 3031 rfc3031.txt Ross KW (1995) Multiservice loss models for broadband telecommunication networks. Springer-Verlag Shi TJ, Mohan G (2004) An efficient traffic engineering approach based on flow distribution and splitting in MPLS networks. In: IEEE International conference on networks, ICON, pp 99–103 Smart DR (1974) Fixed point theorems. London: Cambridge University Press Sullivan E, Callon R (1994) P-NNI draft specification. ATM Forum The ATM Forum (1996) Private network-network interface specification version 1.0. The ATM Forum Trimintzios P, Pavlou P, Flegkas G, Georgatsos P, Asgari A, Mykoniati E (2003) Service-driven traffic engineering for intradomain quality of service management. IEEE Network 17(3):29–36 Wolff RW (1989) Stochastic modeling and the theory of queues. Englewood Cliffs, N.J.: Prentice Hall Xiao X, Hannan A, Bailey B, Ni LM (2000) Traffic Engineering with MPLS in the Internet. IEEE Network 14(2):28–33 Xiao X, Ni LM (1999) Internet QoS: a big picture. IEEE Network, pp 8–18 Xinjie C, Subramanian KR (2000) An optimal admission control scheme for the wireless ATM networks. In: NOM2000 Yaïche H, Mazumdar R, Rosenberg C (2000) Distributed algorithms for fair bandwidth allocation to elastic services in broadband networks. In: INFOCOM