On Optimal Placement of Monotype Network Functions in a Distributed Operator Network

Many network operators use a large number of intermediate devices like firewalls or antiviruses implemented on the proprietary hardware. Installation and maintenance of this equipment are very expensive. Therefore the network function virtualization technology allowing flexible remote services management through a software is a promising option for organizing operator network architecture. Switching to software appliances instead of specialized hardware can optimize the administration of the network functions, significantly reducing its cost. However, a problem of determining a number of virtual network functions and their placement in a distributed network that optimizes operating costs and meets service level agreement is a complex mathematical problem. The paper deals with a problem of efficient monotype network functions placement in a distributed network in order to minimize the total cost, with restrictions on channel delays, throughput and node performance. NP-completeness of the problem is proved, the statement is given in terms of integer linear programming. A heuristic algorithm is proposed and its efficiency is shown on typical network topologies.