基于SDN的流量工程

陈鸿文，王丽

（四川大学计算机学院，成都　610065）

基于SDN的流量工程

陈鸿文，王丽

（四川大学计算机学院，成都610065）

软定义网络是一种新兴的网络，它将控制平面与数据层分离。通过控制的集中化和提供控制接口的开放，使网络管理简单化与灵活化。Google正在用软定义网络连接其数据中心，由于它在执行流量工程功能中的易操作性、有效性和灵活性。他们希望通过SDN结构来使网络利用率更好并且优化延迟和丢包。讲述当SDN逐步引入一个现有网络的时候SDN对流量工程的影响。主要将展示如何利用集中控制器在网络利用率和减少包丢失和延迟上得到显著改善，指出在网络中只有部分网络部署SDN能力的时候这些改进都是可能实现的。

软定义网络；流量工程

0　引言

软定义网络是一种新兴的网络范例［1-3］，它在网络中将控制层和数据层分离。这种功能的分离和控制在不同的控制平面执行由于其预期的收益引发了很多的研究。分离单独路由器的域间路由和使用逻辑路由控制系统作为让路由系统可管理化、简单化在文献［2，4］总有提到。软路由器结构［11］提出不允许路由进入到包的转发单元中，使用开放的标准接口。这种方法是作为更快引入一些像流量工程，新的VPN特点之类的网络功能提出的。文献［9］提出将控制层重新引入到传播平面和决策平面。通过传播平面将信息可靠地分布到网络元素和决策平面决策层来做所有的决策来作用于网络。这种重新引入的方案让决策层很容易有全网的视图和允许操作更轻松地表达所需的网络行为。

上面所有的常见的方法是包含两种组件的SDN：

（1）SDN Controller（SDN-C）：控制器是一种逻辑集中功能［3］。一个网络是被一个或者多个控制器控制的。控制器决定在网络中一个流的转发路径。

（2）SDN Forwarding Element（SDN-FE）：软定义转发单元组成了网络的数据层。包的转发逻辑是由SDN控制器决定的，并且在SDN-FE转发表中实现。

OpenFlow是控制器与转发单元交互的一种标准接口。当在网络中一个流初始化后将会有以下的这些反应：①流的第一个包通过SDN-FE传送到SDN-C，②流的转发路径由SDN-C来计算，③SDN-C发送适当的条目来在SDN转发单元从起点到目的地的路径上安装转发表，④在流中之后所有的包都在数据层进行转发而不需要控制层任何的功能。

SDN控制器是负责路径的选择并且因此所有的策略信息都会保存在控制器中。例如，Google通过OpenFlow路由器建立了一种SDN来连接它的数据中心（G-Scale）［5］。Google希望通过使用SDN来提高网络利用率同时优化延迟和丢包。

我们考虑是在现有网络中不断部署SDN时的流量工程。在这样一个网络当中，不是所有的流量都通过一个单一的控制器来控制。在不同的部分网络中可能有多个控制器并且也有一部分网络可能会使用已存在的网络路由规则。关键的问题是当在网络中所有的流不能被一个SDN控制器集中控制的时候是否还可能执行有效的流量工程。

在本文中，我们考虑在网络中一个SDN控制器仅仅控制一些SDN转发单元的流量的工程。剩余的网络使用标准网关协议OSPF来完成hop-by-hop路由。

本文的目的是建立一个SDN部署方案可以在网络中自适应和动态的管理流以致适应不同的流量模式。本文的主要主要贡献有以下几点：

①我们提出了SDN控制器优化问题并提出FPTAS方案来解决控制器问题。

②我们通过分析展示了当网络中部署有限的SDN转发单元时在延迟和丢包方面的有效作用。

③给定一个数量的SDN转发单元，我们提出一个算法用来确定这些转发单元的位置。

1　系统描述

我们考虑一种一个集中SDN控制器对一部分SDN转发单元的路由表进行计算的网络。假设在网络中SDN转发单元是所有节点的一个分支。剩余的节点执行像OSPF之类的标准网管协议。我们假设SDN控制器同网络一样采集链路状态信息。此外对于转发包，在它们转发到控制器时SDN转发单元做一些简单的流测量。控制器用这些信息在随着信息通过OSPE-TE传送到网络中来在SDN转发单元中动态的改变路由表来适应改变的转发条件。该控制器还利用这些使它可以在不同的SDN转发单元中协调的变化，使它在控制不断变化的流时更有效。常规节点，也可以说是那些非SDN转发单元，还是使用标准的转发机制来执行逐跳。与SDN混合的传统网络和这种混合网络在文献［10］中也有考虑到。

在图1中展示了一种有SDN转发单元和控制器的网络。SDN转发单元2，9，14由外部控制。我们将用这个网络来阐明我们在文章剩余部分中的概念。假设在网络中所有的链路都是双向的并且所有的链路负载都设置为1。我们现在从更细节的方面来介绍SDN控制器和SDN转发单元。在控制器中执行的算法将在第二部分中介绍。

（1）SDN转发单元

SDN转发单元执行以下功能：

转发：SDN转发单元充当基本的转发单元。SDN转发单元的路由表由SDN控制器计算。假设当SDN转发单元在给出一个目标时候可以执行多个下一跳。如果对于一个给定目标有多个下一跳，那么SDN转发单元可以在预先设定多次下一跳方式下将流分离发送到目标。

图1　SDN 控制器和SDN转发单元

对控制器来说计算多个下一跳和对转发单元加载路由表是很容易的［11］。对将流量分离成多个下一跳同时确定一个给定的流不是分离成多个下一跳有多种方法。部分这些方法需要一些额外的测量并且这很容易扩展现有的方法来获取额外的信息。因此在后文中，我们假设SDN转发单元对给定一个目标时可以将流分离成多个下一跳。也假设SDN转发单元可以用文献［14］中的技术来进行流量测量。

测量：在SDN转发单元中的路由表现对于标准的路由表是有细微的改变的，目的是帮助SDN转发单元的流量测量。图2中展示了SDN转发单元中路由表和标准路由表的不同。需要注意的是在网络中的节点能够到达目的地的地址的一个额外的列。当一个包被SDN转发单元处理时它的前缀同目的地址IP匹配来确定下一跳。它也增加由包的长度相应于目的节点计数器。这些是为了确定SDN转发单元和其他节点流量的数量。考虑路由表节点2。假设节点15（45.67.2.5）宣称要到达子网135.2316。让节点11（43.2.34.7）成为节点2到节点15最短路径中的下一跳。节点2的一部分路由表在图2中。对应的流量列跟踪来自节点2到节点15的目的前缀135.2316传送的字节数。

图2　SDN转发单元路由表

（2）SDN控制器

SDN控制有所有的选择逻辑并且协调所有SDN转发单元的路由以实现良好的网络性能。控制器有以下功能：

比较：SDN控制器使用OSPF-TE与在网络中的其他节点交换链路负载和其他的拓扑信息。（文献［9］中有实例。）在OSPF-TE中需要注意，在网络中节点也可以交换链路上的带宽信息。因此控制器知道当前OSPF权重和每一条链路上的流量流的数量（平均时间段内）。

路由计算：在网络中控制器负责所有SDN转发单元路由表的计算。对SDN转发单元的路由表计算的算法必须确定路由将沿着无环路路径且网络中的拥塞最小化。我们将会在文章的第二部分和第三部分描述控制器规划问题和解决技术。

2　SDN控制器问题

我们现在来详细描述SDN控制器需要解决的问题。假设网络由一包含N个节点的定向链路E组成。假设在网络中有n个节点和m条链路。让C（C⊆N）表示SDN转发单元部分，表示非SDN转发单元部分。让w（e）和c（e）分别表示链路e的OPSF链路权重和容量。我们使用f（e）来表示链路e的流量流。在链路e上的所有流都可以从OSPF到控制器。我们使用Tsd来表示从节点s到节点d的传送速率并且用Wud来表示那些通过或者始发与SDN转发单元u⊆C的目标节点d⊆N的通信总量。需要注意是Wud＞Tud。SDN控制器u可以用图2中的信息对所有的目标节点d测量它们的Wud。对于所有节点对（s，d）的值Tsd控制器都不会知道。每个节点都计算到网络中其他节点的最短路径。在节点u⊆N的路由表中包括到网络中其他节点最短路径的下一跳。我们使用NH（u，d）来表示节点d到节点u的下一跳。换句话说，NH（u，d）在u到d最短路径上第一个节点。在本文的其他部分，我们假设对于所有的非SDN转发单元下一跳是独立的，i.e，NH（u，d）对于所有的u∈D仅仅只有一个单元。我们做这个假设纯粹是为了便于说明。需要注意的是当NH（u，d）是基于所有节点u∈D最短路径计算时，NH（u，d）当u∈C如果没有路由环路时可以任意设定。

