基于SDN的流量控制算法综述*

阳 凯，林海涛，黎海雪

（海军工程大学 电子工程学院，湖北 武汉 430000）

0 引 言

近年来，网络的发展趋于扁平化，SDN的理念得到了业界的广泛关注和认可。SDN架构将交换机的控制功能和转发功能分离开来，分成集中控制平面和数据转发平面。根据SDN的专利统计，基于OpenFlow技术的申请量占总申请量的84%[1]。通过OpenFlow协议，可对不同交换机和路由器的流表进行修改，控制每一条数据流的流向，根据需求实现特殊的功能。

1 基于SDN的网络流量控制基本机理

基于OpenFlow协议的SDN网络架构由控制器和交换机组成。控制器运行路由算法，计算数据流最佳路由，实现流表的生成、维护和下发。控制器决定了数据的转发策略，交换机只按照流表执行转发。

现有的流量控制算法从不同角度有不同的分类。本文基于网络性能的优化目标不同进行分类：（1）以负载均衡为目标；（2）以保证流QoS为目标；（3）以降低控制器的开销为目标。三者之间并非界限分明，而是相互联系，若网络达到负载均衡，则网络整体QoS会得到提升。但是，三者之间又并非完全并行不悖，若达到全局路由优化和负载均衡，往往会增加控制器负担和开销。

2 基于负载均衡的流量控制算法

SDN的流量负载均衡性能关系到网络的稳定性和可用性。良好的负载均衡能够增加吞吐量，平衡设备负荷，控制拥塞，提高网络的灵活性。

2.1 最短路径算法

最短路径算法始终以寻求最短的转发路径为准则。现有的主流SDN控制器，采用的是Dijkstra[2]算法，但Dijkstra算法只能计算出单条最短路径。K最短路径算法在最短路径算法基础上进行了拓展，为数据流计算出K条最短路径，其中Yen算法就是一种K最短路径算法。A*算法是解决静态路由网络最短路径的最有效的直接搜索方法。吕启迪[3]采用A*算法和Yen算法实现了单流寻路和冗余路径流寻路，提高了底层网络资源的利用率。

最短路径算法是一种简单的路由机制，难以达到通信量和网络负载的均衡，容错能力较差。

2.2 路径分离算法

路径分离算法是在源节点和目的节点之间寻找满足一定QoS约束的分离路径。当主用路径出现故障时，将承载的业务流转换到备用路径上，以实现快速的业务恢复[4]。链路分离路径能够提高网络的可靠性，减少网络拥塞，并在路径冗余中实现网络的负载均衡。池亚平等[5]改进了Dijkstra算法，并且与分离路径算法相结合，为网络提供了多条可靠路径，提高了网络的鲁棒性。

链路分离路径算法可以计算出多条没有共用链路的路径，将其与SDN的灵活性和细粒度控制特性相结合，可以为不同服务质量的业务提供不同的路径，或为同一类型的业务提供多条路径。

2.3 多路径路由算法

多路径路由算法是根据网络的拥塞程度调整每条路径的使用，如分配流量和平衡网络负载，从而提高网络的利用率。

等价多路由[6]（Equal-Cost Multipath Routing，ECMP）可以增加网络的传输带宽，在等值情况下实现多路径负载均衡和链路备份。LIU J[7]通过控制器识别长流、计算长流ECMP，最后将长流数据包调度到多条路径上传输。加权多路径（Weight-Cost Multipath Routing，WCMP）能够灵活地按照比例在链路上传递流量，其中ECMP是它的特例。在多路径具有同等带宽、时延和可靠性等属性时，ECMP可以部署，但是由于缺乏流量分类功能，无法实现业务的控制。利用哈希算法可以使流量分配扁平化，文献[8-9]分别利用Hash技术将单个数据流分布在多个可用路径上。Hedera[10]先基于哈希算法选择一条等价路由，当网络中的流量增大到门限时，重新计算适合的路径，动态地估测了大象流[10]的需求带宽。但是，Hash运算可能出现“冲突”，造成网络拥塞。彭大芹[11]将大象流根据路径权重值进行路由，而老鼠流[10]选择可用剩余带宽最大的路径作为其路由路径。

