高级搜索

一种面向运营成本优化的虚拟网络功能部署和路由分配策略

史久根 张径 徐皓 王继 孙立

引用本文: 史久根, 张径, 徐皓, 王继, 孙立. 一种面向运营成本优化的虚拟网络功能部署和路由分配策略[J]. 电子与信息学报, 2019, 41(4): 973-979. doi: 10.11999/JEIT180522 shu
Citation:  Jiugen SHI, Jing ZHANG, Hao XU, Ji WANG, Li SUN. Joint Optimization of Virtualized Network Function Placement and Routing Allocation for Operational Expenditure[J]. Journal of Electronics and Information Technology, 2019, 41(4): 973-979. doi: 10.11999/JEIT180522 shu

一种面向运营成本优化的虚拟网络功能部署和路由分配策略

    作者简介: 史久根: 男,1963年生,副教授,研究方向为嵌入式系统、计算机网络和软件定义网络;
    张径: 男,1993年生,硕士生,研究方向为软件定义网络、网络功能虚拟化;
    徐皓: 男,1994年生,硕士生,研究方向为软件定义网络、控制器部署;
    王继: 男,1993年生,硕士生,研究方向为软件定义网络、网络功能虚拟化;
    孙立: 男,1993年生,硕士生,研究方向为软件定义网络、网络功能虚拟化
    通讯作者: 张径,zj0910@mail.hfut.edu.cn
  • 基金项目: 国家重大科学仪器设备开发专项(2013YQ030595)

摘要: 随着网络功能虚拟化(NFV)技术的发展,虚拟网络功能(VNF)可以通过服务功能链(SFC)的形式部署在如虚拟机的通用平台中,为管理带来灵活性。但是对于服务提供商来说,由于网络基础设施的复杂性和日益增长的服务需求,给VNF的部署带来了高昂的运营成本(OPEX)。针对此问题,该文提出一种面向OPEX优化的策略,旨在最小化OPEX中的激活、能耗和传输成本,得到VNF部署和路由分配优化方案。为此建立一种全新的混合整数线性规划(MILP)模型,并设计包括遗传算法(GA)在内的3种OPEX优化算法。仿真实验评估在不同资源配给下MILP和3种算法的OPEX及其性能,其中GA算法在节点资源配比60%以上时可以得到近似于MILP模型的解决方案。

