高级搜索

面向软件定义网络的服务功能链优化部署算法研究

卢昱 刘益岑 李玺 陈兴凯 乔文欣 陈立云

引用本文: 卢昱, 刘益岑, 李玺, 陈兴凯, 乔文欣, 陈立云. 面向软件定义网络的服务功能链优化部署算法研究[J]. 电子与信息学报, 2019, 41(1): 74-82. doi: 10.11999/JEIT180264 shu
Citation:  Yu LU, Yicen LIU, Xi LI, Xingkai CHEN, Wenxin QIAO, Liyun CHEN. Research on Placement Algorithm of Service Function Chaining Oriented to Software Defined Networking[J]. Journal of Electronics and Information Technology, 2019, 41(1): 74-82. doi: 10.11999/JEIT180264 shu

面向软件定义网络的服务功能链优化部署算法研究

    作者简介: 卢昱: 男,1960年生,教授,研究方向为下一代网络体系架构;
    刘益岑: 男,1990年生,硕士生,研究方向为智能VNF编排技术、软件定义服务;
    李玺: 男,1982年生,讲师,研究方向为新型信息网络关键理论与技术;
    陈兴凯: 男,1988年生,博士生,研究方向为未来网络体系架构关键技术;
    乔文欣: 女,1992年生,博士生,研究方向为网络虚拟化技术可靠性;
    陈立云: 男,1968年生,教授,研究方向为深度学习、人工智能
    通讯作者: 刘益岑,18419764051@163.com
  • 基金项目: 国家自然科学基金(51377170, 61271152);国家青年科学基金(61602505)

摘要: 针对网络功能虚拟化(NFV)环境下,现有服务功能链部署方法无法在优化映射代价的同时保证服务路径时延的问题,该文提出一种基于IQGA-Viterbi学习算法的服务功能链优化部署方法。在隐马尔可夫模型参数训练过程中,针对传统Baum-Welch算法训练网络参数容易陷入局部最优的缺陷,改进量子遗传算法对模型参数进行训练优化,在每一迭代周期内通过等比例复制适应度最佳种群的方式,保持可行解多样性和扩大空间搜索范围,进一步提高模型参数的精确度。在隐马尔科夫链求解过程中,针对隐含序列无法直接观测这一难点,利用Viterbi算法能精确求解隐含序列的优势,解决有向图网络中服务路径的优化选择问题。仿真实验结果表明,与其它部署算法相比,所提IQGA-Viterbi学习算法能有效降低网络时延和映射代价的同时,提高了网络服务的请求接受率。

