0 引言

    软件定义网络(Software Defined Networking，SDN)的核心思想在于控制层和转发层的分离，OpenFlow^[1]协议为实现其倡导的网络控制提供可编程接口，能够极大简化网络管理工作。随着SDN网络应用规模的扩大，这种集中工作模式很可能成为其在WAN中的瓶颈点^[2]。为提升网络扩展性、可靠性，多控制器部署的思路逐渐受到较多的关注。

    多控制器的部署问题可以归纳为：给定一个网络拓扑，需要多少个控制器能够满足网络需求，以及如何为这些控制器寻找最优位置进行部署。文献[3，4]中明确将确定控制器数量及位置的问题定义为控制器部署问题（Controller Placement Problem，CPP）。通过文中分析可以看到，现有研究方向都在向优化目标的选择集中，因此控制器部署问题是一个NP难问题。

    本文提出故障场景度量值的概念来寻求控制器部署的解决方案，将节点间控制路径连通度作为实施控制器放置的首要指标。

1 相关工作

    目前对于CPP的研究主要集中在两个方向进行：基于时延优化和基于可靠性优化。基于时延优化主要利用聚类思想来部署控制器及其交换机集合。该部署思想目前主要有基于平均时延、最坏情况时延^[5]等部署方法。基于可靠性优化的控制器部署研究集中于控制层，主要围绕三方面展开：(1)路径可靠性^[6]；(2)节点可靠性^[7]；(3)负载均衡^[8]。也有研究从多目标整合优化的角度来进行基于可靠性部署问题的研究^[9]。

    针对SDN的可靠性研究分为数据层可靠性和控制层可靠性两方面：(1)数据层可靠性：SHARMA S等人^[10]利用OpenFlow1.1协议的故障转移机制来实现数据层的故障恢复，提出并评估两种不同的复原方式的性能。(2)控制层可靠性：控制层可靠性研究分为控制器及其控制路径两部分。控制器的可靠性是指应对控制器故障的可靠性保证，这类可靠性可以通过提升控制器自身的可靠性（如使用更加可靠的硬件）或使用多个备份控制器的方式得到改善^[10]。

    现有OpenFlow广域网部署可由两种网络类型来实现：带内网络（in-band networks）和带外网络（out-of-band networks），如图1、图2所示。在带内网络中，OpenFlow流能够共享常规网络流的相同路径。在基于OpenFlow的广域网中使用带内部署更加合理。根据OpenFlow1.3.2协议，控制器到交换机的通信路径实际上取决于IP路由协议。在广域网中，通常每一对设备之间具备多条可用路径，当前路径失效时，其他路径能够快速取代并传输OpenFlow信息。因此增强OpenFlow控制通道的多路性能够提升OpenFlow广域网的恢复能力。

2 故障场景模型描述

    本文的优化目标在于合理选取控制器的部署位置，具备限制同时故障发生数的能力，在失效场景中控制路径减少的情况下，使失联节点数最小化，从而保证系统可靠性。将网络拓扑模型化为G(V，E)，其中V表示节点设备，E表示节点间的网络链路，文中符号参数定义如表1所示。

2.1 故障场景度量值建模

    在故障场景f_k中，为便于实验分析，使用平均链路失效概率来衡量该故障场景的整体失效概率。

    遍历所有可能的故障场景，寻找使式(3)具有最小值的节点i作为控制器部署位置，此时能够确保节点i对控制路径具有最低的故障发生概率。

    式（4）～式（7）是约束条件。式（4）是故障场景度量值的取值范围；式（5）表示控制器处于活跃状态时，c_i取值为1，否则为0；式（6）表示在故障场景f_k中该节点与所有节点路径连通度小于设定阈值，则f_k(C_i)为1，否则为0；式（7）表示出现故障f_k时，其所有的链路失效概率取值在0～1之间；式（8）表示首先为每个控制器分配r个交换机，如果有剩余，再根据节点连通度大小将其分配给某个控制器。

