Network Function Virtualization (NFV) enables flex- ible deployment of middleboxes as Virtual Machines (VMs) running on general hardware. Different types of middleboxes have the potential to either increase or decrease the volume of processed traffic. In this paper, we investigate the traffic changing effects of middleboxes, and study efficient deployment of NFV middleboxes in Software-Defined Networks (SDNs). To begin with, we formulate the Traffic-Aware Middlebox Placement (TAMP) problem as a graph optimization problem, and show that it is NP-hard when there are multiple flows to consider. Next, by observing that in reality flows arrive one at a time, we leverage the SDN central control mechanism, and propose an optimal solution for the TAMP problem with a single flow. We develop the solution in two steps. First, when the flow path has been determined, we present the Least-First-Greatest- Last (LFGL) rule to place middleboxes. Second, we integrate the LFGL rule with widest-path routing to propose the LFGL based MinMax routing algorithm. Further, we have implemented the proposed algorithm as a module running on top of the Floodlight SDN controller, and conducted experiments in the Mininet emulation system. The experiment results fully demonstrate the superiority of our algorithm over other benchmark solutions.
