可重构服务承载网主动保护算法研究

齐宁，汪斌强，王志明

（1. 国家数字交换系统工程技术研究中心，河南 郑州 450002；2. 中国人民解放军61062部队，北京 100091）

1 引言

互联网由于基于IP分组交换、资源统计复用和“尽力而为”服务模式的特点，辅以Overlay、CDN、VPN、MPLS等技术大大拓展了其所能承载的业务范围，一定程度上满足了规模化的交互式数据业务、音视频业务和多播业务等承载要求，但并未从根本上解决互联网面临的问题，众多业务仍需通过构建物理专网的形式来运营，也使得目前的互联网体系难以支撑网络融合的需求。

深入分析产生上述问题的原因，一方面在当前的互联网体系架构下，部署新的服务和技术需要对网络系统进行升级和改造，而互联网庞大的规模导致这种改造成本过高。另一方面，互联网是由众多异构的自治域组成，分别由不同的互联网服务提供商（ISP）建设、运营和管理，仅仅一个ISP部署应用新技术只能获得很少的收益，而要其他ISP都同意这样做是非常困难的。因此，虽然目前互联网应用上的创新层出不穷，但是在网络技术本身的创新却处于停滞不前的僵化境地[1]。

基于上述分析，摆脱传统网络技术体系的束缚，着眼于网络服务的创新视角，以用户业务需求为驱动，提出了面向服务承载的可重构柔性网络（RFNet,reconfigurable flexible network）技术体系[2,3]，将网络基础设施提供和服务提供2大功能实体在逻辑上分离。基础设施提供商建设、管理和维护物理网络基础设施；服务提供商基于可重构路由交换平台[2,3]，对现有和未来可能出现的用户业务进行科学聚类，针对某一类业务根据其业务特性需求，通过构建可重构服务承载网（RSCN, reconfigurable service carrying network）的方式（如图1所示）为终端用户提供满足业务特性需求的通信服务。物理网络负责提供网络资源，服务承载网负责提供特定价值的服务，从而在共享由不同基础设施提供商提供的底层物理网络资源基础上，能同时支持多个不同服务提供商的异质的网络体系结构并存，为用户提供多样化的网络服务。比如构建了支持视频业务的服务承载网后，可以为终端用户提供高质量的视频点播、IPTV、视频会议、视频电话等业务，并且可以根据网络资源状况对用户接入数量进行控制，以保障网络服务质量。通过将网络服务提供从基础设施提供中分离出来，可重构柔性网络技术使得网络服务的创新变得更加灵活，这种逻辑上的分离使得二者可以独立地演进，可以在支持现有服务的同时灵活地部署新的网络服务。

图1 RFNet中构建RSCN

由于IP骨干网网络故障的时有发生[4,5]，从而造成RSCN服务中断，给用户带来不好的用户体验，同时还给服务提供者造成经济损失，特别是一些重要的应用，如有线电视网络，链路故障造成的负面影响更是不可估量。因此，如何对已构建的RSCN提供可靠有效的保护机制亟待解决，这就迫切需要研究RSCN主动保护模型和机制，在检测到故障后，能够迅速采取措施，将流量切换到保护路径，尽量减小损失。

本文主要解决的问题包括RFNet资源重要程度的描述、RSCN主动保护模型建模、主路径和保护路径构建算法等。本文组织结构如下：第2节对国内外相关研究现状进行论述；第3节对RSCN主动保护问题进行建模，并给出刻画资源紧迫程度的方法；第4节论述RSCN主路径和保护路径构建算法；第5节对本文提出的算法进行理论和仿真分析；第6节是结束语。

2 相关研究

针对RSCN的构建方法，主要集中在虚拟网和逻辑承载网构建算法的研究[2,6,7]。文献[6]利用混合整数规划，针对不同应用场景，有效结合节点映射和链路映射过程，分别提出了确定型虚拟网映射算法(D-ViNE)和随机虚拟网映射算法(R-ViNE)。文献[8]提出了两阶段虚拟网映射算法，首先进行节点映射，然后利用最短路算法，并基于多商品流问题进行路径集映射。文献[9]以构建成本为约束条件，以构建收益最大化为目标，研究虚拟网构建映射问题。文献[7]基于链路负载均衡度和节点负载均衡度提出自适应的均衡虚拟网构建方法。文献[2]以映射路径上所有节点的平均强度最小为目标，采用启发式算法构建逻辑承载网。以上虚拟网和逻辑承载网构建算法主要针对虚拟网构建进行最小代价或最短路径优化，没有考虑节点或链路发生故障及拥塞时的处理策略。

