基于可靠性的5G網(wǎng)絡(luò)切片在線映射算法

唐倫; 趙國繁; 楊恒; 趙培培; 陳前斌

doi:10.11999/JEIT171119

基于可靠性的5G網(wǎng)絡(luò)切片在線映射算法

doi: 10.11999/JEIT171119 cstr: 32379.14.JEIT171119

重慶郵電大學(xué)移動通信技術(shù)重點實驗室 ??重慶 ??400065

基金項目: 國家自然科學(xué)基金(61571073)，重慶市科委重點產(chǎn)業(yè)共性關(guān)鍵技術(shù)創(chuàng)新專項(cstc2015zdcy-ztzx40008)

詳細信息

作者簡介:
唐倫：男，1973年生，教授，博士，研究方向為新一代無線通信網(wǎng)絡(luò)、異構(gòu)蜂窩網(wǎng)絡(luò)、軟件定義無線網(wǎng)絡(luò)等

趙國繁：女，1993年生，碩士生，研究方向為5G網(wǎng)絡(luò)切片中的資源分配、可靠性

楊恒：男，1993年生，碩士生，研究方向5G網(wǎng)絡(luò)切片、虛擬資源分配

趙培培：女，1993年生，碩士生，研究方向為5G網(wǎng)絡(luò)切片映射算法

陳前斌：男，1967年生，教授，博士生導(dǎo)師，研究方向為個人通信、多媒體信息處理與傳輸、下一代移動通信網(wǎng)絡(luò)、異構(gòu)蜂窩網(wǎng)絡(luò)等

通訊作者:
唐倫　 tangl@cqupt.edu.cn

中圖分類號: TN929.5
計量
- 文章訪問數(shù): 2020
- HTML全文瀏覽量: 963
- PDF下載量: 99
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2017-11-28
- 修回日期: 2018-05-09
- 網(wǎng)絡(luò)出版日期: 2018-06-07
- 刊出日期: 2018-08-01

Online Mapping Algorithm Based on Reliability for 5G Network Slicing

Key Laboratory of Mobile Communication Technology, Chongqing University of Post and Telecommunications, Chongqing 400065, China

Funds: The National Natural Science Foundation of China (61571073), The Chongqing Science and Technology Commission Key Industry Common Technology Innovation Special Project (cstc2015zdcy-ztzx40008)

摘要

摘要: 為了滿足業(yè)務(wù)多樣性對5G網(wǎng)絡(luò)切片帶來差異化需求的同時保證切片的可靠性，實現(xiàn)網(wǎng)絡(luò)資源的優(yōu)化配置。該文針對5G網(wǎng)絡(luò)切片的動態(tài)映射、輕量級可靠映射問題，提出對計算資源、鏈路資源和RRU頻譜資源聯(lián)合分配方案。首先，該方案建立面向可靠性約束的多目標資源分配模型，引入李雅普諾夫優(yōu)化模型，在保證隊列穩(wěn)定同時優(yōu)化資源分配。其次，提出了基于隊列穩(wěn)定性的虛擬節(jié)點映射算法和基于可靠性的虛擬鏈路映射算法。最后，將時間離散為一系列連續(xù)的時間窗，利用時間窗動態(tài)處理到達的網(wǎng)絡(luò)切片請求，實現(xiàn)在線的網(wǎng)絡(luò)切片映射算法。仿真結(jié)果表明，該算法提高了資源利用率，并且保證網(wǎng)絡(luò)可靠性。
- 網(wǎng)絡(luò)切片 /
- 資源分配 /
- 可靠性 /
- 李雅普諾夫優(yōu)化
Abstract: To meet the diversified demand of 5G Network Slicing (NS), while ensuring the reliability of slice, to achieve the optimal allocation of network resources, considering the dynamic mapping and lightweight reliable mapping problem of network slicing, this paper proposes a joint allocation scheme of computing resources, link resources and the spectrum resources of Radio Remote Unit (RRU). Firstly, a multi-objective resource allocation model oriented to reliability constraints is established, and the Lyapunov optimization model is introduced to ensure the queue stability and optimize the resource allocation. Then, the virtual node mapping algorithm based on queue stability and virtual link mapping algorithm based on reliability are proposed. Finally, the time is discretized into a series of continuous time windows, and the online network slice mapping algorithm is implemented by using the time window dynamic processing of the incoming network slice request. Simulation results show that the proposed algorithm improves resource utilization and guarantees network reliability.
- Network Slicing (NS) /
- Resource allocation /
- Reliability /
- Lyapunov optimization