多路径广泛存在，传统的类似于ECMP的流量调度方法存在大象流碰撞问题，收敛速度也较慢。粒子群优化算法（Particle Swarm Optimization，PSO）不要求被优化函数具有可微、可导以及连续等性质，收敛速度较快，可避免大流的拥塞。文献[12]给出了一种带收敛因子的PSO算法，文献[13]通过收集邻域的拓扑来提高PSO算法的收敛性能，文献[14]将人工蜂群算法和PSO算法结合，提高了算法的收敛性能。除了具备更好的收敛性，计算流量转发最优路径也是PSO算法的应用热点。文献[15]结合动态邻域信息进行PSO优化，求解多个路径优化目标。文献[16]使用改进的PSO计算网络流的最优路径，从而避免网络拥塞，并在转发层使用分层令牌桶（Hierarchical Token Bucket，HTB）调度算法提高网络的服务质量。文献[17]应用PSO算法对网络的负载均衡问题进行相关优化。由于PSO对具有多个局部极值点的函数容易陷入局部极值点中，导致后期搜索的收敛性变差，准确度变低。应用到现实网络中，PSO算法一般适用于相对独立的网络且对网络资源优化的要求不高的情形。

2.4 轮询算法

轮询算法通常不考虑瞬时链路状态，使用户轮流使用共享资源。从为每个通信链路分配相同数量的资源的角度讲，轮询可以被视为公平调度的一种算法。然而，从为所有通信链路提供相同服务质量的角度来看，轮询调度是不公平的，因为往往好信道的链路会承担更多的业务应用。包轮询算法可以确保每条路径上的转发包数基本相同[18]，从平均分配负荷角度做到了简单的网络均衡。但是，即使是文献[19]中改进后的差额轮询算法，也无法避免数据包乱序到达产生的链路拥塞问题。

2.5 权重算法

从不同参数重要性的角度考虑，可以得到偏向权重的特定性能网络，这就是权重算法的基本思路。可考虑的权重因子有链路、带宽、时延、丢包率等。权重算法往往是在已有路由算法的基础上，为某一或某些网络参数进行加权计算和决策评价，通过增加加权参数数量，实现对网络路由更细化的设计，从而达到对网络资源的合理调配。

黄婧洁[20]先利用遗传算法求解链路最优权值的设置方案调整链路的权值，再基于最短路径算法优化网络路由。祝烈煌[21]考虑了转发路径的可用带宽、丢包率、延迟、交换机无效服务率以及路由长度，综合做出路由决策。与Dijkstra算法相比，这些方案提高了数据交付效率。Guo Y[22]通过动态分配权值减轻SDN交换机和普通交换机混合网络中局部拥塞路径，提高了全网的工作效率。

但是，权重算法自适应性不足，对网络运行状态的反应较为迟滞。随着网络状态的变化，如果权值的计算和更新不及时，网络性能将会受到不当权值的影响。吴杰[23]根据SDN控制器的全局特性定期更新链路状态，从而更新路径权值，具备一定的自适应性，能进一步提高网络吞吐量。

2.6 评估算法

评估算法根据收集和计算得到网络中某些参数值，并对其进行统计评估，以此评估值为标准来反馈和调整流量控制。

文献[24]根据链路的预期平均负载判定链路的关键性，然后将其映射为链路权重，为路由选择提供数据基础来实现对网络流量的负载均衡。文献[25]以多路径瓶颈带宽为评估对象，通过当前交换机节点和链路负载情况，选择最符合数据流传输需求的路径。文献[26]根据网络节点负载、链路负载和数据包大小进行自适应评估，计算过程中更新路径表，可提高全网数据传输效率和吞吐量。刘杰民[27]将影响路径质量的参数拟合为关于路径平均吞吐量的函数，根据路径平均吞吐量衡量和执行数据调度，一定程度上减少了不必要的快速重传问题。文献[28]兼顾数据流的业务属性和流量分布属性，以流量转移代价为评估标准，选择转移代价最小的数据流进行调度。

评估算法可以着重对某一网络特性进行突出优化，实现特定需求的网络，但往往以牺牲其他性能作为代价。

2.7 拥塞控制算法

控制拥塞是设计负载均衡路由算法的基本思路和基础要求。网络的拥塞控制和路径的优化、网络吞吐量的增加往往是正相关的。

庞博等[29]以最小化传输延迟为目标，对数据层中的链路资源进行网络切片，通过整数线性规划求解最佳路由，以避免拥塞。樊自甫等[30]先判别拥塞链路中链路上关键度最大的大流进行重路由，再选择调度开销最小的流进行调度代价计算，最后对调度代价最小的流进行调度，达到缓解网络拥塞的目的。类似的，Hui L等[31]提出一种拥塞避免机制，但准确性较差、灵敏度不高。吴志强等人[32]依据拥塞节点的上一跳节点进行重路由来控制拥塞，但浪费了大量的网络资源。Lu L等人[33]针对不同的拥塞情况采用不同的重路由策略，但是使用的是以终端进行拥塞管理的思想，信令开销较大，不利于提升网络性能。

良好的流量控制算法必须在满足网络特定需求的同时，具有良好的拥塞控制。然而，引起网络拥塞的原因是复杂的、多方面的，需要综合考虑和设计。

2.8 全局优化算法