为此，文献[3]针对网络的动态性，提出了带迁移同时考虑网络均衡的逻辑承载网构建方法。文献[10]基于流量均衡实现虚拟网的拓扑设计，采用周期性地节点优化策略进行虚拟网重映射，但文中提出的算法首先假设资源提供能力没有限制，且节点映射算法复杂度较高，难以实际运用。文献[11]以提高传统虚拟网映射算法的需求接收率和负载均衡为目的，设计了虚节点和虚链路的重映射机制。文献[12]通过预计算备份链路，在发生链路故障时将主路径的数据迁移到备份链路上，从而避免服务中断。上述算法基于网络均衡对虚拟网构建进行重新优化映射，或者没有考虑如何避免物理网络发生故障后对RFNet造成的影响，或者提前计算每条物理链路备份路径并预留带宽，成本太高。

其他还有一些针对 IP-over-WDM 分层网络的可生存性机制的研究工作：文献[13]基于图论设计了高效可扩展的网络故障保护机制 SMART，通过缩小已经映射的子图降低逻辑拓扑的复杂度，从而有效地计算出自愈拓扑映射；文献[14]扩展了最大流最小割理论，提出了新的连接矩阵，采用规划和限界技术最大化保护链路连接度，从而提供较强的网络保护能力；文献[15]针对IP-over-WDM网络的可生存性映射算法，基于整数规划、人工智能搜索算法和图论设计了优化算法。然而，这些算法并不适用于RFNet，首先RSCN的构建请求是实时的，RSCN保护模型本质是个在线问题，而不像上述文章将网络生存性研究抽象成离线问题；其次，设计目标不同，本文要求在网络构建成本尽可能小的情况下，进行RSCN保护路径的规划，在网络故障发生后，确保已经构建的RSCN能够保持联通，从而保证网络收益的最大化，而上述文章的目标主要是保证物理网络的连通性。

针对RSCN主动保护问题，本文的解决思路是，首先结合节点和链路的联通度，对不同网络资源在网络中的重要性进行刻画，在RSCN主路径和保护路径的构建过程中尽量避免使用易成为瓶颈的资源；在构建RSCN主路径时，以构建代价最小为目标，从而保证物理资源的充分利用；在构建RSCN保护路径时不仅要考虑构建代价，还要尽量避免占用紧迫程度较高的资源，从而避免易发生网络故障的资源成为备份资源，提高保护路径的可靠性。

3 RSCN主动保护问题建模

3.1 网络模型

有权无向图 Gp= ( Np,Ep)表示物理承载网络，其中， Np和 Ep分别表示物理网络中节点和链路的集合，对于每个 n ∈Np，CN(n)表示物理节点n能够提供的能力，如节点交换能力；同样，对于每个e∈Ep，表示物理链路e能够提供的能力，如链路带宽。 M B( e)表示经过链路e的所有RSCN虚链路分配的主带宽； P B( e)表示经过链路e的所有RSCN虚链路分配的保护带宽； R( e)表示物理链路的剩余带宽。则 R ( e) = CE(e) - M B( e) - P B( e)；同样可以定义物理节点剩余能力 R ( n)。

有权无向图 Gr= ( Nr, Er)表示 RSCN构建需求，其中， Nr和 Er分别表示RSCN构建需求中虚节点和虚链路的集合，对于每个表示构建请求中对节点承载能力的约束；对于每个表示构建请求中对链路承载能力的约束。

3.2 RSCN构建模型

由于在RSCN构建时需要考虑保护路径，因此，RSCN构建问题包括2个步骤。

1) 主路径构建

一个 RSCN主路径构建问题可以描述成从 Gr到 Gp子集的一个满足 Gr中约束条件的映射 Gs，如式（1）所示。

由于一个 RSCN构建请求中节点位置是确定的，RSCN构建问题可以简化成链路映射，仍是个NP难问题[16]，可以利用启发式算法求解。

2) 保护路径构建

除了进行RSCN主路径构建之外，针对网络故障保护，还需要对RSCN的链路构建保护路径。

对于虚链路re，为了保证在链路故障时其故障链路上的数据流能得到保护，必须保证 er的保护路径和主路径没有重复映射链路。可以利用k最短路算法或双重主路径方法[12]求解保护路径。但是，直接利用上述算法并没有对保护资源进行区别对待，可能产生更多瓶颈资源，从而导致网络故障波及范围扩张，对后续RSCN的可用性产生恶性循环。为此必须对网络资源进行刻画，具体见3.3节描述。同时，考虑到经济性和实用性，保护路径不需预留与主路径等同的带宽，可按照服务提供商与基础设施提供商的协定预留相应能力的资源。

一个 RSCN保护路径构建问题可以描述成从Gr到 Gp子集的一个满足 Gr中服务提供商与基础设施提供商的协定保护带宽的映射 Gps，如式(2)所示。

其中，Nps⊆Np, Eps⊆Ep, Cps代表网络保护能力。

不失一般性，本文研究单链路故障的情况。因此，可以考虑将共享保护路径的资源进行聚合，进一步提高资源利用率。

3.3 资源紧迫度

为了对不同网络资源在网络中的重要性进行刻画，本文首先提出资源紧迫度（RSF, resource stress factor）的概念，主要包括 2个元素：联通度（CF,connectivity factor）和饱和度（SF, saturation factor）。

如图2所示的网络中，由于许多链路都经过节点e，一旦节点e发生故障，将导致大面积的网络瘫痪，网络的联通性所受影响最大。因此，节点 e对网络联通程度的影响最大，其故障导致的网络联通性破坏程度也最大。为此，引入如下概念。

图2 网络联通度

定义1 节点影响度：在网络pG 中，设节点in的度数为id，则向量为节点对邻接点的影响度向量，称之为节点影响度。

定义 2 节点联通度：物理网络资源的节点 CF刻画了由于节点故障给剩余网络造成分割的程度。设A( Gp)为Gp的邻接矩阵，则向量 N CF = N I · A(Gp)为各节点对网络联通性的影响程度， N CF( ni)的值越大，节点联通度越大，采用式（3）对其进行归一化后，称之为节点联通度。

定义 3 链路联通度：链路的邻接节点影响度可以反映该链路故障对网络连通性的影响程度，表示成称之为链路联通度。

定义 4 饱和度：用于刻画当节点或链路发生故障时，有多少 RSCN会受到影响。如式（4）所示。

其中，SF(x)表示资源x的饱和度，x可以是节点资源，也可以是链路资源，k表示资源x承载RSCN的个数，xPM 表示资源x中已分配资源的百分比。

定义 5 资源紧迫度：综合考虑节点联通度、链路联通度和饱和度，由此得到资源紧迫度，如式（5）所示。

其中，Ψ(x)表示x的资源紧迫度，α和β是调节因子，且 α +β=1。Ψ(x)值越大表示资源x的故障对网络影响越大。

3.4 构建目标

本文的目标是在满足RSCN构建请求约束条件的前提下，充分利用剩余网络资源，对RSCN的主路径和保护路径进行合理规划，从而保证在网络故障时，RSCN故障损失尽可能小。为此，结合资源紧迫度以及资源初始价值，给出改进后的RSCN构建代价函数，如式（6）所示。

其中，c( em)和c( nm)分别代表构建的RSCN主路径所占用的物理链路和节点的初始代价， c( eb)和c( nb)分别代表构建的 RSCN保护路径所占用的物理链路和节点的初始代价。由式（5）可知，资源紧迫度越高，占用其资源构建RSCN时付出的代价越高。

此外，还需要保证网络故障发生后的RSCN故障损失尽可能小，为此，假设链路l的故障恢复时间为 R T( l)，则链路l发生故障后，受其影响的RSCN故障损失如式（7）所示。

其中，M ( l)表示映射到链路l上的RSCN虚链路集合， B W( es)表示虚链路 es分配的带宽。

4 RSCN主动保护算法

不失一般性，本文将RSCN构建需求分解为由RSCN中邻接的2个节点和连接这2个节点的链路带宽的基本需求，由三元组(,,)s t d表示，其中，s、t为邻接节点，d为带宽需求，每一个三元组称为一个元需求。

完成对需求的分解之后，RSCN主动保护构建算法（RAPA, RSCN active protection algorithm）简化为对元需求逐一求解的过程。元需求主路径映射实际上就是在pG 中确定一条连接s和t的路径，记为,stP ，且,stP 满足：

其中，b(e)表示分配给相邻节点的链路带宽。保护路径映射是在pG 中另外确定一条连接s和t的路径，记为,'stP ，且,'stP 满足：

其中，'b(e)表示分配给相邻节点的保护带宽，pb表示保护带宽需求。