HTML全文

圖 1 C-RAN場景網(wǎng)絡(luò)切片

下載: 全尺寸圖片幻燈片

圖 2 虛擬鏈路兩點子圖映射

下載: 全尺寸圖片幻燈片

圖 3 基于網(wǎng)絡(luò)切片的隊列模型

下載: 全尺寸圖片幻燈片

圖 4 時間窗在線網(wǎng)絡(luò)切片映射機制

下載: 全尺寸圖片幻燈片

圖 5 不同服務(wù)速率下對網(wǎng)絡(luò)平均隊長的影響比較

下載: 全尺寸圖片幻燈片

圖 6 不同控制參數(shù)V下服務(wù)速率對網(wǎng)絡(luò)隊長的影響

下載: 全尺寸圖片幻燈片

圖 7 兩種算法節(jié)點平均吞吐量對比

下載: 全尺寸圖片幻燈片

圖 8 兩種算法不同控制參數(shù)V下可靠性對比

下載: 全尺寸圖片幻燈片

表 1 基于隊列穩(wěn)定性的虛擬節(jié)點映射

算法1　基于隊列穩(wěn)定性的虛擬節(jié)點映射

(1) 虛擬切片 $\small G_v^g = \left( {N_v^g,E_v^g} \right)$
(2) 生成物理網(wǎng)絡(luò) $\small {G_s} = \left( {N_s,E_s} \right)$
(3) for all $\small n \in N_v^g$, do
(4)　if $\small {C_n} > {C_i},\forall i \in {N_s}$ then
(5)　　拒絕 $\small G_v^g,{y_g} = 0$
(6)　　return
(7)　　end if
(8)　　for all $\small i \in {N_s}|{C_n} \ge {C_i}$ do
(9) $\small {Y_i} \leftarrow \left\{ {V{p_g} - {Z_g}\left( t \right){w_{g,i}}{Q_i}\left( t \right)} \right\} + {Q_i}\left( t \right){\mu _i}\left( t \right)$
(10)　 $\small \varphi \left( i \right) \leftarrow 0,{y_g} \leftarrow 1$
(11)　 $\small {w_{g,i}} = {{{C_n}y_n^i} \Bigr/ {{P_g}}} = {{{C_{{s_{kg}}}}y_{{s_{kg}}}^i} \Bigr/ {{P_g}}} = {{{C_{{d_{kg}}}}y_{{d_{kg}}}^j} \Bigr/ {{P_g}}}\left( {i \ne j} \right)$
(12)　end for
(13)　Let $\small {i_{\max }} = \mathop {\arg \max }\limits_{i \in {N_s}} \left\{ {{Y_i}\left| {\varphi \left( i \right) = 0} \right.} \right\}$
(14)　set $\small y_g^{{i_{\max }}} \leftarrow 1$, $\small \varphi \left( {{i_{\max }}} \right) \leftarrow 1$, $\small {Y_g} \leftarrow {i_{\max }}$
(15)　end for
(16) 基于 $\small {Y_g}$利用VLM-R(基于可靠性的鏈路映射算法)映射虛擬鏈路
(17) VLM-R成功映射 then
(18)　更新物理網(wǎng)絡(luò)剩余的資源容量
(19) else
(20)　拒絕 $\small G_v^g,{y_g} = 0$
(21) end if

下載: 導(dǎo)出CSV

表 2 基于切片可靠性的虛擬鏈路映射

算法2　基于切片可靠性的虛擬鏈路映射

