張盛峰，袁 強，陳會丹，黃 勝

(重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

在彈性光網(wǎng)絡(Elastic Optical Networks, EONs)中，路由和頻譜分配(Routing and Spectrum Assignment, RSA)問題是最主要的問題[1-3]。由于通信網(wǎng)絡中超過80%的信息在光纖鏈路中傳輸，光纖鏈路故障會造成大量的業(yè)務請求中斷和信息丟失[4]。如何在網(wǎng)絡出現(xiàn)故障時對網(wǎng)絡實施有效且快速的保護恢復措施，提高保護資源分配成功率，減少冗余保護資源的消耗，顯得尤為重要[5-7]。

文獻[8]將光纖鏈路上的頻譜分為保護和工作頻譜，通過帶寬分割多保護路徑共享保護，提升了保護頻譜的共享度，降低了帶寬阻塞率；文獻[9]基于多目標遺傳算法優(yōu)化多路徑保護算法，并提到EONs中的多路徑保護RSA問題是一個非確定性多項式(Non-deterministic Polynomial，NP)難解問題；文獻[10]提出了一種基于業(yè)務帶寬分割多路徑傳輸?shù)膮^(qū)分服務分配方案；文獻[11]提出了一種混合單路徑路由與多路徑路由用于空分復用EONs的保護算法；文獻[12]提出了對虛擬網(wǎng)絡映射進行保護，考慮多路徑帶寬可分割的自適應路徑分割(Adaptive Path Split, APS)啟發(fā)式算法，但APS算法沒有考慮到更合理的工作帶寬分割策略來進一步減小頻譜資源的消耗；文獻[13]研究了業(yè)務帶寬分割多路徑傳輸?shù)牟糠謳挶Ｗo可根據(jù)業(yè)務優(yōu)先級進行帶寬壓縮，提出了混合整數(shù)線性規(guī)劃模型，但模型由于復雜度高，只適用于小型的靜態(tài)網(wǎng)絡；文獻[14]提出了一種動態(tài)的考慮單鏈路故障可保護恢復的多路徑保護(Multiple Path Protection, MPP)算法，但MPP算法沒有考慮到距離自適應調(diào)制，即同樣大小的帶寬分配在不同路徑上所消耗頻譜資源不同的問題。

本文研究了在網(wǎng)絡發(fā)生單鏈路故障時對受損業(yè)務進行100%恢復的情景下，業(yè)務傳輸可以進行帶寬分割多路徑專有保護和單路徑專有保護的RSA算法，即混合路徑專有保護(Hybrid Dedicated Path Protection, HDPP)算法，該算法結合單位頻隙最高頻譜效率和路徑跳數(shù)計算出k條候選路徑，并綜合路徑上最大可用頻譜信息，利用多路徑頻譜分配(Multiple Path Spectrum Assignment, MPSA)算法產(chǎn)生多種可行的RSA方案，在可行方案中，按照在網(wǎng)絡中消耗頻譜資源最少的原則選擇較優(yōu)的保護分配方案，節(jié)約頻譜資源，進一步降低了業(yè)務阻塞率。

1 EONs網(wǎng)絡模型與問題描述

1.1 EONs網(wǎng)絡模型

本文中的EONs拓撲可建模為一個無向圖G(V,E,S)，其中，V={v1，v2，v3，…}為網(wǎng)絡節(jié)點集合，|V|為節(jié)點個數(shù)；E={e1，e2，e3，…}為網(wǎng)絡拓撲中鏈路的集合，|E|為鏈路數(shù)目；S={s1，s2，s3，…}為所有鏈路頻隙狀態(tài)的集合，|S|為頻隙數(shù)目，并且每條鏈路上的頻隙數(shù)量相同，F(xiàn)s為單位頻隙，一般Fs=12.5 GHz。第i個業(yè)務請求可表示為Ri(oi,di,bi)，oi和di分別為源和目的地址，bi為業(yè)務請求所需的帶寬。如表1所示，調(diào)制格式可根據(jù)路徑長度自適應，mk為正整數(shù)，表示路徑pk上可用的最高頻譜效率，mk的取值范圍1～4分別對應調(diào)制格式二相相移鍵控(Binary Phase Shift Keying，BPSK)、正交相移鍵控(Quadrature Phase Shift Keying，QPSK)、8-正交幅度調(diào)制(Quadrature Amplitude Modulation，QAM)和16-QAM。G為防止不同業(yè)務間信號發(fā)生串擾而設置的保護頻隙，一般G為1單位頻隙。

