Embedding Service Function Tree With Minimum Cost for NFV-Enabled Multicast
- 21 March 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 37 (5) , 1085-1097
Abstract
Usually, a data flow needs to traverse a series of network functions, which is called a service function chain (SFC), before reaching its destination. The emergence of network function virtualization (NFV) makes the embedding solution of the SFC flexible as far as the deployment location is concerned. When providers embed the SFC into a substrate network, they will hope to minimize the setup cost of the SFC and link connection cost toward clients. For unicast, since there is one path connecting the source node to the destination node, all functions of the SFC are just needed to be deployed along the path. However, when embedding the SFC for a multicast task, the topology of the SFC may change because the function deployment locations have impacts on the traffic delivery cost. Thus, a service function tree (SFT) may be a better choice. Given the huge space of SFT embedding solutions, however, it is extremely hard to find the optimal one such that the total traffic delivery cost is minimized. In this paper, we tackle the optimal SFT embedding problem in the NFV enabled multicast task. Specifically, we formally define the problem and formulate it with an integer linear programming (ILP), which turns out to be NP-hard. Then, a two-stage method is proposed to deal with the problem with an approximation ratio of 1+p , where p is the best approximation ratio of Steiner tree and can be as small as 1.39. With extensive experimental evaluations, we demonstrate that by applying our SFT embedding solution, the delivery cost of multicast traffic can be reduced by 22.05% at most against three benchmarks.Keywords
Funding Information
- National Natural Science Foundation of China (61802421, 61772544, U1536202, U1736216)
- National Key Research and Development Program of China (2017YFB1400700)
- Hunan Provincial Natural Science Fund for Distinguished Young Scholars (2016JJ1002)
- NUDT Research Plan (ZK17-03-50)
This publication has 35 references indexed in Scilit:
- Network Function Virtualization: State-of-the-Art and Research ChallengesIEEE Communications Surveys & Tutorials, 2015
- Reliable multicast routing for software-defined networks2015
- Near optimal placement of virtual network functions2015
- Network function virtualization: Challenges and opportunities for innovationsIEEE Communications Magazine, 2015
- Software-Defined Networking: A Comprehensive SurveyProceedings of the IEEE, 2014
- Service-aware network function placement for efficient traffic handling in carrier cloud2014
- Avalanche: Data center Multicast using software defined networking2014
- Revisiting IP multicast2006
- A fast algorithm for Steiner treesActa Informatica, 1981
- A note on two problems in connexion with graphsNumerische Mathematik, 1959