软件定义网络架构下基于流调度代价的数据中心网络拥塞控制路由算法
时间：2022-07-14 10:33:05
摘要：针对传统数据中心网络极易发生拥塞的问题，提出了在软件定义网络（SDN）的架构下设计基于流调度代价的拥塞控制路由算法加以解决。首先，进行拥塞链路上的大小流区分，并对所有大流的各条等价路径进行路径开销权重的计算，选择权重最小的路径作为可用调度路径；然后，使用调度后路径开销变化量和流占用带宽比例来共同定义流调度代价；最终选择调度代价最小的流进行调度。仿真结果表明，所提算法能在网络发生拥塞时降低了拥塞链路上的负荷，并且与仅进行流路径选择的拥塞控制算法相比，提高了链路利用率，减少了流传输时间，使得网络链路资源得到更好的利用。
关键词：
中图分类号： TP393.2 文献标志码：A
0引言
传统的数据中心网络属于访问式网络，其业务流量大部分都是客户端与数据中心内部的被请求服务器之间的“南北流量”[1]。然而，随着Map Reduce应用、虚拟机迁移以及其他带宽密集型应用等的发展，数据中心服务器内部通信增多，一对多、多对一、多对多等集群通信模式[2]带来了服务器间横向流量的显著增长。随之而来的问题是，数据中心网络内部原有带宽已不能满足横向流量的传输需求，相应链路面临极高的拥塞风险。加之传统网络结构复杂，路由算法大多采用分布式部署，造成拥塞控制算法的设计极为困难。不过，随着软件定义网络（Software Defined Network， SDN）技术的出现和发展，数据中心网络的拥塞控制出现转机。SDN架构将数据层和控制层抽象分离[3]，利用控制层的控制器对网络进行集中管理，保存全网网络状态视图，为算法设计提供了巨大便利。同时，SDN中数据转发颗粒度为流，可以通过路由对流进行调度，从而解决网络拥塞问题，因此，越来越多的研究关注SDN中通过路由算法的设计来进行拥塞控制[4]。
在使用路由应对SDN数据中心网络拥塞问题的方法中，基本思路是在网络拥塞发生时通过对流重新选路来将流从拥塞链路调度到轻负载链路以缓解网络拥塞，即拥塞控制路由[5-7]。而拥塞控制路由主要有主备路径路由和动态重路由两种机制。主备路径路由机制是指流进入网络后为其安装两条路径，在链路拥塞时能够使流从主路径快速切换到备用路径，但是备用路径不仅会消耗流表的存储资源，而且也不具备时效性，在网络发生拥塞时很可能已不满足当前控制需要。而动态重路由机制能更好地利用SDN控制器具有全网网络状态信息视图的优势，对拥塞进行实时控制，因此，国内外拥塞控制路由方案的设计主要集中在基于动态重路由的流调度。
基于动态重路由的流调度包括两方面内容：一是对哪一条流进行重路由；二是如何对流进行重路由。在对哪条流进行重路由的问题上，考虑到数据中心网络中混合了不同业务流量，表现出明显的大象流和老鼠流[8]的大小流特征，而小流量因为持续时间相对较短，改变其路径极有可能会增加时延和开销，所以在链路拥塞时主要通过迁移大流量来实施调度。文献[9]和文献[10]都是在数据中心网络流量达到调度条件时选择大流量进行调度，提高了重路由的有效性。文献[9]是在链路达到拥塞门限值后进行的调度，文献[10]则是针对全网设置了全局负载均衡参数，当参数达到门限值后进行调度，但是它们都没有对所调度的大流量的选择作进一步研究，这难以保证所选流量是最优调度对象。因为相同路径上的多条流在重路由时，调度到相同的链路概率非常大，仍然容易产生新的拥塞问题。而在对流的重路由路径选择问题上，文献[11]和[12]都采用了链路剩余容量作为权重来选择路径，但未考虑链路的实际路由开销会降低调度效率这一因素。
针对上述动态重路由算法的一些不足，本文提出了一种基于流调度代价最小的拥塞控制路由算法，用于解决采用软件定义网络架构的新型数据中心网络拥塞问题。
1基于流调度代价的拥塞控制路由算法
1.1路由算法机制
基于流调度代价最小的拥塞控制路由算法在设计时重点考虑了适合进行调度的大流的二次选择，以及调度后路径开销和链路带宽情况，其主要思想如下：
1）在对拥塞链路上的流进行大小流区分之后，对所有大流的各条等价调度路径进行路径开销的计算，最终选择开销最小的路径作为可用调度路径，以保障调度路径上每条链路具有充足的带宽，实现最优调度路径的选择。
2）引入调度代价来权衡网络稳定性和网络链路利用率，使用调度后路径开销变化量和流占用可用带宽比例来共同定义流调度代价，最终选择调度代价最小的流进行调度。
具体拥塞控制路由机制如图1所示。
考虑到该拥塞控制路由算法是基于现有路由器的控制功能来完成的，为了与其兼容，并在不发生网络链路拥塞的情况下使原有路由功能仍然可以发挥较好作用，所以在路由机制中保留了路由初始化这一环节。而且，链路拥塞判断也需要有一个初始化的路由表来统计链路上的相应信息并作后续处理。所以，图1中，当控制器收到Packagein消息后，仍然会进行路由初始计算，一般以最短路径为初始路由，并向相关交换机下发流表项。然后，控制器通过周期性发送StateRequest消息问询交换机及其端口的状态来对所有链路进行流量监控；同时进行拥塞判断。当发现链路负载大于拥塞门限值时，启动动态重路由。
动态重路由首先对拥塞链路上所有流进行大小流分类。考虑到小数据流占用带宽小、持续时间短和对时延敏感的特性，不宜对其进行调度，因此，选择大数据流进行重路由计算，选择路径开销最小的路径。
在多条大数据流中，还要对等待调度的流进行再次选择，即选出目标流，使得拥塞链路的负载减轻的同时，提高网络的链路利用率。本文中使用调度代价对拥塞链路上的大数据流进行判断，选择最小的调度代价的数据进行调度。
最后删除交换机中的原流表项，同时下发新的流表项。
1.2路由算法实现
1.2.1算法模型
网络描述：给定数据中心网络G=（V，E），其中：V为非空节点集，代表网络节点集合；而E为边集，代表网络所有节点的链路集合，而每一链路e∈E有一固定开销w。另外，定义P为源节点s∈V到目的节点d∈V的路径集，其中第i条路径用pi=ei1 ei2 … eiK，而eijj=1，2，…，K表示第i条路径pi的第j条链路。
链路利用率链路eij∈E的实时带宽利用率ηij定义为链路已占用带宽与该链路的总容量之比，如式（1）所示：
ηij=loadij/Bij×100%（1）
其中：Bij表示链路带宽容量，即最大传输速率；而loadij则表示链路上的负载大小，即已被占用的带宽。
1.2.2算法流程
于是基于流调度代价最小的拥塞控制路由算法可表示如下。
2算法性能仿真分析
2.1仿真环境搭建
实验采用Mininet+Ryu的仿真平台。Mininet是一款基于Linux Container架构开发的功能强大的轻量级软件定义网络仿真及测试平台，利用它可以模拟出包括主机、链路和交换机在内的完整数据中心网络[13]。而Ryu则是SDN中常用的开源控制器模块[14]。此外，网络中的交换机选用OpenvSwitch交换机。本文利用Python自定义编写了如图2所示的数据中心网络中广泛使用的FatTree拓扑，拓扑包括两台核心层交换机（交换机1和交换机2），8台的聚合层交换机和边缘层交换机（交换机3，交换机4，…，交换机10），而每4个聚合层交换机或边缘层交换机组成一个Pod。
为实现控制器的路由及拥塞控制动态路由，在Ryu中添加了拓扑发现模块、流量监测模块、路由模块、拥塞控制重路由模块及流表项管理模块来完成算法功能，所需模块结构如图3所示。其中，拓扑发现模块获取算法中路由及流量监控所需的网络拓扑结构和链路连接接口信息。监控模块主要是对控制器控制下的交换机进行流量监控，统计并存储；同时对链路状态进行判断，当发生链路拥塞时，触发拥塞控制重路由机制，并将网络信息传给重路由模块（Rerouting Engine）进行路径计算和选流判断。路由模块在流刚进入网络时用于初始路径的计算，动态路由模块周期性地检测所用链路的拥塞情况，当任何一条链路的负载超过拥塞门限值时，将会对该链路上的一条或多条链路进行重路由。
实验环境搭建中，流量的设置模拟了数据中心高动态流量特性下发生拥塞后的情况，设置为Pod1和Pod2之间互相发送流，数据包数量、大小、发包间隔相同，流的目的端随机。实验搭建平台为笔记本一台（Inter Core i7 4710、8GB），受条件限制，网络运行规模较小，但两个Pod之间的通信链路数量与具有4个核心交换机的情况下是一致的，仍然具有4条可用链路，拥塞发生时依旧可利用其多路径的特性实施算法。同时由于数据包的发包速率受限，本文未按一般数据中心链路容量进行链路设置，而保持交换机端口速率为160Kb/s。所以在算法仿真验证中，取20Kb/s作为大小流区分的阈值。另外，为了在流调度时优先考虑链路的使用效率，取α=0.5， β=1。
2.2仿真结果及分析
首先，为了验证算法实施后缓解链路拥塞的有效性，本文对两条链路的链路使用情况进行了考察：一条是比较繁忙的链路1（即图2中交换机1到交换机3的链路）；另一条是负载相对较轻的链路2（即图2中交换机1到交换机4的链路）。如图4所示，链路1在网络运行刚开始时链路利用率不断上涨，到达峰值97%，超过90%的门限值，处于拥塞的状态，之后算法开始作用。链路2在30s左右才逐渐有负载，但链路1的拥塞并没有得到立刻缓解，原因是拥塞链路上转移的流的数目和大小没有能使链路1上的负载降低到门限值以下。随着链路1上的流不断转移到包括链路2在内的其他链路上，链路1到了60s以后拥塞情况得到缓解，一直低于门限值，处于平稳状态。
为观察算法在数据中心网络高动态流量模式下缓解链路拥塞的同时提高网络链路利用率的性能，将本文提出的拥塞控制路由算法和仅对流的路径进行选择的非拥塞控制路由算法在网络链路利用率和流量传输时间上进行了对比，链路利用率对比如图5所示，传输时间如图6所示。
由于流的数量较少，在实验中整个网络的链路利用率并不高，最大只有45%左右。由图5可以看出，在各个主机开始发送数据包时，链路利用率逐渐上升，而且刚开始时利用率增长速度非常快，在30s左右增速放缓，网络发生拥塞。到70s左右，拥塞解决后链路利用率达到最高，之后本文提出的算法链路利用率一直保持在40%到46%，而仅对流的路径进行选择的非拥塞控制路由算法链路利用率在37%到43%。图6是每个主机传送整个数据流所用的时间对比此外，将主机1至主机8各自要进行传输的数据流定义为流1至流8，然后在图6中得到了每个主机传输各自数据流所用的时间对比，由图6可看出，本文算法中所有流的平均传输时间低于没有进行流选择的算法10%左右。
综上所述，本文算法在网络链路达到门限值后，能对拥塞链路上的流进行调度，以减缓拥塞，使得链路负载低于门限值，同时通过对流的路径的选择及对所需调度的流的选择，使得网络链路资源得到更好的利用。
3结语
本文针对现有SDN数据中心网络拥塞控制路由算法在区分大小流之后没有对所要调度的大流进行更加合理的选择而导致新的拥塞问题的缺陷，提出了一种基流调度代价最小化的拥塞控制算法，并对其进行仿真验证。仿真结果表明，本文算法能实现对流最优调度路径的选择，并且在调度流的选择过程中，考虑了网络稳定性和网络链路利用率，有效地对拥塞链路进行调度以缓解拥塞情况，并且在链路利用率和传输效率方面有所提升，使得网络链路资源得到更好的利用。然而，重路由的方法较多，本文采取的是全路径路由，并没有考虑到局部路由的情况。同时，在链路过于拥挤时，理论上一次性调度多条流可以提高拥塞缓解效率，而本文没有考虑此种情况。最后，任何动态的拥塞控制路由算法都会随着所处网络规模的扩大而增加算法的复杂度，会给控制器和网络链路传输造成额外负担，这都需要一个量化的分析来体现算法的应用有效性，因此，接下来会针对上述问题作进一步研究。
参考文献：
[1]
邓罡，龚正虎，王宏.现代数据中心网络特征研究[J].计算机研究与发展，2014，51（2）：395-407.（DENG G， GONG Z H， WANG H. Characteristics research on modern data center network [J]. Journal of Computer Research and Development， 2014， 51（2）： 395-407.）
[2]
魏祥麟，陈鸣，范建华，等.数据中心网络的体系结构[J].软件学报，2013，24（2）：295-316.（WEI X L， CHEN M， FAN J H， et al. Architecture of the data center network [J]. Journal of Software， 2013， 24（2）： 295-316.）
[3]
张鹏.SDN：IP网络定制化时代到来[J].通信世界，2013（10）：45-46.（ZHANG P. SDN： the age of customized IP network is coming [J]. Communications World Weekly， 2013（10）： 45-46.）
[4]
樊自甫，伍春玲，王金红.基于SDN架构的数据中心网络路由算法需求分析[J].电信科学，2015，31（2）：42-51.（FAN Z F， WU C L， WANG J H. Requirements analysis of data center network routing algorithm based on SDN architecture [J]. Telecommunications Science， 2015， 31（2）： 42-51.）
[5]
张朝昆，崔勇，唐Gt，等.软件定义网络（SDN）研究进展[J].软件学报，2015，26（1）：62-81.（ZHANG C K， CUI Y， TANG H Y， et al. Stateoftheart survey on softwaredefined networking （SDN） [J]. Journal of Software， 2015， 26（1）： 62-81.）
[6]
ALFARES M， LOUKISSAS A， VAHDAT A. A scalable， commodity data center network architecture [C]// SIGCOMM’08： Proceedings of the 2008 ACM SIGCOMM Conference on Data Communication. New York： ACM， 2008： 63-74.
[7]
GREENBERG A， HAMILTON J R， JAIN N， et a1. VI2： a scalable and flexible data center network [C]// SIGCOMM’09： Proceedings of the 2009 ACM SIGCOMM 2009 Conference on Data Communication. New York： ACM， 2009： 51-62.
[8]
KANDULA S， SENGUPTA S， GREENBERG A， et al. The nature of datacenter traffic： measurements and analysis [C]// IMC’09： Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement Conference. New York： ACM， 2009： 202-208.
[9]
KANAGAVELU R， MINGJIE L N， AUNG K M， et al. OpenFlow based control for rerouting with differentiated flows in data center networks [C]// Proceedings of the 2012 18th IEEE International Conference on Networks. Piscataway， NJ： IEEE， 2012： 228-233.
[10]
KANAGAVELU R， LEE B S， MIGUEL R F， et al. Software defined network based adaptive routing for data replication in data center [C]// Proceedings of the 2013 19th IEEE International Conference on Networks. Piscataway， NJ： IEEE， 2013： 1-6.
[11]
SHINOHARA Y， CHIBA Y， SHIMONISHI H. An adaptive multipath routing algorithm for maximizing flow throughputs [C]// Proceedings of the 2012 World Telecommunications Congress. Piscataway， NJ： IEEE， 2012： 1-6.
[12]
LONG H， SHEN Y， GUO M Y， et al. LABERIO： dynamic loadbalanced routing in OpenFlowenabled networks [C]// Proceedings of the 2013 IEEE 27th International Conference on Advanced Information Networking and Applications. Piscataway， NJ： IEEE， 2013： 290-29.
[13]
Open Network Foundation. OpenFlow switch specification version 1.3.4 [EB/OL]. [20160315]. https：//images/stories/downloads/sdnresources/onfspecifications/openflow/openflowswitchv1.3.4.pdf.
[14]
Nippon Telegraph and Telephone Corporation. Welcome to RYU the Network Operating System （NOS） [EB/OL]. [20160315]. http：///en/latest.
