姚琳元 陈 颖 宋 飞 张宏科



基于时延的软件定义网络快速响应控制器部署

姚琳元*陈 颖 宋 飞 张宏科

(北京交通大学下一代互联网互联设备国家工程实验室 北京 100044)

目前大多数针对软件定义网络(SDN)中控制器的部署方案均重点考虑传输时延(PD)对性能的影响，忽略了发送时延(TD)对于部署效果的影响。该文提出基于时延的网络快速响应控制器部署方案。首先，在合理考虑传输和发送两类时延的基础上，完善了已有的平均时延/最大时延最小化模型，并对两种模型是否存在最优解进行了理论证明；其次，利用模糊集理论得出了一种时延优化模型；第三，结合是否考虑发送时延提出了两种部署算法：传输算法和输送算法。为了测试方案的性能，选取实际网络拓扑及数据进行验证。结果表明输送算法在网络的响应速度及稳定性方面优于传输算法，时延优化模型在总时延方面较平均时延/最大时延最小化模型效果更优。

软件定义网络；部署；控制器；时延

1 引言

软件定义网络(Software-Defined Network, SDN)是由美国斯坦福大学Cleanslate研究组[1]提出的一种基于集中控制的新型网络架构[2]。在不改变传统IP数据包转发行为的基础上，SDN将传统路由器/交换机的数据转发与逻辑控制进行分离，实现数据域与控制域的解耦[3,4]。在数据域中，SDN定义为交换机(Switch)负责数据包的接收、存储和转发。在控制域中，SDN定义为控制器(Controller)负责网络的顶层设计，与交换机连接；收集网络信息，实现全局处理；通过控制交换机的流表项指导交换机对数据包的处理，实现网络的集中管理，为用户提供更好、更便捷的网络服务[5,6]。

良好的上网体验，要求网络畅达、快速，而合理、方便地部署控制器显得尤为重要。当今，核心网设备的部署已趋于固定，重新搭建网络拓扑不符合绿色、节能、便捷等现代网络理念[7]。在已铺设的网络架构基础上进行优化，与现有网络实现良好的硬件连接和逻辑连接是SDN发展的必然趋势。与此同时，SDN在设计之初就确定了数据转发与控制相分离的基本思想，采用集中式管理，实现网络的一致性，势必要求网络的快速响应[8]。在已有网络的基础上，考虑控制器的部署位置是实现网络快速响应的有效方式之一。

文献[9]首次提出了SDN网络中控制器的部署问题：(1)网络中需要多少个控制器；(2)怎么部署控制器。为实现定量分析，作者首先定义了两个测试参数平均时延和最大时延；然后，利用真实拓扑结构进行分析，包括：控制器数量对时延的影响，平均时延与最优时延的对比等；最后，引入交换速度、环保护和网络恢复3个网络时间参数，综合考虑网络对时延的需求，提出一个控制器即可满足当下网络的响应要求。在分析过程中，文献[9]只考虑了传输时延，忽略了发送时延对网络响应速率的影响。

文献[10, 11]分别从网络可靠性和网络弹性两个角度对控制器的部署进行了分析、建模。文献[10]提出了一个新的参量，即可预期控制链路亏损百分比(Expected Percentage of Control Path Loss)，并从可靠性的角度对SDN中控制器的部署进行了分析。文献提出了4种不同的部署算法，利用真实拓扑对算法进行了验证，其中模拟退火法(Simulated Annealing)优于其他算法；认为控制器的数量应适当选择，过多或过少都会影响网络的可靠性。文献[11]从网络弹性和容错的角度对SDN中控制器的部署进行了分析，应用帕累托优化理论，实现网络弹性和网络容错的权衡；通过对OS3E拓扑及拓扑动物园(Topology Zoo)中的大量拓扑进行分析，认为保证网络的连续，网络中至少要有20%的节点设置为控制器。

文献[12]充分利用固定式网络微积分结构，建立数学模型，解决了SDN在部署过程中的可扩展性问题。文中将控制器分为本地控制器(Local Controller)和超级控制器(Root Controller)，利用数学模型从本地控制器中获取固定格式的事件时延和缓存长度，利用经典的排队理论解决了边界和最差条件下的两种部署情况。另外，文献[12]建立了一个控制器互动分析模型，该模型给出了控制器的进程、流量控制函数，利于网络设计人员计算出控制器的时延和缓存需求。对于下一步工作，文章提出了两个方向的目标：(1)采用随机网络微积分的方法对SDN中的部署问题进行研究，完成相关仿真和实验工作；(2)在参照边界条件的同时，考虑均衡条件下的平均值。

通过对相关控制器部署方案的研究，本文提出了一种基于传输时延和发送时延的网络快速响应控制器部署方案。首先，完善平均时延和最大时延最小化模型，在此基础上，推导出时延优化模型；其次，提出了解决上述模型的基于传输时延和发送时延的输送算法(Transmission and Propagation Algorithm, TPA)以及基于传输时延的传输算法(Propagation Algorithm, PA)；最后，利用实际拓扑数据，完成数据仿真，得出不同模型最佳部署方案以及对应的平均时延、最大时延和总时延，并与相关部署方案进行了对比、分析。

2 模型假设及理论证明

网络时延的主要衡量标准分为平均时延和最大时延[9]，本节从传输时延和发送时延两个角度，研究平均时延和最大时延，分析网络响应速度。具体工作如下：首先设定基本假设，定义基本的参考变量，完成数学化描述，推导出参数间的数学关系；在此基础上，对现有的平均时延模型和最大时延模型进行完善，添加发送时延变量，得出平均时延最小化模型和最大时延最小化模型，并利用优化理论对上述模型是否存在最优解进行理论证明[14]；最后从上述模型中提炼出时延优化模型，引入模糊集理论[15]，给出时延优化模型的解决方案。下文的公式表示同时考虑传输时延和发送时间的数学分析模型，与第3节中TPA对应；去除所述模型中发送时延变量的数学分析模型，与第3节中PA对应，限于篇幅，本节不做说明。

2.1 基本假设和参数定义

(2)

2.2 平均时延最小化模型

2.3 最大时延最小化模型

最终数学模型为

该模型可以反应出当前部署方案下的网络最大响应时延，同时，以最大响应时延作为限制条件，找到最优部署方案，定理2是对该模型最优解的说明。

2.4 时延优化模型

3 部署算法

为验证发送时延在网络响应速度以及控制器部署等方面的重要程度，本文首先参照文献[9]，设计了PA，然后依据上文提出的传输时延和发送时延，设计了TPA。

两种算法定义网络节点到控制器的单向传输方向为数据传输方向，认为控制器的部署位置位于网络拓扑中的网络节点处，当某网络设备的位置与控制器的位置重叠时，二者的传输时延为0；当部署多个控制器，需计算其中一个控制器到网络节点的时延时，两种算法设定其余控制器和与之连接的网络节点处于不能通信状态，即传输时延设为无穷大。PA和TPA都以迪杰斯特拉(Dijkstra)算法和贪心(Greedy)算法为基础，以实际拓扑作为算法的输入，得出不同条件下的最优部署方案。二者的不同之处在于：

(1)PA将拓扑中的网络节点视为普通点，只计算传输时延，通过寻找最短路径，得到网络设备到控制器的最短距离，进而获得基于传输时延的最佳部署方案；为统一网络参数，在PA的最后，增加了发送时延，表示在网络运转情况下，即有数据在网络中传输时，网络响应时延的情况；

(2)TPA将传输时延和发送时延作为部署方案的参考因素，当计算拓扑中某个网络节点到控制器的响应时延时，TPA提出将网络节点以外的其他节点设置为与该网络节点相同的发送时延；

(3)TPA可直接使用第2节中的3个数学模型，PA在使用上述模型时，需去掉模型中的发送时延一项。

具体算法伪代码如表1和表2所示。

4 性能评估