Input: Request $\small G_v^g = \left( {N_v^g,E_v^g,{T_g},{b_g}} \right)$, $\small {G_s} = \left( {{N_s},{E_s},{\lambda _s}} \right)$, $\small {Y_g}$,
$\small {e_{kg}} = \left( {{\rm{src}}{{\scriptsize{\_} }}{\rm{id}},{\rm{dst}}{\scriptsize{\_}}{\rm{id}}} \right)$
For $\small {e_{kg}} \in E_v^g$
Begin:
(1) 將每個切片中的虛擬鏈路按照k遞增的順序排列
(2) for each $\small {e_{kg}} \in E_v^g$ do
(3) 由算法1得到的 $\small {Y_g}$為 $\small {e_{kg}}$匹配相對應(yīng)的物理節(jié)點 $\small {n_s}$與 $\small {n_t}$
(4) set $\small {\rm{src}}{\scriptsize{\_}}{\rm{id}} \leftarrow {n_s},{\rm{dst}}{\scriptsize{\_}}{\rm{id}} \leftarrow {n_t}$
(5) 計算所有從 $\small {\rm{src}}{\scriptsize{\_}}{\rm{id}}$到 $\small {\rm{dst}}{\scriptsize{\_}}{\rm{id}}$的子路徑 $\small {P_m} \in \Omega \left( {{e_{kg}}} \right)$
(6) end for
(7) for each 子路徑 $\small {P_m} \in \Omega \left( {{e_{kg}}} \right)$ do
(8) if $\small \left\{ {{b_{ij}} < {b_k}\left| {{l_{ij}} \in {P_m}} \right.} \right\}$ then
(9)　refuse $\small {e_{kg}}$
(10) else $\small x_{ij}^{kg} = 1,\forall {l_{ij}} \in {P_m}$
(11) 計算此路徑 $\small {P_m}$的失效率 $\small \sum\nolimits_{i,j} \!\! {x_{ij}^{kg}} {\lambda _{ij}}{T_g}$作為它的權(quán)值
(12)　end if
(13) for all $\small {p_k}$ do
(14)　 $\small {\lambda _k} \leftarrow \sum\nolimits_{i,j} {x_{ij}^{kg}} {\lambda _{ij}}{T_g}$
(15)　end for
(16) let $\small {p_{\min }} = \mathop {\arg \min }\limits_{{p_m} \in \Omega \left( {{e_{kg}}} \right)} \left\{ {{\lambda _k}} \right\}$
(17)　set $\small X_{ij}^{kg} \leftarrow x_{ij}^{kg}$
(18) end for

下載: 導(dǎo)出CSV

表 3 基于時間窗的在線網(wǎng)絡(luò)切片映射

算法3　基于時間窗的在線網(wǎng)絡(luò)切片映射

(1) 初始化時間窗為空集 $\small {W_1} \leftarrow \left\{ {} \right\}$

(2) loop

(3)　　 $\small {W_2} \leftarrow {W_1}$

(4)　　 $\small {W_1} \leftarrow \left\{ {} \right\}$

(5)　　repeat

(6) 添加新的虛擬切片請求 $\small G_v^g = \left( {N_v^g,E_v^g,{T_g}} \right)$到 $\small {W_2}$

(7)　until 當(dāng)前窗口 $\small {W_2}$過期

(8) 根據(jù)切片生命周期對 $\small {W_2}$內(nèi)的切片進行排序，時間周期越短越優(yōu) 先處理

(9)　將當(dāng)前的時間 $\small {T_2} \leftarrow {\rm{Current}}\;{\rm{time}}$

(10)　　for all $\small G_v^g \in {W_2}$ do

(11) if $\small {t_w}\left( {G_v^g} \right)$在 $\small {T_2}$之前已經(jīng)過期 then

(12)　Reject $\small G_v^g$

(13)　　else

(14)　映射 $\small G_v^g$用算法1

(15) if 算法1映射 $\small G_v^g$失敗 then

(16)　將 $\small G_v^g$添加到 $\small {W_1}$

(17)　　　end if

(18)　　end if

(19)　end for

(20) end loop

下載: 導(dǎo)出CSV

參考文獻(16)

CAO Hantong, ZHU Yongxu, ZHENG Gan, et al. A novel optimal mapping algorithm with less computational complexity for virtual network embedding[J]. IEEE Transactions on Network and Service Management, 2018, 15 (1): 356－371. DOI: 10.1109/TNSM.2017.2778106.

