Top

Wireless Personal Communications

Published in:

24-12-2016

Hop-Limit Path Mapping Algorithm for Virtual Network Embedding

Authors: Min Zhang, Xijie Tang

Published in: Wireless Personal Communications | Issue 3/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Virtual network (VN) mapping which deals with the allocation of network resources from the shared physical substrate to individual VNs is one of the key challenges for the application of realizing network virtualization. While a variety of state-of-the-art algorithms have attempted to address this issue from different aspects, the challenge still remains for mapping virtual link with hop count constraint. This paper presents a fast approximation path mapping algorithm to address this issue by formulating such virtual link mapping problem as a path-flow mathematical programming model, which aims to minimize the maximum link load factor. Through the use of the primal–dual method, a fully polynomial time approximation algorithm is proposed to solve this model. The experimental results show that the proposed algorithm can effectively solve the problem of path mapping with hop limit.

previous article Research on the Construction of the Universe Network Based on Quantum Entanglement Effect

next article The Real-Time Detection and Prediction Method for Ballistic Aircraft Based on Distributed Sensor Networks

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Carapinha, J., & Jiménez J.: ‘Network virtualization: a view from the bottom. In Proceedings of the 1st ACM workshop on virtualized infrastructure systems and architectures, Barcelona, Spain, August 2009, pp. 73–80.

Chowdhury, N., & Boutaba, R. (2008). A survey of network virtualization. Waterloo: David R. Cheriton School of Computer Science University of Waterloo.MATH

Houidi, I., Louati, W., Zeghlache, D., & Baucke, S. (2009). Virtual resource description and clustering for virtual network discovery. In Proceedings of ICC. IEEE, Dresden, Germany, pp. 1–6.

Zhu, Y., & Ammar M. (2006). Algorithms for assigning substrate network resources to virtual network components. In Proceedings of IEEE INFOCOM, Barcelona, Catalunya, Spain, April 2006.

Szeto, W., Iraqi, Y., & Boutaba R. (2003). A multi-commodity flow based approach to virtual network resource allocation. In Proceedings of IEEE GLOBECOM, pp. 3004–3008.

Yu, M., Yi, Y., Rexford, J., & Chiang, M. (2008). Rethinking virtual network embedding: Substrate support for path splitting and migration. ACM SIGCOMM Computer Communication Review, 38(2), 17–29.CrossRef

Chowdhury, N., Rahman, M., & Boutaba, R. (2009). Virtual network embedding with coordinated node and link mapping. In Proceedings of IEEE INFOCOM, pp. 783–791.

Lischka J., & Karl, H. (2009). A virtual network mapping algorithm based on subgraph isomorphism detection. In Proceedings of the 1st ACM workshop on virtualized infrastructure systems and architectures, Barcelona, Spain, August 2009, pp. 81–88.

Wang, L., Qu, H., & Zhao, J. (2014). Virtual network embedding algorithm for load balance with various requests. Chinese Journal of Electronics, 23(2), 382–387.

10.

Zhang, D., & Gao, L. (2014). Virtual network mapping through locality-aware topological potential and influence node ranking. Chinese Journal of Electronics, 23(1), 61–64.

11.

Zhang, Z. B., Cheng, X., Su, S., et al. (2013). A unified enhanced particle swarm optimization-based virtual network embedding algorithm. International Journal of Communication Systems, 26(8), 1054–1073.CrossRef

12.

Hu, Q., Wang, Y., & Cao, X. (2013). Resolve the virtual network embedding problem: A column generation approach. In Proceedings of IEEE INFOCOM, 2013.

13.

Jarray, Abdallah, & Karmouch, Ahmed. (2015). Decomposition approaches for virtual network embedding with one-shot node and link mapping. IEEE/ACM Transactions on Networking, 23(3), 1012–1025.CrossRef

14.

Inführ, J., & Raidl, G. R. (2011). Introducing the virtual network mapping problem with delay, routing and location constraints. Network optimization, volume 6701 of the series lecture notes in computer science, pp. 105–117.

15.

Su, S., Zhang, Z., Liu, A. X., Cheng, X., Wang, Y., & Zhao, X. (2014). Energy-aware virtual network embedding. IEEE/ACM Transactions on Networking, 22(5), 1607–1620.CrossRef

16.

Melo, M., Sargento, S., Killat, U., Timm-Giel, A., & Carapinha, J. (2015). Optimal virtual network embedding: Energy aware formulation. Computer Networks, 91(C), 184–195.CrossRef

17.

Zhang, S., Qian, Z., Wu, J., Lu, S., & Epstein, L. (2014). Virtual network embedding with opportunistic resource sharing. IEEE Transactions on Parallel and Distributed Systems, 25(3), 816–827.CrossRef

18.

Liu, S., Cai, Z., Xu, H., & Xu, M. (2015). Towards security-aware virtual network embedding. Computer Networks, 91(C), 151–163.CrossRef

19.

Gouveia, L. (1996). Multicommodity flow models for spanning trees with hop constraints. European Journal of Operational Research, 95, 178–190.CrossRefMATH

20.

Garg, N., & Könemann, J. (1998). Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proceedings IEEE Symposium on Foundations of Computer Science, pp. 300–309.

21.

Plotkin, S. A., Shmoys, D., & Tardos, E. (1995). Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20, 257–301.MathSciNetCrossRefMATH

Title: Hop-Limit Path Mapping Algorithm for Virtual Network Embedding
Authors: Min Zhang
Xijie Tang
Publication date: 24-12-2016
Publisher: Springer US
Published in: Wireless Personal Communications / Issue 3/2017
Print ISSN: 0929-6212
Electronic ISSN: 1572-834X
DOI: https://doi.org/10.1007/s11277-016-3933-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2017

Tree TDMA MAC Algorithm Using Time and Frequency Slot Allocations in Tree-Based WSNs

Development of a Reconfigurable and Miniaturized CPW Antenna for Selective and Wideband Communication

A Novel Spectrum Sensing Method Based on Tri-Stable Stochastic Resonance and Quantum Particle Swarm Optimization

Protocol for Controlling Congestion in Wireless Sensor Networks

MIMO AF RSs Based OSTBCs for LTE-A Downlink Physical Layer Network

Composite Fault Diagnosis in Wireless Sensor Networks Using Neural Networks