ABSTRACT

In the IP over WDM networks, wavelength circuits typically have backup circuits which are often idle. This situation causes a lot of waste of resources. The growing bandwidth demand puts large pressure on the transmission network, so it is necessary to increase the utilization of idle backup circuits. In this paper, we propose a survivable network design with capacity sharing between IP and wavelength service. An efficient heuristic approach is presented. This approach allocates the idle backup wavelength circuit to the IP network while ensuring the survivability of the IP network. We observe that sharing idle backup circuits with IP traffic enables higher resource utilization. The approach ensures its survivability while reducing network cost.

Keywords:Wavelength Circuits, IP over WDM, Resource Optimization, Survivable Network

一种IP与波长业务共享容量的可生存网络设计

蒋烨¹，黄汉华¹，唐元¹，邵泽²

¹广西电网公司电力调度控制中心，广西 南宁

²北京邮电大学网络与交换技术国家重点实验室，北京

收稿日期：2017年3月11日；录用日期：2017年3月26日；发布日期：2017年3月29日

摘 要

在承载于WDM的IP网中，波长电路通常具备备用电路，在多数时间内该备用电路处于空闲状态，造成了资源浪费。日益增长的带宽需求对传输网造成了巨大的压力，增大空闲备用电路的利用率十分必要。本文提出了一种IP网络与波长业务共享容量的可生存网络设计，通过使用一种高效的启发式算法，在保证IP网络可生存性的状况下，将波长电路的空闲备用电路合理分配给IP网络。实验结果表明，通过波长电路与IP网络共享空闲备用电路，能够实现更高的资源利用率，在保证其生存性的同时降低网络成本。

关键词 :波长电路，IP over WDM，资源优化，可生存网络

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 背景介绍

随着网络的发展，各种服务层被引入，未来的光纤骨干网中预计普遍存在两种服务，分别是是IP服务和波长服务，其中IP服务在运营商网络中成功建立起来，波长服务占当今载波业务的一小部分，但预计将随着一些应用(如电子科学)的出现而增长。当前传送IP业务最主流的技术包括IP over ATM, IP over SDH和IP over WDM三种。相比其他两种技术，IP over WDM充分利用了WDM拥有的巨大带宽和路由交换机强大的交换能力，通过优化IP层和光层的结构，对流量工程、QoS和保护恢复功能进行配置，最终简化了网络管理，使层次结构合理而高效 [1] 。IP层通过恒定比特率(CBR)电路仿真或者基于分组的虚拟专用线路(例如，以太网专用线路)承载具有等于或低于10 Gbps速率的不同粒度的专线服务，而40 Gbps乃至100 Gbps的专线业务作为波长业务承载在光层之上。近年来光网络朝着高速率、大带宽的方向迅猛发展，设备数目快速增加导致网络能耗急剧增长 [2] [3] ，用户对带宽需求与日俱增，特别是诸如视频流技术、宽带无线接入技术，以及三网融合等的飞速发展，使得有线和无线的接入带宽不断增长，导致运营商的骨干网络的业务流量持续增长，长途骨干网正在承受着流量爆炸式增长带来的巨大压力 [4] [5] 。

保证网络可生存性也是当下网络设计必须考虑的因素。网络的生存性又可称为网络的抗毁性，指的是在网络发生故障的时候，网络能保证业务正常运行的能力，最佳的网络生存性技术便是在保证业务能够正常运行的前提下，最小化网络的维护运营成本 [6] [7] 。

因此，在提高网络资源利用率的前提下，开发有效的机制以确保在多种粒度、敏捷性、恢复要求和保护等级等因素下的可生存IP和波长服务稳定运行是非常重要的。

若选择将波长电路的空闲备用电路共享给IP业务需要考虑到以下问题：在备用电路故障的情况下，备用电路上的IP流量将被抢占；而当主电路故障时，需要使用其备用电路以恢复波长业务，此时IP业务也将被抢占。要通过备用路径重新路由被抢占的IP流量，IP拓扑必须始终保持连接 [8] [9] ，因此，只有那些在故障情况下不断开IP拓扑的备用电路可以被共享。

本文的目标是设计可生存的IP拓扑结构，有效地重复使用空闲波长备份容量，提出一种启发式算法，选择并共享能够保持IP拓扑的生存性的备用电路。本文首先简要介绍了相关的背景知识，接着提出一种快速且有效的启发式算法以选择合理的波长备用电路，然后通过一个网络的示例验证算法效率，最后总结全文。

2. IP和波长业务共享容量的启发式算法

2.1. 问题约束

本算法默认已经预先设置了波长服务请求，即网络中已经为波长服务请求分配了主电路以及其备用电路。一旦IP服务发出请求则该请求必须被响应，并且在响应IP请求时，允许重新使用一些空闲备用电路，但是必须确保IP拓扑保持连接以应对所有单个物理链路故障。正式的问题说明如下：给定网络拓扑，背景波长业务，每个链路上的可用波长和IP层需求，我们需要为IP请求分配光路，使得总成本(根据所使用的波长信道的总数来测量)最小化。所需约束如下：

