Skip to main content

Multi-commodity Flow with In-Network Processing

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

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1d82q
Full metadata record
DC FieldValueLanguage
dc.contributor.authorCharikar, Moses-
dc.contributor.authorNaamad, Yonatan-
dc.contributor.authorRexford, Jenifer-
dc.contributor.authorZou, X Kelvin-
dc.date.accessioned2021-10-08T19:44:38Z-
dc.date.available2021-10-08T19:44:38Z-
dc.date.issued2019en_US
dc.identifier.citationCharikar, 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_6en_US
dc.identifier.issn0302-9743-
dc.identifier.uriftp://ftp.cs.princeton.edu/reports/2015/995.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1d82q-
dc.description.abstractModern 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.en_US
dc.format.extent73 - 101en_US
dc.language.isoen_USen_US
dc.relation.ispartofAlgorithmic Aspects of Cloud Computingen_US
dc.relation.ispartofseriesLecture Notes in Computer Science;-
dc.rightsAuthor's manuscripten_US
dc.titleMulti-commodity Flow with In-Network Processingen_US
dc.typeConference Articleen_US
dc.identifier.doi10.1007/978-3-030-19759-9_6-
dc.identifier.eissn1611-3349-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
MultiCommodityFlowInNetworkProcessing.pdf434.14 kBAdobe PDFView/Download


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