我们将用图3来阐明上面的观点。假设所有的链路权重都是1并且实线表示到13节点的最短路径。这是会导致SDN转发单元也使用标准最短路径计算的树。节点2，9，14是SDN转发单元。注意NH（6，13）= 10，NH（1，13）=2等。网络中的虚线显示在SDN转发单元的可替代的路径。例如，节点2可以将到节点13的流分离成一个到节点5另一个到节点11的两个不同的下一跳。

图3　到节点13的最短路径树

定义一：给定一部分SDN转发单元C，路径s=u0，u1，…，uk=d从节点s到节点d是可行的如果j=1，2，…，k，（uj-1，uj）∈E并且：

一条u0，u1，…，uk不同的可行路径被称为允许路径。让Psd表示节点s和节点d中的一组允许路径。

通过定义，指出一条路径如果对所有非SDN转发单元对目标节点的下一跳是通过最短路径算法给定的那么就是可行的。其他的可行路径只有在它是无回路时才是被允许的。因此，我们需要确定在节点s和节点d中的流必须在P∈Psd路由上。

举例说明，在图3中，3-2-5-12-13是节点3到节点13的允许路径。需要注意的是相对于3-2-11-13这并不是最短路径。路径3-6-11-13不是一个被允许的路径，因为节点3的下一跳应该是节点2。

定义二：在非SDN转发单元给定最短路径路由，从起点到目标节点不经过SDN转发单元的流被看做是不可控流。如果包的起点是SDN转发单元，或者在它到达目标节点之前至少经过一个SDN转发单元都将被看做可控流。

在SDN转发单元至少有一次机会去操作路径对于可控流。例如，流从节点6到节点13通过OSPF计算出的路径是6-10-13，因此不管是6还是10都不是SDN转发单元，流从节点6到节点13是不可控的。相反，流从节点8到节点13要经过SDN转发单元9，那么这个流就是可控流。

定义三：我们说一个SDN转发单元u∈C添加到一个包，如果：

①节点u对于包来说是在OSPF路由路径上。

②包在经过u之前经过其他SDN转发单元。

通过SDN转发单元u∈C的流被添加到一些目标节点d∈N将被表示为Iud。

因此，对于所有的可控流都有一个独立的SDN转发单元被添加的这个流。需要注意被添加的SDN转发单元可以是也可以不是流的起点。我们将用图4来阐述这些观点。在图中，到下一节点的数字表示节点到节点13的速率。比如节点1到节点13（T（11，13））的流是3。通过定义三，从节点3到节点13的流将会因为SDN转发单元2被添加。如果对于所有的起始对（s，d）的值Tsd都是已知的，那么Iud的值可以通过以下方式计算：移除SDN转发单元的出路，并且让OSPF发送所有的要求直到它到达SDN转发单元或者目标节点。在图3中举例说明，I2，13=9，I9，13=13和I14，13=5。如上所述，控制器是不知道Tsd的值的。在SDN控制器中唯一可以测量的值是经过节点u∈C到目标节点d的流的Wud。

（1）SDN控制器问题的公式

因为只有经过SDN转发单元的流我们才能对其进行操作，所有我们只关注这种流。通过SDN转发单元被添加的流Iud必须到达目标节点d。它只能沿着允许路径P∈Pud这样做。让g（e）表示在链路e上不可控流。SDN控制器的目的是发送可控流，让在链路上得延迟和丢包最小化。我们使用链路利用率来替代延迟和丢包。SDN控制器的最基本目的就是提高在网络中的链路利用率。在公式中，在路径中的流的变量是x（P）。SDN控制器解决以下的优化问题：

