软件定义网络中的可靠多播路由研究

夏子厚

(信阳职业技术学院 数学与计算机科学学院，河南 信阳 464000)

软件定义网络(SDN)是一个确保网络资源的灵活管理，以支持大量数据传输的新型网络结构[1]。软件定义网络中的OpenFlow[2]有两个主要元素构成：控制器和转发机制。与传统的分布式最短路径路由相比，软件定义网络对通信采取一个单播路由的集中计算以提供网络吞吐量[3]。

多播通信能够实现多目的节点的数据传输，但是，多播传输在最小网络资源消耗方面，如果没有可靠传输，网络的传输效率将会受到很大的影响。为了支持多播中的可靠传输，基于源的可靠多播传输[4]首先被提出，以直接从源恢复丢失的包，但是它也面临扩展性问题，因为源节点需要向大量的目的节点提供丢失数据，这就使得源数据可能被淹没[5]。因此，需要设计一个新的算法来同时实现一个多播树的高效路由和多播传输恢复节点的选择。

本文将基于软件定义控制技术提出了一个新的可靠多播树，叫做故障恢复斯坦纳树(RST)。在一组多播中给定源节点和目的节点和网络中相应的恢复节点以及一个非负整数r，故障恢复斯坦纳树旨在找到一个实现以下功能的树：(1)连接源节点和目的节点；(2)至多跨越树中r个作为本地丢包恢复的恢复节点。我们的目标是将树的资源消耗和总恢复资源消耗最小化，树的资源消耗是树中所有支撑数据传输的资源消耗总和[8]。

1 问题构建

为了找到跨越源节点s和目的节点集合D的边界集合，定义在故障恢复斯坦纳树(RST)中至多有r个恢复节点的集合为R。考虑一个直接图G(V,E),其中V和E分别表示节点和边的集合。每条在集合E中的边e(e∈E)被分配给一个资源消耗值c(e):E→R+，其中R+代表正实数的集合。

在故障恢复斯坦纳树中，通过测试不同的r，软件定义控制技术能够协调本地存储的资源消耗和丢包恢复节点的资源消耗w(T)之间的关系。用一个比较大的值r，树中更多的节点将参与到多播数据传输中的丢包恢复短暂存储中，但是，丢包恢复节点的资源消耗将会显著减少。同时，软件定义控制技术能够根据实时的网络状态调整权重α。如果网络负载过重，设置一个较大的值α，反之亦然。另外，R在有效减少恢复节点的资源消耗上也将起着重要作用，R值和恢复节点的资源消耗成正比例关系。可以看出，故障恢复斯坦纳树问题同时考虑了树的路由和恢复节点的选择，可以认为故障恢复斯坦纳树比传统斯坦纳树更难。

2 算法设计及分析

本节中，我们将提出一个新的的k阶近似算法，称为故障恢复边界减少(RAEARA)算法，RAEARA算法能够找到多播树的路由路径并选择合适的恢复节点，从而达到故障恢复斯坦纳树的资源消耗和恢复节点的资源消耗总和最小化。

RAEARA算法包含两个阶段：(1)故障恢复斯坦纳树路由阶段，(2)恢复节点选择阶段。第一阶段从根节点s的最短路径树开始，通过迭代生成最短路径树以减少树的资源消耗。更具体一点，M表示从根节点s到树中目的节点集合D中所有节点最短路径的资源消耗。计算故障恢复斯坦纳树中所有节点到一个目的节点d的最短路径，然后，选择一个最大的重复路由路径来减少构建树的资源消耗。另外，重复路由路径能够确保从根节点s到另一个目的节点的端对端链接。重复路由路径需要包含至少一个相关的故障恢复节点，以实现本地丢包恢复。同时，为了避免生成一条路径比原有的最短路径树深度更深，在一个新树中，从根节点s到目的节点d的端对端路径资源消耗不能超过M。重复上述路由过程到树的资源消耗不能被进一步地减少。

