Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
An Approximation Algorithm for Path Computation and Function Placement in SDNs
verfasst von : Guy Even, Matthias Rost, Stefan Schmid
Erschienen in: Structural Information and Communication Complexity
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We consider the task of embedding multiple service requests in Software-Defined Networks (SDNs), i.e. computing (combined) mappings of network functions on physical nodes and finding routes to connect the mapped network functions. A single service request may either be fully embedded or be rejected. The objective is to maximize the sum of benefits of the served requests, while the solution must abide node and edge capacities.
We follow the framework suggested by Even et al. [5] for the specification of the network functions and routing of requests via processing-and-routing graphs (PR-graphs): a request is represented as a directed acyclic graph with the nodes representing network functions. Additionally, a unique source and a unique sink node are given for each request, such that any source-sink path represents a feasible chain of network functions to realize the service. This allows for example to choose between different realizations of the same network function. Requests are attributed with a global demand (e.g. specified in terms of bandwidth) and a benefit.
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, \(\varepsilon \) denote a parameter such that \(0< \varepsilon <1\), and \(\mathsf {opt}^*\) 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 \(c_{\min }\) denote the minimum edge capacity, let \(d_{\max }\) denote the maximum demand, and let \(b_{\max }\) denote the maximum benefit of a request. Let \(\varDelta _{\max }\) denote an upper bound on the number of processing stages a request undergoes. If \(c_{\min }/(\varDelta _{\max }\cdot d_{\max })=\varOmega ((\log m)/\varepsilon ^2)\), then with probability at least \(1-\frac{1}{m}-\textit{exp}(-\varOmega (\varepsilon ^2\cdot \mathsf {opt}^*/(b_{\max }\cdot d_{\max })))\), the algorithm computes a \((1-\varepsilon )\)-approximate solution.