图4　SDN转发单元的独立路由流量

服从

θ在所有链路利用率最大化时有最优解。需要注意的是当θ＜1时，所有链路都不会出现过载情况。一旦SDN控制器解决了优化问题，那么对于计算下一跳就很简单了。

在上面的公式当中，我们假设Iud和g（e）的值是已知的。实际上Iud和g（e）都必须通过SDN控制器基于SDN转发单元的测量和通过SDN控制器接收的OSPF-TE信息来计算。

（2）计算Iud和g（e）

对于SDN控制器唯一可行的测量数据是：

①对所有链路e∈E的链路权重f（e）都可以从OSPF-TE信息中获取

②Wud数量对所有的u∈C和d∈N。这可以通过SDN转发单元测量并发送到SDN控制器

使用这两个工程量，SDN控制器必须计算出Iud和g（e）。我们首先来阐述Iud的计算。考虑一个固定的目标节点d。SDN控制器知道到目标节点d的当前路由。它知道在D中所有节点的下一跳并且在所有SDN转发单元中它不知道对目标节点的下一跳和当有多个下一跳时怎么分离它们。

定义四：在网络中给一个目标节点d和通用路由，在C中节点的关于目标d的路由顺序被定义成在C/d中的节点的顺序，这样如果在列表中u∈C比ν∈C先表现出来那么将没有目标是d从u发送到v的流。我们用R（d）表示目标是d的路由顺序并且在R（d）中用u≺d v表示u先于v表现出来。

路由顺序为了对任何目标节点d定义的，因此在到目标d的流量流不能有任何的路由循环。假设在到节点13的现有路由在图5中。我们只给出了与SDN转发单元相关的路由。这里有一个从节点9出发经过节点14的流。因此9≺1314。一个路由顺序是（2，9，14）。除了节点14的顺序必须在节点9之后，其他的顺序都是可能的。

图5　路由顺序的阐明

下面给出计算Iud的算法。

对于每个目标d∈N

①计算路由顺序R（d）

②对在R（d）中的第一个节点u设Iud=Wud

③发送一个从u到d的单元流并设βν（u，d）为

④对于在R（d）中的每个连续节点w

发送一个从w到d的单位流并计算βν（w，d）至此可以计算g（e）

这样Iud和g（e）都已经计算出来了。

（3）动态路由问题公式

SDN控制器发送流以在网络中尽量最小化链路的最大利用率。

服从

为了对上面描述的动态路由规划写出一个双重线性规划，我们设在（4）范围中的变量l（e）和在（5）范围中的，则有：

服从

假设我们设l（e）为链路e∈E的权重。让Iud表示从u到d权重最小的路径。那么公式现在可以写成：

3　选择SDN转发单元的位置

给出一个网络拓扑图，首先要确定SDN转发单元的位置。一旦确定了SDN转发单元的位置，SDN控制器就可以解决在SDN转发单元的动态路由问题了。理论上来说如果SDN控制获得的信息是准确的那么有SDN转发单元的系统将会比没有SDN转发单元的系统做的更好。在实际情况中有SDN转发单元的系统的性能的提升依赖于SDN转发单元的位置。节点的最佳选择依赖于在选择之前不能精确知道的流量矩阵。这里有两个选择。第一种是选择独立于流量矩阵的节点，第二种是用流量矩阵的估计来选择SDN转发单元。我们尝试这两种方法但是在本文中我们只介绍第二种方法。假设在网络中我们知道SDN转发单元的数量并且我们给出Tsd在节点s∈N和节点d∈N的流的流量矩阵。实际上流量可以并且在普通网络中也会偏离这个流量矩阵。假设我们必须确定SDN转发单元d。我们使用T来决定SDN转发单元h在网络中的位置。

定义四：在一组SDN转发单元C中的流量矩阵T的吞吐量被记为最大的标量λ，这样λT就可以沿着允许的路径发送到网络中。我们用λ（T，C）来表示吞吐量的值。

需要注意的事如果C=Ø怎对应于没有SDN转发单元的网络或者网络的行为同OSPF网络一样。当C= N时对应于所有节点都是SDN转发单元的网络。定义可得：