2.2 基于路径连通度的域内交换机选取策略

    本文考虑寻找节点连通度最大的节点作为交换机集合来增强该控制器的控制路径连通效能。

    定义1　控制路径连通度。选定每个控制器放置节点后，优先选取与控制器节点路径连通度最大的前r个交换机作为该控制器域内交换机集合。用控制器部署位置与节点间不相交路径平均数定义路径连通度，表示如下：

    设定路径连通度阈值m_thre，当节点路径连通度小于m_thre时，即认为节点间连通度不足。

2.3 控制路径选取策略

    所有路径具有相同失效概率时，为提高流运转效率，应寻找最大剩余带宽路径，选择该路径作为首要控制路径并将其他路径作为备份路径。

    定义2　最大剩余带宽路径。式（10）实现选择节点a与节点b之间最大剩余带宽路径p，如下所示：

    路径的带宽容量取决于组成该路径链路中的最小带宽链路，如下式所示：

    路径p剩余带宽B_res(p)由路径p可用带宽减去已占用带宽B_al(p)求得：

3 控制器部署算法

    本节设计基于贪婪的控制器放置算法实现控制器部署。便于与现有的随机放置算法和Survivor^[6]方法进行对比。 

3.1 基于贪婪的控制器放置算法

    基于贪婪的控制器放置算法(Greedy-Based Controller Placement，GBCP)使用聚类思想寻找控制器及其域内管控节点集合。在完成所有迭代后，如果存在剩余节点，通过计算剩余节点与各个控制器之间的连通性关系，再将其分配至各个控制器域。

    基于贪婪的控制器放置算法（GBCP）：

    输入：G=(V，E)，控制器数m，故障场景集合F；

    输出：C，S_u。

(1)i=0，V₁=V

(2)for u in V₁

(3)计算u在所有已知可能的故障场景F中的f(C_i)，并升序排序；

(4)选择具有最小f(C_i)的节点u（如有多个相同的节点，则随机选择），加入控制器集合C中；

(5)通过式(9)选取出与节点u连通度最大的前r个点作为该控制域内的交换机集合S_u；

(6)把节点u和集合S_u内的所有节点从集合V₁中移除；

(7)i=i+1  

(8)if i<m：返回以上for循环；

(9)else if i=m：

(10)if V₁≠φ：

(11)for v in V₁

(12)计算v 和集合C中各控制器的连通性关系，并将其分配至连通度最大的控制器域中；

(13)end for

(14)end for

3.2 其他算法介绍

    该两种方案是现有的用来获取m个控制器位置实现控制器部署的实施方案。

    （1）随机放置算法（random）：该算法是随机地在所有可能的V个节点中选取m个位置作为控制器部署节点。

    （2）Survivor：该方法通过明确考虑路径多样性从而增强节点连通性；在控制器部署中增加容量感知机制，主动避免控制器的过载问题；通过控制器容量的备用剩余容量实现故障恢复机制。