表1 調(diào)制格式與傳輸速率、最大傳輸距離和頻譜效率的關系

頻譜分配必須滿足3個基本約束限制。頻譜連續(xù)性約束：保證路徑經(jīng)過光纖鏈路所分配的頻隙在頻域上是連續(xù)的；頻譜一致性約束：保證路徑所經(jīng)過的每條光纖鏈路都采用相同的頻隙；頻譜不重疊約束：兩個不同業(yè)務若存在共享鏈路，則同一頻隙不能被兩個不同業(yè)務請求同時占用，以保證光纖鏈路的任意頻隙最多被一個業(yè)務使用。

1.2 問題描述

由文獻[12-13]可知，帶寬分割多路徑專用保護(Partitioning Dedicated Path Protection, PDPP)方案可適當?shù)販p少業(yè)務專有保護的帶寬消耗，同時也保證了對業(yè)務進行滿足可靠性傳輸?shù)囊螅^PDPP方案是對某一業(yè)務帶寬通過多條子工作路徑傳輸，而用一條保護路徑對這些子工作路徑發(fā)生單鏈路故障時提供保護。Q對應具體的保護路徑和工作路徑資源分配方案，對于具體的一種分配方案，Q需要消耗的網(wǎng)絡頻譜資源可表示為

(1)

式中：CQ為方案所消耗的總頻譜資源；|Q|為分配方案所包含的路徑數(shù)量；bak為在路徑pk上分配的帶寬；pk為任意包含于分配方案Q中的路徑；mk為路徑pk的最大頻譜效率；[*]為向上取整；hk為路徑pk的跳數(shù)。

如圖1(a)所示，若3條路徑P1、P2和P3物理傳輸距離相近，且都采用8-QAM的調(diào)制格式進行傳輸，假定業(yè)務需要的帶寬為400 Gbit/s，采用單工作路徑保護分配方案消耗的頻隙資源為48。而圖1(b)采用PDPP方案，并且業(yè)務帶寬均分，即在子工作路徑P1與P2上都分配200 Gbit/s的帶寬，而在P3上分配的保護帶寬為200 Gbit/s，分配業(yè)務需要占用的頻隙資源為42。在這樣的場景下PDPP方案更加節(jié)省頻譜資源。

圖1 路徑物理傳輸距離差異較小時不同分配方案對比

同樣當業(yè)務帶寬也為400 Gbit/s，在圖2(a)所示情況下，假定P1最高調(diào)制格式為8-QAM、P2最高調(diào)制格式為QPSK和P3最高調(diào)制格式為BPSK，采用單工作路徑保護分配方案消耗的頻隙資源為75。圖2(b)采用PDPP方案在業(yè)務帶寬均分情況下消耗的頻隙資源為109。如果同樣采用PDPP方案，且在P3上分配100 Gbit/s帶寬，P2上分配300 Gbit/s帶寬，則在P1保護路徑上分配300 Gbit/s帶寬的情況下，該方案消耗的頻隙資源為93。在圖2場景下，PDPP方案傳輸消耗更多的頻隙資源，同時，在PDPP方案中不同的帶寬分配策略也會對頻隙消耗產(chǎn)生影響。

圖2 路徑物理傳輸距離差異較大時不同分配方案對比

通過上述的兩個簡單例子，可知不同分配策略所消耗的頻隙資源不同，而且會根據(jù)不同的路徑狀況而改變。于是本文提出了一種在動態(tài)網(wǎng)絡場景下，綜合多種生存性RSA方案的HDPP算法，以降低帶寬阻塞率，節(jié)約頻譜資源。

2 HDPP算法

2.1 改進K最短路徑(MKSP)路由

采用最短路徑優(yōu)先或最小跳數(shù)優(yōu)先的路徑選擇策略，在頻譜消耗上總是存在此消彼長的現(xiàn)象，并不能很好地找出總頻譜消耗更少的路由[15]。因此，本文設計了一種路徑選擇機制，以求達到更優(yōu)的效果。為了優(yōu)先選擇出消耗頻譜資源較少的路徑，定義具體路徑pk的路徑效率系數(shù)為