分解之后，原先较大规模的全图映射问题转换为求解多个单一链路的映射问题，从而将RSCN构建的复杂问题简化。RAPA包括2个子算法：资源紧迫度感知的主路径构建算法（RSF-awareMLCA,RSF-aware main link construction algorithm）和RSCN保护链路构建算法（RPLCA, RSCN protection link construction algorithm），RAPA描述如下。

算法1 RAPA( Gp,Gr)

输入： Gp,Gr

输出： Gs, Gps

1) 初始化 Gs← N ULL ， Gps← N ULL ；

2) 分解RSCN构建需求 Gr；

对每一个RSCN构建元需求 Rmeta= ( s, t, d)，执行3)到 5)步：

4.1 RSCN主链路构建算法

对于每个RSCN构建元需求，可能存在多条可达路径，应该选择构建代价最小的路径作为备选路径。

为了得到连接 2个节点s和t之间的代价最小路，首先需要将 Gp的权值矩阵 W ( Gp)做如下改进：

然后利用最短路算法，找出代价最小路径。RSF-awareMLCA描述如下。

子算法1 RSF -awareMLCA( Gp,Rmeta)

输入： Gp,Rmeta

输出：,stP

1) 初始化,stP 为空；

2) 按照式（8）更新W(p)G，利用最短路算法寻找满足 ,s t之间带宽需求且代价最小的路Ps,t，如果这样的路径不存在，置Ps,t为空，跳转到4)；

3) 更新Ps,t路径上节点和链路的剩余服务能力；

4) 若Ps,t非空返回主路径构建结果Ps,t；若Ps,t为空，无法RSCN构建元需求。

算法第2)步更新权值矩阵，并且基于新的权值矩阵计算出 ,s t间的最短路Ps,t；第3) 承载能力。对于元需求，如果找不到最小代价路，则RSCN主路径构建失败。

4.2 RSCN保护链路构建算法

传统的思路是在构建RSCN之前，对每条物理链路均计算出保护路径，当发生链路故障后，可以从保护路径集中选择合适链路进行保护，这种方式并不能保证形成最优的保护路径，浪费很多链路资源，降低了链路利用率；本文的思路是当RSCN构建请求到达后，进行主路径构建映射的同时，即进行保护路径的构建。构建保护路径时不仅要考虑构建代价，还要尽量避免占用紧迫程度较高的资源，从而避免易发生网络故障的资源成为备份资源；对于保护带宽的设置，由于同时发生链路故障的可能性很低，可以将共享同一条保护链路的所有RSCN链路中保护带宽最高值作为预留带宽值。RPLCA描述如下。

输入： Gp,Ps,t

输出： P 's,t

1) 去除 Gp中 Ps,t经过的所有链路，并按照式（8）更新权值矩阵；

2) 按照式（9）给出的带宽满足条件，利用最短路算法寻找 s, t之间的最小代价路，如果这样的路径不存在，置为空，跳转到4)；

5 算法分析

5.1 算法复杂度分析

对于RSF-awareMLCA子算法，假设pG中有n个节点，则对每个元需求进行权值矩阵更新和最短路算法的最坏时间复杂度都是 O ( n2)；因此RSF-awareCA算法的最坏时间复杂度为 O ( n2)。算法消耗的存储空间主要用于存储最短路径，因此空间复杂度为 O ( n)。

对于RSLFRA子算法，算法第1)步更新权值矩阵的时间复杂度为 O ( n2)；算法第2)步最短路算法的最坏时间复杂度为 O ( n2)；映射的保护路径最多有 n -1条链路，所以第3)步更新路径服务承载能力的最坏时间复杂度为 O ( n)；因此 RSLFRA算法的最坏时间复杂度为 O ( n2)。算法消耗的存储空间主要用于存储最短路径，因此空间复杂度为 O ( n)。

5.2 实验设定

