nach oben

Journal of Network and Systems Management

Erschienen in:

09.05.2017

Node and Link Allocation in Network Virtualization Based on Distributed Constraint Optimization

verfasst von: Alexander R. Gularte, Odorico M. Mendizabal, Raquel M. Barbosa, Diana F. Adamatti

Erschienen in: Journal of Network and Systems Management | Ausgabe 1/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Virtual Networks (VNs) offer a flexible and economic approach to deploy customer suited networks. However, defining how resources of a physical network are used to support VNs requirements is a NP-hard problem. For this reason, heuristics have been used on mapping of virtual networks. Although heuristics do not ensure the optimal solution, they implement fast solutions and showed satisfactory results. This work presents a modeling of the node and link allocation problem using Distributed Constraint Optimization Problem (DCOP) with factor graphs, which is a formalism widely used in real distributed optimization problems. In our approach, we use the max-sum algorithm to solve the DCOP. Correctness criteria for this approach are discussed and verifications are conducted through model checking.

Vorheriger Artikel Putting Sensor Data to the Service of the Smart Grid: From the Substation to the AMI

Nächster Artikel OAuthkeeper: An Authorization Framework for Software Defined Network

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The mathematical symbol\(\backslash\)(backslash) means complement of sets. For example, A\(\backslash\)B means: the set that contains all elements of A that does not belong to B. For example: {1,2,3,4}\(\backslash\)3,4,5,6} = {1,2}.

Fischer, A., Botero, J., Beck, M., De Meer, H., Hesselbach, X.: Virtual Network Embedding: A Survey. Communications Surveys Tutorials, IEEE PP(99), 1 (2013). doi:10.1109/SURV.2013.013013.00155

Beck, M.T., Fischer, A., de Meer, H., Botero, J., Hesselbach, X.: A distributed, parallel, and generic virtual network embedding framework. In: IEEE International Conference on Communications (ICC), 2013 (2013), pp. 3471–3475. doi:10.1109/ICC.2013.6655087

Beck, M.T., Fischer, A., Botero, J.F., Linnhoff-Popien, C., de Meer, H.: Distributed and scalable embedding of virtual networks. J. Netw. Comput. Appl. 56(C), 124 (2015). doi:10.1016/j.jnca.2015.06.012 CrossRef

Farinelli, A., Rogers, A., Petcu, A., Jennings, N.R.: Decentralised coordination of low-power embedded devices using the max-sum algorithm. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 2 (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2008), AAMAS ’08, pp. 639–646. http://dl.acm.org/citation.cfm?id=1402298.1402313

Farinelli, A., Rogers, A., Petcu, A., Jennings, N.R.: Decentralised coordination of low-power embedded devices using the max-sum algorithm. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 2 (International Foundation for Autonomous Agents and Multiagent Systems, 2008), pp. 639–646

Petcu, A., Faltings, B.: DPOP: A Scalable Method for Multiagent Constraint Optimization. In: IJCAI 05 (Edinburgh, Scotland, 2005), pp. 266–271

Modi, P.J., Shen, W.M., Tambe, M., Yokoo, M.: ADOPT: asynchronous distributed constraint optimization with quality guarantees. Artif. Intell. 161(1), 149 (2005)MathSciNetCrossRefMATH

Mailler, R., Lesser, V.R.: Asynchronous partial overlay: a new algorithm for solving distributed constraint satisfaction problems. J. Artif. Int. Res. 25(1), 529 (2006). http://dl.acm.org/citation.cfm?id=1622543.1622558

Petcu, A., Faltings, B.: A scalable method for multiagent constraint optimization. In: International Joint Conference on Artificial Intelligence, vol. 19 (Lawrence Erlbaum Associates LTD, 2005), vol. 19, p. 266

10.

Houidi, I., Louati, W., Zeghlache, D.: Distributed Virtual Network Mapping Algorithm. In: IEEE International Conference on Communications, 2008. ICC ’08. (2008), pp. 5634–5640. doi:10.1109/ICC.2008.1056

11.

Rogers, A., Farinelli, A., Stranders, R., Jennings, N.R.: Bounded approximate decentralised coordination via the max-sum algorithm. Artif. Intell. 175(2), 730 (2011). doi:10.1016/j.artint.2010.11.001 MathSciNetCrossRefMATH

12.

Stranders, R., Farinelli, A., Rogers, A., Jennings, N.R.: Decentralised coordination of mobile sensors using the max-sum algorithm. In: Proceedings of the 21st International Joint Conference on Artifical Intelligence (Morgan Kaufmann Publishers Inc., 2009), pp. 299–304

13.

