摘要
互联网已深刻地影响着人们的生活和工作方式,对经济的发展、社会的进步做出了巨大贡献。但是,互联网及其体系结构经过40年的发展,其面临的可扩展性、安全性、移动性、服务质量、能耗等方面的一系列问题和困难逐渐凸显,难以适应全球网络规模的急剧扩张,难以满足层出不穷的新兴应用和新趋势的需求。
网络虚拟化作为解决当前互联网僵化问题的技术手段,近年来受到了国内外未来网络领域研究的广泛关注。网络虚拟化的本质是通过抽象、分配、隔离机制在一个公共物理网络上独立地运营多个虚拟网络,从而能够有选择性地进行资源分配与调度,最大化物理网络资源利用率、提高服务质量、降低网络运营和维护成本。网络虚拟化在带来上述灵活性的同时,也给网络资源管理提出了巨大挑战。
本论文分别从支持可扩展性、自治性的虚网资源管理架构,基于节点压力的虚网节点映射优化算法,以及基于链路压力的虚网链路映射优化算法等几个方面对虚网资源管理进行了研究,具体内容包括：
1、针对网络虚拟化资源管理架构存在可扩展性不强、自治性差等问题,本文设计了一种层次型的虚网资源管理架构。该架构适用于底层多域物理网络环境,采用分层分域的管理机制,由全局调度中心执行接入控制、虚网划分、虚拟子网映射调度,各分域调度中心并行完成虚拟子网的资源映射及独立处理资源发现、故障管理、移动性管理等工作。这种集中式管理、分布式控制的结构设计,解决了集中式管理容易发生单点失效、性能瓶颈等问题,兼具了分布式系统的优势,能够很好地适应资源动态性、区域自治性等特点,大大降低了虚拟网络的管理复杂度,提高系统整体效率,保障虚网请求的实时处理。
2、为了降低虚网映射算法问题求解的复杂度,大多数启发式算法将虚网映射分为节点映射和链路映射两个部分,并顺序求解。合理设计节点映射算法对于提升虚网整体映射性能具有重要影响。本文以节点压力为优化目标,提出了两种节点映射算法来改善虚网整网映射的性能。首先,受无线资源管理中的注水原理启发,提出一种最小节点压力优先的虚网节点映射算法。该算法通过对节点压力比较排序的方式对节点资源分配进行均衡控制,降低瓶颈节点出现的可能性,改善物理网络负载分布。仿真结果表明,该算法在获得相同映射效率的同时,可明显降低最大节点压力,均衡节点压力分布。其次,针对极限情况下的虚网映射问题,即虚网与物理网等规模的情况,提出一种最大节点压力优先的虚网节点映射算法。该算法通过最大化节点资源利用率,充分利用节点剩余资源,提高节点映射的成功率从而提升虚网整网映射的效率。仿真结果表明,该算法在虚网映射接受比和映射收益两方面均有明显提升,实现了物理网络资源的有效利用。
3、基于链路压力状态反馈的思想提出了一种实现负载感知的自适应虚网映射算法。该算法是一种在线式的基于优先级区分调度的资源分配算法。该算法设计了物理链路剩余带宽反馈因子,有效区分了物理链路的映射接纳能力,通过将虚网映射函数与物理网络负载状态关联起来,实现了保障负载平衡的自适应资源分配。仿真结果表明,所提算法在取得相同映射效率情况下,能有效降低物理链路负载压力,将虚网请求均衡地映射在物理链路上,提高了资源利用率。最后,综合第四章提出的最小节点压力优先虚网节点映射算法与第五章提出的基于链路压力状态反馈的虚网链路映射算法进行联合试验,仿真结果表明两种算法的结合能够同时降低节点压力与链路压力,改善物理节点及链路的负载均衡,更为有效地提高物理网络资源利用率。
The Internet has profoundly affected the way people live and work. It makes a great contribution on economic development and social progress. However, the architecture of Internet faces a range of issues and difficulties such as scalability, security, mobility, quality of service and energy consumption after 40 years of development. It is more difficult to adapt to the rapid expansion of the global network scale and meet the needs of new applications and traffic.
Network virtualization technology plays an important role in solving the ossification problem of Internet. It supports diverse virtual networks sharing the common substrate network by abstraction and isolation mechanism essentially. Network virtualization allocates and schedules resource optimally to maximize the resource utilization and decrease the operation and maintenance cost. The above flexibility and advantage of network virtualization brings great challenge to the virtual resource management.
This dissertation focuses on the scalable and autonomous resource management architecture, the efficient node mapping optimization algorithm based on node stress and the effective link mapping optimization algorithm based on link stress. The major works are outlined as follows:
1. The resource management architecture of network virtualization has the issue of worse scalability and autonomy. To address these issues, we design a resource management architecture based on multi-domain and hierarchy. It adapts to the substrate network composed of multiple infrastructure provider domains. The architecture is composed of a Global Scheduler and several Local Schedulers. The Global Scheduler is responsible for the access control, virtual network partition and global embedding scheduling. And the Local Schedulers complete the sub-virtual network embedding in parallel and deal with the local virtual resource discovery, failure and mobility management independently. The hierarchical architecture reduces the management complexity, improves the efficiency and satisfies the real-time requirement of virtual network embedding. Additionally, it takes advantages of both the central and distributed resource management architectures. It can not only solve the single point failure and performance bottleneck problems caused by centralized models but also reflect the dynamic and autonomous characteristics of resource very well.
2. Existing virtual network embedding algorithms are usually decomposed into two steps:virtual node mapping and virtual link mapping. This decomposition helps reduce the overall complexity of resource allocation for virtual network requests since the virtual network embedding problem is NP-hard. Embedding the virtual node efficiently can promote the performance of the whole virtual network embedding algorithm greatly. We propose two different node mapping algorithm based on node stress to promote the performance of virtual network embedding. First, a node mapping algorithm based on minimum node stress priority is proposed to improve the load balancing of substrate node. It sorts of node stress in order to allocate the node resource balanced. Simulation experiments show that the proposed algorithm achieves the same embedding efficiency and improves the load distribution of substrate nodes distinctly while reducing the average substrate node stress significantly. Another novel node mapping algorithm is proposed based on the maximum node stress priority when the scale of virtual network is equal to that of substrate network. It aims to maximize the substrate node utilization in the node mapping stage to improve the efficiency of virtual network embedding. Simulation experiments show that the proposed algorithm improves the revenue and acceptance ratio of virtual network embedding significantly.
3. A load-aware virtual network mapping algorithm is proposed based on the status feedback of link stress. It deals with the online virtual network requests with priority scheduling defined by mapping revenue. The main contribution is to embed the virtual network requests according to the current load distribution of substrate network. This adaptive algorithm differentiates the residual bandwidth of substrate links and takes full advantage of the multi-path to improve the load balancing of the substrate network by the status feedback factor. Simulation experiments show that the proposed algorithm achieves the same embedding efficiency and improves the load distribution of substrate network distinctly while reducing the average substrate link stress significantly. Finally, we combine the node mapping algorithm based on minimum node stress priority and the link mapping algorithm based on status feedback of link stress to do simulation. The results show that the combined algorithm can reduce the maximum node stress and maximum link stress simultaneously and improve the node load balancing and link load balancing significantly.
引文
[1]T. Anderson, T. Roscoe, D. Wetherall. Preventing internet denial-of-service with capabilities. CCR,2004,34(1):39-44.
[2]B. Braden, T. Faber, M. Handley. From protocol stack to protocol heap role-based architecture. HotNets-Ⅰ,2002.
[3]D. R. Cheriton, M. Gritter. TRIAD:A new next generation internet architecture. Mar 2000.
[4]D. Clark, R. Braden, A. Falk, et al. Fara:reorganizing the addressing architecture. FDNA Workshop,2003:313-321.
[5]H. Balakrishnan. A layered naming architecture for the internet. ACM SIGCOMM,2004:497-506.
[6]M. Handley and A. Greenhalgh. Steps towards a dos-resistant internet architecture. ACM SIGCOMM, FDNA Workshop,2004.
[7]Ion Stoica, D. Adkins, Shelley Zhuang, et. al. Internet indirection infrastructure. IEEE Transactions On Networking,2004,2(12):205-218.
[8]C. Tschudin, R. Gold. Network pointers. ACM SIGCOMM Computer Communication Review,2003,33(1):23-28.
[9]M. Walfish, J. Stribling, M. Krohn, et al. Middleboxes no longer considered harmful.6th Symposium on Operating Systems Design and Implementation(OSDI),2004:215-230.
[10]D. J. Wetherall. Active network vision and reality:lessons from a capsule-based system.17th ACM SOSP,1999:64-79.
[11]X. Yang. Nira:A new internet routing architecture. ACM SIGCOMM, FDNA Workshop,2003:301-312.
[12]D. Zhu, M. Gritter, D. R. Cheriton. Feedback based routing. CCR,2003,33(1): 71-76.
[13]L. Peterson, S. Shenker, J. Turner. Overcoming the Internet impasse through virtualization. IEEE Computer Magazine,2005,38(4):34-41.
[14]GENI计划,http://www.geni.net/.
[15]FIRE计划,http://www.cost.esf.org/index.php?id=989.
[16]AKARI计划,http://akari-project.nict.go.jp/eng/overview.htm.
[17]PlanetLab平台,http://www.planet-lab.org/
[18]N. Feamster, L. Gao, and J. Rexford. How to lease the internet in your spare time. ACM SIGCOMM Computer Communication Review,2007,37(1):61-64.
[19]FIND计划,http://www.nets-find.net/
[20]OpenFlow计划,http://www.openflowswitch.org/
[21]4WARD计划,http://www.4ward-project.eu/
[22]倪宏.宽带信息网3Tnet应用系统及其示范.微计算机应用,2005,26(5)：513-515.
[23]蒋林涛CNGI-——中国下一代互联网示范项目.数据通信,2005：19-20.
[24]吴建平,刘莹,吴茜.新一代互联网体系结构理论研究进展.中国科学E辑：信息科学,2008,38(10)：1540-1564.
[25]胡萍,安捷.GENI、FIND和CNGI、高可信网络的关系与发展.厦门大学学报(自然科学版),2007,S2 46(2)：41-44.
[26]S. Rooney. The hollowman:an innovative ATM control architecture. The 5th IEEE International Symposium on Integrated Network Management Ⅴ: Integrated Management in a Virtual World. London, UK, Chapman & Hall, Ltd., 1997:369-380.
[27]M. Kounavis, A. Campbell, S. Chou, et al. The Genesis Kernel:A programming system for spawning network architectures. IEEE Journal on Selected Areas in Communications,2001,19(3):511-526.
[28]J. Recio, E. Grasa, S. Figuerola, et al. Evolution of the user controlled lightpath provisioning system. The 7th International Conference on Transparent Optical Networks,2005,1:263-266.
[29]A. Greenberg, G. Hjalmtysson, D. A. Maltz, et al. A clean slate 4d approach to network control and management. ACM SIGCOMM Computer Communication Review,2005,35(5):41-54.
[30]Ananth I, Sundararaj, Ashish Gupta, et al. Dynamic topology adaptation of virtual networks of virtual machines. ACM International Conference Proceeding Series, 2004:1-8.
[31]W. Ng, D. Jun, H. Chow, et al. Miblets:A practical approach to virtual network management. The 6th IEEE International Symposium on Integrated Network Management,1999:201-215.
[32]M. Feridan, M. Moser, A. Tanner. Building an abstraction layer for management systems integration. The 1st IEEE International Workshop on End-to-End Virtualization and Gird Management (EVGM'2007),2007:57-60.
[33]Chowdhury NMMK, Zaheer F E, Boutaba R. iMark:An identity management framework for network virtualization environment. Integrated Network Management,2009:335-342.
[34]M. K. Chowdhury, F. Zaheer, R. Boutaba. iMark:An identity management framework for network virtualization environment. The 11th IEEE International Symposium on Integrated Network Management,2009:335-342.
[35]J. He, R. Zhang-Shen, Y. Li, et al. Davinci:Dynamically adaptive virtual networks for a customized internet. ACM CoNEXT,2008.
[36]M. Yu, Y. Yi, J. Rexford, et al. Rethinking virtual network embedding:Substrate support for path splitting and migration. ACM SIGCOMM Computer Communication Review,2008,38(2):17-29.
[37]Costas Courcoubetis, Richard R. Weber. Economic Issues in Shared Infrastructures. ACM SIGCOMM VISA'09,2009:89-95.
[38]Aun Haider, Richard Potter, Akihiro Nakao. Challenges in Resource Allocation in Network Virtualization.20th ITC Specialist Seminar,2009.
[39]D. G. Andersen. Theoretical approaches to node assignment. Unpublished Manuscript, http://www.cs.cmu.edu/-dga/papers/andersen-assign.ps,2002.
[40]J. Fan, M. Ammar. Dynamic topology configuration in service overlay networks: A study of reconfiguration policies. IEEE INFOCOM,2006:1-12.
[41]Jing Lu, Jonathan Turner. Efficient Mapping of Virtual Networks onto a Shared Substrate. Washington University in St.Louis,2006.
[42]Y. Zhu, M. Ammar. Algorithms for assigning substrate network resources to virtual network components. IEEE INFOCOM,2006:1-12.
[43]N. M. M. K. Chowdhury, Muntasir Raihan Rahman, Raouf Boutaba. Virtual Network Embedding with Coordinated Node and Link Mapping. IEEE INFOCOM,2009:783-791.
[1]Global Environment for Network Innovations (GENI). http://www.geni.net/.
[2]Future Internet Network Design (FIND).http://find.isi.edu/.
[3]T. Anderson, L. Peterson, S. Shenker, et al. Overcoming the Internet impasse through virtualization. IEEE Computer Magazine,2005,38(4):34-41.
[4]N. Feamster, L. Gao, R. Nicole, et al. How to lease the Internet in your spare time. SIGCOMM, Comput. Commun. Rev.,2007,37(1):61-64.
[5]PlanetLab平台,http://www.planet-lab.org/[EB/OL].
[6]Emulab-Network Emulation Testbed, http://www.emulab.net/.
[7]OpenFlow计划,http://www.openflowswitch.org/
[8]JGN2+计划,http://www.jgn.nict.go.jp/english/about_us/index.html.
[9]GENI计划,http://www.geni.net/[EB/OL].
[10]J. Lu, J. Turner. Efficient Mapping of Virtual Networks onto a Shared Substrate [EB/OL]. Technical Report WUCSE-2006-35. Washington University,2006.
[11]R. Ricci, C. Alfeld, and J. Lepreau. A Solver for the Network Testbed Mapping Problem, ACM CCR,2003,33(2):65-81.
[12]Mike Hibler, Robert Ricci, Leigh Stoller, et al. Large-scale Virtualization in the Emulab Network Testbed, Proc. of Usenix,2008:113-128.
[13]Nick McKeown, Tom Anderson, Hari Balakrishnan, et al. OpenFlow:Enabling Innovation in Campus Networks. ACM SIGCOMM Computer Communication Review,2008,38(2):69-74.
[14]Rob Sherwood, Glen Gibb, Kok-Kiong Yap. FlowVisor:A Network Virtualization Layer. Technical Report, Stanford University, Jan 2009.
[15]Aun Haider, Richard Potter, Akihiro Nakao. Challenges in Resource Allocation in Network Virtualization.20th ITC Specialist Seminar,2009.
[16]Y. Zhu, M. Ammar. Algorithms for assigning substrate network resources to virtual network components. IEEE INFOCOM,2006:1-12.
[17]M. Yu, Y. Yi, J. Rexford, M. Chiang. Rethinking virtual network embedding: Substrate support for path splitting and migration, ACM SIGCOMM Computer Communication Review,2008,38(2):17-29.
[18]N. M. Mosharaf Kabir Chowdhury, Muntasir Raihan Rahman, Raouf Boutaba. Virtual Network Embedding with Coordinated Node and Link Mapping. IEEE INFOCOM,2009:783-791.
[19]D. G. Andersen. Theoretical approaches to node assignment. Unpublished Manuscript, http://www.cs.cmu.edu/-dga/papers/andersen-assign.ps,2002.
[20]I. Houidi, W. Louati, D. Zeghlache. A distributed virtual network mapping algorithm. Proc. IEEE ICC,2008:5634-5640.
[21]Ye Zhou, Yong Li, Depeng Jin, et al. A Virtual Network Embedding Scheme with Two-Stage Node Mapping Based on Physical Resource Migration. IEEE International Conference on Communication Systems (ICCS),2010:761-766.
[22]J. Fan, M. Ammar. Dynamic topology configuration in service overlay networks: A study of reconfiguration policies. IEEE INFOCOM,2006:1-12.
[23]D. Eppstein. Finding the k shortest paths. In Proc.35th Symp. Foundations of Computer Science IEEE,1994:154-165.
[24]D. Eppstein. Finding the k shortest paths. SIAM J. Computing,1998,28(2): 652-673.
[25]R. K. Ahuja, T. L. Magnanti, J. B. Orlin. Network Flows:Theory, Algorithms, and Applications. Prentice Hall, February 1993.
[26]A. Gupta, J. Kleinberg, A. Kumar, et al. Provisioning a virtual private network:A network design problem for multicommodity flow. In ACM STOC,2001: 389-398.
[27]W. Szeto, Y. Iraqi, R. Boutaba. A multi-commodity flow based approach to virtual network resource allocation. In IEEE GLOBECOM,2003:3004-3008.
[28]E.W.M. Wong, A.K.M. Chan, T.S.P. Yum. A taxonomy of rerouting in circuit-switched networks. Communications Magazine, IEEE,1999,37(11): 116-122.
[29]N. F. Butt, M. Chowdhury, R. Boutaba. Topology-Awareness and Reoptimization Mechanism for Virtual Network Embedding. in Proceedings of the 9th IFIP NETWORKING Conference,2010:27-39.
[30]Jiayue He, Rui Zhang-Shen, Ying Li et al. DaVinci:Dynamically Adaptive Virtual Networks for a Customized Internet. ACM CoNEXT 2008.
[31]J. Shamsi and M. Brockmeyer. QoSMap:QoS aware Mapping of Virtual Networks for Resiliency and Efficiency. Proc. of IEEE Globecom Workshops, 2007:1-6.
[1]GENI计划,http://www.geni.net
[2]GENI Design Principles,http://www.geni.net
[3]GENI System Overview,http://www.geni.net
[4]Overview of the GENI Architecture, http://www.geni.net
[5]GENI System Requirements, http://www.geni.net
[6]Ines HOUIDI, Wajdi LOUATI, Djamal ZEGHLACHE. A Distributed and Autonomic Virtual Network Mapping Framework. Fourth International Conference on Autonomic and Autonomous Systems,2008:241-247.
[1]M. Sayal, Y. Breitbart, P. Scheuermann, et al. Selection algorithms for replicated web servers. SIGMETRICS Perform. Eval. Rev.,1998,26(3):44-50.
[2]P. Krishnan, D. Raz, and Y. Shavitt. The cache location problem. IEEE/ACM Trans. Networking,2000,8(5):568-582.
[3]S. Shi and J. Turner. Placing servers in overlay networks. in Proc. International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPETS),2002.
[4]D. G. Andersen. Theoretical approaches to node assignment. Unpublished Manuscript, http://www.cs.cmu.edu/-dga/papers/andersen-assign.ps,2002.
[5]S. Kirkpatrick, C. D. Gelatt, Jr., et al. Optimization by Simulated Annealing, Science,1983,220(4598):671-680.
[6]Lester Ingber. Very Fast Simulated Re-Annealing. Comput.Modelling,1989: 967-973.
[7]H. Anderson, J. McGeehan. Optimizing microcell base station locations using simulated annealing techniques. In Proceedings of the 44th Vehicular Technology Society Conference,1994:858-862.
[8]Tom Leighton, Fillia Makedon and Spyros Tragoudas. Approximation Algorithms for VLSI Partition Problems. IEEE Intl. Symposium on Circuits and Systems, 1990,4:2865-2868.
[9]Satish Rao. Finding Near Optimal Separators in Planar Graphs.28th Annual Symp. on Foundations of Computer Science,1987:225-237.
[10]Tom Leighton and Satish Rao. Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms. Journal of the ACM, 1999,46(4):787-832.
[11]I. Houidi, W. Louati, D. Zeghlache. A distributed virtual network mapping algorithm. Proc. IEEE ICC,2008:5634-5640.
[12]M. Yu, Y. Yi, J. Rexford, M. Chiang. Rethinking virtual network embedding: Substrate support for path splitting and migration, ACM SIGCOMM Computer Communication Review,2008,38(2):17-29.
[13]J. Lu, J. Turner. Efficient Mapping of Virtual Networks onto a Shared Substrate. Technical Report WUCSE-2006-35. Washington University,2006.
[14]E. W. Zegura, K. L. Calvert, and S. Bhattacharjee. How to model an internetwork. In Proc. IEEE INFOCOM,1996.
[15]N. M. Mosharaf Kabir Chowdhury, Muntasir Raihan Rahman, Raouf Boutaba. Virtual Network Embedding with Coordinated Node and Link Mapping. IEEE INFOCOM,2009:783-791.
[16]D. Eppstein. Finding the k shortest paths. SIAM J. Computing,1998, 28(2):652-673.
[17]Y. Zhu and M. Ammar. Algorithms for assigning substrate network resources to virtual network components. in Proceedings of IEEE INFOCOM,2006.
[18]R. K. Ahuja, T. L. Magnanti, J. B. Orlin. Network Flows:Theory, Algorithms, and Applications. Prentice Hall, February 1993.
[1]D. Eppstein. Finding the k shortest paths. In Proc.35th Symp. Foundations of Computer Science IEEE,1994:154-165.
[2]D. Eppstein. Finding the k shortest paths. SIAM J. Computing,1998, 28(2):652-673.
[3]I. Houidi, W. Louati, D. Zeghlache. A distributed virtual network mapping algorithm. Proc. IEEE ICC,2008:5634-5640.
[4]R. K. Ahuja, T. L. Magnanti, J. B. Orlin. Network Flows:Theory, Algorithms, and Applications. Prentice Hall, February 1993.
[5]A. Gupta, J. Kleinberg, A. Kumar, et al. Provisioning a virtual private network:A network design problem for multicommodity flow. In ACM STOC,2001: 389-398.
[6]W. Szeto, Y. Iraqi, R. Boutaba. A multi-commodity flow based approach to virtual network resource allocation. In IEEE GLOBECOM,2003:3004-3008.
[7]M. Yu, Y. Yi, J. Rexford, M. Chiang. Rethinking virtual network embedding: Substrate support for path splitting and migration, ACM SIGCOMM Computer Communication Review,2008,38(2):17-29.
[8]N. M. Mosharaf Kabir Chowdhury, Muntasir Raihan Rahman, Raouf Boutaba. Virtual Network Embedding with Coordinated Node and Link Mapping. IEEE INFOCOM,2009:783-791.
[9]Y. Aumann and Y. Rabani. An O(log k) Approximate min-cut max-flow theorem and approximation algorithm. In SIAM Journal on Computing,1998,27(1).