Joint Optimization of Virtualized Network Function Placement and Routing Allocation for Operational Expenditure
-
摘要:
随着网络功能虚拟化(NFV)技术的发展，虚拟网络功能(VNF)可以通过服务功能链(SFC)的形式部署在如虚拟机的通用平台中，为管理带来灵活性。但是对于服务提供商来说，由于网络基础设施的复杂性和日益增长的服务需求，给VNF的部署带来了高昂的运营成本(OPEX)。针对此问题，该文提出一种面向OPEX优化的策略，旨在最小化OPEX中的激活、能耗和传输成本，得到VNF部署和路由分配优化方案。为此建立一种全新的混合整数线性规划(MILP)模型，并设计包括遗传算法(GA)在内的3种OPEX优化算法。仿真实验评估在不同资源配给下MILP和3种算法的OPEX及其性能，其中GA算法在节点资源配比60%以上时可以得到近似于MILP模型的解决方案。
Abstract:With the development of Network Function Virtualization (NFV), Virtual Network Functions (VNFs) can be deployed in a common platform such as virtual machines in the form of Service Function Chaining (SFC), providing flexibility for management. However for service providers, these come with high OPerational EXpenditure (OPEX), due to the complexity of the network infrastructure and the growing demand for services. To solve this problem, a strategy for OPEX optimization is proposed, which aims to minimize the startup cost, energy consumption, transmission cost and obtain VNF deployment and routing allocation optimization scheme. The VNF deployment problem as a new Mixed Integer Linear Programming (MILP) model is formulated, and three OPEX optimization algorithms are designed including Genetic Algorithm (GA). The OPEX of MILP model and optimization algorithms are compared under different resource allocation constraints. The calculation result shows that the GA can obtain the near-optimal solutions when node resource ratio is more than 60%.
-
表 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
-
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 XIN Li and CHEN Qian. A survey of network function placement[C]. Consumer Communications & Networking Conference, Las Vegas, USA, 2016: 948–953. 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 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 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 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 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. 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 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. 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. 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. 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 史久根, 许辉亮, 陆立鹏. 软件定义网络中数据中心虚拟机迁移序列问题的研究[J]. 电子与信息学报, 2017, 39(5): 1193–1199 doi: 10.11999/JEIT160792SHI 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 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. ASSAD A A. Multicommodity network flows—A survey[J]. Networks, 1978, 8(1): 37–91 doi: 10.1002/net.3230080107 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 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. -
下载:
计量
- 文章访问数: 1872
- HTML全文浏览量: 539
- PDF下载量: 61
- 被引次数: 0
