Multi-Commodity Flow with In-Network Processing
Report ID: TR-995-15Author: Charikar, Moses / Naamad, Yonatan / Rexford, Jennifer / Zou, Kelvin
Date: 2015-10-19
Pages: 24
Download Formats: |PDF|
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.