SDN网络定义了一个新的网络架构，其转发平面和数据平面分离，并通过控制器实现对整个网络逻辑上的集中控制.SDN控制器不仅可以获取全局网络拓扑信息，而且可以通过向交换机发送询问消息获取网络状态统计信息^[1].与传统网络中的路由器不同，SDN网络中的交换机缺乏智能性.对新到达的业务流，如果交换机中没有对应的流表项匹配，则此交换机会通过安全通道向控制器发送一个packet-in消息，以指示一个新的业务流请求.某一时刻，SDN控制器可能收到网络中各个交换机发来的多个业务流请求，因此本文考虑提出SDN网络中的批路由策略用于同时解决多个业务流的路由请求问题.批路由在传统网络中已有研究，但受到传统网络分布式架构的限制，应用起来十分困难.而SDN网络采用集中式的网络架构，可以通过控制器对网络业务流提供集中式的管理，这使得批路由在SDN网络中的实际应用成为可能.批路由在现实中的应用场景主要体现在批路由队列网络，网络中的各种业务流顺序到达，形成一个业务流请求队列.如果选择批处理方式，则SDN控制器可以实现对队列中的多个业务流请求同时处理；否则SDN控制器根据队列中的业务流请求的优先级逐个计算业务路由路径.

在SDN架构中，交换机根据控制器下发的流表项对分组实现匹配转发(如OpenFlow^[1]).按照现有SDN控制器与交换机的南向标准OpenFlow协议，一张流表可以使用任意的字段组合，这种基于匹配转发的模式要求交换机掩盖不需匹配的字段.在当前的商业芯片设计中，只有使用三态内容寻址存储器(ternary content addressable memory，TCAM)才能实现.TCAM是一种昂贵的资源，具体表现在芯片面积大、功耗大.现有的交换机只支持大约1~2 k^[2-3]的TCAM流表项，而且短期内不会增加太多^[4].因此，与传统网络路由器的路由表项不同，交换机的流表资源也是极其昂贵的奇缺资源.

SDN网络中链路带宽资源的不合理使用会导致瓶颈链路的存在，从而引起链路拥塞；流表资源的不合理使用同样会导致瓶颈节点的存在.例如在极端情况下，如果某个交换机上的流表资源已经耗尽，则控制器无法向此交换机下发流表，交换机亦无法再转发新的业务流.若此交换机的邻接链路的带宽资源依然富余，则这些富余的链路带宽受交换机流表资源的限制亦无法再利用.即瓶颈节点的出现亦会导致带宽资源的浪费.因此在设计SDN网络的路由策略时，需合理利用带宽和流表资源，同时防止瓶颈链路和瓶颈节点的存在.

本文基于业务流的特点，对业务流进行分类，并引入业务资源偏好的概念，旨在设计一种SDN网络中基于业务资源偏好的批路由策略.通过业务资源偏好，根据业务流特点合理使用网络中的带宽和流表资源；通过批路由策略实现对多个业务流路由的全局调度.从而更加均衡地利用网络资源，以获得更好的网络性能.

1 相关工作

近来已有一些工作开始考虑流表资源的限制对SDN网络的影响，并提出了一些机制用于合理利用流表资源和带宽资源.Cohen等^[5]研究流表资源对SDN网络使用率的影响，并研究受流表资源有限性的影响，路径度数受限的网络最大流问题.研究结果显示，SDN网络交换机中的流表资源越少，网络可以接收的总流量也越少.

Luo等^[6]提出一种快速流表聚合算法(FFTA)用于解决SDN网络中TCAM有限的问题.FFTA是一种离线的流表聚合解决方案，它通过将多个流表项聚合成一个而不改变转发规则，但是流聚合的方式在细粒度处理业务流请求时并不适用.Feng等^[7]通过对不同的应用程序计费，并基于计费提出一个适用于多个应用程序的联合流表和带宽资源的比例公平资源调度算法.Zhang等^[8]通过混合路由同时为多个流量矩阵实现负载均衡，其与显示路由相比可以极大地减少流表项的使用.

