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

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.

1 Introduction

Traditionally, network functions such as firewalls, unified threat management, and deep packet inspection are implemented in dedicated hardware appliances. NFV offers a paradigm enabling network functions to be decoupled from hardware and executed as software-based virtualized appliances in virtual machines (VMs), which are hosted on off-the-shelf physical machines (PMs) in datacenters. Thus, NFV offers great flexibility in realizing network services, such as network resilience, service assurance, test/diagnostics and security surveillance. Inspired by the great advantages of NFV, various design of programmable middleboxes has been proposed recently [1], [2], [3]. Combining with the software-defined networking (SDN) [4], NFV significantly simplifies the management of network services [5], [6], [7], [8].