4 性能评估

    为方便实验，设定每个实验场景中所有链路具有相同的链路失效概率，因此实验中使用链路失效概率来量化故障场景度量值。 

    在Internet 2、RNP、GEANT、GOODNET、ARPANET19719等网络拓扑实施如下实验内容：（1）使用GBCP部署方法，计算出控制器数目变化与控制路径损失率的关系；设定所有路径故障概率都为0.05；（2）在GBCP部署方法得到最佳控制器数目时，通过平均路径失效概率的变化，观察各部署方案的网络拓扑中控制路径的损失情况；（3）对比使用本文提出的部署方案，每个网络拓扑中部署不同数目的控制器对应时延变化情况。

    图3是控制器数目与控制路径损失率之间的对应关系，其中m/n表示控制器数目m与交换机节点数目n之间的比率。分析发现，以上5种实验拓扑的曲线变化具有相似的特征，并且m的取值在0.073n～0.164n之间具有最佳的控制路径可靠性。这是因为尽管广域网中通常需要较多的控制器来保证可靠性，但控制器数目不断地增加又会造成控制器与交换机之间的路径连通度降低，控制路径损失也相应地增加。因此实际网络拓扑中的控制器部署需谨慎选择控制器的数目。

    在实验（1）中已经获知，GBCP的部署方案在每个网络拓扑中都有相似的性能表现，因此仅选取Internet 2(m=0.122n)测试3种部署方法得到的路径失效概率与控制路径损失率的关系。图4是路径失效概率与控制路径损失率之间的关系。随着路径失效概率的上升，控制路径损失率也呈现增加的趋势；相同路径失效概率时，Survivor控制路径损失率始终最低，random最高。在路径失效概率为0.1时，random控制路径损失率高达54%。相比随机放置算法，使用最大路径连通效能的部署方案能够降低路径损失率，提升控制路径可靠性。

    现有研究表明，每个控制器在200 ms时限内可以保证流安装时间的一致性^[11]。实验（1）在5种拓扑进行实验的同时，对其相应时延情况也做了统计。图5、图6分别是控制器数目变化与平均时延^[3]和最坏情况时延^[3]的关系。控制器数取值在区间（0.073n，0.164n）之间时，平均时延最大值为18 ms，最坏情况时延最大值为83 ms。文中基于可靠性优化的控制器部署方案选取最优控制器数目后所产生的时延仍然在控制器可承受的性能范围内，从而保证SDN网络在基于可靠性进行控制器部署时不受时延约束。

5 结语

    本文利用最大化控制路径可靠性的思想来解决SDN中的控制器部署问题。使用故障场景度量值的方法来保证控制路径失效率最小化，并权衡可靠性与时延的关系。通过使用不同的放置算法进行实验，得到以下结论：控制器部署的性能取决于使用的控制器部署方法；必须合理选择控制器数目；基于可靠性优化得到的最优控制器部署，其产生的时延在控制器响应时间限制范围内。

参考文献

[1] GUDE N，KOPONEN T，PETTIT J，et al.NOX：towards an operating system for networks[J].Acm Sigcomm Computer Communication Review，2008，38(3)：105-110.

[2] TOOTOONCHIAN A，GANJALI Y.HyperFlow：a distributed control plane for OpenFlow[C].Internet Network Management Conference on Research on Enterprise NETWORKING，Washington，DC，2010.USENIX Association，2010.

[3] HELLER B，SHERWOOD R，MCKEOWN N.The controller placement problem[J].Acm Sigcomm Computer Communication Review，2013，42(4)：7-12.

[4] UL HUQUE M T I，JOURJON G，GRAMOLI V.Revisiting the controller placement problem[C].IEEE，Conference on Local Computer Networks，Clearwater，Florida，USA，2015.IEEE Computer Society，2015：450-453.

[5] 姚琳元，陈颖，宋飞，等.基于时延的软件定义网络快速响应控制器部署[J].电子与信息学报，2014(12)：2802-2808.

[6] MULLER L F，OLIVEIRA R R，LUIZELLI M C，et al.Survivor：An enhanced controller placement strategy for improving SDN survivability[C].IEEE Global Communications Conference，2014：1909-1915.

[7] ZHANG Y，BEHESHTI N，TATIPAMULA M.On resilience of split-architecture networks[C].Global Telecommunications Conference(GLOBECOM 2011)，2011，2011：1-6.

[8] GUO Z，SU M，XU Y，et al.Improving the performance of load balancing in software-defined networks through load variance-based synchronization[J].Computer Networks，2014，68(11)：95-109.

[9] LANGE S，GEBERT S，ZINNER T，et al.Heuristic approaches to the controller placement problem in large scale SDN networks[J].IEEE Transactions on Network & Service Management，2015，12(1)：1.

[10] SHARMA S，STAESSENS D，COLLE D，et al.Enabling fast failure recovery in OpenFlow networks[C].International Workshop on the Design of Reliable Communication Networks，Drcn，2011.Krakow，Poland，2011：164-171.

[11] ABBAS G.Network survivability[M].Springer US，2006.

作者信息:

毛  明，陈庶樵，崔世建

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