陳南岳

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

關(guān)鍵詞：虛擬化；分配資源；算法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）13-0007-03

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

1淺析資源分配

1.1資源分配的概念

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

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

1.2資源分配的目的及特點(diǎn)

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

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

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

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

2基于虛擬化的資源分配

2.1虛擬化的資源分配

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

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

2.2資源分配的典型算法

2.2.1集中式資源分配

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

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

但是此算法具有多種問題：首先，在算法平衡的過程中，還提高了資源分配成本；其次，因?yàn)樗惴ㄖ械亩嗌唐妨魉惴▓?zhí)行了兩次，那么算法時(shí)間較長。

2.2.2分布式資源分配

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

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

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

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

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

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

3.1.2虛擬請(qǐng)求網(wǎng)絡(luò)模型

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

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

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

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

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

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

（5）

（6）

其次，節(jié)點(diǎn)通信能力及通信率。因?yàn)樘摂M節(jié)點(diǎn)映射到節(jié)點(diǎn)中的時(shí)候，物理節(jié)點(diǎn)會(huì)和其中的物理節(jié)點(diǎn)連接，那么節(jié)點(diǎn)的通信能力值得就是節(jié)點(diǎn)相互連接的物理鏈路能夠使用的寬帶和，表示了節(jié)點(diǎn)的通信能力，公式（7）能夠表示。

（7）

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

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

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

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

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

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

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

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

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

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

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

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

4結(jié)束語

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