基于资源个性化需求感知的生存算法设计

林 国 勇

(广西民族大学相思湖学院 广西 南宁 530008)

0 引 言

为了应对云计算和大数据技术部署下光网络载荷呈现指数级暴增的情形，在传统光网络链路层、网络层、传输层的网元中植入多效控制件构建智能控制平面，使各层网元支持相同信令的构思应势而生。在智能控制平面的介入下，光传送网在实施基于不同SLA[1]波长业务的故障智能定位、智能检测、智能自愈将成为可能。以ASON[2]为例，该网络突破了传统网络受链路构建方式束缚而无法为不同SLA波长业务提供承载安全保障的瓶颈，通过改善光路资源管理效率、扩展局向协议来促进光传送网上通路资源的调度，以降低SLA波长业务请求失效的风险，提升全网的生存性。同时ASON的部署克服了繁琐的电路配置产生巨大的时间代价问题，使该网络在响应不同SLA的波长业务对资源请求差异化服务提供了可能。正是这些优势吸引了业界频繁地在ASON上开展与波长业务承载算法相关的探讨，但其中多以通路保护研究为主。甚至一些组织机构也从功能框架上对ASON的生存机制进行统一界定。以国际电联制定的8080建议为例，该建议虽然规定了各类波长业务遭遇异常服务质量(QoS)时的自愈方法，但却未明确自愈实施细则。作为该建议的补充，国际互联网工程任务组为ASON在实施波长业务承载过程中可能面临通路资源匮乏的风险定义了SRLG，以降低自愈过程中工作通路(WC)和保护通路(PC)同时失效的风险。

当前，与此SRLG相关的通路研究主要有ILP算法、APF算法、KSP算法。ILP算法思想[3-4]虽能规避通路对因共享的物理资源遭遇异常而同时失效的风险，但繁琐的计算过程和高昂的时间成本均表明复杂度不占优势。且计算复杂度与网络规模呈正比的特征进一步局限了该算法只能部署在规模较小的网络中，降低了实用性。APF算法机制[5-6]是通过参照链路途经SRLG的数量规模对链路权值进行定义，以便让WC尽可能避开那些隶属于多个SRLG的链路。虽然该机制在计算复杂度方面有所改善，却忽略了链路带宽利用率极小化以及SRLG陷阱等关键性问题。KSP算法策略[7]是从节点对中计算出K条最短WC用于规避波长业务请求失效的风险，然后参照权值排序锁定基于SRLG分离的最佳通路对。虽然提升了实用性，但随波长业务规模增加，算法复杂度也将上升。尤其在参数K较大的情形下表现出的时间代价依然较大。此外，虽存在另外一些复杂度和时间成本均较低的相关研究，比如基于业务区分的路由算法[8]，但事实证明这些研究极易遭遇通路对同时失效的风险。少数研究即便顾及到SRLG陷阱风险问题，也因缺乏考虑不同SLA波长业务对通路资源的客观需求而限制了这些研究的可部署性。基于上述主流研究的单一性，本文从算法复杂度和时间成本代价角度出发，本着兼顾SRLG陷阱问题和SLA区分的原则，构思了一种基于不同SLA波长业务对通路资源客观需求感知的自愈算法，旨在改善ASON在应对波长业务承载期间全网的生存性[9]。

1 基于分离原则的SLA可靠性分析

既有的生存算法研究虽是基于SRLG理念对波长通路展开保护，但只考虑2条以内链路出现故障的情形。这样的保护思想从表面上看虽然使得WC和PC都保持了分离的状态，但部署在复杂网络中时两者却极有可能同属于某一个SRLG。一旦该SRLG出现异常QoS事件，势必导致WC和PC同步失效。可见，该情形下的链路分离、网元分离只能视为SRLG的一种特殊情况而不具备广泛的适应性。因此要显著改善复杂全局网络的生存性，就不得不考虑在源宿网元对内部计算出不但不属于同一个SRLG，还要满足波长业务对通路资源可靠性需求的WC和PC。以此规避WC和PC因同一个SRLG出现异常QoS而引发的通路对同步失效风险，即遵循相对分离原则。基于该原则计算出的通路对可为不同SLA提供通路资源的可靠性保证。

假设五个网元构成了如图1所示的布局图，其对应的SRLG拓扑结构如图2所示。此时由网元1向网元3发起一个波长业务的连接请求。根据KSP启发式算法思想，将最短的e3直接定义为网元对[1,3]的WC。然而此举决定了后续难以从全网中寻得与e3保持SRLG分离的PC。这是缘于网元对[1,3]间的其他组合路径，如e5+e4，e6+e7+e4，e1+e2，和作为WC的e3同时归属于第3个、第8个SRLG。因此KSP算法的计算策略无法保证全网的生存性。

图1 网元布局图

