各种新型网络应用的出现丰富并改善着人类的生活.虽然通信技术和计算机网络的发展为新型应用提供了有力支持，但是由于目前网络的异构性、移动性、不稳定性等特点，导致网络在发生故障时用户的连接可靠性得不到保证.而且新型应用对网络QoS的要求越来越高，客观上要求网络提高容错能力并兼顾QoS保证^[1].容错QoS路由是有效方法之一.

容错路由是保证连接可靠性的重要方法，通常分为预防式和反应式两类.由于反应式策略的时间代价高，不能很好地满足用户QoS需求，因此，本文采用预防式策略，并通过共享路径保护和SRLG分离的策略一定程度上弥补预防式策略备份资源利用率低的缺陷.

实际通信中，由于网络参数是动态变化的，用户对QoS的需求难以定量地准确表达，且链路状态的测量也是不精确的^[2].因此，本文通过采用模糊数学相关方法定量地描述不精确的网络参数和用户相关QoS需求.

容错QoS路由问题是多约束下求解可行路径的问题，属于NP完全问题，而用于解决此类问题的启发式算法往往具有很大的局限性.因此，本文采用结合PSO算法的全局寻优能力和SA算法较强跳出局部最优解能力的PSOSA智能优化算法解决此问题，该混合优化算法已被成功应用，具有较好的性能.

文献[3]提出划分网络失效独立恢复域的方法，保证域内恢复时间的上限.文献[4]提出共享备份路径恢复机制，分离的备份路径可共享同一链路上的带宽.文献[5]用模拟退火构造备份路由表来恢复网络中单链路故障.该方案只将故障点和受影响的邻居节点上的流量转移到备份路径上.文献[6]提出一种可调生存性生成树的机制来解决网络失效问题，该机制可量化任意生成树的生存性来提供灵活的路由选择，并同时考虑树的QoS.文献[7]提出基于快速生成树重连接的以太网生成树，使用部分空间保护机制来提供不同的保护性，使用备份带宽来保护小部分链路，具有更少的信令开销、更快的恢复和更少的重路由次数.文献[8]使用通道和多址技术解决网络双链路或单节点失效.文献[9]提出概率相关失效的最小化链路失效的跨层模型.通过该模型，网络可以量化备份路径的可靠性，并基于此选择多个可靠备份路径来保证通信.文献[10]提出基于虚拟网络的容错机制，建立物理网络和虚拟网络映射关系，并通过机会弹性嵌入的方法反应式地保护虚拟链路.

从上述研究工作可以看出，已有研究成果很少兼顾容错和QoS双重需要，并且没有考虑路由信息的模糊性.为此，本文在满足用户QoS条件的前提下综合考虑了路由信息的模糊性、备份资源利用率和故障恢复率.

1 问题描述 1.1 网络模型与用户需求

将真实的网络拓扑抽象成一个无向连通图G=(V, E)，V是节点集合，E是链路集合^[11].对于E中的每条链路e_l，设其可用带宽为[Bw_L, Bw_H]、延迟为[Del_L, Del_H]、出错率为[Los_L, Los_H].用户QoS路由连接请求包括：带宽需求[bw_rq_L, bw_rq_H]、延迟约束[del_rq_L, del_rq_H]、出错率约束[los_rq_L, los_rq_H].

1.2 链路参数与路径QoS评价

链路e_l能够满足用户带宽需求bw的概率S_B^l(bw) 和延迟约束del的概率S_D^l(del) 分别用式 (1)，式 (2) 描述.

(1)

(2)

其中k＞0，ε＞0且ε<<1.式 (2) 表明链路能够提供带宽bw的概率与带宽值负相关.

将占用的实际带宽定义为UBw^l，其中l∈P，P为路径，B_L是瓶颈带宽，值为Min_l∈P(UBw^l).实际占用带宽g_B^P定义如式 (3)，式 (4)：

(3)

(4)

其中：f_B^P(UBw^l) 表示用户在瓶颈带宽为UBw^l时的满意度函数；S_B^l(UBw^l) 表示链路能够保证提供带宽UBw^l的概率；路径P可以满足用户带宽需求的概率为P上各个链路能够保证提供带宽的概率的乘积.

同样，设用户使用路径P上的各段链路l的延迟取值区间为[Del_L^l, Del_H^l]，令，，则路径P端到端延迟取值区间为[D_L, D_H].故P上端到端延迟的概率g_D^P定义如下：

(5)

(6)

其中，f_D^P(del) 表示端到端延迟为del时的满意度函数.链路延迟计算定义为对路径延迟值在变化区间积分.

对于链路e_l满足出错率约束los的概率S_L^l(los) 的定义以及路径P的出错率评价函数g_L^P(los) 的定义与延迟约束相关定义类似，只需将del用los替换即可.最后定义端到端路径的QoS评价函数：

(7)

