面向軟件定義網絡的服務功能鏈優(yōu)化部署算法研究
doi: 10.11999/JEIT180264 cstr: 32379.14.JEIT180264
-
陸軍工程大學信息工程系 ??石家莊 ??050003
基金項目: 國家自然科學基金(51377170, 61271152)，國家青年科學基金(61602505)
Research on Placement Algorithm of Service Function Chaining Oriented to Software Defined Networking
-
Information Engineering Department, Army Engineering University, Shijiazhuang 050003, China
Funds: The National Natural Science Foundation of China (51377170, 61271152), The National Youth Science Fund Project (61602505)
-
摘要:
針對網絡功能虛擬化(NFV)環(huán)境下，現有服務功能鏈部署方法無法在優(yōu)化映射代價的同時保證服務路徑時延的問題，該文提出一種基于IQGA-Viterbi學習算法的服務功能鏈優(yōu)化部署方法。在隱馬爾可夫模型參數訓練過程中，針對傳統(tǒng)Baum-Welch算法訓練網絡參數容易陷入局部最優(yōu)的缺陷，改進量子遺傳算法對模型參數進行訓練優(yōu)化，在每一迭代周期內通過等比例復制適應度最佳種群的方式，保持可行解多樣性和擴大空間搜索范圍，進一步提高模型參數的精確度。在隱馬爾科夫鏈求解過程中，針對隱含序列無法直接觀測這一難點，利用Viterbi算法能精確求解隱含序列的優(yōu)勢，解決有向圖網絡中服務路徑的優(yōu)化選擇問題。仿真實驗結果表明，與其它部署算法相比，所提IQGA-Viterbi學習算法能有效降低網絡時延和映射代價的同時，提高了網絡服務的請求接受率。
Abstract:For Network Function Virtualization (NFV) environment, the existing placement methods can not guarantee the mapping cost while optimizing the network delay, a service function chaining optimal placement algorithm is proposed based on the IQGA-Viterbi learning algorithm. In the training process of Hidden Markov Model (HMM) parameters, the traditional Baum-Welch algorithm is easy to fall into the local optimum, so the quantum genetic algorithm is proposed, which can better optimize the model parameters. In each iteration, the improved algorithm maintains the diversity of feasible solutions and expands the scope of the spatial search by replicating the best fitness population with equal proportion, thus improving the accuracy of the model parameters. In the process of solving Hidden Markov chain, to overcome the problem that can not be directly observed for hidden sequences, Viterbi algorithm can solve the implicit sequences exactly and solve the problem of optimal service paths in the directed graph. Experimental results show that the network delay and mapping costs are lower compared with the existing algorithms. In addition, the acceptance ratio of requests is raised.
-
表 1 IQGA-Viterbi學習算法具體過程
輸入：服務請求序列O，底層網絡初始參數${{λ}}$0 輸出：最小化開銷部署策略 $\pi_s$ 步驟 1 ?IQGA算法初始化。設置訓練所用的觀測序列O數目為K，將底層初始網絡參數編碼成種群大小為M、量子比特編碼長度為N的染
色體。記迭代次數t的種群$P(t)=\left\{C^{(t)}_1,C^{(t)}_2,·\!·\!·,C^{(t)}_M \right\}$，其中種群個體C(t) M(m=1,2,···,M)的量子比特表示，初始狀態(tài)的網絡參數
可表示為如式(4)。
${C} _m^{(0)} = \left[ {\begin{array}{*{20}{c}} {\alpha _{m1}^{(0)}} \\ {\beta _{m1}^{(0)}} \end{array}\left| {\begin{array}{*{20}{c}} {\alpha _{m2}^{(0)}} \\ {\beta _{m2}^{(0)}} \end{array}} \right.\left| {\begin{array}{*{20}{c}} {·\!·\!· } \\ {·\!·\!· } \end{array}} \right.\left| {\begin{array}{*{20}{c}} {\alpha _{mN}^{(0)}} \\ {\beta _{mN}^{(0)}} \end{array}} \right.} \right] = \left[ {\begin{array}{*{20}{c}} {{1 / {\sqrt 2 }}} \\ {{1 / {\sqrt 2 }}} \end{array}\left| {\begin{array}{*{20}{c}} {{1 / {\sqrt 2 }}} \\ {{1 / {\sqrt 2 }}} \end{array}} \right.\left| {\begin{array}{*{20}{c}} {·\!·\!· } \\ {·\!·\!· } \end{array}} \right.\left| {\begin{array}{*{20}{c}} {{1 / {\sqrt 2 }}} \\ {{1 / {\sqrt 2 }}} \end{array}} \right.} \right],\ m = 1,2,·\!·\!· ,M$ (4)步驟 2 ?種群P(t)復制、變異和選擇。對于種群P(t)進行等比例復制生成P$\,'$(t)，利用高斯變異的操作對種群P$\,'$(t)進行更新，并生成種群
P$\,''$(t)，通過選擇等比例壓縮P$\,''$(t)生成P(t+1)。步驟 3 ?評價種群P(t+1)。對于經選擇后種群P(t+1)中個體的量子位進行測量，隨機生成[0, 1]的隨機數，若該隨機數大于或等于${\left| \alpha \right|^2}$或
${\left| \beta \right|^2}$，則測量的結果取值為1，否則取0。該過程是得到每個個體測量后的狀態(tài)${{{X}}_{C} } = \left\{ {{{x} _1},{{x} _2},·\!·\!· ,{{x} _{N} }} \right\}$，并將其轉化為十進制數，代
入目標函數如式(5)。
${\rm{Fitness} }({X_C}) = \frac{1}{K}\sum\limits_{k = 0}^K {\frac{1}{{{{{C}}^{(k)}}}}} $ (5)步驟 4 ?更新重估計開銷值${\widehat {{a}}_{ij}}$, ${\widehat {}_{ik}}$。記錄并保存當前迭代次數t的最佳個體，以及其對應的開銷數值矩陣${\widehat {{A}}_{n \times n}}$和${\widehat {{B}}_{m \times n}}$，據此更新模型重估
參數${\widehat {{a}}_{ij}}$, ${\widehat {}_{ik}}$，在迭代次數t+1時更新網絡底層視圖，并繼續(xù)對底層網絡參數反復迭代、重估。采用最大進化迭代次數Max_step作
為算法的終止條件，判斷是否到達最大進化迭代次數，若是則終止進化后得到一組最優(yōu)的網絡底層參數${{λ}}$=(A,B,${{Π}}$)，否則返回
至步驟2繼續(xù)迭代。步驟 5 ?Viterbi算法參數初始化。將IQGA算法得到${{λ}}$=(A,B,${{Π}}$)和觀測序列O作為Viterbi的輸入。 步驟 6 ?Viterbi變量${\delta _t}({j} )$遞推。從源端節(jié)點${{{v}}_{{s}}}$開始，根據服務鏈中VNF編排順序${\varphi _l}$，在每個迭代周期內計算從服務節(jié)點si到候選節(jié)點sj的最
小開銷，即Viterbi變量${\delta _t}\left( {j} \right) = \min \left[ {{{A}}\left( {{{s} _i},{{s} _j}} \right) + {{B}}\left( {{{s} _j},{{f} _m}} \right)} \right]$的計算，按照式(6)的遞推方式，搜索整個觀察序列O條件下的具體服務
路徑S，直到最后流出目的節(jié)點${{{v}}_t}$。位于不同時刻的部署開銷值，取其中最小值，進而得到最小開銷服務路徑的函數值$\min {\delta _t}({f_m})$。
$\left. \begin{aligned}{{q7j3ldu95}_{{{{t}}_1}}}({{{f}}_{{1}}})=& {q7j3ldu95}({{{s}}_1}) \\ {{q7j3ldu95}_{{{{t}}_2}}}({{{f}}_2})=&{{ \min}}\left\{ {{{q7j3ldu95}_{{{{t}}_1}}}({{{f}}_1}) + {{A}}({{{s}}_1}{{,}}{{{s}}_k}) + {{B}}({{{s}}_k}{{,}}{{{f}}_2})} \right\} \\ & \vdots \\ {{q7j3ldu95}_{{t_m}}}({{{f}}_m})=&{{\min}}\left\{ {{{q7j3ldu95}_{{{t - 1}}}}({{{f}}_{{{m - 1}}}}) + {{A}}({{{s}}_{{j}}}{{,}}{{{s}}_{{n}}}) + {{B}}({{{s}}_{{n}}}{{,}}{{{f}}_m})} \right\}\end{aligned}\right\} $ (6)步驟7 ?標記函數${\varphi _t}({{i}})$回溯。記錄位于當前時刻最小開銷序列應選取的前一時刻部署服務節(jié)點，利用標記函數${\varphi _t}\left( {i} \right) = \arg \min \left[ {{A}}\left( {{{s} _i},{{s} _j}} \right)\right. $
$ \left.+ {{B}}\left( {{{s} _j},{{f} _m}} \right) \right]$依次回溯，以服務鏈l 中最后一個VNF節(jié)點選取開銷最小時所選擇的服務節(jié)點sn為起點，沿著函數${{{s}}_{i - 1}} = {\varphi _t}({{{s}}_i})$給出
上一時刻所選擇的服務節(jié)點，直到計算出s1，得到開銷最小狀態(tài)序列路徑，并輸出服務路徑的構造方案${\pi _{{s}}}{{ = }}\left\{ {{\pi _{{{{f}}_1}}}{{,}}{\pi _{{{{f}}_2}}}{{,}}·\!·\!· {{,}}{\pi _{{{{f}}_m}}}} \right\}$。
下載: 導出CSV
-
BHAMARE D, JAIN R, SAMAKA M, et al. A survey on service function chaining[J]. Journal of Network & Computer Applications, 2016, 75(C): 138–155. doi: 10.1016/j.jnca.2016.09.001 MEDHAT A and TALEB T. Service function chaining in next generation networks: State of the art and research challenges[J]. IEEE Communications Magazine, 2017, 55(2): 216–223. doi: 10.1109/mcom.2016.1600219rp MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: Enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69–75. doi: 10.1145/1355734 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 KIM S, PARK S, KIM Y, et al. VNF-EQ: Dynamic placement of virtual network functions for energy efficiency and QoS guarantee in NFV[J]. Cluster Computing, 2017, 20(3): 1–11. doi: 10.1007/s10586-017-1004-3 BHAMARE D, SAMAKA M, ERBAD A, et al. Optimal virtual network function placement in multi-cloud service chaining architecture[J]. Computer Communications, 2017, 102(C): 1–16. doi: 10.1016/j.comcom.2017.02.011 BARI M F, CHOWDHURY S R, AHMED R, et al. On orchestrating virtual network functions[C]. International Conference on Network and Service Management, Barcelona, Spain, 2015: 50–56. doi: 10.1109/cnsm.2015.7367338. XIONG Gang, Hu Yuxiang, TIAN Le, et al. A virtual service placement approach based on improved quantum genetic algorithm[J]. Information and Electronic Engineering Frontiers, 2016, 17(7): 661–671. doi: 10.1631/fitee.1500494 LUKOVSZKI T, ROST M, and SCHMID S. It’s a match!: Near-optimal and incremental middlebox deployment[J]. ACM SIGCOMM Computer Communication Review, 2016, 46(1): 30–36. doi: 10.1145/2875951.2875956 MOENS H and TURCK F. VNF-P: A model for efficient placement of virtualized network functions[C]. International Conference on Network and Service Management, Beijing, China, 2014: 418–423. doi: 10.1109/cnsm.2014.701. ZHANG Lijun, HERMANS H, and JANSEN D. Logic and model checking for Hidden Markov Models[C]. International Conference on Formal Techniques for Networked and Distributed Systems, Berlin, Germany, 2005: 98–112. doi: 10.1007/11562436_9. ZHANG Zengyin, YUAN Changan, HU Jianjun, et al. HMM training method based on GEP and Baum-Welch algorithms[J]. Computer Engineering & Design, 2010, 31(9): 2027–2029. XIONG Yan, CHEN Huanhuan, MIAO Fuyou, et al. A quantum genetic algorithm to solve combinatorial optimization problem[J]. Acta Electronica Sinica, 2004, 32(11): 1855–1858. BOULOUTAS A, HART G W, and SCHWARTZ M. Two extensions of the Viterbi algorithm[J]. IEEE Transactions on Information Theory, 2002, 37(2): 430–436. doi: 10.1109/18.75270 ZHANG Lifang and ZHANG Xiping. Network traffic prediction based on BP neural networks optimized by quantum genetic algorithm[J]. Computer Engineering & Science, 2016, 10(3): 12–20. ZHANG Ying, BEHESHTI N, BELIVEAU L, et al. StEERING: A software-defined networking for inline service chaining[C]. IEEE International Conference on Network Protocols, Raleigh, USA, 2014: 1–10. doi: 10.1109/icnp.2013.673. BASTA A, HOFFMANN K, HOFFMANN K, et al. Applying NFV and SDN to LTE mobile core gateways, the functions placement problem[C]. The Workshop on All Things Cellular: Operations, Chicago, USA, 2014: 33–38. doi: 10.1145/2627585.2627592. 劉彩霞, 盧干強, 湯紅波, 等. 一種基于Viterbi算法的虛擬網絡功能自適應部署方法[J]. 電子與信息學報, 2016, 38(11): 2922–2930. doi: 10.11999/JEIT1650507LIU Caixia, LU Ganqiang, TANG Hongbo, et al. Adaptive deployment method for virtualized network function based on Viterbi algorithm[J]. Journal of Electronics &Information Technology, 2016, 38(11): 2922–2930. doi: 10.11999/JEIT1650507 ZEGURA E, CALVERT K, and BHATTACHARJEE S. How to model an Internetwork[J]. Proceedings of IEEE Infocom, 1996, 2: 594–601. doi: 10.1109/infcom.1996.493353 ORLOWSKI S, WESSALY R, PIORO M, et al. SNDlib 1.0-survivable network design library[J]. Networks, 2010, 55(3): 276–286. doi: 10.1002/net.20371 CLAYMAN S, MAINI E, GALIS A, et al. The dynamic placement of virtual network functions[C]. Network Operations and Management Symposium, Seoul, Korea, 2014: 1–9. doi: 10.1109/noms.2014.6838412. SAHHAF S, TAVERNIER W, ROST M, et al. Network service chaining with optimized network function embedding supporting service decompositions[J]. Computer Networks the International Journal of Computer & Telecommunications Networking, 2015, 93(P3): 492–505. doi: 10.1016/j.comnet.2015.09.035 -
圖(10) / 表(2)
計量
- 文章訪問數: 3015
- HTML全文瀏覽量: 951
- PDF下載量: 95
- 被引次數: 0
下載:
