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）