ZHOU Zibo, CHANG Xiaolin, YANG Yang, et al. Resource-aware virtual network parallel embedding based on genetic algorithm[C]. 2016 17th International Conference on Parallel and Distributed Computing, Applications and Technologies, Guangzhou, 2016: 81–86.

ZHENG Hongkun, LI Jingjing, GONG Yuejiao, et al. Link mapping-oriented ant colony system for virtual network embedding[C]. 2017 IEEE Congress on Evolutionary Computation, San Sebastian, 2017: 1223–1230.

TRIVISCONNO R, VAISHNAVI I, and GUERZONI R. Virtual links mapping in future SDN-enabled networks[C]. IEEE SDN for Future Networks and Services, Trento, 2013: 1–5.

CHOWDHURY M, RAHMAN M R, and BOUTABA R. ViNEYard: Virtual network embedding algorithms with coordinated node and link mapping[J]. IEEE/ACM Transactions on Networking, 2012, 20(1): 206－219.

GUERZONI R, DESPOTOVIC Z, and TRIVISONNO R. Modeling reliability requirements in coordinated node and link mapping[C]. IEEE 33rd International Symposium on Reliable Distributed Systems, Nara, 2014: 321–330.

LONG Q, ASSI C, SHABAN K, et al. A Reliability-aware network service chain provisioning with delay guarantees in NFV-enabled enterprise datacenter networks[J]. IEEE Transactions on Network & Service Management, 2017, 14(3): 554－568. DOI: 10.1109/TNSM.2017.2723090.

SHAHRIAR N, AHMED R, CHOWDHURY S, et al. Generalized recovery from node failure in virtual network embedding[J]. IEEE Transactions on Network and Service Management, 2017, 14(2): 261－274. DOI: 10.1109/TNSM.2017.2693404.

HA V N and LONG B L. End-to-end network slicing in virtualized OFDMA-based cloud radio access networks[J]. IEEE Access, 2017, 5: 18675－18691.DOI: 10.1109/ACCESS.2017.2754461.

唐倫, 張亞, 梁榮, 等.基于網(wǎng)絡(luò)切片的網(wǎng)絡(luò)效用最大化虛擬資源分配算法[J]. 電子與信息學(xué)報, 2017, 39(8): 1812－1818. DOI: 10.11999/JEIT161322.

TANG Lun, ZHANG Ya, LIANG Rong, et al. Virtual resource allocation algorithm for network utility maximization based on network slicing[J]. Journal of Electronics & Information Technology, 2017, 39(8): 1812－1818. DOI: 10.11999/JEIT161322.

LI Kenli, TANG Xiaoyong, VEERAVALLI B, et al. Scheduling precedence constrained stochastic tasks on heterogeneous cluster systems[J]. IEEE Transactions on Computers, 2014, 64(1): 191－204. DOI: 10.1109/TC.2013.205

CHEN Yu and ZHANG Hongwei. Optimal request clustering for link reliability guarantee in wireless networked control[C]. IEEE Wireless Communications and Networking Conference, San Francisco, 2017: 1–6.

LIU Jiajia, JIANG Zhongyuan, KATO N, et al. Reliability evaluation for NFV deployment of future mobile broadband networks[J]. IEEE Wireless Communications, 2016, 23(3): 90－96. DOI: 10.1109/MWC.2016.7498079.

CASCAVAL P and FLORIA S A. SDP algorithm for network reliability evaluation[C]. IEEE International Conference on Innovations in Intelligent Systems and Applications, Gdynia, 2017: 119–125.

KANG Jinkyu, SIMEONE O, and KANG J. On the trade-off between computational load and reliability for network function virtualization[J]. IEEE Communications Letters, 2017, 21(8): 1767－1770. DOI: 10.1109/LCOMM.2017.2698040.

SHUMINOSKI T and JANEVSKI T. Lyapunov optimization framework for 5g mobile nodes with multi-homing[J]. IEEE Communications Letters, 2016, 20(5): 1026－1029. DOI: 10.1109/LCOMM.2016.2540622.

相關(guān)文章

施引文獻

資源附件(0)

訪問統(tǒng)計