SDN中基于用户服务等级目标的流量控制算法

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

0 引言

传统IP 网络配置管理存在的主要问题是监控粒度太粗，交换机和路由器的配置能力太弱，不能实施各种网络业务的快速部署。从监控粒度来说，SDN 交换机可以在全部协议层次上进行流的区分和计数，具备对每流计数和监控的能力。SDN 控制器拥有全网所有交换设备的流表项配置能力，不仅能完成传统网管系统做不到的路由表的配置，还可以实施各种网络业务的配置和部署［1］。传统IP网络通过多策略路由表和多转发表实现了对报文路由方式的控制，能够实现流量的分类和传递，但是无法在不同端口、不同路径上实现同一种业务的流量分配。SDN架构将交换机的控制功能和转发功能分离开来，分成集中控制平面和数据转发平面，可对不同交换机和路由器的流表进行修改，控制每一条数据流的流向，根据需求实现特殊的数据流量控制功能［2］。

在SDN 系统里，有独立的中央控制器和上层应用层，转发层只是作为最底层的数据转发，业务编排在控制器中完成。在控制器完成具体动作过程中，SDN的流量控制算法起了决定性的作用。相对于传统方式，SDN 为流量工程的开展提供了更好的基础［3］。目前尚且没有一种万能SDN 流量控制算法能够满足所有QoS 业务目标的需求，自适应路由算法也只能在局部框架内进行自动调整。在不同QoS需求的网络中针对QoS 等级目标来选择控制算法或者算法组合，是解决此问题的有效方法。因此，为解决此问题，提出了基于用户业服务等级目标的流量控制算法。

1 研究现状及研究意义

传统IP 网络采用尽力而为的转发模型，其特点是尽最大可能发送报文，对时延、可靠性等性能不提供有效保障［4］。因此，需要能根据网络可用资源和数据流的QoS 需求来决定如何建立和维护路由。QoS 路由主要解决思路是，如何找到一条能够同时满足多个约束条件且具有最小代价的路径满足服务质量的需求，即解决性能约束和最优化问题。服务质量是一系列从用户感知角度来描述系统提供服务的性能特征的参数，反映了用户对服务的满意程度。这些参数包括业务可用性、时延、丢包率、吞吐量等［2］。从网络用户体现统计结果来看，用户关心的技术指标主要有带宽、连通性、流量参数和网络性能参数等［5］。

与传统IP 网络一致，SDN 中QoS 业务路由协议也分为3个部分，首先根据用户应用体验和需求，关联网络参数建立服务等级指标（SLI）体系，依据服务等级协定（SLA）来实施服务质量控制，以达到用户需要的服务等级目标（SLO）。在实际的网络保障中，管理人员需要关注的是SLI 和目标SLO，根据目标和指标选择路由策略和算法。如表1 所示，SDN 服务质量主要包括SLI、SLO、SLA 3部分。

近年来，业界对于保障IP 网络的QoS 数据业务提出了一系列理论和解决方案，然而传统的互联网架构仍然提供的是尽力而为的转发服务，难以提供有效服务类别的保障。在QoS 技术发展历程中，IETF 提出了几种模型，如经典的集成服务模型IntServ 和综合服务IntServ，但是都没有得到全球化的成功应用，部分原因是这些架构是建立在分散的逐跳路由算法之上，而不是在全局视图下的统一调度。利用快速标记交换，MPLS提供了一种可靠的改善QoS性能的解决方案，但是它是静态的，不具备实时配置和适应能力。

表1 服务质量项目及含义

目前，给予QoS的路由算法积累了很多研究成果，Hedera［6］提出了一种基于模拟退火（SA）的算法，通过当前网络状态将流路由到不同的路径。这项工作比传统的ECMP（Equal Cost Multi-Path）［7］具有更好的多路径性能。Long［8］提出了一种动态重路由算法，当SDN 控制器检测到网络拥塞时，使用单跳或多跳算法将流重新路由到其他路径。与传统的轮询调度（RR）算法相比，该方法可以提高网络利用率。上面提到的相关工作仅考虑一个约束，即链路带宽。但是，用户可能有多个QoS要求，为了解决这个问题，可以记录每个应用程序的QoS 要求，并分配路由路径来满足QoS要求，Chienhung［9］提出了一种基于模拟退火的QoS 感知路由算法，该算法能够在成本函数中自适应地调整延迟、丢失率和带宽要求的权重，以根据QoS要求找到最佳拟合路径。LARAC［10］提出了一种LARAC QoS 感知路由算法，该算法使用基于拉格朗日松弛的聚合成本方法，找到了近似的最优路径。MINA［11］提出了一种用于物联网的QoS 感知流量调度算法，使用遗传算法迭代地计算满足QoS 要求的最佳拟合路径。然而，成本函数中的静态权重和局部最优值难以兼具最优是MINA 的主要问题。但是由于控制器的计算能力存在瓶颈，在大型SDN 网络中利用启发式算法进行迭代计算路由，计算量将急剧增加，即使动态地调整多个权重优化得到综合QoS 最优路径，得到的也是对关键参数平均化后的优化路径，与业务流的QoS 仍会存在一定偏差。

