一種基于負(fù)載均衡的虛擬網(wǎng)絡(luò)資源分配的新算法
相關(guān)鏈接： 中國安全網(wǎng) 中國質(zhì)量網(wǎng) 中國論文網(wǎng) 中國資訊網(wǎng)
作者：鄭曉敏
1 引言
軟件定義網(wǎng)絡(luò)(software defined networking，SDN)技術(shù)具有控制與傳輸分離、集中式控制和軟件可定義的特征，能夠克服IP承載網(wǎng)結(jié)構(gòu)僵化問題，便于在IP承載網(wǎng)中快速開發(fā)并部署新型業(yè)務(wù)，并能為不同業(yè)務(wù)定義網(wǎng)絡(luò)控制與管理策略，應(yīng)用SDN技術(shù)的軟件定義承載網(wǎng)(carrier-SDN)成為目前國內(nèi)外研究的重點(diǎn)。carrier-SDN中針對不同業(yè)務(wù)定義的網(wǎng)絡(luò)控制與管理策略之間不能相互沖突，需應(yīng)用網(wǎng)絡(luò)虛擬化技術(shù)實(shí)例化相互隔離的虛擬網(wǎng)絡(luò)，在虛擬網(wǎng)絡(luò)上部署新業(yè)務(wù)，并面向業(yè)務(wù)個(gè)性化需求開發(fā)控制與管理策略[31，應(yīng)用網(wǎng)絡(luò)虛擬化技術(shù)實(shí)現(xiàn)虛擬網(wǎng)絡(luò)資源分配的虛擬網(wǎng)絡(luò)映射算法成為carrier-SDN研究的重點(diǎn)。
虛擬網(wǎng)絡(luò)映射算法將虛擬節(jié)點(diǎn)和虛擬鏈路分別映射在carrier-SDN的物理節(jié)點(diǎn)和由物理鏈路連接構(gòu)成的物理路徑上，在物理節(jié)點(diǎn)和物理路徑上預(yù)留計(jì)算資源和帶寬資源，實(shí)例化虛擬網(wǎng)絡(luò)。由于carrier-SDN中上層IP交換網(wǎng)絡(luò)承載在下層光傳輸網(wǎng)絡(luò)上，因此首先需建立carrier-SDN的多層網(wǎng)絡(luò)模型。針對虛擬網(wǎng)絡(luò)映射算法，提出以占用網(wǎng)絡(luò)資源最小為優(yōu)化目標(biāo)，當(dāng)網(wǎng)絡(luò)負(fù)載較小時(shí)具有較好性能，但當(dāng)負(fù)載增加時(shí)，物理網(wǎng)絡(luò)中會(huì)出現(xiàn)瓶頸的節(jié)點(diǎn)和鏈路，造成算法性能急劇下降。因此，以負(fù)載均衡為優(yōu)化目標(biāo)的映射算法能夠在網(wǎng)絡(luò)負(fù)載較高時(shí)獲得較好性能。參考文獻(xiàn)中的LB-ILP-VNE算法提出應(yīng)用整數(shù)線性規(guī)劃解決負(fù)載均衡虛擬網(wǎng)絡(luò)映射問題，雖然能夠獲得確定的最優(yōu)解，但是算法復(fù)雜度較高。參考文獻(xiàn)中的LB-G-VNE
算法應(yīng)用貪婪算法求解，雖然算法運(yùn)行時(shí)間短，但是所求解會(huì)隨著網(wǎng)絡(luò)狀態(tài)變化，影響算法性能。考慮到粒子群優(yōu)化算法能夠在解空間多個(gè)域中同時(shí)展開搜索，具有簡單、高效的特征，參考文獻(xiàn)中的LB-DPSO-VNE算法提出應(yīng)用粒子群算法，雖然算法性能較好，但是大量的集合運(yùn)算會(huì)造成算法運(yùn)行時(shí)間過長。
基于此，本文提出carrier-SDN中基于負(fù)載均衡的虛擬網(wǎng)絡(luò)資源分配算法。首先，建立carrier-SDN多層網(wǎng)絡(luò)模型，反映carrier-SDN上層IP交換網(wǎng)絡(luò)與下層光傳輸網(wǎng)絡(luò)間的映射關(guān)系：其次，根據(jù)映射算法的特點(diǎn)，提出一種粒子群算法的二值化方法．保證每個(gè)粒子中1的個(gè)數(shù)始終一致，反映虛擬網(wǎng)絡(luò)請求中虛擬節(jié)點(diǎn)個(gè)數(shù)保持不變的特征；最后，以負(fù)載均衡為優(yōu)化目標(biāo)，應(yīng)用二值粒子群算法求解虛擬節(jié)點(diǎn)映射的解，應(yīng)用Dijkstra算法構(gòu)建carrier-SDN路徑集合，確定承載虛擬鏈路的傳輸路徑，實(shí)例化虛擬網(wǎng)絡(luò)請求。
2 carrier-SDN多層網(wǎng)絡(luò)模型
carrier-SDN包含IP交換網(wǎng)和光傳輸網(wǎng)絡(luò)，IP交換網(wǎng)承載在光傳輸網(wǎng)絡(luò)中，虛擬網(wǎng)絡(luò)請求被接納在IP交換網(wǎng)上，且用戶連接到IP交換網(wǎng)中，carrier-SDN被抽象為多層網(wǎng)絡(luò)模型，如圖1所示。
carrier-SDN底層網(wǎng)絡(luò)記為O_substrate，上層網(wǎng)絡(luò)記為P_suibstrate，底層網(wǎng)絡(luò)中包含的節(jié)點(diǎn)和鏈路分別記為O_node和O_tin,k．上層網(wǎng)絡(luò)中包含的節(jié)點(diǎn)和鏈路分別記為P_n,ode和P_link。
上層網(wǎng)絡(luò)中相鄰交換機(jī)之間的路徑包括多條傳輸路徑，是一組傳輸路徑的集合，表示為{P_lin,k(iJ)}，其中，ij為鏈路集合中所有鏈路的端點(diǎn)，P_lin,k表示{P_lin,k(i,j))集合中的任意一條傳輸鏈路。由于上層中的鏈路承載在光傳輸網(wǎng)絡(luò)中由光傳輸鏈路相互連接構(gòu)成的光傳輸路徑上，將光傳輸路徑表示為
由于下層光傳輸網(wǎng)絡(luò)每次為在其上建立的路徑分配一個(gè)波長，此時(shí)上層IP交換網(wǎng)絡(luò)的鏈路帶寬也是一個(gè)波長，即：Vi,j，k，Bdw(P_lin,k :)=wcwele，z,gth，上層交換機(jī)i、j之間建立了一條傳輸路徑。如果任意P_linkkij上的剩余資源較多，能夠滿足虛擬網(wǎng)絡(luò)請求的帶寬，則在上層網(wǎng)絡(luò)中為虛擬鏈路計(jì)算一條傳輸路徑，將虛擬鏈路承載在這條傳輸路徑上，即:
3 carrier-SDN中基于負(fù)載均衡的虛擬網(wǎng)絡(luò)資源分配算法
3.1 carrier-SDN資源分配機(jī)制
carrier-SDN資源分配機(jī)制流程描述如下。
步驟1 當(dāng)carrier-SDN上沒有承載任何虛擬網(wǎng)絡(luò)請求時(shí)，其IP交換網(wǎng)絡(luò)中沒有傳輸鏈路。
步驟2 當(dāng)虛擬網(wǎng)絡(luò)請求到達(dá)carrier-SDN時(shí)，應(yīng)用虛擬網(wǎng)絡(luò)映射算法確定承載虛擬節(jié)點(diǎn)的IP交換網(wǎng)絡(luò)中交換機(jī)的位置，并為虛擬節(jié)點(diǎn)分配計(jì)算資源。
步驟3根據(jù)虛擬節(jié)點(diǎn)映射方案，在carrier-SDN的IP交換網(wǎng)中計(jì)算連接交換機(jī)的路徑。
·如果在IP交換網(wǎng)上能夠計(jì)算出傳輸路徑，則將虛擬 鏈路承載在P-path上。
·如果IP交換網(wǎng)上沒有滿足虛擬鏈路帶寬請求的路徑，在下層光傳輸網(wǎng)絡(luò)中計(jì)算一條光傳輸路徑，并在IP交換網(wǎng)中建立直連鏈路，為該直連路徑分配一個(gè)波長作為傳輸帶寬,O-path中包含的O_pathp上相應(yīng)地減去一個(gè)波長，再將虛擬鏈路承載在直連鏈路上。
步驟4當(dāng)虛擬網(wǎng)絡(luò)請求離開網(wǎng)絡(luò)時(shí)，釋放虛擬節(jié)點(diǎn)、虛擬鏈路占用的計(jì)算資源和帶寬資源。
步驟5如果carrier-SDN上層IP交換網(wǎng)中任何一條傳輸鏈路沒有承載虛擬鏈路，則拆除分組交換網(wǎng)中的鏈路，釋放承載該IP交換網(wǎng)鏈路的波長到光傳輸網(wǎng)絡(luò)中對應(yīng)的路徑上。
3.2虛擬網(wǎng)絡(luò)映射算法建模
虛擬網(wǎng)絡(luò)映射算法需要滿足資源約束、二值約束條件。資源約束是服務(wù)器上的剩余計(jì)算資源需滿足虛擬節(jié)點(diǎn)請求的計(jì)算資源，carrier-SDN傳輸路徑鏈路上的剩余帶寬資源需滿足虛擬鏈路請求的帶寬資源。
其中，u和(u，u)指虛擬節(jié)點(diǎn)標(biāo)號和虛擬鏈路，Nv和Lv指虛擬網(wǎng)絡(luò)請求的虛擬節(jié)點(diǎn)集合和虛擬鏈路集合。i和(i,j)指carrier-SDN中的節(jié)點(diǎn)標(biāo)號和傳輸鏈路，Ns和Ls指carrier-SDN上層IP交換網(wǎng)的交換機(jī)集合和鏈路集合。虛擬節(jié)點(diǎn)u映射在連接到carrier-SDN的服務(wù)器i上時(shí)xui為1，否則為O。com(u)指虛擬節(jié)點(diǎn)M請求的計(jì)算資源，com(i)指服務(wù)器i上的剩余計(jì)算資源。虛擬鏈路(u,v)映射在carrier-SDN傳輸鏈路(i,j)上時(shí)fwij為1，否則為O。bw(u，v)指虛擬鏈路(u，v)請求的帶寬資源，bw(i,j)指傳輸鏈路(i,j)的剩余帶寬資源。
二值約束：虛擬節(jié)點(diǎn)只能映射在服務(wù)器上；虛擬鏈路只能映射在物理鏈路上；同一個(gè)虛擬網(wǎng)絡(luò)中的虛擬節(jié)點(diǎn)不能同時(shí)映射在同一個(gè)服務(wù)器上；一個(gè)虛擬節(jié)點(diǎn)只能映射在一個(gè)服務(wù)器上。計(jì)算式表示如下：
3.3負(fù)載均衡虛擬網(wǎng)絡(luò)映射算法
3.3.1目標(biāo)函數(shù)
基于負(fù)載均衡的虛擬網(wǎng)絡(luò)映射算法的目標(biāo)函數(shù)用carrier-SDN上連接的服務(wù)器剩余計(jì)算資源和carrier-SDN鏈路剩余帶寬資源的最小標(biāo)準(zhǔn)方差表示二其中.SN表示服務(wù)器總個(gè)數(shù)，N表示鏈路總個(gè)數(shù)。
3.3.2應(yīng)用二值粒子群優(yōu)化的負(fù)載均衡虛擬網(wǎng)絡(luò)映射算法
本文算法將虛擬網(wǎng)絡(luò)映射問題分解為虛擬節(jié)點(diǎn)映射和虛擬鏈路映射，應(yīng)用二值粒子群優(yōu)化算法求解虛擬節(jié)點(diǎn)映射方案，再在應(yīng)用Dijkstra算法構(gòu)建的路徑集合Ps中選擇carrier-SDN路徑，承載虛擬鏈路。
(1)應(yīng)用二值粒子群優(yōu)化的負(fù)載均衡虛擬節(jié)點(diǎn)映射算法建模
粒子群算法中，每個(gè)粒子為一個(gè)向量Xk，表示一個(gè)可能的最優(yōu)解，在求解虛擬節(jié)點(diǎn)映射方案時(shí)，xk,ui表示第k個(gè)解中，將虛擬節(jié)點(diǎn)u映射到服務(wù)器上，其適應(yīng)度函數(shù)定義為服務(wù)器剩余計(jì)算資源的標(biāo)準(zhǔn)方差。
此時(shí)，粒子為VNxSN維，粒子總數(shù)為K個(gè)，ptk,ui為粒子進(jìn)化過程中的最優(yōu)位置,pg,。為所有粒子進(jìn)化過程中的最優(yōu)位置，
為粒子的速度，每個(gè)粒子按照如下計(jì)算式進(jìn)化并更新位置。
其中，k為自然數(shù)，且1≤k≤K;w為慣性參數(shù)，取實(shí)數(shù)；CI、C2為加速因子，取實(shí)數(shù)；r1、r2為服從(0，1)均勻分布的隨機(jī)數(shù)；wmax、wmin為慣性參數(shù)的最大值和最小值；iter為算法當(dāng)前迭代次數(shù)。
Xk,ui的二值化方法如下。
初始化：u=l，i=1；對所有u、i，計(jì)算：
(2)應(yīng)用二值粒子群優(yōu)化的虛擬節(jié)點(diǎn)映射算法虛擬節(jié)點(diǎn)映射算法的詳細(xì)流程描述如下。
步驟1 設(shè)定粒子數(shù)為50，最大迭代次數(shù)為500。
步驟2初始化粒子的初始位置{xok,ui}和
黝初始速度，以適應(yīng)度函數(shù)計(jì)算本地最優(yōu)粒子{pOk,ui）和全局最優(yōu)粒子{pOg,ui}。
步驟3在粒子進(jìn)化的第t代，基于式(9)刷新粒子速度utk,ui，并應(yīng)用粒子二值化方法，確定粒子位置X。根據(jù)適應(yīng)度函數(shù)計(jì)算本地最優(yōu)粒子和全局最優(yōu)粒子，并令t=t+1。
步驟4如果t<迭代次數(shù)上限ite rmax，轉(zhuǎn)至步驟3，否則轉(zhuǎn)至步驟5。
步驟5基于負(fù)載均衡的虛擬節(jié)點(diǎn)映射算法的解為ptg,ui集合。
(3)虛擬鏈路映射
在虛擬節(jié)點(diǎn)映射方案確定后，在承載虛擬節(jié)點(diǎn)的交換機(jī)對之間，以虛擬鏈路請求帶寬資源為約束條件，應(yīng)用Dijkstra算法構(gòu)建傳輸路徑集合，以carrier-SDN鏈路的剩余帶寬資源的標(biāo)準(zhǔn)方差最小為目標(biāo)，選取傳輸路徑，并將虛擬鏈路映射在carrier-SDN上。
在構(gòu)建carrier-SDN路徑時(shí)，應(yīng)用基于負(fù)載均衡的Dijkstra算法，計(jì)算傳輸路徑集合Ps，Ps={P_path。
步驟1 定義carrier-SDN中網(wǎng)絡(luò)節(jié)點(diǎn)之間有連接鏈路時(shí)，節(jié)點(diǎn)之間的距離，否則定義。
屬于集合P的網(wǎng)絡(luò)節(jié)點(diǎn)i，使得{P）={p}U{i}。如果{P}中包含了carrier-SDN中所有網(wǎng)絡(luò)節(jié)點(diǎn)，停止遍歷，否則轉(zhuǎn)至步驟4。
步驟4對有所有不屬于{P）的網(wǎng)絡(luò)節(jié)點(diǎn)j，定義Dj=min{Dj，dji,+Di}，更新Dj后返回步驟3。
記錄計(jì)算所得的任意服務(wù)器之間的路徑，作為carrier-SDN路徑集合Ps中的元素。
如果carrier-SDN傳輸路徑集合構(gòu)建失敗，則虛擬鏈路映射失敗，對應(yīng)的虛擬網(wǎng)絡(luò)請求被阻塞。當(dāng)且僅當(dāng)虛擬鏈路映射成功后，為虛擬節(jié)點(diǎn)和虛擬鏈路分配請求的計(jì)算資源和帶寬資源。
4 仿真與性能分析
4.1 仿真環(huán)境
設(shè)定carrier-SDN底層光傳輸網(wǎng)包括100個(gè)交換節(jié)點(diǎn)，節(jié)點(diǎn)間的連接概率為0.1。相連的交換節(jié)點(diǎn)間配置32根光纖，每個(gè)光纖包含16個(gè)波長，每波長包括5 Gbit/s傳輸帶寬。上層分組交換網(wǎng)包含100個(gè)交換節(jié)點(diǎn)，與光傳輸網(wǎng)的交換節(jié)點(diǎn)對應(yīng)。配置100個(gè)與carrier-SDN連接的服務(wù)器，與分組交換網(wǎng)的交換節(jié)點(diǎn)一一相連，每個(gè)服務(wù)器的計(jì)算資源總量設(shè)為2 500。虛擬網(wǎng)絡(luò)請求的虛擬節(jié)點(diǎn)數(shù)和虛擬鏈路跳數(shù)服從(1，10)的均勻分布，節(jié)點(diǎn)和鏈路分別請求的計(jì)算和帶寬資源皆服從均值為500、方差為0.5的正態(tài)分布，帶寬資源單位為Mbit/s。設(shè)定虛擬網(wǎng)絡(luò)請求間隔時(shí)間服從參數(shù)為1的泊松分布，通過修改成功映射的虛擬網(wǎng)絡(luò)請求持續(xù)時(shí)間服從的參數(shù)，模擬網(wǎng)絡(luò)負(fù)載。針對每一個(gè)確定的網(wǎng)絡(luò)負(fù)載，模擬產(chǎn)生10 000個(gè)虛擬網(wǎng)絡(luò)請求。
仿真過程中，將所提算法記為LB-PSO-VNE，并與參考文獻(xiàn)中的算法進(jìn)行比較，從虛擬網(wǎng)絡(luò)負(fù)載均衡、請求接受率、收益代價(jià)比、網(wǎng)絡(luò)收益幾個(gè)方面進(jìn)行對比分析。
4.2性能分析
圖2為LB-PSO-VNE算法與對比算法關(guān)于負(fù)載均衡的對比曲線。
從圖2可以看出，LB-PSO-VNE算法中carrier-SDN鏈路帶寬剩余資源的標(biāo)準(zhǔn)方差和連接到carrier-SDN的服務(wù)器的剩余計(jì)算資源的標(biāo)準(zhǔn)方差比其他對比算法更小，這是因?yàn)楸疚乃惴軌蛟谔摂M網(wǎng)絡(luò)映射的解空間中獲得更優(yōu)解，保證鏈路剩余帶寬和服務(wù)器剩余計(jì)算資源分布得更均勻。由于carrier-SDN中的鏈路條數(shù)遠(yuǎn)遠(yuǎn)大于服務(wù)器的個(gè)數(shù)，在構(gòu)建carrier-SDN路徑集合時(shí)，一些鏈路并不能被充分利用，使得各算法對應(yīng)的鏈路剩余帶寬的標(biāo)準(zhǔn)方差大于服務(wù)器上剩余計(jì)算資源的標(biāo)準(zhǔn)方差。
圖3為算法關(guān)于虛擬網(wǎng)絡(luò)請求接受率的對比曲線。虛擬網(wǎng)絡(luò)請求接受率定義為成功映射的虛擬網(wǎng)絡(luò)個(gè)數(shù)與虛擬網(wǎng)絡(luò)請求總數(shù)的比值。
從圖3可以看出，在負(fù)載確定的條件下，本文算法能夠保證carrier-SDN中的帶寬資源和服務(wù)器上的計(jì)算資源分布更均勻，虛擬網(wǎng)絡(luò)的請求接受率更高。使用粒子群算法獲得虛擬節(jié)點(diǎn)映射的全局最優(yōu)解，剩余計(jì)算資源分布更均勻，并采用鏈路剩余帶寬最大來構(gòu)建carrier-SDN路徑，剩余帶寬資源分布更為均衡。當(dāng)網(wǎng)絡(luò)負(fù)載增加時(shí)，可用資源減少，無法滿足虛擬網(wǎng)絡(luò)請求的概率增加，請求接受率下降。
圖4為算法關(guān)于收益代價(jià)比的對比曲線。收益代價(jià)比定義為被成功映射的虛擬網(wǎng)絡(luò)請求資源總量與carrier-SDN為映射的虛擬網(wǎng)絡(luò)分配的網(wǎng)絡(luò)資源總量的比值。
從圖4可以看出．LB-PSO-VNE算法為了使連接到carrier-SDN的服務(wù)器上的剩余資源分布得更加均勻，虛擬節(jié)點(diǎn)映射將較為分散，使得連接虛擬節(jié)點(diǎn)的虛擬鏈路計(jì)算的物理路徑平均跳數(shù)反而較大，且該算法會(huì)使鏈路剩余帶寬和服務(wù)器剩余計(jì)算資源的分布更為均勻，最終使得其收益代價(jià)比較小。
圖5所示為算法關(guān)于網(wǎng)絡(luò)收益的對比曲線。網(wǎng)絡(luò)收益定義為成功映射在carrier-SDN上的虛擬網(wǎng)絡(luò)分配的網(wǎng)絡(luò)資源總和。因計(jì)算資源與帶寬資源量綱不同，故為二者設(shè)定不同的加權(quán)系數(shù)a和β。
從圖5可以看出，隨著網(wǎng)絡(luò)負(fù)載的增加，網(wǎng)絡(luò)收益遞增。當(dāng)網(wǎng)絡(luò)負(fù)載大于0.8時(shí)，carrier-SDN中出現(xiàn)節(jié)點(diǎn)和鏈路碎片，請求接受率下降，網(wǎng)絡(luò)收益增速下降。在相同網(wǎng)絡(luò)負(fù)載下，本文算法的虛擬網(wǎng)絡(luò)請求接受率較高，對應(yīng)網(wǎng)絡(luò)收益更高。由于carrier-SDN鏈路條數(shù)遠(yuǎn)大于服務(wù)器個(gè)數(shù)，且承載虛擬鏈路的物理路徑由多條鏈路互聯(lián)組成，使得帶寬資源對網(wǎng)絡(luò)收益影響較大，更大的帶寬資源權(quán)重將獲得更高網(wǎng)絡(luò)收益。
5 結(jié)束語
本文提出carrier-SDN中基于負(fù)載均衡的虛擬網(wǎng)絡(luò)資源分配算法。首先，建立carrier-SDN多層網(wǎng)絡(luò)模型；其次，根據(jù)carrier-SDN上層IP交換網(wǎng)絡(luò)與下層光傳輸網(wǎng)絡(luò)之間的映射關(guān)系建立資源分配機(jī)制，并建立算法模型；最后，詳細(xì)描述了負(fù)載均衡虛擬網(wǎng)絡(luò)映射算法。算法中，首先定義了負(fù)載均衡的優(yōu)化目標(biāo)；其次，應(yīng)用二值粒子群優(yōu)化算法求解虛擬節(jié)點(diǎn)映射方案；最后，以剩余帶寬最大為約束，應(yīng)用負(fù)載均衡Dijkstra算法建立備選的傳輸路徑集合，并選擇合適路徑承載虛擬鏈路。仿真結(jié)果表明，該算法在網(wǎng)絡(luò)負(fù)載較高時(shí)，能實(shí)現(xiàn)較佳的網(wǎng)絡(luò)負(fù)載均衡，具有較好的虛擬網(wǎng)絡(luò)請求接受率和網(wǎng)絡(luò)收益，運(yùn)行效率較高。
6摘要：
在具有集中式控制特點(diǎn)的carrier-SDN（軟件定義承載網(wǎng)）中應(yīng)用網(wǎng)絡(luò)虛擬化技術(shù)為虛擬網(wǎng)絡(luò)分配資源，實(shí)現(xiàn)承載網(wǎng)資源分配是解決承載網(wǎng)結(jié)構(gòu)僵化的重要途徑。提出camer-SDN中基于負(fù)載均衡的虛擬網(wǎng)絡(luò)資源分配算法。首先，建立camer-SDN多層模型；其次，根據(jù)虛擬網(wǎng)絡(luò)映射算法的特點(diǎn)，二值化粒子群優(yōu)化算法；最后，以負(fù)載均衡為優(yōu)化目標(biāo)，求解虛擬網(wǎng)絡(luò)映射問題。仿真結(jié)果表明，與已有方法相比，所提算法在虛擬網(wǎng)絡(luò)負(fù)載均衡性、請求接受率和網(wǎng)絡(luò)收益方面性能優(yōu)越。
