EONs中一種混合路徑專有保護(hù)算法

張盛峰，袁 強(qiáng)，陳會(huì)丹，黃 勝

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

0 引 言

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

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

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

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

1.1 EONs網(wǎng)絡(luò)模型

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

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

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

1.2 問題描述

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

(1)

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

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

圖1 路徑物理傳輸距離差異較小時(shí)不同分配方案對(duì)比

同樣當(dāng)業(yè)務(wù)帶寬也為400 Gbit/s，在圖2(a)所示情況下，假定P1最高調(diào)制格式為8-QAM、P2最高調(diào)制格式為QPSK和P3最高調(diào)制格式為BPSK，采用單工作路徑保護(hù)分配方案消耗的頻隙資源為75。圖2(b)采用PDPP方案在業(yè)務(wù)帶寬均分情況下消耗的頻隙資源為109。如果同樣采用PDPP方案，且在P3上分配100 Gbit/s帶寬，P2上分配300 Gbit/s帶寬，則在P1保護(hù)路徑上分配300 Gbit/s帶寬的情況下，該方案消耗的頻隙資源為93。在圖2場(chǎng)景下，PDPP方案?jìng)鬏斚母嗟念l隙資源，同時(shí)，在PDPP方案中不同的帶寬分配策略也會(huì)對(duì)頻隙消耗產(chǎn)生影響。

圖2 路徑物理傳輸距離差異較大時(shí)不同分配方案對(duì)比

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

2 HDPP算法

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

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

(2)

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

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

2.2 頻譜分配算法

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

(3)

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

(4)

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

(5)

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

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

圖3 MPSA算法流程圖

MPSA算法具體步驟如下：

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

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

第1步：初始時(shí)，將排在PC第一位的路徑暫時(shí)標(biāo)記成保護(hù)路徑，剩余路徑用PW表示為工作路徑集合，變量change初始設(shè)為0標(biāo)記路徑未進(jìn)行交換操作。

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

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

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

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

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

第8步：若分配成功，則返回對(duì)應(yīng)分配方案，否則返回空。

2.3 HDPP算法步驟

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

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

輸出：分配方案。

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

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

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

第5步：若x

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

3 仿真設(shè)置與結(jié)果分析

3.1 仿真參數(shù)設(shè)置

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

3.2 仿真結(jié)果分析

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

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

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

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

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

4 結(jié)束語

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