基于最長有效功能序列的服務(wù)功能鏈部署算法

李丹; 蘭巨龍; 王鵬; 胡宇翔

doi:10.11999/JEIT180402

基于最長有效功能序列的服務(wù)功能鏈部署算法

doi: 10.11999/JEIT180402

國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 ??鄭州 ??450000

基金項(xiàng)目: 國家863計(jì)劃(2015AA016102)，國家自然科學(xué)基金(61521003, 61702547)

詳細(xì)信息

作者簡介:
李丹：男，1989年生，博士生，研究方向?yàn)樾滦途W(wǎng)絡(luò)體系結(jié)構(gòu)

蘭巨龍：男，1962 年生，教授，博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)體系結(jié)構(gòu)、信息安全

王鵬：男，1985年生，博士，主要研究方向?yàn)樾滦途W(wǎng)絡(luò)體系結(jié)構(gòu)、路由技術(shù)

胡宇翔：男，1982年生，博士，主要研究方向?yàn)樾滦途W(wǎng)絡(luò)體系結(jié)構(gòu)、網(wǎng)絡(luò)安全

通訊作者:
李丹　pkulidan@foxmail.com

中圖分類號(hào): TP393
計(jì)量
- 文章訪問數(shù): 1826
- HTML全文瀏覽量: 736
- PDF下載量: 57
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-04-28
- 修回日期: 2018-10-10
- 網(wǎng)絡(luò)出版日期: 2018-10-30
- 刊出日期: 2019-03-01

Service Function Chain Deployment Algorithm Based on Longest Effective Function Sequence

National Digital Switching System Engineering & Technology Research Center, Zhengzhou 450000, China

Funds: The National 863 Program of China (2015AA016102), The National Natural Science Foundation of China (61521003, 61702547)

摘要

摘要:
服務(wù)功能鏈的服務(wù)性能取決于功能的部署位置和數(shù)據(jù)傳輸路徑的選擇。針對資源有限的網(wǎng)絡(luò)中的服務(wù)功能鏈部署問題，該文設(shè)計(jì)了一種基于最長有效功能序列(LEFS)的服務(wù)功能鏈部署算法，以功能復(fù)用和帶寬需求聯(lián)合優(yōu)化為目標(biāo)，在控制路徑長度的同時(shí)根據(jù)LEFS逐步搜索中繼節(jié)點(diǎn)，直至滿足服務(wù)請求。仿真結(jié)果表明，該算法能夠均衡網(wǎng)絡(luò)資源，同時(shí)優(yōu)化網(wǎng)絡(luò)的功能部署率和帶寬利用率，與其他算法相比，網(wǎng)絡(luò)資源利用率降低了10%，可以支持更多的服務(wù)請求，且算法計(jì)算復(fù)雜度低，可以實(shí)現(xiàn)對服務(wù)請求的快速響應(yīng)。
- 服務(wù)功能鏈 /
- 最長有效功能序列 /
- 功能復(fù)用 /
- 帶寬需求
Abstract:
The efficiency of Service Function Chain (SFC) depends closely on where functions are deployed and how to select paths for data transmission. For the problem of SFC deployment in a resource-constrained network, this paper proposes an optimization algorithm for SFC deployment based on the Longest Effective Function Sequence (LEFS). To optimize function deployment and bandwidth requirement jointly, the upper bound of path length is set and relay nodes are searched incrementally on the basis of LEFS until the service request is satisfied. Simulation results show that, the proposed algorithm can balance network resource and optimize the function deploymen rate and bandwidth utilization. Compared with other algorithms, the utilization of network resource decreases 10%, so that more service requests can be supported. What is more, the algorithm has a lower computation complexity and can response to service requests quickly.
- Service Function Chain (SFC) /
- Longest Effective Function Sequence (LEFS) /
- Function reuse /
- Bandwidth requirement

HTML全文

圖 1 服務(wù)功能鏈部署示意圖

下載: 全尺寸圖片幻燈片

圖 2 最長有效功能序列示意圖

下載: 全尺寸圖片幻燈片

圖 3 各算法功能部署率

下載: 全尺寸圖片幻燈片

圖 4 各算法帶寬利用率

下載: 全尺寸圖片幻燈片

圖 5 各算法網(wǎng)絡(luò)資源綜合利用率

下載: 全尺寸圖片幻燈片

圖 6 各算法可支持的服務(wù)請求數(shù)

下載: 全尺寸圖片幻燈片

圖 7 各算法平均響應(yīng)時(shí)間

下載: 全尺寸圖片幻燈片

表 1 算法1：最長有效功能序列函數(shù)

