楊晴東，王紫晴，郭威，王宇平

(西安電子科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西 西安 710071)

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，波分復(fù)用網(wǎng)絡(luò)(Wavelength Division Multiplexing，WDM)因其固定柵格的頻譜分配模式，低的頻譜資源利用率，已不能滿足實(shí)際需求.彈性光網(wǎng)絡(luò)(EON)因其頻譜帶寬的靈活分配，網(wǎng)絡(luò)資源的高利用率而成為未來網(wǎng)絡(luò)的發(fā)展方向，但是，EON的路由和頻譜分配(Routing and Spcetrum Allocation，RSA)問題更加復(fù)雜.因此，RSA問題已成為彈性光網(wǎng)絡(luò)中最熱門的關(guān)鍵問題之一[1]，許多學(xué)者對這一問題進(jìn)行了研究.如，文獻(xiàn)[2]提出了基于相對成本技術(shù)的自適應(yīng)多徑路由和頻譜分配算法，用來平衡流量分配并減少EON中的呼叫阻塞概率.文獻(xiàn)[3]考慮了不斷變化的物理層損害所帶來的違反傳輸質(zhì)量(QoT)的風(fēng)險(xiǎn)，并提出了一種鏈路狀態(tài)感知(LSA)的RSA策略，以保證不同鏈路狀態(tài)下的QoT要求.為了解決彈性光網(wǎng)絡(luò)中流量分布不均衡的情況，文獻(xiàn)[4]對潮汐流量的形成特點(diǎn)進(jìn)行了分析，提出了兩種基于OTTM模型的算法來提高帶寬效率.文獻(xiàn)[5]提出了一種基于相對成本概念的自適應(yīng)RSA算法，該算法可估算在給定網(wǎng)絡(luò)狀態(tài)下給定路由/頻譜集上的呼叫被允許時(shí)的瞬態(tài)效應(yīng)和到達(dá)呼叫轉(zhuǎn)發(fā)目的地的相對成本，從而選出最優(yōu)成本的路徑.文獻(xiàn)[6]分析了三種類型彈性光網(wǎng)絡(luò)的網(wǎng)絡(luò)數(shù)據(jù)流，對頻譜分配問題建立了一個整數(shù)線性規(guī)劃模型，并提出了基于粒子群優(yōu)化和禁忌搜索的兩種元啟發(fā)法.然而RSA問題具有極強(qiáng)的針對性，看待問題的角度不同，則問題的模型也不相同，導(dǎo)致RSA問題的模型適應(yīng)面窄.另外，隨著網(wǎng)絡(luò)用戶數(shù)量的不斷快速增大，網(wǎng)絡(luò)硬件的更新速度往往趕不上用戶的需求.虛擬網(wǎng)絡(luò)功能(VNF)是通過軟件來實(shí)現(xiàn)專用硬件設(shè)備的功能，稱為虛擬功能.VNF在不增加網(wǎng)絡(luò)硬件設(shè)備的情況下便可實(shí)現(xiàn)擴(kuò)大業(yè)務(wù)量，提高網(wǎng)絡(luò)資源利用率.但是，具有VNF的彈性光網(wǎng)絡(luò)除要完成RSA任務(wù)外，還要完成一系列的服務(wù)功能鏈(SFC)，每個SFC由若干個需要依次完成的有序功能組成(如加密，解密，深度包檢測，數(shù)據(jù)監(jiān)測等).目前其面臨著諸多的問題和挑戰(zhàn)，挑戰(zhàn)之一就是如何同時(shí)完成三項(xiàng)任務(wù):負(fù)載均衡地在數(shù)據(jù)中心上部署網(wǎng)絡(luò)服務(wù)功能鏈?zhǔn)沟镁W(wǎng)絡(luò)高效和穩(wěn)定;合理地進(jìn)行路由選擇使得數(shù)據(jù)快速傳輸;有效地進(jìn)行頻譜分配使得節(jié)約頻譜資源.目前，這方面的研究已取得了一定成果.如，為了最大程度地減少能耗和總體成本消耗，文獻(xiàn)[7]提出了一種基于VNF遷移策略的整合算法，解決在遷移過程中發(fā)生信息丟失和用戶遭受的QoS下降所導(dǎo)致的收入損失問題.為處理在網(wǎng)絡(luò)和云環(huán)境中部署虛擬和物理的網(wǎng)絡(luò)功能鏈問題，文獻(xiàn)[8]提出了一種基于自定義貪婪算法的啟發(fā)式算法，用以提高性能并提高特征分解方法的能力.文獻(xiàn)[9]對VNF的資源分配問題進(jìn)行了綜述，介紹了解決VNF資源分配問題的主要方法，以及解決VNF資源分配問題的最新技術(shù).針對具有帶寬可變光路，調(diào)制格式約束和虛擬彈性再生器布局的彈性光襯底網(wǎng)絡(luò)中設(shè)計(jì)多個虛擬光網(wǎng)絡(luò)(VON)的問題，文獻(xiàn)[10]提出了一種混合整數(shù)線性規(guī)劃(MILP)模型，并設(shè)計(jì)了啟發(fā)式和元啟發(fā)式求解方法.文獻(xiàn)[11]研究了如何在彈性光網(wǎng)絡(luò)(EON)中動態(tài)地建立和重新配置多播會話的問題，文獻(xiàn)[12]對具有共享數(shù)據(jù)中心的彈性光網(wǎng)絡(luò)，提出了基于共享路徑保護(hù)策略的頻譜分配方法.