English

    1. [1]

      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

    2. [2]

      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

    3. [3]

      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

    4. [4]

      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

    5. [5]

      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

    6. [6]

      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

    7. [7]

      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.

    8. [8]

      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

    9. [9]

      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

    10. [10]

      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.

    11. [11]

      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.

    12. [12]

      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.

    13. [13]

      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.

    14. [14]

      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

    15. [15]

      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.

    16. [16]

      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.

    17. [17]

      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.

    18. [18]

      刘彩霞, 卢干强, 汤红波, 等. 一种基于Viterbi算法的虚拟网络功能自适应部署方法[J]. 电子与信息学报, 2016, 38(11): 2922–2930. doi: 10.11999/JEIT1650507
      LIU 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

    19. [19]

      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

    20. [20]

      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

    21. [21]

      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.

    22. [22]

      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

    1. [1]

      胡宇翔, 范宏伟, 兰巨龙, 段通. 一种支持硬件加速的虚拟网络功能部署模型. 电子与信息学报, 2019, 41(8): 1893-1901.

    2. [2]

      史久根, 张径, 徐皓, 王继, 孙立. 一种面向运营成本优化的虚拟网络功能部署和路由分配策略. 电子与信息学报, 2019, 41(4): 973-979.

    3. [3]

      季新生, 徐水灵, 刘文彦, 仝青, 李凌书. 一种面向安全的虚拟网络功能动态异构调度方法. 电子与信息学报, 2019, 41(10): 2435-2441.

    4. [4]

      谷允捷, 胡宇翔, 谢记超. 基于重叠网络结构的服务功能链时空优化编排策略. 电子与信息学报, 2019, 41(11): 2675-2683.

    5. [5]

      张红旗, 黄睿, 常德显. 一种基于匹配博弈的服务链协同映射方法. 电子与信息学报, 2019, 41(2): 385-393.

    6. [6]

      李丹, 兰巨龙, 王鹏, 胡宇翔. 基于最长有效功能序列的服务功能链部署算法. 电子与信息学报, 2019, 41(3): 680-686.

    7. [7]

      陈前斌, 杨友超, 周钰, 赵国繁, 唐伦. 基于随机学习的接入网服务功能链部署算法. 电子与信息学报, 2019, 41(2): 417-423.

    8. [8]

      伊鹏, 谢记超, 张震, 谷允捷, 赵丹. 抗侧信道攻击的服务功能链部署方法. 电子与信息学报, 2019, 41(11): 2699-2707.

    9. [9]

      唐伦, 周钰, 杨友超, 赵国繁, 陈前斌. 5G网络切片场景中基于预测的虚拟网络功能动态部署算法. 电子与信息学报, 2019, 41(9): 2071-2078.

    10. [10]

      汤红波, 邱航, 游伟, 季新生. 基于联合备份的服务功能链可靠性保障的部署方法. 电子与信息学报, 2019, 41(0): 1-8.

    11. [11]

      唐伦, 赵培培, 赵国繁, 陈前斌. 基于深度信念网络资源需求预测的虚拟网络功能动态迁移算法. 电子与信息学报, 2019, 41(6): 1397-1404.

    12. [12]

      唐伦, 周钰, 谭颀, 魏延南, 陈前斌. 基于强化学习的5G网络切片虚拟网络功能迁移算法. 电子与信息学报, 2019, 41(0): 1-9.

    13. [13]

      唐伦, 杨恒, 马润琳, 陈前斌. 基于5G接入网络的多优先级虚拟网络功能迁移开销与网络能耗联合优化算法. 电子与信息学报, 2019, 41(9): 2079-2086.

    14. [14]

      胡致远, 宋晓凤, 黄天聪, 李晓娣, 周瑞芳, 徐鑫, 蒙占宇, 彭强. 四表集抄通信网络虚拟化方案及组网算法研究. 电子与信息学报, 2019, 41(3): 588-593.

    15. [15]

      唐伦, 魏延南, 马润琳, 贺小雨, 陈前斌. 虚拟化云无线接入网络下基于在线学习的网络切片虚拟资源分配算法. 电子与信息学报, 2019, 41(7): 1533-1539.

    16. [16]

      王汝言, 李宏娟, 吴大鹏, 李红霞. 基于半马尔科夫决策过程的虚拟传感网络资源分配策略. 电子与信息学报, 2019, 41(0): 1-8.

    17. [17]

      苏玉泽, 孟相如, 康巧燕, 韩晓阳. 核心链路感知的可生存虚拟网络链路保护方法. 电子与信息学报, 2019, 41(7): 1587-1593.

    18. [18]

      刘江义, 王春平. 基于双马尔科夫链的势概率假设密度滤波. 电子与信息学报, 2019, 41(2): 492-497.

    19. [19]

      唐伦, 杨希希, 施颖洁, 陈前斌. 无线虚拟网络中基于自回归滑动平均预测的在线自适应虚拟资源分配算法. 电子与信息学报, 2019, 41(1): 16-23.

    20. [20]

      汤光明, 姜明明, 孙艺. 失真代价动态更新的自适应彩色图像隐写算法. 电子与信息学报, 2019, 41(3): 656-665.

  • 图 1  基于SDN的服务功能链部署模型

    图 2  2级映射模型

    图 3  HMM参数的染色体编码

    图 4  t时刻网络视图

    图 5  Abilene骨干网拓扑结构

    图 6  不同算法的寻优性能比较

    图 7  不同请求强度下的服务请求处理时间

    图 8  不同请求强度下的服务请求接受率

    图 9  不同请求强度下的服务链映射代价

    图 10  不同请求强度下的时延均值比较

    表 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)的量子比特表示,初始状态的网络参数
    可表示为如式(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。该过程是得到每个个体测量后的状态${{{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 {{b}}_{ik}}$。记录并保存当前迭代次数t的最佳个体,以及其对应的开销数值矩阵${\widehat {{A}}_{n \times n}}$和${\widehat {{B}}_{m \times n}}$,据此更新模型重估
    参数${\widehat {{a}}_{ij}}$, ${\widehat {{b}}_{ik}}$,在迭代次数t+1时更新网络底层视图,并继续对底层网络参数反复迭代、重估。采用最大进化迭代次数Max_step作
    为算法的终止条件,判断是否到达最大进化迭代次数,若是则终止进化后得到一组最优的网络底层参数${{λ}}$=(A,B,${{Π}}$),否则返回
    至步骤2继续迭代。
     步骤 5  Viterbi算法参数初始化。将IQGA算法得到${{λ}}$=(A,B,${{Π}}$)和观测序列O作为Viterbi的输入。
     步骤 6  Viterbi变量${\delta _t}({j} )$递推。从源端节点${{{v}}_{{s}}}$开始,根据服务链中VNF编排顺序${\varphi _l}$,在每个迭代周期内计算从服务节点si到候选节点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,直到最后流出目的节点${{{v}}_t}$。位于不同时刻的部署开销值,取其中最小值,进而得到最小开销服务路径的函数值$\min {\delta _t}({f_m})$。
                    $\left. \begin{aligned}{{{d}}_{{{{t}}_1}}}({{{f}}_{{1}}})=& {{d}}({{{s}}_1}) \\ {{{d}}_{{{{t}}_2}}}({{{f}}_2})=&{{ \min}}\left\{ {{{{d}}_{{{{t}}_1}}}({{{f}}_1}) + {{A}}({{{s}}_1}{{,}}{{{s}}_k}) + {{B}}({{{s}}_k}{{,}}{{{f}}_2})} \right\} \\ & \vdots \\ {{{d}}_{{t_m}}}({{{f}}_m})=&{{\min}}\left\{ {{{{d}}_{{{t - 1}}}}({{{f}}_{{{m - 1}}}}) + {{A}}({{{s}}_{{j}}}{{,}}{{{s}}_{{n}}}) + {{B}}({{{s}}_{{n}}}{{,}}{{{f}}_m})} \right\}\end{aligned}\right\} $ (6)
     步骤7  标记函数${\varphi _t}({{i}})$回溯。记录位于当前时刻最小开销序列应选取的前一时刻部署服务节点,利用标记函数${\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节点选取开销最小时所选择的服务节点sn为起点,沿着函数${{{s}}_{i - 1}} = {\varphi _t}({{{s}}_i})$给出
    上一时刻所选择的服务节点,直到计算出s1,得到开销最小状态序列路径,并输出服务路径的构造方案${\pi _{{s}}}{{ = }}\left\{ {{\pi _{{{{f}}_1}}}{{,}}{\pi _{{{{f}}_2}}}{{,}}·\!·\!· {{,}}{\pi _{{{{f}}_m}}}} \right\}$。
    下载: 导出CSV

    表 2  算法测试结果统计与比较

    算法误差最小值平均迭代数
    IQGA0.21420
    QGA0.22348
    BW0.24876
    下载: 导出CSV
  • 加载中
图(10)表(2)
计量
  • PDF下载量:  47
  • 文章访问数:  315
  • HTML全文浏览量:  187
文章相关
  • 通讯作者:  刘益岑, 18419764051@163.com
  • 收稿日期:  2018-03-21
  • 录用日期:  2018-07-27
  • 网络出版日期:  2018-08-24
  • 刊出日期:  2019-01-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章