软件定义网络中基于分段路由的流量调度方法

董谦，李俊，马宇翔,2，韩淑君,2



软件定义网络中基于分段路由的流量调度方法

董谦1,2,3，李俊1，马宇翔1,2，韩淑君1,2

（1. 中国科学院计算机网络信息中心，北京 100190；2. 中国科学院大学，北京 100049； 3. 佛山科学技术学院电子信息工程学院，广东 佛山 528000）

针对软件定义网络流量调度的多商品流问题，提出一种基于分段路由的方法。所提方法预先计算所有源—目的节点间的候选路径集合和相应路径的属性，再结合流的各种需求和约束条件设置候选路径的属性应满足的要求，据此筛选得出流的候选路径集合；基于流的候选路径集合简化了软件定义网络中的多商品流模型，降低了求解难度，支持控制器集中控制和各节点自主控制的工作方式，缓解了控制器的可扩展性问题；还讨论了如何满足网络的节能需求，减少可参与流转发的链路数量。性能评估结果表明，所提方法可满足流的各种需求和约束条件，提高网络性能，减轻求解流量调度问题的计算负担。

分段路由；软件定义网络；流量调度；线性规划

1 引言

互联网服务在人们的工作和生活中扮演着十分关键的角色，为此，人们提出多种类型的流量工程（TE, traffic engineering）技术以完成一系列网络优化任务。与此同时，网络管理员对网络流的细粒度管理也变得越来越重要。例如，网络管理员不仅要考虑传统的QoS（quality of service）需求，如时延、带宽、抖动、丢失分组率等[1]，还要考虑新出现的调度任务类型，如选择若干条不相交路径、部署服务链等。多协议标签交换（MPLS, multi-protocol label switching）是一种十分重要的机制，在这种场景下，标签解耦了转发路径控制和路由协议。但是，基于MPLS的TE相对复杂，特别是在多条流并存的情况下，通常难以取得性能和开销的平衡[2]。

近年来，分段路由（SR, segment routing）以及它与软件定义网络（SDN, software-defined networking）的结合引起了人们的广泛关注。SR支持无状态源路由，可以减轻控制器和中间节点的开销，对路径的管理和控制也十分灵活[2]；SDN能提供网络全局视角，能高效地部署TE任务[3]。显然， SDN结合基于SR的全局源路由可针对具体应用需求，对多条流分别进行细粒度的路径管理和控制[4]；相对于MPLS或传统SDN而言，SR极大简化了控制面，使控制器无需对中间节点下发转发规则，从而降低了控制器的负载，更好地平衡了网络性能与开销。

所有应用都需要满足特定的要求（约束条件），最典型的例子就是QoS。除此之外，SR网络还有一个特有且非常重要的约束条件是进行路径控制时必须满足的：由于设备性能的限制，标签栈最大深度是有限的，这意味着segment列表深度（SLD, segment list depth）是有限的[5]。对于有具体优化目标和约束条件的TE问题，一方面可建立相应的数学模型，另一方面也需要找到合适的算法来求解。如果基于SR解决SDN中的流量调度问题，以满足多个应用即多条流的需求，通常会面临以下挑战。

1) 各种各样的需求及约束条件会极大地提高求解问题的难度。一般来说，可用线性规划（LP, linear programming）、整数线性规划（ILP, integer linear programming）、混合整数线性规划（MILP, mixed integer linear programming）模型来表示多商品流（MCF, multi-commodity flow）问题[5-8]，但在多数情况下，它们是NP-Hard问题[4,7]，相应的算法必须足够高效。

2) SR网络中的硬件设备一般有最大SLD限制，能用于某条流转发的候选路径使用segment列表来表示，而且每个segment列表的SLD不应超过其硬件限制，因此候选路径不是任意的，必须将最大SLD限制以适当形式加入相应的数学模型中[5]。考虑路径的编码问题，将其表示为segment列表[9]，使最终求出的解可行。

3) 在很多场景下，控制器到网络设备间的往返时延不可忽视，一旦时延偏高，甚至由于种种原因超时，将会影响设备对相应流的转发[10-11]，这要求网络设备也具备一定的对流转发进行路径管理和控制的能力。支持SR的网络设备具有这种能力，但其计算性能有限，必须考虑网络设备如何在不依靠控制器的情况下对流进行控制，同时无需复杂的计算过程。

为此，本文分析了SDN中基于SR的流量调度模型，针对多个应用的流量需求并存的情况即 MCF问题，结合最大SLD限制等与应用无关的约束条件，提出一种有效的方法以便求解，同时使网络设备也具备一定的对流转发路径进行管理和控制的能力；还简要分析了如何尽量满足网络的节能需求。本文的主要贡献如下。

1) 针对SDN流量调度的MCF问题，结合SR的特点，设计整体架构，对问题进行建模和分析；

2) 提出一种简便的算法，预先计算所有源—目的节点间满足SLD、等价多路径（ECMP, equal cost multi path）等约束条件的候选路径集合和相应路径的属性，再结合流的各种需求和约束条件筛选得出流的候选路径集合，降低了后续求解的难度；

