彈性光網絡一類調度問題的一個新模型和算法

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

(西安電子科技大學計算機科學與技術學院，陜西 西安 710071)

1 引言

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

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

2 數據中心負載均衡，路由規劃及頻譜分配的優化模型及算法

2.1 問題描述

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

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

2.2 模型建立

1.構建目標函數

本文以數據中心負載最均衡及頻譜資源消耗最小為目標建立約束優化模型.

(A)負載均衡函數S(x)的計算:用x=(x1，x2，···，xNR)T表示各業務在數據中心部署 VNF 功能的方案，表示第k個業務rk在各數據中心上的網絡功能部署方案.其中表示第k個業務rk部署在第i個數據中心的VNF功能數，i=1，2，···，Nd，k=1，2，···，NR.S(x) 為各數據中心上分配待處理網絡功能數的標準差，它可衡量數據中心負載均衡程度.S(x)可計算如下:因NT為NR個網絡服務功能鏈中所有網絡功能的總數，即所有數據中心處理網絡功能的總次數，Fk為第k個網絡服務功能鏈中包含的網絡功能數目，則NR個網絡服務功能鏈中所有網絡功能的總數NT為

每個數據中心處理網絡功能數的平均值為

第h個數據中心上處理網絡功能的數量為

則標準差S(x)計算公式為

2.3 模型求解算法

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

3 數值實驗

3.1 仿真環境及參數配置

本文所采用的實驗環境是 Windows 11操作系統，16G內存，銳龍R7-5800H八核3.2GHz.代碼由Python 3.7語言編寫而成，實驗工具是PyCharm IDE.仿真實驗中采用了四種網絡拓撲:NSFNET[14]，CHNNET[15]，ARPANET[15]和 USANET[10]，網絡圖及詳情見文獻[10，14-15]，網絡參數如表1所示.

表1 網絡參數

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

表2 仿真環境參數

3.2 對比算法

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

3.3 實驗結果分析

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

表3對比了三個算法的平均頻隙消耗量.從表中可以看出，在每個網絡及同樣業務量的情況下，算法1的頻譜消耗量少于算法2和算法3，并且隨著業務量的增加，這種優勢一直保持.同時，本文算法對應的標準差在大部分情況下也小于對比算法的標準差.說明本文算法的穩定性更好.

表3 10次運行中三個方法頻隙消耗量對比

圖1給出了在不同網絡拓撲結構下，三種算法在不同業務量情況下的最大頻隙號的對比結果.

圖1 頻隙消耗量對比

表4對比了三個算法在數據中心部署任務量標準差的均值.可以看出，在NSFNET中，算法1的表現一直優于算法2和算法3.在ARPANET和CHNNET中，在大業務量情況下，算法1的表現也優于算法2和算法3.這說明本文的算法對提高網絡的負載均衡也有較好作用.

表4 10次運行中三個方法的數據中心負載均衡對比

圖2給出了在不同網絡拓撲結構下，三種算法在不同業務量情況下的數據中心負載均衡的對比結果.

表 5對比了三個算法 10次運行得到的最優目標函數均值和標準差.從表 5可看出，對四種網絡的各個任務量情況下，本文算法 1的表現均優于算法 2和算法 3的表現.從10次實驗結果的標準差來看，本文算法穩定性在大多數情況下也優于算法2和算法3.綜上，本文算法在頻譜消耗量上優于算法2和算法3，在負載均衡方面，在NSFNET，ARPANET和CHNNET網絡結構中均有一定優勢，在頻譜消耗量和負載均衡兩個指標的綜合指標來看，本文算法優勢明顯.

表5 10次運行中三個方法的目標函數均值對比

圖3給出了在不同網絡拓撲結構下，三種算法在不同業務量情況下的目標函數均值的對比結果.

圖3 目標函數均值對比

4 結論

本文建立了彈性光網絡調度問題的一個約束全局優化模型，并設計了求解模型的一個進化算法.本模型和算法可以較好地統籌解決網絡負載均衡，分配頻譜和規劃路徑這三個問題，做到較好的負載均衡，節約的頻譜分配和科學的路徑規劃.尤其是對業務量大的網絡調度問題比較有效.