摘  要： 在光网络通信中，计算路由常常会出现共享风险链路组(SRLG)分离和“陷阱”问题。针对这种现象，提出了一种基于SRLG不相关的陷阱避免算法，并采用阿尔卡特朗讯公司的光网络规划工具1356NT进行验证。实验结果表明，与传统路由算法相比，该算法不但缩短了恢复时间，还有效提高了网络连接的可靠性和网络资源的利用率。
关键词： 光网络；共享风险链路组；陷阱避免

　计算机通信网络的可靠性问题十分复杂，抗毁性[1]是其中尤为重要的一点。目前维护网络生存性的方式有很多种，其中最切实可行的就是为每个请求建立两条“物理分离”的路径，分别为工作路由和保护路由，一旦工作路由出现故障，业务可以立刻转换到保护路由上进行。IETF组织针对此提出了共享风险链路组SRLG(Shared Risk Link Group)的概念[2]，对“物理分离”的路径进行进一步抽象和深化。SRLG被定义为共享同一个物理资源的一组链路，同时也是共同承担失效风险的一组链路。
    目前国内外计算路由的算法很多，基于SRLG限制的路由问题已经被证明是NP-完全问题[3]。现有文献提出多种算法来解决该问题，但都有不同程度的缺陷。参考文献[3]提出的整数线性算法，其时间复杂度较大；参考文献[4]提出基于SRLG限制的动态共享通路保护算法，网络资源利用率不高；参考文献[5]提出工作路由优先(APF)算法，虽然简单可靠，但却不能解决“陷阱”问题。本研究基于传统的TA算法[5]，提出了一种新型基于SRLG不相关的陷阱避免算法，并在1356NT平台上进行验证。实验结果标明，该算法成功避免了“陷阱”问题，从而提高了网络连接的可靠性。对于中小型网络，在链路故障发生后，可以使恢复时间控制在50 ms以内，资源利用率提高17.23%，具有较强的实用价值。
1 理论研究
1.1 SRLG限制条件
　每一个SRLG都对应着一个唯一的标识，即SRLG标识。SRLG分离的两条路径可以减少同时失效的可能性，从而提高光路的抗毁能力。传统的多路由保护方式只考虑单一链路或双链路故障，而不考虑SRLG故障。这样一来，如果工作通道和保护通道经过同一SRLG，即没有SRLG分离，就很容易因SRLG故障而同时失效。本研究提出的算法是基于SRLG不相关的情况，该算法需要考虑以下两个SRLG限制条件：(1)在为同一个业务分配工作通道和保护通道时，必须使它们处在两个不同的SRLG里；(2)如果不同的保护通道共享链路上的同一资源，那么，这些保护通道对应的工作路径必须处在不同的SRLG里。这样就可以避免SRLG故障，大幅降低工作路由和保护路由同时失效的可能性，从而提高网络整体的生存能力。
1.2 “陷阱”问题
　基于SRLG分离的双路由选择策略最简单的方法是：当选好工作路由后，将工作路由经过的链路以及这些链路所处的SRLG中的所有链路全部删除，然后再进行备用路由的选择。这种算法称为工作路由优先(APF)算法，它较为简单，并且保证了工作路由和备份路由的SRLG分离，但存在一个明显的缺点，即容易造成备用路由无法获取的情况，如图1所示。以节点D到节点C的连接请求为例来对这种情况进行描述。
　图1中链路上的数字代表权重，工作路由为D-E-B-C，删除工作路由经过的所有链路(即D-E，E-B，B-C)之后，节点D和节点C之间便不存在任何路由。但实际上，这两个节点之间可以找到两条SRLG分离的路由，即D-A-B-C和D-E-F-C。这就是由APF算法的缺陷所导致的“陷阱”问题。

2 算法设计
　结合以前很多研究学者对于光网络中路由保护算法的研究，在传统TA算法的基础上，综合APF算法，本文提出了一种新型的基于SRLG不相关的“陷阱”避免算法。该算法不考虑每条链路上SRLG的数量，同时令每条链路上都有唯一的SRLG标识，该算法适用于SRLG数目不多的中小型网络，简单灵活，并且避免了SRLG故障和“陷阱”问题，对传统的TA算法进行了一定程度的改进。
2.1 网络模型
　为了方便描述算法，光网络图例拓扑由一个四元函数来表示：G(L，N，C，S)，其中，L代表光网络中所有链路的集合，并且全部为双向通信；N代表光网络中全部节点的集合；Cij代表在第i个节点和第j个节点之间链路的权重(代价)；S代表所有SRLG标识组成的集合。规定主路由集合用AP(Active Path)表示，备份路由集合用BP(Backup Path)表示，cost表示每条链路的权重，M为一个权重较大的值，并且规定每条链路都有不同的SRLG标识。
2.2 算法步骤
　基于SRLG不相关陷阱避免算法的具体步骤如下：
　(1)确定网络拓扑G(L，N，C，S)，等待动态业务连接请求到达。如果有业务连接请求到达，转至步骤(2)；否则，更新网络状态。
　(2)检查图G中源节点和目的节点的度是否小于2，如果是，则退出算法，因为不可能找到两条SRLG不相关的路径；否则，跳转到步骤(3)。
　(3)根据APF算法，先计算出图G中的最短路径，放入AP中，并将AP中所有的边从图G中删除，记为图G，然后检查图G′中源节点和目的节点之间的连通性。如果是连通的，即还有路径可达，则计算出一条最短路径，放入BP中，此时AP和BP两条SRLG不相关的路径已经找到，退出算法；如果不是连通的，即没有路径可达，则可能出现“陷阱”问题，由步骤(4)~(6)来解决此问题。首先将图G中所有的信息放入图GAP中，并跳转到步骤(4)。
　(4)将AP和BP设置为空，将GAP中所有边的权重恢复至图G中的原始数据，先计算出图GAP中一条最短路径，放入到AP中。如果AP为空，则不存在主路由。
　(5)在图G中将AP所有边的权重改为M，并在图G中再次计算出一条最短路径，放入到BP中。如果BP为空，则不存在备份路由。
　(6)计算AP和BP的边交集T。如果交集为空，则AP和BP两条SRLG不相关的路径已经找到，退出算法；如果交集不为空，则从图GAP中将边交集T删除，如果图GAP中的边不为空，则返回步骤(4)，否则退出算法。
该算法的流程图如图2所示。

