一种软件定义网络中鲁棒的多控制器优化部署方法，包括：S100：分析网络拓扑结构；S200：构建相关数学模型；S300：近似算法的选取和求解。该方法将SDN网络多控制器部署问题抽象化为一个图论问题，通过建立数学模型将该图论问题转化为整数线性规划问题，利用近似算法对该问题进行求解的策略。所述方法使得SDN网络图在任意移除k条边的情境下既满足给定的控制器覆盖率，又能兼顾网络传输效率和负载均衡。
1.一种软件定义网络中鲁棒的多控制器优化部署方法，包括如下步骤：S100：分析网络拓扑结构；
S101：将软件定义网络SDN中的多控制器部署问题抽象化为一个基于无向网络图的图论问题；
S102：提出一种新的度量，控制覆盖率指标，用于表示能访问到控制器的交换机总数占网络中所有交换机总数的比例；
给定一个无向网络图G(V，L)和控制器覆盖率Cpr，通过合理部署控制器所放置的节点集C，使得该无向网络图在任意移除k条边的情境下，标记为 既满足给定的控制器覆盖率Cpr，又能兼顾网络传输效率和负载均衡，其中，V表示交换机集合，在无向网络图中用节点表示，且n表示节点的个数，即n＝|V|，L表示连接交换机的链路集合，在无向网络图中用边表示，C表示控制器节点集合，即控制器所连接的交换机节点集合，在无向网络图G中移除任意边的情景集合，记为S，移除k条边的情境集合，记为Sk， 移除k条边的一种情境，记为sk，sk∈Sk，移除k条边的最坏情景记为sb，sb∈Sk， 表示任意移除k条边的连接交换机的链路集合， 表示最坏情境下移除k条边的连接交换机的链路集合，k为正整数且1≤k≤|L|；
选取兼顾网络时延和负载均衡的鲁棒的k-RCM近似最优算法，k-RCM算法包括最坏情景下移除边的GN算法，记为k-RCM-GN，对偶近似算法，记为k-RCM-DOLP，和偏远交换机节点提取算法，记为k-RCM-outliers；
所述步骤S300中的k-RCM近似最优算法具体如下：S301：给定无向网络图G(V，L)和控制器覆盖率Cpr；
S302：假设已知控制器最优部署方案中的控制器放置代价的最大值为f‘，修改fj：当fj＞f‘时，令fj＝∞，否则fj不变，其中fj表示节点j上放置控制器的代价；
S303：基于k-RCM-DOLP算法，提取偏远节点，在G中删除偏远节点集；
S304：基于k-RCM-GN算法，寻找最坏断k条边情境；
S305：基于k-RCM-DOLP算法，生成控制器放置节点集合以及各控制器的负载表；
S306：将偏远节点的控制器设置成使偏远节点受控于与其连接费用最小的控制器。
2.根据权利要求1的方法，其特征在于，优选的，具体建模如下：目标函数：约束条件：
在情景sk下，普通交换机节点i连接到控制器放置节点j的时延；
xj：是一个0-1变量，xj＝1表示节点j被选择放置控制器，否则为0；
是一个0-1变量，表示节点i在情景sk中是否被控制器放置节点j覆盖，如果是，则 否则是一个0-1变量，表示节点i在情景sk中是否为偏远交换机节点，如果是，则否则i，j表示交换机集合中任意一个交换机，即i，j∈V。
3.根据权利要求2的方法，其特征在于，假设对应移除k条边的最坏情景sb的发生概率则在移除k条边的最坏情景下建模更新为：目标函数：
其中， 表示节点i在情景sb中是否为偏远交换机节点； 表示节点i在情景sb中是否被控制器放置节点j覆盖。
4.根据权利要求3的方法，其特征在于，为求解上述更新后的模型，对0-1整数进行约束松弛，建模更新为：目标函数：
5.根据权利要求4的方法，其特征在于，将上述约束条件替换为
6.根据权利要求5的方法，其特征在于，利用线性规划问题的对偶规划，建立其对应的对偶规划模型为：目标函数：
max∑i∈Vαi+n(α-1)q (L4-1)约束条件：
∑i∈Vβij≤fj j∈V (L4-2)其中，对偶变量βij表示交换机节点i对其连接的控制器节点j放置代价fj的贡献值；对偶变量αi表示交换机节点i的总消耗代价，总消耗代价包括交换机i连接其控制器j的时延cij和交换机i对其连接的控制器放置代价fj的贡献值βij；对偶变量q表示交换机总消耗代价αi的最大值。
7.根据权利要求1的方法，其特征在于，所述k-RCM-GN算法具体如下：a)初始设置，num＝0，
b)对给定无向网络图中所有边按边介数中心性进行排序，然后在无向网络图中删除边介数中心性指标最大的边l；
d)检查num是否等于k，如果num＜k，则重复步骤b和步骤c；如果num＝k，则执行步骤e；
e)SDN网络最坏情境下移除k条边的连接交换机的链路集合为
8.根据权利要求6的方法，其特征在于，所述k-RCM-DOLP算法具体如下：a)αi＝0，βij＝0，标记所有αi可增加，βij不可增加；
c)是否存在(i，j)满足αi＝cij；如果存在则判断节点j是否已选择为放置控制器的节点，如果是则标记节点i由节点j控制；如果否则标记(i，j)连接边是紧的，且βij在下次循环中可增加；如果不存在则执行下一步；
e)是否存在节点j满足限制条件∑i∈Vβij＝fj(j∈V)；如果存在则从满足限制条件∑i∈Vβij＝fj(j∈V)的节点中选择可连接的网络设备最多的节点j‘为控制器放置节点；如果不存在则执行步骤g；
f)标记可被j‘控制的网络设备，且βij和αi不在增加，i∈{可被j‘控制的网络设备}；
g)是否所有的节点已被选中，若是则结束本算法，若否则跳转执行步骤b。
9.根据权利要求1的方法，其特征在于，所述k-RCM-outliers算法具体如下：a)假设已知控制器最优部署方案中的控制器放置代价的最大值为f‘，修改fj：当fj＞f‘时，令fj＝∞，否则fj不变，其中fj表示节点j上放置控制器的代价；
b)运行k-RCM-DOLP算法，当网络中有低于(1-Cpr)*|V|个节点没有被确定为控制器或者已被控制的网络设备时，则终止k-RCM-DOLP算法，剩下的节点则为被选中的偏远节点；
c)所述偏远节点连接到最近的没有负载饱和的控制器上。
一种软件定义网络中鲁棒的多控制器优化部署方法
技术领域
[0001] 本公开属于网络技术领域，特别涉及一种软件定义网络中鲁棒的多控制器优化部署方法。
背景技术
[0002] 软件定义网络(Software defined network，SDN)采用了控制平面和数据平面相分离的网络架构，实现了网络数据转发的灵活控制。与传统网络不同，控制平面作为SDN网络的核心，控制器的优化部署牵涉到网络时延、负载和网络安全性等各方面；与传统网络类似，SDN网络在突发事件下同样面临着网络节点或链路失效的网络鲁棒性问题。
[0003] 由于控制器担负了整个网络的控制工作，控制器的处理能力及控制器与交换机之间通信的时延对整个网络的性能有着重要的影响。对于大型网络，依靠单个控制器进行流表的分发无法胜任全体交换机的需求，就需要使用分布式的多个控制器来分担整个系统的压力，然而如何在网络中部署多个控制器，即控制器部署(Control Placement，CP)仍然是一个开放的问题；SDN网络转发设备完全受控制平面控制，在网络故障情况下极易造成控制平面与转发平面间的通信中断，进而影响SDN网络的正常运行；特别是在SDN网络节点或链路失效的突发事件下，控制器部署的鲁棒性尤其需要关注。因此，研究应对事件提升SDN网络鲁棒性的控制器优化部署问题具有重要意义。
[0004] 在实际多控制器部署中，为了降低部署成本，应尽量减少控制器个数。在保证低成本的同时还要尽可能提高网络性能，交换机到控制器的平均时延应尽可能小，各控制器间负载应尽可能均衡，因而现有控制器部署策略大多考虑了控制器个数少、时延小、负载均衡的目标，鲜有考虑应对突发事件的控制器部署的鲁棒性问题。SDN网络在遭遇故障或攻击的情况下，如何通过有限的控制器优化配置改善SDN网络控制器服务的可生存性是非常值得研究的。
发明内容
[0005] 为了解决上述问题，本公开提供了一种软件定义网络中鲁棒的多控制器优化部署方法，包括如下步骤：
[0006] S100：分析网络拓扑结构
[0007] S101：分析网络拓扑结构，将软件定义网络SDN中的多控制器部署问题抽象化为一个基于无向网络图的图论问题；
[0008] S102：提出一种新的度量，控制覆盖率指标，用于表示能访问到控制器的交换机总数占网络中所有交换机总数的比例；
[0009] S200：构建相关数学模型
[0010] 给定一个无向网络图G(V，L)和控制器覆盖率Cpr，通过合理部署控制器所放置的节点集C，使得该无向网络图在任意移除k条边的情境下，标记为 既满足给定的控制器覆盖率Cpr，又能兼顾网络传输效率和负载均衡，其中，V表示交换机集合，在无向网络图中用节点表示，且n表示节点的个数，即n＝|V|，L表示连接交换机的链路集合，在无向网络图中用边表示，C表示控制器节点集合，即控制器所连接的交换机节点集合，在无向网络图G中移除任意边的情景集合，记为S，移除k条边的情境集合，记为sk，移除k条边的最坏情景记为sb，sb∈sk， 表示任意移除k条边的连接交换机的链路集合，表示最坏情境下移除k条边的连接交换机的链路集合，k为正整数且1≤k≤|L|；
[0011] S300：近似算法的选取和求解
[0012] 选取兼顾网络时延和负载均衡的鲁棒的k-RCM近似最优算法，k-RCM算法主要包括最坏情景下移除边的GN算法，记为k-RCM-GN，对偶近似算法，记为k-RCM-DOLP，和偏远交换机节点提取算法，记为k-RCM-outliers。
[0013] 通过上述技术方案，本公开能够合理部署最优的控制器资源，使得SDN网络在任意移除k条链路的情境下交换机到控制器的平均时延以及控制器之间的平均时延尽可能小，并使各控制器分配的负载尽可能均衡，提高鲁棒性的控制器放置问题。
附图说明
[0014] 图1是本公开一个实施例中所提供的一种软件定义网络中鲁棒的多控制器优化部署方法的流程示意图；
[0015] 图2是本公开一个实施例中k-RCM近似最优算法的流程示意图；
[0016] 图3是本公开一个实施例中k-RCM-DOLP算法的流程示意图；
[0017] 图4a-4b是本公开一个实施例中OS3E网络控制器放置结果对比图；
[0018] 图5是本公开一个实施例中OS3E网络分支定界算法的负载情况；
[0019] 图6是本公开一个实施例中OS3E网络k-RCM-DOLP算法的负载情况；
[0020] 图7是本公开一个实施例中OS3E网络依次断边时的控制覆盖节点数对比图；
[0021] 图8是本公开一个实施例中OS3E网络随机模拟断边概率对比图；
[0022] 图9是本公开一个实施例中OS3E网络中在移除边的最坏情景下的TE指标对比图；
[0023] 图10是本公开一个实施例中US Carrier网络k-RCM近似算法控制器配置及负载结果；
[0024] 图11是本公开一个实施例中US Carrier网络依次移除边控制覆盖节点数对比图；
[0025] 图12是本公开一个实施例中US Carrier网络在移除边的最坏情景下的TE指标对比图。
具体实施方式
[0026] 为解决SDN网络中鲁棒的多控制器部署问题，需要首先建立k-链路失效的鲁棒控制器部署(Robust Control Placement for k-links-failure，k-RCM)问题的整数线性规划(Integer linear programming，ILP)模型，该模型通过优化配置最小代价的控制器资源，以满足任意k-链路失效情况下SDN网络中控制器的控制覆盖率。为进一步方便求解，对该整数线性规划模型进行松弛，建立k-RCM的线性规划模型，继而利用线性规划问题的对偶规划，并借鉴设施选址求解问题思路，采用兼顾网络时延和负载均衡的鲁棒的k-RCM近似最优算法，简称为k-RCM算法，k-RCM算法能显著降低直接求解k-RCM问题模型的计算复杂性。
[0027] 参见图1，在一个实施例中，其公开了一种软件定义网络中鲁棒的多控制器优化部署方法，包括如下步骤：
[0028] S100：分析网络拓扑结构
[0029] S101：分析网络拓扑结构，将软件定义网络SDN中的多控制器部署问题抽象化为一个基于无向网络图的图论问题；
[0030] S102：提出一种新的度量，控制覆盖率指标，用于表示能访问到控制器的交换机总数占网络中所有交换机总数的比例；
[0031] S200：构建相关数学模型
[0032] 给定一个无向网络图G(V，L)和控制器覆盖率Cpr，通过合理部署控制器所放置的节点集C，使得该无向网络图在任意移除k条边的情境下，标记为 既满足给定的控制器覆盖率Cpr，又能兼顾网络传输效率和负载均衡，其中，V表示交换机集合，在无向网络图中用节点表示，且n表示节点的个数，即n＝V，L表示连接交换机的链路集合，在无向网络图中用边表示，C表示控制器节点集合，即控制器所连接的交换机节点集合，在无向网络图G中移除任意边的情景集合，记为S，移除k条边的情境集合，记为sk， 移除k条边的最坏情景记为sb，sb∈sk， 表示任意移除k条边的连接交换机的链路集合，表示最坏情境下移除k条边的连接交换机的链路集合，k为正整数且1≤k≤|L|；
[0033] S300：近似算法的选取和求解
[0034] 选取兼顾网络时延和负载均衡的鲁棒的k-RCM近似最优算法，k-RCM算法主要包括最坏情景下移除边的GN算法，记为k-RCM-GN，对偶近似算法，记为k-RCM-DOLP，和偏远交换机节点提取算法，记为k-RCM-outliers。
[0035] 在另一个实施例中，将k-RCM问题建模为整数线性规划(integer linear programming，ILP)模型，简称为k-RCM_ILP模型。建模k-RCM_ILP模型包括以下内容：
[0036] 目标函数：
[0037]
[0038] 约束条件：
[0039]
[0040]
[0041]
[0042]
[0043] 其中：
[0044] n：表示SDN网络中节点的数量；
[0045] Sk：表示移除k条边的所有情境集合；
[0046] sk：表示移除k条边的情境集合，
[0047] sb：对应该移除k条边的最坏情景；
[0048] 情景sk出现的概率，
[0049] fj：在节点j上放置控制器的代价；
[0050] 在情景sk下，普通交换机节点i连接到控制器放置节点j的时延；
[0051] Cpr：表示给定的SDN控制器覆盖率；
[0052] xj：是一个0-1变量，xj＝1表示节点j被选择放置控制器，否则为0；
[0053] 是一个0-1变量，表示节点i在情景sk中是否被控制器放置节点j覆盖，如果是，则 否则
[0054] 是一个0-1变量，表示节点i在情景sk中是否为偏远交换机节点，如果是，则否则
[0055] i，j表示交换机集合中任意一个交换机，即i，j∈V，k为正整数且1≤k≤|L|。
[0056] 需要说明的是，上述整数线性规划模型目标是通过优化部署最少的控制器节点，使得SDN网络在移除k条边的任意情境下也能保证控制覆盖率Cpr的要求，并且兼顾改善SDN网络的控制器传输效率。目标函数式(L1-1)中，使用节点的时延指标 来控制候选配置节点的传输效率；使用控制器配置代价fj参数使得控制覆盖率不低于Cpr的同时，使控制器的配置代价最小。
[0057] 约束式(L1-2)控制在所有情境中，节点j已经选为控制器放置节点后，才能将其他普通交换机节点i连接到该控制器上。若xj＝0，则 i∈V；若xj＝1，则 或0i∈V。
[0058] 约束式(L1-3)保证在所有情境中，节点要么是受控制的交换机节点，要么是偏远交换机节点。特别说明，当节点j选为控制器放置节点时
[0059] 约束式(L1-4)是非常重要的约束条件，指出在移除k条边情境下的SDN网络控制覆盖率，应不低于给定的SDN网络控制覆盖率Cpr。
[0060] 最后，约束式(L1-5)表明变量xj、 和 都是0-1变量。
[0061] 由于在SDN网络中寻找部分节点放置控制器，使得控制器在任意断k条边的情景中满足Cpr的控制器覆盖率要求，该问题已证明属于NPC问题。为简化问题求解，模型更新为在移除k条边的最坏情景下，如何优化配置有限的控制器资源，使得SDN网络既能满足给定的控制覆盖率需求，又能兼顾网络传输效率和负载均衡。
[0062] 在另一个实施例中，假设最坏断边情景sb的发生概率 在移除k条边的最坏情景下，k-RCM问题的整数线性规划模型k-RCM_ILP如下：
[0063] 目标函数：
[0064]
[0065] 约束条件：
[0066]
[0067]
[0068]
[0069]
[0070] 其中，i，j表示交换机集合中任意一个交换机，即i，j∈V。
[0071] 在另一个实施例中，为求解L2，对0-1整数进行约束松弛，建立其对应的线性规划模型k-RCM_LP为：
[0072] 目标函数：
[0073]
[0074] 约束条件：
[0075]
[0076]
[0077]
[0078]
[0079] 其中，i，j表示交换机集合中任意一个交换机，即i，j∈V。
[0080] 优选的，考虑到整数求解复杂度相对高，将整数约束修改为线性约束可明显降低算法复杂度，所以将约束条件
[0081] 替换为
[0082] 在另一个实施例中，利用线性规划问题的对偶规划，建立其对应的对偶规划模型k-RCM-DOLP为：
[0083] 目标函数：
[0084] max∑i∈Vαi+n(α-1)q (L4-1)
[0085] 约束条件：
[0086] ∑i∈Vβij≤fjj∈V (L4-2)
[0087]
[0088]
[0089]
[0090] 其中，对偶变量βij表示交换机节点i对其连接的控制器节点j放置代价fj的贡献值；对偶变量αi表示交换机节点i的总消耗代价，总消耗代价包括交换机i连接其控制器j的时延cij和交换机i对其连接的控制器放置代价fj的贡献值βij；对偶变量q表示交换机总消耗代价αi的最大值；i，j表示交换机集合中任意一个交换机，即i，j∈V；n表示网络中节点的个数。
[0091] 控制器是一种服务器资源，需要连接在某台交换机上，所以控制器资源优化部署的位置是指控制器所连接的交换机节点的位置。此外，为了进一步降低控制器资源部署的成本，优化网络控制管理的效率，引入了控制覆盖率指标Cpr，该指标表示能访问到控制器的交换机总数占网络中所有交换机总数的比例。Cpr指标定义为Cpr＝nc/n，其中，nc表示能访问到控制器资源的控制覆盖节点总数，即它包括能访问控制器资源的普通交换机节点，也包括部署了控制器资源的控制器节点自身，n表示网络中所有交换机总数。给定满足需求的控制覆盖率表明突发事件下不要求网络中的交换机被控制器完全覆盖，在不影响网络基本服务功能情况下，允许极个别的偏远交换机(也称为“outlies”)访问不到控制器。
[0092] 介数中心性指标反映了节点和边的信息处理能力和信息传递速率。边介数中心性定义为网络中任意节点对基于最短路径通过该边的所有路径的数目。本方法中移除k条边的最坏情境中的每一条移除边，都是按照网络图中边介数中心性指标的降序排列顺序逐个移除得到的。
[0093] 参见图2，在另一个实施例中，其公开了k-RCM近似最优算法，具体如下：
[0094] S301：给定无向网络图G(V，L)和控制器覆盖率Cpr；
[0095] S302：假设已知控制器最优部署方案中的控制器放置代价的最大值为f‘，修改fj：当fj＞f‘时，令fj＝∞，否则fj不变，其中fj表示节点j上放置控制器的代价；
[0096] S303：基于k-RCM-DOLP算法，提取偏远节点，在G中删除偏远节点集；
[0097] S304：基于k-RCM-GN算法，寻找最坏断k条边情境；
[0098] S305：基于k-RCM-DOLP算法，生成控制器放置节点集合以及各控制器的负载表；
[0099] S306：将偏远节点的控制器设置成使偏远节点受控于与其连接费用最小的控制器。
[0100] 在另一个实施例中，鉴于经典的社区发现GN算法在提取出社区结构的同时能以最快的速度将网络分割成相对均匀的子网，基于GN算法提出的k-RCM-GN算法可实现在SDN网络中移除k条边的最坏情境刻画，进而支持k-RCM算法在兼顾负载均衡的同时提高控制器部署节点对链接失效的鲁棒性，具体如下：
[0101] a)初始设置，num＝0，
[0102] b)对给定无向网络图中所有边按边介数中心性进行排序，然后在无向网络图中删除边介数中心性指标最大的边l；
[0103] c)修正num＝num+1，
[0104] d)检查num是否等于k，如果num
[0105] e)SDN网络最坏情景中断的k条边的集合为
[0106] 当SDN网络中有社团结构时，k-RCM-GN算法可以提取出社团结构。利用社团结构的稠密性，进一步可利用k-RCM-DOLP算法在社团中选择传输效率最高且代价最小的控制器配置节点集合。如果社团结构中的任意节点由该社团中的控制器节点所控制，则可以显著提高控制器节点面对链接失效时的鲁棒性。当SDN网络中无明显的社团结构时，k-RCM-GN算法以最快的速度将网络分割成较均匀的多个不连通子网。进一步利用k-RCM-DOLP算法在各个子网中选择传输效率最优且代价最小的控制器部署方案，使各子网中控制器节点管理对应子网中的交换机节点，从而能有效改善控制器负载均衡的问题。
[0107] 在另一个实施例中，SDN网络中偏远的交换机节点(outliers)对控制器优化部署会产生较大的影响，不仅会降低网络的传输效率，也会使改善网络鲁棒性付出很高的代价。在最坏情景下移除k条边时，为使控制器覆盖尽可能多的节点，采用k-RCM-outliers算法。
在不考虑偏远节点影响的情况下放置控制器，从而降低偏远节点对控制器覆盖率的影响。
所述k-RCM-outliers算法具体如下：
[0108] a)假设已知控制器最优部署方案中的控制器放置代价的最大值为f′，修改fj：当fj＞f′时，令fj＝∞，否则fj不变，其中fj表示节点j上放置控制器的代价；
[0109] b)运行k-RCM-DOLP算法，当网络中有低于(1-Cpr)*|V|个节点没有被确定为控制器或者已被控制的网络设备时，则终止k-RCM-DOLP算法，剩下的节点则为被选中的偏远节点；
[0110] c)这些偏远节点连接到最近的没有负载饱和的控制器上。
[0111] 上述算法将偏远节点连接到最近的没有负载饱和的控制器上，从而实现对偏远节点的管理和控制。
[0112] 参见图3，在另一个实施例中，为寻找最小最优的控制器配置集合，满足给定的SDN网络控制覆盖率和保证网络传输效率，采用了对偶近似算法k-RCM-DOLP。所述k-RCM-DOLP算法具体如下：
[0113] a)αi＝0，βij＝0，标记所有αi可增加，βij不可增加；
[0114] b)对可增加的αi有αi＝αi+1；
[0115] c)是否存在(i，j)满足αi＝cij；如果存在则判断节点j是否已选择为放置控制器的节点，如果是则标记节点i由节点j控制；如果否则标记(i，j)连接边是紧的，且βij在下次循环中可增加；如果不存在则执行下一步；
[0116] d)对可增加的βij有βij＝βij+1；
[0117] e)是否存在节点j满足限制条件∑i∈Vβij＝fj(j∈V)；如果存在则从满足上述限制条件的节点中选择可连接的网络设备最多的节点j‘为控制器放置节点；如果不存在则执行步骤g；
[0118] f)标记可被j‘控制的网络设备，且βij和αi不在增加，i∈{可被j‘控制的网络设备}；
[0119] g)是否所有的节点已被选中，若是则结束本算法，若否则跳转执行步骤b。
[0120] 下面实施例结合附图4-12进行阐述。
[0121] 在一个实施例中，如图4a-4b所示的OS3E网络中，假设在节点效率最高的节点13上放置了一个控制器，正常网络环境下，网络中的所有节点都能高效地访问到节点13上的控制器。基于边介数中心指标降序排列，在移除9条边(即)的最坏情景
下，基于k-RCM算法、k-median近似算法和分支定界算法优化部署OS3E网络控制器的能力分析如下。
[0122] 假设给定的控制覆盖率为85％，分支定界算法得到的最优内容配置节点集合为C＝{2，13，16，28，31}，负载情况见附图5；相同情况下，基于k-RCM算法得到的最优控制器配置节点集合为C＝{2，6，13，29，32}，负载情况见附图6。图4a中×表示的是k-median算法考虑最坏时延时的控制器分布情况，○表示的是k-median算法考虑平均时延时的控制器分布情况；图4b中×表示分支定界算法得到的控制器分布情况，○表示的是k-RCM算法得到的控制器分布情况。
[0123] 鲁棒性：
[0124] 图7描述了控制覆盖率指标随着最坏情景下移除边数目的增加而下降的趋势，通过比较k-median算法基于平均时延、k-median算法基于最坏时延、分支定界算法和基于k-RCM算法配置的控制器配置情况的控制覆盖率指标的变化，从图中数据分析可知：基于k-RCM算法的控制器配置结果能显著地改善OS3E网络在k链路失效时的控制器覆盖率。
[0125] 图8描述了根据基于k-median算法平均时延、基于k-median算法最坏时延、分支定界算法和基于k-RCM算法配置的控制器配置情况，在OS3E网络中，模拟105次随机断l＝{1，2，3…10}条边的实验，统计在105次实验中，控制覆盖率低于Cpr要求水平的概率值。从图中数据分析可知：随机模拟实验中对比k-median算法考虑平均时延算法、分支定界算法以及k-RCM算法比k-median算法考虑最坏时延的算法鲁棒性有着明显的提升。
[0126] 传输效率：
[0127] 由于在任意断边之后可能造成网络不再连通，因此部分交换机节点到控制器节点的时延为无穷大，致使网络的平均时延无法计算和比较，所以选用时延的倒数也就是效率指标来衡量控制器部署结果的优劣。在SDN网络中，网络传输效率指标(Transmission Efficiency，简称TE)定义为， 其中，si＝maxj∈c1/dij(i∈V/C)表示交换机节点i能访问到最近的即效率最高的控制器节点j，dpq表示控制器节点对p和q之间最短路径上的边数。传输效率指标TE中的第一项∑i∈v/Csi用来描述SDN网络中普通的交换机节点访问控制器节点的效率，第二项用来描述任意一对控制器节点对之间交换信息的难以程度。SDN网络传输效率指标TE越大，表明网络中交换机访问控制器资源以及控制器之间交换信息越容易，SDN网络传输效率越高。
[0128] 图9描述了TE指标随着最坏情景下移除边数目的增加而下降的趋势。由图9可知当OS3E网络中依次断3到15条边时，k-RCM算法的效率一直处于最高点，即传输效率最大。由此可知，不论是对于SDN网络的控制器覆盖率指标，还是对于控制器的传输有效性指标，以及负载均衡指标，具有低的计算复杂性的k-RCM近似算法都可以获得较高的控制器优化配置能力。
[0129] 在另一个实施例中，如图10所示的US Carrier中，假设给定的控制覆盖率Cpr＝85％。对于k-RCM近似算法，在移除边的最坏情景下，为保证满足控制覆盖率Cpr，得到的最
0
优控制器配置节点集合V＝{6，18，28，39，48，60，67，69，86，91，99，102，116，136}，负载情况见图10中不同的颜色标记，相同颜色的节点由同一个控制器所管理。在相同情况下，基于分支定界算法得到的最优控制器配置节点集合V0＝{2，10，18，28，40，48，60，70，81，91，99，
102，125，136}。
[0130] 图11描述了控制覆盖节点数随着移除边数目的增加而下降的趋势变化，通过比较分支定界算法和k-RCM近似算法变化分析可知，具有低计算复杂性的k-RCM算法对改善SDN网络的控制覆盖节点数的优势非常明显。图12描述了传输效率TE指标随着移除边数目的增加而下降的趋势，我们得出具有低计算复杂性的k-RCM算法对改善SDN网络的控制传输效率的优势明显，k-RCM算法不仅能有效地改善SDN网络在链路失效时的控制覆盖节点数，也能明显地改善控制器有效性，同时具有负载均衡处理能力。
[0131] 综上，从图4a到图12可以分析得出，在移除SDN网络中边的最坏情境下，基于有限SDN网络控制器的优化配置k-RCM算法可以有效地改善SDN网络面对链接失效时的控制覆盖率和控制有效性指标，能够提升控制器服务的可生存性，并且可以解决无链接失效时的负载均衡问题。此外，通过对比分析可知，不论是对控制覆盖节点数的影响，还是对TE指标的影响，具有低的计算复杂性的k-RCM算法与具有高的计算复杂性的分支定界算法相比，k-RCM算法同样具有较高的SDN网络控制器优化部署能力。
[0132] 尽管以上结合附图对本发明的实施方案进行了描述，但本发明并不局限于上述的具体实施方案和应用领域，上述的具体实施方案仅仅是示意性的、指导性的，而不是限制性的。本领域的普通技术人员在本说明书的启示下和在不脱离本发明权利要求所保护的范围的情况下，还可以做出很多种的形式，这些均属于本发明保护之列。