其中：α_B，α_D和α_L分别代表带宽、延迟和出错率所占的权重；0≤α_B, α_D, α_L≤1，α_B+α_D+α_L=1.本文将出错率的权重设为1/2，带宽和延迟的权重各为1/4.

1.3 SRLG分离的路径保护

SRLG是指共享同一失效风险物理资源的一组链路.每个SRLG全局唯一，每条链路可能属于一个或多个SRLG.对于预防式容错QoS路由机制而言，若工作路径wp_n和保护路径bp_n同时失效 (n为编号)，则故障无法恢复.本文仅考虑单SRLG故障的情况.

基于SRLG分离的路径保护是在源和目的之间找到1条工作路径和1条不经过同一SRLG的保护路径. SRLG条件故障概率定义为

(8)

其中CP (srlg) 表示当SRLG故障时，共享该SRLG的2条链路l_i和l_j同时失效的概率.若连接可靠性要求 (即路径可靠度) 为RD，则wp_n和bp_n同时失效的概率应小于1－RD，即这2条路径需满足式 (9) 条件：

(9)

其中，CSIS是wp_n和bp_n共享的SRLG的集合.若对于wp_n中每个srlg有CP (srlg)＜(1－RD)/P (wp_n failure)，则称此srlg为不需要被保护的SRLG；否则，称此srlg是需要被保护的SRLG (protected-SRLG，PSRLG)，找到的保护路径须PSRLG分离.

1.4 优化模型

优化目标是以用户QoS需求为前提，使端到端可靠性、代价和QoS评价值达到最优目标值.链路代价函数c′_l定义如下：

(10)

其中：p_l为预留的备份资源；r_l为剩余资源；tp_l为恢复单SRLG故障所需的保护路由资源最大值；c_l为基本代价.优化目标及约束如式 (11)~式 (16) 所示：

(11)

(12)

(13)

(14)

(15)

(16)

2 算法设计 2.1 解的表达和初始解的生成

PSOSA算法的每一个解为一条路径，采用向量表示：P(i)=(e₁, e₂, …, e_len)，e为链路，所有链路组成从源到目的的一条路径.采用随机路径算法生成初始解.

2.2 适值函数

从工作和保护路径对中选择一对使端到端可靠性、代价和QoS评价值达到最优的路径作为本次循环的当前最优解.所以，适值函数定义为

(17)

其中JP为跳数.式 (17) 表示适值越小，路径质量越高.

2.3 路由容错质量评价

通过算法寻找到的同一连接请求的主从路径对需要符合下述两个条件：

1) 工作路径和保护路径需PSRLG分离；

2) 共享保护资源的工作路径间需PSRLG分离.

2.4 初始温度选择及退温函数选择

初始温度采用公式t₀=kδ确定，k=10, 20, 100, …等试验值；δ=f_max－f_min，f_max和f_min分别为初始解中最大和最小的目标函数值.

将粒子群变换的新解作为模拟退火算法等温过程的初始解.收敛准则采用Metropolis准则，其中，适值函数 (17) 即为能量函数.退温函数选用常用的t_k+1=α·t_k形式，其中α=0.9.

2.5 粒子飞行速度和位置更新

i时刻粒子当前位置用X(i)=(e₁ⁱ, e₂ⁱ, e₃ⁱ, …, e_lenⁱ) 表示，迭代更新后的粒子位置用X(j)=(e₁^j, e₂^j, e₃^j, …, e_len^j) 表示，粒子飞行速度为v(i)，于是有

(18)

(19)

将v(i) 定义为一组变换：

(20)

变换Ψ_k将X(i) 中的一个分量 (1条边) 变成X(j) 中的对应分量.其中式 (18) 表示将粒子位置“先作v(i) 变换，再作v(j) 变换”.式 (19) 表示其逆向操作.

设粒子id在时刻i的位置为X_id(i)，速度为v_id(i)，则下一时刻i+1的位置可以表示为

(21)

(22)

式 (22) 中，从初始时刻到i时，id历经过的最佳位置为P_id(i)，P_gd(i) 为全局最优位置. w，c₁，c₂是对应的偏差权重系数. c₁×rand ()₁和c₂×rand ()₂分别表示位置变换P_id(i)－X_id(i) 和P_gd(i)－X_gd(i) 发生的概率.其中，一般取w由大到小递减变化，变化范围0.9到1.2，表示PSO算法从广泛到局部精细搜索变化.加速常数c₁和c₂取值为2，rand () 是随机数生成器 (0到1).

2.6 工作流程

  算法PSOSA.

输入:

G=(V, E), bw_req_L, del_req_H, los_req_H, k, α, t₀, NC_max, RD, SRLG－list

输出:wp, bp

1.  Initialize particle swarm P by Stochastic Path Method; /*Include N particles*/

2.  For 1 to i do

3.   While P_i can’t satisfy the s.t.(14)~(16)do

