軟件定義網(wǎng)絡(luò)中基于效率區(qū)間的負(fù)載均衡在線優(yōu)化算法
doi: 10.11999/JEIT180464
-
合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院 ??合肥 ??230009
An Efficient Online Algorithm for Load Balancing in Software Defined Networks Based on Efficiency Range
-
School of Computer and Information, Hefei University of Technology, Hefei 230009, China
-
摘要:
在大型復(fù)雜軟件定義網(wǎng)絡(luò)中，為提高網(wǎng)絡(luò)負(fù)載均衡，減少控制器與交換機(jī)間的傳播時(shí)延，該文提出一種基于效率區(qū)間的負(fù)載均衡在線優(yōu)化算法。在初始靜態(tài)網(wǎng)絡(luò)中，通過貪心算法選擇初始控制器集合，并以其為根節(jié)點(diǎn)構(gòu)建M棵改進(jìn)代價(jià)的最小生成樹(MST)，確定初始M個(gè)負(fù)載均衡的子網(wǎng)；當(dāng)網(wǎng)絡(luò)流量發(fā)生變化時(shí)，通過廣度優(yōu)先搜索(BFS)調(diào)整子網(wǎng)間交換機(jī)映射關(guān)系使其滿足效率區(qū)間，保證任意時(shí)刻網(wǎng)絡(luò)的負(fù)載均衡。算法均以網(wǎng)絡(luò)連通性為基礎(chǔ)，且均以傳播時(shí)延為目標(biāo)重新更新控制器集合。仿真實(shí)驗(yàn)表明，該算法在保證任意時(shí)刻網(wǎng)絡(luò)負(fù)載均衡的同時(shí)，可以保證較低的傳播時(shí)延，與Pareto模擬退火算法、改進(jìn)的K-Means算法等相比，可以使網(wǎng)絡(luò)負(fù)載均衡情況平均提高40.65%。
-
關(guān)鍵詞:
- 軟件定義網(wǎng)絡(luò) /
- 控制器部署 /
- 負(fù)載均衡 /
- 傳播時(shí)延
Abstract:Due to the limitation of individual controller’s processing capacity in large-scale complex Software Defined Networks (SDN), an efficient online algorithm for load balancing among controllers based on efficiency range is proposed to improve load balancing among controllers and reduce the propagation delay between a controller and the switch. In the initial static network, the initial set of controllers is selected by a greedy algorithm, then M improved Minimum Spanning Trees (MST) rooted at the initial set of controllers are constructed, so initial M subnets with load balancing are determined. With the dynamic changes of load, for the purpose of making the controller work within efficiency range at any time, several switches in different subnets are reassigned by Breadth First Search (BFS). The initial set of controllers is updated for minimizing propagation delay in the algorithms’ last step. The algorithm is based on the connectivity of intra-domain and inter-domain. Simulation results show that the proposed algorithms not only guarantee the load balancing among controllers, but also guarantee the lower propagation delay. As to compare to PSA algorithm, optimized K-Means algorithm, etc., it can make Network Load Balancing Index (NLBI) averagely increase by 40.65%.
-
表 1 初始M控制域選擇算法
算法1：初始M控制域選擇算法(IMCDS) 輸入：$G = (V, E) , f, {\rm{MLCC}}, {T_{\rm max}}, {W}, D, {\rm{ID}}, $
$ \{ {\rm{Flag}}, {\rm{Temp}}, {\rm{ICon}}, {\rm{IS}}\} = \varnothing $輸出：${\rm{ICon}}, {\rm{IS}}$ (1) $M \leftarrow {{\displaystyle\sum\nolimits_{i = 1}^{\left| V \,\right|} {{f_i}} }}\Bigr/{{\rm{OL}}} , {\rm{OL}} = 0.85 \times {\rm{MLCC}}$; (2) ${\rm{ICon}} \leftarrow {C_1}, {C_1} \in \{ \max (D) \cap \max ({\rm{ID}})\} $; (3) Adopt $ { \rm{Prim}} ({C_1}, {W}, {\rm{OL}}) $ to construct first improved MST
based 式(11) and 式(12);(4) Update $ {\rm{IS}}_1, {\rm{Flag}}_1 \leftarrow 1, {\rm{Temp}} \leftarrow 1$; (5) do (6) ${\rm{ICon}} \leftarrow {C_i}, {C_i} \in \{ {\rm{Flag}}_i = 0 \cap {\rm{furthest \;from\;}} {\rm{ICon}} \cap $
$ \max (D) \cap \max ({\rm{ID}}),i = 1, ·\!·\!· , n\} $;(7) Adopt $ { \rm{Prim}} ({C_i}, {W}, {\rm{OL}}) $ to construct improved MST
based on 式(11) and 式(12);(8) Update $ {\rm{IS}}_i, {\rm{Flag}}_i \leftarrow 1, {\rm{Temp}} \leftarrow {\rm{Temp}} + 1$; (9) while $ {\rm{Temp}} > M, {\rm{the \ network \ has \ been \ divided \ into}} \ $ M
domains;(10) if there are nodes has not been selected do (11) Add nodes to one closest improved MST by BFS based
on 式(11) and 式(12);(12) Update ${\rm{IS}} , {\rm{Flag}} \leftarrow 1$; (13) end if (14) Update centroids ${\rm{ICon}} = \{ {C_1}, {C_2}, ·\!·\!· , {C_M}\} $ based on the
sum of the shortest distance from all switches in ${\rm{IS}} _i $ to
new controller $ {C_i}$ is minimized;(15) Output ${\rm{ICon}} , {\rm{IS}}$。 
下載: 導(dǎo)出CSV
表 2 M控制域調(diào)整算法
算法2：M控制域調(diào)整算法(M-CDA) 輸入：$G = (V, E), {T_{\max}}, f, {\rm{MLCC}}, (\alpha , \beta ), {\rm{ICon}}, {\rm IS}, T, $
$ \{ {\rm{LS}}, {\rm{LCon}}, {\rm{TNS}}\} = \varnothing $輸出：${\rm{LCon}}, {\rm{LS}}$ (1) for all $ {\rm{}} t\; {\rm{with}} \;0 \le t \le T\; $ do (2) for each $ i \in M $ do (3) ${\rm{TNS}} \leftarrow {\rm{BV}}_{i, j}, {\rm{BV}}_{i, j} \in \{ {\rm{furthest}} \;{\rm{from}} \; $
$ {\rm{ICon}}_i \cap\max \left(f_{i1}^t, ·\!·\!· ,f_{ij}^t\right) ,j \in {\rm{IS}}_i\} $;(4) end for (5) for each $ i \in M $ do (6) if $\sum\nolimits_{l = t - 1}^t {\rm{L C}}_i^l < \alpha \times {\rm{MLCC}} $ do (7) Add nodes in TNS closest from $ {\rm{ICon}}_i$ to ISi by BFS
based 式(11)，式(12)，式(13);(8) end if (9) if $\sum\nolimits_{l = t - 1}^t {\rm{L C}}_i^l > \beta \times {\rm{MLCC}} $ do (10) Add nodes in ISi furthest from ${\rm{ICon}}_i$ to TNS by BFS
based 式(11)，式(12)，式(13);(11) end if (12) end for (13) Compute function
${\rm{ }} {F_t} = \mu \times ({\rm{NLBI}}^t - 1) + \nu \times \sum\limits_{j = 1}^M {{\rm{TRDT}}_j^t} $(14) if ${F_t} < {F_{t - 1}} $ do (15) ${\rm{LS}} \leftarrow {\rm{IS}}$; (16) end if (17) end for (18) Update centroids $ {\rm{ICon}} = \{ {C_1}, {C_2}, ·\!·\!· , {C_M}\} $ based on the
sum of the shortest distance from all switches in ${\rm{}} {\rm{LS}}_i $ to
new controller Ci is minimized, ${\rm{LCon}} \leftarrow {\rm{ICon}}$;(19) Output $ {\rm{LCon}}, {\rm{LS}}$。
下載: 導(dǎo)出CSV
表 3 網(wǎng)絡(luò)拓?fù)涔?jié)點(diǎn)數(shù)和鏈路數(shù)分布
網(wǎng)絡(luò)名稱 Noel Darkstrand OS3E Arnes Ntelos Surfnet 節(jié)點(diǎn)數(shù) 19 28 34 34 48 50 鏈路數(shù) 35 31 43 49 61 73
下載: 導(dǎo)出CSV
表 4 初始靜態(tài)情況下多網(wǎng)絡(luò)拓?fù)涞呢?fù)載均衡情況
子網(wǎng)絡(luò)數(shù) Noel Darkstrand OS3E Arnes Ntelos Surfnet 2 1.05 1.00 1.00 1.00 1.00 1.00 3 1.10 1.07 1.06 1.06 1.00 1.02 4 1.26 1.14 1.06 1.06 1.08 1.04 5 1.05 1.07 1.03 1.18 1.25 1.20 6 1.26 1.06 1.06 1.06 1.13 1.08 7 1.48 1.25 1.03 1.23 1.17 1.12 8 1.52 1.43 1.18 1.41 1.17 1.12
下載: 導(dǎo)出CSV
表 5 動(dòng)態(tài)情況下多網(wǎng)絡(luò)拓?fù)涞呢?fù)載均衡情況
子網(wǎng)絡(luò)數(shù) Noel Darkstrand OS3E Arnes Ntelos Surfnet 2 1.08 1.04 1.02 1.04 1.03 1.05 3 1.09 1.10 1.08 1.11 1.06 1.03 4 1.18 1.23 1.12 1.16 1.08 1.09 5 1.20 1.25 1.13 1.23 1.18 1.15 6 1.34 1.28 1.26 1.28 1.12 1.31 7 1.41 1.33 1.38 1.36 1.33 1.24 8 1.51 1.48 1.26 1.34 1.23 1.18
下載: 導(dǎo)出CSV
-
HLLER B, SHEERWOOD R, and MCKEOWN N. The controller placement problem[J]. ACM Sigcomm Computer Communication Review, 2012, 42(4): 473–478. doi: 10.1145/2377677.2377767 KOPONEN T, CASADO M, GUDE N, et al. Onix: A distributed control platform for large-scale production networks[C]. Usenix Conference on Operating Systems Design and Implementation, Vancouver, Canada, 2010: 351–364. TOOTOONCHIAN A and GANJALI Y. HyperFlow: A distributed control plane for OpenFlow[C]. Internet Network Management Conference on Research on Enterprise Networking, San Francisco, USA, 2010: 3–8. YU M, REXDORD J, FREEDMAN M J, et al. Scalable flow-based networking with DIFANE[J]. ACM Sigcomm Computer Communication Review, 2010, 40(4): 351–362. doi: 10.1145/1851275.1851224 WANG Guodong, ZHAO Yanxiao, HUANG Jun, et al. A K-means-based network partition algorithm for controller placement in software defined network[C]. IEEE International Conference on Communicat–uala Lumpur, Malaysia, 2016: 1–6. 張棟, 郭俊杰, 吳春明. 層次型多中心的SDN控制器部署[J]. 電子學(xué)報(bào), 2017, 45(3): 680–686. doi: 10.3969/j.issn.0372-2112.2017.03.027ZHANG Dong, GUO Junjie, and WU Chunming. Controller placement based on hierarchical multi-center SDN[J]. Acta Electronica Sinica, 2017, 45(3): 680–686. doi: 10.3969/j.issn.0372-2112.2017.03.027 SAHOO K S, SAHOO B, DASH R, et al. Optimal controller selection in software defined network using a greedy-SA algorithm[C]. International Conference on Computing for Sustainable Global Development, New Delhi, India, 2016: 2342–2346. 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 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 JIMENEZ Y, CERVALLO-PASTOR C, and GARCIA A J. On the controller placement for designing a distributed SDN control layer[C]. NETWORKING Conference, Trondheim, Norway, 2014: 1–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): 4–17. doi: 10.1109/TNSM.2015.2402432 JALILI A, AHMADI V, KESHTGARI M, et al. Controller placement in software-defined WAN using multi objective genetic algorithm[C]. International Conference on Knowledge-Based Engineering and Innovation, Tehran, Iran, 2016: 656–662. RATH H K, REVVOORI V, NADAF S M, et al. Optimal controller placement in software defined networks (SDN) using a non-zero-sum game[C]. International Symposium on A World of Wireless, Mobile and Multimedia Networks, Sydney, Australia, 2014: 1–6. 史久根, 邾偉. 軟件定義網(wǎng)絡(luò)中基于負(fù)載均衡的多控制器部署算法[J]. 電子與信息學(xué)報(bào), 2018, 40(2): 455–461. doi: 10.11999/JEIT170464SHI Jiugen and ZHU Wei. 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 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 覃匡宇, 黃傳河, 王才華, 等. SDN網(wǎng)絡(luò)中受時(shí)延和容量限制的多控制器均衡部署[J]. 通信學(xué)報(bào), 2016, 37(11): 90–103. doi: 10.11959/j.issn.1000-436x.2016219QIN Kuangyu, HUANG Chuanhe, WANG Caihua, et al. Balanced multiple controllers placement with latency and capacity bound in software-defined network[J]. Journal on Communications, 2016, 37(11): 90–103. doi: 10.11959/j.issn.1000-436x.2016219 -
計(jì)量
- 文章訪問數(shù): 2223
- HTML全文瀏覽量: 797
- PDF下載量: 73
- 被引次數(shù): 0
下載:
