2016/03/30 by Guy Even, Even, Guy, Matthias Rost +3 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Interconnection Networks and Systems #Networking and Internet Architecture (cs.NI) #Optimization and Search Problems #Software Engineering Techniques and Practices #Software Testing and Debugging Techniques #Software-Defined Networks and 5G
paper · pdf · doi:10.48550/arxiv.1603.09158
openalex publication_date 2016/03/30 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
We consider the task of computing (combined) function mapping and routing for\nrequests in Software-Defined Networks (SDNs). Function mapping refers to the\nassignment of nodes in the substrate network to various processing stages that\nrequests must undergo. Routing refers to the assignment of a path in the\nsubstrate network that begins in a source node of the request, traverses the\nnodes that are assigned functions for this request, and ends in a destination\nof the request. The algorithm either rejects a request or completely serves a\nrequest, and its goal is to maximize the sum of the benefits of the served\nrequests. The solution must abide edge and vertex capacities. We follow the\nframework suggested by Even for the specification of the processing\nrequirements and routing of requests via processing-and-routing graphs\n(PR-graphs). In this framework, each request has a demand, a benefit, and\nPR-graph. Our main result is a randomized approximation algorithm for path\ncomputation and function placement with the following guarantee. Let m denote\nthe number of links in the substrate network, eps denote a parameter such\nthat 0< eps <1, and optf denote the maximum benefit that can be attained\nby a fractional solution (one in which requests may be partly served and flow\nmay be split along multiple paths). Let cmin denote the minimum edge\ncapacity, and let dmax denote the maximum demand. Let Deltamax denote an\nupper bound on the number of processing stages a request undergoes. If\n cmin/( Deltamax\⋅ dmax)=\Ω((\log m)/ eps2), then with probability at\nleast 1-\(1)/(m)-\exp(-\Ω( eps2\⋅ optf /( bmax \⋅\n dmax))), the algorithm computes a (1- eps)-approximate solution.\n