Design and evaluation of schemes for provisioning service function chain with function scalability

Network Function Virtualization (NFV) and Software-Defined Networking (SDN) are two promising paradigms supporting flexible Service Function Chain (SFC) construction. In order to meet the dynamic requirements of enterprises or individuals, the SFC should be scalable to accommodate one or more functions joining or leaving it. We refer to this issue as the Scalable SFC Provision Problem (S2FCP2). Currently, the S2FCP2 is not well studied due to the risk and complexity of routing alteration. In this paper, we first formulate the S2FCP2 as an Integer Linear Programming (ILP) model and propose a scheme to solve this model. Then, to compensate for the limitation of the ILP model, the other heuristic schemes are proposed to address the S2FCP2. Specifically, the SFC requests are fulfilled with the backtracking strategy and the following scalable requests on adding or removing functions are fulfilled based on the reactive and proactive strategies respectively. In particular, the reactive scheme aims at fulfilling the scalable requests without changing the Service Function Path (SFP) while the proactive scheme is intended to optimize the SFP for better serving the subsequent arriving requests and thus achieving better network performance. The simulation results show that the ILP based scheme can obtain the optimal results, but it is limited by the network size; the heuristic schemes can get good (but maybe suboptimal) results and can be easily applied to both the large-scale and small-scale network scenarios.