薛文革，陈莉
(上海电信技术研究院，上海200122)
摘要：生存性是光传送网络中亟待解决的问题.文章基于环网的优良保护倒换能力提出了环覆盖保护策略，给出了选择环覆盖的控制流程，建立了以保护容量需求作为优化目标的环覆盖优化设计模型.
关键词：生存性；环覆盖；整型线性规划；网状网
光传送网络的拓扑结构一直是网络设计人员所关注的问题[1].尽管当前可用的拓扑种类较多，但人们往往比较喜欢网状结构，这是因为网状光传送网络具有高度连通性，所以无论是在正常状态还是故障状态下它都能有效地使用网络资源，从而使得网络容量需求达到最小，但其结构复杂,使得网络资源的控制和管理变得复杂.当发生故障时除了需要硬件交换器以外，还必须使用大量的软件处理(恢复消息的交换和处理、网络配置数据库的一致性维护以及波长信道分配策略等)才能够实现受损业务的恢复，导致故障恢复时间较长，可靠性差。
环形拓扑是所有通信网络都支持的一种结构，在目前的计算机网络和电信网络等领域中正运行着大量的环形网络；它也是光传送网络的一种主要拓扑结构，尽管在容量效率方面比不上网状结构，但它具有一些网状结构无法达到的优良特征，尤其当发生网络故障时，环形网络通过硬件交换器可以轻松地实现网络保护，倒换速度快，可靠性高.正是基于这一优良特性,我们提出了环覆盖保护方法.
1 分层互连环
网络规模是影响环形网络性能的一个关键因素，在环形网络中，随着节点数的增加，网络容量需求以及业务节点间的路径长度将明显增加，这限制了单个环形网络能够容纳的节点数目.为了在大规模网络中利用环形网络的优点，比较实际的做法就是对网络节点分组，然后为每个分组建立一个环形网络，且这些环形网络之间通过公共节点相互连接，从而形成具有层次结构的互连环网(Interconnected Ring)；如果每个环都具有生存能力(即属于自愈环类型)，则称该互连环是为自愈互连环[2～3].
分层互连环根据网络规模可以划分成不同等级，除了最顶层仅包含一个环形网络之外，其它各层都包括一定数量的环网络.较高层次的环可以互连多个较低层次的环，它们的连通性是通过层间公共节点(Common Node)，也被称作互连节点(Interconnecting Node)的桥接作用来保证的，各个环在正常状态下的操作以及故障状态下的自动保护交换都是相互独立的.图1给出了两层互连环的典型拓扑结构，其中，(a)为单归宿(Single homing)型网络，它包括4个初级环和一个2级环，它能够处理任何单个链路故障.但由于环之间仅通过一个公共节点进行连接，所以它无法处理发生在这些公共节点上的故障，此时的互连环被分割成两个“孤岛”，失去了物理连通性的网络显然是不可恢复的.为了解决这个问题，单归宿型互连环网络必须在环之间增加一个冗余公共节点，即必须构建双归宿(Dualhoming)型互连网才能保证网络在公共节点有故障时也是可生存的.图1(b)描述了它的基本结构，图中的所有初级环都是通过两个公共节点与2级环进行互连的.
由于分层互连环的各组成环相互独立，这为网络消除多个故障的影响提供了可能.只要这些故障分布在不同的环网上，它们总能够得到妥善的处理；而且在时间上可以重叠，即具有并发处理特征，这将极大地减少网络保护倒换时间；尤其是在理想情况下，多个故障的处理时间能够做到与单个故障的处理时间几乎相等.
2 环覆盖保护原理
分层互连环是一个比较理想化的解决方案，实际的网络结构存在很大的任意性，它们难以构建出具有严格上、下层次关系的互连环网.为了既适应网络结构的随意性，又能够发挥出环形网络的优势，我们在分层互连环的基础上提出了环覆盖技术，它能够有效地满足上述两项要求.所谓环覆盖(Ring Cover)就是一个必须覆盖网络所有链路的环形网络集合，它实际上是一种混合(Hybrid)互连环结构，与分层互连环不同的是环覆盖中的各组成成员(即环形网络)之间不存在任何关联.环覆盖保护就是通过互连的环形网络来实现对受损业务的保护倒换，它可以将网状网络的业务保护时间缩短到与自愈环大体相当的程度.
根据图论的连通性理论我们可以从网状光传送网络得出如下推论：
推论1：一个给定的网状结构网络可以存在多个环覆盖；
推论2：环覆盖中的环网络尺寸大小可以不一样；
推论3：环覆盖为了覆盖所有的网络链路和节点，必定有使用相同网络链路(节点)的环存在；
推论4：网络路径总是被环覆盖中的一个或多个环所容纳，它不可能超越环覆盖的作用范围；
推论5：单个网络故障影响的工作业务需要环覆盖中提供保护的环个数不得超过覆盖该故障的环个数；
推论6：特定路由上的业务只能由环覆盖中的单个环提供保护；
根据上面分析可以看出：环覆盖技术特别适合于缩短网状光传送网络保护倒换时间，这对于大容量的波长传输信道尤其重要.因为在相同的倒换时间内，它中断的业务数据流量要远远高于任何传统传输网络.
3 环形网络的构建
由于网状拓扑的网络结构可以对应多个环形网络，如何构建并确定合适的环形网络是实施环覆盖保护的先决条件.根据业务负载传输要求，可以将环形网络的构建策略分成两种类型，一种是环内(IntraRing)传输策略；另一种就是环间(InterRing)传输策略.前者是指网络上的所有业务传输只能局限在某一特定的环形网络内部，而不能传输到其它环形网络当中；后者则没有这个限制，它允许业务传输路由跨越单个或者多个环形网络.从理论上讲，我们希望在传输时业务尽可能跨越数量较少的环形网络[5].
图2给出了一个环内传输策略范例，它通过R1=1，2，3，4，5，6｝、R2=｛4，5，6，7，8，9｝和R3=｛1，2，3，4，6，7，8，9｝这3个环形网络来保证网络的任何业务传输都图2环内传输策略可以仅使用一个环即可.例如节点对(1,5)、(4,8)和(1,9)的通信分别使用环形网络R1、R2和R3，没有其它选择；而节点对(1,2)的通信既可以使用R1，也可以使用R3，但最终还是只能确定其中一个.较简单的处理方法就是选择较小的环形网络，但也可以根据网络的业务分布以及链路容量进行选择，这样能够充分利用网络的信道资源，但控制复杂度较高.
图3给出了一个环间传输策略范例，尽管这种情况下的环形网络构建没有限制，但最后的结果必须能够满足网络业务的传输要求.例如环形网络R1=｛1，2，4，5｝、R2=｛2，3，5，6｝、R3=｛4，5，7，8｝和R4=｛5，6，8，9｝就是一个符合需求的结果，所有的网络业务总是能够通过它们的组合得到传输.例如节点对(1,2)和(5,9)的通信仅需要分别使用单个环形网络R1和R4即可，而节点对(1,8)间的通信必须使用环形网络R1和R3的组合才能完成.
环内传输策略与环间传输策略的根本差异在于最终环形网络的大小问题.前者可以避免网络业务跨越多个网络而带来的控制复杂性，但它使得某些环形网络变得非常庞大，甚至会违背环覆盖的初衷，因为互连环本身就是为了克服较大规模的网络结构而提出的；尽管第2种策略的复杂度较高，但它的“区域分割”机制能够真正使用环形网络的固有优势，因此，本文仅针对环间传输策略进行进一步的分析和研究.
4 环形网络选择策略
如果将网状结构的网络看作是一个连通性无向图，那么环形网络的构建问题可以转化成无向图的圈(Cycle)搜索问题[4～6].对于一个强连通图而言，它往往可以搜索出多个不同的圈，这些圈的大小(可容纳在圈上的节点数目)可以相同，也可以不同.基于图论的圈搜索算法尽管很多，但它的实现一般比较复杂，文献[6]提出了一种简单的启发式圈搜索算法，它可以同时适用于无向图和有向图.
从上面分析我们可以得知：一个网状网络可能同时包含多个环形网络，且其数量随着网络规模的扩大成比例增长，它们的可能组合将非常庞大.例如在18节点的欧洲RACE2028计划网络中，它可以生成1 228个大小不同的环形网络.如果仅使用其中的12个环形网络来试构建可行的环覆盖，将会出现2.8×1031种可能组合.因此，计算并比较所有可能的环覆盖以便确定其中的最优者将极为复杂，这使它在实际应用中难以实现.
不过，我们可以充分利用已有的环形网络知识压缩不必要的环覆盖，从而降低计算复杂度.影响环形网络性能特征的核心因素在于它的大小，即较小者在容量使用效率和保护倒换时间等性能优势方面要明显超过较大者.理论上已经证明： 在大小为N且业务需求均匀分布的环形网络中，平均每个业务连接需要经过N2/4(N-1)条链路(N为偶数)或者(N+1)/4条链路(N为奇数)，这表明对于同等级别的业务而言，大环总是比小环需要更多的容量；同时小环在保护倒换时间上具有一定的优势.因此，构建环覆盖的候选环形网络必须限制在一定的规模范围以内；这不仅可以发挥小环的性能优势，而且能有效地解决计算复杂度问题.
经过上述分析可以发现环覆盖设计问题必须包括业务分布、环形网络搜索、构建环覆盖需要的候选环以及环覆盖优化5个基本功能模块，图4给出了环覆盖设计问题的功能模块控制流程.
5 环覆盖保护优化模型
由于环覆盖保护本身能够保证最小网络保护倒换时间需求，因此，它的优化设计主要集中在容量需求领域.在提出环覆盖保护优化设计模型之前，我们先给出它的适用环境，即必须满足下列假设条件：
· 只能在单个网络故障状态下对业务保证完全恢复，而对于多故障必须要求它们分布在不同的环形网络当中；
· 网络链路上的波长保护信道只能在环形网络内部共享，而各环形网络之间不能共享任何保护波长信道；
· 为了减轻网络控制管理复杂度，要求经过同一网络链路的环形网络数量不得超过某一预置的门限值；
· 为了降低网络节点复杂度，要求方位同一节点的环形网络数量不得超过某一预置的门限值；
· 为了简化环覆盖设计问题，假定网络节点具有完全波长转换能力.
符号定义：
· N：网络节点集合；
· L：网络光纤链路集合；
· D：业务连接集合，即可能的源、宿(s-d)节点对集合 ，如果网络满足全连通关系，则｜D｜=｜N｜·(｜N｜-1)/2，它表明任意两个节点之间都存在业务连接；
· dm：网络业务连接m的光路径需求；
· lj：链路j的物理距离；
· Nl：允许经过同一网络链路的最大环形网络数量；
· TMax：常量参数，表明网络链路提供工作波长信道的上门限值；
· CMax：常量参数，表明网络链路提供保护波长信道的上门限值；
· R：用于构建环覆盖的候选环形网络集合；
· Pm：网络业务连接m的工作路由集合；
· ：表明网络业务连接m的第p条工作路由是否经过链路j，如果是则 =1，否则 =0；
：表明环形网络r是否包含链路j，如果是则=1，否则=0；
· ：表明链路j上的负载流量是否需要环形网络r的保护，如果是则=1，否则=0；
· ：网络业务连接m的第p条工作路由的物理长度，它的数值等于沿途经过链路的长度总和；
· ：环形网络r的物理长度，它的数值等于包含在该环形网络中的所有链路长度的总和；
· ：业务连接m要求工作路由p提供的光路径需求；
· δr：表明环形网络r是否被确定为环覆盖的组成部分，如果是则δr=1，否则δr=0；
· cr：环形网络r为提供保护而必需的保护波长信道需求.
上述符号中，、δr和cr是随后环覆盖优化设计问题需要求解的变量，其它各符号可以从现有网络拓扑以及业务规划中得到具体数值.下面以网络容量总需求(同时包括工作容量和保护容量)为优化目标建立数学模型.
优化目标函数：
约束条件：
(1) 任何网络业务在它的工作路由上所建立的光路径总和必须满足负载流量需求，即：
(2) 对于任何承载工作光路径的网络链路，至少需要一个覆盖该链路的环形网络对它提供保护，即：
(3) 波长保护信道只能分配给构成环覆盖的那些环形网络，且其容量不得超过预定的门限数值，即：
(4) 对于任何网络链路，包含它的环形网络必须得到足够的保护波长信道容量以保护那些正在使用该网络链路的工作光路径，即：
(5) 环覆盖中利用同一网络链路构建的环网网络数量不能超过预置的上限(该约束条件在一定程度上也可以限制访问同一节点的环形网络数目)，即：
(6) 环形网络保护波长信道容量需求以及业务连接保护路由分担的恢复流量必须满足非负整数要求，即：
环覆盖保护设计问题就是求解以上描述的整型线性规划问题，至于它的求解存在许多方法，我们可以采用一些启发式算法来解决此类组合优化问题.
6 结论
我们可以看到环覆盖保护方法不但可以使网状结构的光传送网络能够利用环形网络的优点，而且提高了网络在多故障场合下的生存能力.但由于强连通网络可能构造出多个不同的环覆盖，它们将直接影响网络的保护容量需求、光节点硬件结构以及网络控制和管理，因此，如何选择一个合理的环覆盖就成为实施环覆盖保护技术的关键.
参考文献
［1］Wayne D, Grover. Case studies of survivable ring, mesh and mesharc hybrid networks [J]. Proc. GLOBECOM, 1992,1:633 638.
［2］Proestaki A, Sinclair M C. Design and dimensioning of dualhoming hierarchical multiring networks [J]. IEE ProcCommun, 2000, 147(2):96104.
［3］Jianxu Shi, John P, Fonseka. Hierarchial selfhealing rings [J]. IEEE/ACM Trans. Networking, 1995, 3(6):690697.
［4］Andrea Fumagalli, Isabella Cerutti, Marco Tacca, et al. Survivable networks based on optimal routing and WDM selfhealing rings [J]. ICC 1999(8):726733.
［5］Wuttisittikulkij L, O'Mahony M J. Design of a WDM network using a multiple ring approach [J]. GLOBECOM, 1997(11):551555.
［6］Gardner L M, Heydari M, Shah J, et al. Techniques for finding ring covers in survivable networks [J]. GLOBECOM, 1994(3):18621866
