一種虛擬化分配資源算法的研究

陳南岳

摘要：互聯(lián)網(wǎng)技術為人們的日常生活及工作提供了方便，使人們獲取信息及交換信息更加方便，在互聯(lián)網(wǎng)技術不斷發(fā)展的過程中伴隨著一系列的挑戰(zhàn)。因為互聯(lián)網(wǎng)體系結(jié)構具有多種缺點，并且由多個運營商同時提供，導致互聯(lián)網(wǎng)體系結(jié)構的改革步伐緩慢，互聯(lián)網(wǎng)的發(fā)展也處于瓶頸時期。要想解決互聯(lián)網(wǎng)發(fā)展瓶頸問題，能夠通過網(wǎng)絡虛擬化實現(xiàn)，其能夠支持多種網(wǎng)絡體系結(jié)構、業(yè)務及實驗，網(wǎng)絡虛擬化解決的基本問題就是資源分配，能夠提高基礎設備的使用效率，并且降低資源使用成本，設計基于虛擬化的分配資源算法具有重要的現(xiàn)實意義。

關鍵詞：虛擬化；分配資源；算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）13-0007-03

互聯(lián)網(wǎng)在信息傳播中有著重要的作用，在長時間的發(fā)展過程中，其已經(jīng)被廣泛應用到社會各行各業(yè)中。但是由于互聯(lián)網(wǎng)的規(guī)模不斷擴大，用戶的數(shù)量也在不斷的上升，其缺點也越來越突出。在物聯(lián)網(wǎng)及云計算等全新的技術出現(xiàn)之后，互聯(lián)網(wǎng)架構的發(fā)展也受到了阻礙，比如傳統(tǒng)IP網(wǎng)絡的可擴展性較差，全新的技術無法在目前網(wǎng)絡結(jié)構中部署。為了能夠創(chuàng)建全新的網(wǎng)絡架構，網(wǎng)絡虛擬化技術就產(chǎn)生了，其能夠有效提高資源的使用效率，所以也稱為下代網(wǎng)絡發(fā)展的主要技術。

1淺析資源分配

1.1資源分配的概念

網(wǎng)絡虛擬化包括兩種方式，分別為縱向和橫向。縱向虛擬化主要是將一個物理設備虛擬成為多個不同的小設備，每個小設備能夠獨立使用物理資源，彼此不影響；橫向虛擬化主要是多個物理設備相互聯(lián)合虛擬成為一個大設備，其能夠調(diào)度內(nèi)部的物理設備。這兩種方式的關鍵問題就是資源分配，如果分配資源算法優(yōu)秀，那么能夠有效提高物理資源的使用效率及網(wǎng)絡性能，還能夠降低資源分配的成本，提高網(wǎng)絡的收益。

要想使虛擬網(wǎng)絡能夠使用一個底層物理資源，就要通過資源的分配進行，也就是通過先進的資源映射算法實現(xiàn)虛擬資源到物力資源的映射。資源映射指的是虛擬服務供應商從基礎設備供應商中得到有效資源創(chuàng)建虛擬網(wǎng)絡的過程。虛擬化的資源分配主要包括資源抽象、資源發(fā)現(xiàn)、資源映射及協(xié)調(diào)管理，詳見圖1。

1.2資源分配的目的及特點

資源分配的主要目的是能夠降低物理資源使用率，并且提高虛擬網(wǎng)絡請求。簡單來說，也就是實現(xiàn)降低物理資源使用的同時，提供給眾多虛擬網(wǎng)絡服務。目前，在網(wǎng)絡虛擬化中，資源分配是重要的問題，其能夠滿足虛擬請求及物理資源映射，也是供應商和用戶的橋梁，其主要特點包括：

其一，虛擬網(wǎng)絡請求的差異化。不同虛擬網(wǎng)絡請求具有不同的服務特點，那么網(wǎng)絡結(jié)構及協(xié)議也不同；

