高效可靠的虚拟网络映射技术研究
|
摘要
互联网在经济发展、社会进步、人民生活水平提高等方面发挥着越来越重要的作用,已经成为现代社会最重要的基础设施之一。网络虚拟化允许在共享的底层物理网络基础设施之上共存多重异构的虚拟网络,使在不影响现有网络服务的前提下部署新的网络架构、协议以及应用成为可能,从而有效地支持网络技术创新。网络虚拟化提供了一条由当前互联网向未来网络演进的可行途径,是未来互联网应具备的关键特性。
虚拟网络映射问题是网络虚拟化面临的主要挑战之一,已经成为网络虚拟化研究领域的热点问题,受到了学术界和工业界的普遍关注。虽然目前已经有多种虚拟网络映射算法被提出,但现有研究成果仍然存在以下几个方面的问题：(1)虚拟网络映射成功率低；(2)底层网络的资源利用效用差；(3)虚拟网络服务可靠性差。因此,针对上述问题,本文对虚拟网络映射问题进行了深入研究,并取得如下成果：
(1)针对虚拟网络映射成功率低的问题,提出了一种新颖的拓扑感知的节点资源度量方法。该度量方法的特点在于它不仪能够反映网络节点的资源能力,而且还能够反映其周围网络节点的资源能力,从而为虚拟网络映射方案的构造提供更加全面的启发式信息。基于拓扑感知的节点资源度量方法,提出了虚拟节点优先映射以及虚拟节点和虚拟链路同时映射的两种新的虚拟网络映射算法。实验结果表明,基于拓扑感知节点资源度量方法设计的虚拟网络映射算法可以有效地提高虚拟网络映射的成功率
(2)针对底层网络资源利用效用低的问题,以降低虚拟网络映射的底层网络资源开销为目标,建立了虚拟网络映射问题的整数规划模型。为了求解该模型,提出了一种新的基于粒子群优化的虚拟网络映射算法。实验结果表明,基于元启发式优化技术的虚拟网络映射算法具有执行速度快,求解质量高等特点,并可以有效提高底层网络资源的利用效用。
(3)针对虚拟网络服务可靠性差的问题,首次提出了虚拟网络映射的路由可生存性问题,并建立了该问题的数学模型。为了求解该模型,提出了一种割集感知的虚拟网络映射算法。实验结果表明,割集感知的虚拟网络映射算法可以有效地构造路由可生存的虚拟网络映射方案。路由可生存的虚拟网络映射为被映射的虚拟网络提供了一种新的轻量级的可靠性保障手段,补充了现有的对虚拟网络映射可靠性的研究。
The Internet plays an increasingly important role in economic development, social progress and improvement of people's living standard, which has become one of the most important infrastructures of modern society. Network virtualization allows multiple heterogeneous virtual networks to coexist over a shared substrate network infrastructure, which enables the deployment of new network architectures, protocols, and applications without affecting the existing network service and thus make network innovations easier. Network virtualization provides a viable way to evolve to the future network, and it also should be the key feature of the future Internet.
Virtual network (VN) embedding is a major challenge faced by network virtualization. It has become a hot research topic and draws more and more attention from both academic and industrial communities. Although a large body of VN embedding algorithms has been proposed, there is still room for improvement in the following three aspects:(1) VN request acceptance ratio;(2) the utilization of the substrate network resources;(3) the reliability of the embedded VNs. Therefore, through in-depth study of the VN embedding problem from these three aspects, we made the following major contributions:
(1) To increase the VN request acceptance ratio, we propose a novel topology-aware node resource ranking measure. Since this measure can reflect not only the resource quality of the node itself but also the resource quality of its neighbors, it provides better heuristic information for the construction of the VN embedding solution. Based on the topology-aware node ranking measure, we propose two new VN embedding algorithms. Both two-stage and one-stage mapping strategies are investigated. The experimental results show that the proposed topology-aware VN embedding algorithms can increase the virtual network acceptance ratio.
(2) Aiming at increasing the utilization of the substrate network resource, we first model the VN embedding problem as an integer linear programming and consider the resource cost of VN request as the fitness function. Then, we propose a new VN embedding algorithm based on particle swarm optimization for solving this problem. The experimental results demonstrate that the proposed meta-heuristic based algorithm can generate near-optimal solution without consuming much running time and thus increase the utilization of the substrate network resource.
(3) To improve the reliability of the embedded VNs, we introduce the survivable routing problem of VN embedding and establish a mathematical model for this problem. To address this problem, we put forward a heuristic algorithm called cut-aware VN embedding. The experimental results show that the proposed cut-aware VN embedding algorithm can effectively obtain the VN embedding solution with survivable routing. VN embedding with survivable routing provides a new and lightweight way to guarantee the reliability of the embedded VNs, which makes a complementary to the previous studies on the reliability of VN embedding.
虚拟网络映射问题是网络虚拟化面临的主要挑战之一,已经成为网络虚拟化研究领域的热点问题,受到了学术界和工业界的普遍关注。虽然目前已经有多种虚拟网络映射算法被提出,但现有研究成果仍然存在以下几个方面的问题：(1)虚拟网络映射成功率低；(2)底层网络的资源利用效用差；(3)虚拟网络服务可靠性差。因此,针对上述问题,本文对虚拟网络映射问题进行了深入研究,并取得如下成果：
(1)针对虚拟网络映射成功率低的问题,提出了一种新颖的拓扑感知的节点资源度量方法。该度量方法的特点在于它不仪能够反映网络节点的资源能力,而且还能够反映其周围网络节点的资源能力,从而为虚拟网络映射方案的构造提供更加全面的启发式信息。基于拓扑感知的节点资源度量方法,提出了虚拟节点优先映射以及虚拟节点和虚拟链路同时映射的两种新的虚拟网络映射算法。实验结果表明,基于拓扑感知节点资源度量方法设计的虚拟网络映射算法可以有效地提高虚拟网络映射的成功率
(2)针对底层网络资源利用效用低的问题,以降低虚拟网络映射的底层网络资源开销为目标,建立了虚拟网络映射问题的整数规划模型。为了求解该模型,提出了一种新的基于粒子群优化的虚拟网络映射算法。实验结果表明,基于元启发式优化技术的虚拟网络映射算法具有执行速度快,求解质量高等特点,并可以有效提高底层网络资源的利用效用。
(3)针对虚拟网络服务可靠性差的问题,首次提出了虚拟网络映射的路由可生存性问题,并建立了该问题的数学模型。为了求解该模型,提出了一种割集感知的虚拟网络映射算法。实验结果表明,割集感知的虚拟网络映射算法可以有效地构造路由可生存的虚拟网络映射方案。路由可生存的虚拟网络映射为被映射的虚拟网络提供了一种新的轻量级的可靠性保障手段,补充了现有的对虚拟网络映射可靠性的研究。
The Internet plays an increasingly important role in economic development, social progress and improvement of people's living standard, which has become one of the most important infrastructures of modern society. Network virtualization allows multiple heterogeneous virtual networks to coexist over a shared substrate network infrastructure, which enables the deployment of new network architectures, protocols, and applications without affecting the existing network service and thus make network innovations easier. Network virtualization provides a viable way to evolve to the future network, and it also should be the key feature of the future Internet.
Virtual network (VN) embedding is a major challenge faced by network virtualization. It has become a hot research topic and draws more and more attention from both academic and industrial communities. Although a large body of VN embedding algorithms has been proposed, there is still room for improvement in the following three aspects:(1) VN request acceptance ratio;(2) the utilization of the substrate network resources;(3) the reliability of the embedded VNs. Therefore, through in-depth study of the VN embedding problem from these three aspects, we made the following major contributions:
(1) To increase the VN request acceptance ratio, we propose a novel topology-aware node resource ranking measure. Since this measure can reflect not only the resource quality of the node itself but also the resource quality of its neighbors, it provides better heuristic information for the construction of the VN embedding solution. Based on the topology-aware node ranking measure, we propose two new VN embedding algorithms. Both two-stage and one-stage mapping strategies are investigated. The experimental results show that the proposed topology-aware VN embedding algorithms can increase the virtual network acceptance ratio.
(2) Aiming at increasing the utilization of the substrate network resource, we first model the VN embedding problem as an integer linear programming and consider the resource cost of VN request as the fitness function. Then, we propose a new VN embedding algorithm based on particle swarm optimization for solving this problem. The experimental results demonstrate that the proposed meta-heuristic based algorithm can generate near-optimal solution without consuming much running time and thus increase the utilization of the substrate network resource.
(3) To improve the reliability of the embedded VNs, we introduce the survivable routing problem of VN embedding and establish a mathematical model for this problem. To address this problem, we put forward a heuristic algorithm called cut-aware VN embedding. The experimental results show that the proposed cut-aware VN embedding algorithm can effectively obtain the VN embedding solution with survivable routing. VN embedding with survivable routing provides a new and lightweight way to guarantee the reliability of the embedded VNs, which makes a complementary to the previous studies on the reliability of VN embedding.
引文
[1]中国互联网信息中心,“第30次中国互联网络发展状况统计报告,”[EB/OL].: http://www.cnnic.cn/hlwfzyj/hlwxzbg/hlwtjbg/201207/P02012072347745120247 4.pdf.
[2]吴建平,刘莹,吴茜,“新一代互联网体系结构理论研究进展,”中国科学：E辑,Vol.38, No.10,2009, pp.1540-1564.
[3]吴建平,吴茜,徐恪,“下一代互联网体系结构基础研究及探索,”计算机学报,Vol.31, No.9,2008, pp.1536-1548.
[4]T. Anderson, L. Peterson, S. Shenker, and J. Turner, "Overcoming the Internet impasse through virtualization," Computer, Vol.38, No.4,2005, pp.34-41.
[5]J. Turner and D. Taylor, "Diversifying the internet," in Proceedings of IEEE GLOBECOM,2005.
[6]D.G. Andersen, H. Balakrishnan, N. Feamster, T. Koponen, D. Moon, and S. Shenker, "Accountable internet protocol (AIP)," in Proceedings of ACM SIGCOMM,2008, pp.339-350.
[7]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, 2007, pp.61-64.
[8]郝甲东,张云飞,魏冰,"PlanetLab综述,”中国通信学会信息通信网络技术委员会2009年年会论文集(上册),Vol.,No.2009.
[9]B. Chun, D. Culler, T. Roscoe, A. Bavier, L. Peterson, M. Wawrzoniak, and M. Bowman, Planetlab:an overlay testbed for broad-coverage services, ACM SIGCOMM Computer Communication Review, Vol.33, No.3,2003, pp.3-12.
[10]Global Environment for Networking Innovation, [EB/OL].: http://www.geni.net.
[11]A. Bavier, N. Feamster, M. Huang, L. Peterson, and J. Rexford, "In VINI veritas: realistic and controlled network experimentation," in Proceedings of ACM SIGCOMM,2006, pp.3-14.
[12]M. Handley, O. Hodson, and E. Kohler, "XORP:An open platform for network research," ACM SIGCOMM Computer Communication Review, Vol.33, No.1, 2003, pp.53-57.
[13]E. Kohler, R. Morris, B. Chen, J. Jannotti, and M.F. Kaashoek, "The Click modular router," ACM Transactions on Computer Systems (TOCS), Vol.18, No. 3,2000, pp.263-297.
[14]N. Feamster and H. Balakrishnan, "Detecting BGP configuration faults with static analysis," in Proceedings of USENIX NSDI 2005, pp.43-56.
[15]C. Wenlong, X. Mingwei, Y. Yang, L. Qi, and M. Dong-Chao, "Virtual network with high performance:VegaNet," Chinese Journal of Computers, Vol.33, No.1, 2010, pp.63-73.
[16]The FP7 4WARD Project, [EB/OL].:www.4ward-project.eu/.
[17]韩言妮,蕈毅芳,慈松,“未来网络虚拟化关键技术研究,”中兴通讯技术,Vol.17, No.2,2011, pp.15-19.
[18]L.E. Li, Z.M. Mao, and J. Rexford, "Toward Software-Defined Cellular Networks," in Proceedings of European Workshop on Software Defined Networking 2012.
[19]C. Guo, G. Lu, H.J. Wang, S. Yang, C. Kong, P. Sun, W. Wu, and Y. Zhang, "Secondnet:a data center network virtualization architecture with bandwidth guarantees," in Proceedings of ACM CONEXT 2010.
[20]TX Matrix Plus Router,, [EB/OL].: http://www.juniper.net/techpubs/en_US/release-independent/junos/information-p roducts/pathway-pages/t-series/.
[21]N. Chowdhury and R. Boutaba, "Network virtualization:state of the art and research challenges," IEEE Communications Magazine, Vol.47, No.7,2009, pp. 20-26.
[22]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,2008, pp.17-29.
[23]N. Chowdhury, M. Rahman, and R. Boutaba, "Virtual network embedding with coordinated node and link mapping," in IEEE INFOCOM,2009, pp.783-791.
[24]W.L. Yeow, C. Westphal, and U. Kozat, "Designing and embedding reliable virtual infrastructures," in the 2st ACM workshop on Virtualized infrastructure systems and architectures,2010, pp.33-40.
[25]Y. Chen, J. Li, T. Wo, C. Hu, and W. Liu, "Resilient Virtual Network Service Provision in Network Virtualization Environments," in IEEE International Conference on Parallel and Distributed Systems,2010, pp.51-58.
[26]J. Kennedy and R. Eberhart, "Particle swarm optimization," in Proceedings of IEEE International Conference on Neural Networks,1995, pp.1942-1948.
[1]V. Rajaravivarma. "Virtual local area network technology and applications," IEEE Transactions on Communications,1997, pp.49-52.
[2]R. Yuan, W.T. Strayer, and T. Strayer, "Virtual private networks:technologies and solutions," Addi son-Wesley,2001.
[3]E.K. Lua, J. Crowcroft, M. Pias, R. Sharma, and S. Lim, "A survey and comparison of peer-to-peer overlay network schemes," IEEE Communications Surveys and Tutorials, Vol.7, No.2,2005, pp.72-93.
[4]N. Chowdhury and R. Boutaba, "Network virtualization:state of the art and research challenges," IEEE Communications Magazine, Vol.47, No.7,2009, pp. 20-26.
[5]F.A. Tobagi and V. Bruce Hunt, "Performance analysis of carrier sense multiple access with collision detection," Computer Networks, Vol.4, No.5,1980, pp. 245-259.
[6]W. Townsley, A. Valencia, A. Rubens, G. Pall, G. Zorn, and B. Palter, "Layer two tunneling protocol (L2TP)," IETF,1999.
[7]W. Simpson, "The point-to-point protocol (PPP)," IETF,1993.
[8]A. Valencia, M. Littlewood, and T. Kolar, "Cisco Layer Two Forwarding Protocol (L2F)," IETF,1998.
[9]K. Hamzeh, G. Pall, W. Verthein, J. Taarud, W. Little, and G. Zorn, "Point-to-point tunneling protocol (PPTP)," IETF,1999.
[10]D. Farinacci, P. Traina, S. Hanks, and T. Li, "Generic routing encapsulation (GRE)," IETF,1994.
[11]N. Doraswamy and D. Harkins, "IPSec:the new security standard for the Internet, intranets, and virtual private networks," Prentice Hall,2003.
[12]E. Rosen, A. Viswanathan, and R. Callon, "Multiprotocol label switching architecturez (MPLS)," IETF,2001.
[13]L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala, "RSVP:A new resource reservation protocol," Network, IEEE, Vol.7, No.5,1993, pp.8-18.
[14]R. Yavatkar, D. Hoffman, Y. Bernet, F. Baker, and M. Speer, "Subnet Bandwidth Manager (SBM):A protocol for RSVP-based admission control over IEEE 802-style networks," IETF,2000.
[15]S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, "An architecture for differentiated services," IETF,1998.
[16]J. Wroclawski, "The use of RSVP with IETF integrated services," IETF,1997.
[17]王肠肠,毕军,吴建平,“互联网覆盖路由技术研究,”Journal of Software, Vol. 20, No.11,2009, pp.2988-3000.
[18]S. Savage, T. Anderson, A. Aggarwal, D. Becker, N. Cardwell, A. Collins, E. Hoffman, J. Snell, A. Vahdat, and G. Voelker, "Detour:Informed Internet routing and transport," IEEE Micro, Vol.19, No.1,1999, pp.50-59.
[19]D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris, "Resilient overlay networks," ACM SIGCOMM Computer Communication Review, Vol.32, No. 1,2002, pp.66-66.
[20]L. Subramanian, I. Stoica, H. Balakrishnan, and R. Katz, "OverQoS:An overlay based architecture for enhancing Internet QoS," in Proceedings of NSDI,2004, pp.6-21.
[21]J. Shamsi and M. Brockmeyer, "QoSMap:QoS aware Mapping of Virtual Networks for Resiliency and Efficiency," in Proceedings of IEEE Globecom Workshops 2007.
[22]Y. Li, Y. Zhang, L.L. Qiu, and S. Lam, "SmartTunnel:Achieving reliability in the internet," in Proceedings of INFOCOM,2007, pp.830-838.
[23]R. Kokku, A. Bohra, S. Ganguly, and A. Venkataramani, "A multipath background network architecture," in Proceedings of INFOCOM,2007, pp. 1352-1360.
[24]S. Banerjee, B. Bhattacharjee, and C. Kommareddy, "Scalable application layer multicast," UM Computer Science Department Technical Report,2002.
[25]S. Saroiu, K.P. Gummadi, R.J. Dunn, S.D. Gribble, and H.M. Levy, "An analysis of internet content delivery systems," in Proceedings of OSDI,2002, pp. 315-328.
[26]B. Chun, D. Culler, T. Roscoe, A. Bavier, L. Peterson, M. Wawrzoniak, and M. Bowman, "Planetlab:an overlay testbed for broad-coverage services," ACM SIGCOMM Computer Communication Review, Vol.33, No.3,2003, pp.3-12.
[27]B. White, J. Lepreau, L. Stoller, R. Ricci, S. Guruprasad, M. Newbold, M. Hibler, C. Barb, and A. Joglekar, "An integrated experimental environment for distributed systems and networks," in Proceedings of OSDI,2002, pp.255-270.
[28]A.D. Keromytis, V. Misra, and D. Rubenstein, "SOS:Secure overlay services," in Proceedings of SIGCOMM,2002, pp.61-72.
[29]D.G. Andersen, "Mayday:Distributed filtering for internet services," in Proceedings of USENIX Symp. Internet Technologies and Systems,2003, pp. 37-39.
[30]M. Hosseini, D.T. Ahmed, S. Shirmohammadi, and N.D. Georganas, "A survey of application-layer multicast protocols," IEEE Communications Surveys & Tutorials, Vol.9, No.3,2007, pp.58-74.
[31]J. Turner and D. Taylor, "Diversifying the internet," in Proceedings of IEEE GLOBECOM,2005.
[32]T. Anderson, L. Peterson, S. Shenker, and J. Turner, "Overcoming the Internet impasse through virtualization," Computer, Vol.38, No.4,2005, pp.34-41.
[33]Global Environment for Networking Innovation, [EB/OL].:http://www.geni.net.
[34]A. Bavier, N. Feamster, M. Huang, L. Peterson, and J. Rexford, "In VINI veritas: realistic and controlled network experimentation," in Proceedings of ACM SIGCOMM,2006, pp.3-14..
[35]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, 2007, pp.61-64.
[36]A. Gavras, A. Karila, S. Fdida, M. May, and M. Potts, "Future internet research and experimentation:the FIRE initiative," ACM SIGCOMM Computer Communication Review, Vol.37, No.3,2007, pp.89-92.
[37]N. Niebert, S. Baucke, I. El-Khayat, M. Johnsson, B. Ohlman, H. Abramowicz, K. Wuenstel, H. Woesner, J. Quittek, and L.M. Correia, "The way 4WARD to the creation of a future Internet," in Proceedings of IEEE PIMRC,2008, pp.1-5.
[38]M. Handley, O. Hodson, and E. Kohler, "XORP:An open platform for network research," ACM SIGCOMM Computer Communication Review, Vol.33, No.1, 2003, pp.53-57.
[39]G. Watson, N. McKeown, and M. Casado, "NetFPGA:A tool for network research and education," in Proceedings of WARFP,2006.
[40]N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, "OpenFlow:enabling innovation in campus networks," ACM SIGCOMM Computer Communication Review, Vol.38, No.2,2008, pp. 69-74.
[41]N. Gude, T. Koponen, J. Pettit, B. Pfaff, M. Casado, N. McKeown, and S. Shenker, "NOX:towards an operating system for networks," ACM SIGCOMM Computer Communication Review, Vol.38, No.3,2008, pp.105-110.
[42]N. Handigol, S. Seetharaman, M. Flajslik, N. McKeown, and R. Johari, "Plug-n-Serve:Load-balancing web traffic using OpenFlow," ACM SIGCOMM Demo,2009.
[43]K.K. Yap, M. Kobayashi, R. Sherwood, T.Y. Huang, M. Chan, N. Handigol, and N. McKeown, "OpenRoads:Empowering research in mobile networks," ACM SIGCOMM Computer Communication Review, Vol.40, No.1,2010, pp. 125-126.
[44]G. Gibb, D. Underhill, A. Covington, T. Yabe, and N. McKeown. "OpenPipes: Prototyping high-speed networking systems," in Proceedings of ACM SIGCOMM Demo,2009.
[45]R. Sherwood, G. Gibb, K. Yap, G. Appenzeller, M. Casado, N. McKeown, and G. Parulkar, "Flowvisor:A network virtualization layer, OpenFlow Switch Consortium," Technical Report,2009.
[46]B. Pfaff, J. Pettit, T. Koponen, K. Amidon, M. Casado, and S. Shenker, "Extending networking into the virtualization layer," in Proceedings of HotNets, 2009.
[47]A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yener, "Provisioning a virtual private network:A network design problem for multicommodity flow," in the thirty-third annual ACM symposium on Theory of computing,2001, pp. 389-398.
[48]A. Haque and P. Ho, "Design of survivable optical virtual private networks (O-VPNs)," Network, Vol.1, No.3, pp.4.
[49]W. Szeto, Y. Iraqi, and R. Boutaba, "A multi-commodity flow based approach to virtual network resource allocation," in Proceedings of IEEE GLOBECOM, 2004.
[50]Q. Fang, J. Cobb, and E. Leiss, "A pre-selection routing scheme for virtual circuit networks," 1999.
[51]R. Ricci, C. Alfeld, and J. Lepreau, "A solver for the network testbed mapping problem," ACM SIGCOMM Computer Communication Review, Vol.33, No.2, 2003, pp.81.
[52]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,2008, pp.17-29.
[53]N. Chowdhury, M. Rahman, and R. Boutaba, "Virtual network embedding with coordinated node and link mapping," in Proceedings of IEEE INFOCOM, 2009, pp.783-791.
[54]J. Lischka and H. Karl, "A virtual network mapping algorithm based on subgraph isomorphism detection," in the 1st ACM workshop on Virtualized infrastructure systems and architectures,2009, pp.81-88.
[55]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, Vol.35, No.2006.
[56]Y. Zhu and M. Ammar, "Algorithms for assigning substrate network resources to virtual network components," in Proceedings of IEEE INFOCOM,2006,
[57]J. He, R. Zhang-Shen, Y. Li, C. Lee, J. Rexford, and M. Chiang, "Davinci: Dynamically adaptive virtual networks for a customized internet," in Proceedings of ACM CoNEXT,2008, pp.1-12.
[58]I. Houidi, W. Louati, and D. Zeghlache, "A distributed virtual network mapping algorithm," in Proceedings of IEEE ICC,2008, pp.5634-5640.
[59]Y. Chen, J. Li, T. Wo, C. Hu, and W. Liu, "Resilient Virtual Network Service Provision in Network Virtualization Environments," in Proceedings of IEEE International Conference on Parallel and Distributed Systems,2010, pp.51-58.
[60]D. Eppstein, "Finding the k shortest paths," 1994.
[61]R. Ahuja, T. Magnanti, and J. Orlin, "Network flows:theory, algorithms, and applications," Prentice-Hall,1993.
[62]L. Cordella, P. Foggia, C. Sansone, and M. Vento, "An improved algorithm for matching large graphs," 2001.
[63]J. Holland, "Adaptation in natural and artificial systems," MIT Press Cambridge, MA, USA,1992.
[1]G.H. Weiss and R.J. Rubin, "Random walks:theory and selected applications," Advances in Chemical Physics, Volume 52, Vol., No.2007, pp.363-505.
[2]N. Chowdhury and R. Boutaba, "Network virtualization:state of the art and research challenges," IEEE Communications Magazine, Vol.47, No.7,2009, pp. 20-26.
[3]N. Chowdhury and R. Boutaba, "A survey of network virtualization," Computer Networks, Vol.54, No.5,2010, pp.862-876.
[4]D. Andersen, "Theoretical approaches to node assignment," Unpublished Manuscript,2002.
[5]J. Lischka and H. Karl, "A virtual network mapping algorithm based on subgraph isomorphism detection," in the 1st ACM workshop on Virtualized infrastructure systems and architectures,2009, pp.81-88.
[6]L. Cordella, P. Foggia, C. Sansone, and M. Vento, "An improved algorithm for matching large graphs," 2001, pp.149-159.
[7]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,2008, pp.17-29.
[8]W. Szeto, Y. Iraqi, and R. Boutaba, "A multi-commodity flow based approach to virtual network resource allocation," in Proceedings of IEEE GLOBECOM, 2004.
[9]J. Dean and S. Ghemawat, "MapReduce:simplified data processing on large clusters," Communications of the ACM, Vol.51, No.1,2008, pp.107-113.
[10]X. Meng, V. Pappas, and L. Zhang, "Improving the scalability of data center networks with traffic-aware virtual machine placement," in Proceedings of INFOCOM,2010.
[11]J.T. Piao and J. Yan, "A network-aware virtual machine placement and migration approach in cloud computing," in Proceedings of GCC,2010, pp.87-92.
[12]G. Lee, N. Tolia, P. Ranganathan, and R.H. Katz, "Topology-aware resource allocation for data-intensive workloads," in Proceedings of the first ACM asia-pacific workshop on systems,2010.
[13]B. Palanisamy, A. Singh, L. Liu, and B. Jain, "Purlieus:locality-aware resource allocation for MapReduce in a cloud," in Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, 2011.
[14]M. Cardosa, M.R. Korupolu, and A. Singh, "Shares and utilities based power consolidation in virtualized server environments," in Proceedings of Integrated Network Management,2009, pp.327-334.
[15]A. Verma, G. Dasgupta, T.K. Nayak, P. De, and R. Kothari, "Server workload analysis for power minimization using consolidation," in Proceedings of the USENIX Annual technical conference,2009, pp.28-28.
[16]N. Bobroff, A. Kochut, and K. Beaty, "Dynamic placement of virtual machines for managing sla violations," in Proceedings of Integrated Network Management, 2007, pp.119-128.
[17]N. Farooq Butt, M. Chowdhury, and R. Boutaba, "Topology-awareness and reoptimization mechanism for virtual network embedding," in Proceedings of IFIP NETWORKING,2010, pp.27-39.
[18]Y. Wang, E. Keller, B. Biskeborn, J. van der Merwe, and J. Rexford, "Virtual routers on the move:live router migration as a network-management primitive,' ACM SIGCOMM Computer Communication Review, Vol.38, No.4.2008, pp. 231-242.
[19]P. Pisa, N. Fernandes, H. Carvalho, M. Moreira, M. Campista, L. Costa, and O. Duarte, "Openflow and Xen-based virtual network migration. Communications: Wireless in Developing Countries and Networks of the Future," 2010, pp. 170-181.
[20]L. Page, S. Brin, R. Motwani, and T. Winograd, "The PageRank citation ranking: bringing order to the web," 1999.
[21]M. Diligenti. M. Gori, and M. Maggini, "A unified probabilistic framework for web page scoring systems," IEEE Transactions on Knowledge and Data Engineering, Vol.16, No.1,2004, pp.4-16.
[22]M. Gori, M. Maggini. and L. Sarti. "Exact and approximate graph matching using random walks," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.27, No.7.2005. pp.1100-1111.
[23]E. Seneta, "Non-negative Matrices and Markov Chains," Springer,1981.
[24]M. Bianchini, M. Gori, and F. Scarselli, "Inside pagerank," ACM Transactions on Internet Technology (TOIT), Vol.5, No.1,2005, pp.92-128.
[25]N. Chowdhury, M. Rahman, and R. Boutaba, "Virtual network embedding with coordinated node and link mapping," in Proceedings of IEEE INFOCOM,2009, pp.783-791.
[1]N. Chowdhury and R. Boutaba, "Network virtualization:state of the art and research challenges," IEEE Communications Magazine, Vol.47, No.7,2009, pp. 20-26.
[2]N. Chowdhury, M. Rahman, and R. Boutaba, "Virtual network embedding with coordinated node and link mapping," in Proceedings of IEEE INFOCOM,2009, pp.783-791.
[3]X. Cheng, S. Su, Z. Zhang, H. Wang, F. Yang, Y. Luo, and J. Wang, "Virtual Network Embedding Through Topology-Aware Node Ranking," ACM SIGCOMM Computer Communication Review, Vol.41, No.2,2011, pp.39-47.
[4]J. Lischka and H. Karl, "A virtual network mapping algorithm based on subgraph isomorphism detection," in the 1st ACM workshop on Virtualized infrastructure systems and architectures,2009, pp.81-88.
[5]J. Shamsi and M. Brockmeyer, "QoSMap:QoS aware Mapping of Virtual Networks for Resiliency and Efficiency," in Proceedings of IEEE Globecom Workshops 2007.
[6]Y. Zhu and M. Ammar, "Algorithms for assigning substrate network resources to virtual network components," in Proceedings of IEEE INFOCOM,2006.
[7]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, Vol.35, No.2006.
[8]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,2008, pp.17-29.
[9]Y. Chen, J. Li, T. Wo, C. Hu, and W. Liu, "Resilient Virtual Network Service Provision in Network Virtualization Environments," in Proceedings of IEEE International Conference on Parallel and Distributed Systems,2010, pp.51-58.
[10]I. Houidi, W. Louati, W. Ben Ameur, and D. Zeghlache, "Virtual network provisioning across multiple substrate networks," Computer Networks, Vol.55, No.4,2011, pp.1011-1023.
[11]I. Houidi, W. Louati, D. Zeghlache, and S. Baucke, "Virtual resource description and clustering for virtual network discovery," in Proceedings of IEEE ICC Workshops,2009.
[12]A. Schrijver, "Theory of linear and integer programming," Wiley,1986.
[13]E.L. Lawler and D.E. Wood, "Branch-and-bound methods:A survey, Operations research," Vol.14, No.4,1966, pp.699-719.
[14]J.E. Kelley Jr, The cutting-plane method for solving convex programs, "Journal of the Society for Industrial & Applied Mathematics," Vol.8, No.4,1960, pp. 703-712.
[15]J. Holland, "Adaptation in natural and artificial systems," MIT Press Cambridge, MA, USA,1992.
[16]S. Kirkpatrick Jr, CD Gelatt, and MP Vecchi, "Optimization by simulated annealing," Science, Vol.220, No.4598,1983, pp.671-680.
[17]J.H. Kim and H. Myung, "Evolutionary programming techniques for constrained optimization problems," IEEE Transactions on Evolutionary Computation, Vol.1, No.2,1997, pp.129-140.
[18]J. Kennedy and R. Eberhart, "Particle swarm optimization," 1995, pp. 1942-1948.
[19]Y. Shi, "Particle swarm optimization:developments, applications and resources," in Proceedings of Evolutionary Computation,2001, pp.81-86.
[20]G. Klir and B. Yuan, "Fuzzy sets and fuzzy logic:theory and applications," Prentice Hall PTR Upper Saddle River, NJ, USA,1995.
[21]S. Savage, T. Anderson, A. Aggarwal, D. Becker, N. Cardwell, A. Collins, E. Hoffman, J. Snell, A. Vahdat, and G. Voelker, "Detour:Informed Internet routing and transport," IEEE Micro, Vol.19, No.1,1999, pp.50-59.
[22]J. Kennedy and R.C. Eberhart, "A discrete binary version of the particle swarm algorithm," in Proceedings of IEEE International Conference on Systems, Man, and Cybernetics,1997, pp.4104-4108.
[23]M. Clerc, "Discrete particle swarm optimization illustrated by the traveling salesman problem," New optimization techniques in engineering, Vol.141, No. 2004, pp.219-239.
[24]R. Poli, J. Kennedy, and T. Blackwell, "Particle swarm optimization, Swarm intelligence," Vol.1, No.1,2007, pp.33-57.
[25]X. Zhao, X.S. Gao, and Z.C. Hu, "Evolutionary programming based on non-uniform mutation," Applied Mathematics and Computation, Vol.192, No. 1,2007, pp.1-11.
[26]N. Higashi and H. Iba, "Particle swarm optimization with Gaussian mutation," in Swarm Intelligence Symposium,2003, pp.72-79.
[27]N. Farooq Butt, M. Chowdhury, and R. Boutaba, "Topology-awareness and reoptimization mechanism for virtual network embedding," in Proceedings of IFIP NETWORKING,2010, pp.27-39.
[1]X. Cheng, S. Su, Z. Zhang, H. Wang, F. Yang, Y. Luo, and J. Wang, "Virtual Network Embedding Through Topology-Aware Node Ranking," ACM SIGCOMM Computer Communication Review, Vol.41, No.2,2011, pp.39-47.
[2]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,2008, pp.17-29.
[3]X. Cheng, Z.B. Zhang, S. Su, and F.C. Yang, "Virtual network embedding based on particle swarm optimization," Acta Electronica Sinica, Vol.39, No.10,2011, pp.2240-2244.
[4]N. Chowdhury, M. Rahman, and R. Boutaba, "Virtual network embedding with coordinated node and link mapping," in Proceedings of IEEE INFOCOM,2009, pp.783-791.
[5]N. Chowdhury and R. Boutaba, "A survey of network virtualization," Computer Networks, Vol.54, No.5,2010, pp.862-876.
[6]G. Koslovski, W.L. Yeow, C. Westphal, T.T. Huu, J. Montagnat, and P. Vicat-Blanc, "Reliability support in virtual infrastructures," in Proceedings of IEEE CloudCom,2010, pp.49-58.
[7]T. Guo, N. Wang, K. Moessner, and R. Tafazolli, "Shared Backup Network Provision for Virtual Network Embedding," in Proceedings of IEEE ICC,2011, pp.1-5.
[8]M. Motiwala, M. Elmore, N. Feamster, and S. Vempala, "Path splicing," ACM SIGCOMM Computer Communication Review, Vol.38, No.4,2008, pp.27-38.
[9]J. Shamsi and M. Brockmeyer, "QoSMap:QoS aware Mapping of Virtual Networks for Resiliency and Efficiency," in Proceedings of IEEE Globecom Workshops 2007.
[10]D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris, "Resilient overlay networks," ACM SIGCOMM Computer Communication Review, Vol.32, No.1, 2002, pp.66-66.
[11]M. Rahman, I. Aib, and R. Boutaba, "Survivable Virtual Network Embedding, " in Proceedings of IFIP NETWORKING,2010, pp.40-52.
[12]Y. Chen, J. Li, T. Wo, C. Hu, and W. Liu, "Resilient Virtual Network Service Provision in Network Virtualization Environments," in Proceedings of IEEE International Conference on Parallel and Distributed Systems,2010, pp.51-58.
[13]W.L. Yeow, C. Westphal, and U. Kozat, "Designing and embedding reliable virtual infrastructures," in the 2st ACM workshop on Virtualized infrastructure systems and architectures,2010, pp.33-40.
[14]W. Cui, I. Stoica, and R.H. Katz, "Backup path allocation based on a correlated link failure probability model in overlay networks," in Proceedings of IEEE Network Protocols,2002, pp.236-245.
[15]W. Lau and S. Jha, "Failure-oriented path restoration algorithm for survivable networks," IEEE Transactions on Network and Service Management, Vol.1, No. 1,2004, pp.11-20.
[16]Y. Liu, D. Tipper, and P. Siripongwutikorn, "Approximating optimal spare capacity allocation by successive survivable routing," in Proceedings of INFOCOM,2001, pp.699-708.
[17]R. Ramaswami and K. Sivarajan, "Routing and wavelength assignment in all-optical networks," IEEE/ACM Transactions on Networking, Vol.3, No.5, 1995, pp.489-500.
[18]E. Modiano and A. Narula-Tam, "Survivable routing of logical topologies-in WDM networks," in Proceedings of IEEE INFOCOM,2001, pp.348-357.
[19]M. Kurant and P. Thiran, "Survivable routing of mesh topologies in IP-over-WDM networks by recursive graph contraction," IEEE Journal on Selected Areas in Communications, Vol.25, No.5,2007, pp.922-933.
[20]P.H. Ho, J. Tapolcai, and H.T. Mouftah, "On achieving optimal survivable routing for shared protection in survivable next-generation internet," IEEE Transactions on Reliability, Vol.53, No.2,2004, pp.216-225.
[21]A. Haque and P. Ho, "Design of survivable optical virtual private networks (O-VPNs)," Network, Vol.1, No.3, pp.4.
[22]R.M. Karp, "On the Computational Complexity of Combinatorial Problems," Networks, Vol.5, No.175, pp.45-68.
[23]X. Cheng, S. Su, Z. Zhang, K. Shuang, F. Yang, Y. Luo, and J. Wang, "Virtual network embedding through topology awareness and optimization," Computer Networks,2012.
[24]S. Tsukiyama, I. Shirakawa, H. Ozaki, and H. Ariyoshi, "An algorithm to enumerate all cutsets of a graph in linear time per cutset," Journal of the ACM, Vol.27, No.4,1980, pp.619-632.
[1]B. Augustin, X. Cuvellier, B. Orgogozo, F. Viger, T. Friedman, M. Latapy, C. Magnien, and R. Teixeira, "Avoiding traceroute anomalies with Paris traceroute," in Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, 2006, pp.153-158.
[2]A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford, "NetScope: Traffic engineering for IP networks," IEEE Network, Vol.14, No.2,2000, pp. 11-19.
[3]J. He and J. Rexford, "Toward internet-wide multipath routing," Network, IEEE, Vol.22, No.2,2008, pp.16-21.
[4]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,2008, pp.17-29.
[5]B.G. Chun, G. Iannaccone, R. Katz, G. Lee, and L. Niccolini, "An energy case for hybrid datacenters," ACM SIGOPS Operating Systems Review, Vol.44, No.1, 2010, pp.76-80.
[6]S. Seetharaman, "Energy conservation in multi-tenant networks through power virtuaiization," in Proceedings of the 2010 international conference on Power aware computing and systems,2010.
[7]S. Srikantaiah, A. Kansal, and F. Zhao, "Energy aware consolidation for cloud computing," in Proceedings of the conference on Power aware computing and systems,2008, pp.10-10.
[8]A. Verma, G. Dasgupta, T.K. Nayak, P. De, and R. Kothari, "Server workload analysis for power minimization using consolidation," in Proceedings of the conference on USENIX Annual technical conference,2009, pp.28-28.
[2]吴建平,刘莹,吴茜,“新一代互联网体系结构理论研究进展,”中国科学：E辑,Vol.38, No.10,2009, pp.1540-1564.
[3]吴建平,吴茜,徐恪,“下一代互联网体系结构基础研究及探索,”计算机学报,Vol.31, No.9,2008, pp.1536-1548.
[4]T. Anderson, L. Peterson, S. Shenker, and J. Turner, "Overcoming the Internet impasse through virtualization," Computer, Vol.38, No.4,2005, pp.34-41.
[5]J. Turner and D. Taylor, "Diversifying the internet," in Proceedings of IEEE GLOBECOM,2005.
[6]D.G. Andersen, H. Balakrishnan, N. Feamster, T. Koponen, D. Moon, and S. Shenker, "Accountable internet protocol (AIP)," in Proceedings of ACM SIGCOMM,2008, pp.339-350.
[7]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, 2007, pp.61-64.
[8]郝甲东,张云飞,魏冰,"PlanetLab综述,”中国通信学会信息通信网络技术委员会2009年年会论文集(上册),Vol.,No.2009.
[9]B. Chun, D. Culler, T. Roscoe, A. Bavier, L. Peterson, M. Wawrzoniak, and M. Bowman, Planetlab:an overlay testbed for broad-coverage services, ACM SIGCOMM Computer Communication Review, Vol.33, No.3,2003, pp.3-12.
[10]Global Environment for Networking Innovation, [EB/OL].: http://www.geni.net.
[11]A. Bavier, N. Feamster, M. Huang, L. Peterson, and J. Rexford, "In VINI veritas: realistic and controlled network experimentation," in Proceedings of ACM SIGCOMM,2006, pp.3-14.
[12]M. Handley, O. Hodson, and E. Kohler, "XORP:An open platform for network research," ACM SIGCOMM Computer Communication Review, Vol.33, No.1, 2003, pp.53-57.
[13]E. Kohler, R. Morris, B. Chen, J. Jannotti, and M.F. Kaashoek, "The Click modular router," ACM Transactions on Computer Systems (TOCS), Vol.18, No. 3,2000, pp.263-297.
[14]N. Feamster and H. Balakrishnan, "Detecting BGP configuration faults with static analysis," in Proceedings of USENIX NSDI 2005, pp.43-56.
[15]C. Wenlong, X. Mingwei, Y. Yang, L. Qi, and M. Dong-Chao, "Virtual network with high performance:VegaNet," Chinese Journal of Computers, Vol.33, No.1, 2010, pp.63-73.
[16]The FP7 4WARD Project, [EB/OL].:www.4ward-project.eu/.
[17]韩言妮,蕈毅芳,慈松,“未来网络虚拟化关键技术研究,”中兴通讯技术,Vol.17, No.2,2011, pp.15-19.
[18]L.E. Li, Z.M. Mao, and J. Rexford, "Toward Software-Defined Cellular Networks," in Proceedings of European Workshop on Software Defined Networking 2012.
[19]C. Guo, G. Lu, H.J. Wang, S. Yang, C. Kong, P. Sun, W. Wu, and Y. Zhang, "Secondnet:a data center network virtualization architecture with bandwidth guarantees," in Proceedings of ACM CONEXT 2010.
[20]TX Matrix Plus Router,, [EB/OL].: http://www.juniper.net/techpubs/en_US/release-independent/junos/information-p roducts/pathway-pages/t-series/.
[21]N. Chowdhury and R. Boutaba, "Network virtualization:state of the art and research challenges," IEEE Communications Magazine, Vol.47, No.7,2009, pp. 20-26.
[22]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,2008, pp.17-29.
[23]N. Chowdhury, M. Rahman, and R. Boutaba, "Virtual network embedding with coordinated node and link mapping," in IEEE INFOCOM,2009, pp.783-791.
[24]W.L. Yeow, C. Westphal, and U. Kozat, "Designing and embedding reliable virtual infrastructures," in the 2st ACM workshop on Virtualized infrastructure systems and architectures,2010, pp.33-40.
[25]Y. Chen, J. Li, T. Wo, C. Hu, and W. Liu, "Resilient Virtual Network Service Provision in Network Virtualization Environments," in IEEE International Conference on Parallel and Distributed Systems,2010, pp.51-58.
[26]J. Kennedy and R. Eberhart, "Particle swarm optimization," in Proceedings of IEEE International Conference on Neural Networks,1995, pp.1942-1948.
[1]V. Rajaravivarma. "Virtual local area network technology and applications," IEEE Transactions on Communications,1997, pp.49-52.
[2]R. Yuan, W.T. Strayer, and T. Strayer, "Virtual private networks:technologies and solutions," Addi son-Wesley,2001.
[3]E.K. Lua, J. Crowcroft, M. Pias, R. Sharma, and S. Lim, "A survey and comparison of peer-to-peer overlay network schemes," IEEE Communications Surveys and Tutorials, Vol.7, No.2,2005, pp.72-93.
[4]N. Chowdhury and R. Boutaba, "Network virtualization:state of the art and research challenges," IEEE Communications Magazine, Vol.47, No.7,2009, pp. 20-26.
[5]F.A. Tobagi and V. Bruce Hunt, "Performance analysis of carrier sense multiple access with collision detection," Computer Networks, Vol.4, No.5,1980, pp. 245-259.
[6]W. Townsley, A. Valencia, A. Rubens, G. Pall, G. Zorn, and B. Palter, "Layer two tunneling protocol (L2TP)," IETF,1999.
[7]W. Simpson, "The point-to-point protocol (PPP)," IETF,1993.
[8]A. Valencia, M. Littlewood, and T. Kolar, "Cisco Layer Two Forwarding Protocol (L2F)," IETF,1998.
[9]K. Hamzeh, G. Pall, W. Verthein, J. Taarud, W. Little, and G. Zorn, "Point-to-point tunneling protocol (PPTP)," IETF,1999.
[10]D. Farinacci, P. Traina, S. Hanks, and T. Li, "Generic routing encapsulation (GRE)," IETF,1994.
[11]N. Doraswamy and D. Harkins, "IPSec:the new security standard for the Internet, intranets, and virtual private networks," Prentice Hall,2003.
[12]E. Rosen, A. Viswanathan, and R. Callon, "Multiprotocol label switching architecturez (MPLS)," IETF,2001.
[13]L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala, "RSVP:A new resource reservation protocol," Network, IEEE, Vol.7, No.5,1993, pp.8-18.
[14]R. Yavatkar, D. Hoffman, Y. Bernet, F. Baker, and M. Speer, "Subnet Bandwidth Manager (SBM):A protocol for RSVP-based admission control over IEEE 802-style networks," IETF,2000.
[15]S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, "An architecture for differentiated services," IETF,1998.
[16]J. Wroclawski, "The use of RSVP with IETF integrated services," IETF,1997.
[17]王肠肠,毕军,吴建平,“互联网覆盖路由技术研究,”Journal of Software, Vol. 20, No.11,2009, pp.2988-3000.
[18]S. Savage, T. Anderson, A. Aggarwal, D. Becker, N. Cardwell, A. Collins, E. Hoffman, J. Snell, A. Vahdat, and G. Voelker, "Detour:Informed Internet routing and transport," IEEE Micro, Vol.19, No.1,1999, pp.50-59.
[19]D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris, "Resilient overlay networks," ACM SIGCOMM Computer Communication Review, Vol.32, No. 1,2002, pp.66-66.
[20]L. Subramanian, I. Stoica, H. Balakrishnan, and R. Katz, "OverQoS:An overlay based architecture for enhancing Internet QoS," in Proceedings of NSDI,2004, pp.6-21.
[21]J. Shamsi and M. Brockmeyer, "QoSMap:QoS aware Mapping of Virtual Networks for Resiliency and Efficiency," in Proceedings of IEEE Globecom Workshops 2007.
[22]Y. Li, Y. Zhang, L.L. Qiu, and S. Lam, "SmartTunnel:Achieving reliability in the internet," in Proceedings of INFOCOM,2007, pp.830-838.
[23]R. Kokku, A. Bohra, S. Ganguly, and A. Venkataramani, "A multipath background network architecture," in Proceedings of INFOCOM,2007, pp. 1352-1360.
[24]S. Banerjee, B. Bhattacharjee, and C. Kommareddy, "Scalable application layer multicast," UM Computer Science Department Technical Report,2002.
[25]S. Saroiu, K.P. Gummadi, R.J. Dunn, S.D. Gribble, and H.M. Levy, "An analysis of internet content delivery systems," in Proceedings of OSDI,2002, pp. 315-328.
[26]B. Chun, D. Culler, T. Roscoe, A. Bavier, L. Peterson, M. Wawrzoniak, and M. Bowman, "Planetlab:an overlay testbed for broad-coverage services," ACM SIGCOMM Computer Communication Review, Vol.33, No.3,2003, pp.3-12.
[27]B. White, J. Lepreau, L. Stoller, R. Ricci, S. Guruprasad, M. Newbold, M. Hibler, C. Barb, and A. Joglekar, "An integrated experimental environment for distributed systems and networks," in Proceedings of OSDI,2002, pp.255-270.
[28]A.D. Keromytis, V. Misra, and D. Rubenstein, "SOS:Secure overlay services," in Proceedings of SIGCOMM,2002, pp.61-72.
[29]D.G. Andersen, "Mayday:Distributed filtering for internet services," in Proceedings of USENIX Symp. Internet Technologies and Systems,2003, pp. 37-39.
[30]M. Hosseini, D.T. Ahmed, S. Shirmohammadi, and N.D. Georganas, "A survey of application-layer multicast protocols," IEEE Communications Surveys & Tutorials, Vol.9, No.3,2007, pp.58-74.
[31]J. Turner and D. Taylor, "Diversifying the internet," in Proceedings of IEEE GLOBECOM,2005.
[32]T. Anderson, L. Peterson, S. Shenker, and J. Turner, "Overcoming the Internet impasse through virtualization," Computer, Vol.38, No.4,2005, pp.34-41.
[33]Global Environment for Networking Innovation, [EB/OL].:http://www.geni.net.
[34]A. Bavier, N. Feamster, M. Huang, L. Peterson, and J. Rexford, "In VINI veritas: realistic and controlled network experimentation," in Proceedings of ACM SIGCOMM,2006, pp.3-14..
[35]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, 2007, pp.61-64.
[36]A. Gavras, A. Karila, S. Fdida, M. May, and M. Potts, "Future internet research and experimentation:the FIRE initiative," ACM SIGCOMM Computer Communication Review, Vol.37, No.3,2007, pp.89-92.
[37]N. Niebert, S. Baucke, I. El-Khayat, M. Johnsson, B. Ohlman, H. Abramowicz, K. Wuenstel, H. Woesner, J. Quittek, and L.M. Correia, "The way 4WARD to the creation of a future Internet," in Proceedings of IEEE PIMRC,2008, pp.1-5.
[38]M. Handley, O. Hodson, and E. Kohler, "XORP:An open platform for network research," ACM SIGCOMM Computer Communication Review, Vol.33, No.1, 2003, pp.53-57.
[39]G. Watson, N. McKeown, and M. Casado, "NetFPGA:A tool for network research and education," in Proceedings of WARFP,2006.
[40]N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, "OpenFlow:enabling innovation in campus networks," ACM SIGCOMM Computer Communication Review, Vol.38, No.2,2008, pp. 69-74.
[41]N. Gude, T. Koponen, J. Pettit, B. Pfaff, M. Casado, N. McKeown, and S. Shenker, "NOX:towards an operating system for networks," ACM SIGCOMM Computer Communication Review, Vol.38, No.3,2008, pp.105-110.
[42]N. Handigol, S. Seetharaman, M. Flajslik, N. McKeown, and R. Johari, "Plug-n-Serve:Load-balancing web traffic using OpenFlow," ACM SIGCOMM Demo,2009.
[43]K.K. Yap, M. Kobayashi, R. Sherwood, T.Y. Huang, M. Chan, N. Handigol, and N. McKeown, "OpenRoads:Empowering research in mobile networks," ACM SIGCOMM Computer Communication Review, Vol.40, No.1,2010, pp. 125-126.
[44]G. Gibb, D. Underhill, A. Covington, T. Yabe, and N. McKeown. "OpenPipes: Prototyping high-speed networking systems," in Proceedings of ACM SIGCOMM Demo,2009.
[45]R. Sherwood, G. Gibb, K. Yap, G. Appenzeller, M. Casado, N. McKeown, and G. Parulkar, "Flowvisor:A network virtualization layer, OpenFlow Switch Consortium," Technical Report,2009.
[46]B. Pfaff, J. Pettit, T. Koponen, K. Amidon, M. Casado, and S. Shenker, "Extending networking into the virtualization layer," in Proceedings of HotNets, 2009.
[47]A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yener, "Provisioning a virtual private network:A network design problem for multicommodity flow," in the thirty-third annual ACM symposium on Theory of computing,2001, pp. 389-398.
[48]A. Haque and P. Ho, "Design of survivable optical virtual private networks (O-VPNs)," Network, Vol.1, No.3, pp.4.
[49]W. Szeto, Y. Iraqi, and R. Boutaba, "A multi-commodity flow based approach to virtual network resource allocation," in Proceedings of IEEE GLOBECOM, 2004.
[50]Q. Fang, J. Cobb, and E. Leiss, "A pre-selection routing scheme for virtual circuit networks," 1999.
[51]R. Ricci, C. Alfeld, and J. Lepreau, "A solver for the network testbed mapping problem," ACM SIGCOMM Computer Communication Review, Vol.33, No.2, 2003, pp.81.
[52]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,2008, pp.17-29.
[53]N. Chowdhury, M. Rahman, and R. Boutaba, "Virtual network embedding with coordinated node and link mapping," in Proceedings of IEEE INFOCOM, 2009, pp.783-791.
[54]J. Lischka and H. Karl, "A virtual network mapping algorithm based on subgraph isomorphism detection," in the 1st ACM workshop on Virtualized infrastructure systems and architectures,2009, pp.81-88.
[55]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, Vol.35, No.2006.
[56]Y. Zhu and M. Ammar, "Algorithms for assigning substrate network resources to virtual network components," in Proceedings of IEEE INFOCOM,2006,
[57]J. He, R. Zhang-Shen, Y. Li, C. Lee, J. Rexford, and M. Chiang, "Davinci: Dynamically adaptive virtual networks for a customized internet," in Proceedings of ACM CoNEXT,2008, pp.1-12.
[58]I. Houidi, W. Louati, and D. Zeghlache, "A distributed virtual network mapping algorithm," in Proceedings of IEEE ICC,2008, pp.5634-5640.
[59]Y. Chen, J. Li, T. Wo, C. Hu, and W. Liu, "Resilient Virtual Network Service Provision in Network Virtualization Environments," in Proceedings of IEEE International Conference on Parallel and Distributed Systems,2010, pp.51-58.
[60]D. Eppstein, "Finding the k shortest paths," 1994.
[61]R. Ahuja, T. Magnanti, and J. Orlin, "Network flows:theory, algorithms, and applications," Prentice-Hall,1993.
[62]L. Cordella, P. Foggia, C. Sansone, and M. Vento, "An improved algorithm for matching large graphs," 2001.
[63]J. Holland, "Adaptation in natural and artificial systems," MIT Press Cambridge, MA, USA,1992.
[1]G.H. Weiss and R.J. Rubin, "Random walks:theory and selected applications," Advances in Chemical Physics, Volume 52, Vol., No.2007, pp.363-505.
[2]N. Chowdhury and R. Boutaba, "Network virtualization:state of the art and research challenges," IEEE Communications Magazine, Vol.47, No.7,2009, pp. 20-26.
[3]N. Chowdhury and R. Boutaba, "A survey of network virtualization," Computer Networks, Vol.54, No.5,2010, pp.862-876.
[4]D. Andersen, "Theoretical approaches to node assignment," Unpublished Manuscript,2002.
[5]J. Lischka and H. Karl, "A virtual network mapping algorithm based on subgraph isomorphism detection," in the 1st ACM workshop on Virtualized infrastructure systems and architectures,2009, pp.81-88.
[6]L. Cordella, P. Foggia, C. Sansone, and M. Vento, "An improved algorithm for matching large graphs," 2001, pp.149-159.
[7]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,2008, pp.17-29.
[8]W. Szeto, Y. Iraqi, and R. Boutaba, "A multi-commodity flow based approach to virtual network resource allocation," in Proceedings of IEEE GLOBECOM, 2004.
[9]J. Dean and S. Ghemawat, "MapReduce:simplified data processing on large clusters," Communications of the ACM, Vol.51, No.1,2008, pp.107-113.
[10]X. Meng, V. Pappas, and L. Zhang, "Improving the scalability of data center networks with traffic-aware virtual machine placement," in Proceedings of INFOCOM,2010.
[11]J.T. Piao and J. Yan, "A network-aware virtual machine placement and migration approach in cloud computing," in Proceedings of GCC,2010, pp.87-92.
[12]G. Lee, N. Tolia, P. Ranganathan, and R.H. Katz, "Topology-aware resource allocation for data-intensive workloads," in Proceedings of the first ACM asia-pacific workshop on systems,2010.
[13]B. Palanisamy, A. Singh, L. Liu, and B. Jain, "Purlieus:locality-aware resource allocation for MapReduce in a cloud," in Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, 2011.
[14]M. Cardosa, M.R. Korupolu, and A. Singh, "Shares and utilities based power consolidation in virtualized server environments," in Proceedings of Integrated Network Management,2009, pp.327-334.
[15]A. Verma, G. Dasgupta, T.K. Nayak, P. De, and R. Kothari, "Server workload analysis for power minimization using consolidation," in Proceedings of the USENIX Annual technical conference,2009, pp.28-28.
[16]N. Bobroff, A. Kochut, and K. Beaty, "Dynamic placement of virtual machines for managing sla violations," in Proceedings of Integrated Network Management, 2007, pp.119-128.
[17]N. Farooq Butt, M. Chowdhury, and R. Boutaba, "Topology-awareness and reoptimization mechanism for virtual network embedding," in Proceedings of IFIP NETWORKING,2010, pp.27-39.
[18]Y. Wang, E. Keller, B. Biskeborn, J. van der Merwe, and J. Rexford, "Virtual routers on the move:live router migration as a network-management primitive,' ACM SIGCOMM Computer Communication Review, Vol.38, No.4.2008, pp. 231-242.
[19]P. Pisa, N. Fernandes, H. Carvalho, M. Moreira, M. Campista, L. Costa, and O. Duarte, "Openflow and Xen-based virtual network migration. Communications: Wireless in Developing Countries and Networks of the Future," 2010, pp. 170-181.
[20]L. Page, S. Brin, R. Motwani, and T. Winograd, "The PageRank citation ranking: bringing order to the web," 1999.
[21]M. Diligenti. M. Gori, and M. Maggini, "A unified probabilistic framework for web page scoring systems," IEEE Transactions on Knowledge and Data Engineering, Vol.16, No.1,2004, pp.4-16.
[22]M. Gori, M. Maggini. and L. Sarti. "Exact and approximate graph matching using random walks," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.27, No.7.2005. pp.1100-1111.
[23]E. Seneta, "Non-negative Matrices and Markov Chains," Springer,1981.
[24]M. Bianchini, M. Gori, and F. Scarselli, "Inside pagerank," ACM Transactions on Internet Technology (TOIT), Vol.5, No.1,2005, pp.92-128.
[25]N. Chowdhury, M. Rahman, and R. Boutaba, "Virtual network embedding with coordinated node and link mapping," in Proceedings of IEEE INFOCOM,2009, pp.783-791.
[1]N. Chowdhury and R. Boutaba, "Network virtualization:state of the art and research challenges," IEEE Communications Magazine, Vol.47, No.7,2009, pp. 20-26.
[2]N. Chowdhury, M. Rahman, and R. Boutaba, "Virtual network embedding with coordinated node and link mapping," in Proceedings of IEEE INFOCOM,2009, pp.783-791.
[3]X. Cheng, S. Su, Z. Zhang, H. Wang, F. Yang, Y. Luo, and J. Wang, "Virtual Network Embedding Through Topology-Aware Node Ranking," ACM SIGCOMM Computer Communication Review, Vol.41, No.2,2011, pp.39-47.
[4]J. Lischka and H. Karl, "A virtual network mapping algorithm based on subgraph isomorphism detection," in the 1st ACM workshop on Virtualized infrastructure systems and architectures,2009, pp.81-88.
[5]J. Shamsi and M. Brockmeyer, "QoSMap:QoS aware Mapping of Virtual Networks for Resiliency and Efficiency," in Proceedings of IEEE Globecom Workshops 2007.
[6]Y. Zhu and M. Ammar, "Algorithms for assigning substrate network resources to virtual network components," in Proceedings of IEEE INFOCOM,2006.
[7]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, Vol.35, No.2006.
[8]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,2008, pp.17-29.
[9]Y. Chen, J. Li, T. Wo, C. Hu, and W. Liu, "Resilient Virtual Network Service Provision in Network Virtualization Environments," in Proceedings of IEEE International Conference on Parallel and Distributed Systems,2010, pp.51-58.
[10]I. Houidi, W. Louati, W. Ben Ameur, and D. Zeghlache, "Virtual network provisioning across multiple substrate networks," Computer Networks, Vol.55, No.4,2011, pp.1011-1023.
[11]I. Houidi, W. Louati, D. Zeghlache, and S. Baucke, "Virtual resource description and clustering for virtual network discovery," in Proceedings of IEEE ICC Workshops,2009.
[12]A. Schrijver, "Theory of linear and integer programming," Wiley,1986.
[13]E.L. Lawler and D.E. Wood, "Branch-and-bound methods:A survey, Operations research," Vol.14, No.4,1966, pp.699-719.
[14]J.E. Kelley Jr, The cutting-plane method for solving convex programs, "Journal of the Society for Industrial & Applied Mathematics," Vol.8, No.4,1960, pp. 703-712.
[15]J. Holland, "Adaptation in natural and artificial systems," MIT Press Cambridge, MA, USA,1992.
[16]S. Kirkpatrick Jr, CD Gelatt, and MP Vecchi, "Optimization by simulated annealing," Science, Vol.220, No.4598,1983, pp.671-680.
[17]J.H. Kim and H. Myung, "Evolutionary programming techniques for constrained optimization problems," IEEE Transactions on Evolutionary Computation, Vol.1, No.2,1997, pp.129-140.
[18]J. Kennedy and R. Eberhart, "Particle swarm optimization," 1995, pp. 1942-1948.
[19]Y. Shi, "Particle swarm optimization:developments, applications and resources," in Proceedings of Evolutionary Computation,2001, pp.81-86.
[20]G. Klir and B. Yuan, "Fuzzy sets and fuzzy logic:theory and applications," Prentice Hall PTR Upper Saddle River, NJ, USA,1995.
[21]S. Savage, T. Anderson, A. Aggarwal, D. Becker, N. Cardwell, A. Collins, E. Hoffman, J. Snell, A. Vahdat, and G. Voelker, "Detour:Informed Internet routing and transport," IEEE Micro, Vol.19, No.1,1999, pp.50-59.
[22]J. Kennedy and R.C. Eberhart, "A discrete binary version of the particle swarm algorithm," in Proceedings of IEEE International Conference on Systems, Man, and Cybernetics,1997, pp.4104-4108.
[23]M. Clerc, "Discrete particle swarm optimization illustrated by the traveling salesman problem," New optimization techniques in engineering, Vol.141, No. 2004, pp.219-239.
[24]R. Poli, J. Kennedy, and T. Blackwell, "Particle swarm optimization, Swarm intelligence," Vol.1, No.1,2007, pp.33-57.
[25]X. Zhao, X.S. Gao, and Z.C. Hu, "Evolutionary programming based on non-uniform mutation," Applied Mathematics and Computation, Vol.192, No. 1,2007, pp.1-11.
[26]N. Higashi and H. Iba, "Particle swarm optimization with Gaussian mutation," in Swarm Intelligence Symposium,2003, pp.72-79.
[27]N. Farooq Butt, M. Chowdhury, and R. Boutaba, "Topology-awareness and reoptimization mechanism for virtual network embedding," in Proceedings of IFIP NETWORKING,2010, pp.27-39.
[1]X. Cheng, S. Su, Z. Zhang, H. Wang, F. Yang, Y. Luo, and J. Wang, "Virtual Network Embedding Through Topology-Aware Node Ranking," ACM SIGCOMM Computer Communication Review, Vol.41, No.2,2011, pp.39-47.
[2]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,2008, pp.17-29.
[3]X. Cheng, Z.B. Zhang, S. Su, and F.C. Yang, "Virtual network embedding based on particle swarm optimization," Acta Electronica Sinica, Vol.39, No.10,2011, pp.2240-2244.
[4]N. Chowdhury, M. Rahman, and R. Boutaba, "Virtual network embedding with coordinated node and link mapping," in Proceedings of IEEE INFOCOM,2009, pp.783-791.
[5]N. Chowdhury and R. Boutaba, "A survey of network virtualization," Computer Networks, Vol.54, No.5,2010, pp.862-876.
[6]G. Koslovski, W.L. Yeow, C. Westphal, T.T. Huu, J. Montagnat, and P. Vicat-Blanc, "Reliability support in virtual infrastructures," in Proceedings of IEEE CloudCom,2010, pp.49-58.
[7]T. Guo, N. Wang, K. Moessner, and R. Tafazolli, "Shared Backup Network Provision for Virtual Network Embedding," in Proceedings of IEEE ICC,2011, pp.1-5.
[8]M. Motiwala, M. Elmore, N. Feamster, and S. Vempala, "Path splicing," ACM SIGCOMM Computer Communication Review, Vol.38, No.4,2008, pp.27-38.
[9]J. Shamsi and M. Brockmeyer, "QoSMap:QoS aware Mapping of Virtual Networks for Resiliency and Efficiency," in Proceedings of IEEE Globecom Workshops 2007.
[10]D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris, "Resilient overlay networks," ACM SIGCOMM Computer Communication Review, Vol.32, No.1, 2002, pp.66-66.
[11]M. Rahman, I. Aib, and R. Boutaba, "Survivable Virtual Network Embedding, " in Proceedings of IFIP NETWORKING,2010, pp.40-52.
[12]Y. Chen, J. Li, T. Wo, C. Hu, and W. Liu, "Resilient Virtual Network Service Provision in Network Virtualization Environments," in Proceedings of IEEE International Conference on Parallel and Distributed Systems,2010, pp.51-58.
[13]W.L. Yeow, C. Westphal, and U. Kozat, "Designing and embedding reliable virtual infrastructures," in the 2st ACM workshop on Virtualized infrastructure systems and architectures,2010, pp.33-40.
[14]W. Cui, I. Stoica, and R.H. Katz, "Backup path allocation based on a correlated link failure probability model in overlay networks," in Proceedings of IEEE Network Protocols,2002, pp.236-245.
[15]W. Lau and S. Jha, "Failure-oriented path restoration algorithm for survivable networks," IEEE Transactions on Network and Service Management, Vol.1, No. 1,2004, pp.11-20.
[16]Y. Liu, D. Tipper, and P. Siripongwutikorn, "Approximating optimal spare capacity allocation by successive survivable routing," in Proceedings of INFOCOM,2001, pp.699-708.
[17]R. Ramaswami and K. Sivarajan, "Routing and wavelength assignment in all-optical networks," IEEE/ACM Transactions on Networking, Vol.3, No.5, 1995, pp.489-500.
[18]E. Modiano and A. Narula-Tam, "Survivable routing of logical topologies-in WDM networks," in Proceedings of IEEE INFOCOM,2001, pp.348-357.
[19]M. Kurant and P. Thiran, "Survivable routing of mesh topologies in IP-over-WDM networks by recursive graph contraction," IEEE Journal on Selected Areas in Communications, Vol.25, No.5,2007, pp.922-933.
[20]P.H. Ho, J. Tapolcai, and H.T. Mouftah, "On achieving optimal survivable routing for shared protection in survivable next-generation internet," IEEE Transactions on Reliability, Vol.53, No.2,2004, pp.216-225.
[21]A. Haque and P. Ho, "Design of survivable optical virtual private networks (O-VPNs)," Network, Vol.1, No.3, pp.4.
[22]R.M. Karp, "On the Computational Complexity of Combinatorial Problems," Networks, Vol.5, No.175, pp.45-68.
[23]X. Cheng, S. Su, Z. Zhang, K. Shuang, F. Yang, Y. Luo, and J. Wang, "Virtual network embedding through topology awareness and optimization," Computer Networks,2012.
[24]S. Tsukiyama, I. Shirakawa, H. Ozaki, and H. Ariyoshi, "An algorithm to enumerate all cutsets of a graph in linear time per cutset," Journal of the ACM, Vol.27, No.4,1980, pp.619-632.
[1]B. Augustin, X. Cuvellier, B. Orgogozo, F. Viger, T. Friedman, M. Latapy, C. Magnien, and R. Teixeira, "Avoiding traceroute anomalies with Paris traceroute," in Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, 2006, pp.153-158.
[2]A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford, "NetScope: Traffic engineering for IP networks," IEEE Network, Vol.14, No.2,2000, pp. 11-19.
[3]J. He and J. Rexford, "Toward internet-wide multipath routing," Network, IEEE, Vol.22, No.2,2008, pp.16-21.
[4]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,2008, pp.17-29.
[5]B.G. Chun, G. Iannaccone, R. Katz, G. Lee, and L. Niccolini, "An energy case for hybrid datacenters," ACM SIGOPS Operating Systems Review, Vol.44, No.1, 2010, pp.76-80.
[6]S. Seetharaman, "Energy conservation in multi-tenant networks through power virtuaiization," in Proceedings of the 2010 international conference on Power aware computing and systems,2010.
[7]S. Srikantaiah, A. Kansal, and F. Zhao, "Energy aware consolidation for cloud computing," in Proceedings of the conference on Power aware computing and systems,2008, pp.10-10.
[8]A. Verma, G. Dasgupta, T.K. Nayak, P. De, and R. Kothari, "Server workload analysis for power minimization using consolidation," in Proceedings of the conference on USENIX Annual technical conference,2009, pp.28-28.