3) 基于流的候选路径集合，简化SDN中的MCF模型，为控制器集中控制和各节点自主控制的工作方式设计相应处理流程；

4) 针对网络的节能需求，讨论如何减少可参与流转发的链路数量。

2 SR简介和相关工作

2.1 SR简介

SR采用源路由范式，节点根据一个有序指令列表转发数据分组，这些指令称为segment。由于SR和MPLS之间的继承关系，MPLS的转发面本身并不用修改，segment以MPLS标签的形式表现时，一个有序segment列表也就是一个标签栈，栈内标签数量即SLD，转发时从栈顶标签开始处理；如果SR应用于IPv6，segment可利用IPv6头部中的路由扩展，通过指针来控制当前segment[12]。

segment标识符简称为SID，最常用的SID是节点（node）SID和邻接（adjacency）SID，用于标识SR路由器和它们间的邻接关系。源节点将segment列表封装进数据分组的头部，收到数据分组的路由器基于当前（active）segment处理，对segment的动作则有push、next、continue 3种。push，在分组头部插入一组segment；next，处理当前segment完毕后转到下一个segment，与之对应的是MPLS中的POP；continue，当前segment并未处理完毕因而保留，与之对应的是MPLS中的SWAP[12]。

SR数据面决定了设备如何根据segment来处理数据分组；SR控制面定义了如何在设备间传播SID信息。SR一般使用IGP（interior gateway protocol）通告SID信息，与MPLS的LDP（label distribution protocol）等协议相比，简化了控制面；SR只需在源节点维护流状态，根据源路由的原理和SR的转发过程，中间设备无需各类复杂的资源配置机制，只需按照当前segment处理数据分组即可，流的转发完全由源节点通过segment列表控制；SR还能很好地支持ECMP[12]。

总之，在源节点处对流配置一个segment列表，这条流的转发路径就确定了。通过SR能方便地对每条流进行细粒度管理，却无需修改IGP参数，从而保证了网络基础配置的稳定性。

2.2 相关工作

目前已有很多工作讨论如何在SDN中进行流量调度，如周桐庆等[13]总结了基于SDN的流量工程，将其分为数据层流量调度和控制层流量调度两大类。数据层流量调度的主要目的是借助控制器的全局视角提高链路利用率，避免拥塞；控制层流量调度的主要目的是解决控制器的可扩展性问题。本文注意到，源路由技术与SDN结合用于流量调度有突出优势。Li等[10]对SD-WAN（SDN for wide-area network）的研究表明，源路由可显著节省控制器建立流转发路径的时间；Dong等[11]则提出了AJSR，利用基于MPLS的源路由，平衡了下发规则的开销以及网络性能。因此，源路由技术不仅有利于减少控制器建立流转发路径所需的时间，提高网络性能，还能缓解控制器的可扩展性问题。

表1 几种基于SR的流量调度方法

也有一些工作讨论如何将SR用于流量调度。Bhatia等[6]认为SR的关键思想是将路径分解或表达成为若干个segment，他们只考虑两段segment的情况，分别开发了离线和在线流量调度优化算法。Hartert等[7]提出了一种新的混合约束规划框架来解决SR中的流量放置问题，设计了一种名为SR路径变量的数据结构，记录已经过的节点，列出接下来可能到达的节点，减小对计算资源的消耗。Hartert等[4]还设计了一种方法，用来控制电信级网络中的转发路径，提出名为DFEO的集中式优化器，通过中间点路由（MR, middle point routing）模型进行计算，而MR基于转发图，因此可支持多路径。Moreno等[5]分析了SR网络中的流量模型，认为ECMP会导致数据分组重新排序，因此考虑流转发不使用ECMP而使用单路径，还要满足SLD约束条件。在现实环境下特别是运营商网络中，并非所有设备都支持SR，混合网络或渐进式部署也是很重要的场景，为此Cianfrani等[14]引入分段路由域（SRD, segment routing domain）的概念，区分单个SRD和多个SRD的场景，建立MILP模型以求解SRD设计问题，在SRD内部则配置合适的流表。总结上述工作的特点如表1所示。

表1说明，流量调度的主要目的是降低最大链路利用率，如要使用SR技术，一般应考虑SLD约束条件。SR支持ECMP，但流转发是否支持多路径应从实际情况出发，并在建模时体现。针对MCF问题，一般先收集相关信息然后求解，再由控制器或网络管理员根据求得的结果将规则分别下发到相关的设备。

由于SR中路径编码的重要性，一些工作专门就此进行讨论。Giorgetti等[9]提出两种算法，保证对一条路径求出的SLD最小；Guedrez等[15]提出两种算法，对于邻接SID再将其区分为本地和全局两种类型；Cianfrani等[16]将路径编码与TE模型相结合，先基于网络图创建辅助图，然后列出源—目的节点间所有可选择的路径，再基于辅助图求解MCF问题。上述工作表明，如果先设定segment类型，则可根据路径求出其对应的segment列表且使其SLD最小。