图2为利用PA和TPA求出的3种优化模型P1, P2, P3的时延对比图，mean表示平均时延，max表示最大时延，mm表示平均时延与最大时延的和。图2(a)表示不考虑信息量I, PA得出的3种优化模型分别对应的平均时延(mean)，最大时延(max)和总时延(mm)随控制器数量增加的变化情况；图2(b)表示在图2(a)得出的3种最优部署方案下，增加I后，时延随控制器数量增加的变化情况；图2(c)表示使用TPA得出的3种优化模型分别对应的3种时延随控制器数量增加的变化情况。从图2可看出：

表1 PA算法

图1 网络拓扑图

表2 TPA算法

(1)图2(a)和图2(c)中，3种模型得到的部署方案，在PA信息量为0或TPA情况下，时延随控制器数量的增多而下降，控制器数量越多，网络的响应速率越快；

(2)图2(b)中，考虑发送时延，在图2(a)的最优部署条件下，时延随控制器数量的增多上下波动，没有固定的变化规律，不能体现控制器数量增多在部署过程中的优势；

(3)图2(b)和图2(c)中，信息量相同情况下，TPA算法的3种时延明显低于PA算法的时延。

图3(a)，图3(b)，图3(c)分别代表3种模型最优部署方案的时延情况，其中横坐标表示控制器数量，纵坐标表示同一种算法PA或TPA下的最大时延与平均时延的比值。从图3中可以看出：

(1)3种模型下，TPA的比值要明显低于PA的比值，表明在网络响应平均时延相同的情况下，TPA较PA能够实现更快的网络响应，网络节点到控制器的响应时延波动范围更小。

图2 时延比较图

图3 时延比值图

(2)通过3个子图的对比，TPA的比值比较稳定：控制器数量增多，平均时延下降，最大时延稳步降低；PA的比值变动较大，无明显规律，当控制器数量为1时，比值最小，控制器数量增多，比值大小不一。

图4(a)和图4(b)分别表示PA算法(=0)和TPA算法下，3种模型的时延比较图。从图4可以看出，模型P3的总时延取P2, P1二者中较低项，或低于二者。

从上述分析可以看出，较PA, TPA在平均时延、最大时延和总时延更低、比值更低，可以更快实现网络响应；时延优化模型较平均时延最小化模型和最大时延最小化模型在总时延更有优势，网络的响应时间更加集中。

5 结束语

在充分考虑传输时延和发送时延的前提下，本文提出了基于时延的网络控制器快速响应部署方案。已有时延模型仅考虑传输时延，在此基础上，本文增加了发送时延，得出了平均时延最小化模型和最大时延最小化模型，并结合二者特点，创建了时延优化模型，通过优化理论和模糊理论，对模型的最优解进行了论证。按照是否考虑发送时延，设计了PA和TPA，通过仿真结果我们发现，将发送时延纳入考虑范围可以增加网络的响应速度，增加网络部署的稳定性；时延优化模型可以使网络响应时间更加集中。下一步工作将利用网络仿真工具，引入节点处理时延等变量，同时从介数角度探讨网络中控制器的部署。

图4 模型比较图

[1] McKeown N, Anderson T, Balakrishnan H,.. OpenFlow: enabling innovation in campus networks[J]., 2008, 38(2): 69-74.

[2] Jain S, Kumar A, Mandal S,.. B4: experience with a globally-deployed software defined WAN[C]. The Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, Hong Kong, 2013: 3-14.

[3] ONF. software-defined networking: the new norm for networks, white paper[OL]. https://www.opennetworking. org, 2013. 12.

[4] Mueller J, Wierz A, Vingarzan D,.. Elastic network design and adaptive flow placement in software defined networks[C]. 2013 22nd International Conference on Computer Communications and Networks (ICCCN), California, 2013: 1-6.

[5] 周烨, 杨旭, 李勇, 等. 基于分类的软件定义网络流表更新一致性方案[J]. 电子与信息学报, 2013, 35(7): 1746-1752.

Zhou Ye, Yang Xu, Li Yong,.. Classification based consistent flow update scheme in software defined network[J].&, 2013, 35(7): 1746-1752.

[6] Dixit A, Hao F, Mukherjee S,.. Towards an elastic distributed sdn controller[C]. The Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, Hong Kong, 2013: 7-12.

