多纖芯彈性光網(wǎng)絡中虛擬網(wǎng)絡映射模型及算法

宋俊輝, 謝 華, 高海龍

(1.信陽師范學院 計算機與信息技術(shù)學院, 河南 信陽 464000;2.信陽職業(yè)技術(shù)學院 檢驗學院, 河南 信陽 464000;3.中國人民解放軍68128部隊, 甘肅 武威 733200)

0 引言

隨著大數(shù)據(jù)、云計算等新型業(yè)務的快速發(fā)展，導致現(xiàn)有光網(wǎng)絡架構(gòu)難以滿足網(wǎng)絡業(yè)務多樣、動態(tài)和突發(fā)等需求.網(wǎng)絡虛擬化應運而生，它可以靈活地為連接請求分配帶寬，無需對傳統(tǒng)網(wǎng)絡架構(gòu)進行很大改動就能獲得較高的頻譜利用率，滿足用戶的多樣化需求.通過邏輯隔離的多個虛擬網(wǎng)絡共享底層物理網(wǎng)絡資源，可實現(xiàn)網(wǎng)絡資源的彈性管理，加快網(wǎng)絡新技術(shù)的開發(fā)與部署，有效地增加資源利用率[1,2].

近年來已經(jīng)有越來越多的研究關(guān)注于彈性光網(wǎng)絡的虛擬化，并對其進行了深入研究.網(wǎng)絡虛擬化的難點在于如何設計高效的虛擬結(jié)點、鏈路的映射及頻譜分配方案以達到某種預期的目的[3].為解決虛擬網(wǎng)絡節(jié)點映射問題，文獻[4]提出了一種整數(shù)線性規(guī)劃模型和一種基于業(yè)務矩陣的映射算法以得到最優(yōu)的方案.文獻[5]研究了網(wǎng)絡虛擬化環(huán)境下的跨域虛擬網(wǎng)絡映射，分別提出了基于OWL及SWRL的資源匹配算法和基于遺傳算法的虛擬網(wǎng)絡劃分算法.文獻[6]根據(jù)虛擬網(wǎng)絡帶寬需求將物理網(wǎng)絡抽象為多個分層輔助圖，應用最短路徑算法在分層輔助圖上進行虛鏈路，提高鏈路映射效率，但是未考慮物理承載節(jié)點特性和鏈路負載對映射的影響.文獻[7]建立了兩個整數(shù)線性規(guī)劃模型，并提出了基于貪心策略的虛擬網(wǎng)絡映射算法，以減少最小化網(wǎng)絡的最大占用頻隙號.文獻[8]利用節(jié)點介數(shù)中心性，將實時感知的網(wǎng)絡狀態(tài)作為選路因子，采用K最短路算法進行映射虛鏈路.由于該算法并未考慮鏈路頻譜使用狀態(tài)的影響而導致部分物理鏈路承載過重.

已有相關(guān)文獻旨在最小化網(wǎng)絡的能耗或網(wǎng)絡最大占用頻隙號等目標，然而頻譜也是彈性光網(wǎng)絡中的一種重要資源，因此本文研究了最小化網(wǎng)絡中的占用資源數(shù)及最小化最大占用頻隙號為目標的虛擬網(wǎng)絡映射問題，建立了一個混合規(guī)劃模型，并提出了一種有效的全局優(yōu)化算法以得到最優(yōu)的虛擬結(jié)點映射、虛擬鏈路映射及選路方案.

1 問題描述與建模

1.1 網(wǎng)絡與業(yè)務描述

無向圖G=(V,E)表示一個物理彈性光網(wǎng)絡，其中V={v1,v2,…,vNv}表示物理彈性光網(wǎng)絡中的結(jié)點集合，N是物理網(wǎng)絡中結(jié)點的個數(shù).對于每個物理結(jié)點vi(vi∈V),都有h(vi)個虛擬機.E={Lij|vi,vj∈V}表示物理網(wǎng)絡中鏈路的集合，Lij是結(jié)點vi和結(jié)點vj之間的鏈路，NE是鏈路的條數(shù).F={f1,f2,…,fNf}是一系列可用頻隙，Nf是每個鏈路上可用頻隙的個數(shù)，假設每個頻隙具有相同的帶寬Cfs.

1.2 問題建模

本研究旨在為確定最優(yōu)的節(jié)點映射、鏈路映射及頻譜分配方案，以使得為所有業(yè)務請求分配頻譜后所占用總的頻隙最少.為此建立一個帶有約束的全局優(yōu)化模型，下面給出研究問題的數(shù)學模型.