仿真实验在配置 Pentium 4 3.06GHz CPU和1GB内存的普通PC上进行，实验利用BRITE工具在100×100的空间下随机产生由100个节点组成的物理网络拓扑，BRITE参数设置如下：HS=LS=100，N=100，Model=WaxMan，Node Placement=Random，alpha=0.15，beta=0.2，m=2，Growth Type=Incremental，BWdist=Unif，MaxBW=100，MinBW=50。因此，任意2个节点的连接概率是0.5，带宽资源在50到100间均匀分布。RSCN构建请求的到达过程服从时间单位为 100，强度 λr=5的泊松过程，链路故障发生过程服从强度为λf的泊松过程，链路故障恢复时间服从θ=20的指数分布；每个RSCN的生存时间服从θ=400的指数分布。RSCN节点需求个数在5到10之间均匀分布，任意2个虚节点的连接概率为0.5，带宽需求在0到50之间均匀分布。实验过程中α和β均取0.5，节点初始价值设为1，链路初始价值设为连接链路两端点的欧式距离。算法比较BACA[7]、SVNE-Hybrid[12]、不考虑保护机制的RSF-awareMLCA和采用主动保护机制的RAPA在构建成功率、主链路利用率和平均网络链路故障损失3个方面的差异。鉴于MATLAB具有强大的函数库，仿真用MATLAB编写完成，为了使结果更准确，仿真共进行10次，取所有实验结果的平均值。

5.3 RSCN成功运行率

RSCN成功运行率是仿真运行后RSCN构建成功且不受故障影响中断服务的个数占构建请求数的百分比，即

RSCN成功运行率可以反映构建方法的有效性和故障保护能力，成功运行率越高表明构建方法越有效且保护能力越强，图3和图4分别是和这2种情况下构建请求数从0到300时的RSCN成功运行率结果。

图3 λf/λr为0.1的RSCN成功运行率

图4 λf/λr为0.5的RSCN成功运行率

5.4 主链路利用率

主链路平均利用率是构建的RSCN所占主链路带宽之和与物理网络所有链路资源带宽之和的比值，即

在完成RSCN构建后，平均网络链路利用率可以反映RSCN构建的网络资源利用效率，图5是仿真运行时间为10 000单位时间，不同取值情况下的平均链路利用率实验结果。

由实验结果可知， 链路故障率较低时，几种算法的链路利用率相差不大，其中，RAPA利用率最高，RSF-awareMLCA和SVNE-Hybrid次之，BACA利用率最低；随着链路故障率的增大，各算法的链路利用率都呈现下降趋势，其中，BACA最为明显，这是由于算法构建RSCN时没有考虑关键资源，且没有故障保护机制，受链路故障影响较大；RAPA的链路利用率下降最慢，该算法在故障发生时能够切换RSCN故障链路到保护路径，且构建RSCN时充分考虑了资源的紧迫程度；SVNE-Hybrid次之，这是由于该算法的故障保护机制占用了较多的保护链路资源，减少了主路径剩余提供能力。

图5 主链路利用率

5.5 平均网络链路故障损失

平均网络链路故障损失是网络链路故障损失与成功运行的RSCN个数的比值，即

平均网络链路故障损失可以反映RSCN构建和保护机制的经济性，图6是仿真运行时间为10 000单位时间，不同取值情况下的平均网络链路故障损失实验结果。

图6 网络链路故障损失

由实验结果可知，链路故障率较低时，几种算法的网络链路故障损失相差不大，其中，RAPA的平均网络链路故障损失最低，RSF-awareMLCA和SVNE-Hybrid略高，BACA平均网络链路故障损失最高；随着链路故障率的增大，各算法的平均网络链路故障损失都呈现上升趋势，其中BACA最为明显，这是由于BACA构建RSCN时没有考虑关键资源，且没有故障保护机制，受链路故障影响的RSCN数目较多，故障损失最大；RAPA的故障上升最慢，该算法在故障发生时能够切换RSCN故障链路到保护路径，且构建RSCN时充分考虑了资源的紧迫程度；SVNE-Hybrid居中，尽管该算法提供了较多资源进行故障保护，但是其RSCN构建成功率较RAPA较低，因此平均链路故障损失较RAPA略高。

从上述实验数据可知，只有 RAPA在构建RSCN时充分考虑了资源的紧迫程度，并且为RSCN主路径映射了相应的保护路径，且保护链路带宽尽可能小；在故障发生时能够将RSCN故障链路快速切换到保护路径，RSCN成功运行率、主链路利用率和平均网络链路故障损失明显优于其他 3种构建方法。

6 结束语

互联网设计之初的目标使得众多业务仍需通过构建物理专网的形式来运营，也使得目前的互联网体系难以支撑未来三网融合的需求。可重构柔性网络体系架构能够快速、灵活和高效地为用户业务提供多样化的网络服务，推动传统互联网技术向新一代网络体系平滑演进。