相关工作分析验证了SDN中基于SR的流量调度的优势、可行性和效果，表1中基于SR的流量调度方式多为集中式计算求解路径及流量分担比例。然而，实际MCF问题中的约束条件种类较多，加之SR网络必须考虑最大SLD限制，单路径或多路径也使流量模型更加复杂，即使求出了模型的解，有时还需考虑路径的编码问题，集中式的计算方式如应用于各节点自主控制的场景也较为不便。另外，Lee等[17-18]提出MPLS中的多路径负载均衡算法通常分为两步，第一步计算候选路径，第二步计算流量分割比例。本文还注意到，在进行流量调度相关计算前，预先计算好候选路径的方案有突出优势：Suchara等[19]提出预计算多条路径则路由器不再需要进行路径计算，能够减轻路由器的负担；Leconte等[20]提出只要选择合适的预计算路径集合并将其控制在相对小的规模，可极大提高优化计算的速度。

因此，对于SDN中相对复杂的流量调度模型，本方法结合SR的特点提出了一种预计算候选路径集合的算法，不仅能满足各类需求和约束条件，还记录了候选路径对应的segment列表并使其SLD最小；根据候选路径集合计算流量分担比例，能够简化MCF模型，降低求解难度；本方法也支持各节点自主控制，各节点预先从控制器获取已经计算好的候选路径集合，调度时只需根据流的需求和当前网络状态在候选路径中选择合适路径。

3 问题分析

3.1 整体架构

在SDN中，控制器能通过南向接口协议获取网络信息，下发规则。在IP网络中，基于IGP的扩展能收集当前链路状态等必要信息。SDN中的流量调度如图1所示。

图1 SDN中的流量调度示意

图1中实线表示节点间的邻接关系即链路，假定有一条流从节点1先后经过节点5、节点4转发到节点3，粗箭头表示流的转发路径走向，虚线表示OpenFlow[21]等接口协议中控制器与节点间的packet-in和packet-out交互，控制器需要给这条流转发路径上的每个节点下发相应的转发规则。

将源路由技术SR引入SDN后，流量调度如图2所示。对于同样的一条流，此时控制器只需与源节点1交互，对路径进行编码并下发相应的segment列表。与图1中的SDN不同的是，SR网络通过SR控制面传播SID信息，控制器无需对中间节点下发转发规则，节省了控制器建立流转发路径所需的时间，减轻了控制器的负担；控制器可专注于根据MCF需求和约束条件进行流量调度优化计算，即使控制器失效，SR网络也具备转发能力，各节点能作为源节点自主控制某条流。

图2 SDN中基于SR的流量调度示意

3.2 模型建立与分析

式(8)表示链路可参与流转发的条件。如优化任务是最小化最大链路利用率，可表示为

min(9)

所有链路l为1时，式(1)~式(7)是SDN流量调度的MCF模型里的基本约束，所有流转发支持多路径时为LP模型，只支持单路径时为ILP模型。然而，如对流进行细粒度管理，例如满足应用的时延要求，或满足服务链中必经某节点的要求，每条流的需求都应体现，使得约束条件更多，通常导致求解难度增加；有些条件甚至难以表达，例如SR特有的SLD约束难以用线性关系式写出。

为此，本文提出一种基于SR的流量调度方法，为简化讨论只使用节点SID，不使用邻接SID。先做如下说明。

1) 将路径集合记为，每个都以矩阵形式表示。矩阵的列数等于，为中元素的数量，对所有链路编号，将链路记为e，链路编号=1,2,…,。矩阵的行数表示为()，因此，由()个一行列的一维数组即行向量组成，即()是矩阵中的数量。若考虑空集即行数为0的空矩阵[22]，则()最小为0。

2) 每个的实际意义是能用一个segment列表表示的一条路径或多条等价路径，分别规定如下：若表示一条路径，则中第列元素的值表示当这条路径负担的流量为1时链路e上的流量大小，故路径没有重复使用e，则路径经过e时元素值为1，不经过时为0；若表示多条等价路径且这些路径可编码为一个segment列表（按某些segment转发且存在ECMP负载均衡时，相应各条等价路径上的流量分担比例一般是固定的），则根据这些等价路径负担的流量之和为1时链路e上的流量大小设定中第列元素的值。流量平衡条件体现在的元素值中。

3) 对每个设置若干属性，的属性也就是路径的属性，例如：ecmp表示中是否存在ECMP负载均衡，存在则为1，否则为0；sld表示对编码所需SID数量的最小值；表示的segment列表记为sl，sl的获得基于4.1节中的路径产生过程；cost表示的路由代价；hop表示的跳数；delay表示的时延；nodein、nodeout分别表示负担流量时每个节点是否有流量流入、流出，均为一行列的一维数组即行向量形式，为中元素的数量，对所有节点编号，将节点再记为n，节点编号=1,2,…,，nodein、nodeout中第列元素的值为1分别表示节点n在负担流量时有流量流入、流出，否则为0。还可根据需要设置其他类型的属性。

