软件定义光网络中的高效路由机制研究

俞慧慧

(安徽电子信息职业技术学院 信息与智能工程系，蚌埠 233000)

光纤的超大容量的特性使得光网络在网络数据传输和转移方面一直以来扮演着重要的角色。然而，由于缺乏灵活的管理和合理的调度分配机制，大部分的光波长资源都处于被浪费的状态[1]。此外，传统的光传输网络极度依赖人工的干预和管理。软件定义网络(Software-Defined Networking, SDN)提出为公共基础设施的管理建立一个抽象且灵活的控制平面，用于对底层设备进行统一管理和配置[2-3]。尽管SDN已经被广泛研究并且已有成果应用于传统IP网络中，对于软件定义光网络(Software-Defined Optical Networking, SDON)的研究目前还比较少。SDON将光网络的快速传输能力与SDN的灵活控制能力相结合，既提高了光传输网络的能力、降低了能耗，也为底层设备的管理提供了灵活且集中的控制机制。这种结合所获得的优势能够在一定程度上打破当前光网络的研究瓶颈，进一步推动对光网络的研究[4]。

在传统的波分复用(Wavelength Division Multiplexed, WDM)网络中, 光纤中的所谓带宽资源通常被分为不同的频率段，它们被称为波长(Wavelength)。通过在网络中重新配置光交换机，我们能够在不同节点终端上选择特定的波长作为光电交换或者光波长路由的媒介。对于一个具有多个节点的网络，理想情况是建立多条光路径。这样可以保证任意一对节点之间的突发流量请求都能得到满足。然而实际的情况并没有那么多的波长资源供我们去使用，这就限制了我们能够建立的光路径数量。传统AON中的波长路由问题已经得到了较好地解决，对此类问题进行了优化，同时提出一系列的启发式算法来求解多路径路由波长选择问题。然而，针对SDON背景下的多径长路由的路由波长选择问题研究较少，因此有必要对其进行深入研究。

将SDN的思想引入到AON中，基于SDN的全局资源视图和控制机制，能够对底层的光设备进行统一的配置和管理，使其具有高度的协同工作能力。同时，数据链路的增加引起端到端的路径延迟，也称为差分时延(Differential Delay, DD)。针对这些问题，在SDON中提出一种差分时延约束多路径路由波长选择算法。该方法不仅可以避免单路径路由限制和可能的路径障碍，同时还可以提高网络吞吐量和利用率。该方法将多路径优化问题，转变为解决非相交路径基数M最大化问题和平均端到端传输延迟最小化问题。采用迭代方法和整数规划，求解M最小值，并根据M值确定最优路由波长。

1 软件定义光网络(SPON)架构

(SDON)寻求利用灵活的SDN控制为底层光网络基础设施提供网络应用能力。图1为SDON架构。这个架构的控制核心是一个抽象概念，通过扩展OpenFlow (OF) 控制器和协议实现。这个机制支持底层异构光传输和数据包集成。这个架构包括3个组件，分别为硬件抽象层，OF扩展层和SDN应用层。硬件抽象层的作用在于隐藏底层异构传输网络资源的细节，同时为硬件状态配置提供编程接口；在OF扩展中，SDON采用多维流表来表示OF使能交换。每个表中包括详细的匹配域、计数器和一系列附属动作。

图1 软件定义光网络架构

2 问题描述及模型引入

SDON中路由波长的选择是指光信号经过网络节点通过一定的波长进行传播。多路径路由是一种网络功能，它控制数据流在多个物理路径之间从源到目的地的分裂。在多路径路由规划算法中，主要的研究重点在于从给定的源节点到目标节点间的路由路径的确定，路由路径集的完备性直接影响请求路由的波长选择。在相同的差分时延束下，找到M个链路不相交的S-T路径集，最小化平均端到端延迟L，我们称之为复合模型。为了简化对复合模型的求解过程，我们将复合模型公式转换成一个由混合整数规划公式(Mixed-Integer Linear Programming， MILP)的子问题进行迭代求解，在复合模型中的单路径路由中强制添加差分时延约束会使得与路由路径相关的路由循环出现，这种循环出现问题会导致路径判断误差。因此，对复合模型进行如下定量描述。

