On the complexity of a Virtual Network Function Placement and Routing problem

The demand for network services, such as proxy or firewall, is ever increasing due to the massive diffusion of applications, both on computers and mobile devices. Virtual Network Functions allow to instantiate network services on clouds in a software based manner, thus allowing to dynamically provide services at a reasonable cost. In this work we consider the problem of placing Virtual Network Function instances (services) and routing the demands so as to guarantee that demands can reach the requested services. We discuss the complexity of a particular version of the Virtual Network Function placement and routing problem and the impact of the network topology on the problem complexity.