摘要
作为一个可以解决现有互联网僵化问题的利器,网络虚拟化技术在学术界和工业界吸引了越来越多的关注。为了将网络虚拟化技术融入下一代互联网架构中,需要克服一个严峻的挑战,即将多个异构的虚拟网络同时映射至底层共用的基础设施中。这个问题被称为虚拟网络映射问题。由于存在多个维度的资源限制,虚拟网络映射问题属于NP困难问题,相关的解决方案大多依赖于启发式算法。本文专注于虚拟网络映射算法的改进,主要工作包括以下四个方面：
(一)对虚拟网络映射算法的最新进展做了详细的综述,并将现有的映射算法进行分类。现有的映射算法可以分为基于单个基础设施提供商的算法和基于多个基础设施提供商的算法。基于单个基础设施提供商的算法可以进一步按问题空间是否受限和映射过程是否完整进行细分；基于多个基础设施提供商的算法可以根据水平维度和垂直维度进行细分;在文章的结论部分,对该领域的研究方向提出了展望。
(二)提出了基于截止时间优先的混合式虚拟网络映射算法。不限制问题空间的映射算法可以细分为一阶段的映射算法和两阶段的映射算法,这两类算法各有优劣。通过k核分解技术,将虚拟网络划分为核心网络和边缘网络,并在这两类子网中分别应用两阶段的映射算法和一阶段的映射算法。此外,当一个虚拟网络请求的生命周期结束时,底层物理网络将释放其占用的资源。结合这个特点,使用基于截止时间优先的队列调度机制,进一步改进了映射算法的性能。
(三)提出了基于贝叶斯网络推理的拓扑感知型映射算法。基于马尔科夫随机游走模型,拓扑感知型的虚拟网络映射算法对节点的资源能力进行排名,通过改变节点之间的匹配关系,改进映射算法的性能。然而,节点排名采用的资源评价标准并不合理。此外,由于忽视了已选节点对待选节点的影响,节点的贪婪匹配映射规则会导致不必要的带宽浪费。因此,本文从统计学的角度重新思考虚拟网络的映射过程,通过收集虚拟网络映射的历史信息,生成两个关联矩阵,分别代表底层网络中节点的重要度和节点之间的关联度。基于这些关联矩阵,在节点映射过程中,始终采用贝叶斯网络推理技术选择与已选节点关联最大的节点进行映射。大量的仿真实验结果表明,新提出的虚拟网络映射算法在长期运行过程中具有更好的映射性能。
(四)提出了基于布隆过滤器的分布式映射算法。基于单个基础设施提供商的映射算法大多属于集中式的映射算法,容易产生系统单点故障问题。借助机器学习和推理技术,在没有底层资源更新消息的条件下对资源能力进行评价,并依赖节点的自主映射实现整个虚拟网络的映射。此外,采用布隆过滤器实现底层信息的同步,有效规避了采用洪泛而导致的大量通信开销。最后,将集中式映射算法和分布式映射算法的性能做了对比。仿真实验结果表明,相对于集中式映射算法,分布式映射算法具有可接受、甚至更好的映射性能。
Network virtualization is promoted as a powerful vehicle to solve the ossification of the Internet architecture so that it has attracted increasing attention in both academia and industry. To integrate network virtualization into the future Internet architecture, a big challenge, how to map multiple heterogenous virtual networks onto the shared substrate network, known as virtual network embedding problem, should be solved. Due to multi-dimensional resource constraint, virtual network embedding problem is NP-hard so that its solutions almost rely on heuristic-based algorithms. Our work focuses on improving the performance of virtual network embedding algorithm. Our paper presents the following four major contributions:
(1)A survey of the latest research progress of virtual network embedding algorithm is conducted in detail to divide current virtual network embedding algorithms into two categories, i.e., algorithms based on one infrastructure provider and algorithms based on multiple infrastructure providers. Within an infrastructure provider, virtual network embedding algorithms can be subdivided further in terms of whether the problem space is constrained and the number of mapping stages. Within multiple infrastructure providers, virtual network embedding algorithms can be subdivided according to the relationship among multiple infrastructure providers in the horizontal and vertical dimension. Moreover, this survey sheds light on the potential future research directions in the conclusion.
(2) We propose a hybrid virtual network embedding algorithm with time-oriented scheduling policy. Without reducing any problem space, current virtual network embedding algorithms can be simply classified as one-stage mapping algorithm and two-stage mapping algorithm. However, every coin has two sides. To exploit the respective advantage of the two classes of algorithm, the virtual network is decomposed into core network and edge netwok, while two-stage algorithm and one-stage algorithm are applied in the core network and edge network, respectively. Moreover, a time-oriented scheduling policy is introduced to improve the mapping performance by leveraging the fact that the occupied substrate resource will be released after virtual network departs.
(3) We propose a topology-aware virtual network embedding algorithm based on Bayesian network analysis. Topology-aware virtual network embedding algorithms efficiently improve the performance by leveraging a node ranking method based on Markov random walk model. However, as the basis of node ranking, the resource evaluation of node may be incorrect. Moreover, a greedy matching strategy is always applied in the node mapping stage, which may lead to unnecessary bandwidth consumption by ignoring the relationships between the mapped substrate nodes and the mapping one. Therefore, we rethink the topology-aware virtual network embedding from a statistical perspective. A statistical method is proposed to generate two dependency matrices, respectively representing the importance of every node and the relationships between every two nodes in the substrate network. Based on these dependency matrices, Bayesian network analysis is adapted to iteratively select the substrate node which has the closest relationship with the mapped nodes to achieve node mapping process. Extensive simulations were conducted and the results show that the long-term average performance of our proposed algorithm is better.
(4) We propose a distributed virtual network embedding algorithm based on Bloom filter. Current solutions are almost provided in a centralized way within an infrastructure provider, which may have hot spot problem. In this paper, by leveraging the learning and inference technology, a novel resource evaluation method is proposed without the updated message in the substrate network and virtual network is mapped in a peer-to-peer way according to its own resource evaluating table. Moreover, instead of flooding which generates massive communication overhead, Bloom filter is introduced to synchronize the mapping information. Finally, explicit comparisons between the centralized algorithms and our distributed algorithm are conducted for the first time and the results show that our proposed algorithm has acceptable, even better performance in terms of long-term average revenue and long-term average acceptance ratio.
引文
网络虚拟化环境中的虚拟网络嵌套映射算法[J].软件学报,2012年第11期.
* Hybrid Virtual Network Embedding with K-core Decomposition and Time-oriented Priority [C]. In Proceedings of IEEE International Conference on Communications(ICC 2012), Ottawa, Canada,2012:2695-2699.
* Topology-aware Virtual Network Embedding through Bayesian Network Analysis [C]. In Proceedings of IEEE Global Telecommunications Conference (GLOBECOM 2012), California, USA,2012:2645-2651.
* P2PVNE:A Peer-to-Peer Mapping Approach to Virtual Network Embedding with Bloom Filter [J]. Peer-to-Peer Networking and Applications,2013.
[1]Leiner B M, Cerf V G, Clark D D, et al. A brief history of the Internet [J]. Contributions in Librarianship and Information Science,2001,96:3-24.
[2]Armbrust M, Fox A, Griffith R, et al. A view of cloud computing [J]. Communications of the ACM,2010,53(4):50-58.
[3]Atzori L, Iera A, Morabito G. The internet of things:A survey [J]. Computer Networks, 2010,54(15):2787-2805.
[4]McKeown N, Anderson T, Balakrishnan H, et al. OpenFlow:enabling innovation in campus networks [J]. ACM SIGCOMM Computer Communication Review,2008,38 (2): 69-74.
[5]Programmable Open Mobile Internet.http://cleanslate.stanford.edu/pomi-overview.ppt.
[6]How Mobile Disrupts Social as we know it. http://mobisocial.stanford.edu/papers/iui 13-keynote.pdf.
[7]Stanford Experimental Data Center Laboratory. http://simula.stanford.edu/sedcl/files/sedcl-overview.pdf.
[8]McKeown N.Software-defined networking [J].INFOCOM keynote talk, Apr,2009.
[9]Turner J S, Taylor D E. Diversifying the internet [C]. In Proceedings of the 2005 Global Telecommunications Conference, GLOBECOM'05.2005,2:754-760.
[10]Anderson T, Peterson L, Shenker S, et al. Overcoming the Internet impasse through virtualization [J]. Computer,2005,38 (4):34-41.
[11]Ruth P, Jiang X, Xu D, et al. Virtual distributed environments in a shared infrastructure [J]. Computer,2005,38 (5):63-69.
[12]Bavier A, Feamster N, Huang M, et al. In VINI veritas:realistic and controlled network experimentation [J]. ACM SIGCOMM Computer Communication Review,2006,36(4): 3-14.
[13]WangY, Keller E, Biskeborn B, et al. Virtual routers on the move:live router migration as a network management primitive [J]. ACM SIGCOMM Computer Communication Review,2008,38 (4):231-242.
[14]Bhatia S, Motiwala M, Muhlbauer W, et al. Trellis:A platform for building flexible, fast virtual networks on commodity hardware [C]. In Proceedings of the 2008 ACM CoNEXT Conference,2008:72.
[15]CLEAN SLATE, http://cleanslate.stanford.edu.
[16]GENI.http://www.geni.net.
[17]VINI.http://www.vini-veritas.net.
[18]PlanetLab. http://www.planet-lab.org.
[19]CABO.http://www.cs.princeton.edu/-irex/virtual.html.
[20]4WARD.http://www.4ward-project.eu.
[21]TRILOGY.http://www.trilogy-project.org
[22]UCLP.http://www.uclp.ca.
[23]Nouveau.http://netlab.cs.uwaterloo.ca/virtual.
[24]AKARI.http://akari-project.nict.go.jp.
[25]Lua E K, Crowcroft J, Pias M, et al. A survey and comparison of peer-to-peer overlay network schemes [J]. IEEE Communications Surveys and Tutorials,2005,7 (2):72-93.
[26]Chan K K, Hartmann PW, Lamons S P, et al. Virtual local area network.1989. US Patent 4,823,338.
[27]Scott C, Wolfe P, Erwin M. Virtual private networks [M]. O'Reilly Media, Inc.,1999.
[28]Tennenhouse D L, Smith J M, Sincoskie W D, et al. A survey of active network research [J]. Communications Magazine,1997,35 (1):80-86.
[29]Andersen D, Balakrishnan H, Kaashoek F, et al. Resilient overlay networks [M]. ACM, 2001.
[30]Jannotti J, Gifford D K, Johnson K L, et al. Overcast:reliable multicasting with on overlay network [C]. In Proceedings of the 4th conference on Symposium on Operating System Design and Implementation,2000:14-24.
[31]Li Z, Mohapatra P. QRON:QoS-aware routing in overlay networks [J]. IEEE Journal on Selected Areas in Communications,2004,22 (1):29-40.
[32]Stone R, et al. CenterTrack:An IP overlay network for tracking DoS floods [C]. In Proceedings of the 9th USENIX Security Symposium,2000:199-212.
[33]Byers J, Considine J, Mitzenmacher M, et al. Informed content delivery across adaptive overlay networks [J],2002,32 (4):47-60.
[34]Mahalingam M, Dutt D, Duda K, et al. VXLAN:A framework for overlaying virtualized layer 2 networks over layer 3 networks [J]. draftmahalingam-dutt-dcops-vxlan-01.txt, 2012.
[35]Generic routing encapsulation over IPv4 networks.1994. http://tools.ietf.org/html/rfc1702.
[36]Hoelzle U. Openflow@ google [J]. Open Networking Summit,2012.
[37]Cormen T H, Leiserson C E, Rivest R L, et al. Introduction to algorithms [M]. MIT press, 2001.
[38]Cook S A. The complexity of theorem-proving procedures [C].In Proceedings of the third annual ACM symposium on Theory of computing,1971:151-158.
[39]West D B, et al. Introduction to graph theory[M]. Prentice hall Englewood Cliffs,2001.
[40]Lawler E L, Lenstra J K, Kan A R, et al. The traveling salesman problem:a guided tour of combinatorial optimization [M]. Wiley Chichester,1985.
[41]Leighton T, Makedon F, Tragoudas S.Approximation algorithms for VLSI partition problems [C]. In Proceedings of IEEE International Symposium on Circuits and Systems. 1990:2865-2868.
[42]Andersen D G. Theoretical approaches to node assignment [J]. Computer Science Department,2002:86.
[43]雷德明.多目标智能优化算法及其应用[M].科学出版社,2009.
[44]David Goldberg, John Holland. Genetic algorithms and machine learning [J], Machine learning,1989,3(2):95-99.
[45]Van Laarhoven P J, Aarts E H.Simulated annealing [M].Springer,1987.
[46]Hagan M T, Demuth H B, Beale M H, et al. Neural network design [M]. Pws Pub. Boston London,1996.
[47]Glover F, Laguna M, et al. Tabu search [M]. Springer,1997.
[48]Zitzler E, Thiele L, Zitzler E, et al. An evolutionary algorithm for multiobjective optimization:The strength pareto approach [M]. Citeseer,1998.
[49]Dorigo M, Caro G D, Gambardella L M. Ant algorithms for discrete optimization [J]. Artificial life,1999,5 (2):137-172.
[50]Hogg Tad, Portnov Dmitriy. Quantum optimization [J]. Information Sciences,2000,128 (3):181-197.
[51]Motiwala M, Elmore M, Feamster N, et al. Path splicing [J]. ACM SIGCOMM Computer Communication Review,2008,38 (4):27-38.
[52]Liao J, Wang J, Li T, et al. Introducing multipath selection for concurrent multipath transfer in the future internet [J]. Computer networks,2011,55 (4):1024-1035.
[53]Lu J, Turner J. Efficient mapping of virtual networks onto a shared substrate [J]. Washington University in St. Louis,Tech. Rep,2006.
[54]Fan J,Ammar M H. Dynamic topology configuration in service overlay networks:A study of reconfiguration policies [C]. In Proceedings of IEEE INFOCOM,2006.
[55]Zhu Y, Ammar M. Algorithms for assigning substrate network resources to virtual network components [C]. In Proceeding of IEEE INFOCOM,2006:1-12.
[56]Yu M, Yi Y, Rexford J, et al. Rethinking virtual network embedding:substrate support for path splitting and migration [J]. ACM SIGCOMM Computer Communication Review, 2008,38(2):17-29.
[57]Chowdhury N M K, Rahman M R, Boutaba R. Virtual network embedding with coordinated node and link mapping [C]. In Proceedings of IEEE INFOCOM,2009: 783-791.
[58]Butt N F, Chowdhury M, Boutaba R. Topology-awareness and reoptimization mechanism for virtual network embedding [M]. Springer,2010.
[59]Cheng X, Su S, Zhang Z, et al. Virtual network embedding through topology-aware node ranking [J]. ACM SIGCOMM Computer Communication Review,2011,41 (2):38-47.
[60]Houidi I, LouatiW, Zeghlache D. A distributed virtual network mapping algorithm [C]. In Proceedings of IEEE International Conference on Communications,2008:5634-5640.
[61]Lischka J, Karl H. A virtual network mapping algorithm based on subgraph isomorphism detection [C]. In Proceedings of the 1st ACM workshop on Virtualized infrastructure systems and architectures,2009:81-88.
[62]Cai Z, Liu F, Xiao N, et al. Virtual network embedding for evolving networks [C]. In Proceedings of IEEE Global Telecommunications Conference (GLOBECOM 2010), 2010:1-5.
[63]Kumar A, Rastogi R, Silberschatz A, et al. Algorithms for provisioning virtual private networks in the hose model [J]. IEEE/ACM Transactions on Networking,2002,10 (4): 565-578.
[64]Duffield N G, Goyal P, Greenberg A, et al. Resource management with hoses: point-to-cloud services for virtual private networks [J]. IEEE/ACM Transactions on Networking,2002,10 (5):679-692.
[65]Ricci R, Alfeld C, Lepreau J. A solver for the network testbed mapping problem [J]. ACM SIGCOMM Computer Communication Review,2003,33 (2):65-81.
[66]Fingerhut J A. Approximation algorithms for configuring nonblocking communication networks [J], Washington University,1994.
[67]Minoux M, Vajda S. Mathematical programming:theory and algorithms [M]. Wiley New York,1986.
[68]Howard R A. Dynamic Programming and Markov Processes [J],1960.
[69]Eppstein D. Finding the k shortest paths [J]. SI AM Journal on computing,1998,28 (2): 652-673.
[70]Ahuja R K, Magnanti T L, Orlin J B. Network flows:theory, algorithms, and applications [J],1993.
[71]Schrijver A. Theory of linear and integer programming [M]. Wiley,1998.
[72]Spitzer F. Principles of random walk [M]. Springer Verlag,2001.
[73]Tesauro G, Chess D M, Walsh W E, et al. A multi-agent systems approach to autonomic computing [C]. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 1,2004:464-471.
[74]Cordella L P, Foggia P, Sansone C, et al. An improved algorithm for matching large graphs [C]. In Proceedings of 3rd IAPR-TC15 workshop on graph-based representations in pattern recognition,2001:149-159.
[75]Rahman M R. Mechanism design for network virtualization [R].2010.
[76]Zaheer F-E, Xiao J, Boutaba R. Multi-provider service negotiation and contracting in network virtualization [C]. In Proceedings of IEEE Network Operations and Management Symposium (NOMS),2010:471-478.
[77]Chowdhury M, Samuel F, Boutaba R. Polyvine:policy-based virtual network embedding across multiple domains [C]. In Proceedings of the second ACM SIGCOMM workshop on Virtualized infrastructure systems and architectures,2010:49-56.
[78]Nisan N, Roughgarden T, Tardos E, et al. Algorithmic game theory [M]. Cambridge University Press,2007.
[79]Groves T. Incentives in teams [J]. Econometrica:Journal of the Econometric Society, 1973:617-631.
[80]Goldschmidt O, Hochbaum D S. A polynomial algorithm for the k-cut problem for fixed k [J]. Mathematics of operations research,1994,19(1):24-37.
[81]Kondrak G, Van Beek P. A theoretical evaluation of selected backtracking algorithms [J]. Artificial Intelligence,1997,89 (1):365-387.
[82]Bondy J A, Murty U S R. Graph theory with applications [M]. Macmillan London,1976.
[83]Dorogovtsev S N, Goltsev A, Mendes J F F. K-core organization of complex networks [J]. Physical review letters,2006,96 (4):040601.
[84]Alvarez-Hamelin J I, Dall Asta L, Barrat A, et al. Large scale networks fingerprinting and visualization using the k-core decomposition [J]. Advances in neural information processing systems,2006,18:41.
[85]Andrews M. Probabilistic end-to-end delay bounds for earliest deadline first scheduling [C]. In Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies,2000:603-612.
[86]Kargahi M, Movaghar A. A method for performance analysis of earliest-deadline-first scheduling policy [J]. The Journal of Supercomputing,2006,37 (2):197-222.
[87]Calvert K L, Doar M B, Zegura E W. Modeling internet topology [J]. Communications Magazine, IEEE,1997,35 (6):160-163.
[88]Even S. Graph algorithms [M]. Cambridge University Press,2011.
[89]Naimzada A K, Stefani S, Torriero A. Networks.topology and dynamics:theory and applications to economics and social systems [M]. Springer,2009.
[90]Michalski R S, Carbonell J G, Mitchell T M. Machine learning:An artificial intelligence approach [M]. Morgan Kaufmann,1986.
[91]Andrieu C, De Freitas N, Doucet A, et al. An introduction to MCMC for machine learning [J]. Machine learning,2003,50 (1-2):5-43.
[92]Han J, Kamber M, Pei J. Data mining:concepts and techniques [M]. Morgan kaufmann, 2006.
[93]Neapolitan R E. Learning bayesian networks [M]. Pearson Prentice Hall Upper Saddle River,2004.
[94]Smets P. The degree of belief in a fuzzy event [J]. Information sciences,1981,25 (1): 1-19.
[95]Kahneman D, Tversky A. Subjective probability:A judgment of representativeness [J]. Cognitive psychology,1972,3 (3):430-454.
[96]Koller D, Friedman N. Probabilistic graphical models:principles and techniques [M]. MIT press,2009.
[97]Erlebach T, Mereu A. Path splicing with guaranteed fault tolerance [C]. In Proceedings of IEEE Global Telecommunications Conference,2009:1-6.
[98]Iyengar J R, Amer P D, Stewart R. Concurrent multipath transfer using SCTP multihoming over independent end-to-end paths [J]. IEEE/ACM Transactions on Networking,2006,14 (5):951-964.
[99]Rahman M R, Aib I, Boutaba R. Survivable virtual network embedding [C]. In Proceedings of IFIP NETWORKING 2010,2010:40-52.
[100]Yu H, Qiao C, Anand V, et al. Survivable virtual infrastructure mapping in a federated computing and networking system under single regional failures [C]. In Proceedings of IEEE Global Telecommunications Conference (GLOBECOM),2010:1-6.
[101]Chen Y, Li J, Wo T, et al. Resilient virtual network service provision in network virtualization environments [C]. In Proceedings of 2010 IEEE 16th International Conference on Parallel and Distributed Systems (ICPADS),2010:51-58.
[102]Yu H, Anand V, Qiao C,et al. Cost efficient design of survivable virtual infrastructure to recover from facility node failures [C].In Proceedings of 2011 IEEE International Conference on Communications (ICC),2011:1-6.
[103]Guo T, Wang N, Moessner K, et al. Shared backup network provision for virtual network embedding [C]. In Proceedings of 2011 IEEE International Conference on Communications (ICC),2011:1-5.
[104]Lin M-J, Marzullo K, Masini S. Gossip versus deterministic flooding:Low message overhead and high reliability for broadcasting on small networks [M]. Department of Computer Science and Engineering, University of California, San Diego,1999.
[105]Bishop C M, et al. Pattern recognition and machine learning [M].Springer New York, 2006.
[106]Bloom B H. Space/time trade-offs in hash coding with allowable errors [J]. Communications of the ACM,1970,13 (7):422-426.
[107]Mullin J K. A second look at Bloom filters [J]. Communications of the ACM,1983,26 (8):570-571.
[108]Broder A, Mitzenmacher M. Network applications of bloom filters:A survey [J]. Internet Mathematics,2004,1 (4):485-509.
[109]Qing S, Qi Q, Wang J, et al. Topology-aware Virtual Network Embedding through Bayesian Network Analysis [C]. In Proceedings of 2012 IEEE Global Telecommunications Conference (GLOBECOM),2012:2621-2627.
[110]Lam X N, Vu T, Le T D, et al. Addressing cold-start problem in recommendation systems [C]. In Proceedings of the 2nd international conference on Ubiquitous information management and communication,2008:208-211.
[111]Neyman J. Frequentist probability and frequentist statistics [J]. Synthese,1977,36 (1): 97-131.
[112]Maurer W D, Lewis T G. Hash table methods [J]. ACM Computing Surveys (CSUR), 1975,7(1):5-19.
[113]Bose P, Guo H, Kranakis E, et al. On the false-positive rate of Bloom filters [J]. Information Processing Letters,2008,108 (4):210-213.
[114]Narvaez P, Siu K-Y, Tzeng H-Y. New dynamic algorithms for shortest path tree computation [J]. IEEE/ACM Transactions on Networking (TON),2000,8 (6):734-746.
[115]Awerbuch B, Bar-Noy A, Gopal M. Approximate distributed bellman-ford algorithms [J]. IEEE Transactions on Communications,1994,42 (8):2515-2517.
[116]Qing S, Liao J, Wang J, et al. Hybrid virtual network embedding with K-core decomposition and time-oriented priority [C]. In Proceedings of 2012 IEEE International Conference on Communications (ICC),2012:2695-2699.
[117]杨义先,钮心忻.应用密码学[M].北京邮电大学出版社,2005.
[118]Stoica I, Morris R, Karger D, et al. Chord:A scalable peer-to-peer lookup service for internet applications [J]. ACM SIGCOMM Computer Communication Review,2001,31 (4):149-160.
[119]Mu'alem A W, Feitelson D G. Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling [J]. Parallel and Distributed Systems, IEEE Transactions on,2001,12 (6):529-543.
[120]Shreedhar M, Varghese G. Efficient fair queuing using deficit round-robin [J]. IEEE/ACM Transactions on Networking,1996,4 (3):375-385.
[121]Capone A, Elias J, Martignon F. Routing and resource optimization in service overlay networks [J]. Computer Networks,2009,53 (2):180-190.
[122]Bienkowski M, Feldmann A, Jurca D, et al. Competitive analysis for service migration in vnets [C]. In Proceedings of the second ACM SIGCOMM workshop on Virtualized infrastructure systems and architectures,2010:17-24.