使用无向图G(v,ε)表示的由各节点经过一定的连接方式组成的网络，其中，v和ε分别表示的是各个节点组成的节点集合以及节点之间的无向连接。每个连接链路e∈ε与连接其节点的两个相对定向弧e′和e″相关联。所有这类弧的集合由η表示(注意，由此产生的有向图G(v,Ν)是有向且是双向的)。弧η的源节点和目标节点分别用A(η)和B(η)表示。加权值ωη表示弧η∈Ν的延迟程度参数。弧σ+(v)和σ-(v)集合分别表示从节点v∈V发出的弧的传出方向和指向v的弧的传入方向。对复合模型的求解的关键点是在给定的差分时延以及端到端的平均延迟上界α的条件下，求给定源节点A以及目标节点B之间的多路径路由连接的最优解，并且能够最大化不相交路径M，之后根据确定的最多的不相交路径使得端到端的平均延迟L最小化。

3 基于SDON的差分时延约束多路径路由波长优化

多径路由连接问题实际是有向图G(v,N)从节点A到节点B的M个不相交路径W的一个集合。我们采用4个参数来表达多径路由连接请求，这4个参数分别为A，B，和Δ，M。其中，A和B分别为源节点和目的点，Δ是微分延迟上界，M是假定的不相交路径数。提出的差分时延约束多路径路由波长优化算法共包括3个部分：M值最大化、差分时延约束和路由波长选择。

3.1 M值最大化

M值的最大化，可以充分提高算法解决网络拥塞能力。不相交路径的最大化可以为DD求解提供更大的解析空间，并一定程度提高网络分发速度。我们将多径路由连接累积延迟作为目标函数。在公式(1)中，φη为M中的传输延迟，xηm为流变量，m为路由跳数。φη和xηm的乘积表示累积延迟。在公式(1)的基础上，我们提出6条约束条件，通过约束条件限定目标函数，从而获得M最大值。用xηm的差值表示源节点A到目标节点B的M条路径，如公式(2)所示。通过公式(3)，我们限定了路由路径的不连接属性。引入微分延迟上限，作为M条路径的延迟上限，用公式(4)和公式(5)表示。为了获得最优解，采用非负变量作为最优解下线，如公式(6)所示。其中，hvm表示从源节点A到v的每条路径。公式(7)为hvm的约束条件。综上，我们可以获得M的最大优化值。

minimize∑η∈Ν∑m∈Mωηxηm，

(1)

(2)

∑m∈Mxe'm+xe''m≤1,e∈ε，

(3)

∑η∈Νωηxηm-∑η∈Νωηxμn≤Δ,m,n∈M,m

(4)

∑η∈Νωηxηn-∑η∈Νωηxμm≤Δ,m,n∈M,m

(5)

hb(η)k-ha(η)k≥1-M(1-xηm),η∈Ν,m∈M，

(6)

xηmbinary,hvm≥0.

(7)

3.2 差分延迟约束

差分延迟补偿可以有效缓解和解决SDON中的环路和隔离环问题。为了实现差分延迟补偿，我们假设网络内部允许路由循环的存在。在3.1节的基础上，我们增加2个限制变量和一个约束条件。通过新增加的变量和约束条件，解决路径内循环问题，并实现差分延迟约束功能，从而最小化DD。

设集合Rηvm和rηm分别为人工流约束条件，用来对流变量进行约束。其中，Rηvm表示路径W上的节点v到节点B的人工流值，rηm表示属于路径W的人流值。我们通过加强对xηm约束，去除网络内路由循环问题，这种方式也可以避免孤立循环。流量变量的差分延迟限制公式为：

Rηvm≤xηm≤rvm,η∈Ν,v∈V{A,B},m∈M，

(8)

同时，路径W上的流量守恒公式为：

(9)

通过约束条件，将xηm取值范围限定在正整数范围内，即xηm∈N+。由于引入了新的限制变量，我们需要将3.1节中公式(7)更新为：

xηmbinary,Rηvm·rvm≥0

，

(10)

至此，我们可以通过公式(8)～(10)，并结合3.1节公式(1)～(6)得到最小化的DD。

3.3 多路径路由波长选择

在完成3.1节和3.2节内容之后，我们可以得到差分约束条件下的基数M和最优的DD，根据网络请求优先级排序，进行最优化路由和波长分配。这种分配方式可以对更高延迟请求实现波长配置的优先分配。尽可能满足建立光路的高层次要求，提高光网络资源的利用率，降低高等级请求的拒绝率。影响域内路由选路的主要因素有：(1)下一跳节点的程度；(2)距目标节点的距离；(3)在链路中占用波长的情况下，下一跳链路优先选择波长更大且无波长转换的链路；(4)请求级别越高，路由优先级越高。

