research-article

A Game Theoretic Approach for Distributed Resource Allocation and Orchestration of Softwarized Networks

Authors:

Salvatore D'Oro,

Laura Galluccio,

Sergio Palazzo,

Giovanni SchembraAuthors Info & Claims

IEEE Journal on Selected Areas in Communications, Volume 35, Issue 3

Pages 721 - 735

https://doi.org/10.1109/JSAC.2017.2672278

Published: 01 March 2017 Publication History

Abstract

Softwarization of networks allows simplifying deployment, configuration, and management of network functions. The driving force toward this evolution is represented by software defined networking that allows more flexible and dynamic network resource allocation and management. The efficient allocation and orchestration of network resources is of extreme importance for this softwarization process, and many centralized solutions have been proposed. However, they are complex and exhibit scalability issues. So, distributed solutions are to be preferred but, in order to be effective, should quickly converge towards equilibrium solutions. In this paper, we focus on making distributed resource allocation and orchestration a viable approach, and prove convergence of the relevant mechanisms. Specifically, we exploit game theory to model interactions between users requesting network functions and servers providing these functions. Accordingly, a two-stage Stackelberg game is presented, where servers act as leaders of the game and users as followers. Servers have conflicting interests and try to maximize their utility; users, on the other hand, use a replicator behavior and try to imitate other user’s decisions to improve their benefit. The framework proves the existence and uniqueness of an equilibrium, and a learning mechanism to converge to such equilibrium is proposed. Numerical results show the effectiveness of the approach.

References

[1]

Software-Defined Networking: The New Norm for Networks, <institution content-type=division>Open Networking Foundation</institution>, Palo Alto, CA, USA, White Paper, 2012.

[2]

M. Yu, L. Jose, and R. Miao, “ Software defined traffic measurement with OpenSketch,” in Proc. NSDI, vol. Volume 13 . Apr. 2013, pp. 29–42.

Digital Library

[3]

C. Monsanto, J. Reich, N. Foster, J. Rexford, and D. Walker, “ Composing software defined networks,” in Proc. NSDI, Apr. 2013, pp. 1–13.

Digital Library

[4]

Network Functions Virtualisation-Introductory White Paper, accessed on 4, 2017. {Online}. Available: http://portal.etsi.org/NFV/NFV White Paper.pdf

[5]

S. Raynovich, “ Lifecycle service orchestration (LSO) market overview,” SDX Central Market Report, 2016.

[6]

F. Wuhib, R. Yanggratoke, and R. Stadler, “ Allocating compute and network resources under management objectives in large-scale clouds,” J. Netw. Syst. Manage., vol. Volume 23, no. Issue 1, pp. 111–136, 2015.

Digital Library

[7]

M. Alicherry and T. V. Lakshman, “ Network aware resource allocation in distributed clouds,” in Proc. IEEE INFOCOM, Mar. 2012, pp. 963–971.

[8]

X. Meng, V. Pappas, and L. Zhang, “ Improving the scalability of data center networks with traffic-aware virtual machine placement,” in Proc. IEEE INFOCOM, Mar. 2010, pp. 1–9.

Digital Library

[9]

J. W. Jiang, T. Lan, S. Ha, M. Chen, and M. Chiang, “ Joint VM placement and routing for data center traffic engineering,” in Proc. IEEE INFOCOM, Mar. 2012, pp. 2876–2880.

[10]

A. Basta, W. Kellerer, M. Hoffmann, H. J. Morper, and K. Hoffmann, “ Applying NFV and SDN to LTE mobile core gateways, the functions placement problem,” in Proc. 4th Workshop All Things Cellular, Oper., Appl. Challenges, Chicago, IL, USA, 2014, pp. 33–34.

Digital Library

[11]

A. Lombardo, A. Manzalini, V. Riccobene, and G. Schembra, “ An analytical tool for performance evaluation of software defined networking services,” in Proc. IEEE SDNMO, Krakow, Poland, May 2014, pp. 1–7.

[12]

H. Moens and F. de Turck, “ VNF-P: A model for efficient placement of virtualized network functions,” in Proc. CNSM, Nov. 2014, pp. 418–423.

[13]

M. Bouet, J. Leguay, and V. Conan, “ Cost-based placement of virtualized deep packet inspection functions in SDN,” in Proc. IEEE MILCOM, Nov. 2013, pp. 992–997.

[14]

S. Gebert et al., “ opsel, “Demonstrating the optimal placement of virtualized cellular network functions in case of large crowd events,” in Proc. ACM SIGCOMM, 2014, pp. 359–360.

Digital Library

[15]

M. Scholler, M. Stiemerling, A. Ripke, and R. Bless, “ Resilient deployment of virtual network functions,” in Proc. 5th Int. Congr. Ultra Modern Telecommun. Control Syst. Workshops (ICUMT), Sep. 2013, pp. 208–214.

[16]

R. Cohen, L. Lewin-Eytan, J. S. Naor, and D. Raz, “ Near optimal placement of virtual network functions,” in Proc. IEEE INFOCOM, May 2015, pp. 1346–1354.

[17]

