基于蟻群算法的虛擬網絡映射研究
發(fā)布時間：2019-05-22 08:07
【摘要】：隨著計算機網絡在近幾年的迅猛發(fā)展,存在于現(xiàn)有互聯(lián)網架構中的問題日益顯著,例如可擴展性、可控可管性、服務質量保證、綠色節(jié)能等方面。為了徹底解決這些問題,學術界提出了對未來網絡“從頭再來(clean-slate)"的設計思想,希望能夠擺脫現(xiàn)有互聯(lián)網約束,重新設計能夠適應未來網絡的體系架構。網絡虛擬化是構建新一代互聯(lián)網體系架構的核心技術,它允許多個網絡應用能同時共享在一個底層物理網絡上,并能夠為用戶提供多樣化的定制服務。在網絡虛擬化中,網絡實體分為物理網絡和虛擬網絡。多個不同的虛擬網絡根據(jù)服務需求,需要不同的網絡資源包括充足的網絡節(jié)點數(shù)和足夠的網絡鏈路帶寬。虛擬網絡上的節(jié)點和鏈路能夠在物理網絡上創(chuàng)建、刪除。網絡虛擬化已經被應用于數(shù)據(jù)中心解決擴展性、復雜性、資源利用率等問題。另外,在云計算環(huán)境中,為了實現(xiàn)計算資源的共享、分離與聚合以及資源的易管理性,網絡虛擬化成為解決這些問題的關鍵技術。虛擬網絡映射問題(VNE)是網絡虛擬化在資源分配的核心問題。將不同虛擬網絡的資源包括節(jié)點資源和鏈路資源映射到物理網絡上。其中,節(jié)點資源一般有CPU、內存、地理位置等；鏈路資源有延遲、帶寬等。虛擬網絡映射的目標是在滿足虛擬網絡資源約束的前提下,將虛擬網絡嵌入到合適的底層物理網絡上。在保證虛擬網絡資源請求的情況下,盡可能的降低虛擬網絡請求的拒絕率,同時提高底層物理網絡的資源收益。虛擬網絡映射不僅要解決準入控制、請求排隊、資源約束問題,還要解決拓撲多樣性等多方面的問題。由于應用場景、優(yōu)化目標、映射方式和約束條件的不同,虛擬網絡映射又分為不同類型的優(yōu)化問題。本文基于蟻群算法分別對離線虛擬網絡映射ACO-VNE和在線虛擬網絡映射提出了相應的映射算法VNE-CACO.對于ACO-VNE算法,屬于兩階段映射算法,首先進行節(jié)點映射,然后進行鏈路映射。通過判斷映射結果的好壞,螞蟻將信息素分布于節(jié)點上。螞蟻之間通過信息素進行學習,學習前代螞蟻的映射經驗,另外將節(jié)點的資源情況作為啟發(fā)式因子。螞蟻通過輪盤賭選擇節(jié)點映射方案,然后再進行鏈路的映射。直到蟻群算法收斂或者達到設定的運行次數(shù)上限即得到映射解。針對在線虛擬網絡映射,我們提出了VNE-CACO。VNE-CACO是一種一階段的協(xié)同映射算法。一方面,該算法將物理網絡拓撲上的關鍵路徑作為稀有資源盡量保留,來應對后續(xù)的虛擬網絡請求。另一方面,該算法通過螞蟻之間對映射解空間的探索所遺留的信息素,然后結合啟發(fā)式因子信息,不斷的向最優(yōu)解靠攏。算法直到收斂或者達到運行的最大代數(shù)停止,獲得最終解。本文對兩種算法均做了詳細的仿真實驗,實驗結果表明蟻群算法在解決虛擬網絡映射問題中具有優(yōu)秀的表現(xiàn)。
[Abstract]:With the rapid development of computer network in recent years, the problems existing in the existing Internet architecture are becoming more and more obvious, such as scalability, controllability, quality of service assurance, green energy saving and so on. In order to solve these problems thoroughly, the academic circles put forward the design idea of "starting from scratch (clean-slate)" for the future network, hoping to get rid of the existing Internet constraints and redesign the architecture that can adapt to the future network. Network virtualization is the core technology to build a new generation of Internet architecture, which allows multiple network applications to share on one underlying physical network at the same time, and can provide users with a variety of custom services. In network virtualization, network entities are divided into physical network and virtual network. According to the service requirements, many different virtual networks need different network resources, including sufficient number of network nodes and sufficient network link bandwidth. Nodes and links on virtual networks can be created and deleted on physical networks. Network virtualization has been used in data centers to solve scalability, complexity, resource utilization and other issues. In addition, in order to realize the sharing, separation and aggregation of computing resources and the ease of management of resources, network virtualization has become the key technology to solve these problems in cloud computing environment. Virtual network mapping problem (VNE) is the core problem of network virtualization in resource allocation. The resources of different virtual networks, including node resources and link resources, are mapped to the physical network. Among them, node resources generally have CPU, memory, geographical location and so on; link resources have delay, bandwidth and so on. The goal of virtual network mapping is to embed the virtual network into the appropriate underlying physical network under the premise of satisfying the constraints of virtual network resources. Under the condition of ensuring the virtual network resource request, the rejection rate of the virtual network request is reduced as much as possible, and the resource income of the underlying physical network is improved at the same time. Virtual network mapping not only solves the problems of admission control, request queuing, resource constraints, but also solves the topology diversity and so on. Due to the different application scenarios, optimization objectives, mapping methods and constraints, virtual network mapping is divided into different types of optimization problems. In this paper, the corresponding mapping algorithms VNE-CACO. for offline virtual network mapping ACO-VNE and online virtual network mapping are proposed based on ant colony algorithm. For ACO-VNE algorithm, it belongs to two-stage mapping algorithm, first node mapping, and then link mapping. By judging the quality of the mapping results, ants distribute pheromones on the nodes. Ants learn from each other through pheromones to learn the mapping experience of the previous generation of ants. In addition, the resource situation of nodes is used as a heuristic factor. Ants select node mapping scheme through roulette, and then map the link. Until the ant colony algorithm converges or reaches the set upper limit of running times, the mapping solution is obtained. For online virtual network mapping, we propose that VNE-CACO.VNE-CACO is a one-stage collaborative mapping algorithm. On the one hand, the algorithm preserves the critical path in the physical network topology as a rare resource as much as possible to cope with the subsequent virtual network requests. On the other hand, the algorithm is based on the pheromones left behind by the exploration of mapping solution space between ants, and then combines the heuristic factor information to get close to the optimal solution. Until the algorithm converges or reaches the maximum algebra to stop, the final solution is obtained. In this paper, the two algorithms are simulated in detail, and the experimental results show that ant colony algorithm has excellent performance in solving the problem of virtual network mapping.
【學位授予單位】：山東大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP393.01;TP18
本文編號：2482795
[Abstract]:With the rapid development of computer network in recent years, the problems existing in the existing Internet architecture are becoming more and more obvious, such as scalability, controllability, quality of service assurance, green energy saving and so on. In order to solve these problems thoroughly, the academic circles put forward the design idea of "starting from scratch (clean-slate)" for the future network, hoping to get rid of the existing Internet constraints and redesign the architecture that can adapt to the future network. Network virtualization is the core technology to build a new generation of Internet architecture, which allows multiple network applications to share on one underlying physical network at the same time, and can provide users with a variety of custom services. In network virtualization, network entities are divided into physical network and virtual network. According to the service requirements, many different virtual networks need different network resources, including sufficient number of network nodes and sufficient network link bandwidth. Nodes and links on virtual networks can be created and deleted on physical networks. Network virtualization has been used in data centers to solve scalability, complexity, resource utilization and other issues. In addition, in order to realize the sharing, separation and aggregation of computing resources and the ease of management of resources, network virtualization has become the key technology to solve these problems in cloud computing environment. Virtual network mapping problem (VNE) is the core problem of network virtualization in resource allocation. The resources of different virtual networks, including node resources and link resources, are mapped to the physical network. Among them, node resources generally have CPU, memory, geographical location and so on; link resources have delay, bandwidth and so on. The goal of virtual network mapping is to embed the virtual network into the appropriate underlying physical network under the premise of satisfying the constraints of virtual network resources. Under the condition of ensuring the virtual network resource request, the rejection rate of the virtual network request is reduced as much as possible, and the resource income of the underlying physical network is improved at the same time. Virtual network mapping not only solves the problems of admission control, request queuing, resource constraints, but also solves the topology diversity and so on. Due to the different application scenarios, optimization objectives, mapping methods and constraints, virtual network mapping is divided into different types of optimization problems. In this paper, the corresponding mapping algorithms VNE-CACO. for offline virtual network mapping ACO-VNE and online virtual network mapping are proposed based on ant colony algorithm. For ACO-VNE algorithm, it belongs to two-stage mapping algorithm, first node mapping, and then link mapping. By judging the quality of the mapping results, ants distribute pheromones on the nodes. Ants learn from each other through pheromones to learn the mapping experience of the previous generation of ants. In addition, the resource situation of nodes is used as a heuristic factor. Ants select node mapping scheme through roulette, and then map the link. Until the ant colony algorithm converges or reaches the set upper limit of running times, the mapping solution is obtained. For online virtual network mapping, we propose that VNE-CACO.VNE-CACO is a one-stage collaborative mapping algorithm. On the one hand, the algorithm preserves the critical path in the physical network topology as a rare resource as much as possible to cope with the subsequent virtual network requests. On the other hand, the algorithm is based on the pheromones left behind by the exploration of mapping solution space between ants, and then combines the heuristic factor information to get close to the optimal solution. Until the algorithm converges or reaches the maximum algebra to stop, the final solution is obtained. In this paper, the two algorithms are simulated in detail, and the experimental results show that ant colony algorithm has excellent performance in solving the problem of virtual network mapping.
【學位授予單位】：山東大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP393.01;TP18
【參考文獻】
相關期刊論文 前3條
1 朱強;王慧強;馮光升;呂宏武;王振東;姚崇東;;VNE-ABC:基于人工蜂群的網絡虛擬化映射算法[J];北京工業(yè)大學學報;2014年01期
2 卿蘇德;廖建新;朱曉民;王敬宇;戚琦;;網絡虛擬化環(huán)境中虛擬網絡的嵌套映射算法[J];軟件學報;2012年11期
3 程祥;張忠寶;蘇森;楊放春;;虛擬網絡映射問題研究綜述[J];通信學報;2011年10期
，本文編號：2482795
本文鏈接：http://sikaile.net/guanlilunwen/ydhl/2482795.html
最近更新
教材專著
