SDN中一种基于拓扑变换的功能组合方法

2016-11-30席孝强兰巨龙段通江逸茗

电信科学 2016年7期

关键词：表项流表交换机

席孝强，兰巨龙，段通，江逸茗

（国家数字交换系统工程技术研究中心，河南郑州 450002）

研究与开发

SDN中一种基于拓扑变换的功能组合方法

席孝强，兰巨龙，段通，江逸茗

（国家数字交换系统工程技术研究中心，河南郑州 450002）

现有软件定义网络（SDN）中的功能组合方法大多都在单节点内进行，均未考虑单节点交换机的功能承载力。为此，首先提出一种基于拓扑变换的功能组合方法，通过拓扑变换将功能组合分散到多个节点中进行处理。其次，将拓扑变换建模成0-1线性规划问题并提出了综合搜索算法进行求解。最后，基于NetFPGA-10G和Ryu控制器完成了所提功能组合方法的原型系统实现。实验结果表明，与现有方法相比，所提出的功能组合方法在降低流处理时延和存储开销的同时提高了组合效率。

软件定义网络；拓扑变换；功能组合；NetFPGA-10G

1 引言

软件定义网络[1]（software defined networking，SDN）将控制功能从底层网络设备中剥离出来，实现了控制平面与数据平面相分离。其中，控制平面通过北向接口与应用层交互以实现多样的网络业务功能，通过南向接口（OpenFlow[2]等）实现控制器与交换机的交互，使网络功能以表项的形态存在于数据平面。SDN支持大数据、云计算等多样化新兴网络业务，这些业务往往需要多个功能（如监控、路由、负载均衡、NAT、接入控制等）共同作用于数据分组，然而，如果将各种不同的功能都包含于单个应用内，会导致不同功能生成的表项相互覆盖，也会使网络应用中的功能逻辑变得错综复杂，进而增加应用开发难度。Monsanto C等人[3]指出模块化可以降低SDN软件系统开发的复杂度，并提出将SDN中应用转为多个可以同时协作处理网络数据分组的功能模块组合，从而降低SDN应用的逻辑复杂性并提高可扩展性。产业界中，在城域网中SDN技术可以实现业务的智能控制与多样化，通过利用策略和业务链中的功能组合，可以为不同用户灵活定制差异化的业务服务。尤其是近年来在SDN中引入NFV技术，改变了设备状态，简化和开放了网络能力，并逐渐凸显出网络功能在新型网络体系结构中的重要性，这就使得网络功能编排成为产业界的一个研究热点。

每个功能都会生成相应的功能表项并下发至数据平面，因此，功能模块组合问题可以转化为表项组合问题。参考文献[4,5]中提出了网络编程语言Frenetic，将功能生成表项进行并行组合，实现了多个功能（如路由、监控、计数）同时作用于数据分组。随后，又提出了优化的模块化编程语言Pyretic[3]，并增加了功能表项的串行组合方案，从而实现了不同的功能先后作用于数据分组（如一个被接入控制功能处理后的数据分组再经过路由功能处理）的效果。以上工作基于OpenFlow单级流表[6]实现，面临表项存储开销大等问题。为此，参考文献[7]基于OpenFlow多级流表[8]实现了SDN功能模块的串行和并行组合，并针对任意多级流表结构提出了相应组合算法，降低了表项开销和应用开发复杂度。

以上研究中提出的功能组合方案均基于单个网络节点，当应用下发所需的功能数量超过单个交换节点的承载能力时，以上方法均难以处理。而考虑到单个交换机的功能承载力十分有限（承载功能的个数约等于流表级数），因此以上方法在实际应用中存在较大局限性。为此，参考文献[9]从可重构网络[10]中引入元能力概念，提出一种基于元能力的SDN功能组合机制，通过多个交换节点协作的方式将功能组合分散到多个交换机内进行，从而减小单个交换机的开销，但在该方法所预设的应用场景中，功能表项是提前下发到交换机中的，并不符合SDN实时下发流表项的特性。