其二，異構網(wǎng)絡技術共存。網(wǎng)絡虛擬化為不同的網(wǎng)絡架構和技術提供了共存平臺，所以其能夠支持不同網(wǎng)絡架構及技術，提高網(wǎng)絡的整體靈活性及可用性；

其三，物理資源的共享。網(wǎng)絡虛擬化中的虛擬網(wǎng)絡都是一起使用底層物理資源，資源的分配不僅要最小化物理資源，還要使虛擬請求最大化。

2基于虛擬化的資源分配

2.1虛擬化的資源分配

虛擬化的資源分配指的是InPs在接受SPS服務請求Reg之后創(chuàng)建的虛擬網(wǎng)絡拓撲結(jié)構及資源約束條件，在InPs物理網(wǎng)絡中選擇科學的虛擬資源創(chuàng)建虛擬網(wǎng)絡，此過程就是虛擬化資源分配。詳見圖2：

其中式（1）表示為InPs的物理網(wǎng)絡，V^S為物理節(jié)點的集合，E^S為物理鏈路的集合，R^S_n（i）為在t時間中，物理節(jié)點空間的資源，R^S_l（t為在t時間中，物理鏈路的空閑資源。其中式（2）表示為在i次Req請求時候創(chuàng)建的虛擬網(wǎng)絡，Vv（i）為虛擬網(wǎng)絡的節(jié)點集合，Ev（i）為虛擬網(wǎng)絡的鏈路集合，Rvn（i）為虛擬節(jié)點的資源需求總和，Rvl（i）為虛擬鏈路的資源需求總和。資源分配的整個過程從形式方面分析，可以分為兩個過程，分別為虛擬鏈路資源及虛擬節(jié)點資源兩種分配。在實際的資源分配過程中，這兩種分配過程并不是相互獨立的，如果使整個資源分配問題分為節(jié)點資源及鏈路資源兩種分配，進行先后的解決，得到的結(jié)果并不是最優(yōu)的。

2.2資源分配的典型算法

2.2.1集中式資源分配

集中式資源分配的算法是對虛擬網(wǎng)絡初始資源分配之后的生命周期中，不對分配資源進行改變，其主要特點就是配置一次，能夠終身使用。如果虛擬網(wǎng)絡資源的需求發(fā)生變化，其分配的資源不會發(fā)生變化。如果初始資源分配較多的話，會導致出現(xiàn)資源浪費，相反，就會對虛擬網(wǎng)絡的使用產(chǎn)生影響。所以初始資源的分配要以虛擬網(wǎng)絡資源的需求為基礎。

鏈路及節(jié)點協(xié)調(diào)的資源分配的算法指的是以InPs分配給SPS虛擬網(wǎng)絡的成本為基礎，創(chuàng)建資源分配目標函數(shù)，之后對物理網(wǎng)絡進行拓展，從而改變資源分配，使其成為混合整數(shù)規(guī)劃。由于混合整數(shù)規(guī)劃的計算較為復雜，所以對整數(shù)并沒有較大的約束，以此可以使用確定四舍五入及隨機四舍五入的技術。

但是此算法具有多種問題：首先，在算法平衡的過程中，還提高了資源分配成本；其次，因為算法中的多商品流算法執(zhí)行了兩次，那么算法時間較長。

2.2.2分布式資源分配

分布式虛擬化資源分配算法能夠?qū)崿F(xiàn)分布資源分配通信協(xié)議，此算法能夠通過相關的通信協(xié)議使其中的物理節(jié)點實現(xiàn)資源信息的交互及分配，通過資源信息的交互，物理節(jié)點能夠有效掌握其他節(jié)點的沒有用的空間信息，從而決定自身的分配任務。所有物理節(jié)點都要實現(xiàn)虛擬網(wǎng)絡拓撲的星型分割，資源較大的物理節(jié)點要實現(xiàn)分割的資源分配，并且將結(jié)果通過通信協(xié)議為其他物理節(jié)點所告知，以此使所有物理節(jié)點都能夠掌握資源的使用及分配的進度。

