基于SDN的云数据App-RS路由算法

文杰斌，廖海洲

(湖南邮电职业技术学院， 长沙 410015)

基于SDN的云数据App-RS路由算法

文杰斌，廖海洲

(湖南邮电职业技术学院， 长沙 410015)

当前,随着云数据服务应用的普及,因不同类型的云业务应用的网络需求不同，故不能平等地对待所有类型的云业务应用。为此，提出了一种App-RS(application-aware routing scheme)路由算法。对于calss 1业务应用，该算法考虑端对端的时延及链路负载；对于calss 2业务应用，考虑延迟偏差及链路负载；对于其他业务应用，只考虑链路负载。仿真结果表明：APP-RS路由算法比CORouting路由算法在3类业务应用中的平均吞吐量分别高出9.86%、4.53%和4.07%，相比CORouting路由算法中的calss 1业务应用平均点对点延迟少25.47%，相比CORouting路由算法中的class 2业务应用平均时延偏差少49.65%。因此，APP-RS路由算法比CORouting路由算法更能满足SDN云数据中心所有class业务应用对网络的需求。

SDN；云数据；App-RS；路由算法

在云数据应用中，因不同类型的业务应用对网络资源的要求不同，所以对不同类型的业务应用进行平等对待并不合适。现已提出的在云数据中心业务应用的感知资源(如CPU、GPU、内存、磁盘I/O)管理方法用于预测应用资源需求及尽力满足这些业务应用需求,但是这些方法没有考虑网络应用需求。

应用感知路由是一种很多前途的网络资源云数据中心方案，可满足不同类型业务应用的网络需求。针对不同网络需求可分配切实可行的路由来满足不同业务应用。例如：流媒体视讯业务应用较Web业务应用就需要更多的带宽；VoIP业务应用相对P2P文件共享业务应用则需要较低的网络时迟。然而，通过传统的网络结构来实现这些目标并不容易，但在SDN网络中让网管通过外部控制器来管理自身网络变得很有前途，即通过SDN基于网络应用需求来实现应用感知路由成为可能。

1 SDN网络中OpenFlow结构

在SDN网络结构中，因控制面和数据面独立，所以网络控制变得直接可程序化。另外，SDN网络中需通过控制面协议来保证数据面通信。当前较高级的协议是OpenFlow，图1为OpenFlow结构。图1中：OpenFlow交换机及控制器通过SSL(secure sockets layer)通信，当OpenFlow交换机接收一个在流表中不匹配的封包时，它会通过安全信道转发此封包到控制器，然后由控制器决定怎么处理此封包并修改OpenFlow交换机中的流表。通过此方式，能以当前网络信息(如链路负载、时延及时延偏差)来直接控制OpenFlow控制器以确定其路由。

2 App-RS算法

App-RS算法是一种基于SDN云数据中心业务应用的感知路由算法。该算法考虑所有class类业务应用并把这些应用根据它们对网络的需求分成3种主要类型。每种类型业务应用通过考虑不同参数(如链路负载、时延或时延偏差)用不同的路由方案来进行处理。

2.1 业务应用分类

在App-RS算法中，把所需传输的业务应用数据根据各自所容忍的时迟、时延偏差及包丢失率分为3类，业务应用分类及对传输的要求如表1所示。

表1 业务应用分类

2.2 App-RS路由方案

在App-RS路由方案中,对于不同类型的业务应用使用不同的路由算法。对于class 1类业务应用，需找到一条低时延路径，同时要通过路径负载平衡实现低丢包率，只要时延不超过一定值，给用户的感觉效果如同实时应用。对于class 2类业务应用，需找到一条低时延偏差路径，同时也要通过路径负载平衡实现低丢包率，只要时延偏差不超过某值，流类业务应用能被大家接受。对于class 3类业务应用，只需找到一条最小拥挤路径以确保低丢包率。

对于class 1和class 2业务应用，目标是找到一条最小链路负载及满足时延上限的剩余路径。其解决思路与已通过使用LARAC(拉格朗日松弛)算法解决的时延约束下的最小代价路径问题类似。LARAC算法流程如下：

procedure LARAC(G,s,t,c,d,Dmax)

rC← Dijkstra(G,s,t,c)

if fD(rC) ≦ Dmaxthen return rC

else rD← Dijkstra(G,s,t,d)

if fD(rD) > Dmaxthen return“no feasible solution”

else

while true do

r ← Dijkstra(G,s,t,Cλ)

if fλ(r)= fλ(rC)then return rD

else if fD(r)≦ Dmaxthen rD←r

else rC← r

end if

end while

end if

end if

end procedure