综上所述，如何基于多交换节点进行SDN中的功能组合是一个有待解决的问题。为此，本文提出了一种基于拓扑变换的SDN功能组合方法，该方法在控制器中完成组合策略的分析，当所需功能数量大于单个节点的承载力时，对发送给各个功能模块的网络拓扑进行虚拟变换，然后将各个功能生成的表项分散到虚拟变换的几个节点中，从而在不影响上层功能处理逻辑的同时实现了多功能组合处理。最后，在Ryu[11]控制器内实现了该功能组合模块的原型系统。

2 功能组合整体架构

本文所提的功能组合方法在控制器中实现，其整体架构如图1所示，由功能组合模块、功能库以及组合策略等部分组成，其中，功能组合模块完成策略分析、拓扑构建、表项下发等任务。根据网络业务功能需要，上层应用下发组合策略。组合策略中包含多种有序编排的网络功能，功能对应生成相应的表项并下发到OpenFlow交换机中完成对数据分组的处理。策略分析模块用来接收组合策略并进行分析，判断组合策略中的功能数是否超过单个交换机功能承载力，如果超过，则拓扑构建模块将获取的底层抽象拓扑进行虚拟变换。拓扑构建模块用来生成虚拟网络拓扑以供上层功能模块使用，其首先根据底层实际物理网络拓扑生成抽象拓扑，然后根据策略分析模块的处理结果决定是否对抽象拓扑进行拓扑变换。控制器根据组合策略从功能库中调用处理数据分组所需的功能，并将功能生成表项下发到表项下发模块。表项下发模块根据拓扑构建模块传来的网络拓扑，决定将功能表项下发到单个或者多个OpenFlow交换机中。

2.1 功能库

功能库，是指在SDN控制器上运行的各种不重叠的网络功能模块的集合，其中包含常见的网络功能，如监控、接入控制、路由、转发等。功能库的存在使得在设计不同的SDN应用时不用再重新开发功能的实现模块，而仅需通过下发组合策略的方式，并用功能组合模块从功能库中获取相应的功能。控制器将功能相应表项下发到交换机中，从而实现业务所需的多功能处理，避免了不同应用中相同功能模块的重复开发。

2.2 组合策略描述

面对网络业务的多样化需求，上层应用通过下发组合策略的方式实现业务对数据分组的多功能处理。组合策略由目标集和功能集组成。目标集是指被处理的数据流集合，如在异常检测过程中处理{SrcIP=192.168.2.1/16;DstIp=192.168.3.3/16}的数据流；功能集是指处理目标集中数据流所需功能的有序集合，即功能组合链，对目标数据流的操作必须包含功能组合链中的所有功能。功能组合链和组合策略的形式化描述如下。

图1 功能组合整体系统结构

定义1 （功能组合链）网络业务所需各种功能有序排列的集合，在应用层表现为功能的排列，即逻辑功能组合链；控制层根据底层网络拓扑将功能组合链向下映射到数据层，得到功能组合实例链，并以下发流表项的方式实现上层的组合链。F是功能集合，且F≠。功能序列Fp就是一个功能组合链。

通过一个例子简要说明。管理员希望用户在访问IP地址为10.10.21.1/24的服务器之前，要经过负载均衡、监控、计数功能处理，所以该组合策略可以表述为＜{SrcIP=192.168.2.1/24,DstIP=10.10.21.1/24},{load-balance,monitor,count}＞。

2.3 拓扑变换

拓扑变换是指控制器从底层网络获得抽象拓扑后，根据策略需求将源节点附近若干能与其形成到达目的节点的数据流通路的节点看成一个虚拟节点而完成的虚拟变换。经过拓扑变换，控制器可以将下发到源节点交换机的功能表项改为下发到一个虚拟节点中，然后再将功能表项分散到虚拟节点内的多个物理节点中，从而解决单点交换机承载能力有限的问题。为方便后文叙述，定义单个节点的功能承载力。

定义3 （功能承载力）OpenFlow交换机同时执行功能表项对应动作的能力，以能够同时执行的动作指令的数量定义功能承载力。当处理数据分组所需功能较多时，对应下发到交换机中功能表项也较多，而交换机的表项容量以及动作执行数量均有限，就可能导致单个节点无法承载多个功能处理。假设单点交换机的功能承载力为N（约为流表级数）。

