HOWBAN中支持降級(jí)服務(wù)的共享保護(hù)算法

董丹，何榮希（大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧 大連116026）

?

中文核心期刊

HOWBAN中支持降級(jí)服務(wù)的共享保護(hù)算法

董丹，何榮希
（大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧 大連116026）

摘要：針對(duì)光無(wú)線混合寬帶接入網(wǎng)（H O W BA N）的特點(diǎn)提出一種支持降級(jí)服務(wù)的共享保護(hù)算法（D S-SPP）。依據(jù)用戶請(qǐng)求的連接可用性、帶寬需求和降級(jí)帶寬程度，選擇備用O N U并分配降級(jí)備用帶寬，然后通過(guò)前端無(wú)線網(wǎng)狀網(wǎng)（W M N）重路由受影響業(yè)務(wù)。仿真結(jié)果表明：D S-SPP算法可以大大降低備用O N U和無(wú)線路由器上備用資源的預(yù)留量，進(jìn)一步提高網(wǎng)絡(luò)的資源利用率。

關(guān)鍵詞：光無(wú)線混合寬帶接入網(wǎng)；保護(hù)；降級(jí)服務(wù)；共享；無(wú)線網(wǎng)狀網(wǎng)

0　引言

光無(wú)線混合寬帶接入網(wǎng)（HOWBAN）融合了無(wú)源光網(wǎng)絡(luò)（PON）和無(wú)線網(wǎng)絡(luò)各自優(yōu)勢(shì)，是下一代接入網(wǎng)最具競(jìng)爭(zhēng)力的候選方案之一［1，2］。由于覆蓋范圍廣、傳輸容量大，網(wǎng)絡(luò)發(fā)生故障時(shí)損失嚴(yán)重，因此生存性問(wèn)題是其中一個(gè)關(guān)鍵問(wèn)題［3］。不少文獻(xiàn)［3-5］涉及HOWBAN的生存性問(wèn)題，大多通過(guò)預(yù)留備用資源來(lái)提高網(wǎng)絡(luò)應(yīng)對(duì)故障能力。自然災(zāi)害不可預(yù)測(cè)，而且不常發(fā)生。如果對(duì)所有業(yè)務(wù)都提供100%保護(hù)，需部署大量備用資源，成本很高。因此，文獻(xiàn)［6］提出了一種降低成本的方法，即當(dāng)網(wǎng)絡(luò)發(fā)生故障時(shí)提供一種降級(jí)服務(wù)（Degraded-Service），可以使網(wǎng)絡(luò)在某種程度上可用，網(wǎng)絡(luò)服務(wù)處于可接受水平。降級(jí)服務(wù)依據(jù)不同業(yè)務(wù)需求的差異性，有針對(duì)性地預(yù)留備用資源，可以提升網(wǎng)絡(luò)應(yīng)對(duì)災(zāi)難的能力。文獻(xiàn)［7］針對(duì)WDM網(wǎng)絡(luò)提出降級(jí)服務(wù)感知多路徑資源分配策略，發(fā)生故障時(shí)只需保護(hù)受影響業(yè)務(wù)，既滿足業(yè)務(wù)服務(wù)等級(jí)需求，同時(shí)又能減少資源占用。文獻(xiàn)［8］針對(duì)WDM網(wǎng)絡(luò)大災(zāi)難場(chǎng)景提出支持降級(jí)服務(wù)保護(hù)策略，當(dāng)自然災(zāi)害導(dǎo)致網(wǎng)絡(luò)可用資源急劇減少時(shí)，對(duì)需要保護(hù)的業(yè)務(wù)進(jìn)行帶寬降級(jí)，以增加業(yè)務(wù)恢復(fù)成功機(jī)會(huì)。與WDM網(wǎng)絡(luò)不同，HOWBAN可以利用前端無(wú)線重路由為后端受影響業(yè)務(wù)提供迂回保護(hù)［9］，其支持降級(jí)服務(wù)的保護(hù)問(wèn)題還是一個(gè)較新問(wèn)題。本文針對(duì)HOWBAN提出一種支持降級(jí)服務(wù)的共享保護(hù)算法（DS-SPP），可根據(jù)業(yè)務(wù)請(qǐng)求的帶寬需求和允許帶寬降級(jí)程度，為無(wú)法滿足其可用性要求的工作ONU選擇備用ONU，分配降級(jí)備用帶寬，并通過(guò)前端WMN重路由受影響業(yè)務(wù)。DS-SPP可以降低備用ONU資源和備用無(wú)線資源的預(yù)留量，提高網(wǎng)絡(luò)資源利用率。