Banerjee和Kannan^[9]指出可采用混合TCAM和SRAM(static random access memory)方式匹配流表项.TCAM存储方式可提供快速查找(O(1))，但是TCAM芯片面积大、功耗大，因此其可用大小受限.TCAM资源少意味着可用流表数目少，这是流表资源受限的根本原因.SRAM与TCAM相比，会降低50%的功耗，但会提高20多倍的匹配延迟.考虑到实际网络应用的需求，SDN网络环境更希望交换机有较少的匹配延时，因此在匹配性能方面TCAM优于SRAM.联合TCAM/SRAM的流表存储方式，可以在一定程度上实现功耗和延时的折中，缓解流表资源的受限问题.

现有网络是基于分布式的路由决策模型，而批路由更适合SDN集中控制的网路架构，同时也更好地利用了集中控制的优点.Trivisonno^[10]提出一种虚拟链路映射算法用于同时网络中的多个业务流请求.结果显示虚拟链路映射算法在带宽分配上性能优于最短路径优先算法.

与现有工作不同，本文考虑了业务流特点和网络资源使用之间的关系，并据此引入业务资源偏好的概念.然后结合业务资源偏好和SDN集中控制的优点，设计了一种基于业务资源偏好的批路由策略.

2 问题描述 2.1 SDN网络模型

本文将SDN网络建模成一个有权无向图G=(V,E,ρ,μ),ρ=V→N⁺,μ=E→R⁺，其中V和E分别代表网络中交换机和链路的集合.在设计路由策略时考虑网络中交换机流表资源和链路带宽资源的限制.在无向加权图中，流表资源抽象成交换机上的可用流表数目ρ；带宽资源抽象成链路上的可用带宽μ.对任意节点i∈V，ρ_i表示节点i上的可用流表数；任意链路ij∈E，μ_ij表示链路ij的可用带宽.

2.2 业务资源偏好

SDN网络中有限的流表资源限制流经OpenFlow交换机的业务流的数目；与此同时，网络中的带宽限制流经网络链路的数据流量.换言之，业务流对流表资源的消耗与其业务流量大小无关，只与业务流数目多少有关；而业务流对带宽资源的消耗与业务数据流量呈正相关.根据调研，网络流量服从Zipf分布^[11]，少数的业务流产生了大量的业务数据流量，多数业务流的业务数据流量都很少.Cai等^[12]通过挖掘网络中的业务流特性证明了上述规律.这在现代社会中尤其如此，越来越多的手持终端设备产生了大量的即时消息、心跳消息等，这些消息的流量很小但是数目巨大.本文以业务数据流量(带宽需求)为标准将业务流分类为长流^[13](视频流等)和短流^[14](即时消息等).根据以上分析可以得出如下结论：

1) 长流：流量大，流数少，耗带宽多，耗流表少；

2) 短流：流量小，流数多，耗带宽少，耗流表多.

由此可以看出长流更偏好带宽资源，而短流更偏好流表资源.基于流分类的业务资源偏好的提出，使得业务流路由策略更符合业务流特点，以均衡带宽资源和流表资源的使用.

2.3 业务流批到达

在SDN网络中，当一个新的业务流到达且在交换机中没有对应的流表项匹配，则交换机会向控制器发送一个packet-in消息.每个packet-in消息表示一个新的业务流请求.如图 1所示，网络中所有的交换机在某一时刻都可能有新的业务流到达，则控制器会收到批到达的业务流请求^[15].

某一时刻控制器中批到达的新业务流请求总数记为K，f_k=(s_k,t_k,d_k)表示第k个业务流请求^[16]，k=1,2,…,K.其中(s_k,t_k)表示业务流请求f_k的源-目的地址对，d_k表示带宽需求.F={f_k,k=1,2,…,K}表示批到达的业务流请求的集合.

3 系统模型

本节首先基于业务流分类和流量特点定义业务资源偏好和单位路由开销；然后参考最小开销多商品流模型^[17]，为SDN网络中基于业务资源偏好的批路由问题建立优化模型.