图2 共享风险链路组图

但是，相对分离原则下的生存算法在感知e3与e5+e4、e6+e7+e4、e1+e2隶属于相同SRLG后，将重新计算出路径组合e1+e2用于取代e3，定义为网元对[1,3]之间波长业务的WC，同时将路径组合e6+e7+e4定义为该波长业务下基于SRLG相对分离的PC。可见，相对分离原则下的生存算法在满足波长业务对带宽资源需求的前提下，可为波长业务的承载与保护提供良好的保障。同时，根据SLA协议规定，在通路对中承载不同层级的波长业务时，可通过测试该波长业务在一定周期内实施路由[10]局向的稳定程度来定义不同层级波长业务的可靠等级。因此，在全局网络中为不同SLA波长业务提供一个基于不同等级可靠性的资源需求为前提，寻找一个基于SRLG相对分离的通路对方案是可行的。

2 算法设计

2.1 失效风险模型

定义一个共享了光纤/缆、通道和路径等物理资源的通路对对应于某编号的共享风险链路组(S-No.)。一旦上述四个层次的物理[11]资源出现异常，则源宿网元对之间所有链路上的各等级SLA波长业务都将面临失效风险。若这些链路在不同程度上共享了不同的物理资源，那么链路上各等级SLA波长业务面临的失效风险程度也将有所不同。因此链路对物理资源的共享程度与相同S-No.内的链路出现失效风险的概率息息相关。假设某一个S-No.内有n条链路，且定义m

L(srlg)=P(m失效|n失效) (m,n)∈srlg

由于在实际应用中，该失效率的参数可通过链路所共享的四个层次物理资源来量化，故此处假设该失效率为给定的赋值。

2.2 基于SLA资源需求模型

实际应用中由于并非所有的波长业务均要求提供1∶1的带宽资源保护，也就是无需在基于SRLG绝对分离的情形下为所有不同SLA的波长业务寻找通路对。于是，本次研究的思路调整为只要通路对的资源能够满足不同SLA波长业务的可靠性需求即可，无需遵循SRLG绝对分离的原则。因此，为使链路满足某一个波长业务对带宽资源的可靠需求，要求波长业务对链路带宽资源的可靠率R必须超过通路对同时失效的可能性，即：1-R≥L(WC,PC)。

式中，S-m和S-n分别为链路m和链路n所对应的S-No.集合。由此可得：

将通路对中对应于同一个S-No.的链路定义为风险链路，同时令srlg-i为某一个S-No.。当定义每条链路仅对应于唯一的S-No.，那么在风险链路仅一条时，上述公式演化为：

(S-m)∩(S-n)=srlg-i,m∈WC,n∈PC

当存在多个风险链路的情形时，上述公式进一步演化为：

(1-Am)]

在遵循相对分离原则的前提下，若存在多个风险链路，只要其满足该式即可视为该链路是符合不同SLA的波长业务对带宽通路资源的可靠性需求[13]。

为了评估每个链路作为通路对的可行性，算法将为每一个链路定义两个权值评估函数分别展开计算。通过该函数的动态考量，将搜索出SRLG中的风险链路用于实施不同SLA的波长业务对带宽通路资源的可靠性需求分析。令某个通路对的权值为σwc-l和σpc-l，当源节点发起波长业务请求时，为通路对的链路分别赋予权值函数。该权值函数分别记作：

若假设全局网络的链路带宽资源均衡[14]分布，则链路总带宽Ball为一个恒数。同时链路的闲置带宽表征为Bidle。定义C为一个数值较大的恒数。如果途径WC的链路和l同属于某一个S-No.，则要参照公式

(1-Am)]

进一步分析这样的风险链路能否符合不同SLA的波长业务对带宽通路资源的可靠性需求。

3 算法实施

步骤1初始化全网，将迭代计算参量置零。若未收到建立链接的请求指令，根据全网链路初始权值等状态参量动态[15]更新链路的权值；若收到建立链接的请求指令，进入下一步骤。

步骤2若迭代计算参量为零，经由σwc-l函数更新所有链路的权值，并根据Dijsktra算法规划出WC。如果未能寻得WC，则返回步骤1；反之进入下一步骤。若此时迭代计算参量不为零，则参照前一次迭代计算过程计算出来的WC权值，根据Dijsktra算法规划出WC。如果依旧不能寻得WC，说明建立链接的请求指令被中断，此时需重返步骤1；反之进入下一个步骤。

[L(srlg-i)·(1-Am)]之间的关系来判断当前通路对能否符合不同SLA的波长业务对带宽通路资源的可靠性需求。若前者小于后者，表明通路对未能符合不同SLA的波长业务对带宽通路资源的可靠性需求。此时随机定义一条风险链路的工作权值并赋值∞，同时对迭代计算参量执行一次加法计数后返至第二个步骤。