实际网络中，服务需求不同的多种业务流均同时在网络中传输，单一的路由算法往往顾此失彼，无法兼顾所有业务流的SLO。自适应算法和感知流量算法往往预先给定了加权计算模型，最终得到的路由可能是某一评价体系下的综合最优，并不一定符合用户的业务目标需求。同样，类似于遗传算法的全局最优算法得到的拟合路径也都是在预定变量约束模式下的网络最优，都没有结合SLO来计算路径。

本文所提算法充分利用SDN 全局视图功能，掌握全网节点和链路的带宽、速率、时延等重要SLI，根据用户SLO 要求和优先级将QoS 流进行分类，建立约束模型来针对性地计算路由，因流施策，为业务流分配达到SLO要求的路由。

2 流量控制算法建模

2.1 QoS流分类

通过监控流表项中流表优先级、ToS 服务类型字段，获得QoS 数据包的业务类别、优先级、延迟时间等控制参数。将业务流按照SLO进行划分，分类如下。

类型1：传输速率目标。如高优先级的需要限时传递的大数据业务，要求在指定的速率限值以上完成业务传输，若低于传输速率，将影响完成时间。

类型2：传输时延目标。如实时传输的音视频流，超过某一时延，将会产生用户可感知的明显卡顿，影响用户体验。

类型3：传输丢包率目标。如对丢包率容忍度低的网络检索、网络游戏等交互类业务，超过一定丢包率将影响数据交互和用户体验。

用户的QoS业务流SLO可能是1种，也可能有2种甚至多种，而大规模SDN 网络中往往会发生参数路径竟合的现象，符合的SLO 种类越多，竟合的路径越少。按照用户SLO 的重要性顺序进行计算，可以找到筛选出符合用户全部SLO 的路径。由于网络业务服务目标类型和种类繁多，仅从业务流的速率、时延、丢包率3个目标值进行讨论。

2.2 控制算法模型

如图1所示，所提算法的控制层接纳控制机制为：首先在准入过程中，权衡异构网络各自当前的负载状况，对入流按照优先级大小排序，从端到端链路资源角度考虑是否能满足业务需求，并不损害已有优先级业务的QoS 流。其次，实时地依据网络负载状况设置业务的接入门限，以确定不同类业务服务质量与对网络影响的最佳协调点。而后，根据SLO 分类的QoS 策略匹配路由算法，并根据网络监控参数执行算法计算得到最佳路由，而后映射生成流表项，下发到转发节点。资源预留机制为：优先级由高到低，尽力而为地保证QoS流的预留网络资源。无优先级业务不预留资源，在剩余网络资源中以最短路径路由算法尽力而为地转发。

2.3 控制算法建模

图1 算法流程图

由于节点端口上下行链路带宽和时延不同，将拓扑建模为无多重边的简单有向图G（V，E），其中，V是SDN 网络中交换机节点的集合，E为链路集合，包含链路指标参数（带宽、时延、丢包率）。给定G中的2 个顶点vi、vj。设P是G中从vi到vj的链路est=［vs，vt］的集合，［est］∈Pst。每一条相邻直连链路都可以用带宽bij、时延dij、丢包率lij描述形成相应拓扑图，直连链路权值为w（eij）=wij=［bij，dij，lij］。链路指标参数均为一个拓扑更新周期T内的统计值，假定周期内网络拓扑参数保持不变，数据流量性能稳定。设Ov为业务流速率目标，Od为业务流时延目标、Ol为业务流丢包率目标。

算法规则：采用分层思想，将网络拓扑每一个业务流的传输作为赋权拓扑图G分层的支撑子图。检测周期T内获得的网络链路参数，建立网络相邻节点权值［bij，dij，lij］矩阵：