本文方法的主要步骤如下。

1) 通过4.1节中的路径产生过程可获得网络拓扑中所有源—目的节点间的候选路径集合和相应路径的属性。源节点和目的节点间的候选路径集合再记为，所有()应大于等于1；所有节点对之间的及相应的属性作为控制器进行后续处理和MCF计算的依据；对于每个网络节点，可预先将以它为源节点的及相应的属性下发给它，使网络节点无需进行复杂计算便可筛选得出候选并对流转发进行控制。

式(12)和式(13)为链路容量条件和链路可参与流转发的条件，流量平衡条件体现在和式(10)及式(11)中，其他需求和约束条件体现在中，的取值范围由式(5)确定，至此简化了SDN中的MCF模型；式(9)是TE的经典优化任务[4]，还可添加其他优化目标，并对每个优化目标设定合适优先级和权重[23]。

4 方法描述

本文方法首先求出网络拓扑中所有源—目的节点间的候选路径集合，记录相应路径的属性，然后以此为基础，针对控制器和各节点自主控制分别设计相应处理流程进行流量调度。

4.1 路径产生

在SR网络中，sld为1表示segment列表中只有目的节点的SID，此时转发路径是从源节点到目的节点的最短路径或存在ECMP负载均衡的多条等价最短路径。网络拓扑确定则链路的路由代价即权重已知，可由最短路径算法得到所有节点对之间的最短路径或多条等价最短路径；最短路径不存在环路，这是后续排除有环路路径过程的前提。

将,间的最短路径集合再记为-1，将sld=2,3,…,的候选路径集合分别再记为-2、-3、…、，且-2、-3、…、在计算前应初始化为空集即行数为0的空矩阵，为所允许的最大sld，即sld≤。为便于表述，本文也将所允许的最大sld称为sld最大值。先根据最短路径算法求出网络拓扑中所有节点对之间的-1，显然任意一对,间的-1都只有一个，且这个的sl为目的节点的SID，sld=1；若,间只有一条最短路径，则这个表示这条最短路径；若有多条等价最短路径，则这个表示存在ECMP负载均衡的多条等价最短路径；记录相应的属性。

图3 预计算p的过程示意

简要给出计算所有节点对之间的-2的算法，如算法1所示。

算法1 计算所有节点对之间的-2

1) 输入，所有节点对之间的-1，相应的属性

2) for each∈do

3) for each∈ {} do

4) 初始化-2为空集即行数为0的空矩阵

5) for each∈ {,} do

6) if-1为空集即空矩阵 then

7) else

8) for= 1 to(-1) do

11) else

13) end if

14) end for

15) end if

16) end for

17) end for

18) end for

4.2 流量调度

控制器预计算得出所有节点对之间的。流量调度目标为min时，控制器先收集流集合、当前链路信息，所有链路l通常为1，也可根据要求设定l。然后由对应的筛选得出，设定的精度要求，控制对应的临时变量用于试探求解，所有流转发支持多路径时为LP模型，只支持单路径时为ILP模型。简要给出求解算法，如算法2所示。

算法2 优化任务为min时控制器求解

1) 输入，所有节点对之间的，相应的属性，当前链路信息，所有链路l，的精度要求

2) for each∈do

3) 根据对应的筛选得出

4) end for

5) 根据式(5)，结合的精度要求设定的取值范围，再将设定为其取值下限即满足式(5)且符合的精度要求的最小值，并以试探求解

6) if有解 then

7)←

8) else

9) 使按的精度要求增加并在增加后再以试探求解，无解则重复此步骤直到有解为止

10)←

11) end if

调整的方式也可使用其他更高效的方式。控制器根据当前条件及精度要求下求得的最小值对应的解配置流转发，segment列表直接取自sl。

各节点自主控制进行流量调度时，先从控制器获取其作为源节点的所有。当它自主控制某条流时，只考虑当前网络状况，收集链路信息，此时MCF问题变为这条流的路径选择问题，一般来说求解算法与算法2相似，只是变为{}，变为，若想使求得的解是唯一的，可添加其他优化目标。

4.3 节能控制

定义节能效果即不可休眠或关闭的物理连接数量为，将节能控制的优化任务设为使最小，即可参与流转发的链路数量最少，有

min(16)

根据式(16)进行优化计算并通过流量调度实现时，一般是约束条件而非优化目标，应设定值，将其代入相关约束条件。此时除式(10)~式(13)外，还应满足式(14)~式(15)。根据式(12)，l包含在中，求解前应先收集链路信息，根据收集的信息设定所有链路l的取值范围：u>0时链路已使用，相应的l必为1；u=0时链路暂未使用，相应的l可取0或1。控制器进行流量调度时，需求解和所有链路l，所有流转发支持多路径时为MILP模型，只支持单路径时为ILP模型。简要给出求解算法，如算法3所示。