· 对于每个IP层需求，可以使用现有的空闲备用电路或者建立新的光路。

· 每个链路上的光路数必须小于或等于其支持的波长通道数。

· 对于所有单个物理链路故障，IP拓扑必须始终保持连接

2.2. 涉及算法的重要概念

首先介绍涉及到本算法的一些重要概念，图1中的IP拓扑需要图2中7个节点的物理拓扑支持，IP拓扑中每条边代表IP请求，该请求需要在物理拓扑的光路中传输。如图2所示，此时物理拓扑中有三个波长服务请求，分别为(1-2)、(1-6)和(6-5)，图2中分别用P₁、P₂和P₃表示，其备用电路分别用B₁、B₂和B₃。由图1和图2可知，图1的IP拓扑中IP请求(1-5)和(1-2)可以直接使用用于传递波长服务请求(1-2)、(1-6)和(6-5)的备用电路的，而不用去建立新的光路。

图1. 简单IP拓扑

图2. 简单物理拓扑

例如，波长服务请求(1-2)的备用电路可用于支持IP请求(1-2)，波长服务请求(1-6)和(6-5)的备用电路可联合用于支持IP请求(1-5)。图3和图4是两种不同的解决方案。在图3中，所有的备用电路都用于支持IP请求，这样做可以避免额外新建光路，最大程度的节约了资源，然而一旦链路(1-6)因出现故障而断开，那么备用电路B₁和B₂将变得不可用，B₂之所以对IP请求不可用是因为其主电路P₂因断开而不可用，因此P₂上的波长服务请求将抢占备用电路B₂。由此可知备用电路不可用的情况有两种，一种是备用电路所在的链路断开(如上述情况的B₂)，另一种是备用电路所支持的主电路所在的链路断开(如上述情况的B₂)，因而上述情况中(1-2)和(1-5)的传输电路皆变得不可用，导致IP拓扑断开连接。因此图3中的解决方案并未提供一个可生存性的IP映射。而图4中的解决方案使用了备用电路B₂和B₃而未使用B₁，该方案是可生存的。由此可知，对于备用电路的合理选择可以保证IP拓扑的可生存性。

接下来介绍冲突指数(index of conflict, IC)的概念，该指数可帮助下文介绍的启发式算法为IP请求选择适合的波长服务请求的备用电路。

冲突指数(index of conflict, IC)：对每个备用电路(B_i)计算冲突指数。该值表示一旦本备用电路出现故障会导致最多几条其他备用电路被抢占，可通过观察该备用电路与几条其他主电路相交而得出。若IC值高于预先所定的阈值，该备用电路将不可用于承载IP请求，若IC值小于阈值，则可将该备用电路添加入候选电路。

2.3. 可生存容量共享算法

可生存容量共享算法：在本算法中，IP拓扑被划分为多个独立的子图，并且每个子图以可生存的方式映射在物理拓扑上。可生存容量共享算法如下：

图3. 不具有生存性的IP-WDM共享路由选择

图4. 具有生存性的IP-WDM共享路由选择

1. 选择嵌入在IP拓扑中的k连接子图。子图中的每个边是IP请求。这些IP请求具有单位波长容量。k连通意味着子图中任一节点连接到其他k个节点。若无法找到这样的子图，则返回映射不具有可生存性。此处选择尽量选择k值小的子图。

2. 对于子图中的每个IP请求，检查是否存在用于支持其业务的空闲备用波长电路。如果存在这样的备用电路，计算其冲突指数(IC)，并检查IC值是否小于k − 1。若IC值大于或等于k − 1，则子图可能成为断开的单链路故障，导致IP拓扑某些业务中断；若IC值小于k − 1，则接受备用电路作为支持IP请求的候选光路径。对子图中的所有IP请求重复此过程。

3. 以链路不相交的方式为所选子图中的每个IP请求分配光路。对于子图中的每个IP请求，检查备用电路是否存在于候选光路径集合中。如果存在备用电路，则尝试以链路不相交的方式设置该备用电路，使得新的光路与已完成分配的IP请求子图的所有光路是链路不相交的，否则，以链路不相交的方式为IP请求建立新的光路径，注意此处的链路不相交仅代表当前子图内分配的光路。我们对子图中的所有IP请求重复此过程。如果整个子图的光路分配不成功，则返回到步骤1并选择不同的子图。

4. 如果分配成功，将该子图合并为IP拓扑中的单个节点，并转到步骤1。成功分配意味着子图已经以可生存的方式映射到物理拓扑上，并且在单链路故障事件中仍能保持连接。子图的收缩确保映射的子图与IP拓扑的剩余部分之间的连接也是可生存的。当收缩子图时，子图中所有边的端点被合并成一个单点。将新边添加到IP拓扑以下情况的边中：未出现在子图，同时在子图中边的端点之间或者在子图中边的端点与IP拓扑剩余部分之间的边，子图收缩可能使得新的IP拓扑中产生自循环和多重边。

