基于SDN的数据中心动态优先级多路径调度算法

肖军弼，程 鹏，谭立状，孟祥泽

(1.中国石油大学(华东)计算机科学与技术学院，山东 青岛 266580；2.北京交通大学下一代互联网互联设备国家工程实验室，北京 100044)

0 引 言

云计算的发展使得越来越多的服务选择部署在大型的数据中心，而不是部署在本地服务器上。传统的数据中心流量主要是来自数据中外部客户端请求访问数据中心内部服务器的流量，近年来随着分布式业务的发展，数据中心内部服务器之间的流量大幅增加，例如主从备份、设备动态迁移等。这些流量称为“东西向”流量，现在数据中心中“东西向”流量占总流量的80%[1-2]，即数据中心内部服务器之间的通信流量占绝大多数。数据中心网络的特点是服务器之间的流量大、突发流量大等，通常数据中心是通过增加冗余链路来达到增加带宽的目的[1]，如何调度多个链路成为提高网络性能的关键，所以需要为数据中心制定高效可行的流量调度方法，来缓解网络流量压力。

传统网络模式下的数据中心网络具有纯分布式控制、控制与转发高度耦合的特点，以及尽力而为的转发模式，导致针对性强且复杂的调度策略很难在传统网络的结构下实施。传统网络中每个节点独立工作，若网络环境改变，使得网络整体不能动态地调整，所以越来越多的人会考虑使用软件定义网络(SDN)这种松耦合且扩展性强的网络架构[3]。

SDN作为新型的网络体系结构，其核心思想是数控分离[4]。交换机只负责简单的数据转发工作，决策功能全部集中在控制器中。控制器作为SDN的核心能够管控整个网络，并通过OpenFlow[5]消息与交换机交互，可以针对复杂多变的业务场景制定灵活的网络转发策略，为数据中心流量负载均衡问题提供了新思路。

1 相关工作

为了避免拥塞，数据中心网络(DCN)通常在任意2台服务器之间设计有多条路径来提高带宽和容错，例如Fat-tree架构[6]，但是如何合理地调度多个路径是一个很大的挑战。

等价多路径路由(ECMP)是目前应用最广泛的流量调度策略。ECMP是一个基于流的流量调度策略，它根据流的五元组信息通过哈希、轮询或者随机的方式将流分配到某一个路径中，达到增加带宽的目的[7]。然而ECMP有2个明显的缺点，首先是ECMP没有拥塞感知机制，给已经拥塞的链路继续分配转发任务，导致加重拥塞；另外ECMP并不区分大象流和老鼠流，这种无差别的转发策略显然已经不再适用于当今的数据中心网络。

Hedera[8]是一种集中式的动态流量调度策略，结合OpenFlow[9]动态地求得大象流带宽阈值，老鼠流使用ECMP策略转发，大象流通过模拟退火算法求得转发路径，转发效率相对于ECMP有了显著提升。虽然Hedera从理论上可行，但由于流量的庞大，大象流的调度策略难以很好地扩展到DCN。Curtis等人[10]已经证明Hedera的说法过于乐观，并且控制器无法快速提取流量统计数据以做出路由决策。此外，Hedera的大象流量检测机制也会增加网络负担。

Zhang等人[11]针对将数据中心流量和交换机内存转化为一个稳定匹配问题，设计了一种名叫Fincher的算法，并证明了这一问题是一个NP难问题。Fincher寻找流与交换机之间的稳定匹配，考虑到了交换机内存对于流完成时间的影响，但是只考虑了共享内存式交换机内存对大象流转发的影响，并未考虑链路，且缺乏实时性。

针对以上现有流量调度策略的局限性，本文提出一种动态优先级多路径调度算法(DPMS)。DPMS结合数据中心流量重尾分布[12-13]的特性降低了大象流检测所消耗的额外负载，并且能根据链路实时状态动态改变多路径的优先级，达到提高网络吞吐量的目的。

2 多路径调度算法设计

2.1 算法思想

多路径调度算法是一种SDN架构下适用于数据中心Fat-Tree网络的多路径流量调度策略。该策略中主要工作包括数据包采集、大象流检测、链路代价计算和可行路径计算。流量调度流程如图1所示。

图1 流量调度流程图

详细步骤如下：当流到达边缘交换机时，首先检测该交换机流表项中是否已经有相匹配的流表，若有，则说明之前已经为该流做出了转发策略且策略未过期，交换机直接按照流表规则转发；若没有，则把首个数据包通过Packet_In消息发送给控制器，由控制器做决策。控制器接收到Packet_In消息后首先判断该流是大象流还是老鼠流，若为大象流，交换机计算K条最短路径，并根据链路代价计算各个链路的优先级，控制器根据K条路径及其优先级通过Flow_Mod消息下发组表和流表，交换机根据组表和流表规则转发大象流；若为老鼠流，则控制器计算时延最短的路径，通过Packet_Out消息下发流表，交换机根据流表规则转发老鼠流。