4.   Regenerate P_i by Stochastic Path Method;

5.  End while

6.  Calculate the fitness value of P_i by (17);

7. End for

8. Select P_i with min fitness value as P_gd;

9. While do

10.   Generate the SIS of P_gd; /*SIS is srlg set of a path*/

11.   For 1 to j do

12.    If CP (srlg_j)≥(1－RD)/P(P_gd failure)then add srlg_j into SIS_d; /*SIS_d is srlg set that must be disjoint*/

13.  End for

14.   Calculate the subgraph G’by delete the SIS_d;

15.  Find the suboptimal P′_gd in G’;

16.  If Sig of Al.2==0 then wp←P_gd; bp←P′_gd; Update SRLG－list;

17.  If NC＞NC_max then Reject Request;

18.    Calculate the new position and new velocity by (21)，(22) of each P_i;

19.    While P_i can't satisfy the s.t.(14)~(16) do

20.    Regenerate P_i;

21.   End while

22.  Update the P_gd with smaller fitness value;

23.   While 1 to i do

24.    If ΔE＜0 of P_i then update the P_i;

25.    Continue

26.   Accept the P_i by Metropolis Criterion;

27.   End while

28.  Annealing by t_k+1=α·t_k;

29. End while

30. Return wp←P_gd; bp←P′_gd; Update SRLG－list

算法1~8行的作用是生成满足约束的初始粒子群，并选出当前全局最优粒子；9~16行的作用是为不满足可靠度要求的工作路径生成备份路径，并输出符合容错质量评价条件的主从路径；算法18~22行的作用是计算粒子更新后的新速度及新位置，选择满足约束条件的新粒子；算法23~27行的作用是更新满足约束条件的新粒子的适应值，并根据Metropolis准则判断是否接受；算法28行的作用是进行退温.

3 性能评价

基于NS2平台在4个实际的网络拓扑 (NSFNet、CERNET2、CERNET和GEANT) 上对本文设计的机制 (PSOSA) 进行仿真实验，并与采用基于多Agent进化算法的机制 (Multi-Agent)，文献[8]提出的机制 (FRuT) 和文献[12]提出的机制 (DRLR) 进行对比分析.

NS2平台的相关仿真参数如表 1所示.每个SRLG的条件故障概率随机从10%，20%，50%选择.请求到达速率和持续时间分别服从对应参数的泊松分布和指数分布.

4种机制的路由成功率对比如图 1所示.结果表明对于网络参数的动态性，PSOSA和Multi-Agent有较强的适应性，FRuT只考虑双链路失效，而DRLR考虑单链路失效且没有考虑网络参数的动态变化问题，因而性能较差.

图 2给出在CERNET拓扑上4种机制平均资源占用量的对比.结果表明随着负载的增加，4种机制平均资源占用量逐渐减小，资源利用率都逐渐增高，但增高速率PSOSA较DRLR有较大提升.这是因为PSOSA采用共享通路的保护策略，全局优化了资源配置，使其没有更多的冗余预留.因为Multi-Agent算法缺乏全局信息，依赖Agent的自治行为实现进化，容易陷入局部最优解，所以增高速率不如PSOSA.而FRuT虽然同样采用共享通路的保护策略，但其多址技术增加了资源预留.

4种机制的故障恢复率比较如图 3所示.结果表明PSOSA在4个拓扑中的故障恢复率性能在小型拓扑上较优，而在较大型的拓扑上和Multi-Agent相差无几.因PSOSA可以处理单SRLG故障，容错能力较DRLR大大提高.而由于FRuT可以处理单节点故障，所以FRuT稍逊于PSOSA.

为了验证拓扑结构对算法的影响，在给定的4个拓扑上运行4个算法. 图 4对比了4个算法在不同拓扑上获得最优解所需的平均迭代次数. 图 5对比了4个算法相应的平均运行时间.结果表明4个算法对于网络规模变化是敏感的，迭代次数和运行时间都会相应增加.在拓扑规模和复杂度较小的网络中，平均迭代次数相差无几，但是PSOSA在平均运行时间上性能较Multi-Agent算法有较大提升，这是因为PSOSA只需要根据已有的信息进行分量的替换，而Multi-Agent算法中复杂的繁殖过程增加了时间开销.虽然在算法性能层面本文PSOSA的表现与FRuT和DRLR相比提升不明显，但是提高了容错率、资源利用率和故障恢复率.

4 结语

本文采用模糊数学分析方法，定量刻画动态、不精确网络的环境，采用SRLG模型和共享路径保护提高预防式容错策略的资源利用率，提出一种优化的网络容错QoS路由模型，并结合PSOSA混合优化算法解决了预防式多约束下容错QoS路由问题.仿真结果表明，本文的机制可以在允许时间范围内找到优化的主从路径，具有较好的性能.今后的研究重点是如何使网络模型更加客观合理和如何使算法更加高效.