彈性光網(wǎng)絡(luò)一類調(diào)度問(wèn)題的一個(gè)新模型和算法

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

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

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

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

2.1 問(wèn)題描述

具有VNF的彈性光網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可用無(wú)向圖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個(gè)頻隙.SFC={r1，r2，···，rk，···，rNR}表示網(wǎng)絡(luò)中服務(wù)功能鏈 (SFC)的集合，第k個(gè)服務(wù)功能鏈 (簡(jiǎn)稱為第k個(gè)業(yè)務(wù))表示為rk=(sk，dk，bk，tk)，其中sk為源節(jié)點(diǎn)，dk為目的節(jié)點(diǎn)，tk為第k個(gè)業(yè)務(wù)rk中需依次處理的網(wǎng)絡(luò)功能序列，其中是第k個(gè)業(yè)務(wù)rk要完成的第i個(gè)虛擬網(wǎng)絡(luò)功能 (VNF)的編號(hào)(為方便，網(wǎng)絡(luò)虛擬功能VNF也簡(jiǎn)稱為功能).tk中各個(gè)功能互不相同.Fk表示第k個(gè)網(wǎng)絡(luò)服務(wù)功能鏈中包含的網(wǎng)絡(luò)功能數(shù)目，NT表示NR個(gè)業(yè)務(wù)中所有不同功能的總數(shù).bk表示第k個(gè)業(yè)務(wù)中需要占用的頻隙數(shù).

本文考慮的問(wèn)題是:如何將每個(gè)業(yè)務(wù)中的網(wǎng)絡(luò)功能在數(shù)據(jù)中心上部署?如何為每一個(gè)業(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個(gè)業(yè)務(wù)rk在各數(shù)據(jù)中心上的網(wǎng)絡(luò)功能部署方案.其中表示第k個(gè)業(yè)務(wù)rk部署在第i個(gè)數(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個(gè)網(wǎng)絡(luò)服務(wù)功能鏈中所有網(wǎng)絡(luò)功能的總數(shù)，即所有數(shù)據(jù)中心處理網(wǎng)絡(luò)功能的總次數(shù)，F(xiàn)k為第k個(gè)網(wǎng)絡(luò)服務(wù)功能鏈中包含的網(wǎng)絡(luò)功能數(shù)目，則NR個(gè)網(wǎng)絡(luò)服務(wù)功能鏈中所有網(wǎng)絡(luò)功能的總數(shù)NT為

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

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

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

2.3 模型求解算法

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

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語(yǔ)言編寫(xiě)而成，實(shí)驗(yàn)工具是PyCharm IDE.仿真實(shí)驗(yàn)中采用了四種網(wǎng)絡(luò)拓?fù)?NSFNET[14]，CHNNET[15]，ARPANET[15]和 USANET[10]，網(wǎng)絡(luò)圖及詳情見(jiàn)文獻(xiàn)[10，14-15]，網(wǎng)絡(luò)參數(shù)如表1所示.

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

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

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

3.2 對(duì)比算法

為后面記號(hào)方便，本文模型的求解算法3簡(jiǎn)記為算法1，對(duì)比算法分別記為算法2和算法3.

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

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

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

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

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

圖1 頻隙消耗量對(duì)比

表4對(duì)比了三個(gè)算法在數(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.這說(shuō)明本文的算法對(duì)提高網(wǎng)絡(luò)的負(fù)載均衡也有較好作用.

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

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

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

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

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

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

4 結(jié)論

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