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

Huawei Huang, Peng Li, Song Guo, Weifa Liang, Kun Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)


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 the objective 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.

Original languageEnglish
Article number8166787
Pages (from-to)585-596
Number of pages12
JournalIEEE Transactions on Cloud Computing
Issue number2
Publication statusPublished - 1 Apr 2020


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

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Science Applications
  • Computer Networks and Communications

Cite this