R. Ravi and A. Sinha, “ Approximation algorithms for multicommodity facility location problems,” SIAM J. Discrete Math., vol. Volume 24, no. Issue 2, pp. 538–551, 2010.

Digital Library

[18]

M. F. Bari, S. R. Chowdhury, R. Ahmed, and R. Boutaba, “ On orchestrating virtual network functions,” in Proc. 11th IEEE Int. Conf. Netw. Service Manage. (CNSM), Nov. 2015, pp. 50–56.

Digital Library

[19]

A. Gupta, M. F. Habib, P. Chowdhury, M. Tornatore, and B. Mukherjee, “ Joint virtual network function placement and routing of traffic in operator networks,” <institution content-type=department>Dept. Comput. Sci</institution>., <institution content-type=institution>University of California Davis</institution>, <institution content-type=division>One Shields Avenue Davis</institution>, CA, USA, Tech. Rep., 2015.

[20]

W. H. Sandholm, “<chapter-title>Evolutionary game theory</chapter-title>,” in Encyclopedia of Complexity and Systems Science . New York, NY, USA: Springer, 2009, pp. 3176–3205.

[21]

ETSI NVF GS, Network Functions Virtualization (NFV) Infrastructure Overview, ETSI, Sophia, France, 2015.

[22]

ETSI NFV GS, Network Function Virtualization (NFV) Management and Orchestration, NFV-MAN 001 v0.8.1, ETSI, Sophia, France, 2014.

[23]

G. Faraci and G. Schembra, “ An analytical model to design and manage a green SDN/NFV CPE node,” IEEE Trans. Netw. Service Manage., vol. Volume 12, no. Issue 3, pp. 435–450, 2015.

[24]

S. D'Oro, L. Galluccio, S. Palazzo, and G. Schembra, “ Exploiting congestion games to achieve distributed service chaining in NFV networks,” IEEE J. Sel. Areas Commun., vol. Volume 35, no. Issue 7, pp. 405–420, 2017.

Digital Library

[25]

R. W. Shephard and F. Rolf, The Law of Diminishing Returns, Production Theory . Berlin, Germany: Springer, 1974.

[26]

A. Mas-Colell et al., Microeconomic Theory, vol. Volume 1 . New York, NY, USA: Oxford Univ. Press, 1995.

[27]

A. Bosch-Domènech and N. J. Vriend, “Imitation of successful behaviour in cournot markets,” Econ. J., vol. Volume 113, no. Issue 487, pp. 495–524, 2003.

[28]

G. Nan, Z. Mao, M. Yu, M. Li, H. Wang, and Y. Zhang, “ Stackelberg game for bandwidth allocation in cloud-based wireless live-streaming social networks,” IEEE Syst. J., vol. Volume 8, no. Issue 1, pp. 256–267, 2014.

[29]

J. Elias, F. Martignon, A. Capone, and E. Altman, “ Non-cooperative spectrum access in cognitive radio networks: A game theoretical model,” Comput. Netw., vol. Volume 55, no. Issue 17, pp. 3832–3846, 2011.

Digital Library

[30]

H. Tembine, E. Altman, R. El-Azouzi, and Y. Hayel, “ Evolutionary games in wireless networks,” IEEE Trans. Syst., Man, Part B, vol. Volume 40, no. Issue 3, pp. 634–646, 2010.

Digital Library

[31]

S. Geisendorf et al., “ The influence of innovation and imitation on economic performance,” Econ. Issues, vol. Volume 14, no. Issue 1, p. pp.65, 2009.

[32]

P. D. Taylor and L. B. Jonker, “ Evolutionary stable strategies and game dynamics,” Math. Biosci., vol. Volume 40, no. Issue 1, pp. 145–156, 1978.

[33]

J. C. Goodman, “ Note on existence and uniqueness of equilibrium points for concave n-person games,” Econ., J. Econ. Soc., vol. Volume 48, no. Issue 1, p. pp.251, 1980.

[34]

J. B. Rosen, “ Existence and uniqueness of equilibrium points for concave n-person games,” Econ., J. Econ. Soc., vol. Volume 33, no. Issue 3, pp. 520–534, 1965.

[35]

S. D'Oro, P. Mertikopoulos, A. L. Moustakas, and S. Palazzo, “ Interference-based pricing for opportunistic multicarrier cognitive radio systems,” IEEE Trans. Wireless Commun., vol. Volume 14, no. Issue 12, pp. 6536–6549, 2015.

[36]

P. Mertikopoulos and A. L. Moustakas, “ The emergence of rational behavior in the presence of stochastic perturbations,” Ann. Appl. Probab., vol. Volume 20, no. Issue 4, pp. 1359–1388, 2010.

[37]

M. Benaïm, “<chapter-title>Dynamics of stochastic approximation algorithms</chapter-title>,” in Seminaire de Probabilites XXXIII . New York, NY, USA: Springer, 1999, pp. 1–68.

Cited By