3啟發(fā)式的虛擬化分配資源算法

為了能夠有效解決網(wǎng)絡資源分配的負載及算法效率問題，本文就提出了啟發(fā)式的虛擬化分配資源算法——HVNE，此算法通過虛擬節(jié)點和鏈路的橋梁——虛擬網(wǎng)絡拓撲（VN），能夠統(tǒng)一節(jié)點及鏈路的映射過程，有效完善了映射算法性能較差的問題。另外，其還能夠使同個虛擬請求的多個節(jié)點在同個物理節(jié)點中映射，有效節(jié)約了物理鏈路資源。虛擬化分配資源算法其實就是傳統(tǒng)拓撲分割及無向圖K區(qū)域劃分兩者的理論結(jié)合，從而提出了虛擬拓撲的關聯(lián)因子，有效完善了傳統(tǒng)的星型分割，使其能夠滿足現(xiàn)代網(wǎng)絡的需求。

3.1啟發(fā)式虛擬化分配資源的網(wǎng)絡模型

3.1.1物理網(wǎng)絡模型

物理網(wǎng)絡的表示為無向帶權圖G^S=（N^S，L^S），N^S為物理網(wǎng)絡節(jié)點集合，L^S為物理網(wǎng)絡鏈路集合。在鏈路分配的過程中，具有一條虛擬鏈路在多條集合中映射的情況，那么物理節(jié)點s到d的路徑就通過P^S（s，d）表示，此路徑不僅能夠作為單一鏈路，還能夠作為多鏈路集合。

3.1.2虛擬請求網(wǎng)絡模型

虛擬請求網(wǎng)絡模型和物理網(wǎng)絡模型有多種共同點，都是通過無向帶權圖表示虛擬請求，兩者的不同之處在于，虛擬請求網(wǎng)絡模型中的虛擬請求只有一個P^V，其表示為虛擬請求分配影響物理網(wǎng)絡負載的情況。因為虛擬請求具有不同的特點，網(wǎng)絡延遲較為敏感，所以就能夠調(diào)整P^V，以此能夠?qū)μ摂M節(jié)點和物理節(jié)點映射的密度進行改變，從而節(jié)省網(wǎng)絡寬帶，有效提高了網(wǎng)絡的使用效率。

3.1.3網(wǎng)絡資源的分配流程

在某個虛擬請求到達的時候，物理網(wǎng)絡就要決定是否接受，如果接受，那么物理網(wǎng)絡就要從節(jié)點和鏈路中選擇滿足虛擬請求的路徑和節(jié)點，在虛擬請求消失的時候，其占據(jù)的資源就會釋放。

3.1.4網(wǎng)絡能力因子

通過虛擬請求的特有屬性PV限制網(wǎng)絡負載，使網(wǎng)絡負載能夠平衡，并且提高資源的使用效率，所以要設計網(wǎng)絡能力因子表示節(jié)點和鏈路之間的關系。

首先，節(jié)點資源能力和能力率。節(jié)點資源能力指的是物理節(jié)點的剩余計算能力，也就是節(jié)點的能力因子，公式（5）能夠表示。節(jié)點資源的能利率為節(jié)點資源能力及物理節(jié)點資源能力的最大比值，其能夠反映出節(jié)點資源能力的所有排名，公式（61能夠表示，其中0≤Radio^Cpt（n^S）≤1。

（5）

（6）

其次，節(jié)點通信能力及通信率。因為虛擬節(jié)點映射到節(jié)點中的時候，物理節(jié)點會和其中的物理節(jié)點連接，那么節(jié)點的通信能力值得就是節(jié)點相互連接的物理鏈路能夠使用的寬帶和，表示了節(jié)點的通信能力，公式（7）能夠表示。

（7）

最后，路徑能力。路徑能力指的是物理路徑的能力，通過路徑能力和跳數(shù)的結(jié)合組成，能夠通過公式（8）表示。（8）