算法1：最長有效功能序列函數(shù)(${\rm LEFS}\left( {z,S} \right)$)
(1) $\varphi = {\text{functions along }}z$
(2) for $i = 1{\text{ to }}\left\| S \right\|$
(3) 　 for $j = 1{\text{ to }}\left\| \varphi \right\|$
(4) 　　　if ${S_i} = {\varphi _j}$
(5) 　　　　${\theta _{ij}} = {\theta _{i - 1j - 1}} + 1$, ${\omega _{ij}} = {\omega _{i - 1j - 1}} + 1$
(6) 　　else if ${\varphi _j} = {\text{0}}$
(7) 　　　${\theta _{ij}} = {\theta _{i - 1j - 1}} + 1$, ${\omega _{ij}} = {\omega _{ij - 1}}$
(8) 　　　else ${\theta _{ij}} = {\theta _{ij - 1}}$, ${\omega _{ij}} = {\omega _{ij - 1}}$
(9) 　　　end if
(10) 　　end for
(11) 　　if ${\theta _{i\left\| \varphi \right\|}} < i$
(12) 　　　$i = i - 1$, break
(13) 　　end if
(14) end for
(15) ${\rm le} = {\theta _{i\left\| \varphi \right\|}}$, ${\rm re} = {\omega _{i\left\| \varphi \right\|}}$//$\rm le$：最長有效功能序列長度；$\rm re$：功能復(fù)用度
(16) ${\rm flag} = \left\| \varphi \right\|$
(17) for $k = i{\text{ to }}1$
(18) 　　for $j = {\rm flag}{\text{ to }}1$
(19) 　　　if ${S_k} = {\varphi _j}$ and ${\theta _{kj}} = k$ then
(20) 　　　　${\rm flag} = j$, break
(21) 　　end if
(22) 　end for
(23) 　if $j < k$
(24) 　　for $j = {\rm flag}{\text{ to }}1$
(25) 　　　if ${\varphi _{2j}} = {\text{0}}$
(26) 　　　　break
(27) 　　　end if
(28) 　　end for
(29) 　　${\rm flag} = j$, ${\rm de}\left( {{S_k}} \right) = {\varphi _j}$//$\rm de$：剩余功能部署位置
(30) 　end if
(31) end for
(32) return $\rm le$, $\rm re$ and $\rm de$

下載: 導(dǎo)出CSV

表 2 算法2：基于最長有效功能序列的服務(wù)功能鏈部署

算法2　基于最長有效功能序列的服務(wù)功能鏈部署
(1) for each service request ${r_i}$
(2) 　${v_0} = {o_i}$, ${z_0} = \varnothing $, $k = 0$
(3) 　while ${\rm LEFS}\left( {{z_k},{S_i}} \right).{\rm le} < \left\| {{S_i}} \right\|$
(4) 　　$k = k + 1$, ${h_k} = \varnothing $ //${h_k}$：備選路徑集合
(5) 　　for ${v_k} \in V$and ${v_k} \notin {z_{k - 1}}$
(6) 　　　${z_k} = {z_{k - 1}} + {P_{{v_{k - 1}},{v_k}}}$
(7) 　　　calculate ${\rm LEFS}\left( {{z_k},{S_i}} \right)$ according to algorithm 1
(8) 　　　calculate ${u_i}$ according to Eq. (5)
(9) 　　　if $\left\| {{z_k}} \right\| + \left\| {{P_{{v_k},{t_i}}}} \right\| {\rm \le} {u_i}$ and ${\rm LEFS}\left( {{z_k},{S_i}} \right).{\rm le} > {\rm LEFS}\left( {{z_{k - 1}},{S_i}} \right).{\rm le}$
(10) 　　　　put ${z_k}$into ${h_k}$
(11) 　　　end if
(12) 　　end for
(13) 　　select ${z_k}$ with the maximum ${g_{ik}}$ in ${h_k}$ according to Eq. 　　　　　(8)
(14) 　　update ${v_k}$ and ${z_k}$
(15) 　end while
(16) 　$z \!=\! {z_k} \!+\! {P_{{v_k},{t_i}}}$, deploy functions according to ${\rm LEFS}\left( {{z_k},{S_i}} \right).{ }$ de, and update ${C_E}$ and ${C_V}$
(17) end for

下載: 導(dǎo)出CSV

參考文獻(xiàn)(19)

HAN Bo, GOPALAKRISHNAN V, JI Lusheng, et al. Network function virtualization: Challenges and opportunities for innovations[J]. IEEE Communications Magazine, 2015, 53(2): 90–97. doi: 10.1109/MCOM.2015.7045396