目標函數(shù)：為所有業(yè)務請求分配頻譜后所占用的頻譜數(shù)最少且最大占用頻隙號最小.目標函數(shù)可以表示為

(1)

虛擬結(jié)點映射滿足的約束條件：(1)所有的虛擬節(jié)點必須映射到一個物理結(jié)點上；(2)同一個虛擬網(wǎng)中的虛擬結(jié)點不能映射到同一個物理結(jié)點上；(3)映射到同一個物理結(jié)點上的虛擬結(jié)點數(shù)不大于該物理結(jié)點上的虛擬機的數(shù)量.因此有：

研究手段：以錯誤分析理論為指導在整個學年的口譯課上，對老師當堂布置的口譯任務中學生出現(xiàn)的錯誤進行記錄，同時對整個學年當中，學生課后口譯錄音作業(yè)中所出現(xiàn)的錯誤也進行了記錄，最后分類、歸納、整理。

(2)

(3)

(4)

頻譜分配滿足約束條件：(a)業(yè)務請求只能占用聯(lián)通原結(jié)點和宿結(jié)點所有通路中的一條路徑；(b)業(yè)務在所占路徑中的不同鏈路上具有相同的的起始頻隙號；(c)一個業(yè)務請求必須占用若干個連續(xù)的頻隙；(d)任意兩個業(yè)務所占用的頻譜無重疊.

(5)

(6)

(7)

(8)

2 全局優(yōu)化遺傳算法

遺傳算法在工程技術(shù)領域等實際應用問題中得到了廣泛的應用，尤其是解決NP組合優(yōu)化問題中更是表現(xiàn)出了其優(yōu)良的性能[9].因此，本文設計了一種新的全局優(yōu)化遺傳算法來求解本文提出的最大化服務質(zhì)量的可分任務調(diào)度模型.

2.1 編碼與解碼

采用首次適應策略(First Fit, FF)進行頻譜分配，因此只需要對虛擬節(jié)點映射和選路進行編碼.

(9)

(10)

2.2 交叉與變異算子

交叉操作是遺傳算法的主要進化手段，通過兩兩染色體基因交叉互換，繁殖兩個新的子代個體，并將父代好的基因遺傳至子代個體，產(chǎn)生的子代個體可能會優(yōu)于父代個體.交叉操作保持了遺傳算法種群個體的多樣性和全局搜索能力.本文采用兩點交叉方式生成新個體：隨機生成兩個整數(shù)j1和j2滿足2≤j1≤j2≤N′(對選路個體進行交叉時2≤j1≤j2≤NR′)作為交叉點，將兩個父代個體交叉點之間的基因進行交換，生成兩個后代個體.

變異算子通過一定概率的基因變異，可以在一定程度上提高多樣性，強化了算法搜索到最優(yōu)解的能力.本文采用單點變異方式生成新個體：隨機生成一個整數(shù)j1滿足2≤j3≤N′(對選路個體進行交叉時2≤j3≤NR′)作為變異點，將個體在該點的基因位取反，產(chǎn)生新的后代個體.

2.3 不可行解可行化

由于物理結(jié)點vi(?vi∈V)只有h(vi)個虛擬機，因此只能有不超過h(vi)個虛擬結(jié)點映射到物理結(jié)點vi上，然而在交叉變異過程中,會使得某些結(jié)點上映射的虛擬結(jié)點數(shù)超過其所擁有的虛擬機的數(shù)量,導致該虛擬結(jié)點映射個體成為一個不可行解，因此本文設計了一個可以將虛擬結(jié)點映射的不可行解進行可行化的可行化算子，如算法1所示.

算法1：不可行解可行化

輸入：結(jié)點映射個體x;

輸出：新的結(jié)點映射個體x′;

x′=x;

fori=1 toNvdo

Cap(1,i)=h(vi);

end

forj=1 toN′ do

c(j)是xj在個體x出現(xiàn)的次數(shù)，即映射到結(jié)點vxj上虛擬結(jié)點的個數(shù)；

diffCap(1,j)=h(vxj)-c(j);

end

forj=1 toN′ do

ifdiffCap(1,j)<0 do

η是diffCap中最大值所在的位置；

end

end

2.4 適應度函數(shù)

適應度函數(shù)是一個衡量個體好壞的標準，本文所建立的優(yōu)化模型中的目標函數(shù)是最小化最大占用頻隙號.因此本文采用的適應度函數(shù)為式(11)所示.

