An approximation algorithm for path computation and function placement in SDNs

DOI10.1007/978-3-319-48314-6_24MaRDI QIDQ2835038zbMATH OpenOpenAlexFDO

Authors Guy Even, Matthias Rost, Stefan Schmid

Publication date 1 December 2016

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.09158

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25)

Abstract: We consider the task of computing (combined) function mapping and routing for requests in Software-Defined Networks (SDNs). Function mapping refers to the assignment of nodes in the substrate network to various processing stages that requests must undergo. Routing refers to the assignment of a path in the substrate network that begins in a source node of the request, traverses the nodes that are assigned functions for this request, and ends in a destination of the request. The algorithm either rejects a request or completely serves a request, and its goal is to maximize the sum of the benefits of the served requests. The solution must abide edge and vertex capacities. We follow the framework suggested by Even for the specification of the processing requirements and routing of requests via processing-and-routing graphs (PR-graphs). In this framework, each request has a demand, a benefit, and PR-graph. Our main result is a randomized approximation algorithm for path computation and function placement with the following guarantee. Let $m$ denote the number of links in the substrate network, $eps$ denote a parameter such that $0<eps<1$, and $op{t}_f$ denote the maximum benefit that can be attained by a fractional solution (one in which requests may be partly served and flow may be split along multiple paths). Let $cmin$ denote the minimum edge capacity, and let $dmax$ denote the maximum demand. Let $Deltamax$ denote an upper bound on the number of processing stages a request undergoes. If $cmin/(Deltamaxcdotdmax)=Omega((logm)/ep{s}^2)$, then with probability at least $$, the algorithm computes a $(1-eps)$-approximate solution.

Recommendations

• On-line path computation and function placement in SDNs
• On-line path computation and function placement in SDNs
• Service chain placement in SDNs
• Online admission control and embedding of service chains
• Competitive and deterministic embeddings of virtual networks

Cites work

• An approximation algorithm for path computation and function placement in SDNs
• scientific article; zbMATH DE number 910872 (Why is no real title available?)
• Online admission control and embedding of service chains
• OpenNF
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• vnep-approx

Cited in

(10)

• Perfect sets of paths in the full graph of SDN switches
• Relaxed and approximate graph realizations
• Service chain placement in SDNs
• An approximation algorithm for path computation and function placement in SDNs
• Online admission control and embedding of service chains
• Algorithm for Reducing the Number of Forwarding Rules Created by SDN Applications
• On-line path computation and function placement in SDNs
• Walking through waypoints
• On-line path computation and function placement in SDNs
• Robust network function virtualization

Describes a project that uses

Uses Software

• Merlin
• vnep-approx
• OpenNF

This page was built for publication: An approximation algorithm for path computation and function placement in SDNs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835038)