QUINN P and GUICHARD J. Service function chaining: Creating a service plane via network service headers[J]. Computer, 2014, 47(11): 38–44. doi: 10.1109/MC.2014.328

LI Yong, ZHENG Feng, CHEN Min, et al. A unified control and optimization framework for dynamical service chaining in software-defined NFV system[J]. IEEE Wireless Communications, 2015, 22(6): 15–23. doi: 10.1109/MWC.2015.7368820

COHEN R, LEWIN-EYTAN L, NAOR J S, et al. Near optimal placement of virtual network functions[C]. 2015 IEEE Conference on Computer Communications (INFOCOM), Hong Kong, China, 2015: 1346–1354.

李丹, 蘭巨龍, 王鵬, 等. 一種集中調(diào)控的分布式服務(wù)路徑選擇算法[J]. 電子與信息學(xué)報(bào), 2018, 40(4): 785–793. doi: 10.11999/JEIT170600

LI Dan, LAN Julong, WANG Peng, et al. Distributed service path selection algorithm under central control[J]. Journal of Electronics &Information Technology, 2018, 40(4): 785–793. doi: 10.11999/JEIT170600

梁寧寧, 蘭巨龍, 張巖. 基于分布式選擇探測算法的服務(wù)路由機(jī)制[J]. 電子學(xué)報(bào), 2017, 45(7): 1545–1552. doi: 10.3969/j.issn.0372-2112.2017.07.001

LIANG Ningning, LAN Julong, and ZHANG Yan. A service routing mechanism based on the distributed selection probing algorithm[J]. Acta Electronica Sinica, 2017, 45(7): 1545–1552. doi: 10.3969/j.issn.0372-2112.2017.07.001

XIA Ming, SHIRAZIPOUR M, ZHANG Ying, et al. Network function placement for NFV chaining in packet/optical datacenters[J]. Journal of Lightwave Technology, 2015, 33(8): 1565–1570. doi: 10.1109/JLT.2015.2388585

BARI M F, CHOWDHURY S R, AHMED R, et al. Orchestrating virtualized network functions[J]. IEEE Transactions on Network & Service Management, 2016, 13(4): 725–739. doi: 10.1109/TNSM.2016.2569020

BARI M F, CHOWDHURY S R, AHMED R, et al. On orchestrating virtual network functions[C]. 2015 11th International Conference on Network and Service Management (CNSM), Barcelona, Spain, 2015: 50–56. doi: 10.1109/CNSM.2015.7367338.

KLINKOWSKI M A and WALKOWIAK K. On the advantages of elastic optical networks for provisioning of cloud computing traffic[J]. IEEE Network, 2013, 27(6): 44–51. doi: 10.1109/MNET.2013.6678926

ZHANG Liang and ZHU Zuqing. Spectrum-efficient anycast in elastic optical inter-datacenter networks[J]. Optical Switching & Networking, 2014, 14(4): 250–259. doi: 10.1016/j.osn.2014.05.018

XIE Lijun, JIANG Yiming, WANG Binqiang, et al. An approach for network function combination based on least busy placement algorithm[J]. China Communications, 2016, 13(Sup): 167–176. doi: 10.1109/CC.0.7560888

MEHRAGHDAM S, KELLER M, and KARL H. Specifying and placing chains of virtual network functions[C]. 2014 IEEE 3rd International Conference on Cloud Networking (CloudNet), Luxembourg, 2014: 7–13.

LONG Qu, 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

MECHTRI M, GHRIBI C, and ZEGHLACHE D. A scalable algorithm for the placement of service function chains[J]. IEEE Transactions on Network and Service Management, 2016, 13(3): 533–546. doi: 10.1109/TNSM.2016.2598068

YANG Ke, ZHANG Hong, and HONG Peilin. Energy-aware service function placement for service function chaining in data centers[C]. 2016 IEEE Global Communications Conference (GLOBECOM), Washington, D.C., USA, 2016: 1–6.

FANG Wenjian, ZENG Menglu, LIU Xiahe, et al. Joint spectrum and IT resource allocation for efficient vNF service chaining in inter-datacenter elastic optical networks[J]. IEEE Communications Letters, 2016, 20(8): 1539–1542. doi: 10.1109/LCOMM.2016.2580151

KUO Tungwei, LIOU Bangheng, LIN Kate Chingju, et al. Deploying chains of virtual network functions: On the relation between link and server usage[J]. IEEE/ACM Transactions on Networking, 2018, 26(4): 1562–1576. doi: 10.1109/TNET.2018.2842798

SALAMA H F. Multicast Routing for Real-time Communication of High-speed Networks[M]. Raleigh, USA, North Carolina State University, 1996: 198.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)