1　算法描述

在HOWBAN中，用戶業(yè)務(wù)通過(guò)前端WMN的無(wú)線多跳匯聚到覆蓋相應(yīng)區(qū)域的ONU（工作ONU），繼而經(jīng)后端PON接入骨干網(wǎng)。由于前端為網(wǎng)狀網(wǎng)，具有極強(qiáng)的自愈能力，本文僅針對(duì)后端網(wǎng)絡(luò)故障進(jìn)行討論。一般來(lái)說(shuō)，PON中ONU、OLT等設(shè)備發(fā)生故障的概率較小，而且在部署時(shí)有冗余備份措施，即使發(fā)生故障，網(wǎng)絡(luò)設(shè)備切換所需時(shí)間很短，能快速恢復(fù)［10］，因此本文主要考慮光纖故障對(duì)業(yè)務(wù)連接的影響。后端PON中連接OLT、分光器和ONU的光纖鏈路可分為零級(jí)光纖、一級(jí)光纖和二級(jí)光纖3個(gè)等級(jí)［5］。根據(jù)不同級(jí)別光纖的覆蓋范圍和可靠性保障，3個(gè)等級(jí)的光纖故障概率依次增大。ONU能為用戶提供的可用性取決于該ONU到OLT的光路徑（工作連接）能夠正常工作的概率。如果工作ONU的可用性滿足用戶的可用性需求，則不需預(yù)留備用資源；否則，需要尋找備用ONU，并配置備用資源。DS-SPP算法主要為不滿足可用性需求的業(yè)務(wù)尋找備用ONU，并根據(jù)業(yè)務(wù)報(bào)告的帶寬降級(jí)參數(shù)，在備用ONU中降級(jí)預(yù)留備用帶寬，同時(shí)在前端WMN中部署從工作ONU到備用ONU的無(wú)線備用路徑。本文用pi表示光纖鏈路i的可用性概率，F(xiàn)x表示ONUx到OLT的光路徑上的光纖鏈路集合，那么ONUx和OLT之間的工作連接可用性可表示為：

ONU在滿足自身業(yè)務(wù)可用性需求的前提下還可作為其它業(yè)務(wù)的備用ONU。為了提高網(wǎng)絡(luò)資源利用率，不同ONU上的業(yè)務(wù)可以在滿足連接可用性約束條件下共享同一個(gè)ONU的備用容量。假設(shè)ONUy為當(dāng)前選定的備用ONU，該ONU上已經(jīng)分配的備用容量為u，共享這部分備用容量的業(yè)務(wù)所在工作ONU構(gòu)成集合Op（u），那么ONUy能提供的備用連接可用性為：

其中，F(xiàn)Op（u）表示集合Op（u）中的ONU到OLT光路徑上的光纖鏈路集合，F(xiàn)y表示ONUy到OLT的光路徑上的光纖鏈路集合。對(duì)某一業(yè)務(wù)t來(lái)說(shuō)，部署備用ONU后，能夠?yàn)樵摌I(yè)務(wù)提供的可用性大小為工作ONU和備用ONU不同時(shí)發(fā)生故障的概率，即：