3.1 业务资源偏好度定义

本文基于网络业务流区分提出业务资源偏好度的概念.业务资源偏好度本质上是基于网络流量特点和业务流特点定义的经验值，其定义基于业务流分类.不失一般性，本文根据业务流带宽需求将其分为长流和短流.SDN网络中的路由策略需同时考虑链路带宽资源和交换机流表资源，因此对长流和短流需分别定义带宽资源偏好度和流表资源偏好度.

根据网络流量特点可以分别获取网络中长流和短流的流数比例和平均带宽需求.其中长流和短流的平均带宽分别用d_e和d_m表示，流数比例分别用γ_e和γ_m表示，且γ_e+γ_m=1.由于网络流量服从Zipf定律[11]，则有如下关系式成立：

$\begin{align} & {{d}_{e}}>{{d}_{m}}, \\ & {{\gamma }_{e}}<{{\gamma }_{m}}, \\ & {{\gamma }_{e}}\times {{d}_{e}}>{{\gamma }_{m}}\times {{d}_{m}}. \\ \end{align}$

(1)

SDN网络中流表资源的使用只与流数有关，而带宽资源使用与业务流的带宽需求和流数均有关系.因此，带宽资源偏好度α和流表资源偏好度β定义成如下形式：

$cl:{{\alpha }_{e}}=g\left( \frac{{{\gamma }_{e}}\times {{d}_{e}}}{{{\gamma }_{m}}\times {{d}_{m}}} \right),{{\beta }_{e}}=1,$

(2)

$dl:{{\alpha }_{m}}=1,{{\beta }_{e}}=g\left( \frac{{{\gamma }_{m}}}{{{\gamma }_{e}}} \right).$

(3)

其中,函数g(.)表示资源偏好度定义函数，α_e和β_e对应长流的带宽资源偏好和流表资源偏好，α_e>β_e(长流偏好带宽资源)；α_m和β_m对应短流的带宽资源偏好度和流表资源偏好度，α_m<β_m(短流偏好流表资源).

3.2 单位路由开销定义

本文引入单位路由开销的概念用于衡量链路和节点负载.当业务流在某条路径上传输时，业务流会消耗路径上的链路带宽和交换机流表资源，因此会产生链路开销和节点开销.单位路由开销包含链路开销和节点开销，其定义基于资源使用率、业务流需求和资源偏好度.

用ρ⁰_i表示交换机i∈V的最大流表资源容量，μ⁰_ij表示链路ij∈E的最大带宽资源容量.则对业务流请求f_k=(s_k,t_k,d_k)，节点流表资源使用率η^k_i和链路带宽资源使用率η^k_ij可以定义成如下形式：

$\eta _{i}^{k}=1-\frac{\rho _{i}^{k}}{\rho _{i}^{0}},\eta _{^{ij}}^{k}=1-\frac{\mu _{ij}^{k}}{\mu _{ij}^{0}}.$

(4)

其中，ρ^k_i表示业务流请求f_k流经交换机i时当前可用流表资源，μ^k_ij表示链路ij的当前可用带宽资源.η^k_i和η^k_ij分别反映当前节点和链路的负载大小.

为实现节点流表资源和链路带宽资源的均衡使用，节点开销应该与交换机流表资源使用率η^k_i成正比；链路开销应该与链路带宽资源使用率η^k_ij成正比.节点开销c^k_i和链路开销c^k_ij定义如下：

$c_{i}^{k}=w\left( \eta _{i}^{k},{{\beta }^{k}} \right),c_{ij}^{k}=\left( \eta _{i}^{k},{{\alpha }^{k}} \right).$

(5)

β其中，w(.)表示开销函数，资源使用率体现当前网络负载情况.业务资源偏好度α^k,β^k由业务流请求f_k的业务流类型决定，参考式(2)、式(3).根据式(5)，若一条链路的资源使用率已知且固定，受业务资源偏好的影响，不同类型的业务流f_k流过这条链路，其单位路由开销亦不同.