算法3 优化任务为min时控制器，求解和所有链路l

1) 输入，所有节点对之间的，相应的属性，当前链路信息，

2) for each∈do

3) 根据对应的筛选得出

4) end for

5) 设定所有链路l的取值范围

6) 求解和所有链路l，根据式(15)得

各节点自主控制进行流量调度时，先从控制器获取其作为源节点的所有。当它自主控制某条流时，只考虑当前网络状况，收集链路信息，设定所有链路l的取值范围，此时MCF问题变为这条流的路径选择问题，求解算法与算法3相似，只是变为{}，变为，优先选择已用链路。

4.4 算法分析

控制器进行流量调度时，根据算法2和算法3，的元素数量等于所有流的()之和，链路的数量即l的数量是固定的，流量调度模型中的变量数量通常较多，控制器可使用Gurobi[26]等优化器求解；已有工作表明，选择合适的预计算路径集合[20]能缩小后续求解的搜索空间，降低求解难度，还能避免使用过长的路径[25]，而5.2.3节的评估结果表明，对进行筛选减少流量调度模型中的变量数量后，后续求解的难度降低。网络设备作为源节点自主控制某条流时，只考虑这条流的路径选择问题，求解难度更低；特别是当流转发只支持单路径时，通常无需求解ILP模型，只需依次检验中的每个是否可行，若都不可行则调整或l后再次检验。

对于所有流可使用任意多路径或单路径转发的SDN流量调度模型，增加约束条件通常会增加求解难度，部分约束例如SLD约束甚至难以表达；本方法预先计算候选路径集合，根据一定要求即约束条件对进行筛选意味着在后续求解时无需再考虑这些约束条件，从而简化了MCF模型。本方法基于源路由技术，控制器无需给中间节点下发转发规则；即使控制器失效，各节点只要已获得了相关便能自主控制；对进行筛选降低了后续求解的难度。这些特点均缓解了控制器的可扩展性问题。

5 性能评估

本文从公开数据集SNDLib[27]获取网络拓扑信息（包括节点、链路、链路的容量及路由代价）和流量数据，拓扑为GÉANT和Germany50，分别有22个和50个节点，考虑分别有72条和176条链路。

5.1 实验拓扑分析

首先基于GÉANT的网络拓扑信息进行分析，根据最短路径算法，GÉANT中所有节点对之间的最短路径均无ECMP，故ecmp必然为0；分别设定sld≤2, 3, 4，根据4.1节中的原则1)~原则2)，分别计算得出所有462对源—目的节点间相应的；统计所有节点对中()小于等于个的源—目的节点对的数量，除以此拓扑中源—目的节点对的总数即462后得到比例()，()表示()在数量上的分布情况。结果如图4所示。再基于Germany50的网络拓扑信息进行分析，根据最短路径算法，Germany50中部分节点对之间的最短路径有ECMP，故ecmp为0或1；分别设定sld≤2, 3，再用SP表示所有流转发只支持单路径，MP表示所有流转发支持多路径，区别在于前者ecmp应为0而后者无此要求，根据4.1节中的原则1)~原则3)，分别计算得出所有2 450对源—目的节点间相应的。结果如图5所示。

图4和图5表明sld最大值不同时，()随变化的趋势相似；()相同时，sld最大值越大则越大。根据4.1节中的原则1)~原则3)计算能使()的大小控制在相对有限的范围。图5还表明，sld最大值及()相同时，若部分节点对之间的最短路径有ECMP，由于ecmp还应为0，所有流转发只支持单路径时的通常小于支持多路径时的。

5.2 流量调度优化效果评估

5.2.1 GÉANT拓扑流量调度优化效果

图4 GÉANT网络拓扑分析结果

图5 Germany50网络拓扑分析结果

中的每对源—目的节点间有一条流，size为它们之间的流量需求大小；这3个分别用GÉANT-1、GÉANT-2、GÉANT-3从GÉANT的流量矩阵（TM, traffic matrix）数据集中取出3个作为用于评估的3个TM；设TM表示，各有462条流。再用Con表示有控制器，用nCon表示无控制器即各节点自主控制。流量调度优化任务为min，的精度要求设为1‱，优化效果用当前条件优化计算求得的评估且越小越好，为方便表示，再定义最大链路利用率优化效果为

式(19)中，SDN使用多路径指采用3.2节中约束条件为式(1)~式(7)的流量调度模型且所有流转发支持多路径，此时只考虑了基本约束且多路径能更合理地均衡负载，因此每个在此条件下求得的是相应精度要求下的最优值，故越小越好且最小值为1。基于5.1节中计算得出的sld≤4的，对每条流筛选其对应的，分别得出sld最大值为2、3、4条件下的（因ecmp必然为0，故SP和MP这两种情况下使用相同的）。以所有流沿最短路径转发的情况作为对比，表示为sld最大值为1。