f=ρ+δ×ω,

(11)

其中δ是一個布爾型變量，當且僅當結(jié)點映射個體x和行路個體y組合形成一個解(x,y)是問題的可行解時δ=0，否則δ=1.ω是一個常數(shù)(該常數(shù)只要大于1即可，本文取ω=100).

3 實驗與分析

3.1 參數(shù)設置

在仿真實驗中，采用兩種網(wǎng)絡拓撲：網(wǎng)絡拓撲1是包含13個節(jié)點和21個鏈路的NSFNET(如圖1所示)， 網(wǎng)絡拓撲2是包含20和節(jié)點和32個鏈路的ARPANET(如圖2所示)， 鏈路上的數(shù)據(jù)表示網(wǎng)絡節(jié)點間的距離.

圖1 NFSNET拓撲Fig. 1 Topology of NFSNET

圖2 ARPANET拓撲Fig. 2 Topology of ARPANET

仿真實驗中假定每個頻隙(Frequency Slots, FSs)為12.5 GHz，4種調(diào)制格式BPSK，QPSK，8QAM和16QAM的傳輸距離分別設置為9600、4800、2400和1200 km[10,11].物理網(wǎng)絡中的每個物理結(jié)點上有10～20個虛擬機，當一個虛擬結(jié)點映射到物理結(jié)點上時需要占用該物理結(jié)點上的一個虛擬機.每一個虛擬網(wǎng)中有3～7個虛擬結(jié)點， 每兩個虛擬結(jié)點之間有業(yè)務請求的概率是0.5.遺傳算法中參數(shù)設置如下：種群規(guī)模Psize=100，交叉概率Pc=0.85，變異概率Pm=0.15，精英保留個數(shù)E=5，終止條件為進化代數(shù)Gmax=5000.

3.2 實驗結(jié)果

為了驗證算法的有效性，本文提出的算法(用GA表示)和文獻[12]提出的算法(用LL表示)在不同的情況下進行對比.在本文設計的算法中，首先對業(yè)務按照某種策略排序，根據(jù)不同的排序策略可以產(chǎn)生不同的算法.本文采用三種常用的排序策略，即MSF(Most Subcarrier First, MSF)、LPF(Longest Path First, LPF)、EMkPSF(Extended Most K Path Subcarrier First, EMkPSF)，與本文提出的遺傳算法結(jié)合可以得到三種算法，即GA-MSF、GA-LPF、GA-EMkPSF.圖3和圖4分別給出了α=0，β=1時在NSFNET和ARPANET中的實驗結(jié)果；圖5和圖6分別給出了α=0.5，β=0.5時在NSFNET和ARPANET中的實驗結(jié)果.圖7和圖8分別給出了α=1，β=0時在NSFNET和ARPANET中的實驗結(jié)果.

圖3 NSFNET中對比圖(α=0，β=1)Fig. 3 Compared in NSFNET(α=0，β=1)

圖4 ARPANET中對比圖(α=0，β=1)Fig. 4 Compared in ARPANET(α=0，β=1)

3.3 實驗結(jié)果分析

圖5 NSFNET中對比圖(α=0.5，β=0.5)Fig. 5 Compared in NSFNET(α=0.5，β=0.5)

圖6 ARPANET中對比圖(α=0.5，β=0.5)Fig. 6 Compared in ARPANET(α=0.5，β=0.5)

圖7 NSFNET中對比圖(α=1，β=0)Fig. 7 Compared in NSFNET(α=1，β=0)

圖8 ARPANET中對比圖(α=1，β=0)Fig. 8 Compared in ARPANET(α=1，β=0)

4 結(jié)論

本文針對虛擬彈性光網(wǎng)絡中虛擬結(jié)點的映射及選路、頻譜分配等問題進行了研究，建立了一個最小化占用頻譜數(shù)及最小化最大占用頻隙號為目標的全局約束優(yōu)化模型.為有效地求解該約束優(yōu)化模型，設計了全局優(yōu)化算法.通過在不同的網(wǎng)絡拓撲中進行仿真實驗，實驗結(jié)果表明：本文設計的算法可以有效降低網(wǎng)絡中占用的頻隙數(shù)和最大頻隙號.但是算法的復雜度較大，因此在后續(xù)的研究中我們將降低計算復雜度，以快速地確定最優(yōu)的虛擬節(jié)點映射及選路、頻譜分配方案.