3.3 优化模型

本部分参考最小开销多商品流模型^[17]对基于业务资源偏好的批路由策略建立数学优化模型，且优化目标为最小化K个批到达的业务流请求的总路由开销.该优化问题是一个混合整型线性规划问题，其优化模型(边-节点公式)如下所示：

变量说明：

y^k_ij：二进制变量，如果业务流请求f_k流经链路ij，则y^k_ij=1；否则y^k_ij=0.

x^k_i：二进制变量，如果业务流请求f_k流经交换机i，则x^k_i=1；否则x^k_i=0.

b^k_i：指示业务流请求f_k的流供给变量，若i是路由路径的源节点，则b^k_i=1；若i是目的节点，则b^k_i=－1；若i是中间节点，则b^k_i=0.

$\begin{align} & \left( P1 \right)\underset{y_{ij}^{k},x_{l}^{k}}{\mathop{\min }}\,\sum\limits_{k=1}^{K}{\sum\limits_{ij\in E}{\left\{ {{d}_{k}}\times c_{ij}^{k}\times y_{ij}^{k}+c_{i}^{k}\times x_{i}^{k} \right\}}} \\ & s.t.\left( a \right)\sum\limits_{k=1}^{K}{{{d}_{k}}\times y_{ij}^{k}\le {{\mu }_{ij}},\forall ij\in E,} \\ & \left( b \right)\sum\limits_{k=1}^{K}{x_{i}^{k}\le {{p}_{i}},\forall i\in V}, \\ & \left( c \right)\sum\limits_{ij\in E}{y_{ij}^{k}-}\sum\limits_{ji\in E}{y_{ji}^{k}=b_{i}^{k},k=1,2,\cdots ,K,} \\ & \left( d \right)x_{i}^{k}=y_{ij}^{k},k=1,2,\cdots ,K,i\ne {{t}_{k}}, \\ & \left( e \right)x_{i}^{k}\in \left\{ 0,1 \right\},y_{ij}^{k}\in \left\{ 0,1 \right\},k=1,2,\cdots ,K. \\ \end{align}$

(6)

其中，单位链路开销c^k_ij和节点开销c^k_i的定义参考式(5)，其定义基于业务资源偏好和当前网络资源负载.假定批处理的业务流数目为K，其优化目标P1是最小化K个业务流请求的总的路由开销，这是一个全局优化问题.约束条件(a)表示带宽资源约束，即流经链路的业务流的总带宽需求不能超过当前链路可用带宽资源μ_ij的限制.约束条件(b)表示流表资源约束，即流经交换机的总的业务流数目不能超过当前交换机可用流表资源ρ_i限制.约束条件(c)是流守恒约束，以保证路由路径的连通性和有效性.约束条件(d)表示网络拓扑约束，即流经链路ij的业务流必然流经交换机i.约束条件(e)表示不可分割流约束，即每条业务流只在一条路由路径上传输，不可分割.

优化问题P1变量和约束较多，求解复杂.为简化问题求解，引入路径开销c^k_p，其定义如下

$c_{p}^{k}=\sum\limits_{ij\in p}{c_{ij}^{k}\times {{d}_{k}}+\sum\limits_{i\in p}{c_{i}^{k}.}}$

(7)

此时可将边-节点公式P1转化成基于路径的优化公式P2.如下所示：

$\begin{align} & \left( P2 \right)\underset{y_{p}^{k}}{\mathop{\min }}\,\sum\limits_{k\in K}{\sum\limits_{p=P}^{K}{c_{p}^{k}\times y_{p}^{k}}} \\ & s.t.\left( a \right)\sum\limits_{k\in K}{\sum\limits_{p=P\left( k \right)}^{K}{{{d}_{k}}}}y_{p}^{k}\delta _{ij}^{p}\le {{\mu }_{ij}},\forall ij\in E, \\ & \left( b \right)\sum\limits_{k\in K}{\sum\limits_{p=P\left( k \right)}^{K}{y_{p}^{k}\le {{p}_{i}},\forall i\in V,}} \\ & \left( c \right)\sum\limits_{p\in E\left( k \right)}{y_{p}^{k}=1,k=1,2,\cdots ,K,} \\ & \left( d \right)y_{p}^{k}\in \left\{ 0,1 \right\},k=1,2,\cdots ,K, \\ & \left( e \right)\delta _{ij}^{p}\in \left\{ 0,1 \right\}. \\ \end{align}$