其中，不相邻节点间的权值为：wij=［0，∞，1］，表示不相邻节点间直连链路带宽为0，时延为无穷大，丢包率为100%。确定了相邻节点权值矩阵就确定了网络拓扑连接及网络参数。

通过避圈法计算获得所有从vs发往vt业务流链路est的集合Pst，需满足约束：链路最小带宽满足流量传输速度需求，链路累计时延不超过最大目标时延，链路累积丢包率不超过目标丢包率。由此建立目标方程：

其中，i、j为链路est的任意相邻中间节点vi到vj编号。由目标函数，可以实现路由链路的计算。

由于QoS业务流的服务质量是以业务流的优先级进行先占排序计算路由的，在衡量算法是否达到保障QoS 的SLO，就要体现出流量优先级的评价作用。按照完成用户SLO的情况程度，对其进行评价，评价值设为Dest，定义为QoS 业务流优先级加权的SLO 完成结果的期望值。当网络的路由分配满足QoS 业务流的SLO时，计完成目标值设为Cst，p，则有：

主要算法描述：

输入：各QoS流的SLO矢量值（Ov，Od，Ol）。

输出：QoS流路由，Dest值。

a）收集并建立网络拓扑：G（V，E，W）。

b）根据流的服务类型字段将流量进行分类，从G中抽出相应服务参数的权值拓扑G（V，E，bij）、G（V，E，dij）、G（V，E，lij）。

c）根据源、目的节点地址，用避圈法得到所有无环路径Pst=Kruskal（vs，vt）。

d）根据SLO 约束优先级顺序，结合约束条件（1）、（2）、（3）逐条循环计算符合SLO 矢量值（Ov，Od，Ol）的所有Pst，剔除不符路径。

e）对每条QoS 业务流，存在满足SLO 业务路径，则分配路由，令Cst，p为1，否则为0。更新网络拓扑参数，跳转至b）进行下一业务流的计算。所有流计算完则跳转至f）。

3 仿真和结果分析

3.1 仿真环境

实验采用的拓扑如图2 所示，链路标示为节点直连链路的网络指标参数。使用Mininet软件生成拓扑，Floodlight 作为控制器，Iperf 来生成数据流，Wireshark抓包分析。

3.2 仿真及结果分析

在网络中通过Iperf产生32组定义了1-8优先级3类QoS 数据流，随机依次发送，为简便计算，将所有数据流的SLO 值统一设置为（25，100，0.18），在此SLO 下计算所提算法最终评价值Dest，并与QoS-aware routing算法［9］和LARAC QoS 算法［10］测试结果进行了对比，如图3所示。

从仿真测试结果可以看出，所提算法基本达到了设计目标，SLO 目标完成评价优于QoS-aware routing算法和LARAC QoS 算法。由于该算法是在符合目标约束条件下的所有通行链路中筛选出可行解，现有网络资源依次用来保障业务流的QoS 需求，可在有限网络资源中尽最大可能地为各业务流匹配路径。而QoS-aware routing 算法是通过调整服务指标参数权重来自适应拟合路径，改变了链路指标参数的相对值，影响了实际符合路径的选择。LARAC QoS 感知路由算法使用拉格朗日松弛模型，通过适当选取权系数来整调成本函数校正量，近似拟合路径，在宽约束条件下能得到较好的近似松弛结果，但是由于取权系数的影响，实际计算结果和符合路径仍会出现偏差。

4 结束语

用户的业务流服务质量体验是网络服务保障的重点，从流的服务质量目标倒推合理路径是本算法的主要思路。根据SLO 分类进行路径约束的计算，算法复杂度低，执行速度快，准确性高，达到了用户QoS 业务流要求目标，适合大型复杂网络的QoS数据流应用。与已有的2 种QoS 算法相比，准确性完成度更高，更能贴合用户的业务需求。在设计指定规模下的网络时，其网络容量和服务能力可以利用此算法进行计算。但是，所提算法仅仅是针对用户SLO需求进行设计，在网络均衡负载、资源利用率和吞吐量上缺乏设计，容易造成资源浪费和成本提升。下一步可在SLO可行解域内结合负载均衡算法进行链路配置，达到兼顾提高网络资源利用率和吞吐量的目的。

图2 实验拓扑

图3 仿真测试结果