由于以上三個問題相互沖突，同時(shí)解決三個問題非常困難，已有工作主要為解決上述三個問題中的一到兩個問題提供高效模型和算法.為了較好地解決以上三個問題，本文將建立可同時(shí)解決上述三個問題的優(yōu)化模型與算法.

2 數(shù)據(jù)中心負(fù)載均衡，路由規(guī)劃及頻譜分配的優(yōu)化模型及算法

2.1 問題描述

具有VNF的彈性光網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可用無向圖G(V，E)表示，其中頂點(diǎn)集合V={v1，v2，···，vNv}表示網(wǎng)絡(luò)的節(jié)點(diǎn)集，數(shù)據(jù)中心節(jié)點(diǎn)集記為VD={v1，v2，···，vNd}，邊集合E={Lij|vi，vj∈V}表示網(wǎng)絡(luò)的鏈路集，每條鏈路上有NF個頻隙.SFC={r1，r2，···，rk，···，rNR}表示網(wǎng)絡(luò)中服務(wù)功能鏈 (SFC)的集合，第k個服務(wù)功能鏈 (簡稱為第k個業(yè)務(wù))表示為rk=(sk，dk，bk，tk)，其中sk為源節(jié)點(diǎn)，dk為目的節(jié)點(diǎn)，tk為第k個業(yè)務(wù)rk中需依次處理的網(wǎng)絡(luò)功能序列，其中是第k個業(yè)務(wù)rk要完成的第i個虛擬網(wǎng)絡(luò)功能 (VNF)的編號(為方便，網(wǎng)絡(luò)虛擬功能VNF也簡稱為功能).tk中各個功能互不相同.Fk表示第k個網(wǎng)絡(luò)服務(wù)功能鏈中包含的網(wǎng)絡(luò)功能數(shù)目，NT表示NR個業(yè)務(wù)中所有不同功能的總數(shù).bk表示第k個業(yè)務(wù)中需要占用的頻隙數(shù).

本文考慮的問題是:如何將每個業(yè)務(wù)中的網(wǎng)絡(luò)功能在數(shù)據(jù)中心上部署?如何為每一個業(yè)務(wù)選擇路徑以及分配頻譜?使得完成所有業(yè)務(wù)時(shí)，路徑合理，數(shù)據(jù)中心負(fù)載均衡及頻譜資源占用少.

2.2 模型建立

1.構(gòu)建目標(biāo)函數(shù)

本文以數(shù)據(jù)中心負(fù)載最均衡及頻譜資源消耗最小為目標(biāo)建立約束優(yōu)化模型.

