Minimal Coverage Model for Fault-Tolerant Controller Placement in Software Defined Networks
-
摘要:
容错控制平面通过将多个控制器部署在不同的网络设备上进而增强网络的可靠性，但是大量的控制器部署带来了巨大的布局成本，严重地限制了容错控制平面在实际网络中的部署与应用。为了解决上述问题，该文首先构造了容错控制平面的最小覆盖布局模型，然后设计了一种基于局部搜索策略的启发式控制器布局算法，避免搜索结果陷入局部最优解。在不同规模网络中的仿真结果表明，相对于其他算法，所提算法可以在保证网络容错需求的同时，降低网络中部署控制器的数量。
Abstract:In order to deploy fault-tolerant Software-Defined Networks(SDN), many controllers must be physically distributed among different network devices. However, a large number of controllers bring huge costs, which limits severely the application of the fault-tolerant control plane to the real networks. In order to solve the above problems, the fault-tolerant control plane is analyzed and a mathematical model that covers all switches using the least number of controllers is constructed. Then, a heuristic controller placement algorithm based on the local search strategy is proposed to avoid the local optimal solution. The experimental results show that compared with other algorithms, the proposed algorithm can effectively reduce the number of required controllers while ensuring network fault tolerance requirements in different scale networks.
-
算法1 控制器布局搜索CAA 输入：网络拓扑$G$，交换机集合$S$ 输出：控制器布局$P$ 步骤1 计算每一个交换机的CCG 步骤2 利用式(13)计算交换机的分配顺序 步骤3 While ($S$) 步骤4 $s \leftarrow {\rm{order}}\left( S \right)$, $S \leftarrow S - \left\{ s \right\}$ 步骤5 随机选择1个${\rm{CCG}}$ 步骤6 $P \leftarrow {\rm{CCG}}$ 步骤7 ${\rm{Load}} \leftarrow {\rm{Load}}\left( P \right)$ 步骤8 利用式(11)更新交换机的分配顺序 步骤9 End While 步骤10 输出控制器布局$P$ 
下载: 导出CSV
算法2 基于局部搜索算法的控制器布局算法LSCPA 输入：网络拓扑$G$，交换机集合$S$，最大迭代次数${l_{\max }}$ 输出：优化后的控制器布局$P*$ 步骤1 运行CAA得到控制器初始布局${P_{\rm{0}}}$ 步骤2 $l = 0$ 步骤3 While ($l \le {l_{\max } }$) 步骤4 计算变异算子${\rm{wp}}$ 步骤5 ${P_{l + 1}}\mathop \leftarrow \limits^{} {\rm{Update}}\left( {{P_l}} \right)$ 步骤6 If (${\rm{Num}}\left( {{P_{l + 1}}} \right) < {\rm{Num}}\left( {{P_l}} \right)$) 步骤7 $P* = {P_{l + 1}}$ 步骤8 $l = {\rm{0}}$ 步骤9 ${P_l} = P*$ 步骤10 else 步骤11 $P* = {P_l}$ 步骤12 $l = l + 1$ 步骤13 End If 步骤14 End While 步骤15 输出控制器布局$P*$
下载: 导出CSV
-
SCOTT-HAYWARD S, NATARAJAN S, and SEZER S. A survey of security in software defined networks[J]. IEEE Communications Surveys & Tutorials, 2016, 18(1): 623–654. doi: 10.1109/COMST.2015.2453114 KILLI B P R and RAO S V. Optimal model for failure foresight capacitated controller placement in software defined networks[J]. IEEE Communications Letters, 2016, 20(6): 1108–1111. doi: 10.1109/LCOMM.2016.2550026 LI He, LI Peng, GUO Song, et al. Byzantine–resilient secure software–defined networks with multiple controllers in cloud[J]. IEEE Transactions on Cloud Computing, 2014, 2(4): 436–447. doi: 10.1109/TCC.2014.2355227 李军飞, 胡宇翔, 邬江兴. 基于拜占庭容错提高SDN控制层可靠性的研究[J]. 计算机研究与发展, 2017, 54(5): 952–960. doi: 10.7544/issn1000-1239.2017.20160055LI Junfei, HU Yuxiang, and WU Jiangxing. Research on improving the control plane’s reliability in SDN based on byzantine fault-tolerance[J]. Journal of Computer Research and Development, 2017, 54(5): 952–960. doi: 10.7544/issn1000-1239.2017.20160055 WOOD T, SINGH R, VENKATARAMANI A, et al. ZZ and the art of practical BFT execution[C]. The 6th Conference on Computer Systems, Salzburg, Austria, 2011: 123–138. doi: 10.1145/1966445.1966457. ROS F J and RUIZ P M. On reliable controller placements in software–defined networks[J]. Computer Communications, 2016, 77: 41–51. doi: 10.1016/j.comcom.2015.09.008 史久根, 谢熠君, 孙立. 软件定义网络中面向时延和负载的多控制器放置策略[J]. 电子与信息学报, 2019, 41(8): 1869–1876. doi: 10.11999/JEIT181053SHI Jiugen, XIE Yijun, and SUN Li. Multi–controller placement strategy based on latency and load in software defined network[J]. Journal of Electronics &Information Technology, 2019, 41(8): 1869–1876. doi: 10.11999/JEIT181053 史久根, 邾伟, 贾坤荥, 等. 软件定义网络中基于负载均衡的多控制器部署算法[J]. 电子与信息学报, 2018, 40(2): 455–461. doi: 10.11999/JEIT170464SHI Jiugen, ZHU Wei, JIA Kunying, et al. Multi–controller deployment algorithm based on load balance in software defined network[J]. Journal of Electronics &Information Technology, 2018, 40(2): 455–461. doi: 10.11999/JEIT170464 KILLI B P R and RAO S V. Controller placement with planning for failures in software defined networks[C]. 2016 IEEE International Conference on Advanced Networks and Telecommunications Systems, Bangalore, India, 2016: 1–6. doi: 10.1109/ANTS.2016.7947795. ELDEFRAWY K and KACZMAREK T. Byzantine fault tolerant Software–Defined Networking (SDN) controllers[C]. 2016 IEEE 40th Annual Computer Software and Applications Conference, Atlanta, USA, 2016: 208–213. doi: 10.1109/COMPSAC.2016.76. JIMÉNEZ Y, CERVELLÓ-PASTOR C, and GARCIA A J. On the controller placement for designing a distributed SDN control layer[C]. 2014 IFIP Networking Conference, Trondheim, Norway, 2014: 1–9. doi: 10.1109/IFIPNetworking.2014.6857117. XIE Junjie, GUO Deke, ZHU Xiaomin, et al. Minimal fault–tolerant coverage of controllers in IaaS datacenters[J]. IEEE Transactions on Services Computing, 2017, 36(3): 1–14. doi: 10.1109/TSC.2017.2753260 GAREY M R and JOHNSON D S. Computers and INTRACTABILITY: A GUIDE to the Theory of NP–Completeness[M]. New York: W. H. Freeman and Company, 1979: 199–201. -
下载:
计量
- 文章访问数: 1805
- HTML全文浏览量: 591
- PDF下载量: 71
- 被引次数: 0