4 实验结果与数据分析

4.1 实验条件设置和对比方法

假设SDON中没有使用波长转换器，并且每对邻接节点之间都由两条光纤所连接以构成双向链路。另外，所有的光纤都包含相同的波长数目。采用14个节点的NSFNET拓扑作为仿真对象。并且基于该拓扑，对两种情况进行仿真，分别为每条光纤中波长数为8，如图2(a)所示；和波长数为16，如图2(b)所示。

为了验证文中算法的适应性以及合理性，选取了另外三种算法作为比较的对象，分别为固定路由(Fixed Routing, FR)、固定可选路由(Fixed Alternate Routing, FAR)和自适应路由(Adaptive Routing, AR)。其中，FR是一种比较直接的光网络路由算法，它提前规划好任意源目的节点对之间的路径，一旦有流量请求到达，就会按照预先定义好的路径进行转发。该方法简单，但是缺乏灵活性。FAR以FR为基础，区别在于FR仅仅只为任意的源目的节点对规划一条可用路径，而FAR则会规划多条，一旦发生阻塞或者断路，FAR就会迅速切换到另外一条光通路上以减少损失。AR相对文中的静态LPR而言，其本质属于动态路由。任意的源目的节点对之间的路由都根据网络当前状态而制定。即对于同样的源目的节点对，不同时刻它们之间的路由可能是不一样的。

4.2 对比实验结果及分析

分别使用这4种算法测试了在SDON环境下，随着时间变化网络的阻塞率(Blocking Probability, BP)，BP描述的是网络整体的阻塞率。通常，我们会为每条光链路定一个阈值，超过这个阈值则可以判断其处于拥塞的状态。通过判断整个网络中的所有链路的状态变能够得到全局的网络阻塞率。另外，使用Matlab工具来求解上述定义的LPR问题。

图2对比了文中算法和另外几种算法在解决光网络中的路由问题时所产生的网络拥塞随时间变化的情况。通过观察整体的结果形式可以发现，图2(b)中的结果要明显优于图2(a)，原因很简单，因为图2(b)中的结果是通过仿真每条光纤中具有16条波长所得到的。相反，图2(a)中的结果是基于每条光纤只含有8条波长。图2(b)仿真使用的资源数量是图2(a)的两倍，因此更加利于网络流量的传播，降低阻塞率。此外，我们分别观察图2(a)和图2(b)中的结果，会发现LPR都能够取得很好的效果。这是因为LPR相对来说是一种静态的策略，需要提前知晓流量的情况，并且基于线性规划来进行集中式求解，这个过程相对耗时较长，这是LPR所需要克服的问题。

(a)波长数=8

(b)波长数=16

另外，还对比了各种算法对于波长利用的均衡性分析。也就是在建立光路径的过程中，波长资源的使用是否平衡。这个指标从一定程度上也能够反映出网络中的拥塞情况。比如，一条波长如果使用次数过多，必然会造成其他波长使用率可能不高或者被闲置。在这种情况下，波长的使用不均衡势必在某些特定情况下造成网络中某些部分拥塞。同样还是针对波长数分别为8和16的情况，假设任意的节点对之间都存在着流量，且每条流量对波长资源数量的需求都小于1。在此情况下进行仿真并记录仿真过程中各条波长的使用次数，结果如表1所示。通过观察表1中的数据，我们能够发现：(1)LPR的波长总的使用次数相对要高一些，这说明LPR具有较好的波长利用率；(2)从波长使用次数的分布情况来看，基于LPR的波长负载相对要更均匀，这种优势在波长数较多时表现得尤为明显，如W=16时，各算法得到的波长负载情况就比W=8情况下要明显。(3)波长数越多，其平均使用次数越少。另外，还需要注意的一点是，在W=16时，LPR实际上只使用了其中的14条，这一点也说明了LPR具有较高的波长利用率。

表1 各波长使用次数分析

5 结语

SDON是一种将软件定义技术融入到光通信网络的新型网络，代表了未来光网络的发展方向。拟从SDON中的路由问题出发，研究了SDN架构对于突破传统光网络中的瓶颈问题的价值所在，提出了一种基于SDON的差分时延约束多路径路由波长优化算法。结果表明，在传统光网络中引入SDN机制能够减小网络的阻塞情况，提高网络的整体性能，对于促进SDON的发展有重大意义。