(A)負(fù)載均衡函數(shù)S(x)的計(jì)算:用x=(x1，x2，···，xNR)T表示各業(yè)務(wù)在數(shù)據(jù)中心部署 VNF 功能的方案，表示第k個業(yè)務(wù)rk在各數(shù)據(jù)中心上的網(wǎng)絡(luò)功能部署方案.其中表示第k個業(yè)務(wù)rk部署在第i個數(shù)據(jù)中心的VNF功能數(shù)，i=1，2，···，Nd，k=1，2，···，NR.S(x) 為各數(shù)據(jù)中心上分配待處理網(wǎng)絡(luò)功能數(shù)的標(biāo)準(zhǔn)差，它可衡量數(shù)據(jù)中心負(fù)載均衡程度.S(x)可計(jì)算如下:因NT為NR個網(wǎng)絡(luò)服務(wù)功能鏈中所有網(wǎng)絡(luò)功能的總數(shù)，即所有數(shù)據(jù)中心處理網(wǎng)絡(luò)功能的總次數(shù)，F(xiàn)k為第k個網(wǎng)絡(luò)服務(wù)功能鏈中包含的網(wǎng)絡(luò)功能數(shù)目，則NR個網(wǎng)絡(luò)服務(wù)功能鏈中所有網(wǎng)絡(luò)功能的總數(shù)NT為

每個數(shù)據(jù)中心處理網(wǎng)絡(luò)功能數(shù)的平均值為

第h個數(shù)據(jù)中心上處理網(wǎng)絡(luò)功能的數(shù)量為

則標(biāo)準(zhǔn)差S(x)計(jì)算公式為

2.3 模型求解算法

因上模型是一個難以求解的非線性整數(shù)規(guī)劃模型，沒有現(xiàn)成的方法可以利用，本節(jié)設(shè)計(jì)一個進(jìn)化算法對模型進(jìn)行求解.算法的主要框架如下:先設(shè)計(jì)了產(chǎn)生初始種群的方法;其次，設(shè)計(jì)了變異算子;最后，通過不斷對種群進(jìn)行變異進(jìn)化，得到最優(yōu)解的一個近似.下面依次介紹算法的各個模塊.

3 數(shù)值實(shí)驗(yàn)

3.1 仿真環(huán)境及參數(shù)配置

本文所采用的實(shí)驗(yàn)環(huán)境是 Windows 11操作系統(tǒng)，16G內(nèi)存，銳龍R7-5800H八核3.2GHz.代碼由Python 3.7語言編寫而成，實(shí)驗(yàn)工具是PyCharm IDE.仿真實(shí)驗(yàn)中采用了四種網(wǎng)絡(luò)拓?fù)?NSFNET[14]，CHNNET[15]，ARPANET[15]和 USANET[10]，網(wǎng)絡(luò)圖及詳情見文獻(xiàn)[10，14-15]，網(wǎng)絡(luò)參數(shù)如表1所示.

表1 網(wǎng)絡(luò)參數(shù)

下面通過計(jì)算機(jī)模擬來驗(yàn)證模型和算法的有效性.實(shí)驗(yàn)分為四組，每組針對一個網(wǎng)絡(luò)，對 NSFNET和 NSFNET，設(shè)置數(shù)據(jù)中心節(jié)點(diǎn)個數(shù)為Nd=7，對 ARPANET和USANET，設(shè)置數(shù)據(jù)中心節(jié)點(diǎn)個數(shù)為Nd=10.每組實(shí)驗(yàn)設(shè)置了不同的業(yè)務(wù)個數(shù)NR.表2給出了每組實(shí)驗(yàn)的業(yè)務(wù)個數(shù)(NR)，VNF數(shù)量(NT)，種群規(guī)模(NPop)，最大進(jìn)化代數(shù)(Ngen)的實(shí)驗(yàn)參數(shù).對每種情況進(jìn)行了10次仿真實(shí)驗(yàn)，取10次仿真實(shí)驗(yàn)結(jié)果的平均值作為最終結(jié)果.

表2 仿真環(huán)境參數(shù)

3.2 對比算法

為后面記號方便，本文模型的求解算法3簡記為算法1，對比算法分別記為算法2和算法3.

3.3 實(shí)驗(yàn)結(jié)果分析