传统的SDN算法往往并不能利用全局视图达到流量控制的全局优化，容易陷入局部优化的境地。大型网络环境中，往往追求的是全网整体的性能最优，这就启发人们将全局优化算法应用到SDN流量控制中。

多商品流算法是为所有业务寻找合适的路径，优化目标是所有业务的流量总代价之和。赵笑楠[34]提出了基于多商品流算法的精细化流量控制方法。Yu M等[35]基于多商品流思想，结合PSO算法，实现了便捷高效的精确查找最优路径。文献[36]在Floodlight控制器中使用广度优先搜索算法代替最短路径优先算法实现全局最优的路径搜索。魏凯[37]根据控制器提供的实时网络负载情况，利用蚁群算法计算最小负载的链路，从而给交换机动态地提供数据流转发策略。李宏慧等[38]通过重定义蚁群算法的参数和操作求解整数线性规划模型，得到大象流重路由的最优路径。王文涛[39]基于模拟退火遗传算法建立了按需自适应的流量调度机制，达到了网络带宽资源优化分配的目的。文献[40]结合遗传算法（GA）和模拟退火算法（SA）提出了SAGA路径搜索算法，根据链路带宽资源状况搜索流的调度路径，达到了负载均衡的目的。

全局优化算法相对于传统的局部优化算法具有明显优势，可以得到从全局衡量的最优流量控制效果。但是，全局优化算法需要实时更新全局拓扑信息并获得全网性能数据，同时进行流量控制转发策略计算。这不但会产生一定的开销占用资源，也增加了控制器的负荷，同时会加大网络控制的时延。因此，如何协调好延时增大与控制效果更好之间的矛盾，是全局优化算法需要解决的问题。

3 基于QoS的流量控制算法

当网络发生拥塞时，所有的数据流都有可能被丢弃，网络必须根据业务的需求分配和调度资源，并为不同的数据流提供不同的QoS。具备QoS功能的网络，能够有效分配网络带宽，更加合理地利用网络资源。

通常，网络中的流量可分为两类：一类是持续时间较长、带宽需求较高的大象流；另一类是持续时间较短、带宽需求较低的老鼠流。在实际的网络中，大象流的占比小于10%，却承载了80%的流量[10]。Hedera[10]关注通过边界交换机的大象流，根据全局流量请求为数据流计算冲突路径，为超过特定速率的流预估数据传输请求量，并计算最优路径。但是，与全局优化算法类似，实时针对每个流进行统计和大象流检测，会增加交换机的负担。Mahout[40]通过设定终端缓存阈值标记大象流，利用控制器对大象流计算特定的转发策略。类似的，文献[41]利用网络中的剩余带宽来缓解利用率过高造成的链路性能损失。这些方法欠缺对网络状态变化的考虑，或者仅仅考虑了有限的最短路径方案，没有充分利用拓扑中路径的多样性。庄怀东[42]利用多商品流思想对大象流的分布进行建模，并通过粒子群算法求解全局最优值为大象流选择路径。以上是以流的大小和链路带宽进行路由计算度量的，而阳利[43]以获取的实时链路时延、网络整体吞吐量和丢包率三个性能指标，为大象流和老鼠流分别进行路由计算度量。该方案与ECMP、Hedera相比，进一步提高了网络吞吐量和链路利用率。由于根据链路实时状态进行路由计算始终会滞后于网络的变化，文献[44]根据媒体生产网络中网络流量可以预测的特点，预留带宽，以达到提高资源利用率和节约成本的目的。

以带宽为主设计QoS是常用策略，而针对视频等时延敏感的业务，需要以时延为主进行QoS策略设计。文献[45]优先选择具有最小时延的传输路径进行传输，之后待发送的数据选择具有第二时延小的路径，依次重复以上过程，直至数据发送完毕。

SDN中需要保障的QoS业务有多种，对于多业务服务质量的综合保障更符合实际需求。Lu Y等[46]先对网络拓扑进行切片，而后对不同路由、带宽、容量的网络节点制定不同的转发策略，最后在切片内尽力而为地以最小代价、最大流量进行转发，满足各种QoS要求。孙志等[47]通过识别和映射服务流的多维属性，提出了基于业务流综合优先权（Priority Based QoS，PriQoS）策略，根据该优先权控制边界交换机上的带宽资源。文献[48]基于云用户优先级和应用类型建立带宽保证资源分配机制，将业务流分为QoS流和尽力而为的流，而QoS流的路由选择考虑了带宽、时延和路径长度。类似地，Tomovic等[49]提出了QoS-aware算法。

基于QoS的算法具有很强的业务流量针对性。和评估算法类似，以保证QoS为目标的算法通常以QoS业务为对象、以业务需求为目标建立目标函数和模型，计算最佳的流量调度策略。

