Multi-Commodity Flow with In-Network Processing

Abstract:

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.