Skip to main content

Multi-commodity Flow with In-Network Processing

Author(s): Charikar, Moses; Naamad, Yonatan; Rexford, Jenifer; Zou, X Kelvin

To refer to this page use:
Abstract: Modern networks run “middleboxes” that offer services ranging from network address translation and server load balancing to firewalls, encryption, and compression. In an industry trend known as Network Functions Virtualization (NFV), these middleboxes run as virtual machines on any commodity server, and the switches steer traffic through the relevant chain of services. Network administrators must decide how many middleboxes to run, where to place them, and how to direct traffic through them, based on the traffic load and the server and network capacity. Rather than placing specific kinds of middleboxes on each processing node, we argue that server virtualization allows each server node to host all middlebox functions, and simply vary the fraction of resources devoted to each one. This extra flexibility fundamentally changes the optimization problem the network administrators must solve to a new kind of multi-commodity flow problem, where the traffic flows consume bandwidth on the links as well as processing resources on the nodes. We show that allocating resources to maximize the processed flow can be optimized exactly via a linear programming formulation, and to arbitrary accuracy via an efficient combinatorial algorithm. Our experiments with real traffic and topologies show that a joint optimization of node and link resources leads to an efficient use of bandwidth and processing capacity. We also study a class of design problems that decide where to provide node capacity to best process and route a given set of demands, and demonstrate both approximation algorithms and hardness results for these problems.
Publication Date: 2019
Citation: Charikar, Moses, Yonatan Naamad, Jenifer Rexford, and X. Kelvin Zou. "Multi-commodity flow with in-network processing." Algorithmic Aspects of Cloud Computing 11409 (2019): 73-101. doi: 10.1007/978-3-030-19759-9_6
DOI: 10.1007/978-3-030-19759-9_6
ISSN: 0302-9743
EISSN: 1611-3349
Pages: 73 - 101
Type of Material: Conference Article
Series/Report no.: Lecture Notes in Computer Science;
Journal/Proceeding Title: Algorithmic Aspects of Cloud Computing
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.