(8)

其中，P(k)表示业务流请求f_k的所有源节点s_k到目的节点d_k可用路径集合.y^k_p∈{0,1}是一个二进制变量，若业务流请求f_k流经路径p∈P(k)，y^k_p=1；否则y^k_p=0.P2中(a)(b)分别对应链路带宽约束和交换机流表约束.(c)(d)对应不可分割流约束.约束条件(e)是网络拓扑约束，δ^p_ij用于指示链路ij是否在路径p∈P(k)上.

4 BRP-SA算法

本节基于模拟退火法^[19]提出一个启发式算法BRP-SA，用于求解基于业务资源偏好的批路由优化问题P2(NP-难问题^[18]).

4.1 算法描述

BRP-SA基于业务流分类和业务资源偏好，因此首先要实现算法预处理过程：将SDN控制器中批到达的业务流分为长流和短流，并根据式(2)、式(3)设定资源偏好度，根据式(4)计算单位链路和节点开销.

优化问题P2的解是所有K个业务流请求的路由路径的集合.BRP-SA算法详细流程如表 1所示：

步骤1：BRP-SA算法设定初始化参数，包括初始温度T_max，最低温度T_min和算法最大迭代次数I等.

步骤2： BRP-SA算法为优化问题P2设定初始解，即顺序处理批到达的K个业务流请求，并根据式(7)采用Dijkstra以此分别计算最小开销路径.这K个业务流路径的集合即为P2的初始解S₀，根据P2的优化目标即可计算初始路由总开销C(S₀).当前最优解S=S₀.

步骤3：打乱K个批到达业务流的处理顺序，为P2计算新解S′及对应路由总开销C(S′).若新解路由总开销比当前最优解小，则接受新解；否则以Metropolis准则^[19]接受新解.若接受新解，则更新当前最优解S=S′.每次新解处理结束后要降低当前温度.

步骤4：迭代执行步骤2，并不断更新当前最优解.若达到终止条件，则算法终止，当前最优解S即为BRP-SA算法输出的最优解.终止条件设定为连续若干个新解都没有接受或者迭代终止.

业务流请求处理顺序会影响网络资源使用率，因为先处理的业务流会优先占用资源，增加链路带宽负载和交换机流表负载，必然会导致单位链路开销和节点开销的增加.基于引理4.1^[22]，在步骤3中引入一种特殊的流处理顺序，即对批到达的业务流请求根据其带宽需求排序，优先处理带宽需求比较大的业务流.

引理4.1 假设0<a₁<a₂<…<a_n，并且0<b₁<b₂<…<b_n，则对[1,2,…,n]的任意排列π，有以下不等式成立：

$\sum\limits_{i=1}^{n}{{{a}_{i}}{{b}_{n-i+1}}\le \sum\limits_{i=1}^{n}{{{a}_{i}},{{b}_{\pi \left( i \right)}}\le \sum\limits_{i=1}^{n}{{{a}_{i}}{{b}_{i}}.}}}$

(9)

4.2 算法性能分析

BRP-SA算法设计基于模拟退火法，通过设置合理的参数可以在较快时间内收敛到近似最优解.批处理的业务流个数K影响算法的迭代次数I；网络拓扑大小用节点数n表示，其影响路径计算复杂度T_p.BRP-SA算法批处理K个业务流的总时间复杂度T_K计算如下：

$\begin{align} & I=0\left( K \right),{{T}_{P}}=O\left( {{n}^{2}} \right), \\ & {{T}_{K}}=I\times K\times O\left( {{n}^{2}} \right)=O\left( {{K}^{2}}\times {{n}^{2}} \right). \\ & \\ \end{align}$