根据网络业务功能需要，上层应用下发组合策略，控制器分析组合策略，根据网络拓扑从功能库中获取相应功能并生成表项下发到源节点交换机中，即在单节点内完成功能组合。当功能需求超过单个节点的功能承载力时，控制器会根据变换后的拓扑将功能表项下发到多个交换节点中，假设需要M个功能，单节点功能承载力为N，则需要将功能表项下发到[M/N]+1个交换机中，功能表项与交换机的对应关系由拓扑变换方法得出（见第4节）。

单节点内的功能表项组合，就是将不同功能表项匹配域与动作集进行拆分合并，然后用多级流表进行连接，route（路由）和 load-balance（负载均衡）的示例如图 2所示，具体组合方法见参考文献[7]。由于并行组合方法是串行组合方法的一种特殊情况，所以将参考文献[7]中串行和并行组合方法进行合并，并统一用&表示；对于多节点内功能表项组合，就是将相应功能表项放在不同交换机上进行连接，monitor（监控）、route、load-balance、count（计数）与NAT的示例如图3所示。

图2 单节点内功能组合示例

通过一个简单例子具体说明拓扑变换的过程，如图4所示。假设组合策略的功能集为{monitor，count、load-balance，NAT}，单点交换机的功能承载力N=2。当数据流到达源点交换机E6时，通过分析组合策略判定需要进行拓扑变换，通过拓扑变化方法得到需要变换的节点以及执行路径{E6-E4-E5-E3}，即将节点E6、E4看成一个虚拟节点E0完成变换，如图4所示。最后下发功能表项时，将monitor与 count组合表项下发到 E6，将 load-balance与NAT组合表项下发到E4。

3 功能组合问题建模

3.1 问题描述

将单节点功能承载力作为功能组合的影响因素，是本文的一个创新点。因此，本文提出SDN中基于全局网络拓扑的功能组合问题并对其进行建模。

定义4 （功能组合问题）对于给定的组合策略、底层网络拓扑，控制器为策略规定的功能组合链寻找一条最优执行路径并将相应的功能表项下发到底层OpenFlow交换机中。是功能集中相应功能映射到底层拓扑的一条执行路径。定义SF={s1,s2,…,sm,…,si,…,sn}是功能集F的一条执行路径，且需要满足下列条件:

· 节点 si与 si+1是相互连通的，1≤i≤n-1；

·{s1,s2,…,sm}是功能集映射到底层拓扑的节点集；

·s1是源节点，sn是目的节点。

多节点内的功能组合过程可建模为“组合策略—执行路径—交换机表项”的两级映射过程，即“组合策略—执行路径”的映射和“执行路径—交换机表项”的映射，定义如下。

定义6 （“组合策略—执行路径”映射）将组合策略P中的功能集作为功能组合链，以业务需求为约束条件，为每个功能组合链选取最优的执行路径，即将功能组合链中功能映射到底层拓扑交换机中，形成从源节点到目的节点的数据流通路。映射过程可以表示为h:P→SF，其中，P={＜Op,Fp＞|Op⊆O,Fp⊆F}，SF是功能组合链 F 的执行路径。

定义7 （“执行路径—交换机表项”映射）根据功能组合链与底层网络拓扑的映射关系，将功能相应表项按次序下发到底层OpenFlow交换机中。映射过程可以表示为g:SF→EF，EF表示执行路径中交换机的表项，其包含功能表项和普通表项。

图3 多节点内功能组合示例

图4 拓扑变换示例

一个“组合策略—执行路径—交换机表项”的映射过程示例如图5所示。该组合策略的目标集为 (src=W1,dst=

执行路径的形式化描述见定义5，其中，符号“⇒”表示功能所在节点交换机。

定义5 （执行路径）F是功能集合W6),首先将逻辑功能组合链映射到底层拓扑交换机上，得到从W1到W6的执行路径，图5中阴影的节点是功能组合链映射到底层拓扑的节点。然后根据“组合策略—执行路径”的映射关系，控制器将表项下发到交换机中，得到E1到E6的表项，图5阴影的表项是功能组合链对应生成的功能表项；非阴影的表项是普通表项，仅起到连接的作用。

图5 “组合策略—执行路径—交换机表项”映射过程

3.2 “组合策略—执行路径”映射