English

    1. [1]

      HAN B, GOPALAKRISHNAN V, JI L, 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

    2. [2]

      XIN Li and CHEN Qian. A survey of network function placement[C]. Consumer Communications & Networking Conference, Las Vegas, USA, 2016: 948–953.

    3. [3]

      HERRERA J G and BOTERO J F. Resource allocation in NFV: A comprehensive survey[J]. IEEE Transactions on Network and Service Management, 2016, 13(3): 518–532. doi: 10.1109/TNSM.2016.2598420

    4. [4]

      GREENHALGH A, HUICI F, HOERDT M, et al. Flow processing and the rise of commodity network hardware[J]. ACM SIGCOMM Computer Communication Review, 2009, 39(2): 20–26. doi: 10.1145/1517480.1517484

    5. [5]

      BOUET M, LEGUAY J, COMBE T, et al. Cost-based placement of vDPI functions in NFV infrastructures[J]. International Journal of Network Management, 2015, 25(6): 490–506. doi: 10.1109/netsoft.2015.7116121

    6. [6]

      LIN Tachun, ZHOU Zhili, TORNATORE M, et al. Demand-aware network function placement[J]. Journal of Lightwave Technology, 2016, 34(11): 2590–2600. doi: 10.1109/JLT.2016.2535401

    7. [7]

      LUIZELLI M C, BAYS L R, BURIOL L S, et al. Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions[C]. IFIP/IEEE International Symposium on Integrated Network Management, Ottawa, Canada, 2015: 98–106.

    8. [8]

      BHAMARE D, SAMAKA M, ERBAD A, et al. Optimal virtual network function placement in multi-cloud service function chaining architecture[J]. Computer Communications, 2017, 102: 1–16. doi: 10.1016/j.comcom.2017.02.011

    9. [9]

      CAO Jiuyue, ZHANG Yan, AN Wei, et al. VNF placement in hybrid NFV environment: Modeling and genetic algorithms[C]. IEEE International Conference on Parallel and Distributed Systems, Wuhan, China, 2017: 769–777.

    10. [10]

      CARPIO F, DHAHRI S, and JUKAN A. VNF Placement with replication for load balancing in NFV networks[C]. IEEE International Conference on Communications, Paris, France, 2017: 1–6.

    11. [11]

      RANKOTHGE W, MA Jiefei, LE Franck, et al. Towards making network function virtualization a cloud computing service[C]. IFIP/IEEE International Symposium on Integrated Network Management, Ottawa, Canada, 2015: 89–97.

    12. [12]

      BARI 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

    13. [13]

      史久根, 许辉亮, 陆立鹏. 软件定义网络中数据中心虚拟机迁移序列问题的研究[J]. 电子与信息学报, 2017, 39(5): 1193–1199. doi: 10.11999/JEIT160792
      SHI Jiugen, XU Huiliang, and LU Lipeng. Research on the migration queue of data center’s virtual machine in software defined networks[J]. Journal of Electronics &Information Technology, 2017, 39(5): 1193–1199. doi: 10.11999/JEIT160792

    14. [14]

      MOUSTAFA N, MASHALY M, and ASHOUR M. Modeling and simulation of energy-efficient cloud data centers[C]. International Conference on Engineering and Technology, Cairo, Egypt, 2014: 1–5.

    15. [15]

      ASSAD A A. Multicommodity network flows—A survey[J]. Networks, 1978, 8(1): 37–91. doi: 10.1002/net.3230080107

    16. [16]

      ORLOWSKI S, WESSÄLY R, PIÓRO M, et al. SNDlib 1.0—Survivable network design library[J]. Networks, 2010, 55(3): 276–286. doi: 10.1002/net.20371

    17. [17]

      MARTINS J, AHMED M, RAICIU C, et al. ClickOS and the art of network function virtualization[C]. 11th USENIX Symposium on Networked Systems Design and Implementation, Seattle, USA, 2014: 459–473.

    1. [1]

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

    2. [2]

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

    3. [3]

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

    4. [4]

      卢昱, 刘益岑, 李玺, 陈兴凯, 乔文欣, 陈立云. 面向软件定义网络的服务功能链优化部署算法研究. 电子与信息学报, 2019, 41(1): 74-82.

    5. [5]

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

    6. [6]

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

    7. [7]

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

    8. [8]

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

    9. [9]

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

    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(7): 1587-1593.

    15. [15]

      王汝言, 李宏娟, 吴大鹏. 基于Stackelberg博弈的虚拟化无线传感网络资源分配策略. 电子与信息学报, 2019, 41(2): 377-384.

    16. [16]

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

    17. [17]

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

    18. [18]

      王汝言, 徐宁宁, 吴大鹏. 能耗和时延感知的虚拟化云无线接入网络资源分配机制. 电子与信息学报, 2019, 41(1): 83-90.

    19. [19]

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

    20. [20]

      刘小强, 袁国顺, 乔树山. FPGA硬核处理器系统加速数字电路功能验证的方法. 电子与信息学报, 2019, 41(5): 1251-1256.

  • 图 1  网络功能部署在物理节点的虚拟机中

    图 2  节点虚拟机资源充足和受限2种情况的解决方案

    图 3  pdh网络在不同资源配给下的OPEX

    图 4  pdh网络在不同资源配比下的求解时间

    图 5  Newyork网络在1个月中的流量分布

    图 6  Newyork网络在1个月中的OPEX

    表 1  算法1:发现可行的SFC部署方案

     输入:$G(V,E)$, $N$, $D$, ${M_k}$, ${l_k}$
     输出:${\rm VM}_i$, ${\rm finalSFC}_k$ by a tuple $\left\langle {{\rm order} \in {N^*},n \in N,i \in V} \;\right\rangle $,     ${R_k}$
     (1) while 未分配的请求${d_k} \in D$ do
     (2) 获取从${s_k}$到${t_k}$时延${l_k}$内的简单路径集合${P_k}$,以最短路径排序;
     (3)  t=0; //t为SFC中需要初始化的虚拟机个数
     (4)  while $t \le \left| {{M_k}} \right|$ and ${\rm Path}_k \in {P_k}$ do
     (5)  从$N$中选出所有t-子集的组合序列$\rm initVMs$;
     (6)  调用算法2得到请求$k$的预部署方案${\rm preSFC}_k$;
     (7)  if $\left| {{\rm preSFC}_k} \right| = = \left| {{M_k}} \right|$ the
     (8)  ${\rm finalSFC}_k \leftarrow {\rm preSFC}_k$, ${R_k} \leftarrow {\rm Path}_k$; break;
     (9)  end if
     (10) end while
     (11) end while
     (12) return ${\rm VM}_i$, ${\rm finalSFC}_k$, ${R_k}$;
    下载: 导出CSV

    表 2  算法2:请求SFC的预部署

     输入:$\rm initVMs$, ${\rm VM}_i$, ${C_i}$, $T_i^n$
     输出:${\rm preSFC}_k$ by a tuple $\left\langle {{\rm order} \in {N^*},n \in N,i \in V} \;\right\rangle $
     (1) ${\rm preSFC} \leftarrow \varnothing $;\; ${\rm order} \leftarrow 1$;//$\rm order$为SFC的次序索引
     (2) while $i \in V\;\;{\rm{in}}\;{{\rm Path}_k}$ and ${\rm order} \le \left| {{M_k}} \right|$ do
     (3)  $n = \left\{ {n|n \in N:{M_k} = {\rm order}} \right\}$//找到对应索引的VNF
     (4) if $n \in {\rm VM}_i$ and ${r_k} + {\rm VM}_i{的吞吐容量} \le T\ _i^n$ then
     (5)   ${\rm preSFC}_k \cup \left\{ {\left\langle {{\rm order},n,i} \right\rangle } \right\}$; $\rm order$++;返回步骤(2);
     (6) end if
     (7) if $n \notin {\rm VM}_i$ and $n \in {\rm initVMs}$ and $\left| {{\rm VM}_i} \right| < {C_i}$ then
     (8)  ${\rm VM}_i \cup \left\{ n \right\}$; ${\rm preSFC}_k \cup \left\{ {\left\langle {{\rm order},n,i} \right\rangle } \right\}$; $\rm order$++; 返回     步骤(2);
     (9) end if
     (10) end while
     (11) return ${\rm preSFC}_k$;
    下载: 导出CSV

    表 3  算法3:休眠活跃节点

     (1) while 活跃节点$i \in \!V\;$能被关闭 do
     (2) 关闭虚拟机数量最少且在图$G$中的度最小的节点$i$;
     (3) 调用算法1重新计算SFC部署方案;
     (4) 如果没有可行的方案,则回溯上次方案;
     (5) end while
    下载: 导出CSV
  • 加载中
图(6)表(3)
计量
  • PDF下载量:  38
  • 文章访问数:  467
  • HTML全文浏览量:  219
文章相关
  • 通讯作者:  张径, zj0910@mail.hfut.edu.cn
  • 收稿日期:  2018-05-28
  • 录用日期:  2018-11-30
  • 网络出版日期:  2018-12-10
  • 刊出日期:  2019-04-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章