(10)

由式(10)可以看出，BRP-SA可以在多项式时间内求得较优解.批处理的业务流请求数目K越大，算法复杂度也越高，因此要设定合适的批路由数目，以实现算法性能和算法复杂度的折中.

5 BRP-SA算法性能分析 5.1 仿真设定

仿真基于Erdos_Renyi拓扑模型^[20]产生一个包含15个节点和34个边的SDN网络拓扑，设置交换机流表资源容量ρ⁰_i为1 500^[2-3]，链路带宽资源容量为μ⁰_ij为1 Gbps.业务流请求基于网络流特点^{[11, 21]}设定，具体参数如表 2所示.

5.2 仿真结果

本文优化目标为最小化总体路由开销，其本质上是基于业务资源偏好、考虑当前链路负载，通过批路由方式实现链路带宽资源和节点流表资源的均衡利用.仿真结果中的“瓶颈节点使用率”和“瓶颈链路使用率”从一定程度上反映当前网络的资源均衡情况，是最小化总体路由开销后流表资源和链路带宽资源均衡程度的反映.而本文中的另一个仿真结果“业务流请求接受率”则是在流表和带宽资源均衡使用后的直接结果，即网络可以接纳更多的业务流请求.

图 2比较了随着网络业务负载增加，贪心路由算法GA和BRP-SA算法在不同的K取值时的瓶颈交换机流表资源使用率情况，其中GA为传统考虑链路带宽的最小开销路径算法.仿真结果显示BRP-SA算法在均衡交换机流表资源使用的性能上优于GA算法.但是，BRP-SA在不同K值下的流表资源均衡性能并无明显差别.这表明BRP-SA路由算法由于考虑到流表资源的有限性和业务资源偏好，可以更加均衡地使用交换机流表资源.但是，批路由策略并不能明显提高流表资源的均衡使用率，这是因为流表资源的使用只与业务流数目和业务流路径长度(跳数)有关，而BRP-SA选择的是最小总开销的路由路径集合，并不能保证路径长度最短.

图 3比较了随着网络负载增加，贪心路由算法GA和BRP-SA算法在不同K取值时的瓶颈链路带宽资源使用率.仿真结果表明，BRP-SA算法可以在考虑流表资源限制的同时，较好地均衡链路带宽资源的使用.BRP-SA算法均衡带宽资源的性能随着K值的增大逐渐提高.另外，结果同时表明，若不考虑批路由策略，受交换机流表资源的影响，算法在均衡流表资源的同时，会降低链路带宽资源的性能.

图 4比较了随着网络业务负载增加，贪心路由算法GA和BRP-SA算法在不同K取值时的网络业务流请求接受率.仿真结果表明采用BRP-SA算法可以使SDN网络接收更多的业务流请求，而且业务流请求的接受率随着K值的增加而提高.

结合图 2、图 3、图 4的仿真结果，可以得出如下结论：业务资源偏好和批路由具有互补性，基于业务流特点和业务资源偏好可均衡使用流表资源，基于批路由策略可均衡使用带宽资源.BRP-SA算法通过基于业务资源偏好的批路由策略，可同时实现这两种网络资源的均衡使用，从而极大提高网络资源使用率.因此，BRP-SA可使网络接受更多的业务流请求.

6 结论

本文提出一种SDN网络中基于业务资源偏好的批路由策略BRP-SA.首先，BRP-SA考虑SDN网络中的一种特殊的网络资源，即流表资源(TCAM)的有限性.其次，基于网络流特点实现业务流分类，提出业务资源偏好的概念，以根据业务流偏好分配带宽和流表资源.最后，BRP-SA考虑SDN网络架构集中控制的特点，提出批路由策略用同时处理多个业务流请求.仿真结果表明BRP-SA可同时均衡带宽资源和流表资源的使用，防止由于网络资源不合理使用导致的现瓶颈节点和瓶颈链路问题.BRP-SA的设计使得SDN网络可接受更多的业务流请求.