5. 最后，经过若干次收缩，若IP拓扑仅由一个点组成，则映射成功，否则映射不成功。

2.4. 应用实例

在实例的实现中，将在可生存容量共享算法的第一步中选择k = 2的连接子图。本文将用下面的例子来讨论可生存的容量共享算法。如图5展示了一个IP拓扑示例，该样例需要得到图6中所示的带有背景波长流量(背景波长流量指的是已经在网络中分配了电路的波长服务请求)的物理拓扑的支持。该IP拓扑的每个边缘都是一个单位波长容量IP请求。可以注意到，图5中的一些IP请求可以被图6中的备用电路所支持，这些请求是(1-14)、(5-8)和(2-6)，其中(1-14)和(2-6)的备用电路B1和B2都没有与任何主电路链路相交，因此它们的IC值皆为0，备用电路B3其中一段链路与主电路P1相交，其IC值为1，等于阈值(k − 1 = 1)，所以不能够支持IP业务。在启发式算法第一次运行期间，我们选择图5中的三个节点组成的子图(1-5-8)。该子图的映射如图7所示。在该子图中针对所有IP需求建立新的光路，并且所有这些光路是链路不相交的。新建的光路分别是为IP请求(1-5)所建立的IP₁，为IP请求(5-8)所建立的IP₂和

图5. 一种简单的IP拓扑

为IP请求(1-8)所建立的IP₃。注意，不能利用备用电路B3来支持IP请求(5-8)，因为它的IC值大于阈值。

在第一次运行之后，节点5和8被合并到节点1中，如图8所示。

在启发式算法第二次运行期间，选择具有IP请求(8-14)和(1-14)的多重边子图(1-14)(即图8中加粗部分)，其映射如图9所示。为IP需求(8-14)建立新的光路IP₄，并且现有波长备用电路B₁用于IP需求(1-14)。第二次运行后收缩的IP拓扑如图10所示。可发现节点1处有一新的自循环。

在启发式算法的第三次运行期间，映射自循环。下文将不再演示第三次以及第四次运行时光路的映射。

第三次运行后的收缩的IP拓扑将去掉自循环边5，当前剩下一个子图(1-2-6)。第四次运行后，IP拓扑收缩到单点，映射成功。在可生存容量共享算法每次运行期间，循环映射以及所得到的收缩后的IP拓扑都是可生存的。

图6. 具有背景波长流量的物理拓扑

图7. 第一次执行算法后得到的光路映射

图8. 第二次算法执行前的IP拓扑

3. 实验结果分析及讨论

本章节考虑一组8个节点车轮网络，即存在从k等于3到7的四个不同k连接网络(k连接意味着IP拓扑中的每个节点都连接到k个其他节点)，拓扑图因形似车轮所以称作车轮网络。随着车轮网络的连接数增加，IP请求的数量增加，需要满足这些请求所需的资源量。本文对背景波长流量占IP流量50%情况进行了实验。50%的背景业务意味着多达50%的IP业务可以由在物理层中路由的现有备用波长电路支持。在每个方法中使用的波长信道的确切数目在表1中给出，第一种方案不允许为IP业务分配备份波长容量，它直接为每个IP请求建立新的光路径，在这种方案中，IP和波长服务之间的容量划分是固定的。第二种方案就是本文所提出的启发式算法构建可生存性拓扑，他与第一种方案的区别在于是否使用波长业务的空闲波长信道来传输IP服务，前者不使用，若发现两点间无光路连接则新建光路，后者根据本文提出算法合理的选择空闲波长备用电路并使用。通过观察表1可知，在k等于3、4、5和7时(即在k连接数为3、4、5和7的车轮网络中)，不共享空闲电路的方案需要新建大量的新光路，造成了资源的浪费，而本文使用启发式算法且使用了空闲备用电路共享的方案大约能节约30%~40%的光路资源。通过该仿真实验，可以观察到启发式方法执行得很好，并且在计算上开销更低。

图9. 第二次算法执行后的光路映射

图10. 第三次算法执行前的IP拓扑

表1. 两种方案所用波长信道数目

4. 结论

本文提出并研究了用于可生存IP拓扑设计的高效启发式算法的特性，总体的思路是通过在电信主干网中使用的IP-over-WDM网络中重新使用备用波长电路。本方法实现了在IP层和光层的请求之间的动态资源共享，同时确保在光纤骨干网络中的IP和波长服务的100%可生存性。研究结果表明，通过重新使用波长服务的备份容量，我们可以在网络中为IP服务节省大量的使用容量，同时不会影响IP和波长服务的可生存性。该研究可以使运营商通过同时支持IP和波长业务来设计具有成本效益的网络。未来将考虑IP和波长服务的进一步集成。

文章引用

蒋 烨,黄汉华,唐 元,邵 泽. 一种IP与波长业务共享容量的可生存网络设计
A Survivable Network Design with Capacity Sharing between IP Service and Wavelength Service[J]. 计算机科学与应用, 2017, 07(03): 240-247. http://dx.doi.org/10.12677/CSA.2017.73030

参考文献 (References)