恢复选择阶段是在故障恢复斯坦纳树中选择恢复节点，从而达到恢复资源消耗的最小化。对于任何一个节点v∈VT，VT表示根在v的T的子树。Rv为在Tv上的恢复子集，Tv关于Rv的恢复资源消耗表示为w(Tv,Rv)。RAEARA算法为两种情况选择最优恢复节点集合：v在Rv中被选中。如果v没有在Rv中被选中，RAEARA算法将随后分配一些在T中的先辈节点作为恢复父节点。如果在Tv中的恢复节点满足v∉R，我们称为情况Ⅰ，反之，如果v∈R，我们称为情况Ⅱ。对于给定的Rv，如果Rv中没有其它的恢复节点在Tv的v到u路径上，则在集合DYRv中的节点u(u≠v)能够被任意节点v控制。对于一个满足x≤r的非负整数和一个满足k≤|D|的正整数，σxmk(Tv)表示在情况I下所有在Tv上满足|Rv|≤x的Rv(v不在Rv上)。因此，v完全的控制树T上在集合D∪Rv中的节点k。相应地，τx(Tv)表示所有情况Ⅱ下满足|Rv|≤x的恢复集合Rv在树Tv上的最小恢复资源消耗。

算法：故障恢复边界减少算法(RAEARA)

输入：网络的实时状态信息

输出：最小资源消耗的最优路径

开始

/*步骤1：故障恢复斯坦纳树路由阶段*/

发送传输数据流请求给软件定义网络控制器;

for i=1 to n

找到min w(T)并把具有min w(T)的链路作为最优路径；

/*步骤2: 恢复节点选择阶段*/

If v∈Rvthen

选择当前节点为故障恢复节点；

else

寻找当前树的子节点为故障恢复节点；

软件定义控制器发送配置信号给相应的网络设备。

结束

3 性能评估

我们将在本节中对RAEARA算法进行仿真分析，通过和其它路由策略进行比较，证明RAEARA路由算法的效率。

3.1 仿真设置

在一个OpenFlow的以太网络仿真器[6]中，设定有29个节点和33条链路的真实软件定义网络。然后，通过EstiNet网生成了一个有上千节点和链路的集成网络，并和软件定义网络网络相连接。源节点、目的节点和相关的恢复节点从每个网络中随机选择。

把RAEARA算法与以下三个算法进行比较：(1)最短路径树算法(SPT)(2)斯坦纳树算法(ST)[7](3)CPLEX[8]。在SPT算法和ST算法中，恢复节点的选择是随机的。并改变网络规模|V|、目的节点数量k、和恢复节点个数r。

图1树路由资源消耗图2节点恢复资源消耗

3.2 仿真结果

通过不同的目的节点个数k对RAEARA算法、SPT算法、ST算法和CPLEX算法进行性能比较，其中恢复节点的个数r选为2，在这些小网络中，每个节点都是一个候选恢复节点。图1所示，RAEARA算法生成解的资源消耗非常接近于最优解。SPT算法的资源消耗比其他算法更高。即使ST算法跟SPT算法相比有更小的构建树资源消耗，但是其目的节点和源节点之间的路径更长，这是因为为了跟其他路径相交，目的节点和源节点之间的路径需要与最短的路径相隔离。图2中，如果恢复节点选择不恰当，ST算法可能产生更高的恢复资源消耗。图3证明RAEARA算法的重传资源消耗依然最接近于最优情况。如图4所示，通过对每个目的节点的观测，计算每个数据包在网络中的平均延迟。因为恢复节点更靠近目的节点，树的深度(比如树的最长路径资源消耗)受M限制，因此，RAEARA算法比SPT算法和ST算法提供了更短的传输延迟，而且仿真延迟接近于接近于最优解。

图3平均重传数据包(Mbps)图4平均延迟

4 小结

单播数据传输是软件定义网络主要的通信方式。但是，多播数据传输可以显着地减少网络资源的消耗。由于许多应用程序(例如YouTube)需要可靠的数据传输，因此，在软件定义网络中的可靠多播服务显得尤为重要。本文中，我们首先提出了软件定义网络中的故障恢复斯坦纳树(RST)，它将构建树和数据恢复的资源消耗拟合最小化。另外，我们也提出了故障恢复边界减少算法(RAEARA)。仿真结果证明，RAEARA算法能够提供更低的的总资源消耗，并减少数据包的重传概率，并有效降低数据传输延迟。