4 基于降低开销的流量控制算法

由于SDN中由控制器对数据流进行集中的转发规则计算和管理，单个控制器很可能成为网络的性能瓶颈。以现有NOX控制器为例，每秒处理不超过3×104个流的初始化，每个流表的安装时间约为10 ms[50]。控制器的处理能力是有限的，除去从网络结构布局上进行优化外，从算法上减少控制器开销成为业界研究的重点方向。

合理的流表分配可以减少网络资源的耗费，降低流表转发时延，提高交换机吞吐量，从而提升网络流量转发性能。Zhang等[51]通过混合路由极大地减少流表项的使用，同时为多个流量矩阵实现负载均衡。为解决交换机流表资源和控制器计算资源有限的问题，文献[25]结合网络运行状态和数据流特性，引入流表资源代价、计算资源代价和资源偏好度等指标来优化分配流表。为了增强调整流表的自适应性，王勇等[52]根据全部流表中活动流表项所占的比重，实时调整响应流表项的生存时间和优先级来提高流表的匹配命中率，并降低转发时延。类似的，文献[53]提出了一种流表自动控制机制来解决大数据流下交换机的拥塞和可用问题，预测流表变化功能的网络，增强优化流表的匹配性，以获得最及时的流控效果。文献[54-55]提出了通过收集单位时间内新增的流表条目数量来预测下一时刻新增的流表项数，据此计算调整因子来动态调整流条目的停滞超时时长。文献[56]用AR算法[57]分析单次输入流的到达数量来预测下一个周期的流数量，并用威布尔分布[58]估算下一取样周期中尚存的流表项数量，以此调整下一周期流表分配策略。文献[59]通过分析流表的使用情况和流到达特征，预测活动流表项的数量和失效时间，自适应调整流表项默认停滞超时时长，并更新新流的停滞超时时长。为了更充分利用有限的流表资源，文献[60]设置流停滞超时登记模块动态调整停滞超时时间，反馈控制模块动态调整流表项最大停滞超时时间，达到减少流表溢出的目的。然而，增加模块加重了控制器的负载，降低了系统性能。以上方法要求控制器实时分析预测输入流分布，对控制器提出了较高要求。

除优化流表分配方法外，还有其他一些降低控制器开销的方法，如改变节点交换机权重，对业务进行迁移达到负载均衡等。文献[61]通过分析触发学习机制后各节点转发状态的变化，提出了基于Dyna agent算法的控制器控制策略，以改善网络资源利用率。文献[62]以网络中任意两节点的通信过程建立Markov模型，通过多步转移概率计算网络节点间各链路权重，以控制交换机和控制器负载，达到负载均衡。

5 流量控制算法的研究趋势

传统的策略路由通过多策略路由表和多转发表实现了对报文路由方式的控制，能够实现流量的分类和传递，但是无法在不同端口、不同路径上实现同一种业务的流量分配，而SDN的出现实现了这一点。SDN的流量控制算法发展到现在，经历了由单路由到多路由、由简单到复杂、由静态到动态、由局部优化到全局优化、由非自适应到自适应的过程。最初，SDN静态的选路算法未对网络资源的动态变化进行考虑，适应性较差，传统的路径算法都是静态的选路算法。权重算法和评估算法考虑了网络中数据流业务属性和服务质量需求的关系，具有特定需求的局部优化特点。全局优化算法可以从全局高度得到最优的流量控制效果，但是开销较大。合理均衡控制器的处理开销和控制时延，是未来大型SDN网络需要解决的重点问题。

在设计SDN流量控制算法时，没有最优的策略，只有结合需求的最优策略组合。在不同需求的网络中可以选择不同的控制算法或者算法组合进行应用。中小型网络的拓扑信息较少，一般的路由算法都可以适用，主要困难在于大型复杂网络的流量控制，这是未来SDN流量控制算法的主流研究方向。

未来SDN流量控制算法可能向智能化方向发展，以解决大型异构网络的需求，需要网络具备预测和适应网络变化的能力，提前做好资源的动态调配，弥补软硬件反应的时间差。这需要在实时分析网络流量和精确预估流量变化趋势的前提下，根据分析建立的业务量矩阵设置流量路径、分配骨干带宽和调整节点权重等。SDN未来可结合人工智能技术发展自组织和自学习能力，通过云计算发展大数据分析和计算能力，最终走向智能网络。例如，杨喜敏等[63]提出的基于增长型自组织映射（GSOM）的增量学习算法，可以对数据平面交换机的流表统计信息进行持续学习，动态获取网络流量的GSOM神经网络模型，不断学习网络流量特征，具有一定的自适应和预测功能。可见，结合人工智能的预测路由算法可能成为未来大型SDN网络发展应用的主流方向。