底层网络拓扑用G(V,L)表示，其中，V表示交换机节点集，L表示执行路径的链路集合。“组合策略—执行路径”映射，即把组合策略中的逻辑功能组合链映射到底层网络拓扑，得到执行路径。假设应用下发组合策略P，通过形式化的描述对该映射过程进行建模，称其为功能组合模型。从源节点到目的节点有多条执行路径，通过选取最优执行路径，最小化链路代价。本文计算链路代价，考虑执行路径距离代价、流表空间耗费参数与最小节点数目对链路代价的影响。

由于现有网络路由算法均以最小化路径距离代价为设计目标，低的路径距离代价可以降低系统能耗。因此，执行路径的距离代价依然是本文优先考虑的因素。对于流表空间耗费而言，由于功能表项不止一条，而交换机流表存储空间有限，如果流表存储空间占用过大，会降低交换机处理性能，导致分组丢失率和处理时延增大。因此，流表空间耗费是选择执行路径时需要考虑的关键因素之一。最小化节点数目可以降低交换机总体存储开销，减少系统资源占用。

模型用式（1）～式（6）进行表示，表1中给出主要符号的含义。

表1 描述中主要符号的含义

优化目标：

式（1）是该模型的优化目标，最小化执行路径的代价，其中，N表示拓扑中节点数目，M表示功能集中的功能数。式（2）中R表示承载功能所需最小节点数目，T表示交换机流表级数。式（3）表示归一化后的执行路径距离代价。式（4）表示归一化后的流表空间耗费，在选取执行路径的前R个节点时需要考虑，因为功能生成表项条目较多，而普通表项只有一条，起到连接转发的作用，所以普通表项空间耗费可以忽略不计。式（5）表示两个放缩系数应满足的条件，可以用来调节执行路径距离代价和流表空间耗费这两个因素的重要程度比例。式（6）表明该问题的解空间取值为0或1，即该问题为0-1线性规划问题。式（7）保证所选执行路径从源地址s到目的地址t的可达性。

3.3 “执行路径—交换机表项”映射

“执行路径—交换机表项”映射是一个表项下发的过程，控制器根据“组合策略—执行路径”映射中所选的执行路径 SF={s1,s2,…,sm,…,sn}，将功能表项下发到进行拓扑变换的交换机上，将其他普通表项下发到执行路径的其余交换机上，这些流表项仅起到连接的作用。该过程可以表示为 SF⇒EF，EF={siei,1≤i≤n|e1,e2,…,em,…,en}，其中，{e1,e2,…,em}是功能表项，其余的为普通表项。

4 拓扑变换方法

拓扑变换方法其实就是在源节点附近寻找R-1个节点（R同式（2）），确保这R-1个节点在从源节点到目的节点的可达执行路径上，并满足所需的约束条件。其实就是从源地址到目的地址间找到一条链路代价最小的执行路径，执行路径中的前R个点（包含源节点在内）就是需要进行拓扑变换的节点。由第2.2节中得到执行路径的选取是0-1线性规划问题，即拓扑变换方法也是0-1线性规划问题。为求解该问题，本文基于链路代价提出一种节点搜索算法——综合搜索算法。

4.1 综合搜索算法

综合搜索算法可以减小搜索范围，在保证所选执行路径满足所需约束条件的前提下，最小化链路代价。该算法的过程是：在满足约束条件的前提下，从源节点出发搜索其邻接点中路径代价最小的点（路径代价包括两点之间的距离代价与节点的流表空间耗费之和），并将其记录；然后从该节点出发，搜索其邻接点中路径代价最小的点，参照上述过程，直到搜索到第R个（含源节点）满足条件的节点；继续搜索节点时，只考虑路径距离代价，直到搜索到目的地址为止，最终得到链路代价最小的执行路径，即最优执行路径。

算法1 综合搜索算法

输入网络拓扑G(V,L)及其邻接矩阵W、组合策略P及其目标集{src=vi,dst=vt}。

输出最优执行路径SFP及拓扑变换的节点集。

Src=vi,SF-Set=[vi] //源节点vi是执行路径的第一个

节点，SF-Set表示执行路径节点集；

for j=1:N

while(len.SF-Set＜R&&w(i,j)=1)do//从源节点出发，搜索其邻接点，w(i,j)=1表示节点vi与vj相邻；