假設(shè)某一業(yè)務(wù)t的帶寬請(qǐng)求為bt，可用性請(qǐng)求為at和帶寬降級(jí)參數(shù)為βt，βt為（0，1）之間的常數(shù)。當(dāng)業(yè)務(wù)t的工作ONU提供的可用性大小不滿足其可用性要求時(shí)，需要為它尋找備用ONU，以滿足At＞at（為了進(jìn)一步節(jié)約備用資源，并不需要為所有業(yè)務(wù)都提供100%帶寬保護(hù)，而是根據(jù)帶寬降級(jí)參數(shù)βt，在備用ONUy中為業(yè)務(wù)t預(yù)留bt×βt的備用容量即可）。找到合適的備用ONU后，DS-SPP在前端WMN利用Dijkstra算法尋找從工作ONU到備用ONU的代價(jià)最小的備用無(wú)線路徑，并在路徑經(jīng)過(guò)的無(wú)線路由器中配置備用無(wú)線容量。由于Dijkstra算法基于網(wǎng)絡(luò)中的鏈路權(quán)值來(lái)選擇最小開(kāi)銷(xiāo)的路徑，需要將路由器的節(jié)點(diǎn)代價(jià)轉(zhuǎn)化為鏈路代價(jià)。在進(jìn)行選路時(shí)，將無(wú)線路由器剩余容量的大小轉(zhuǎn)換為無(wú)線鏈路的權(quán)值。WMN中的無(wú)線路由器根據(jù)無(wú)線帶寬容量的使用情況可分為三類(lèi)［5］：①無(wú)線路由器中有剩余容量，且有備用容量。選用這樣的路由器建立無(wú)線備用路徑，可以減少新增備用資源消耗量。因此，應(yīng)鼓勵(lì)選擇這樣的無(wú)線路由器作為下一跳節(jié)點(diǎn)，可設(shè)置其所在鏈路權(quán)值為一個(gè)接近0的常數(shù)ξ。②無(wú)線路由器中有剩余容量，但備用容量為0。如果使用這樣的無(wú)線路由器建立備用無(wú)線路徑，需要消耗額外的備用無(wú)線容量，因此不鼓勵(lì)選擇這樣的無(wú)線路由器作為下一跳節(jié)點(diǎn)，設(shè)置其對(duì)應(yīng)鏈路權(quán)值為一個(gè)較大值。③無(wú)線路由器中的工作容量等于總?cè)萘?，即沒(méi)有剩余容量，也沒(méi)有備用容量。這樣的路由器無(wú)法建立備用無(wú)線路徑，因此其所在鏈路權(quán)值設(shè)置為無(wú)窮大。

在描述具體算法之前，引入以下變量：Ωo：候選備用ONU集合；NΩo：Ωo中ONU的個(gè)數(shù)；Ωw：候選備用無(wú)線路由器集合；Φo：所有待保護(hù)業(yè)務(wù)t所在的ONU集合；Tt：與業(yè)務(wù)t共享同一備用ONU容量的業(yè)務(wù)所在的工作ONU集合；Ψo：為待保護(hù)業(yè)務(wù)t分配的備用ONU集合；Ψw：為待保護(hù)業(yè)務(wù)t分配的備用無(wú)線路徑集合。

本文以某一待保護(hù)業(yè)務(wù)t為例，給出DS-SPP算法的主要步驟如下：

◆步驟1，初始化。

步驟1-1：輸入HOWBAN的網(wǎng)絡(luò)拓?fù)?，得到ONU、OLT、分光器和無(wú)線路由器的坐標(biāo)位置和每條光纖鏈路的故障概率；根據(jù)無(wú)線路由器的坐標(biāo)位置計(jì)算兩個(gè)路由器之間是否能夠直接通信，得到鄰接矩陣；令集合Ωo、Φ0、Tt、ψ0、ψw為空集。

步驟1-2：按照式（1）計(jì)算出每個(gè)ONU的工作光連接可用性，收集網(wǎng)絡(luò)中所有業(yè)務(wù)的帶寬請(qǐng)求和可用性請(qǐng)求，將所有工作連接可用性大小不滿足業(yè)務(wù)可用性請(qǐng)求的ONU放入Φ0中，將工作連接可用性大小滿足業(yè)務(wù)請(qǐng)求的ONU放入Ωo中，分別將兩個(gè)集合中的ONU按連接可用性從大到小排序。對(duì)于待保護(hù)業(yè)務(wù)t，DS-SPP算法優(yōu)先考慮選擇能夠?yàn)樗峁┹^大連接可用性的ONU作為備用ONU。

◆步驟2，選擇備用ONU。

