KSII Transactions on Internet and Information Systems (TIIS)

Korean Society for Internet Information (한국인터넷정보학회)
권호 표지
DOI QR코드

DOI QR Code

Topology-aware Virtual Network Embedding Using Multiple Characteristics

  • Liao, Jianxin (State Key Lab of Networking and Switching Technology, Beijing University of Posts and Telecommunications) ;
  • Feng, Min (State Key Lab of Networking and Switching Technology, Beijing University of Posts and Telecommunications) ;
  • Li, Tonghong (Department of Computer Science, Technical University of Madrid) ;
  • Wang, Jingyu (State Key Lab of Networking and Switching Technology, Beijing University of Posts and Telecommunications) ;
  • Qing, Sude (State Key Lab of Networking and Switching Technology, Beijing University of Posts and Telecommunications)
  • Received : 2013.01.13
  • Accepted : 2013.12.28
  • Published : 2014.01.30
Download PDF
⟨ Previous Next ⟩

Abstract

Network virtualization provides a promising tool to allow multiple heterogeneous virtual networks to run on a shared substrate network simultaneously. A long-standing challenge in network virtualization is the Virtual Network Embedding (VNE) problem: how to embed virtual networks onto specific physical nodes and links in the substrate network effectively. Recent research presents several heuristic algorithms that only consider single topological attribute of networks, which may lead to decreased utilization of resources. In this paper, we introduce six complementary characteristics that reflect different topological attributes, and propose three topology-aware VNE algorithms by leveraging the respective advantages of different characteristics. In addition, a new KS-core decomposition algorithm based on two characteristics is devised to better disentangle the hierarchical topological structure of virtual networks. Due to the overall consideration of topological attributes of substrate and virtual networks by using multiple characteristics, our study better coordinates node and link embedding. Extensive simulations demonstrate that our proposed algorithms improve the long-term average revenue, acceptance ratio, and revenue/cost ratio compared to previous algorithms.

Keywords

References

  1. N. Chowdhury and R. Boutaba, "A survey of network virtualization," Computer Networks, vol.54, no. 5, pp. 862-876, 2010. https://doi.org/10.1016/j.comnet.2009.10.017
  2. T. Anderson, L. Peterson, S. Shenker and J. Turner, "Overcoming the Internet impasse through virtualization," IEEE Computer Magazine, vol. 38, no. 4, pp.34-41, 2005.
  3. J. Turner and D. Taylor, "Diversifying the Internet," in Proc. of IEEE GLOBECOM, vol. 2, pp. 755-760, 2005.
  4. N. Feamster, L. Gao and J. Rexford, "How to lease the Internet in your spare time," ACM SIGCOMM Computer Communication Review, vol. 37, no. 1, pp. 61-64, 2007.
  5. A. Bavier, N. Feamster, M. Huang, L. Peterson and J. Rexford, "In VINI veritas: Realistic and controlled network experimentation," ACM SIGCOMM Computer Communication Review, vol. 36, no. 4, pp. 3-14, 2006. https://doi.org/10.1145/1140086.1140087
  6. W. Szeto, Y. Iraqi and R. Boutaba, "A multi-commodity flow based approach to virtual network resource allocation," in Proc. of IEEE GLOBECOM, vol. 6, pp. 3004-3008, 2003.
  7. Y. Zhu and M. Ammar, "Algorithms for assigning substrate network resources to virtual network components," in Proc. of IEEE INFOCOM, 2006.
  8. I. Houidi, W. Louati and D. Zeghlache, "A distributed virtual network mapping algorithm," in Proc. of IEEE ICC, pp. 5634-5640, 2008.
  9. M. Yu, Y. Yi, J. Rexford and M. Chiang, "Rethinking virtual network embedding: substrate support for path splitting and migration," ACM SIGCOMM Computer Communication Review, vol. 38, no. 2, pp. 17-29, 2008.
  10. N. Chowdhury, M. Rahman and R. Boutaba, "Virtual network embedding with coordinated node and link mapping," in Proc. of IEEE INFOCOM, pp. 783-791, 2009.
  11. X. Cheng, S. Su, F. Yang et al., "Virtual network embedding through topology-Aware node ranking," ACM SIGCOMM Computer Communication Review, vol. 41, no. 2, pp. 38-47, 2011.
  12. S. Qing, J. Liao, J. Wang, X. Zhu and Q. Qi, "Hybrid virtual network embedding with K-core decomposition and time-oriented priority," in Proc. of IEEE ICC, pp. 2695-2699, 2012.
  13. Z. Wang, Y. Han, T. Lin, H. Tang and S. Ci, "Virtual network embedding by exploiting topological information," in Proc. of IEEE GLOBECOM, 2012.
  14. P. Marchetta, P. Merindol, B. Donnet, A. Pescape and J. Pansiot, "Topology discovery at the router level: a new hybrid tool targeting ISP networks," IEEE Journal on Selected Areas in Communications, vol. 29, no.9, pp.1776-1787, 2011. https://doi.org/10.1109/JSAC.2011.111003
  15. D. Stezenbach, M. Hartmann and K. Tutschku, "Parameters and challenges for virtual network embedding in the future internet," in Proc. of IEEE NOMS, pp. 1272-1278, 2012.
  16. M. Newman, Networks: An Introduction, Oxford University Press, Oxford, UK, 2010.
  17. T. Opsahl, F. Agneessens and J. Skvoretz, "Node centrality in weighted networks: generalizing degree and shortest paths," Social Networks, vol. 32, no. 3, pp. 245-251, 2010. https://doi.org/10.1016/j.socnet.2010.03.006
  18. L. Freeman, The development of social network analysis, Empirical Press, Vancouver, Canada, 2004.
  19. P. Hagmann, L. Cammoun, X. Gigandet, et al., "Mapping the structural core of human cerebral cortex," PLoS biology, vol. 6, no. 7: e159, 2008. https://doi.org/10.1371/journal.pbio.0060159
  20. D. Eppstein, "Finding the k shortest paths," SIAM Journal on computing, vol. 28, no. 2, pp. 652-673, 1998. https://doi.org/10.1137/S0097539795290477
  21. R. K. Ahuja, T. L. Magnanti, J. B. Orlin and K. Weihe, Network flows: theory, algorithms, and applications, Prentice Hall, 1993.
  22. J. Castro and N. Nabona, "An implementation of linear and nonlinear multicommodity network flows," European Journal of Operational Research, vol. 92, no.1, pp.37-53, 1996. https://doi.org/10.1016/0377-2217(95)00137-9
  23. D. Austin, "How Google finds your needle in the web's haystack," American Mathematical Society Feature Column, pp.10-12, 2006.
  24. S. N. Dorogovtsev, A. V. Goltsev and J. F. F. Mendes, "K-core organization of complex networks," Physical review letters, vol. 96, no. 4, 2006.
  25. J. I. Alvarez-Hamelin, L. Dall'Asta, A. Barrat and A. Vespignani, "Large scale networks fingerprinting and visualization using the k-core decomposition," Advances in neural information processing systems, pp. 41-50, 2005.
  26. E. Zegura, K. Calvert and S. Bhattacharjee, "How to model an Internetwork," in Proc. of IEEE INFOCOM, 1996.
  27. Virtual Network Embedding Simulator. https://github.com/minlanyu/embed

Cited by

  1. LIVE: Learning and Inference for Virtual Network Embedding vol.24, pp.2, 2014, https://doi.org/10.1007/s10922-015-9349-5
  2. Virtual Network Embedding with Multi-attribute Node Ranking Based on TOPSIS vol.10, pp.2, 2014, https://doi.org/10.3837/tiis.2016.02.005
  3. Virtual Network Embedding through Security Risk Awareness and Optimization vol.10, pp.7, 2014, https://doi.org/10.3837/tiis.2016.07.002
  4. Virtual Network Embedding based on Node Connectivity Awareness and Path Integration Evaluation vol.11, pp.7, 2017, https://doi.org/10.3837/tiis.2017.07.005
  5. COVE: Co-operative Virtual Network Embedding for Network Virtualization vol.26, pp.1, 2014, https://doi.org/10.1007/s10922-017-9408-1
  6. Elastic Vehicular Resource Providing Based on Service Function-Group Resource Mapping of Smart Identify Network vol.12, pp.2, 2014, https://doi.org/10.1109/jsyst.2017.2771443
  7. Different QoS Constraint Virtual SDN Embedding under Multiple Controllers vol.12, pp.9, 2018, https://doi.org/10.3837/tiis.2018.09.003