Independent set conditions for all fractional ( g,f,n ′,m )-critical deleted NFV networks

Abstract

Network function virtualization (NFV) can be regarded as the latest trick development in the provisioning of network service. Software programs are running on virtual machines and industry standard servers to replace the traditional hardware middleboxes, and thus lead to flexibility, service agility and cost decreasing. A basic problem in NFV service chain provisioning is the ability of resource scheduling which equals to the existence of fractional factor. The concept of all fractional (g, f, n′, m)-critical deleted graph is the extension of fractional (g, f, n′, m)-critical deleted graph. In this paper, we consider the resource scheduling problem in NFV networks using graph theory, and an independent set degree condition and an independent set neighborhood union condition for all fractional (g, f, n′, m)-critical deleted graphs are determined. Furthermore, we show that the result are tight on independent set condition.