步驟2-1：選擇Ωo集合中當(dāng)前ONUy作為候選的備用ONU，按照式（3）計(jì)算業(yè)務(wù)t的總連接可用性大小。若滿足At＞at，執(zhí)行步驟2-3；否則，執(zhí)行步驟2-2；

步驟2-2：選擇集合Ωo中的下一個(gè)ONU作為候選的備用ONU（即令y=y+1），若y≤NΩ0，返回步驟2-1；否則，將該業(yè)務(wù)丟棄，執(zhí)行步驟4-2。

步驟2-3：判斷ONUy中是否已有預(yù)留的備用容量。若ONUy中備用容量為空，執(zhí)行步驟2-4；若ONUy中已分配備用容量不為空，添加業(yè)務(wù)t共享其中的備用容量后，判斷Tt中所有ONU的業(yè)務(wù)總的連接可用性大小是否仍然滿足可用性需求。如果滿足，繼續(xù)進(jìn)行步驟2-4；否則返回步驟2-2。

步驟2-4：根據(jù)業(yè)務(wù)t報(bào)告的降級(jí)帶寬參數(shù)βt在備用ONUy中預(yù)留備用帶寬。若βt=1，那么此業(yè)務(wù)不可以進(jìn)行備用帶寬降級(jí)，需要預(yù)留100%的備用帶寬；若βt在0～1之間，需要預(yù)留的備用帶寬為βt×bt；若βt=0，則可以不用為此業(yè)務(wù)預(yù)留備用帶寬。成功分配業(yè)務(wù)t的備用ONU資源后，繼續(xù)執(zhí)行步驟3；如果備用資源不足，返回步驟2-2。

◆步驟3，部署備用無(wú)線路徑。

步驟3-1：遍歷Ωw中無(wú)線路由器的剩余帶寬容量，根據(jù)式（4）和無(wú)線路由器的鄰接矩陣將其轉(zhuǎn)換為無(wú)線鏈路的選路代價(jià)。

步驟3-2：利用Dijkstra算法尋找從源節(jié)點(diǎn)（工作ONU）到目的節(jié)點(diǎn)（備用ONU）的一條代價(jià)最小的備用無(wú)線路徑。如果找到，執(zhí)行步驟4-1；否則將業(yè)務(wù)t丟棄，跳到步驟4-2。

◆步驟4，輸出結(jié)果。

步驟4-1：記錄為待保護(hù)業(yè)務(wù)t分配的備用ONU、備用無(wú)線路徑，根據(jù)式（2）更新ONUy所能提供的備用連接可用性大小，更新ONUy的備用容量和無(wú)線鏈路權(quán)值，輸出Ψo、Ψw。

步驟4-2：為待保護(hù)業(yè)務(wù)t尋找備用資源失敗，將其統(tǒng)計(jì)到業(yè)務(wù)阻塞中。

2　計(jì)算機(jī)仿真及數(shù)據(jù)分析

本節(jié)利用VC++軟件搭建HOWBAN仿真平臺(tái)，對(duì)提出的DS-SPP算法進(jìn)行仿真分析，并與不考慮帶寬降級(jí)的基于連接可用性的保護(hù)算法［5］（用UDS-SPP表示）進(jìn)行對(duì)比。HOWBAN的前端WMN中100個(gè)無(wú)線路由器均勻分布在1000m×1000m區(qū)域中，后端PON 由16個(gè)ONU、5個(gè)分光器和三級(jí)光纖組成。零級(jí)光纖鏈路連接OLT到第一級(jí)分光器，可用性概率為1；一級(jí)光纖鏈路連接第一級(jí)分光器到第二級(jí)分光器，可用性概率在0.9995～0.9999之間隨機(jī)產(chǎn)生；二級(jí)光纖鏈路連接第二級(jí)分光器到各個(gè)ONU，可用性概率在0.999～0.9999之間隨機(jī)產(chǎn)生［5］。每個(gè)ONU的總帶寬容量為20個(gè)單位帶寬，每個(gè)無(wú)線路由器的總帶寬容量為10個(gè)單位帶寬。仿真中ONU的負(fù)載（匯聚的用戶業(yè)務(wù)量）可從3～5遞增到3～13個(gè)單位帶寬，用戶業(yè)務(wù)允許的降級(jí)帶寬參數(shù)β從0.1到0.9依次遞增，所有業(yè)務(wù)的可用性需求均為0.999。

