Abstract: Network service providers have to cope with the growing on-demand need from end-users as well as the diversity of usage. The softwerization and cloudification of the network components offer an interesting solution to achieve the agility necessary to dynamically match the requirement with the level of resource consumption. This materializes with the deployment of Network Functions Virtualization (NFV) where Virtual Network Functions (VNFs) may be chained together to create network services. This paper explores important design and architectural issues related to this approach. We study the resource allocation problem in an NFV system for minimizing its cost under constraints on interconnectivity among VNFs, system resources, and service requirements. We formalize the problem in a comprehensive manner taking into account a broad set of relevant parameters. The static (offline) and dynamic (online) cases are considered. We propose and analyze three heuristic algorithms: two for handling large dimensions of the offline problem and one designed to address the online scenario. The evaluation shows that our solutions outperform the state of the art  with respect to critical performance index. Finally, we focus on the online scenario, evaluate the impact of migrating a set of running demands, and propose a simple migration technique.
Softwerization of network components is a candidate to provide the agility requested by the increasing on-demand need of customers as well as the ability to gently match those needs with the resource consumption. This trend is achieved by using a cloud approach where virtualization techniques are intensively exploited. Although this trend is prevalent, it is still necessary to better understand the right level of abstraction and hence performance that will be made possible with this approach. NFV relying upon virtualization techniques should support network operators to meet the growing customer requirements while controlling capital and operational expenditures.
In order to enable such an agile solution, a network service can be decomposed into an ordered sequence of VNFs (Virtual Network Functions), which can run on several standard physical nodes. Therefore, the resources allocated to a VNF instance will impact the capacity and performance of the network service as a whole. This raises important issues related to NFV deployment such as: 1) How and where to locate and chain VNFs? 2) How to distribute resources to VNFs? and 3) What is the cost of NFV deployment in a network? Such problems are different from the VM placement optimization in cloud computing as VNFs are associated with a single network service. In this paper, we consider a joint problem of VNFs allocation upon service requests from users and routing paths for chaining them. We develop a comprehensive solution addressing the static and dynamic scenario, when taking into account the execution order of VNFs in a service demand with regard to resource constraints for nodes and links.
The major contributions of this paper are as follows:
• We formulate the optimization problem of VNF placement as a quadratic program (QP) solving multiple objectives including optimal service location and optimal routing among VNF instances of a network service, under both resource and traffic cost constraints, simultaneously optimizing the acceptance ratio of new demands. Both the static and dynamic problems are considered.
• We propose three efficient heuristics for large dimensions of the problem within an acceptable computation time.
• We evaluate our proposed solutions in various scenarios and compare it against the ProvisionTraffic (PT) algorithm  that illustrates the state of the art, as well as a Random Algorithm.
• We provide a cost comparison between a network relying on NFV and a network that does not use NFV and discuss some architectural implications.
• We also propose a simple migration technique for the dynamic problem.
The result provides guidelines for the percentage of traffic to be migrated in order to achieve the best gain. The rest of this paper is organized as follows. Section II reviews the related work. In Section III, we model the NFV system under study and formalize the NFV placement problem. We present our solutions in Section IV. In Section V, we validate the algorithms and discuss the results. Section VI concludes the paper.