Zivan, R., Peled, H.: Max/Min-sum Distributed Constraint Optimization Through Value Propagation on an Alternating DAG. In: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 1 (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2012), AAMAS ’12, pp. 265–272. http://dl.acm.org/citation.cfm?id=2343576.2343614

14.

Holzmann, G.: Spin Model Checker, the: Primer and Reference Manual, 1st edn. Addison-Wesley Professional, Boston (2003)

15.

Holzmann, G.J.: The Model Checker SPIN. IEEE Trans. Softw. Eng. 23(5), 279 (1997). doi:10.1109/32.588521 CrossRef

16.

Botero, J., Hesselbach, X., Fischer, A., Meer, H.: Optimal mapping of virtual networks with hidden hops. Telecommun. Syst. 51(4), 273 (2012). doi:10.1007/s11235-011-9437-0 CrossRef

17.

Chowdhury, M., Rahman, M.R., Boutaba, R.: ViNEYard: Virtual network embedding algorithms with coordinated node and link mapping. IEEE/ACM Trans. Netw. 20(1), 206 (2012). doi:10.1109/TNET.2011.2159308 CrossRef

18.

Nogueira, J., Melo, M., Carapinha, J., Sargento, S.: Virtual Network Mapping into Heterogeneous Substrate Networks. In: Proceedings of the 2011 IEEE Symposium on Computers and Communications (IEEE Computer Society, Washington, DC, USA, 2011), ISCC ’11, pp. 438–444. doi:10.1109/ISCC.2011.5983876

19.

Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. (TOPLAS) 5(1), 66 (1983)CrossRefMATH

20.

Dijkstra, E.W.: Guarded commands, nondeterminacy and formal derivation of programs. Commun. ACM 18(8), 453 (1975)MathSciNetCrossRefMATH

21.

Fischer, A., Botero, J.F., Beck, M.T., De Meer, H., Hesselbach, X.: Virtual network embedding: a survey. IEEE Commun. Surv. Tutor. 15(4), 1888–1906 (2013)CrossRef

22.

Chowdhury, M., Samuel, F., Boutaba, R.: PolyViNE: policy-based virtual network embedding across multiple domains. In: Proceedings of the Second ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures (ACM, New York, NY, USA, 2010), VISA ’10, pp. 49–56. doi:10.1145/1851399.1851408

23.

Zhang, M., Wu, C., Jiang, M., Yang, Q.: Mapping multicast service-oriented virtual networks with delay and delay variation constraints. In: IEEE Global Telecommunications Conference (GLOBECOM 2010), 2010 (IEEE, 2010), pp. 1–5

24.

Inführ, J., Raidl, G.R.: Introducing the virtual network mapping problem with delay, routing and location constraints. In: Network Optimization (Springer, 2011), pp. 105–117

25.

Yang, Y., Chen, S.z., Li, X., Wang, Y.: Rmap: An algorithm of virtual network resilience mapping. In: 7th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM), 2011 (IEEE, 2011), pp. 1–4

26.

Belbekkouche, A., Hasan, M.M., Karmouch, A.: Resource discovery and allocation in network virtualization. IEEE Commun. Surv. Tutor. 14(4), 1114 (2012)CrossRef

27.

Yeoh, W.: Speeding up distributed constraint optimization search algorithms. Ph.D. thesis, University of Southern California (2010)

28.

Zhang, W., Wang, G., Xing, Z., Wittenburg, L.: Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks. Artif. Intell. 161(1), 55 (2005)MathSciNetCrossRefMATH

29.

Maheswaran, R.T., Pearce, J.P., Tambe, M.: Distributed algorithms for DCOP: a graphical-game-based approach. In: ISCA PDCS (2004), pp. 432–439

30.

Pearce, J.P.: Solution sets for DCOPs and graphical games. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, 2006), pp. 577–584

Titel: Node and Link Allocation in Network Virtualization Based on Distributed Constraint Optimization
verfasst von: Alexander R. Gularte
Odorico M. Mendizabal
Raquel M. Barbosa
Diana F. Adamatti
Publikationsdatum: 09.05.2017
Verlag: Springer US
Erschienen in: Journal of Network and Systems Management / Ausgabe 1/2018
Print ISSN: 1064-7570
Elektronische ISSN: 1573-7705
DOI: https://doi.org/10.1007/s10922-017-9410-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2018

Modelling LTE Solved Troubleshooting Cases

Seamless Configuration of Virtual Network Functions in Data Center Provider Networks

An HTTP/2 Push-Based Approach for Low-Latency Live Streaming with Super-Short Segments

OAuthkeeper: An Authorization Framework for Software Defined Network

Acknowledgment to Reviewers

Adaptive Service Management in Mobile Cloud Computing by Means of Supervised and Reinforcement Learning

Premium Partner