图6 GÉANT流量调度优化效果−Θ

从图6中可以总结如下规律。

1) 有控制器时，流量调度是全局优化，可以取得相对理想的效果，所有流转发支持多路径时为1，意味着求得的能达到最优值；所有流转发只支持单路径时为1.06~1.14，意味着求得的接近最优值；无控制器时，流量调度是局部优化，在候选路径集合相同的情况下，有控制器时的全局优化比局部优化的效果更好；即使是局部优化，效果也比所有流沿最短路径转发时更好，支持多路径时求得的相比所有流沿最短路径转发时的值降低42%以上，只支持单路径时也可降低27%以上。

2) 有控制器时，sld最大值分别为2、3、4时的优化效果相同；无控制器时，sld最大值为2、3、4时的效果可能存在一定波动，不一定sld最大值越大效果越好，这也是局部优化导致的。

3) 无论有无控制器，一般来说所有流转发支持多路径时求得的比只支持单路径时略小（也可能在有控制器时相同，如表2所示），这是因为单路径的约束更严格，多路径能更合理地均衡负载。

5.2.2 Germany50拓扑流量调度优化效果

为验证本方法在不同规模拓扑下以及基于的属性做合适筛选得出的优化效果，先从Germany50的TM数据集中取出3个，然后分别取每个TM中源—目的节点间流量需求大小在本TM最大前200的流量数据，作为用于评估的3个TM；设TM中的每对源—目的节点间有一条流，size为它们之间的流量需求大小；这3个分别用Germany50-1、Germany50-2、Germany50-3表示，各有200条流。

基于5.1节中计算得出的SP和MP这两种情况下sld≤3的，对每条流筛选其对应的，仍将sld最大值设定为3，同样区分SP和MP这两种情况，分别得出cost相对其对应的源—目的节点之间最短路径的cost的比值在（以下简称为cost相对最短路径的比值）小于1.25、1.5、1.75的。结果如表2所示。

从表2中可以总结如下规律。

1) 无论所有流转发是支持多路径还是只支持单路径，以及有无控制器，在取得相同条件下无cost约束时的值以前，候选路径数量对优化效果影响较大，cost相对最短路径的比值上限增加意味着候选路径数量增多，优化效果通常也会更好。

表2 Germany50流量调度优化效果−Θ

2) 有控制器时，流量调度是全局优化，无论所有流转发是支持多路径还是只支持单路径，当cost相对最短路径的比值小于1.75时为1，意味着求得的都能达到最优值，因此只要基于cost做合适筛选，既可减小()，也能获得较好的优化效果。

5.2.3 Germany50拓扑流量调度求解时间

考虑5.2.2节有控制器时的情况，与3.2节中约束条件为式(1)~式(7)即无sld、cost约束条件的SDN流量调度模型对比；均区分所有流转发支持多路径和只支持单路径，即区分LP模型和ILP模型，统计其中的变量数量如图7所示。

图7表明，cost相对最短路径的比值上限越大，变量数量越多；cost相对最短路径的比值上限相同时，所有流转发支持多路径时的变量数量比只支持单路径时的变量数量更多；对进行筛选后，变量数量相对于SDN流量调度模型更少。

再将设定为当前条件优化计算求得的，不添加其他优化目标，此时模型有解，以代入求解一次所需时间作为求解时间；硬件为i7-6700处理器和12 GB内存，软件为Windows 10操作系统，在Matlab R2017a下用Gurobi[26]7.5.1求解并统计时间，用同一软硬件环境下的求解时间衡量求解难度。结果如图8所示。

图7和图8表明，对于LP和ILP模型，通常变量数量越少求解越快。cost相对最短路径的比值小于1.75时，根据5.2.2节的结果和统计求解时间的前提，此时本方法与SDN流量调度模型设定的相同，对于LP模型，本方法的求解时间比SDN流量调度模型少83%以上；对于ILP模型，本方法的求解时间比SDN流量调度模型少23%以上；一般而言，相同情况下ILP模型的求解时间相对LP模型更长。上述结果说明本方法在约束条件更多的情况下能简化MCF模型，通过对进行筛选可降低后续求解的难度，使求解时间更短，且求得的可达到最优值，能较好平衡网络性能与求解时间。无控制器时，参见4.2节，每条流求解时的变量数量只取决于()，比有控制器的全局优化时的变量数量更少，根据上述结果，每条流的求解时间会更短，更适合性能相对较弱的网络节点。

图7 5.2.2节有控制器时流量调度模型中的变量数量

5.3 节能控制优化效果评估

节能控制优化任务为min，优化效果用当前条件优化计算求得的评估且越小越好；仍使用GÉANT-1、GÉANT-2、GÉANT-3并将设定为典型值0.5[25]，为减轻计算负担由各节点对流进行自主控制；以所有流沿最短路径转发的情况作为对比，表示为sld=1。结果如表3所示。

图8 5.2.2节有控制器时流量调度求解时间

表3 GÉANT节能控制优化效果-SUM

