Near-Optimal Deployment of Service Chains by Exploiting Correlations between Network Functions

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

6 Scopus Citations
View graph of relations



Original languageEnglish
Article number8166787
Pages (from-to)585-596
Journal / PublicationIEEE Transactions on Cloud Computing
Issue number2
Online published6 Dec 2017
Publication statusPublished - Apr 2020
Externally publishedYes


A modern Network Function Virtualization (NFV) service is usually expressed in a service chain that contains a list of ordered network functions, each can run in one or multiple virtual machines. Although lots of efforts have been devoted to service chain deployment, the researchers normally consider a simple model of network functions where different service chains have their own network functions no matter whether some of the network function appliances are interdependent. In this paper, we study the service chain deployment by exploiting two types of correlations between network functions: the Coordination Effect due to information exchanges among multiple VMs running the same network function, and the Traffic-Change Effect where the volume of outgoing traffic is not necessarily equal to the volume of its incoming traffic at each network function because of packet manipulations such as compression and encryption. These two effects have not been studied simultaneously in the context of service chaining. With theobjective to maximize the profit measured by the admitted traffic minus the implementation cost, we first formulate a joint service-function deployment and traffic scheduling (SUPER) problem that is proved to be NP-hard. We then devise an approximation algorithm based on the Markov approximation technique and analyze its theoretical bound on the convergence time. Simulation results show that the proposed algorithm outperforms two existing benchmark algorithms significantly.

Research Area(s)

  • Coordination effect, Markov approximation, NFV, Service chain, Traffic-change effect

Citation Format(s)