鉴于IP骨干网网络故障导致RSCN服务中断，给用户带来不好的用户体验，同时还给服务提供者造成经济损失，本文针对RSCN主动保护问题进行了数学建模和理论分析。为了尽量避免重要资源故障给网络带来的影响，设计了资源紧迫度感知的主路径构建子算法RSF-awareMLCA；为了提高RSCN的运行成功率和网络收益，设计了RSCN保护链路构建子算法RPLCA；结合2个子算法，设计了RSCN主动保护构建算法 RAPA。最后，分析了算法的复杂度，从RSCN成功运行率、主链路利用率和平均网络链路故障损失3个方面验证了本文提出的算法的优越性。

RSCN的生存性还有很多问题有待研究与探索，需进一步研究跨域RSCN域间链路故障的保护机制。

[1] TURNER J, TAYLOR D. Diversifying the Internet[A]. Proceedings ofthe IEEE Conference on Global Telecommunications[C]. St Louis USA, 2005. 755 -760.

[2] 王浩学, 汪斌强, 于婧等. 一体化承载网络体系架构研究[J]. 计算机学报, 2009, 3(32):371-376.WANG H X, WANG B Q, YU J, et al. Research on architecture of universal carrying network [J]. Chinese Journal of Computers, 2009,3(32):371-376.

[3] 齐宁, 汪斌强, 郭佳. 逻辑承载网构建方法的研究[J]．计算机学报，2010, 9(33):1533-1540.QI N, WANG B Q, GUO J. Research on construction methods of logical carrying network[J]. Chinese Journal of Computers,2010,9(33):1533-1540.

[4] IANNACCONE G, CHUAH C, MORTIER R, et al. Analysis of link failures in an IP backbone[A]. Proceedings of ACM SIGCOMM Internet Mensurenient Workshop 2002[C]. Marseille, France, 2002.237-242.

[5] MARKOPULOU A, IANNACCONE G, BHATTACHARYYA S.Characterization of failures in an IP backbone[A]. Proceedings of INFOCOM 2004[C]. Hong Kong, China, 2004. 2307-2317.

[6] MASHARAF N M, RAHMAN M R, BOUTABA R. Virtual network embedding with coordinated node and link mapping[A]. Proceedings of the 28th Conference on Computer Communications, Rio de Janeiro[C]. USA, IEEE, 2009. 783-791.

[7] 齐宁, 王保进, 汪斌强等. 均衡虚拟网构建算法研究[J]. 电子与信息学报, 2011, 33(6): 1301-1306.QI N, WANG Q, WANG B J, et al. Research on balanced construction algorithm of virtual network[J]. Journal of Electronics and Information Technology, 2011, 33(6): 1301-1306.

[8] YU M L, YI Y, REXFORD J, et al. Rethinking virtual network embedding: substrate support for path splitting and migration[A]. Proceedings of ACM SIGCOMM on Computer Communication[C]. Seattle, WA, USA, 2008. 17-29.

[9] CAPONE A, ELIAS J, MARTIGNON F. Routing and resource optimization in service overlay networks [J]. Elsevier Computer Networks,2009, 53(2):180-190.

[10] ZHU Y, AMMAR M. Algorithms for assigning substrate network resources to virtual network components[A]. Proceedings of IEEE INFOCOM[C]. Barcelona, Catalunya, Spain, 2006. 1-12.

[11] NABEEL B, CHOWDHURY N M, BOUTABA R. Topology-awareness and reoptimization mechanism for virtual network embedding[A]. Proceedings of the 9th International Networking Conference[C]. Chennai, India, 2010. 27-39.

[12] RAIHAN M, ISSAM A, BOUTABA R. Survivable virtual network embedding[A]. Proceedings of the 9th International Networking Conference[C]. Chennai, India, 2010. 40-52.

[13] MACIEJ K, PATRICK T. Survivable routing of mesh topologies.in IP-over-WDM networks by recursive graph contraction[J]. IEEE Journal on Selected Areas in Communications, 2007, 25(5): 922-933.

[14] LEE K, MODIANO E. Cross-layer survivability in wdm-based networks[A]. IEEE INFOCOM 2009[C]. Rio de Janeiro, Brazil. 2009.1017-1025.

[15] KRISHNAIYAN T, MUHAMAD S, LARRY X. Circuits/cutsets duality and a unified algorithmic framework for survivable logical topology design in ip-over-wdm optical networks[A]. Proceedings of IEEE INFOCOM 2009[C]. Rio de Janeiro, Brazil. 2009.

[16] KOLLIOPOULOS S, STEIN C. Improved approximation algorithms for unsplittable flow problems[A]. Proceedings of IEEE Symposium on Foundations of Computer Science[C]. 1997.