Multi-commodity Flow with In-Network Processing

Moses Charikar, Yonatan Naamad, Jennifer L. Rexford, X. Kelvin Zou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAlgorithmic Aspects of Cloud Computing - 4th International Symposium, ALGOCLOUD 2018, Revised Selected Papers
EditorsVassilios S. Verykios, Yann Disser
PublisherSpringer Verlag
Number of pages29
ISBN (Print)9783030197582
StatePublished - 2019
Event4th International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2018 - Helsinki, Finland
Duration: Aug 20 2018Aug 21 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11409 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference4th International Symposium on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2018

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Approximation algorithms
  • Hardness of approximation
  • Middleboxes
  • Multi-commodity flow
  • Network Function Virtualization


Dive into the research topics of 'Multi-commodity Flow with In-Network Processing'. Together they form a unique fingerprint.

Cite this