Traffic aware placement of interdependent NFV middleboxes

TLDR

Network function virtualization enables flexible implementation of network functions as virtual machines on standard servers, but placement is challenging due to multiple hosting servers, variable traffic volumes, and inter‑middlebox dependencies. The paper tackles optimal placement of NFV middleboxes, proposing solutions for varying traffic effects and dependency relations. The authors formulate the placement as a graph optimization, devise optimal algorithms for predetermined flow paths, prove NP‑hardness for non‑ordered sets without predetermined paths, and propose a traffic‑ and space‑aware routing heuristic. Evaluation via large‑scale simulations and prototype experiments demonstrates the effectiveness of the proposed algorithms.

Abstract

Network function virtualization enables flexible implementation of network functions, or middleboxes, as virtual machines running on standard servers. However, the flexibility also creates a challenge for efficiently placing such middleboxes, due to the availability of multiple hosting servers, capability of middleboxes to change traffic volumes, and dependency between middleboxes. In this paper, we address the optimal placement challenge of NFV middleboxes, and propose solutions for middleboxes of different traffic changing effects and with different dependency relations. First, we formulate the Traffic Aware Placement of Interdependent Middleboxes problem as a graph optimization problem. When the flow path is predetermined, we design optimal algorithms to place a non-ordered or totally-ordered middlebox set, and propose an efficient heuristic for the general scenario of a partially-ordered middlebox set after proving its NP-hardness. When the flow path is not predetermined, we show that the problem is NP-hard even for a non-ordered middlebox set, and propose a traffic and space aware routing heuristic. We have evaluated the proposed algorithms using large scale simulations and prototype experiments, and present extensive evaluation results to demonstrate the effectiveness of our design.