[7] Sezer S, Scott-Hayward S, Chouhan P K,.. Are we ready for SDN? Implementation challenges for software-defined networks[J]., 2013, 51(7): 36-43.

[8] Levin D, Wundsam A, Heller B,.. Logically centralized: state distribution trade-offs in software defined networks[C]. Proceedings of the First ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, New York, 2012: 1-6.

[9] Heller B, Sherwood R, and McKeown N. The controller placement problem[C]. The First ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, New York, 2012: 7–12.

[10] Hu Y, Wendong W, Gong X,.. Reliability-aware controller placement for Software-Defined Networks[C]. 2013 IFIP/IEEE International Symposium on Integrated Network Management (IM 2013), Sophia Antipolis, 2013: 672-675.

[11] Hock D, Hartmann M, Gebert S,.. Pareto-optimal resilient controller placement in SDN-based core networks[C]. IEEE 2013 25th International Teletraffic Congress (ITC), California, 2013: 1-9.

[12] Azodolmolky S, Wieder P, and Yahyapour R. Performance evaluation of a scalable software-defined networking deployment[C]. IEEE 2013 Second European Workshop on Software Defined Networks (EWSDN), Berlin, 2013: 68-74.

[13] Kurose J F and Ross K W. Computer Networking: a Top- Down Approach Featuring the Internet[M]. India: Pearson Education, 2013: 35-44.

[14] Boyd S P and Vandenberghe L. Convex Optimization[M]. Cambridge: Cambridge University Press, 2004: 43-46, 127-152.

[15] Zadeh L A, Klir G J, and Yuan B. Fuzzy Sets, Fuzzy Logic, Fuzzy Systems[M]. Singapore, World Scientific Press, 1996: 165-175.

[16] Huang D, Yang D, Zhang H,.. Energy-aware virtual machine placement in data centers[C]. 2012 IEEE Global Communications Conference (GLOBECOM), California, 2012: 3243-3249.

[17] Christian raack. Sndlib [OL]. http://sndlib.zib.de/home. action, 2013.12.

[18] Spring N, Mahajan R, and Wetherall D. Measuring ISP topologies with rocketfuel[J]., 2002, 32(4): 133-145.

姚琳元： 男，1988年生，博士生，研究方向为下一代互联网网络层关键技术.

陈 颖： 女，1987年生，硕士生，研究方向为下一代互联网网络层关键技术.

宋 飞： 男，1983年生，副教授，硕士生导师，研究方向为下一代互联网网络层、传输层关键技术.

张宏科： 男，1957年生，教授，博士生导师，研究方向为下一代互联网架构、协议理论与技术、移动互联网络路由、传感器网络技术等.

Delay-aware Controller Placement for Fast Responsein Software-defined Network

Yao Lin-yuan Chen Ying Song Fei Zhang Hong-ke

(,,100044,)

Most of Controller placements take the Propagation Delay (PD) as the important consideration in Software-Defined Network (SDN), ignoring the influence of the Transmission Delay (TD) on the network performance.This paper provides a delay-aware controller placement for fast response. First, the Controller placement is formulated as an optimization problem based on PD and TD. Average delay and maximum delay minimization models are updated, of which the processes about the optimal solution are circumstantiated. Further, delay optimization model is deduced by fuzzy set theory. Finally, according to whether or not considering TD, two placement algorithms, Transmission and Propagation Algorithm (TPA) and Propagation Algorithm (PA), are presented. In order to measure the performance of the solutions, a factual network topology is chosen and the simulation result shows that TPA superiorities over PA in terms of response speed and network stability, the total delay of delay optimization model is less than the others.

Software-Defined Network (SDN); Placement; Controller; Delay

TP393

A

1009-5896(2014)12-2802-07

10.3724/SP.J.1146.2014.00211

姚琳元 11111020@bjtu.edu.cn

2014-02-19收到，2014-05-20改回

国家自然科学基金(61301081)，高等学校博士学科点专项科研基金(20120009120005)和中央高校科研业务费专项基金(2014JBM010)资助课题