if vj≠vi&&min f(y)then //搜索代价最小节点，并且节点集长度小于R时，搜索的节点不能是目的节点；

SF-Set=[SF-Set,vj]，i=j//更新执行路径节点集，更新搜索起点；

end if

end while

while(len.SF-Set≥R&&w(i,j)=1)do

if min h(y,n)then//当执行路径节点集大于或等于R时，以最小距离代价为条件进行搜索，当vj=vi时停止搜索；

SF-Set=[SF-Set,vj]，i=j//更新执行路径节点集，更新搜索起点；

end if

end while

end for

4.2 算法分析

在节点寻找问题上，一般使用穷举算法，从源节点出发，搜索整个拓扑中满足约束条件的节点，假设网络拓扑中有N个节点，穷举算法的时间复杂度为O((N-1)!)。而本文所提综合搜索算法综合考虑链路代价与计算复杂度，并在它们之间寻求平衡，搜索空间较小，其算法时间复杂度为O((N-1)2)。当网络中节点较多时，综合搜索算法搜索空间较小，时间复杂度较低，明显优于穷举算法。

5 实验分析

5.1 基于Ryu的原型系统实现

[12]中提出的Application-aware是在交换节点内加入功能组合模块（App和App table），数据平面通过在控制平面调用所需功能完成功能组合。然而，该方法需要修改控制平面与数据平面之间交互的OpenFlow协议，这会导致开发难度大，交换机复杂度高。参考文献[7]将功能组合模块放在控制器中，针对单节点交换机完成功能组合并下发表项，并未考虑单节点交换机功能承载力有限的问题。因此，在上述基础上将功能组合模块放置在Ryu控制器中，并且考虑到单节点功能承载力有限的问题，在模块中加入策略分析、拓扑构建、表项下发等模块，通过分析策略所需功能，完成在单节点或者多节点下发功能表项。

控制平面中引入功能组合模块改变了传统SDN处理数据流的过程。当数据流到达OpenFlow交换机时，如果数据流匹配到交换机中的流表项，则执行对该数据流的相关处理；如果未匹配成功，则将数据流头部封装分组的packet in消息上传至控制器，交由功能组合模块进行处理；数据流头部信息匹配组合策略，从而得到处理数据流所需功能，如果未匹配到相应组合策略，则交由控制器其他组件进行处理；匹配后判断是否超过单节点功能承载力，并决定将功能表项下发到单节点还是多节点交换机中，以完成对数据流的多功能处理。

为了实现文中所述功能组合方法（control plane function composition，CPFC），基于 NetFPGA-10G[13]平台和Ryu控制器设计并实现了CPFC的原型系统，如图6所示。在数据平面，采用NetFPGA-10G实验平台，现已实现最大支持OpenFlow 1.3[8]协议的4级流表串联的流水线处理机制，可实现路由、转发、计数、负载均衡等功能，为了更好地进行对照实验，实验时限制节点流表级数为两级。NetFPGA-10G板卡通过PCIe插槽插在工控机中，工控机中运行OpenFlow agent软件包，以实现与控制器的互联。控制平面采用Ryu控制器，Python语言编写的Ryu提供强大的API，有利于网络应用的开发，而且Ryu自带一些功能模块，如防火墙、路由、交换等。

5.2 功能组合性能分析

采用第5.1节提到的CPFC原型系统对CPFC的性能进行仿真分析，实验仿真拓扑如图7所示。本文采用参考文献[14]中提到的仿真验证方法，基于NetFPGA-10G构造6个交换节点，各节点由Ryu控制器控制并下发流表。该实验拓扑用来实现用户向视频服务器请求视频服务，实验时上层组合策略为＜{SrcIP=192.168.2.146,DstIP=192.168.3.3},{monitor,route,load-balance}＞，各功能表项具体如图8所示。实验时各NetFPGA-10G节点均限制为两级流表，每级流表由64条表项组成，每条表项宽度是 64 bit的匹配域（存于 TCAM中）和 380 bit的动作域（存于SRAM中）。采用综合搜索算法得到的最优路径为 E1-E3-E4-E6，因此在 E1上下发 monitor和route对应功能表项，在E3上下发 load-balance对应功能表项。

图6 CPFC原型系统

图7 实验拓扑

