  Middleboxes or network appliances like firewalls, proxies and WAN optimizers
have become an integral part of today's ISP and enterprise networks. Middlebox
functionalities are usually deployed on expensive and proprietary hardware that
require trained personnel for deployment and maintenance. Middleboxes
contribute significantly to a network's capital and operational costs. In
addition, organizations often require their traffic to pass through a specific
sequence of middleboxes for compliance with security and performance policies.
This makes the middlebox deployment and maintenance tasks even more
complicated. Network Function Virtualization (NFV) is an emerging and promising
technology that is envisioned to overcome these challenges. It proposes to move
packet processing from dedicated hardware middleboxes to software running on
commodity servers. In NFV terminology, software middleboxes are referred to as
Virtualized Network Functions (VNFs). It is a challenging problem to determine
the required number and placement of VNFs that optimizes network operational
costs and utilization, without violating service level agreements. We call this
the VNF Orchestration Problem (VNF-OP) and provide an Integer Linear
Programming (ILP) formulation with implementation in CPLEX. We also provide a
dynamic programming based heuristic to solve larger instances of VNF-OP. Trace
driven simulations on real-world network topologies demonstrate that the
heuristic can provide solutions that are within 1.3 times of the optimal
solution. Our experiments suggest that a VNF based approach can provide more
than 4x reduction in the operational cost of a network.
