Multi-Commodity Flow with In-Network Processing

We introduce and study a new class of multi-commodity flow problems where, 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. These problems are motivated by the placement and configuration of so-called middleboxes at nodes in the network so as to perform services on the network traffic: how many middleboxes to run, where to place them and how to direct traffic through them? We study the problems that arise from jointly optimizing the: (1) placement of middleboxes over a pool of server resources, (2) steering of traffic through a suitable sequence of 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.