同样需要注意的是λ（T，N）也可以从解决网络中标准的最大并发流问题中得到。

因此给出T和f，目标就是确定：

我们使用贪婪算法来解决这个问题。首先我们假设一组SDN转发单元是空的。在算法的每一步，我们将给出最大吞吐量提升的节点添加到那个已存在的SDN转发单元组。重复这个过程知道在网络中我们有hSDN转发单元组。因为Tsd的值是已知的，那么吞吐量的问题可以这样解决：

服从

因为这个问题从结构上同SDN控制的问题一样，所以我们可以用同样的方法解决这种问题。

4　结语

在SDN和传统的网络中不断地部署SDN是一个值得考虑的重要方案。这对于那些需要完全部署SDN的大型网络非常重要。我们已经展示了在一个已经存在的网络中部署SDN对提高网络性能是可行的。及时部署少数的SDN转发单元都可以提高网络性能。该方案对网络中剩余节点不存在任何修改协议的操作。初步性能测试也表明了该理论可以提高总体网络的吞吐量并且在网络中提供更好的延迟和丢包操作。

［1］M.Casado，M.Freedman，J.Petit，J.Luo，N.McKeown，S.Shenker.Ethane：Taking Control of the Enterprise.ACM SIGCOMM CCR，37（4）：1-12，2007

［2］M.Caesar，D.Caldwell，N.Feamster，J.Rexford，A.Shaikh，and K.van der Merwe.Design and Implementation of a Routing Control Platform.Networked Systems Design and Implementation，May 2005

［3］N.Gude，T.Koponen，J.Petit，B.Pfaff，M.Casado，N.McKeown.Nox：Towards a Network Operating System.ACM SIGCOMM CCR，July，2008

［4］N.Feamster，H.Balakrishnan，J.Rexford，A.Shaikh，K.van der Merwe.The Case for Separating Routing from Routers.FDNA 2004.

［5］U.Holzle，”Opening Address：2012 Open Network Summit”，April 2012

［6］Network Development and Deployment Initiative（NDDI）”.http：//www.internet2.edu/network/ose/.

［7］Onix：A Distributed Control Platform for Large Scale Production Networks.T.Koponen et.al.，OSDI 2010，October，2010.

［8］Virtual Routers as a Service：the RouteFlow Approach Leveraging Software-Defined Networks.M.R.Nascimento，C.E.Rothenberg，M.R.Salvador，C.N.A.Correa，S.C.de Lucena，M.F.Magalhaes CFI 2011.

［9］J.Rexford et.al..Network-Wide Decision Making：Toward a Wafer-Thin Control Plane.HotNets-III，November 2004.

［10］C.Rothernberg，C.N.A.Correa，R.Raszuk.Revisiting Routing Control Platforms with the Eyes and Muscles of Software-Defined Networking.ACM-SIGCOMM HotSDN Workshop，2012

［11］T.V.Lakshman，T.Nandagopal，R.Ramjee，K.Sabnani，T.Woo.The SoftRouter Architecture.Proceeding of Hotnets 2004，November 2004.

CHEN Hong-wen ，WANG Li
（College of Computer Science，Sichuan University，Chengdu 610065）

Software Defined Networking is a new paradigm that separates the network control plane from the packet forwarding plane.Leveraging the centralized control ability and open programming interface SDN provides，network management can be dramatically simplified and flexibility.Google is using a Software Defined Network to interconnect its data centers due to ease，efficiency and flexibility in performing traffic engineering functions.It expects the SDN architecture to result in better network capacity utilization and improved delay and loss performance.Uses SDNs for traffic engineering especially when SDNs are incrementally introduced into an existing network，shows how to leverage the centralized controller to get significant improvements are possible even in cases where there is only a partial deployment of SDN capability in a network.

Software Defined Network（SDN）；Traffic Engineering

1007-1423（2016）26-0003-07DOI：10.3969/j.issn.1007-1423.2016.26.001

陈鸿文（1991-），男，四川阆中人，硕士，研究方向为软定义网络

2016-07-22修改日期：2016-09-10Traffic Engineering Based on SDN

王丽（1991-），女，山西临汾人，硕士，研究方向为软定义网络