HOWBAN中支持降級服務的共享保護算法

董丹，何榮希（大連海事大學信息科學技術學院，遼寧 大連116026）

?

中文核心期刊

HOWBAN中支持降級服務的共享保護算法

董丹，何榮希
（大連海事大學信息科學技術學院，遼寧 大連116026）

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

關鍵詞：光無線混合寬帶接入網；保護；降級服務；共享；無線網狀網

0　引言

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

1　算法描述

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

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

其中，FOp（u）表示集合Op（u）中的ONU到OLT光路徑上的光纖鏈路集合，Fy表示ONUy到OLT的光路徑上的光纖鏈路集合。對某一業務t來說，部署備用ONU后，能夠為該業務提供的可用性大小為工作ONU和備用ONU不同時發生故障的概率，即：

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

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

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

◆步驟1，初始化。

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

步驟1-2：按照式（1）計算出每個ONU的工作光連接可用性，收集網絡中所有業務的帶寬請求和可用性請求，將所有工作連接可用性大小不滿足業務可用性請求的ONU放入Φ0中，將工作連接可用性大小滿足業務請求的ONU放入Ωo中，分別將兩個集合中的ONU按連接可用性從大到小排序。對于待保護業務t，DS-SPP算法優先考慮選擇能夠為它提供較大連接可用性的ONU作為備用ONU。

◆步驟2，選擇備用ONU。

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

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

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

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

◆步驟3，部署備用無線路徑。

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

步驟3-2：利用Dijkstra算法尋找從源節點（工作ONU）到目的節點（備用ONU）的一條代價最小的備用無線路徑。如果找到，執行步驟4-1；否則將業務t丟棄，跳到步驟4-2。

◆步驟4，輸出結果。

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

步驟4-2：為待保護業務t尋找備用資源失敗，將其統計到業務阻塞中。

2　計算機仿真及數據分析

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

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

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

圖1　不同業務負載下備用ONU容量

圖2比較了不同負載情況下算法在不同β值下消耗的備用無線路由器容量大小，可以看出：隨著負載和β值的增大，備用無線路由器資源呈上升趨勢，但DS-SPP占用的備用無線路由器容量仍然遠遠低于UDS-SPP。這是因為DS-SPP算法考慮了業務支持降級服務，因此在備用ONU中需要預留的備用ONU容量減少，相應地需要通過前端WMN轉移的業務量減少，在前端預留的備用無線路由器容量較低。

圖2　不同業務負載下備用無線路由器容量

圖3給出了不同業務負載下不同算法的工作備用資源比的變化情況，可以看出：無論負載如何變化，DS-SPP算法的工作備用資源比均高于UDS-SPP，這說明DS-SPP算法中相同數量的備用資源可以為更多的工作資源提供保護，體現了DS-SPP算法的優越性。

圖3　不同業務負載下的工作備用資源比

與UDS-SPP算法［5］相比，DS-SPP算法能大大節約網絡中所需的備用ONU和備用無線路由器容量，擁有較高的工作備用資源比，算法效率較高。隨著降級帶寬參數β的增加，DS-SPP算法中節約的備用資源數量增大。因此，適當地考慮網絡中業務可忍受的降級備用帶寬，按照每個業務的不同需求預留備用資源，在滿足高級別用戶的需求同時還能夠節約網絡中的備用容量。

3　結束語

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

參考文獻：

［1］馬姍姍，何榮希.光無線混合寬帶接入網的現狀和發展［J］.光通信技術，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.基于以太網的無源光網絡［M］.陳雪，孫曙和，劉冬，等，譯.北京：北京郵電大學出版社，2007.

中圖分類號：TN929.18

文獻標識碼：A

文章編號：1002-5561（2016）06-0005-04

DOI：10.13921/j.cnki.issn1002-5561.2016.06.002

收稿日期：2016-01-22。

基金項目：國家自然科學基金資助項目（61371091）資助。

作者簡介：董丹（1990-），女，碩士生，主要研究方向為光網絡。

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）