Fan WLi XTang BSu YLiu Y(2024)MEC Network Slicing: Stackelberg-Game-Based Slice Pricing and Resource Allocation With QoS GuaranteeIEEE Transactions on Network and Service Management10.1109/TNSM.2024.340927721:4(4494-4509)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TNSM.2024.3409277
Datar MAltman ECadre H(2023)Strategic Resource Pricing and Allocation in a 5G Network Slicing Stackelberg GameIEEE Transactions on Network and Service Management10.1109/TNSM.2022.321658820:1(502-520)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1109/TNSM.2022.3216588
Hara TSasabe M(2022)Lagrangian Heuristics for Capacitated Shortest Path Tour Problem Based Online Service ChainingNOMS 2022-2022 IEEE/IFIP Network Operations and Management Symposium10.1109/NOMS54207.2022.9789758(1-9)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1109/NOMS54207.2022.9789758
Show More Cited By

Recommendations

A non-cooperative game-theoretic framework for resource allocation in network virtualization

Network virtualization is a new technology that aims at allowing multiple virtual networks (VNs) to coexist in the same equipment and to hide the heterogeneity of network infrastructure. The critical issue for a given infrastructure provider (InP), is ...
A Game-Theoretic Based Resource Allocation Strategy for Cloud Computing Services

We propose an economics-oriented cloud computing resources allocation strategy with the use of game theory. Then we develop a resource allocation algorithm named NCGRAA noncooperative game resource allocation algorithm to search the Nash equilibrium ...
A game-theoretic model for dynamic load balancing in distributed systems
ICAC3 '09: Proceedings of the International Conference on Advances in Computing, Communication and Control

Process of improving the performance of a parallel and distributed system through a redistribution of load among the processors is called load balancing. If it is being done at run time then it treats as dynamic load balancing. In this paper we present ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Journal on Selected Areas in Communications

IEEE Journal on Selected Areas in Communications Volume 35, Issue 3

March 2017

280 pages

ISSN:0733-8716

Issue’s Table of Contents

Copyright © 2017.

Publisher

IEEE Press

Publication History

Published: 01 March 2017

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fan WLi XTang BSu YLiu Y(2024)MEC Network Slicing: Stackelberg-Game-Based Slice Pricing and Resource Allocation With QoS GuaranteeIEEE Transactions on Network and Service Management10.1109/TNSM.2024.340927721:4(4494-4509)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TNSM.2024.3409277
Datar MAltman ECadre H(2023)Strategic Resource Pricing and Allocation in a 5G Network Slicing Stackelberg GameIEEE Transactions on Network and Service Management10.1109/TNSM.2022.321658820:1(502-520)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1109/TNSM.2022.3216588
Hara TSasabe M(2022)Lagrangian Heuristics for Capacitated Shortest Path Tour Problem Based Online Service ChainingNOMS 2022-2022 IEEE/IFIP Network Operations and Management Symposium10.1109/NOMS54207.2022.9789758(1-9)Online publication date: 25-Apr-2022
https://dl.acm.org/doi/10.1109/NOMS54207.2022.9789758
Cappello GColajanni GDaniele PGalluccio LGrasso CSchembra GScrimali L(2022)A Multi-UAVs’ Provider Model for the Provision of 5G Service Chains: A Game Theoretic ApproachLearning and Intelligent Optimization10.1007/978-3-031-24866-5_32(445-459)Online publication date: 5-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-24866-5_32
Zanzi LSciancalepore VGarcia-Saavedra ASchotten HCosta-Pérez X(2021)LACO: A Latency-Driven Network Slicing Orchestration in Beyond-5G NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2020.302796320:1(667-682)Online publication date: 9-Jan-2021
https://dl.acm.org/doi/10.1109/TWC.2020.3027963
Xie SMa JZhao J(2021)FlexChain: Bridging Parallelism and Placement for Service Function ChainsIEEE Transactions on Network and Service Management10.1109/TNSM.2020.304783418:1(195-208)Online publication date: 10-Mar-2021
https://dl.acm.org/doi/10.1109/TNSM.2020.3047834
Huang XTang YShao ZYang YXu H(2021)Joint Switch–Controller Association and Control Devolution for SDN Systems: An Integrated Online Perspective of Control and LearningIEEE Transactions on Network and Service Management10.1109/TNSM.2020.304467418:1(315-330)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1109/TNSM.2020.3044674
Sasabe MHara T(2021)Capacitated Shortest Path Tour Problem-Based Integer Linear Programming for Service Chaining and Function Placement in NFV NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2020.304432918:1(104-117)Online publication date: 10-Mar-2021
https://dl.acm.org/doi/10.1109/TNSM.2020.3044329
Sandoval RGarcia-Sanchez AGarcia-Haro J(2019)Performance optimization of LoRa nodes for the future smart city/industryEURASIP Journal on Wireless Communications and Networking10.1186/s13638-019-1522-12019:1(1-13)Online publication date: 1-Dec-2019
https://dl.acm.org/doi/10.1186/s13638-019-1522-1
Miao ZWang YHan Z(2019)A Supplier-Firm-Buyer Framework for Computation and Content Resource Assignment in Wireless Virtual NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2019.292134418:8(4116-4128)Online publication date: 9-Aug-2019
https://dl.acm.org/doi/10.1109/TWC.2019.2921344
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents