Xiang Cheng
Abstract
Virtualizing and sharing networked resources have become a growing trend that reshapes the computing and networking architectures. Embedding multiple virtual networks (VNs) on a shared substrate is a challenging problem on cloud computing platforms and large-scale sliceable network testbeds. In this paper we apply the Markov Random Walk (RW) model to rank a network node based on its resource and topological attributes. This novel topology-aware node ranking measure reflects the relative importance of the node. Using node ranking we devise two VN embedding algorithms. The first algorithm maps virtual nodes to substrate nodes according to their ranks, then embeds the virtual links between the mapped nodes by finding shortest paths with unsplittable paths and solving the multi-commodity flow problem with splittable paths. The second algorithm is a backtracking VN embedding algorithm based on breadth-first search, which embeds the virtual nodes and links during the same stage using node ranks. Extensive simulation experiments show that the topology-aware node rank is a better resource measure and the proposed RW-based algorithms increase the long-term average revenue and acceptance ratio compared to the existing embedding algorithms.
- Amazonec2,http://aws.amazon.com/ec2/.Google Scholar
- VNE-RW Simulator http://int.bupt.edu.cn/~sensu/vne-rw.html.Google Scholar
- VNE Simulator http://www.cs.princeton.edu/~minlanyu/embed.tar.gz.Google Scholar
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin, and K. Weihe. Network fows: theory, algorithms, and applications. Prentice hall Englewood Cliffs, NJ, 1993. Google ScholarDigital Library
- David G. Andersen. Theoretical approaches to node assignment. Unpublished Manuscript, December 2002.Google Scholar
- M. Bianchini, M. Gori, and F. Scarselli. Inside pagerank. ACM Transactions on Internet Technology (TOIT), 5(1):92--128, 2005. Google ScholarDigital Library
- N. Butt, M. Chowdhury, and R. Boutaba. Topology-Awareness and Re-optimization Mechanism for Virtual Network Embedding. In Networking 2010: 9th International Ifip Tc 6 Networking Conference, Chennai, India, May 11-15, 2010, Proceedings, page 27. Not Avail, 2010. Google ScholarDigital Library
- N.M.M.K. Chowdhury and R. Boutaba. Network virtualization: state of the art and research challenges. IEEE Communications magazine, 47(7):20--26, 2009. Google ScholarDigital Library
- N.M.M.K. Chowdhury, M.R. Rahman, and R. Boutaba. Virtual network embedding with coordinated node and link mapping. In IEEE INFOCOM, 2009.Google ScholarCross Ref
- L.P. Cordella, P. Foggia, C. Sansone, and M. Vento. An improved algorithm for matching large graphs. In 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, pages 149--159, 2001.Google Scholar
- M. Diligenti, M. Gori, M. Maggini, and D. di Ingegneria dell'Informazione. A unified probabilistic framework for web page scoring systems. IEEE Transactions on knowledge and data engineering, 16(1):4--16, 2004. Google ScholarDigital Library
- D. Eppstein. Finding the k shortest paths. In Proc. of IEEE Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press, 1994. Google ScholarDigital Library
- J. Fan and M. Ammar. Dynamic topology configuration in service overlay networks: A study of reconfiguration policies. In Proc. IEEE INFOCOM, 2006.Google ScholarCross Ref
- N. Feamster, L. Gao, and J. Rexford. How to lease the Internet in your spare time. ACM SIGCOMM Computer Communication Review, 37(1):64, 2007. Google ScholarDigital Library
- Global Environment for Network Innovations. National Science Foundation, http://www.geni.net/, August 2005.Google Scholar
- M. Gori, M. Maggini, and L. Sarti. Exact and approximate graph matching using random walks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(7):1100--1111, 2005. Google ScholarDigital Library
- C. Guo, G. Lu, H.J. Wang, S. Yang, C. Kong, P. Sun, W. Wu, Y. Zhang, MSR Asia, and MSR Redmond. SecondNet: A Data Center Network Virtualization Architecture with Bandwidth Guarantees.Google Scholar
- A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yener. Provisioning a virtual private network: A network design problem for multicommodity flow. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 389--398. ACM New York, NY, USA, 2001. Google ScholarDigital Library
- J. He, R. Zhang-Shen, Y. Li, C.Y. Lee, J. Rexford, and M. Chiang. Davinci: Dynamically adaptive virtual networks for a customized internet. In Proceedings of the 2008 ACM CoNEXT Conference, pages 1--12. ACM, 2008. Google ScholarDigital Library
- I. Houidi, W. Louati, and D. Zeghlache. A distributed virtual network mapping algorithm. In Proceedings of IEEE ICC, pages 5634--5640, 2008.Google ScholarCross Ref
- J. Lischka and H. Karl. A virtual network mapping algorithm based on subgraph isomorphism detection. In Proceedings of the 1st ACM workshop on Virtualized infrastructure systems and architectures, pages 81--88. ACM, 2009. Google ScholarDigital Library
- J. Lu and J. Turner. Efficient mapping of virtual networks onto a shared substrate. Department of Computer Science and Engineering, Washington University in St. Louis, Technical Report WUCSE-2006, 35, 2006.Google Scholar
- L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.Google Scholar
- R. Ricci, C. Alfeld, and J. Lepreau. A solver for the network testbed mapping problem. ACM SIGCOMM Computer Communication Review, 33(2):81, 2003. Google ScholarDigital Library
- E. Seneta. Non-negative matrices and Markov chains. Springer Verlag, 2006.Google Scholar
- W. Szeto, Y. Iraqi, and R. Boutaba. A multi-commodity flow based approach to virtual network resource allocation. In Proc. GLOBECOM: IEEE Global Telecommunications Conference, 2003.Google ScholarCross Ref
- JS Turner and DE Taylor. Diversifying the internet. In IEEE Global Telecommunications Conference, 2005. GLOBECOM'05, volume 2.Google Scholar
- M. Yu, Y. Yi, J. Rexford, M. Chiang, et al. Rethinking virtual network embedding: Substrate support for path splitting and migration. COMPUTER COMMUNICATION REVIEW, 38(2):17, 2008. Google ScholarDigital Library
- Y. Zhu and M. Ammar. Algorithms for assigning substrate network resources to virtual network components. In Proc. IEEE INFOCOM, 2006.Google ScholarCross Ref
Index Terms
- Virtual network embedding through topology-aware node ranking
Recommendations
Rethinking virtual network embedding: substrate support for path splitting and migration
Network virtualization is a powerful way to run multiple architectures or experiments simultaneously on a shared infrastructure. However, making efficient use of the underlying resources requires effective techniques for virtual network embedding--...
Topology-aware virtual network embedding based on closeness centrality
Network virtualization aims to provide a way to overcome ossification of the Internet. However, making efficient use of substrate resources requires effective techniques for embedding virtual networks: mapping virtual nodes and virtual edges onto ...
A Latency-Aware Reward Model Based Greedy Heuristic for the Virtual Network Embedding Problem
VALUETOOLS'16: proceedings of the 10th EAI International Conference on Performance Evaluation Methodologies and Tools on 10th EAI International Conference on Performance Evaluation Methodologies and ToolsThe increasing use of virtualization (e.g., in Cloud Computing, Software Defined Networks), demands to Infrastructure Providers (InPs) to optimize the placement of the virtual network requests (VNRs) into a substrate network. In addition to that, they ...
Comments