(2)

式中，Sk為路徑pk的路徑效率系數(shù)。綜合路徑的最大頻譜效率mk和路徑跳數(shù)hk，以Sk最大路徑優(yōu)先為準則修改K最短路徑(KShort Path，KSP)算法，求出k條鏈路不相關路徑，目的是為了優(yōu)先選擇跳數(shù)少且調(diào)制格式較高的路徑。

當使用鏈路不相關路徑的數(shù)量過多時，帶寬可分割多路徑傳輸所帶來的效益并不明顯[16]，同時，考慮實際網(wǎng)絡中的鏈路不相關路徑只有少數(shù)情況下會超過5條，所以本文設置最多5條鏈路不相關路徑。

2.2 頻譜分配算法

HDPP算法考慮多種可行分配方案，在這些分配方案中選擇消耗頻隙資源最小的一種在網(wǎng)絡中實施，滿足該情形的前提條件是路徑集合至少包括兩條以上路徑。對于單工作路徑專有保護方案，根據(jù)MKSP算法計算出k條路徑，以路徑效率系數(shù)Sk值降序依次選出一條工作路徑和一條保護路徑，要求路徑上的可用連續(xù)頻譜可滿足業(yè)務傳輸，若存在單工作路徑專有保護方案，將其加入候選分配方案集合；對于PDPP方案，若路徑集合包含的路徑數(shù)目為X(3≤X≤5)，則最多會產(chǎn)生16種帶寬分割多路徑專用保護方案，以路徑效率系數(shù)降序?qū)γ恳唤M中的路徑排序。對于每一種路徑組合，不同的帶寬分割策略會產(chǎn)生不同網(wǎng)絡資源消耗。因此，文中提出了一種動態(tài)的帶寬多路徑分配啟發(fā)式算法—MPSA算法，目的是為了最小化多路徑帶寬分配的頻譜消耗。根據(jù)具體路徑集合信息判斷帶寬均分與非均分的優(yōu)劣，定義判斷系數(shù)為

(3)

式中：f為判斷系數(shù)；PC為所有參與業(yè)務帶寬分配的路徑集合，包括保護路徑和工作路徑；pc為屬于路徑集合PC的路徑；Sc為PC集合中各路徑的路徑效率系數(shù)；X為所有參與業(yè)務帶寬分配的路徑數(shù)，即|PC|；PW為除去保護路徑的工作路徑集合；pw為屬于路徑集合PW的路徑；Sw為PW集合中路徑w的路徑效率系數(shù)。由式(3)可在可用路徑已知的條件下，根據(jù)判斷f與0的大小來采用不同的帶寬分配方法。計算具體路徑的分配帶寬參考值npm為

(4)

式中：PA為需要參與帶寬分配的工作路徑集合；Sn為PA集合中各路徑的路徑效率系數(shù)；Sm為PA集合中最小路徑效率系數(shù)，其對應路徑為pm；bleft為未分配帶寬，初始時bleft等于業(yè)務請求帶寬。由式(4)可知，在任意一條屬于集合PA的最小路徑效率系數(shù)工作路徑pm上分配的帶寬大小以npm為參考基準的帶寬，若f≤0，采用帶寬均分方法在每條路徑上分配相同大小帶寬；否則將依據(jù)工作路徑pm的路徑效率系數(shù)除以PA集合中所有路徑的路徑效率系數(shù)總和的大小來分配帶寬。為了提高頻譜效率，使分配帶寬盡量充分利用路徑上的頻隙，對分配帶寬參考值進行修整：

(5)

式中：spm為具體計劃在路徑pm上分配的帶寬大小；mm為路徑pm最大頻譜效率；[*]為向下取整。

將多種路徑組合依次輸入到MPSA算法中求出分配方案，并將MPSA算法返回為非空的分配方案加入到候選分配方案集合，設Bk為路徑pk上考慮左右相鄰保護頻隙G的最大連續(xù)頻隙可承載帶寬。圖3所示為MPSA算法流程圖。

圖3 MPSA算法流程圖

