Published on *Computer Science Department at Princeton University* (https://www.cs.princeton.edu)

Recent industry trends towards virtualization of network functions has led to a growing interest

in the problems of placement and configuration of so-called “middleboxes” to perform services on

the network traffic. The goal is to determine: how many middleboxes to run, where to place them,

and how to direct traffic through them. Towards this end, we introduce and study a new class of

multi-commodity flow problems. Here, in addition to demands on flows and capacity constraints on

edges in the network, there is an additional requirement that flows be processed by nodes in the

network.

We study the problems that arise from jointly optimizing the: (1) allocation of middleboxes over

a pool of server resources, (2) steering of traffic through middleboxes, and (3) routing of the traffic

between the servers over efficient network paths. We introduce and study several problems in this

class from the exact and approximation point of view.

We consider the problem of allocating resources within a given network to maximize the processed

flow and show that this can be optimized exactly via an LP formulation, and to arbitrary accuracy

via an efficient combinatorial algorithm. We also study a class of network design problems where

the goal is to purchase processing capacity in order to process and route a given set of demands in

a network. We design approximation algorithms as well as obtain hardness of approximation results

for four natural problems in this class: the minimization problem (minimize purchase cost so as to

process all the demand) and maximization problem (maximize flow processed subject to budget on

purchase cost) for both undirected and directed graphs.