基于SDN的数据中心网络路由算法研究

赖香武，彭大芹＊，黄德玲，刘艳林

（重庆邮电大学 通信与信息工程学院，重庆 400065）

基于SDN的数据中心网络路由算法研究

赖香武，彭大芹＊，黄德玲，刘艳林

（重庆邮电大学 通信与信息工程学院，重庆 400065）

针对云计算、大数据等互联网应用规模不断扩大，新应用的发展对传统网络提出更高效集中的网络管理需求、高效灵活的组网需求。文章对在软件定义网络架构下的数据中心网络路由方面展开研究，提出基于流分类的软件定义数据中心网络路由算法，使用改进的路由算法，在Fat-Tree架构上建立流量模型并与传统的ECMP算法进行性能分析和对比。结果表明，文章中提出的路由算法能够在提高链路利用率的基础上提高网络吞吐量和降低分组端到端时延。

数据中心；SDN；Fat-Tree；路由算法

随着云计算、大数据等互联网应用的快速发展，数据中心内部的通信量正以指数级的速度增长，新型应用对数据中心网络的带宽需求不断增加[1]。与传统网络相比，软件定义网络（Software Defined Network，SDN）通过集中控制取代了原来的路由协议自协商方式，极大地提升了网络的管控效率和开放程度，能够对整个数据中心网络资源作出全局判断[2]。文献[4]发现，数据中心网络中大部分的数据流量是由小流组成的。近90%的数据流大小不超过1MB，持续时间不超过10秒，而90%的数据流量都集中在大于100 MB的数据流中。文献[5]提出了一种软件定义数据中心网络混合路由机制（Software-Defined Hybrid Routing，SHR）。SHR采取了一种折中的办法，对数据流进行分类，对不同类型的流量采用不同的路由算法。该机制与传统ECMP算法相比，虽然降低了数据流丢弃率，提高了网络吞吐量，但没有考虑链路利用率这方面的性能，给机制带来一定的缺陷性。

考虑到数据中心网络的流量特征以及现有路由方式的优缺点，本文提出一种路由策略，该策略从两方面考虑，针对无法事先知道大小的新流使用改进的ECMP算法进行路由；而针对已经在网络中转发的大流则采用考虑路径整体转发能力的动态路由算法，当计算出来的路由与原有路由不同时对大流进行重路由。

1 基于流分类的路由机制设计（见图1）

图1 路由机制总体设计

图1是该机制的总体设计图。简要描述如下：（1a）对于新到的数据流，由于不知道其大小，故使用改进的ECMP算法，以链路的剩余带宽作为其选择路径的概率；每隔T2周期将交换机中已传输的数据流信息发送给控制器，对流进行分类。（1b）每隔T1周期将链路状态的统计信息发送到控制器。（2）控制器2为新流和需要进行重路由的大流制定路由策略，最后以流表的形式下发到各个交换机中。

2 算法思想及实现流程

式中：Lin是第i条链路第n个统计周期T1内的负载，是该周期内端口发送的字节数，是同周期内端口接收的字节数。

则选择第i条链路的概率为：

式中Bin是第i条链路的最大带宽，l为总链路数。先计算出每条链路的负载Lin，然后计算出每条链路的剩余带宽（Bin-Lin），将某条链路剩余带宽占所有可选路径剩余带宽的比值Pi作为小流分配到该条链路的占比，控制器在第n个周期内收到的新流请求按照第n-1个周期计算出来的占比Pi为分配到相应的传输链路上。

（2）本文设定链路利用率大于75%时为拥塞链路[6]，当检测到链路存在拥塞情况时，对链路中的大流采用路径整体转发能力的动态路由算法进行重路由。具体操作流程如图2所示。

两种路由策略具体算法描述如下：

算法1改进的ECMP算法。

输入：新数据流f；

Fat-tree拓扑全网信息；

链路负载信息Lin；

输出：新数据流的路径Path

（1）获取f的源主机和目的主机和连接二者的边缘交换机。

（2）计算两主机所在的Pod，确定f需要达到的最高层节点。

（3）根据最高层节点计算f的所有等价路径Paths。

（4）根据Lin计算第i条链路的概率。

（5）获取链路i的起点，确定路由的开始节点。

（6）路由到下一跳后继续向上搜索适合的链路。

（7）搜索到最高节点后即可确定到目的主机的路由路径。算法2大流重路由算法。

输入：Fat-Tree拓扑全网信息；

链路统计信息；

拥塞链路L上的大流Flows；

输出：Flows中大流的路径Path

（1）For f in Flowsdo。

（2）计算f的所有等价路径Paths。

（3）计算f当前所占的带宽。

（4）获取拥塞链路L的起点，确定重路由的开始节点。

（5）向上一层搜索最先适应的链路。

（6）若同层中无满足条件的节点则向下层回溯。

（7）到达最高层节点后，若下行路径链路空闲带宽>f当前所占带宽，则返回f的路径；否则返回（6）。