从表3中可以总结出如下规律。

1)sld最大值越大，求得的越小，这是由于sld最大值决定了候选路径的数量，候选路径越多则越有可能让所有流使用更少的链路转发。

2) 当sld最大值相同时，所有流转发支持多路径与只支持单路径求得的相同，这是因为当设定的较大也就是链路可用容量足够大时，节能控制优化目标与流量负载分担因素关联不大。

5.4 评估结果讨论

首先，对GÉANT和Germany50拓扑的分析表明，根据4.1节中的原则1)~原则3)计算能使()的大小控制在相对有限的范围。

然后，若将优化任务设为最小化最大链路利用率，基于GÉANT和Germany50拓扑的评估结果表明，选择合适的候选路径集合后，本方法的优化效果良好，有控制器且所有流转发支持多路径时为1即求得的达到最优值，有控制器且所有流转发只支持单路径时为1~1.14即达到或接近最优值，无控制器即各节点自主控制时也有较好效果。

另外，基于Germany50拓扑的评估结果还表明，考虑有控制器时的情况，当cost相对最短路径的比值小于1.75时不仅为1即求得的达到最优值，所有流转发支持多路径时求解时间也比约束条件更少的SDN流量调度模型少83%以上，只支持单路径时求解时间比SDN流量调度模型少23%以上，说明当网络拓扑规模较大时，基于的属性做合适筛选得出，能在获得较好优化效果的同时减少流量调度模型中的变量数量，减轻计算负担。

最后，基于GÉANT拓扑的评估结果表明，本方法能较好满足节能控制需求，候选路径越多则节能效果越有可能更好，设定为0.5时求得的可达到所有流沿最短路径转发时的60%左右。

6 结束语

本文针对SDN流量调度的MCF问题，将SR引入SDN，设计整体架构；通过建模分析，结合SR的特点设计算法，预先计算所有源—目的节点间的候选路径集合和相应路径的属性，再结合流的需求和约束条件根据路径的属性筛选得出流的候选路径集合，不仅简化了SDN中的MCF模型，降低了后续求解的难度，还支持控制器集中控制和各节点自主控制的工作方式，也缓解了控制器的可扩展性问题；讨论如何满足网络节能需求，减少可参与流转发的链路数量。评估结果表明，SDN中基于SR的流量调度方法能满足流的各种需求和约束条件，提高网络性能，减轻求解流量调度问题的计算负担。

[1] WANG N, HO K, PAVLOU G, et al. An overview of routing optimization for internet traffic engineering[J]. IEEE Communications Surveys & Tutorials, 2008, 10(1): 36-56.

[2] FILSFILS C, NAINAR N K, PIGNATARO C, et al. The segment routing architecture[C]//IEEE Global Communications Conference. 2015: 1-6.

[3] KREUTZ D, RAMOS F M V, VERISSIMO P E, et al. Software-defined networking: a comprehensive survey[J]. Proceedings of the IEEE, 2015, 103(1): 14-76.

[4] HARTERT R, VISSICCHIO S, SCHAUS P, et al. A declarative and expressive approach to control forwarding paths in carrier-grade networks[J]. ACM SIGCOMM Computer Communication Review, 2015, 45(4): 15-28.

[5] MORENO E, BEGHELLI A, CUGINI F. Traffic engineering in segment routing networks[J]. Computer Networks, 2017, 114: 23-31.

[6] BHATIA R, HAO F, KODIALAM M, et al. Optimized network traffic engineering using segment routing[C]//IEEE International Conference on Computer Communications. 2015: 657-665.

[7] HARTERT R, SCHAUS P, VISSICCHIO S, et al. Solving segment routing problems with hybrid constraint programming techniques[C]//International Conference on Principles and Practice of Constraint Programming. 2015: 592-608.

[8] SCHÜLLER T, ASCHENBRUCK N, CHIMANI M, et al. Traffic engineering using segment routing and considering requirements of a carrier IP network[C]//IFIP Networking Conference and Workshops. 2017: 1-9.

[9] GIORGETTI A, CASTOLDI P, CUGINI F, et al. Path encoding in segment routing[C]//IEEE Global Communications Conference. 2015: 1-6.

[10] LI S, HU D, FANG W, et al. Source routing with protocol-oblivious forwarding (POF) to enable efficient e-health data transfers[C]//IEEE International Conference on Communications. 2016: 1-6.

[11] DONG X, GUO Z, ZHOU X, et al. AJSR: an efficient multiple jumps forwarding scheme in software-defined WAN[J]. IEEE Access, 2017, 5: 3139-3148.

[12] FILSFILS C, MICHIELSEN K, TALAULIKAR K. Segment routing, part I[M]. North Charleston: CreateSpace Independent Publishing Platform, 2017.

[13] 周桐庆, 蔡志平, 夏竟, 等. 基于软件定义网络的流量工程[J]. 软件学报, 2016, 27(2): 394-417.