仿真指標(biāo)為備用ONU容量、備用無(wú)線路由器容量及工作備用資源比。備用ONU容量表示為所有工作ONU提供保護(hù)所消耗的備用ONU的帶寬容量，其值越小表示備用ONU上預(yù)留的備用資源越小，算法性能越好。備用無(wú)線路由器容量表示建立無(wú)線備用路徑時(shí)無(wú)線路由器上需要預(yù)留的備用容量，同樣地，其值越小算法性能越好。工作備用資源比定義為后端PON中工作ONU容量和備用ONU容量的比值，其值越大意味著備用資源的利用率越高，算法性能越好。

圖1比較了不同業(yè)務(wù)負(fù)載下算法在不同β值下消耗的備用ONU容量，可以看出DS-SPP算法占用的備用ONU容量遠(yuǎn)遠(yuǎn)低于UDS-SPP。這是因?yàn)镈S-SPP算法考慮到網(wǎng)絡(luò)中部分業(yè)務(wù)可以忍受備用帶寬降級(jí)，不需要為所有業(yè)務(wù)都提供100%的備用帶寬，有利于降低預(yù)留的備用資源。另外，從圖中還可以看出：隨著β值的增大，DS-SPP算法需要預(yù)留的備用ONU容量增大，但是與UDS-SPP相比，DS-SPP算法還是大大降低了備用ONU的帶寬容量。

圖1　不同業(yè)務(wù)負(fù)載下備用ONU容量

圖2比較了不同負(fù)載情況下算法在不同β值下消耗的備用無(wú)線路由器容量大小，可以看出：隨著負(fù)載和β值的增大，備用無(wú)線路由器資源呈上升趨勢(shì)，但DS-SPP占用的備用無(wú)線路由器容量仍然遠(yuǎn)遠(yuǎn)低于UDS-SPP。這是因?yàn)镈S-SPP算法考慮了業(yè)務(wù)支持降級(jí)服務(wù)，因此在備用ONU中需要預(yù)留的備用ONU容量減少，相應(yīng)地需要通過(guò)前端WMN轉(zhuǎn)移的業(yè)務(wù)量減少，在前端預(yù)留的備用無(wú)線路由器容量較低。

圖2　不同業(yè)務(wù)負(fù)載下備用無(wú)線路由器容量

圖3給出了不同業(yè)務(wù)負(fù)載下不同算法的工作備用資源比的變化情況，可以看出：無(wú)論負(fù)載如何變化，DS-SPP算法的工作備用資源比均高于UDS-SPP，這說(shuō)明DS-SPP算法中相同數(shù)量的備用資源可以為更多的工作資源提供保護(hù)，體現(xiàn)了DS-SPP算法的優(yōu)越性。

圖3　不同業(yè)務(wù)負(fù)載下的工作備用資源比

與UDS-SPP算法［5］相比，DS-SPP算法能大大節(jié)約網(wǎng)絡(luò)中所需的備用ONU和備用無(wú)線路由器容量，擁有較高的工作備用資源比，算法效率較高。隨著降級(jí)帶寬參數(shù)β的增加，DS-SPP算法中節(jié)約的備用資源數(shù)量增大。因此，適當(dāng)?shù)乜紤]網(wǎng)絡(luò)中業(yè)務(wù)可忍受的降級(jí)備用帶寬，按照每個(gè)業(yè)務(wù)的不同需求預(yù)留備用資源，在滿足高級(jí)別用戶的需求同時(shí)還能夠節(jié)約網(wǎng)絡(luò)中的備用容量。

3　結(jié)束語(yǔ)