四種網(wǎng)絡(luò)NSFNET，USANET，ARPANET和CHNNET的每一種包含三種情況，對每種情況均進(jìn)行了10次實(shí)驗(yàn)，獲得10次性能指標(biāo)的均值和標(biāo)準(zhǔn)差.實(shí)驗(yàn)中，采用如下三個性能指標(biāo):(1)最大頻隙占用號的均值與標(biāo)準(zhǔn)差，記為NSmean和NSstd.均值可反映網(wǎng)絡(luò)鏈路中頻隙消耗量，值越小說明網(wǎng)絡(luò)中的頻譜消耗越少;(2)數(shù)據(jù)中心VNF部署數(shù)目的標(biāo)準(zhǔn)差的均值和標(biāo)準(zhǔn)差，記為V NFmean和V NFstd.均值可反映數(shù)據(jù)中心的負(fù)載均衡情況，值越小說明彈性光網(wǎng)絡(luò)的數(shù)據(jù)中心負(fù)載越均衡，網(wǎng)絡(luò)的運(yùn)行效率也越高;(3)目標(biāo)函數(shù)值的均值和標(biāo)準(zhǔn)差，記作Fmean和Fstd.均值越小，說明算法的效果越好.而三個指標(biāo)的標(biāo)準(zhǔn)差可反映算法的穩(wěn)定性.值越小，算法的穩(wěn)定性越好.

表3對比了三個算法的平均頻隙消耗量.從表中可以看出，在每個網(wǎng)絡(luò)及同樣業(yè)務(wù)量的情況下，算法1的頻譜消耗量少于算法2和算法3，并且隨著業(yè)務(wù)量的增加，這種優(yōu)勢一直保持.同時(shí)，本文算法對應(yīng)的標(biāo)準(zhǔn)差在大部分情況下也小于對比算法的標(biāo)準(zhǔn)差.說明本文算法的穩(wěn)定性更好.

表3 10次運(yùn)行中三個方法頻隙消耗量對比

圖1給出了在不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，三種算法在不同業(yè)務(wù)量情況下的最大頻隙號的對比結(jié)果.

圖1 頻隙消耗量對比

表4對比了三個算法在數(shù)據(jù)中心部署任務(wù)量標(biāo)準(zhǔn)差的均值.可以看出，在NSFNET中，算法1的表現(xiàn)一直優(yōu)于算法2和算法3.在ARPANET和CHNNET中，在大業(yè)務(wù)量情況下，算法1的表現(xiàn)也優(yōu)于算法2和算法3.這說明本文的算法對提高網(wǎng)絡(luò)的負(fù)載均衡也有較好作用.

表4 10次運(yùn)行中三個方法的數(shù)據(jù)中心負(fù)載均衡對比

圖2給出了在不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，三種算法在不同業(yè)務(wù)量情況下的數(shù)據(jù)中心負(fù)載均衡的對比結(jié)果.

表 5對比了三個算法 10次運(yùn)行得到的最優(yōu)目標(biāo)函數(shù)均值和標(biāo)準(zhǔn)差.從表 5可看出，對四種網(wǎng)絡(luò)的各個任務(wù)量情況下，本文算法 1的表現(xiàn)均優(yōu)于算法 2和算法 3的表現(xiàn).從10次實(shí)驗(yàn)結(jié)果的標(biāo)準(zhǔn)差來看，本文算法穩(wěn)定性在大多數(shù)情況下也優(yōu)于算法2和算法3.綜上，本文算法在頻譜消耗量上優(yōu)于算法2和算法3，在負(fù)載均衡方面，在NSFNET，ARPANET和CHNNET網(wǎng)絡(luò)結(jié)構(gòu)中均有一定優(yōu)勢，在頻譜消耗量和負(fù)載均衡兩個指標(biāo)的綜合指標(biāo)來看，本文算法優(yōu)勢明顯.

表5 10次運(yùn)行中三個方法的目標(biāo)函數(shù)均值對比

圖3給出了在不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，三種算法在不同業(yè)務(wù)量情況下的目標(biāo)函數(shù)均值的對比結(jié)果.

圖3 目標(biāo)函數(shù)均值對比

4 結(jié)論

本文建立了彈性光網(wǎng)絡(luò)調(diào)度問題的一個約束全局優(yōu)化模型，并設(shè)計(jì)了求解模型的一個進(jìn)化算法.本模型和算法可以較好地統(tǒng)籌解決網(wǎng)絡(luò)負(fù)載均衡，分配頻譜和規(guī)劃路徑這三個問題，做到較好的負(fù)載均衡，節(jié)約的頻譜分配和科學(xué)的路徑規(guī)劃.尤其是對業(yè)務(wù)量大的網(wǎng)絡(luò)調(diào)度問題比較有效.