2.2 大象流检测模型

本文使用sFlow agent统计交换机中的流量，使用sFlow-rt作为收集器[14]。整个过程中sFlow agent过滤掉已经被认定为大象流的流量不必全量采样，且对数据包的处理过程发生在数据平面，这样有效地减少了控制平面的额外负担。采样率设置为1/z，表示每z个数据包采样一个数据包，采样率必须设置合理，过大会导致大象流的丢失，影响准确性，过小会增加内存和计算负担[17]。整个过程中，采样的数据包需要实时计算自适应阈值σ来判断是否是大象流。

数据中心的流量服从重尾分布，大象流的数量很少，但却占据了大部分的网络流量，老鼠流的数量很多，却只占有很少的流量，数据中心经常使用这一特性改善网络链路。本文使用Pareto[15-16]重尾模型来计算动态阈值，其概率密度函数是P(βi=x)=αkx-a-1(x≥k)，其累积分布函数用公式(1)表示，公式(2)表示互补累计分布，其中α=1.2，k=2。

(1)

(2)

(3)

公式(4)表示采样数据包大于阈值x的条件下，总数据包数量超过阈值X的概率[18]。

P(mi≥X|ki≥x)=

(4)

2.3 链路代价计算

大象流的链路代价计算需要考虑链路带宽和时延这2个因素，定义p(s,d)表示从源s到目的地d的k条路径，p(s,d)k表示第k条路径。

每条链路包含多个子链路，而链路的剩余带宽类似于木桶原理，链路的剩余带宽等于子链路剩余带宽的最小值，定义p(s,d)k上链路剩余带宽(remaining bandwidth， rb)为：

rb(s,d)k=min(bwki),i∈p(s,d)k

(5)

其中，bwki是第k条路径上第i段链路的剩余带宽，i是p(s,d)k路径上的第i段路径。

那么可以定义路径p(s,d)k上各链路利用率(Link Resource Utilization， LRU)为：

(6)

其中，tb(s,d)k表示p(s,d)k的链路总带宽，链路总带宽等于该链路包含的子链路的带宽最小值。

定义路径p(s,d)k上大象流的链路代价(link cost of elephant flow， lce)为：

lce(s,d)k=m×NRUp(s,d)k+n×d(s,d)k

(7)

其中,d(s,d)k表示路径p(s,d)k的平均时延，m、n分别是剩余带宽和时延的链路代价系数，且m+n=1。由于大象流是带宽敏感型[19]，与大象流相关的业务一般对链路资源要求较高，对时延要求较少，所以m的取值要比n大一些。在本文中，通过仿真实验分析，链路代价系数m、n的取值分别为0.8、0.2。

由于老鼠流是时延敏感性流[20]，数量较多，但携带数据很少，所以交换机没必要为每个老鼠流配置永久流表。当收到老鼠流时控制器只需要计算得到当前时延最小的路径，然后下发流表并设置软超时时间，使得转发完成后交换机自动删除该流表。所以老鼠流的链路代价(link cost of mouse flow， lcm)表示为：

lcm(s,d)k=m×d(s,d)k

(8)

2.4 可行路径计算

K-pod Fat-tree网络分为3个层次：自上而下分别为边缘层、汇聚层和核心层，图2给出了一个4-pod Fat-tree网络架构的示例。拓扑含有(k/2)2个核心交换机，其中汇聚层交换机与边缘层交换机构成一个pod，每个pod有k/2个汇聚层交换机。在此网络拓扑中，pod间任何主机对之间都存在(k/2)2条相同的最短路径。pod内流分为2种情况：如果2个主机连接在一个交换机上，那么就只有一条最短路径可选，如果不在同一个交换机上则有k/2条最短路径[22]。

图2 4-pod Fat-tree网络架构图

本文采用K短路径算法(KSP)[21]来得到跳数最少的k条路径，并计算链路代价作为每条路径的优先级，最后下发组表和流表。本文将此算法称为动态优先级多路径调度算法(DPMS)。DPMS的伪代码如算法1所示。

算法1DPMS

输入：当前要处理的流flow，网络拓扑

输出：最优路径path

1 if (flow是大象流)

2 if (flow是pod间流)

3w=跳数;

4 path[]=KSP((k/2)2,w,s,d);

5 else if (flow是pod内流)

6 if (s和d在同一交换机上)

7 path[]=KSP(1,w,s,d);

8 else

9 path[]=KSP(k/2,w,s,d);

10 for (p: path)

11p.priority=priority(s,d)p

12 else

13 weight=时延;

14 path[]=KSP(1,weight,s,d);

15 return path;

其中第4行是调用Floodlight控制器的内置KSP算法，4个参数分别是要求得路径个数、计算参数、源地址和目的地址，算法第11行是计算每条链路的优先级，如公式(9)所示，p(s,d)中k个链路的优先级定义为k条链路代价的总和与当前链路的链路代价的比。