图8 具体功能表项

实验与参考文献[12]的数据平面组合方法（data plane function composition，DPFC）和 NFC （network function composition）[7]进行对比。实验时，CPFC的功能组合均在多节点中进行，单节点内功能组合的思想来源于NFC，后续仿真分析不再讨论。本文采用与参考文献[7]中相同的实验方法，利用数据分组测试工具packet sender从网口发送10 Gbit/s数据分组，分别记录 DPFC、NFC、CPFC 3种方法的单节点流处理时延情况，如图9所示。从图9中可以看出，NFC和CPFC的流处理时延明显低于DPFC，这是由于在控制平面调用功能模块比在数据平面调用控制平面内功能模块的时延小。随着数据分组流量的增大，3种方法的时延均变大，当数据分组流量超过单个节点的处理能力（约350 Mbit/s）时，CPFC较NFC的时延增速显著下降，这是由于CPFC将功能组合分散到多个交换机中，会减少单个交换机的负载。从图9中还可以得出，对于源地址重写所带来的时延，DPFC低于NFC和CPFC，因为对于简单的转发功能来说，DPFC可以直接在交换机中处理，而NFC和CPFC还要调用控制平面中的功能组合模块进行判断。

5.3 组合效率分析

在功能组合效率方面，Frenetic、Pyretic利用OpenFlow单级流表结构将不同功能生成表项进行合并，完成功能组合，NFC则利用OpenFlow多级流表结构，对不同功能生成表项的匹配域进行判断后，进行拆分与合并，并用多级流表进行连接；以上功能组合方法均是在单节点交换机中完成的。为与以上功能组合方法进行对比，本文采用参考文献[3，4，7]中提到的 3 类功能表项 monitor、route、load-balance进行验证，随机生成1 000～7 000次组合策略，得到不同功能组合方法生成表项的时间，如图10所示。Frenetic和Pyretic分别是在单级流表上引入功能并行组合与串行组合方法，这两种方法需要判断表项匹配域的可合并性以及对表项进行合并，所以时间复杂度较高，表项生成时间较长。NFC利用多级流表结构分别实现功能串行和并行组合，由于多级流表表项合并流程复杂度比单级流表高，所以NFC时间复杂度最高。而所提功能组合方法直接对各个功能表项进行下发和连接，省去了表项合并的时间，因此表项生成时间最短，即功能组合效率最高。

图9 流处理时延对比

5.4 表项存储开销分析

对于两个功能产生的表项，A有M条，B有N条，则Pyretic的存储开销为M×N，因为A和B的每一条表项均需要进行合并；NFC的存储开销则与多级流表结构有关，若交换机有K级流表，则其存储开销近似为(M×N)/K；CPFC则直接将不同功能的表项下发至不同交换机的流表，因此其存储开销为M+N；当M和N较大时，CPFC的存储开销更低。考虑到匹配域字段放在TCAM中，动作字段放在SRAM中。采用第5.3节中提到的3种功能表项，图11给出了4种功能组合方法对应表项存储开销对比。NFC由于使用多级流表结构对匹配域进行判断合并，所以该方法较Frenetic与Pyretic节省了宝贵的TCAM资源。CPFC方法也使用多级流表并将不同功能表项下发到不同交换机的流表，在SRAM资源占用比NFC高约6%的情况下，能够节省约25%的TCAM资源。由于TCAM的成本远高于SRAM，因此CPFC能够节省一定的交换机存储开销。

图10 表项生成时间对比

图11 表项存储开销对比

6 结束语

针对SDN中单节点功能组合无法满足多功能组合需求的问题，提出了一种基于拓扑变换的功能组合方法，并设计和实现了相应的功能组合模块。当业务功能需求大于单节点交换机的功能承载力时，对底层抽象拓扑进行虚拟变化，把原来在单节点内进行的功能组合分散到多节点中进行。实验结果表明，该方法提高了组合效率并且降低了流处理时延，而且也节省了交换机存储开销。

参考文献：

[1]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.

[2]SHIN M K,NAM K H,KIM H J.Software-defined networking(SDN): A reference architecture and open APIs[C]//International Conference on ICT Convergence,October 15-17,2012,Jeju Island,Korea.New Jersey:IEEE Press,2012:360-361.