MPSA算法具體步驟如下：

輸入：網(wǎng)絡狀態(tài)G(V,E,S)，請求Ri(oi,di,bi)，x條按路徑效率系數(shù)降序排序的路徑組合PC。

輸出：路徑組合的帶寬分配方案。

第1步：初始時，將排在PC第一位的路徑暫時標記成保護路徑，剩余路徑用PW表示為工作路徑集合，變量change初始設為0標記路徑未進行交換操作。

第2步：要求PW中所有工作路徑的最大連續(xù)頻隙可承載帶寬之和不小于請求帶寬bi，bleft=bi，初始化集合PA=PW，由式(3)計算f。

第3步：PA中選出路徑效率系數(shù)最小的路徑pm，由式(4)計算得到npm。由式(5)計算得到計劃在該路徑上分配的具體帶寬大小為spm。

第4步：pm路徑上最大連續(xù)頻隙可承載帶寬為Bm，若spm≤bleft，且spm≤Bm，則在路徑pm上分配帶寬bam=spm，并當spmBm，則bam=Bm。若spm≥bleft，且bleft≤Bm，則bam=bleft；若spm≥bleft，且bleft>Bm，則在pm分配帶寬bam=Bm。

第5步：更新bleft=bleft-bam并將pm從PA中刪除。重復第3～5步，直到PA為空或bleft=0。

第6步：若bleft>0，位于ST棧頂?shù)穆窂剑谠撀窂揭逊峙鋷挼幕A上嘗試擴充bleft大小的帶寬，擴充后該路徑上分配的帶寬不大于其最大可承載帶寬，然后彈出ST棧頂路徑并更新bleft。重復第6步，直到bleft=0。

第8步：若分配成功，則返回對應分配方案，否則返回空。

2.3 HDPP算法步驟

在包含上述多種分配方案的候選分配方案集合中，由式(1)計算得到各分配方案的相應CQ值，并選擇CQ值最小的分配方案在實際網(wǎng)絡中實施，并使用首次適配(First Fit, FF)頻譜分配算法計算得到在每條分配路徑上占用的具體頻隙。下面是HDPP算法的具體流程步驟：

輸入：網(wǎng)絡狀態(tài)G(V,E,S)和請求Ri(oi,di,bi)。

輸出：分配方案。

第1步：根據(jù)改進的MKSP算法計算k條從oi到di的鏈路不相關路徑。

第2步：若存在單路徑專有保護方案，則將方案放入候選分配方案集合SL中。

第3步：若k>2，設變量x初始值為3，轉(zhuǎn)第4步；否則轉(zhuǎn)第6步。

第5步：若x

第6步：若集合SL不為空，則返回CQ值最小的分配方案；否則阻塞該業(yè)務請求。

3 仿真設置與結果分析

3.1 仿真參數(shù)設置

網(wǎng)絡中的每條鏈路都是雙向的，每根光纖的總頻隙寬度為4.475 THz，每條鏈路的頻隙數(shù)為358，單位頻隙為Fs=12.5 GHz。仿真時，源和目的節(jié)點對在節(jié)點集合中隨機產(chǎn)生并服從均勻分布，業(yè)務請求到達服從參數(shù)為λ的泊松分布，業(yè)務持續(xù)時間服從大小為1/μ的指數(shù)分布。業(yè)務請求帶寬大小bi從集合{40，100，400} Gbit/s中隨機產(chǎn)生，且服從均勻分布?？蛇x擇的調(diào)制格式有BPSK、QPSK、8-QAM和16-QAM。不同業(yè)務請求間的保護頻隙G為1 Fs，每次仿真105個業(yè)務，將多次仿真結果取平均值。本文仿真網(wǎng)絡為11個節(jié)點、26條鏈路的COST239網(wǎng)絡，通過帶寬阻塞率和頻譜利用率兩個性能指標來評估算法的性能。

3.2 仿真結果分析

將本文所提HDPP算法與基于文獻[14]提出的MPP算法和基于文獻[11]提出的APS算法進行性能比較。MPP算法傾向于動態(tài)地在每條路徑上將帶寬均分以求達到分配的總帶寬最小，但不一定會達到消耗頻譜資源最??；APS算法則總是以最短或最少跳數(shù)路徑優(yōu)先嘗試將工作帶寬分配完成后，再計算相應需要分配的保護資源。