4 算法成效

对生存算法成效的评估主要在NSFNET网络上开展，其结构如图3所示，可见整个网络共有21个链路和14个网元。假设每个链路仅分配唯一的S-No.，该链路平均最大可承载16个波长业务，链路的平均可靠率在区间[0.97，0.99]内。同时假设14个具有全光波变换[16]功能的网元中可随机生成源宿网元对，且每一次所发起的业务连接建立请求均被定义为是一个波长业务的带宽，该波长业务也在此源宿网元对之间随机产生。该波长业务对链路资源的可靠性要求在区间[0.97，1]内。假设算法开展三次迭代计算，且为单个SRLG的失效率参数赋值0.5、0.3、0.2。

图3 NSFNET网络拓扑图

为了考察生存算法在筛选通路方面的相对优势，在通路资源配置上选择专用保护算法(SPA)与生存算法做对比分析。对于SPA算法，其思想是为每一个WC配置一个专用的PC，且要求网中其他的光通路不能分享该PC上的光波带宽资源。算法对ASON全网波长业务的保护成效可通过分析阻塞率、资源占用率和PC跳数等指标[17]来确定。

图4描述了两种算法下的不同SLA波长业务请求链接的通畅程度。正如前文所述，并非所有波长业务均要求提供1∶1[18]的通路资源保护，即无需在基于SRLG绝对分离情形下为所有不同的SLA波长业务寻找通路对。本文构思的生存算法正是基于此实际情况而设计，因此算法依据不同波长业务对通路资源可靠性要求的不同，在不存在SRLG绝对分离的通路对情形下，依然可搜索出合适的PC用于为不同SLA的波长业务提供链接请求保障。但SPA算法却无法针对此情形响应出有效的选路策略，进而导致该波长业务的链接请求无法获得保证。同时，生存算法主张的循环迭代计算机制在应对PC无法符合SRLG相对分离要求的情形时，可自动将风险链路删除并重新实施路径的计算与分析，从而避免陷入无解的境况。相比之下，SPA算法在面对此情形时却无法搜索到和WC保持分离的PC。正是由于上述原因才导致生存算法在应对不同SLA波长业务请求时能保证较好链接率。

图4 不同算法下SLA波长业务通畅程度

图5所示曲线描述了不同算法下PC跳数大小情况。该指标体现了不同SLA波长业务的自愈时长，是衡量ASON生存能力的重要指标之一。其自愈时间和PC的段数呈正比。观察图中曲线可知，生存算法在本项测试中表现出的PC段数相对较少，因此该算法的自愈时长较短，于是实施该算法的ASON将具有更好的生存性。导致生存算法曲线走势总体较低的原因是该算法在搜索PC时将那些和WC同属于某一个编号S-No.的链路也考虑在内，展开选路的计算。但SPA算法思想与此截然相反，其选路机制主张放弃那些与WC同属于某一个编号S-No.的链路。这就决定了SPA算法的计算对象锐减，需绕行更远的链路方可获得PC。这显著增加了PC的段数，进而使得SPA算法下的跳值曲线走势总体偏高。

图5 不同算法下PC跳值

图6所示为不同算法下的PC资源被占用的程度。该指标主要用于描述为一个SLA的波长业务链接请求需要的WC资源，所提供的预留PC资源的规模，可定义为WC和PC跳数的比值。从图中曲线走势不难看出，生存算法下的ASON保护带宽资源被占用的程度较低。缘于生存算法的思想主张，在保持通路相对分离的前提下若WC可满足不同SLA波长业务对其资源[19]的可靠性需求，就不再额外地去占用PC资源，因此可最大程度降低波长业务的请求对ASON全网开销资源的消耗。故生存算法在节约全网通路资源方面表现出了SPA算法所不具备的优势。

图6 不同算法下PC资源占用程度

根据表1数据显示，对于相同业务量的SLA波长业务请求，随着迭代计算频次的增加，业务通畅程度逐步好转。但纵观三组测试[20]数据可见，好转幅度最为显著的是在赋值2和3期间，在随后的表现中这种变化趋势较为微弱。因此在本次定义的ASON网络环境中，三次以内的迭代频次对生存算法效能度的影响最佳。

表1 迭代计算频次对波长业务通畅度的影响力

5 结 语

助力大数据技术在ASON中的融合应用发展，首要解决的问题是网络生存性。本文从生存性指标出发提出了一种基于不同SLA波长业务对通路对资源不同需求的生存性算法。算法本着相对分离原则从SRLG中规划出科学的通路对用于实施SLA波长业务的承载。评估数据表明所构思的生存算法能够较好地改善ASON在应对SLA多波长业务承载请求时的生存能力。相对于传统的算法方案，本文算法具有更优的全局性和适应性。