本文采用LARAC算法来为class 1和class 2业务应用找到合适的路径，表2为LARAC路由算法所用的符号定义。

表2 LARAC路由算法所用的符号定义

App-RS路由算法流程如图2所示。服务器通过检查某业务应用的App-ID确定其业务应用所属的class。获取网络最新信息并针对不同业务应用使用不同路由算法。例如：对于class 1业务应用(即实时业务应用)，使用LARAC(G,s,t,c,d,Dmax)算法来找到一条d是时延代价矩阵中的系数且Dmax是点对点时延上限值的路径；对于class 2业务应用(即视频流业务应用)，也是使用LARAC(G,s,t,c,d,Dmax)算法来找到一条d是时延偏差代价矩阵中的系数且Dmax是点对点时延偏差上限值的路径；对于class 3业务应用(即其他业务应用)，则使用Dijkstra(G,s,t,c)算法来找到一条最小拥挤路径。在以上3类业务应用中，c都是其链路负载矩阵系数。一旦确定了应用业务路径，则对应的流记录就会被沿着这条路径添加到每个交换机。

图2 App-RS算法流程

2.3 App-RS算法应用举例

以图3的App-RS路由算法中class 1业务应用举例,而对于class 2业务应用则与此类似，只是将class 1中的时延约束条件改为时延偏差。而对于class 3业务应用，则采用著名的Dijkstra’s算法。因此，以下仅以class 1业务应用举例介绍。

图3 App-RS算法举例

图3中关键是找到从节点1到节点6不超过时延上限1.4的最小负载路径。在表3中，随着λ的增加，时延fD(r)在fC(r)+λfD(r)合计代价中的权重将提高。当λ=0时，最小链路负载是1—2—4—6，但是其时延大于1.4，不满足要求。而路径1—3—2—5—6和1—3—5—6虽然都满足时延约束条件，但是1—3—2—5—6路径具有更小的链路负载fC(r)，所以LARAC路由算法将选择1—3—2—5—6作为节点1到节点6的数据路径。

LARAC路由算法的目标是找到一个最好λ值，对应此λ值的链路具有最小负载，且满足时延偏差条件。

表3 拉格朗日乘子分析表

3 算法仿真比较

3.1 仿真条件及仿真建立

选择SDN模拟器EstiNet，使用Floodlight作为SDN OpenFlow主流控制器。具体仿真参数设置如表4所示。

表4 仿真条件设置

为比较App-RS算法、CORouting算法及Floodlight OpenFlow算法的性能差异，选择1个4层级胖树拓扑结构网络，如图4所示。实验中取平均带宽率、平均包丢失率、平均点到点时延及平均时延偏差作为性能指标。

图4 胖树网络拓扑结构(k=4)

仿真时某些链路倾向于拥塞，且整个流量的80%从胖树的单一层级出发。表5为由许多使用者日常行为统计到的不同class业务应用负载所占比率情况。

表5 不同class业务应用负载所占比率情况

3.2 仿真结果

图5～7为class 1业务应用分别采用Floodlight、CORouting、App-RS三种不同路由算法时的平均带宽率、平均包丢失率、平均点到点时延仿真比较情况。

图5 class 1类业务应用平均带宽率仿真比较

图6 class 1类业务应用平均包丢失率仿真比较

图7 class 1类业务应用平均点到点时延仿真比较

由于CORouting算法和Floodlight算法总是为class 1类业务应用选择跳跃点数最少的路径，所以两类控制器将指示所有class 1类业务应用流向相同路径。因此，当网络中存在太多的class 1类业务应用流经过同一路径时，两种算法都可能导致网络的拥塞。而App-RS算法既考虑了链路负载，又考虑到了端到端的时延，所以其对于class 1类业务应用的平均带宽率、平均包丢失率、平均端到端时延要分别比CORouting算法高9.86%、9.76%、25.47%。

图8～10为class 2类业务应用分别采用Floodlight、CORouting、App-RS三种不同路由算法时的平均带宽率、平均包丢失率、平均时延偏差仿真比较情况。虽然App-RS和CORouting两种算法都考虑了链路负载，但是App-RS算法比CORouting算法多考虑了时延偏差，所以App-RS算法对class 2类业务应用的时延偏差要比 CORouting算法的低。因class 1类业务应用导致的拥塞可能会影响到class 2类业务应用的平均带宽率、平均包丢失率，所以对class 2类业务应用采用App-RS算法时的平均带宽率、包丢失率及时延偏差要比采用CORouting算法时相应提升4.53%、4.1%及4.95%。

图8 class2类业务应用平均带宽率仿真比较

图9 class 2类业务应用平均包丢失率仿真比较