ZHOU T Q, CAI Z P, XIA J, et al. Traffic engineering for software defined networks[J]. Journal of Software, 2016, 27(2): 394-417.

[14] CIANFRANI A, LISTANTI M, POLVERINI M. Incremental deployment of segment routing into an ISP network: a traffic engineering perspective[J]. IEEE/ACM Transactions on Networking, 2017, 25(5): 3146-3160.

[15] GUEDREZ R, DUGEON O, LAHOUD S, et al. Label encoding algorithm for MPLS segment routing[C]//IEEE International Symposium on Network Computing and Applications. 2016: 113-117.

[16] CIANFRANI A, LISTANTI M, POLVERINI M. Translating traffic engineering outcome into segment routing paths: the encoding problem[C]//IEEE Conference on Computer Communications Workshops. 2016: 245-250.

[17] LEE K, TOGUYENI A, NOCE A, et al. Comparison of multipath algorithms for load balancing in a MPLS network[C]//International Conference on Information Networking. 2005: 463-470.

[18] LEE K, TOGUYENI A, RAHMANI A. Hybrid multipath routing algorithms for load balancing in MPLS based IP network[C]//IEEE International Conference on Advanced Information Networking and Applications. 2006.

[19] SUCHARA M, XU D, DOVERSPIKE R, et al. Network architecture for joint failure recovery and traffic engineering[C]//ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems. 2011: 97-108.

[20] LECONTE M, DESTOUNIS M, PASCHOS G. Traffic engineering with precomputed pathbooks[C]//IEEE International Conference on Computer Communications. 2018.

[21] MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74.

[22] HIGHAM D J, HIGHAM N J. MATLAB guide[M]. Philadelphia: Society for Industrial and Applied Mathematics, 2016.

[23] BRANKE J, DEB K., MIETTINEN K, et al. Multiobjective optimization: interactive and evolutionary approaches[M]. Berlin: Springer Science & Business Media, 2008.

[24] ZHANG J, YU F R, WANG S, et al. Load balancing in data center networks: a survey[J]. IEEE Communications Surveys & Tutorials, 2018, 20(3): 2324-2352.

[25] ZHANG M, YI C, LIU B, et al. GreenTE: power-aware traffic engineering[C]//The 18th IEEE International Conference on Network Protocols. 2010: 21-30.

[26] GUROBI OPTIMIZATION, LLC. Gurobi optimizer reference manual [M]. Beaverton: Gurobi Optimization, 2018.

[27] ORLOWSKI S, WESSÄLY R, PIÓRO M, et al. SNDlib 1.0 - survivable network design library[J]. Networks, 2010, 55(3): 276-286.

Traffic scheduling method based on segment routing in software-defined networking

DONG Qian1,2,3, LI Jun1, MA Yuxiang1,2, HAN Shujun1,2

1. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China 2. University of Chinese Academy of Sciences, Beijing 100049, China 3. Department of Electronic and Information Engineering, Foshan University, Foshan 528000, China

In order to address the multi-commodity flow problem for traffic scheduling in software-defined networking, a method based on segment routing was proposed. The proposed method pre-computed sets of candidate paths and attributes of these paths for all source-target nodes, and set the requirements of attributes of candidate paths that should be met combined with various demands and constraints of flows, then generated sets of candidate paths for flows. In the proposed scheme, multi-commodity flow model in software-defined networking was simplified based on sets of candidate paths for flows, the difficulty of solving was reduced, the centralized control by the controller and the autonomous control by nodes were supported, the scalability of controller was improved. In addition, how to meet the energy-saving needs of the network was proposed, i.e., reducing the number of links that could participate in flow forwarding. The performance evaluation results indicate that the proposed method can meet various demands and constraints of flows, improve network performance, and reduce the computational load of solving the problem of traffic scheduling.

segment routing, software-defined networking, traffic scheduling, linear programming

TP393

A

10.11959/j.issn.1000-436x.2018245

董谦（1986−），男，湖北咸宁人，中国科学院计算机网络信息中心博士生，佛山科学技术学院讲师，主要研究方向为未来互联网、软件定义网络、流量工程等。

李俊（1968−），男，安徽桐城人，博士，中国科学院计算机网络信息中心研究员、总工程师、博士生导师，主要研究方向为未来互联网、网络安全等。

马宇翔（1991−），男，河南开封人，中国科学院计算机网络信息中心博士生，主要研究方向为网络体系结构、网络安全等。

韩淑君（1986−），女，山东高唐人，中国科学院计算机网络信息中心博士生，主要研究方向为网络体系结构、网络功能虚拟化等。

2018−05−31；

2018−10−10

李俊，lijun@cnic.cn

国家重点研发计划基金资助项目（No.2017YFB1401500）；中国科技云建设工程资助项目（No.Y72923）；国家自然科学基金资助项目（No.61672490）

The National Key R&D Program of China (No.2017YFB1401500), The China Science and Technology Cloud Project (No.Y72923), The National Natural Science Foundation of China (No.61672490)