光电混合数据中心网络负载均衡流量调度机制
2017-08-12蔡岳平樊欣唯王昌平
蔡岳平 樊欣唯 王昌平
(重庆大学通信工程学院 重庆 400030)
光电混合数据中心网络负载均衡流量调度机制
蔡岳平 樊欣唯 王昌平
(重庆大学通信工程学院 重庆 400030)
光电混合数据中心网络采用传统的RED(Random Early Detection)流量调度机制容易造成数据流丢失，同时在等价转发路径的选择上存在随机性。提出一种基于流量预测矩阵的负载均衡流量调度机制。该机制利用软件定义网络，具有全局视角的优点，周期性统计网络流量，建立流量预测矩阵。通过流量预测矩阵动态计算数据流在多条等价链路上的转发概率，并按此概率完成下一个周期的转发。同时，利用电交换链路单独处理突发流量，提高网络吞吐量，实现网络负载均衡。在光电混合数据中心网络拓扑结构上建立合成流量模型进行仿真实验和性能分析。结果表明，与传统的RED流量调度机制相比，该机制能够提高网络吞吐量、降低数据流丢弃率。
光电混合数据中心网络架构 软件定义 流量调度 负载均衡
0 引 言
随着云计算技术的不断发展，数据中心内部的通信量呈爆炸式增长，对数据中心网络带来巨大的带宽需求[1]。云计算[2]广泛应用于搜索引擎、在线地图、社交网络等数据密集型应用中，而这些应用的实现得益于高效的数据中心交换网络[3-7]。一个拥塞的数据中心网络通常面临大量数据分组丢失和网络吞吐量下降等问题，这会导致搜索的时延大、即时信息不能够被迅速转发等，降低服务的质量。
文献[8-9]提出了一种混合光路由和电分组交换的数据中心网络架构HWRE(Hybrid optical Wavelength Routing and Electrical packet switching)，其利用基于阵列波导光栅路由器AWGR(Arrayed Waveguide Grating Router)的光路由技术带来的低时延、高带宽的光互连网络与电分组交换网络协同通信，解决了高带宽需求问题。此HWRE架构的光路由核心部分采用AWGR，与传统架构Helios[10]和c-Throng[11]采用的MEMS光交换机相比，能降低配置的时延，提高网络的吞吐量。然而在此架构中需要使用高效的流量调度机制来获得更好的网络性能。
传统的队列调度采用随机早期检测算法RED[19]。该算法通过计算平均队列长度对网络的拥塞程度进行估计。当平均队列长度超过一定阈值时，根据拥塞的程度计算将数据分组丢弃的概率，从而有效地控制平均队列长度。在该算法中，每个输出端口缓存队列中维持两个参数，即队列最小门限和最大门限。当有新的数据流到达某队列时，计算该队列的平均长度，若平均队列长度小于最小门限，则把新到达的数据流放入队列进行缓存。若平均队列长度超过最大门限，则将新到达的流丢弃。若平均队列长度在最小门限和最大门限之间，则按某一概率将数据流丢弃。这种算法在一定程度上造成了数据流的丢弃，降低网络吞吐量。
本文提出了一种新的负载均衡流量调度机制以解决在光电混合数据中心网络架构中的流量调度问题，同时该机制利用具有集中控制优势的SDN技术，从全局的角度掌控全网的流量状态信息，并能够根据网络状况动态调整流量调度方案，实现负载均衡。在HWRE架构中，架顶交换机ToR需要在多条等价链路间选择一条进行数据转发。本方案为每条等价链路动态的计算转发概率，以实现负载均衡，提高网络吞吐量。首先，SDN控制器对数据流量进行周期性统计，并依此建立、更新流量预测矩阵。在方案中，电分组交换链路专门用来处理突发流量，不参与等价链路转发概率的计算。控制器根据流量预测矩阵，计算出每条链路的利用率，并根据结果求出每条链路的可利用率，然后对所有等价链路的可利用率进行归一化处理，得到每条等价链路上数据流的转发概率，在下一个周期内，数据流按此概率完成转发。在转发过程中，若交换机转发端口的队列长度超过了设定的阈值，则将其调度至队列长度最小的可用端口，若该端口的队列长度依然超过阈值，则将其调度至电分组交换端口处理。
1 光电混合数据中心网络
本文研究的数据流调度机制针对基于阵列波导光栅路由器的混合光路由AWGR与电交换的数据中心网络架构(HWRE)[13]。该架构充分利用光传输网络具有的高带宽、高吞吐量、低能耗等优点，减少电分组交换机的部署，且光路由网络选用光无源器件实现，保证了网络的可靠性。
1.1 阵列波导光栅路由器(AWGR)
阵列波导光栅路由器[11-12]AWGR(Arrayed Waveguide Grting Router)是该架构光路由的核心器件，无需配置就能够根据循环波长路由特性直接实现光波长路由。AWGR具有的循环波长路由特性可以将不同波长的光信号从同一输入端口路由到不同的输出端口。
图1 阵列波导光栅路由器
1.2 光电混合数据中心网络架构
以电分组交换机EPS(Electronic Packet Switch)为核心的电分组交换网络和以阵列波导光栅路由器为核心的光路由网络构成了光电混合数据中心网络架构[13]。如图2所示，控制平面与数据平面分离，数据平面由AWGR、EPS、ToR等构成，控制平面由SDN控制器构成。
图2 光电混合数据中心网络架构(HWRE)
在HWRE架构中数据流可以经过光路由网络传输，也可以选择电交换网络传输，具体的传输路径由SDN控制平面进行集中控制选择。当路径选择光路由路径时，网络中的上行数据在架顶交换机的上行端口处被调制到合适波长的光载波上，然后通过AWGR将输入的光信号路由到相应的输出端口，传输到目的ToR，由目的交换机将信号进行解复用后转发到相应的服务器。数据经过电交换网络传输时，ToR将数据调制到光载波上转发到核心电分组交换机，核心电分组交换机将光信号转换成为电信号后进行处理，然后再将数据调制到光载波上通过光纤传输给目的ToR。目的ToR将接收到的光信号转换成为电信号后转发给相应的服务器。
2 负载均衡调度机制
在HWRE架构中，当使用固定波长激光器作为光源时，各ToR间的光路径是固定的，且只能通过一条路径分担负载。而当使用波长可调谐激光器作为光源时，ToR在数据转发的时候，可以在多条等价链路间进行选择。由于数据中心网络的流量大部分持续时间较短，多为突发流量，流量在大小和时间上分布不均匀，因此我们采用电分组交换机专门处理突发流量。
图3是HWRE架构基于SDN的负载均衡流量调度机制总体设计，共包含三个功能模块：流量数据的收集，流量预测矩阵的建立和链路转发概率的计算。首先，各架顶交换机ToR以间隔时间T为周期，统计本周期内从每个ToR各端口链路转发到其他ToR的数据流量，并上报至控制器。控制器根据收集的流量数据建立本周期的流量矩阵，并依此计算下一周期的预测矩阵。根据流量预测矩阵，计算得到每条等价链路上数据流的转发概率。在新的周期内，数据流按此概率完成转发。在数据流转发时，若交换机转发端口的队列长度超过了阈值，则将其调度至AWGR中队列长度最小的可用端口，若该端口的队列长度依然超过其阈值，则将其调度至电分组交换端口做转发或丢弃处理。
图3 HWRE数据流调度方案总体设计
研究人员发现，数据中心网络的流量具有突发性的特点，当时间跨度超过150 s时，其流量矩阵难以预测[15,17]。然而文献[10]研究发现，在1 s的时间周期内数据中心网络流量并没有明显的变化(设定为大于20%的改变)。此结果表明，在细时间粒度内流量矩阵具有可预测性。因此本文选择统计周期时间为1 s进行流量数据的收集与流量预测矩阵的建立。
本文在光电混合数据中心网络架构上进行研究架顶交换机完成对流量数据的收集、汇总、汇报和更新。
2.1 流量预测矩阵
流量预测矩阵的建立是整个调度机制的基础和创新点。首先，各架顶交换机ToR以间隔时间T(1 s)为周期，统计本周期内从一个ToR的各端口转发到其他ToR的数据流量，并同时上报至SDN控制器。控制器收到各ToR上报的信息后，对每个端口收到的数据流进行统计，建立每台ToR上各等价链路本周期的流量矩阵MnT，流量矩阵对应此ToR的端口号和转发至其它各ToR的统计流量和。通过本周期流量矩阵MnT建立下一周期该ToR的预测矩阵，根据公式：PM(n+1)T=MnT+γ×MnT。其中(0<γ<1)为调整因子，用以下一周期容纳突发流量。在本文中，我们按照文献[10]的研究，选取γ=0.2。流量预测矩阵的建立为转发概率的计算提供依据，控制器根据预测矩阵PM(n+1)T计算下一个周期的数据流在各条链路上的转发概率，以实现负载均衡的目的。
2.2 转发概率的计算
2.3 算 法
下面我们对流量调度算法进行分析，其计算复杂度为O(n2)。算法1是对流量调度算法的总体描述。T表示统计的周期时间，FnT表示第n个周期时流的统计信息集，PMnT表示本周期的流量预测矩阵。当一个新流到达一台架顶交换机ToR的时候，算法被触发，算法根据流量矩阵为新流提供一条转发路径。首先，当新流f到达后，ToR会将其统计信息添加至第n个周期时流量的统计信息集FnT中并存储在缓存当中，在nT时刻打包发送给控制器。控制器收到FnT的信息后，据此建立下一周期的流量预测矩阵(算法2至4行)。与此同时，触发子算法ProbabilityCalculation(·)进行链路转发概率的计算，得到各等价链路的转发概率。在转发时，当转发的链路其链路队列超过阈值Threshold·path时，将数据流调度至电分组交换机端口完成转发(算法7至11行)。若电分组交换机端口处的队列同样超过了其阈值Threshold·EPS，则将数据流做丢弃处理(算法15至17行)。
算法1流量调度算法
输入:G:HWRE数据中心网络拓扑;
FnT：第n个周期时流的统计信息集;
PMnT：本周期的流量预测矩阵;
Cap:链路的容量；
Threshold·path：链路的队列阈值；
Threshold·EPS：电分组交换机链路队列阈值。
输出:{
1)IF a new flow f arrives THEN
2) FnT← { f };
3) MnT←FnT;
4) PM(n+1)T←MnT;
//建立下一周期的流量预测矩阵
5) < p(i,j)> ←ProbabilityCalculation(G,PM,Cap);
//触发转发概率计算算法，得到链路转发概率
6) f.path ←p(i,j);
//通过链路转发概率选择转发路径
7) IF queue.path <= Threshold.path THEN
8) f.method ←FORWARD
9) RETURN < FORWARD,f.path >
10) ELSE
11) f.path ←EPS.path
//转发至电分组交换机端口
12) IF queue.EPS<= Threshold.EPS THEN
13) f.method ←FORWARD
14) RETURN < FORWARD, EPS.path >
15) ELSE
16) f.method ←DISCARD
17) RETURN < DISCARD,-l >;
18) END
19) END
20)END
算法2是对等价链路转发概率计算算法ProbabilityCalculation(·)的描述，算法需要为等价路径计算下一周期内数据流的转发概率。若等价链路的数量为1，即没有等价链路的时候，其转发概率为1(算法6至8行)。否则，首先计算第i台ToR第j条等价链路的利用率，而后用1减去链路的利用率得到链路可利用率并做归一化处理，得到等价链路上的转发概率p(i,j)(算法2至5行)。
算法2转发概率计算算法
输入:G:HWRE数据中心网络拓扑;
PM(n+1)T：第n+1个周期的流量预测矩阵；
Capj.1≤j≤J：第j条链路的容量;
J：等价链路的数量。
输出:
1) IF J >1 THEN
2) u(i,j)←CalculateUtil (G,);
//计算第i台ToR第j条等价链路的利用率
3) Ava(i,j)←1-u(i,j);
//计算链路可利用率
4)
//归一化得到转发概率
5) RETURN < p(i,j)>;
6) ELSE;
7) < p(i,j)>←1;
8) RETURN < p(i,j)>;
9) END
3 仿真分析与性能评价
本节我们在HWRE架构上提出的调度机制进行仿真实验分析。通过对比采用RED算法的传统流量调度机制，本文展示了负载均衡流量调度机制在网络吞吐量、流丢弃率方面的性能优势。此外，还分析对比不同光源部署方案对网络性能的影响。
3.1 仿真设置
网络拓扑：本文选取含有8台ToR的光电混合数据中心网络HWRE架构进行性能评价。架构中每台ToR有48个端口，其缓存为512 MB，则平均每个端口的缓存队列最大可以达到10.41 MB。每台ToR交换机分别有7个向上的端口与光路由网络互连和1个向上的端口与电分组交换网络相连，端口速率为10 Gbps。
流量模型本文根据文献[13-15]对数据中心内部流量特征的研究分析结论模拟产生数据中心集群内流量。其研究表明，企业级数据中心网络的边缘层交换机到达的活动流数量为1 000～5 000条/s。该文献还对数据中心的数据流大小进行分析，结果表明小于10 KB的数据流占总活动流数量的80%，而量大的数据被包含在少量的大数据流中。
根据上述研究，本文采用数据流层面的合成流量模型对两种调度机制进行对比分析，每种数据流所占比例如表1所示。仿真时参考文献[14]的研究结论，设置ToR交换机处活动流的数量为1 000～5 000条/秒，流的到达速率服从泊松分布，到达的间隔时间服从负指数分布，共仿真10 000个流。
表1 数据流比例分布
3.2 性能评价
本文选取网络吞吐量、流丢弃率作为性能评价指标。网络吞吐量是指在单位时间内通过网络传输并成功接收的数据总量。流丢弃率指单位时间内数据流被丢弃的比率。首先我们将负载均衡流量调度机制应用到在ToR上全部部署波长可调谐激光器的HWRE架构中，仿真对比了方案在网络吞吐量和流丢弃率上的性能优势。然后再将其分别应用到ToR上全部部署波长可调谐激光器、混合部署固定波长激光器和波长可调谐激光器，以及全部部署固定波长激光器三种情况进行性能对比，分析说明不同光源方案对网络性能的影响。混合部署的光源方案为在ToR上部署1个波长可调谐激光器和6个固定波长激光器。
图4是ToR上全部部署波长可调谐激光器作为光源的网络架构吞吐量仿真分析结果。结果表明，随着数据流到达速率不断增加，两种调度算法的网络吞吐量随之增加，负载均衡调度算法的网络吞吐量要高于传统流量调度机制，随着数据流到达速率的增大，差别越明显。当架顶交换机处的流到达速率为5 000条/秒时，负载均衡流量调度机制的网络吞吐量比传统流量调度机制的网络吞吐量高32.78%。这是由于当平均队列长度大于一定阈值时，传统流量调度机制采用随机早期检测算法按一定概率将数据流丢弃，影响了网络吞吐量。而本文负载均衡的调度算法能够根据网络的状况动态地调整各条链路上的流量分配，一定程度上避免拥塞，提高了吞吐量。
图4 网络吞吐量仿真对比
图5展示了在ToR上全部部署波长可调谐激光器作为光源的网络架构中数据流丢弃率与数据流到达速率之间的关系。随着数据流到达速率不断增加，两种算法的数据流丢弃率也不断增加。当架顶交换机处的流到达速率为5 000条/秒时，负载均衡调度机制的流丢弃率比传统流量调度机制的流丢弃率降低52.6%。其原因为负载均衡调度机制能够根据网络状态动态调整链路上负载的分配，同时利用电交换链路处理突发流量，尽可能完成数据流的转发。因此负载均衡流量调度机制下的数据流丢弃率低于传统流量调度机制下的数据流丢弃率。
图5 流丢弃率仿真对比
负载均衡流量调度机制根据网络的全局状态对流量进行调度。为了研究该机制在不同光源方案架构中的性能，本文分别针对ToR上全部部署波长可调谐激光器、混合部署固定波长激光器和波长可调谐激光器以及全部部署固定波长激光器三种情况进行仿真对比。
图6所示为负载均衡流量调度机制应用到三种不同的光源方案上的网络吞吐量仿真结果。仿真结果显示，随着数据流到达速率增加，网络吞吐量不断增加。全部部署波长可调谐激光器的网络吞吐量性能最优，混合部署波长固定和可调谐激光器的网络吞吐量性能要优于全部部署固定波长激光器。这是因为固定波长激光器的架构为各ToR之间固定地分配了链路，这导致数据流不能转发至链路拥塞最轻的链路中，降低了链路利用率，影响网络吞吐量。而全部部署波长可调谐激光器的架构则可以从全局的角度灵活调度数据流，使链路负载更均衡，提高了网络吞吐量。
图6 不同光源网络吞吐量仿真对比
图7所示为负载均衡流量调度机制应用到不同光源方案架构中的数据流丢弃率对比仿真结果。结果表明，随着流量到达速率不断增加，数据流丢弃逐渐增大。全部部署波长可调谐激光器的数据流丢弃率最小，混合部署固定波长激光器和波长可调谐激光器的数据流丢弃率低于全部部署固定波长激光器的数据流丢弃率。表明负载均衡流量调度机制应用在网络拓扑结构灵活的架构中性能更优，其原因与不同光源网络吞吐量相同。
图7 不同光源流丢弃率仿真对比
4 结 语
本文提出了一种面向光电混合数据中心网络架构HWRE的流量调度机制——负载均衡流量调度机制。该机制通过SDN控制器对数据流量进行周期性统计，建立流量预测矩阵。根据流量预测矩阵计算出每条等价链路的利用率并对其进行相应处理，得到每条等价链路上数据流的转发概率，新的数据流按照此概率完成转发。本文通过建立合成流量模型对软件定义流量调度机制进行性能评价。仿真结果表明，相比较传统的RED流量调度机制算法，该调度机制能够提高数据中心网络的吞吐量，降低数据流丢弃率。同时，当该机制应用于波长可调谐的光源架构中时，其性能表现更优。
[1] Chen Y,Jain S,Adhikari V K,et al.A first look at inter-data center traffic characteristics via yahoo! datasets[C]//INFOCOM,2011 Proceedings IEEE.IEEE,2011:1620-1628.
[2] Armbrust,Michael,Fox,et al.Above the Clouds:A Berkeley View of Cloud Computing[J].Eecs Department University of California Berkeley,2009,53(4):50-58.
[3] Al-Fares M,Loukissas A,Vahdat A.A scalable,commodity data center network architecture[J].ACM SIGCOMM Computer Communication Review.ACM,2008,38(4):63-74.
[4] Farrington N,Porter G,Radhakrishnan S,et al.Helios:a hybrid electrical/optical switch architecture for modular data centers[J].ACM SIGCOMM Computer Communication Review,2010,40(4):339-350.
[5] Han QI,Muhammad SHIRAZ,Jie-Yao LIU,et al.Data Center Network Architecture in Cloud Computing:A Taxonomy and Review[J].Zhejiang University-SCIENCE C (Computers & Electronics),2014,15:776.
[6] Guo C,Lu G,Li D,et al.BCube:a high performance,server-centric network architecture for modular data centers[J].ACM SIGCOMM Computer Communication Review,2009,39(4):63-74.
[7] Guo C,Wu H,Tan K,et al.Dcell:a scalable and fault-tolerant network structure for data centers[J].ACM SIGCOMM Computer Communication Review.ACM,2008,38(4):75-86.
[8] Cai Yueping,Zhou Li,Yan Yao.Software Defined Data Center Network Architecture with Hybrid Optical Wavelength Routing and Electrical Packet Switching[C]//Proceedings of the Optoelectronics and Communications Conference (OECC’14),Melbourne,Australia,Jul 6-10,2014:682-684.
[9] Cai Yueping,Yan Yao,Zhou Li,et al.Architecture Design of AWGR-based Data Center Network with Hybrid Optical Wavelength Routing and Electrical Packet Switching [C]//Proceedings of the 3nd CCF Internet Conference of China (CCF ICoC’13),Shanghai,China,Jul 9-10,2013.
[10] Farrington N,Porter G,Radhakrishnan S,et al.Helios:a hybrid electrical/optical switch architecture for modular data centers[J].ACM SIGCOMM Computer Communication Review,2010,40(4):339-350.
[11] Wang G,Andersen D G,Kaminsky M,et al.c-Through:Part-time optics in data centers[C]//ACM SIGCOMM Computer Communication Review.ACM,2010,40(4):327-338.
[12] Maier M,Scheutzow M,Reisslein M.The arrayed-waveguide grating-based single-hop WDM network: an architecture for efficient multicasting[J].IEEE Journal on Selected Areas in Communications,2003,21(21):1414-1432.
[13] Benson T,Anand A,Akella A,et al.MicroTE:Fine grained traffic engineering for data centers[C]//Proceedings of the Seventh COnference on emerging Networking EXperiments and Technologies.ACM,2011:8.Centers.Proceedings of ACM SIGCOMM.
[14] Ye X,Yin Y,Yoo S J B,et al.DOS:A scalable optical switch for datacenters[C]//Proceedings of the 6th ACM/IEEE Symposium on Architectures for Networking and Communications Systems.ACM,2010:24.
[15] Yin Y,Proietti R,Ye X,et al.LIONS:An AWGR-based low-latency optical switch for high-performance computing and data centers[J].IEEE Journal of Selected Topics in Quantum Electronics,2013,19(2):3600409-3600409.
[16] 蔡岳平,晏尧,周丽,等.基于AWGR的光电混合数据中心网络架构设计[J].计算机科学与探索,2014,8(10):1195-1205.
[17] Benson T,Akella A,Maltz D A.Network traffic characteristics of data centers in the wild[C]//Proceedings of the 10th ACM SIGCOMM conference on Internet measurement.ACM,2010:267-280.
[18] Kandula S,Sengupta S,Greenberg A,et al.The nature of data center traffic:measurements & analysis[C]//Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference.ACM,2009:202-208.
[19] Floyd S,Jacobson V.Random early detection gateways for congestion avoidance[J].IEEE/ACM Transactions on networking,1993,1(4):397-413.
[20] Benson T,Anand A,Akella A,et al.Understanding data center traffic characteristics[J].ACM SIGCOMM Computer Communication Review,2010,40(1):92-99.
LOADBALANCETRAFFICSCHEDULINGMECHANISMINANOPTICAL-ELECTRICALHYBRIDDATACENTERNETWORK
Cai Yueping Fan Xinwei Wang Changping
(CollegeofCommunicationEngineering,ChongqingUniversity,Chongqing400030,China)
Using traditional RED traffic scheduling mechanism, optical-electrical hybrid data center network is likely to cause data loss. And the choice of equal cost forwarding path is random. So we proposed a software-defined load balance traffic scheduling mechanism based on traffic prediction matrix. The mechanism uses software to define the network, which has the advantages of a global perspective, and periodic statistics of network traffic. Through this mechanism, traffic prediction matrix calculates the forwarding probability of the data stream with multiple equal links and completes the next cycle of forwarding according to this probability. Meanwhile, we use the electrical exchange link to deal with burst traffic alone to improve network throughput and achieve network load balancing. In this paper, a synthetic flow model is established on the topology of optoelectronic hybrid data center network for simulation experiment and performance analysis. The proposed mechanism can efficiently improve network throughput and reduce data loss rate.
Optical-electrical hybrid data centre network architecture Software-defined Routing algorithm Load balance
2016-10-08。国家自然科学基金项目(61301119)；教育部留学归国人员启动基金项目(1020607820140002)。蔡岳平，副教授，主研领域：云计算数据中心网络，光通信网络，软件定义网络和未来互联网。樊欣唯，硕士生。王昌平，硕士生。
TP3
A
10.3969/j.issn.1000-386x.2017.08.026