本文在不同負載下進行仿真，由圖4可知，本文所提HDPP算法相比于APS和MPP算法在帶寬阻塞率上有著較為明顯的提升。圖中LH為使用最少跳數(shù)優(yōu)先計算出的候選路徑；KSP為以最短路徑優(yōu)先計算的候選路徑；MKSP為由本文提出的以Sk最大優(yōu)先原則計算的候選路徑。HDPP算法低阻塞率的主要原因有如下3點：(1)HDPP算法綜合考慮了不同路徑上的調(diào)制格式和節(jié)點數(shù)的情況，使頻譜更少，同時在多種路徑組合中，HDPP算法傾向于選擇消耗頻譜資源更少的路徑組合，可以為后續(xù)到達的業(yè)務提供更多的可用頻譜資源；(2)MPP算法最多考慮3條路徑帶寬分割多路徑傳輸，與MPP算法不同的是，HDPP算法還考慮了3條以上帶寬分割多路徑傳輸?shù)那闆r，降低了帶寬阻塞率；(3)通過本文提出的一種基于KSP改進的路由算法—MKSP算法，可以在網(wǎng)絡中找到能使頻譜消耗更小的路徑，從而避免了過多的頻譜消耗，讓更多業(yè)務可以在網(wǎng)絡中分配，降低了帶寬阻塞率。

圖4 COST239網(wǎng)絡不同負載下的帶寬阻塞率

在高負載情況下，由圖5可知，APS算法的頻譜利用率最低，其原因在于，APS算法首先按照路徑最短優(yōu)先的方式選擇路徑分配工作帶寬，然后在剩余的路徑中選擇一條滿足保護帶寬要求的路徑，容易造成較多的保護帶寬分配在調(diào)制格式低以及節(jié)點跳數(shù)多的路徑上，使得頻譜消耗較高。而后面隨著負載的增加，由于初期頻譜資源消耗較高，后續(xù)能滿足業(yè)務帶寬需求的頻譜資源較少，造成在較高負載情況下的阻塞率較高，從而由仿真結果可知，相同負載情況下，本文所提算法沒有MPP和HDPP算法的頻譜利用率高。同時，可以看到采用MKSP算法計算出的路徑能在低負載下節(jié)省頻譜資源的同時有低的阻塞率，而在高負載情況下，節(jié)省出來的頻譜可以為更多業(yè)務提供傳輸，從而有著較高的頻譜利用率。HDPP與MPP算法相比，在相同較低負載情況下，HDPP算法在有更小阻塞率的同時，消耗的頻譜資源較少，主要原因是采用PDPP方案時，并沒有簡單使用MPP算法提出的以帶寬均分為頻譜分配準則，同時還進一步考慮到某些路徑狀態(tài)下根據(jù)路徑頻譜效率分配帶寬，可達到更加節(jié)省頻譜資源的目的；并且HDPP算法還將大于3條路徑的PDPP方案考慮在內(nèi)，使帶寬阻塞率降低；因為在負載較高情況下，HDPP算法的帶寬阻塞率最低，所以使得頻譜利用率高于MPP算法。

圖5 COST239網(wǎng)絡不同負載下的頻譜利用率

4 結束語

本文研究了EONs中保障單鏈路故障可100%恢復的生存性RSA問題，結合單路徑專有保護和帶寬分割多路徑專有保護，本文定義了一種根據(jù)路徑的頻隙頻譜效率和節(jié)點數(shù)之比得到相對于路徑的單位頻譜效率參數(shù)Sk，以Sk最大優(yōu)先改進KSP算法得到多條頻譜效率較高的鏈路不相關路徑的方法；然后，為多路徑頻譜分配問題設計了MPSA算法，可根據(jù)頻譜效率和路徑跳數(shù)信息進行帶寬分割多路徑專有保護的頻譜分配，生成合理的RSA方案；最后，在多種可選分配方案中，選擇出消耗頻譜資源最小的分配方案作為實際的執(zhí)行方案。實驗仿真結果表明，所提HDPP算法相比于對比算法有最低的業(yè)務阻塞率和最高的頻譜利用率。