[3]MONSANTO C,REICH J,FOSTER N,etal.Composing software defined networks[C]//NSDI,April 3-5,2013,Lombard,IL,USA.New York:ACM Press,2013:1-13.

[4]FOSTER N,HARRISON R,FREEDMAN M J,et al.Frenetic:a network programming language[C]//ACM SIGPLAN Notices,March 3-7,2011,Las vegas,USA.New York:ACM Press,2011,46(9):279-291.

[5]MONSANTO C,FOSTER N,HARRISON R,et al.A compiler and run-time system for network programming languages[J].ACM SIGPLAN Notices,2012,47(1):217-230.

[6]Open Networking Foudation. OpenFlow_v1.0 [EB/OL].(2016-01-03)[2016-04-10].https://archive.openflow.org/wk/index.php/OpenFlow_v1.0,2016.

[7]段通,兰巨龙,胡宇翔,等.SDN中一种基于多级流表的功能组合方法[J].电子学报,2015.DUAN T,LAN J L,HU Y X,et al.A function composition method of software-defined network based on multiple tables[J].Accepted by Chinese Journal of Electronics,2015.

[8]Open Networking Foudation. OpenFlow1.3,OpenFlowswitch specification 1.3.0[EB/OL].(2012-02-10)[2016-04-10].https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/OpenFlow/OpenFlow-spec-v1.3.0.pdf,2012.

[9]段通,兰巨龙,程国振,等.基于元能力的 SDN功能组合机制[J].通信学报,2015,36(5):19-2015178.DUAN T,LAN J L,CHENG G Z,et al.SDN function combination mechanism based on meta-ability[J].Journal of Communications,2015,36(5):19-2015178.

[10]兰巨龙,程东年,胡宇翔.可重构信息通信基础网络体系研究[J].通信学报,2014(1):128-139.LAN J L,CHENG D N,HU Y X.Reconfigurable network system based on information and communication research[J].Journal of Communications,2014(1):128-139.

[11]Ryu Framework Community.Ryu controller project[EB/OL].(2014-01-20)[2016-04-10].https://osrg.github.io/ryu,2014.

[12]HESHAM M,FANG H,SARIT M,et al.Application-aware data plane processing in SDN[M].New York:Acm Press,2014:13-18.[13]Github. NetFPGA-10G project [EB/OL]. (2014-01-10)[2016-04-10].https://github.com/NetFPGA-public/wiki,2014.

[14]GIBB G,ZENG H,MCKEOWN N.Outsourcingnetwork functionality[C]//The Workshop on Hot Topics in Software Defined Networks,March 5-10,2012,Las vegas,USA.New York:ACM Press,2012:73-78.

A function composition method of software defined networking based on topology transformation

XI Xiaoqiang,LAN Julong,DUAN Tong,JIANG Yiming
National Digital Switching System Engineering&Technology Research Center,Zhengzhou 450002,China

The existing function composition methods of software defined networking(SDN)are mostly carried out in the single node without considering the function bearing capacity of the single switch.To solve this problem,firstly a function composition method based on topology transformation was proposed to carry out function composition in multiple nodes by transforming abstract topology.Secondly,the topology transformation was modeled as the 0-1 linear programming problem and a comprehensive search algorithm was proposed to solve this problem.Finally,the function composition module and implemented the prototype system based on NetFPGA-10G and Ryu controller were devised to do the function composition.The experimental results show that the method can reduce processing delay and storage cost as well as improve the composition efficiency compared with the existing method.

software defined networking,topology transformation,function composition,NetFPGA-10G

s:The National Basic Research Program of China(973 Program)(No.2012CB315901,No.2013CB329104)，The National Natural Science Foundation of China（No.61372121,No.61309019,No.61502530），The National High Technology Research and Development Program of China(863 Program)(No.2013AA013505,No.2015AA016102)

TP393

10.11959/j.issn.1000-0801.2016175

2016-05-10；

2016-06-14

国家重点基础研究发展规划(“973”计划)基金资助项目(No.2012CB315901,No.2013CB329104)；国家自然科学基金资助项目(No.61372121,No.61309019,No.61502530)；国家高技术研究发展计划(“863”计划)基金资助项目(No.2013AA013505,No.2015AA016102)