(9)

OpenFlow1.3支持组表，组表[23]是一种复杂的转发模式，用在多路径、快速重路由等场景下。通过算法求得的大象流最优路径是一组k个链路及其优先级的集合，组表中可以含有多个group_buckets，即粗略对应多条路径，每个group_buckets里的bucket_weight对应其优先级。研究表明，SDN网络中主要时延来自于交换机发送Packet_In消息时，交换机缓存数据包等待控制器命令的下发这部分时间，在本方案中，交换机下发组表后该组表会一直存储在交换机中，只需要根据网络状态定时更新每个bucket_weight，并不需要中断当前通信去请求控制器，在缩短时延方面有明显的优势。

2.5 系统总体架构

该流量调度系统架构如图3所示，主要包含3个部分：最底层的是数据平面，数据平面除了包含OpenFlow交换机外还有sFlow agent，负责流量采样；负责流量监测的是sFlow收集器，该部分接受数据平面中sFlow agent采样的数据，并进行大象流检测，最后把检测结果发送给SDN控制器；最后一部分是SDN控制器，SDN控制器负责获取全网信息，并计算转发路径下发流表。

图3 流量调度系统架构图

3 仿真与分析

3.1 仿真环境

本文在Linux系统上使用Floodlight控制器实现了DPMS算法，并使用mininet[24]模拟数据平面拓扑，构建了一个如图2所示的4-pod Fat-Tree网络拓扑结构进行仿真。本实验通过Iperf性能工具产生流量，且大象流和老鼠流的比例是9:1，链路带宽设置为100 Mbit/s。

仿真使用2种数据中心常用的流量模式：

1)Random：每台主机等概率地向其他主机发送数据。

2)Staggered Prob(EdgeP,PodP)：主机以概率EdgeP发送到同一边缘交换机中的另一个主机，称为机柜流量。以概率PodP发送到其相同的pod且不在同一边缘交换机的主机，即pod内流量。以概率1-EdgeP-PodP发送到网络的其余部分，即pod间流量。

3.2 仿真结果分析

本文从平均吞吐率、平均流完成时间(FCT)和链路利用率这3个角度比较了DPMS、Hedera和ECMP这3种策略，以验证性能的实际提高。

平均吞吐率是衡量网络性能的重要指标，本文在6组网络模式下比较3个调度策略的性能。如图4所示，在EdgeP较低时，即网络内有较多的pod内流和pod间流时，DPMS、Hedera和ECMP这3种策略的吞吐率差距较大。因为在pod内流和pod间流多的情境下，ECMP无法根据链路拥塞状态动态地分配链路资源，大象流的碰撞率增大。Hedera区分大象流和老鼠流，动态对大象流进行调度，所以效果比ECMP要好。DPMS除了为大象流提供动态调度，还针对pod内流和间流进行路径优化，并且改善了交换机同控制器的通信，减少了流等待时间。

图4 网络平均吞吐率

数据中心的老鼠流通常是时延敏感性，通常与对时延敏感的应用相关联，所以平均流完成时间(Avg FCT)是此类流量的关键性能指标。本文在5组流量模式下比较了3个流量调度策略的Avg FCT，如图5所示，当机柜流量占比为多数时3种调度策略的差异不大，随着跨交换机和跨pod的流量的增多，DPMS逐渐展现出优势。这是因为数据中的老鼠流是以没有拥塞感知的ECMP策略调度的，当大象流量发生碰撞时会阻塞链路，如果此时老鼠流被调度到此链路便会发生拥塞。DPMS更加合理地调度了大象流，均衡地利用了网络资源，间接地保证了老鼠流的传输环境。

图5 网络平均流完成时间

通过DPMS进行多路径的调度最直观的表现就是链路利用率，它反映了算法是否合理地利用了冗余链路。选取6组流量模式进行试验，如图6所示，同样ECMP和Hedera在pod间流量占比较大时大象流碰撞较多，容易造成链路拥塞，链路带宽利用不均衡。DPMS算法更好地利用了链路，并对pod内流和pod间流作出优化，其链路利用率更高。在stag(0.8,0.1)的流量模式下，由于机柜流量较多，即表示没有太多的冗余链路可以利用，所以3种调度策略的链路利用率差异不明显。

图6 链路利用率

4 结束语

本文研究了数据中心大象流调度问题，发现数据中心内“东西向”流量的合理调度是数据中心流量负载均衡的关键点。然后在SDN的架构下提出了一种动态优先级多路径调度算法DPMS，该算法根据链路实时状态以及大象流和老鼠流的特性动态地改变路由策略，减少了交换机中数据包队列的等待时间。通过对比实验表明，与ECMP和Hedera相比，部署DPMS的网络具有更高的链路利用率和吞吐量、更低的时延。通过模拟仿真的形式验证了算法的可行性，并在真实环境下部署测试，因此真实环境下该算法对控制器的负载问题还需要进一步研究。