图10 class 2类业务应用平均时延偏差仿真比较

图11～12为class 3类业务应用分别采用Floodlight、CORouting、App-RS三种不同路由算法时的平均带宽率、平均包丢失率仿真比较情况。尽管App-RS和CORouting两种算法都只考虑了链路负载，但因class 1类业务应用导致的拥塞也可能影响到class 3类业务应用时的平均带宽率、平均包丢失率，所以对class 3类业务应用采用App-RS算法时的平均带宽率、平均包丢失率要比采用CORouting算法时提升4.07%、3.97%。

图11 class 3类业务应用平均带宽率仿真比较

图12 class 3类业务应用平均包丢失率仿真比较

4 结束语

本文提出了基于SDN云数据服务的应用感知路由算法(App-RS)。该算法根据各自业务应用特性及网络需求把应用分成3类，每类业务应用通过不同路由算法进行处理，这些路由算法考虑到了不同的参数以满足其网络需求。仿真结果显示：在class 1、class 2、class 3三类业务应用中使用App-RSS算法时，其对应的平均带宽率要比使用CORouting算法分别高出9.86%、4.53%及4.07%；在class l业务应用中使用App-RSS算法时的平均端到端时延要比使用CORouting算法时低25.47%；在class 2业务应用中使用App-RSS算法时的平均时延偏差要比使用CORouting算法时低49.65%。

[1] 黄韬,刘江,魏亮.软件定义网络核心原理与应用实践[J].通信学报,2015(3):12-15.

[2] 左青云,陈鸣,赵广松.基于OpenFlow的SDN技术研究[J].软件学报,2013(5):1079-1097.

[3] 吴宇文.软件定义网络控制平面可扩展性研究进展[J].软件学报,2017(7)：1-16.

[4] 侯长逸.OpenFlow网络软件路由研究[J].兰州大学学报(自然科学版),2013(2):260-263.

[5] 刘中金,李勇,苏厉.TCAM存储高效的OpenFlow多级流表映射机制[J].清华大学学报(自然科学版),2014(4):437-442.

[6] 李龙,付斌章,陈明宇.Nimble:一种适用于OpenFlow网络的快速流调度策略[J].计算机学报,2015(5):1056-1068.

[7] 杨思锦,庄雷,胡颖.一种动态自调节的SDN控制器负载均衡算法[J].计算机应用与软件,2016(12):71-74.

[8] 贾濡,郜帅,罗洪斌.智慧协同网络中基于流量矩阵的负载均衡路由机制[J].通信学报,2016(4):128-138.

[9] 周环,刘慧.基于Floodlight的SDN控制器研究[J].计算机工程与应用,2016(24):137-147.

[10] 蔡岳平,王昌平.软件定义数据中心网络混合路由机制[J].通信学报,2016(4):44-52.

(责任编辑刘 舸)

CloudDataApp-RSRoutingAlgorithmBasedonSDN

WEN Jiebin, LIAO Haizhou

(Hunan Post And Telecommunication College, Changsha 410015, China)

At present, the application of cloud data services is popular. Because of different network requirements of different types of cloud applications, all types of cloud applications cannot be treated equally. It proposes a App-RS(application-aware routing scheme)routing algorithm. For calss1 business applications, the algorithm considers end-to-end delay and link load, and for calss2 business applications, considering delay bias and link load for other business applications, and only consider the link load. The simulation results show that the average throughput of App-RS routing algorithm is 9.86%, 4.53% and 4.07% higher than CORouting routing algorithm in three kinds of business applications, and the average delay is less 25.47% than CORouting routing algorithm, and the average delay deviation is 49.65% compared with the class 2 services in CORouting routing algorithm. Therefore, the App-RS routing algorithm can meet the requirements of all the class service application of SDN more than CORouting routing algorithm.

SDN; cloud data; App-RS; routing algorithm

2017-08-18

湖南省教育厅科学研究项目“基于SDN的集客专线业务传送承载解决方案研究”(15C1018)

文杰斌(1982—)，男，湖南桃江人，硕士，讲师，主要从事通讯技术研究，E-mail:32383101@qq.com ; 廖海洲(1965—)，男，湖南桃源人，副教授，主要从事通讯技术研究。

文杰斌，廖海洲.基于SDN的云数据App-RS路由算法[J].重庆理工大学学报(自然科学)，2017(11):172-178.

formatWEN Jiebin, LIAO Haizhou.Cloud Data App-RS Routing Algorithm Based on SDN[J].Journal of Chongqing University of Technology(Natural Science)，2017(11):172-178.

10.3969/j.issn.1674-8425(z).2017.11.026

TP393

A

1674-8425(2017)11-0172-07