2.3 算法实例
　以图1所示的网络为例，说明该陷阱避免算法如何工作。对于节点D和C之间的连接请求，由步骤(4)~(6)算得AP为(D，E，B，C)，BP为(D，A，B，C)，AP和BP的边交集T为(B，C)，从图GAP中删除边T后，重复步骤(4)~(6)，算得AP为(D，E，F，C)，BP为(D，A，B，C)，此时，AP和BP没有交集，即找到两条SRLG不相关的路径，从而避免了“陷阱”问题。
3 算法验证及分析
　为了验证此算法的正确性和有效性，实验采用阿尔卡特朗讯公司的1356NT作为测试平台，1356NT是一种智能光网络解决方案的分布式网络分析和规划工具。验证算法的网络拓扑结构如图3所示。

　图3中A、B、C、D、E代表网元(NE)，每条链路上的数字代表该链路的权重，并设置每条链路的SRLG不相同，保证了SRLG的不相关性。通过1356NT测试平台，可以查看到相应的工作路由、备份路由以及恢复时间。对该算法的验证主要从可靠性、恢复时间和资源利用率三个方面进行。
3.1 实验步骤
　测试项目：两条业务，多次故障。
　(1)在图3所示的网络中，建立一条从C→D的标签交换路径(LSP)，设置保护类型为PRC，主路由为C-D，备份路由为C-E-D；
　(2)在相应端口设置SDH分析仪；
　(3)断开主路由，即C和D之间连接的光纤，查询并记录恢复路由和恢复时间；
　(4)断开备份路由，即C和E之间连接的光纤，查询并记录恢复路由和恢复时间；
　(5)断开工作路由和保护路由，即C、D之间和C、E之间连接的光纤，查询并记录恢复路由和恢复时间。
3.2 实验结果及分析
　实验结果如表1所示。

　PRC类型的业务始终有两条路由，即一条主路由和一条备份路由，当其中一条发生故障时，网络会重新为该业务寻找一条新的路由，当主路由和备份路由都发生故障时，网络则会为该业务建立两条路由。
从表1可以看出，当主路由或备份路由发生故障时，按照APF算法计算的备份路由均为C-A-B-D，当主路由和备份路由同时发生故障时，电路存在“陷阱”问题。如果按照APF算法计算出的路由只有一条，即C-A-B-D，不能满足PRC业务的需求。而按照本研究中提出的算法，可以计算出两条SRLG不相关的路由，即C-A-D和C-B-D，避免了“陷阱”问题，提高了整个网络的可靠性。
　从恢复时间上分析，该算法应用到该网络的恢复时间均小于50 ms，相对于其他算法而言，恢复时间快、效率高。
　从资源利用率上分析，用Load表示资源占用率，假设该PRC业务的速率为ODU1(2.5 G)，NE的Load=每个网元节点使用的带宽/网元总的带宽；链路的Load=每个链路使用的带宽/链路总的带宽，通过在该软件中查看相应的表，计算出网元的Load=0.26%，链路的Load= 25%，相对于其他算法，资源利用率提高了17.23%。
随着网络信息量与日俱增，提高网络抗毁能力的重要性日益凸显。考虑SRLG约束，建立两条SRLG不相关的路径可以降低工作路由和保护路由同时失效的可能性，从而提高网络的生存能力。在传统TA算法的基础上，本研究提出了一种新型基于SRLG不相关的陷阱避免算法，并在阿尔卡特朗讯公司1356NT平台上进行验证。实验结果表明，该算法成功避免了“陷阱”问题，提高了网络连接的可靠性，在链路故障发生后，可以让恢复时间控制在50 ms以内，资源利用率提高17.23%，具有较强的实用价值。本算法仅适用于中小型网络，并未考虑SRLG复杂的网络类型，这将是以后研究的方向。
参考文献
[1] 刘啸林.网络抗毁性研究介绍[J].计算机应用与软件，2007，24(6)：135-137.
[2] PAPADIMITRIOU D， POPPE F， JONES J. Inference of shared risk link groups [EB/OL]. http：//www.watersprings.org/pub/id/draft-many-inference-srlg-02.txt，2001-11-14
[3] HU J Q． Diverse routing in optical Mesh networks [J].IEEE Transactions on Communications，2003，51(3)：489-494．
[4] Guo Lei ， Yu Hongfang ， Li Lemin  ． Dynamic shared-path protection based on SRLG constraints in WDM Mesh networks[A]． ICCCAS 2004． Chengdu， China： IEEE PRESS，2004．
[5] Xu Dahai，Xiong Yizhi，Qiao Chunming． Failure protection in layered networks with shared risk link groups[J]．IEEE Network， 2004，18(3)：36-41.