軟件定義網(wǎng)絡(luò)中面向時延和負載的多控制器放置策略
doi: 10.11999/JEIT181053
-
合肥工業(yè)大學計算機與信息學院 合肥 230009
基金項目: 國家重大科學儀器設(shè)備開發(fā)專項(2013YQ030595)
Multi-controller Placement Strategy Based on Latency and Load in Software Defined Network
-
School of Computer and Information, Hefei University of Technology, Hefei 230009, China
Funds: The National Major Scientific Instruments Development Project (2013YQ030595)
-
摘要: 在多控制器管理的軟件定義網(wǎng)絡(luò)(SDN)中，時延和負載是控制器放置問題(CPP)要考慮的重要因素。該文以降低控制器之間的傳播時延、流請求的傳播時延和排隊時延、均衡控制器間負載為目標，提出一種控制器放置及動態(tài)調(diào)整的策略，其中包括用于初始控制器放置的負載均衡算法(BCRA)和遺傳算法(GA)，用于動態(tài)調(diào)整控制器負載的在線調(diào)整算法(ADOA)。以上算法均考慮網(wǎng)絡(luò)連通性。仿真結(jié)果表明：在初始控制器放置時，在保證流請求的傳播時延、排隊時延和控制器傳播時延較低的情況下，BCRA部署在中小型網(wǎng)絡(luò)中時，其負載均衡性能與GA相近且優(yōu)于k-center和k-means算法；GA部署在大型網(wǎng)絡(luò)中時，與BCRA, k-center和k-means算法相比，使得負載均衡率平均提高了49.7%。在動態(tài)情況下，與現(xiàn)有動態(tài)調(diào)整算法相比，ADOA可以保證較低排隊時延和運行時間的同時，仍能使負載均衡參數(shù)小于1.54。
-
關(guān)鍵詞:
- 軟件定義網(wǎng)絡(luò) /
- 控制器放置 /
- 負載均衡 /
- 網(wǎng)絡(luò)時延 /
- 動態(tài)調(diào)整
Abstract: In Software Defined Networks (SDN), latency and load are important factors for Controller Placement Problem (CPP). To reduce the transmission latency between controllers, the propagation latency and queuing latency of flow requests, and balance the controller load, a strategy on how to place and adjust the controller is proposed. It mainly includes Genetic Algorithm (GA) and Balanced Control Region Algorithm (BCRA) which are used to place the initial controller and one Algorithm of Dynamic Online Adjustment (ADOA), that is an online adjusting algorithm in term dynamic controlling. The above algorithms are all based on the network connectivity. The simulation results show that in initial controller placement situation, under the premise of guaranteeing the lower propagation latency, queue latency and controller transmission latency of flow request, when BCRA is deployed in small and medium-sized networks, its load balancing performance is similar to that of GA and superior to k-center and k-means algorithm; When GA is deployed in large networks, compared with BCRA, k-center and k-means, the load balancing rate increases averagely 49.7%. In the dynamic situation, ADOA can guarantee lower queuing delay and running time, and can still make the load balance parameter less than 1.54. -
表 1 BCRA算法
算法1 BCRA算法 輸入：圖$G(V,E)$, ${\lambda _{i,j}}$, ${\rm{Cons}}$, ${\rm{C}}{{\rm{A}}_{{\rm{cons}}}}$, $C\;$//${\rm{C}}{{\rm{A}}_{{\rm{cons}}}}$, $C\;$都是空集 輸出：$F$的值，控制器集合$C$和子網(wǎng)集合${\rm{C}}{{\rm{A}}_{{\rm{cons}}}}$ (1) 計算各個節(jié)點的度$D$; //步驟(1)～步驟(10)是網(wǎng)絡(luò)劃分階段；
(2) 計算$k = \sum\nolimits_{j = 1}^n {{\lambda _j}} /{\rm{LCPmax}}$; //${\lambda _j}$表示第$j$個交換機流量，${\rm{LCPmax}}$表示最大負載；(3) while $\left| C\, \right| < k$ (4) 如果算法第1次執(zhí)行，則選擇度最大的節(jié)點${\rm{Cons}}$作為控制器節(jié)點；否則，從剩余節(jié)點中找到度最大的節(jié)點并組成集合，再從該集
合中選擇距離當前控制器節(jié)點最近的點${\rm{Cons}}$作為新的控制器節(jié)點；(5) 將節(jié)點${\rm{Cons}}$加入控制器集合$C$； (6) while ${\rm{LC}}{{\rm{P}}_{{\rm{cons}}}} < {\mu _{{\rm{cons}}}}$//基于${\rm{Con}}$使用廣度優(yōu)先搜索方法構(gòu)建樹； (7) 選擇離${\rm{Con}}$最近且未被分配的節(jié)點$j$，將其加入${\rm{C}}{{\rm{A}}_{{\rm{cons}}}}$； (8) end while (9) end while (10) 找到每個控制器對應的交換機集合$\left\{ {{\rm{C}}{{\rm{A}}_{{\rm{cons}}}}} \right\} ,{\rm{cons}} \in C\;$,計算$F\;$的值并記為${\rm{Fold}}$； (11) while ${\rm{BL}} - 1 > \xi $//$\xi $是一個極小值，步驟(11)—步驟(19)是子網(wǎng)調(diào)整階段； (12) 找到負載最大的控制器${\rm{Cons}}$的子網(wǎng)，并計算子網(wǎng)內(nèi)的邊界交換機與相鄰控制器之間的距離； (13) 預先計算將距離最小的交換機分配給相鄰控制器后的$F$的值，并標記為${\rm{Fnew}}$； (14) if ${\rm{Fnew}} \le {\rm{Fold}}$ (15) 將距離最小的交換機分配給相鄰控制器，并令${\rm{Fold = Fnew}}$；
(16) 更新交換機集合$\left\{ {{\rm{C}}{{\rm{A}}_{{\rm{cons}}}}} \right\}$并計算$\sum\nolimits_{j \in {\rm{C}}{{\rm{A}}_{{\rm{cons}}}}} {\lambda _{{\rm{cons}},j}^{}} $；(17) end if (18) $F = {\rm{Fold}}$； (19) end while (20) 輸出$F,C,\left\{ {{\rm{C}}{{\rm{A}}_{{\rm{cons}}}}} \right\}$ 
下載: 導出CSV
表 2 BLA算法
算法2 BLA算法 輸入：圖$G(V,E)$, ${\lambda _{i,j}}$, ${\mu _i}$, ${\rm{CA}}$, $C\,$//${\rm{CA}}$是空集 輸出：適應度函數(shù)值$F$ (1) for $i \in C$ (2) 選擇節(jié)點$j$，其滿足離控制器$i$最近且未被標記；
(3) if $\sum\nolimits_{j \in {\rm{C}}{{\rm{A}}_i}} {{\lambda _{i,j}}} < {\mu _i}$(4) 將節(jié)點$j$加入${\rm{C}}{{\rm{A}}_i}$； (5) end if (6) end for (7) 找到每個控制器對應的交換機集合$\left\{ {{\rm{C}}{{\rm{A}}_i}} \right\} ,i \in C\,$，計算
$F\,$的值并記為${\rm{Fold}}$；(8) 接著調(diào)用BCRA的子網(wǎng)調(diào)整階段算法；//即算法1的步
驟(11)—步驟(19)；(9) 輸出$F$
下載: 導出CSV
表 3 ADOA算法
算法3 ADOA算法 輸入：${\rm{C}}{{\rm{A}}_i}$, ${\lambda _{i,j}}$, ${\mu _i}$, $C$, ${\rm{LC}}{{\rm{P}}_i}^{}$, $D$ 輸出：${\rm{C}}{{\rm{A}}_{i,o}}$ (1) while ${\rm{LC}}{{\rm{P}}_i}$改變并且${\rm{T}}{{\rm{q}}_i} > {\rm{Tqmax}}$ (2) 選擇當前子網(wǎng)中度最大的節(jié)點$o$作為從控制器； (3) for $j \in {\rm{C}}{{\rm{A}}_i}$ (4) 如果${\rm{LC}}{{\rm{P}}_o} > {\rm{LC}}{{\rm{P}}_i}$，則跳出當前循環(huán)并轉(zhuǎn)入步驟2； (5) if 相對于控制器$i$，節(jié)點$j$離控制器$o$近； (6) 預先計算將$j$分配給$o$后的${\rm{T}}{{\rm{q}}_o}$； (7) 如果${\rm{T}}{{\rm{q}}_o} < {\rm{Tqmax}}$，則令$j \in {\rm{C}}{{\rm{A}}_{i,o}}$且$j \notin {\rm{C}}{{\rm{A}}_i}$； (8) end if (9) end for (10) end while (11) 輸出${\rm{C}}{{\rm{A}}_{i,o}}$
下載: 導出CSV
-
HELLER B, SHERWOOD R, and MCKEOWN N. The controller placement problem[J]. ACM SIGCOMM Computer Communication Review, 2012, 42(4): 473–478. doi: 10.1145/2377677.2377767 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 and Service Management, 2015, 12(1): 4–17. doi: 10.1109/TNSM.2015.2402432 ZHANGA Bang, WANG Xingwei, and HUANG Min. Multi-objective optimization controller placement problem in internet-oriented software defined network[J]. Computer Communications, 2018, 123: 24–35. doi: 10.1016/j.comcom.2018.04.008 JALILI A, KESHTGARI M, and AKBARI R. Optimal controller placement in large scale software defined networks based on modified NSGA-II[J]. Applied Intelligence, 2018, 48(9): 2809–2823. doi: 10.1007/s10489-017-1119-5 HU Ying, LUO Tao, BEAULIEU N C, et al. The energy-aware controller placement problem in software defined networks[J]. IEEE Communications Letters, 2017, 21(4): 741–744. doi: 10.1109/LCOMM.2016.2645558 SALLAHI A and ST-HILAIRE M. Optimal model for the controller placement problem in software defined networks[J]. IEEE Communications Letters, 2015, 19(1): 30–33. doi: 10.1109/LCOMM.2014.2371014 JIMÉNEZ Y, CERVELLÓ-PASTOR C, and GARCÍA A. 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. YAO Guang, BI Jun, LI Yuliang, et al. On the capacitated controller placement problem in software defined networks[J]. IEEE Communications Letters, 2014, 18(8): 1339–1342. doi: 10.1109/LCOMM.2014.2332341 HUQUE M T I U, SI Weisheng, JOURJON G, et al. Large-scale dynamic controller placement[J]. IEEE Transactions on Network and Service Management, 2017, 14(1): 63–76. doi: 10.1109/TNSM.2017.2651107 SOOD K and XIANG Yong. The controller placement problem or the controller selection problem?[J]. Journal of Communications and Information Networks, 2017, 2(3): 1–9. doi: 10.1007/s41650-017-0030-x WANG Guodong, ZHAO Yanxiao, HUANG Jun, et al. An effective approach to controller placement in software defined wide area networks[J]. IEEE Transactions on Network and Service Management, 2018, 15(1): 344–355. doi: 10.1109/TNSM.2017.2785660 高先明, 王寶生, 鄧文平, 等. SDN網(wǎng)絡(luò)中控制器放置問題綜述[J]. 通信學報, 2017, 38(7): 155–164. doi: 10.11959/j.issn.1000-436x.2017136GAO Xianming, WANG Baosheng, DENG Wenping, et al. Survey of controller placement problem in software defined network[J]. Journal on Communications, 2017, 38(7): 155–164. doi: 10.11959/j.issn.1000-436x.2017136 WANG Tao, LIU Fangming, and XU Hong. An efficient online algorithm for dynamic SDN controller assignment in data center networks[J]. IEEE/ACM Transactions on Networking, 2017, 25(5): 2788–2801. doi: 10.1109/TNET.2017.2711641 HU Tao, GUO Zehua, YI Peng, et al. Multi-controller based software-defined networking: A survey[J]. IEEE Access, 2018, 6: 15980–15996. doi: 10.1109/ACCESS.2018.2814738 WANG Guodong, ZHAO Yanxiao, HUANG Jun, et al. On the data aggregation point placement in smart meter networks[C]. The 26th International Conference on Computer Communication and Networks, Vancouver, Canada, 2017: 1–6. doi: 10.1109/ICCCN.2017.8038499. 史久根, 邾偉, 賈坤滎, 等. 軟件定義網(wǎng)絡(luò)中基于負載均衡的多控制器部署算法[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 WANG Guodong, ZHAO Yanxiao, HUANG Jun, et al. A K-means-based network partition algorithm for controller placement in software defined network[C]. 2016 IEEE International Conference on Communications, Kuala Lumpur, Malaysia, 2016: 1–6. doi: 10.1109/ICC.2016.7511441. BARI M F, ROY A R, CHOWDHURY S R, et al. Dynamic controller provisioning in software defined networks[C]. The 9th International Conference on Network and Service Management, Zurich, Switzerland, 2013: 18-25. doi: 10.1109/CNSM.2013.6727805. -
圖(6) / 表(3)
計量
- 文章訪問數(shù): 1908
- HTML全文瀏覽量: 1088
- PDF下載量: 79
- 被引次數(shù): 0
下載:
