集成SDN框架的启发式数据流调度算法研究

黄 润 肖志良,2

1(佛山职业技术学院电子信息学院 广东 佛山 528137) 2(武汉大学信息管理学院 湖北 武汉 430072)

0 引 言

近些年，云数据中心的规模越来越大，托管着大量主机。由于海量数据的生成，数据中心面临着ToR交换机之间的巨大通信量需求的严峻挑战[1]。因此，ToR之间的业务流调度问题逐渐成为云服务供应商的一个难题，需要通过流准入决策来实现某些特定的目标，如收入、能量效率或资源利用率最大化[2-3]。

目前，已经有一些研究成果。如文献[4]研究了光数据中心网络的分组级调度，其特点是网络逻辑拓扑的频繁重构。文献[5]提出了针对数据中心环境的流调度算法，可应用于多根分层式树结构的动态流调度。该算法对网络链路上负载进行动态估计，并将数据流从重负载链路移动到轻负载链路，由此确保了网络链路间的负载平衡。文献[6]基于广域电分组交换网络背景，利用交换机发送的显式拥塞通知包，在广域网中跨多条路径执行动态流量工程。文献[7]将流调度问题转化成背包问题求解，提出基于离散粒子群DPSO的流调度算法，以两次迭代冲突流个数差值作为目标函数，但该方法需要分组交换机，由此增加了功耗和布线复杂度。文献[8]根据网络资源使用状态，提出自适应请求选择策略，即自适应从频谱资源方面选取请求。对选出来的请求进行重新服务，利用混合整型线性规划模型进行数学建模。

本文旨在最大化云服务供应商的总收入，同时满足波长连续性约束和带宽容量约束。其设计理念是在每个时隙后对光路进行动态重构，将不再使用的光路从逻辑网络拓扑中移除，同时，活跃的流也能够迁移到新光路中。在此基础上，设计了一个集成的SDN框架，以执行业务流调度和光路重构。仿真结果验证了本文算法的高效性。

1 数据中心的流调度问题

本文研究的两层数据中心架构如图1所示。假设数据中心中存在M个ToR交换机。每个ToR交换机通过光纤连接到核心光交换机，每条光纤最多可承载W个波长，即：一个ToR交换机可以通过光路同时到达W个ToR交换机。在没有波长转换器的情况下，穿过光交换机的两个ToR交换机之间的光路必须具备波长连续性。

图1 两层光数据中心架构

另外，每个业务流要求一个波长的最大带宽容量，一对ToR交换机之间所容纳的流数量，必须低于将这两个ToR连接到光交换机的光纤所承载的波长数量，否则应该丢弃一定数量的业务流。

设Ft为在时隙t开始时处于活动状态的所有业务流集合，即包括在时隙(t-1)中网络容纳的所有流和所有被提交的流。每个流f∈Ft表示为元组(sf,df,uf,ef)，其中，sf、df、uf和ef分别表示流f在网络中的源ToR交换机、目的地ToR交换机、服务时间、已经过的服务时间。数据中心的目标是最大限度增加云服务供应商的长期总收入，该目标函数可表示如下：

(1)

式中：cunit为每时隙容纳一个流的单位成本；xf为二元变量，表示流f是否被数据中心容纳过。式(1)第二项表示：如果以往时隙中被容纳过的流，在当前时隙中被拒绝，则从总收入中扣除通过该流从以往时隙中所得到的所有收入。

给定已经被容纳于数据中心内的流f，设yf为决策变量。准入决策和波长分配均需要满足光纤容量约束和波长连续性约束。光纤容量约束表示为[9]：

(2)

波长连续性约束表示为：

(3)

该约束确保了对于某个特定ToR，将该ToR连接至核心光交换机的光纤所承载的波长w最多仅使用过一次。

现在定义光数据中心的流调度问题的形式化表达：给定一组业务流，每个流f表示为一个元组(sf,df,uf,ef)，确定一个准入决策和一个波长分配策略，以使得服务供应商的长期总收入最大化。

(4)

满足：

(5)

(6)

求解上述问题不具备计算可行性，原因是：1) 问题的规模，即决策变量的数量非常大；2) 由于输入业务流的动态到达，当前时隙的准入决策会影响到未来时隙的准入决策，由此影响到总体收入；3) 两个ToR交换机之间的光路波长选择会影响到未来ToR连通性。因此，本文提出求解上述问题的启发式算法。

2 SDN框架下的启发式流调度

2.1 最小拥塞和服务时间优先的调度

由于流的服务时间也将影响到ToR的未来连通性，服务时间越长，则ToR因为波长连续性约束而失去连通性的时间越长。因此，本文方法向服务时间较短的业务流给予较高的优先级，使其先于其他流被容纳。提出的最小拥塞和服务时间优先算法的伪代码如下：

Input：网络状态

Output：准入和波长分配决策

1.fort=1…Tdo

2. 执行光路重构；

5. 得到具有最小拥塞因子和服务时间的流f；

6.if可在ToRsf和ToRdf间建立起一条光路

7. 则确定最优波长；

8. 在ToRsf和ToRdf之间建立光路；

9. 将流f容纳在网络中；

10. 更新波长使用情况；

11.else

12. 通知流f的拒绝消息；

13.endif

15.endwhile

16.return准入控制和波长分配；

17.endfor

流f的拥塞因子[10]定义如下：

(7)

然后，选择具有最低的拥塞因子和服务时间的流f。若ToRsf和ToRdf之间可以建立起一条光路，即ToRsf和ToRdf之间存在共同波长，则确定新光路的最优波长，并对波长的使用情况进行更新以反映在下一次调度中。否则，该业务流将因为波长约束而被拒绝。算法继续处理下一个输入流，直到完成所有流的处理。

2.2 基于拥塞的循环算法

应用上述算法会为网络建立较好的连通性，由此增加网络中容纳业务流的数量。然而，其可能会导致业务流饥饿问题，即：具有更短服务时间的新业务流的动态到达导致一些流永远无法被容纳到网络中。为实现流之间的公平性，本文使用了循环方法，而不是基于流服务时间进行优先级排序，即基于拥塞的循环CBL算法。首先，在计算出业务流的拥塞因子后，通过业务流的拥塞因子来选择要调度的流。由于许多流可能有着相同的源和目的地，这些流可能有相同的拥塞因子。然后将所有流分入不同集合中，每个集合有一个不同的拥塞因子。在应用循环调度时，在每个调度轮，从每个集合中选出一个流进行调度，且从具有最低拥塞因子的集合开始。

表1给出了根据不同优先级方法得出不同调度顺序的输入流样例。若应用2.1节的算法，其调度顺序为f1、f2、f3、f4。若使用循环方法，其调度顺序为f1、f3、f2、f4。已知将ToR 2连接至核心光交换机的光纤具有2个可用波长，则根据算法f3和f4将被拒绝。若根据循环方法则将拒绝f2和f4。因此在应用算法时，服务时间较短或较长的流被容纳于网络中的机会均等。

表1 使用不同的优先方法进行流调度的样例

2.3 基于SDN的流调度框架

在SDN控制器下，光数据中心流调度的总体框架设计如图2所示。

图2 光数据中心流调度的SDN框架图

数据收集模块接收到达每个交换机的输入流信息。基于网络状态和数据收集模块所接收到的输入流信息、控制器运行的调度算法，取决于云服务供应商选择的调度算法。波长分配被转发至光路配置模块，以调用电路交换，并在ToR交换机之间建立光路。准入决策则发送至ToR交换机，以开始准入流的数据传输并丢弃其他流。云服务供应商还可决定运行算法的频率，以实现性能最大化，即通过每个时隙的持续时间实现性能最大化。在SDN的支持下，上述框架可利用支持OpenFlow的交换机[11]实现，且文献[12]已经证明了在光网络上进行SDN控制的可行性，由此可以灵活地执行光路配置。图2中的可重构光分插复用器[13](ROADM)是光网络的一个重要光子交换设备。通过波长选择光交换机，ROADM能够对光路丢弃或添加多个波长，且不需要将光信号转换为电信号。由于ROADM设计了一个管理控制平面，并提供OpenFlow协议，使得SDN控制器可以远程控制波长的变化。

在SDN框架下，MC-STP的算法流程步骤总结如下：

1) SDN控制器通过光网络层中ROADM的OpenFlow协议，远程执行光路重构。

2) 支持OpenFlow的ToR交换机计算拥塞因子，得到具有最小拥塞因子和服务时间的流。

3) 如果能在某两个ToR交换机间建立一条光路，则确定最优波长。

4) SDN控制器通过调度决策层将该流容纳在网络中，并更新波长使用情况。

5) SDN控制器通过基础控制层将波长分配转发至光路配置模块。

在SDN框架下，CBL与MC-STP不同的主要体现在：CBL在每个调度轮中，从每个集合中选出一个流进行循环调度，而不是基于流服务时间进行优先级排序。这样可以避免业务流饥饿问题。

本文两个算法的时间复杂度为O(nlogn)，其中n为输入流的总数量。因此，在执行调度时，本文算法不会为控制器带来较大开销，在SDN框架下具有一定的可行性。

3 性能分析

3.1 设 置

本文研究的光数据中心网络及其架构如图1所示，核心交换机连接着48个ToR交换机，将ToR交换机连接至核心交换机的光纤承载了25个波长。每个波长的容量为1 Gbit/s。从ToR集合中随机选出源ToR和目的地ToR以生成输入流，从时隙[5, 20]范围中随机选出每个流的服务时长，并假定每个流要求一个波长的整个容量。

本文对以下4个算法进行性能检验：

1) 本文最小拥塞和服务时间优先(MC-STP)算法：服务时间短和拥塞因子小的业务流将得到更高的优先级。2) 本文基于拥塞的循环(CBL)算法：确保流之间的公平性。3) 文献[4]基于端到端(E2E)的流调度：使用先到先服务原则，基于业务流到达顺序对输入流进行调度。4) 文献[7]基于离散粒子群(DPSO)算法的流调度：应用智能算法，基于网络状态判定每个流的准入或丢弃。