图2 处理流程

3 实验仿真与结果分析

本文在Fat-Tree架构上对提出的软件定义网络架构下基于流分类的路由算法进行仿真实验分析。与传统的ECMP算法进行对比，展示改进的路由算法在网络吞吐量、链路利用率和时延方面的性能优势。

3.1 实验环境搭建

使用Mininet网络仿真器搭建基于四元Fat-Tree拓扑结构的软件定义数据中心网络，选取Floodlight作为仿真实验所需控制器。参考已有对数据中心网络内部流量的研究，本次实验共仿真1万个流，并且将T1和T2均设置为1s来收集链路状态信息和流的统计信息。

3.2 性能分析

图3是在Fat-Tree拓扑上分别采用ECMP和改进算法进行路由的网络吞吐量仿真对比图。仿真结果表明网络吞吐量随着数据流到达速率不断增加而增加，当边缘交换机的流到达速率达到2 500条/秒时，改进算法的网络吞吐量比ECMP算法的网络吞吐量高12.2%。这是由于ECMP在路径分配前并没有检测负载情况，只能提供静态的流量均衡。而本文提出的算法按照可行路径上的负载情况选择最优路径，提高了吞吐量。

图3 网络吞吐量仿真对比

图4的仿真结果表示，随着网络负载的增加，两种路由方式的分组时延也随之增加，ECMP算法的时延明显要高，且随着负载的增加，其时延的增长速度也要高些。图5所示为在不同时刻下，两种不同路由方式的网络中所有链路的平均链路利用率，记录了网络中的平均链路利用率随着时间的变化。从图5中可以看出，本文提出的算法在平均链路利用率上要高于传统的ECMP算法。当链路中的流陆续完成转发时，链路的平均利用率呈下降趋势。

4 结语

本文在软件定义网络架构下提出基于流分类的数据中心网络路由算法，并在Fat-Tree架构上建立流量模型，与传统的ECMP算法进行性能分析和对比，结果表明提出的路由算法能够在提高链路利用率的基础上提高网络吞吐量和降低分组端到端时延。

图4 分组时延仿真对比

图5 链路利用率仿真对比

[1]中国互联网信息中心.第37次中国互联网络发展状态统计报告[R].北京：中国互联网络信息中心，2016.

[2]黄韬，刘江，魏亮，等.软件定义网络核心原理与应用实践[J].通信学报，2015（3）：288.

[3]陈元谋，周丽娜.基于SDN的云计算数据中心网络技术探讨[J].电子世界，2015（18）：147-148.

[4]蔡岳平，王昌平.软件定义数据中心网络混合路由机制[J].通信学报，2016（4）：44-52.

[5]CHU C Y，XI K，LUO M，et al.Congestion-aware single link failure recovery in hybrid SDN networks[C].2015 IEEE Conference Computer Communications，2015：1086-1094.

[6]KANAGEVLU R，AUNG K M M.SDN Controlled Local Re-routing to Reduce Congestion in Cloud Data Center[C].2015 International Conference on Cloud Computing Research and Innovation，2015：80-88.

[7]ZAHAVI E，KESLASSY I，KOLODNY A.Distributed adaptive routing convergence to non-blocking dcn routing assignments[J]. Selected Areas in Communications，2014（1）：88-101.

[8]BHARTI S，PATTANAIK K K.Dynamic Distributed Flow Scheduling with Load Balancing for Data Center Networks [J].Procedia Computer Science，2013（19）：124-130.

[9]SHEN S H，HUANG L H，YANG D N，et al. Reliable multicast routing for software-defined networks[C].2015 IEEE Conference on Computer Communications，2015：181-189.

[10]DUAN J，WANG Z，WU C. Responsive multipath TCP in SDN-based datacenters[C]. IEEE International Conference on Communications，2015.

Research on routing algorithm of data center network based on SDN

Lai Xiangwu, Peng Daqin*, Huang Deling, Liu Yanlin
（Communication and Information Engineering College of Chongqing University of Posts and Telecommunications, Chongqing 400065, China）

With Internet application scale such as cloud computing, big data, expanding unceasingly, the development of new applications for traditional network makes a more efficient centralized network management requirements, highly efficient and flexible network requirements. This paper spread a study in the software-defined data center network routing aspect, putting forward software-defined data center network routing algorithm which based on traffic classification, proposing an improved routing algorithm, building the traffic model on the Fat-Tree architecture and comparing with the traditional ECMP algorithm. The results showed that the proposed routing algorithm can improve network throughput and reduce packet end-to-end delay on the basis of improving link utilization.

data center; SDN; Fat-Tree; routing algorithm

赖香武（1991— ），男，江西吉水，硕士研究生；研究方向：未来网络，SDN。

＊通讯作者：彭大芹（1969— ），男，四川雅安，硕士，正高级工程师；研究方向：LTE，物联网以及车联网标准。