3.2啟發(fā)式虛擬化分配資源的算法

3.2.1啟發(fā)式虛擬化分配資源的算法

啟發(fā)式虛擬化分配資源的算法一共有八個步驟，圖3為啟發(fā)式虛擬化分配資源的算法流程。

（1）在虛擬請求到達的時候，物理網(wǎng)絡要檢查是否具有滿足虛擬請求的鏈路和節(jié)點資源。如果滿足，那么就接受虛擬請求，進行下一個步驟；如果不滿足，就要將虛擬請求當人到隊列的末尾，等待其他資源；

（2）生成虛擬請求已經(jīng)映射的節(jié)點列表NodeList及路徑分類列表PathList，使其能夠存儲已經(jīng)映射的虛擬節(jié)點和鏈路之間的最短路徑；根據(jù)虛擬請求的節(jié)點需求能力，實現(xiàn)虛擬請求的降序排列，以此得到VnNodeList，尋找能夠被節(jié)點使用的資源比節(jié)點需求要大的物理節(jié)點，以此形成能夠使用的物理節(jié)點列表，之后降序排列；在VnNodeLise中設置虛擬節(jié)點序號（i=-[i﹤number]），進入下一個步驟；

（3）根據(jù)步驟2得到的分配節(jié)點序號i的鄰居節(jié)點列表及映射節(jié)點列表和路徑分裂列表的交際，得出i的鄰居節(jié)點列表MapedNeighborNodeList，如果其不是空集，那么就能夠根據(jù)MapedNeighborNodeList生成需求的映射鏈路列表，根據(jù)映射鏈路列表的寬帶需求，實現(xiàn)MapedNeighborNodeList的降序排序，設置分配節(jié)點序號i的鄰居節(jié)點序號（j=0[i﹤number]），進入下一個步驟；否則，就要對物理節(jié)點序號進行設置（k=0[k﹤num-ber]），進入第七個步驟；

（4）判斷i的映射物理節(jié)點（map（i））是否能夠承載i，如果能承載，就進入下一步；如果不能承載，就要使i=j+1；

（5）判斷i在map（i）映射的前后負載及網(wǎng)絡復雜的差異是否比虛擬資源的PV要大，如果大于，那么就是j=j+1，返回上一步；如果不大于，就進入的下一步；

（6）通過k最短路徑算法，判斷map（i）鏈路資源是否能夠承載鏈路映射列表中的鏈路，如果可以，那么就使i映射到map（i）中，得到鏈路映射列表中鏈路的映射路徑，存人到路徑分類列表中；如果不能，就使j=i+1，返回到第四個步驟；

（7）求出物理節(jié)點的綜合能力，判斷其是否為最大的，如果是，那么就要將i映射到物理節(jié)點中，更新物理節(jié)點列表，通過k最短路徑算法，得到鏈路映射列表的最短路徑，進人下一步；否則就要使物理節(jié)點（k）=k+1；

（8）通過鏈路映射列表，在路徑分類列表中找到相應的映射路徑，實現(xiàn)鏈路的映射。之后使i=i+1，判斷i能夠成為虛擬節(jié)點的最后，如果是，那么虛擬資源的映射就是成功的；如果不是，就要返回第三個步驟。

4結(jié)束語

資源的分配是網(wǎng)絡虛擬化要面臨的重要任務，資源分配的有效性關乎到物理網(wǎng)絡的負載是否均衡，是否能夠有效提高物理網(wǎng)絡資源的使用效率，并且還能夠提高物理網(wǎng)絡中虛擬網(wǎng)絡的數(shù)量，降低了資源實用的成本?；诖耍疚木椭饕芯苛司W(wǎng)絡虛擬化資源分配的問題，并且介紹了資源分配的典型算法，最后提出了一種啟發(fā)式虛擬化分配資源的算法，并且對其進行了模型創(chuàng)建及描述，使其能夠有效處理網(wǎng)絡中的故障問題，保持網(wǎng)絡運行的穩(wěn)定性。