所有算法均运行2 000个接收输入流的时隙。使用以下度量对算法进行性能评价：

1) 拒绝率：丢弃流的数量与输入流数量间的比率。

2) 平均收入：根据式(1)计算。

3) 波长利用率：2L/(MW)。其中：L为网络中创建的光路总数量；M为ToR的总数量；W为光纤承载的波长数量，取算法运行2 000个时隙的均值。

3.2 结果与分析

3.2.1 总体性能

图3给出了相对于每时隙到达的不同流数量，各算法所生成的拒绝率。可以看到，MC-STP和CBL算法性能优于其他算法。在拒绝率低于10%的区间(实际应用有意义的情形)，MC-STP和CBL的拒绝率明显低于E2E[4]和DPSO[7]。随着流数量的增加，在不采用任何优先排序方法的情况下，容纳数据流会导致网络性能变得很低，因为容纳某个特定流会造成整个网络堵塞，使得随后到达的所有流均被丢弃。此外，应用CBL为输入流之间带来公平性，但会造成拒绝率小幅上升。

图3 业务流到达的拒绝率变化情况

图4给出了从经济角度看，2 000个时隙后云服务供应商得到的平均收入。结果表明：与E2E[4]、DPSO[7]相比，MC-STP和CBL最高提升了3%的平均收入。从中还可观察到，CBL在平均收入方面的性能稍优于MC-STP。这是因为MC-STP算法给予服务时长较短流更高的优先度。由于业务流的动态到达，造成波长(光路)利用率碎片化，短空闲时间更多。由此，容纳服务时间更长的流将使得平均收入更加稳定。结果表明，MC-STP的拒绝率低于CBL，但MC-STP产生的收入也低于CBL。供应商可根据需要选择合适的算法集成到所提框架中进行流调度。

图4 长期运行后的平均收入

图5给出了各算法的波长利用率。结果表明，本文算法对光纤载波的利用较好。当每时隙到达70个流时，本文算法将波长利用率从86%提升至89%，这一提升得益于本文提出的优先方法。由于每条光路涉及到将源ToR和目的地ToR连接至核心光交换机的两条光纤，且优先容纳具有最小拥塞因子的流，实现了对ToRs相关光纤中的共同波长的更好利用。由此避免了源ToR的光纤中的可用波长在目的地ToR的光纤中不可用的情况。

图5 网络的波长利用率

3.2.2 波长再分配

本文在两个场景中运行所提算法，并测量拒绝率。1) 带波长再分配(用-1标识)：在每个时隙结束时，从网络的逻辑拓扑中移除不再需要的光路，而且对现有业务流所使用的所有活动光路进行修改，并再次分配新的波长。2) 不带波长再分配(用-2标识)：仅移除不再需要的光路。

本文算法在上述两个场景运行时的拒绝率如图6所示。结果表明：应用波长再分配能够显著提升性能。在拒绝率低于10%的区间内，带波长再分配的算法MC-STP-1和CBL-1的拒绝率明显低于不带波长再分配的算法(MC-STP-2和CBL-2)。当每时隙到达70个时隙时，与不带波长再分配相比，带波长再分配的算法能够将拒绝率最高降低16%。如前文所述，波长再分配能够提升ToR间的连通性，以便容纳后续到达的更多流。同时，由于波长连续性约束，波长再分配增加了任何一对ToR的光纤中可用波长数量。在不带波长再分配的算法中，ToR间的可用波长数量较少，因此拒绝率较高。值得一提的是，两类方法均不会增加或减少ToR连接到核心光交换机的光纤可用波长数量，但会影响ToR间的一些性能。

图6 使用或不使用波长再分配时的拒绝率比较

3.2.3 增量拓扑与可重构拓扑的比较

通过仿真评价了本文算法使用增量拓扑时的性能。在增量拓扑中，即使不再需要一条光路，也不会将其从逻辑拓扑中移除。增量拓扑场景中，波长再分配也被禁用。比较结果如图7所示，其结果符合预期，增量拓扑案例(MC-STP-增量)的拒绝率大幅上升。当每时隙到达20个流时，可重构拓扑案例(MC-STP-重构)中未出现拒绝情况，而增量拓扑案例中拒绝率则达到50%。造成这一现象的原因是业务流的动态到达，以及业务流的源ToR和目的地ToR的随机性，使得对于不同源与目的地ToR，可用光路非常少，而其他ToR没有可用的光路来容纳到达的业务流，这在实际应用场景中是必须要避免的。而MC-STP-重构的拒绝率大部分情况下低于10%，在实践中可用。

图7 增量网络拓扑与可重构网络拓扑的性能比较

4 结 语

本文研究了数据中心网络中的流调度问题，并针对该问题提出的一个优化方法，以最大化云服务供应商的长期收入。由于流调度问题不具备计算可能性，本文采用了业务流调度的启发式算法，利用拥塞因子来确定业务流调度顺序。此外，还利用优化函数来确定最优波长，以确保ToR交换机的连通性。本文算法不但保证了云服务供应商的最大收入，而且确保业务流之间的公平性。仿真结果表明，本文算法的性能优于其他算法，最高能够降低10%的拒绝率。