基于蟻群算法的虛擬網(wǎng)絡(luò)映射研究
發(fā)布時(shí)間：2019-05-22 08:07
【摘要】：隨著計(jì)算機(jī)網(wǎng)絡(luò)在近幾年的迅猛發(fā)展,存在于現(xiàn)有互聯(lián)網(wǎng)架構(gòu)中的問題日益顯著,例如可擴(kuò)展性、可控可管性、服務(wù)質(zhì)量保證、綠色節(jié)能等方面。為了徹底解決這些問題,學(xué)術(shù)界提出了對未來網(wǎng)絡(luò)“從頭再來(clean-slate)"的設(shè)計(jì)思想,希望能夠擺脫現(xiàn)有互聯(lián)網(wǎng)約束,重新設(shè)計(jì)能夠適應(yīng)未來網(wǎng)絡(luò)的體系架構(gòu)。網(wǎng)絡(luò)虛擬化是構(gòu)建新一代互聯(lián)網(wǎng)體系架構(gòu)的核心技術(shù),它允許多個(gè)網(wǎng)絡(luò)應(yīng)用能同時(shí)共享在一個(gè)底層物理網(wǎng)絡(luò)上,并能夠?yàn)橛脩籼峁┒鄻踊亩ㄖ品⻊?wù)。在網(wǎng)絡(luò)虛擬化中,網(wǎng)絡(luò)實(shí)體分為物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)。多個(gè)不同的虛擬網(wǎng)絡(luò)根據(jù)服務(wù)需求,需要不同的網(wǎng)絡(luò)資源包括充足的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)和足夠的網(wǎng)絡(luò)鏈路帶寬。虛擬網(wǎng)絡(luò)上的節(jié)點(diǎn)和鏈路能夠在物理網(wǎng)絡(luò)上創(chuàng)建、刪除。網(wǎng)絡(luò)虛擬化已經(jīng)被應(yīng)用于數(shù)據(jù)中心解決擴(kuò)展性、復(fù)雜性、資源利用率等問題。另外,在云計(jì)算環(huán)境中,為了實(shí)現(xiàn)計(jì)算資源的共享、分離與聚合以及資源的易管理性,網(wǎng)絡(luò)虛擬化成為解決這些問題的關(guān)鍵技術(shù)。虛擬網(wǎng)絡(luò)映射問題(VNE)是網(wǎng)絡(luò)虛擬化在資源分配的核心問題。將不同虛擬網(wǎng)絡(luò)的資源包括節(jié)點(diǎn)資源和鏈路資源映射到物理網(wǎng)絡(luò)上。其中,節(jié)點(diǎn)資源一般有CPU、內(nèi)存、地理位置等；鏈路資源有延遲、帶寬等。虛擬網(wǎng)絡(luò)映射的目標(biāo)是在滿足虛擬網(wǎng)絡(luò)資源約束的前提下,將虛擬網(wǎng)絡(luò)嵌入到合適的底層物理網(wǎng)絡(luò)上。在保證虛擬網(wǎng)絡(luò)資源請求的情況下,盡可能的降低虛擬網(wǎng)絡(luò)請求的拒絕率,同時(shí)提高底層物理網(wǎng)絡(luò)的資源收益。虛擬網(wǎng)絡(luò)映射不僅要解決準(zhǔn)入控制、請求排隊(duì)、資源約束問題,還要解決拓?fù)涠鄻有缘榷喾矫娴膯栴}。由于應(yīng)用場景、優(yōu)化目標(biāo)、映射方式和約束條件的不同,虛擬網(wǎng)絡(luò)映射又分為不同類型的優(yōu)化問題。本文基于蟻群算法分別對離線虛擬網(wǎng)絡(luò)映射ACO-VNE和在線虛擬網(wǎng)絡(luò)映射提出了相應(yīng)的映射算法VNE-CACO.對于ACO-VNE算法,屬于兩階段映射算法,首先進(jìn)行節(jié)點(diǎn)映射,然后進(jìn)行鏈路映射。通過判斷映射結(jié)果的好壞,螞蟻將信息素分布于節(jié)點(diǎn)上。螞蟻之間通過信息素進(jìn)行學(xué)習(xí),學(xué)習(xí)前代螞蟻的映射經(jīng)驗(yàn),另外將節(jié)點(diǎn)的資源情況作為啟發(fā)式因子。螞蟻通過輪盤賭選擇節(jié)點(diǎn)映射方案,然后再進(jìn)行鏈路的映射。直到蟻群算法收斂或者達(dá)到設(shè)定的運(yùn)行次數(shù)上限即得到映射解。針對在線虛擬網(wǎng)絡(luò)映射,我們提出了VNE-CACO。VNE-CACO是一種一階段的協(xié)同映射算法。一方面,該算法將物理網(wǎng)絡(luò)拓?fù)渖系年P(guān)鍵路徑作為稀有資源盡量保留,來應(yīng)對后續(xù)的虛擬網(wǎng)絡(luò)請求。另一方面,該算法通過螞蟻之間對映射解空間的探索所遺留的信息素,然后結(jié)合啟發(fā)式因子信息,不斷的向最優(yōu)解靠攏。算法直到收斂或者達(dá)到運(yùn)行的最大代數(shù)停止,獲得最終解。本文對兩種算法均做了詳細(xì)的仿真實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明蟻群算法在解決虛擬網(wǎng)絡(luò)映射問題中具有優(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.
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：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.
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP393.01;TP18
【參考文獻(xiàn)】
相關(guān)期刊論文 前3條
1 朱強(qiáng);王慧強(qiáng);馮光升;呂宏武;王振東;姚崇東;;VNE-ABC:基于人工蜂群的網(wǎng)絡(luò)虛擬化映射算法[J];北京工業(yè)大學(xué)學(xué)報(bào);2014年01期
2 卿蘇德;廖建新;朱曉民;王敬宇;戚琦;;網(wǎng)絡(luò)虛擬化環(huán)境中虛擬網(wǎng)絡(luò)的嵌套映射算法[J];軟件學(xué)報(bào);2012年11期
3 程祥;張忠寶;蘇森;楊放春;;虛擬網(wǎng)絡(luò)映射問題研究綜述[J];通信學(xué)報(bào);2011年10期
，本文編號：2482795
本文鏈接：http://sikaile.net/guanlilunwen/ydhl/2482795.html
最近更新
教材專著
