On a virtual network functions placement and routing problem: Some properties and a comparison of two formulations

The mass diffusion of internet applications, both from computers and mobiles, has yielded to an increasing demand for network services with which the expensive and not flexible hardware appliances cannot keep up. On the other hand, computational capability has become available on the network nodes connected with computing servers and the cloud. This has suggested the network functions virtualization paradigm: services are provided on a software basis thus giving a flexible and cost effective response to the request for services. The network functions virtualization proposes challenging optimization problems such as the virtual network functions (VNFs) chaining problem, where service instances must be located on some network nodes and each demand must be routed through the services it requires. Most of the literature is currently focused on heuristic solutions, rather than on studying the problem properties or comparing approaches. With the aim of investigating the problem properties and comparing existing formulations, both from the theoretical and the numerical points of view, we consider a single service VNFs chaining problem, with different link and service capacities and the objective of minimizing the number of installed VNF instances.