本文將降級(jí)服務(wù)的概念引入HOWBAN中，提出了一種支持帶寬降級(jí)的DS-SPP算法，該算法根據(jù)業(yè)務(wù)不同的連接可用性要求和降級(jí)帶寬需求，尋找合適的備用ONU和備用無(wú)線路徑并配置相應(yīng)的備用資源，為用戶提供滿足其可用性要求的連接服務(wù)，有利于減少網(wǎng)絡(luò)中預(yù)留的冗余備用資源，提高全網(wǎng)資源利用率。仿真結(jié)果表明：DS-SPP算法在滿足用戶可用性需求的前提下，最小化預(yù)留的備用ONU容量和備用無(wú)線容量，有利于實(shí)現(xiàn)較高的工作備用資源比，減少網(wǎng)絡(luò)資源消耗。

參考文獻(xiàn)：

［1］馬姍姍，何榮希.光無(wú)線混合寬帶接入網(wǎng)的現(xiàn)狀和發(fā)展［J］.光通信技術(shù)，2011，35（11）：36-39.

［2］AURZADA F，LEVESQUE M，MAIER M，et al.FiWi Access Networks Based on Next-Generation PON and Gigabit-Class WLAN Technologies：A Capacity and Delay Analysis［J］.IEEE/ACM Trans.Netw.，2014，22（4）：1176-1189.

［3］GHAZISAIDI N，SCHEUTZOW M，MAIER M.Survivability Analysis of Next-Generation Passive Optical Networks and Fiber-Wireless Access Networks［J］.IEEE Trans.Reliability，2011，60（2）：479-492.

［4］LIU Y，GUO L，GONG B，et al.Green Survivability in Fiber-Wireless（FiWi）Broadband Access Network［J］.Optical Fiber Tech.，2012，18（2）：68-80.

［5］LIU Y，GUO L，YU Y，et al.Connection availability based protection algorithm in wireless-optical broadband access network［J］.Science China Information Sciences，2014，57（4）：1-9.

［6］SAVAS S S，HABIB M F，TORNATORE M，et al.Network Adaptability to Disaster Disruptions by Exploiting Degraded-Service Tolerance［J］. IEEE Commun.Mag.，2014，52（12）：58-65.

［7］SHENG H，MING X，MARTEL C U，et al.A Multistate Multipath Provisioning Scheme for Differentiated Failures in Telecom Mesh Networks［J］. IEEE JLT，2010，28（11）：1585-1596.

［8］SAVAS S S，MA C，TORNATORE M，et al.Backup reprovisioning with partial protection for disaster-survivable software-defined optical networks［J］.Photonic Netw.Commun.，2015：1-10.

［9］THOTA S，BHAUMIK P，CHOWDHURY P，et al.Exploiting wireless connectivity for robustness in WOBAN［J］.IEEE Net.，2013，27（4）：72-79. ［10］KRAMER G.基于以太網(wǎng)的無(wú)源光網(wǎng)絡(luò)［M］.陳雪，孫曙和，劉冬，等，譯.北京：北京郵電大學(xué)出版社，2007.

中圖分類(lèi)號(hào)：TN929.18

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1002-5561（2016）06-0005-04

DOI：10.13921/j.cnki.issn1002-5561.2016.06.002

收稿日期：2016-01-22。

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61371091）資助。

作者簡(jiǎn)介：董丹（1990-），女，碩士生，主要研究方向?yàn)楣饩W(wǎng)絡(luò)。

Degraded-service aware shared-path protection algorithm in hybrid optical-wireless broadband access networks

DONG Dan，HE Rong-xi
（College of Information Science and Technology，Dalian Maritime University，Dalian Liaoning 116026，China）

Abstract：Based on the characteristics of hybrid optical-wireless broadband access networks（HOWBAN），a degraded-service aware shared-path protection algorithm（DS-SPP）has been proposed in this paper.With a comprehensive consideration of connection availability，bandwidth demand and degraded-service for different network users，DS-SPP chooses backup ONUs with less reservation of backup bandwidth.And then it reroutes the affected traffic from the work ONU to the backup ONU through the front wireless mesh network（WMN）. The simulation results show that，DS-SPP reserves less backup ONU capacity and wireless router capacity and has a higher primary-backup capacity ratio.

Key words：HOWBAN，protection，degraded-service，share，wireless mesh network（WMN）