軟件定義網(wǎng)絡(luò)容錯(cuò)控制平面的最小覆蓋布局方法
doi: 10.11999/JEIT190972
-
中國人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 鄭州 450001
Minimal Coverage Model for Fault-Tolerant Controller Placement in Software Defined Networks
-
PLA Strategic Support Force Information Engineering University, Zhengzhou 450001, China
-
摘要:
容錯(cuò)控制平面通過將多個(gè)控制器部署在不同的網(wǎng)絡(luò)設(shè)備上進(jìn)而增強(qiáng)網(wǎng)絡(luò)的可靠性，但是大量的控制器部署帶來了巨大的布局成本，嚴(yán)重地限制了容錯(cuò)控制平面在實(shí)際網(wǎng)絡(luò)中的部署與應(yīng)用。為了解決上述問題，該文首先構(gòu)造了容錯(cuò)控制平面的最小覆蓋布局模型，然后設(shè)計(jì)了一種基于局部搜索策略的啟發(fā)式控制器布局算法，避免搜索結(jié)果陷入局部最優(yōu)解。在不同規(guī)模網(wǎng)絡(luò)中的仿真結(jié)果表明，相對于其他算法，所提算法可以在保證網(wǎng)絡(luò)容錯(cuò)需求的同時(shí)，降低網(wǎng)絡(luò)中部署控制器的數(shù)量。
-
關(guān)鍵詞:
- 軟件定義網(wǎng)絡(luò) /
- 錯(cuò)誤容忍 /
- 控制器布局 /
- 最小覆蓋
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 輸入：網(wǎng)絡(luò)拓?fù)?G$，交換機(jī)集合$S$ 輸出：控制器布局$P$ 步驟1 計(jì)算每一個(gè)交換機(jī)的CCG 步驟2 利用式(13)計(jì)算交換機(jī)的分配順序 步驟3 While ($S$) 步驟4 $s \leftarrow {\rm{order}}\left( S \right)$, $S \leftarrow S - \left\{ s \right\}$ 步驟5 隨機(jī)選擇1個(gè)${\rm{CCG}}$ 步驟6 $P \leftarrow {\rm{CCG}}$ 步驟7 ${\rm{Load}} \leftarrow {\rm{Load}}\left( P \right)$ 步驟8 利用式(11)更新交換機(jī)的分配順序 步驟9 End While 步驟10 輸出控制器布局$P$ 
下載: 導(dǎo)出CSV
算法2 基于局部搜索算法的控制器布局算法LSCPA 輸入：網(wǎng)絡(luò)拓?fù)?G$，交換機(jī)集合$S$，最大迭代次數(shù)${l_{\max }}$ 輸出：優(yōu)化后的控制器布局$P*$ 步驟1 運(yùn)行CAA得到控制器初始布局${P_{\rm{0}}}$ 步驟2 $l = 0$ 步驟3 While ($l \le {l_{\max } }$) 步驟4 計(jì)算變異算子${\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*$
下載: 導(dǎo)出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 李軍飛, 胡宇翔, 鄔江興. 基于拜占庭容錯(cuò)提高SDN控制層可靠性的研究[J]. 計(jì)算機(jī)研究與發(fā)展, 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 史久根, 謝熠君, 孫立. 軟件定義網(wǎng)絡(luò)中面向時(shí)延和負(fù)載的多控制器放置策略[J]. 電子與信息學(xué)報(bào), 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 史久根, 邾偉, 賈坤滎, 等. 軟件定義網(wǎng)絡(luò)中基于負(fù)載均衡的多控制器部署算法[J]. 電子與信息學(xué)報(bào), 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. -
計(jì)量
- 文章訪問數(shù): 1952
- HTML全文瀏覽量: 677
- PDF下載量: 71
- 被引次數(shù): 0
下載:
