Paper Info
Title
An Approximation Algorithm for Incrementally Deploying SDN Forwarding Devices
Abstract
There are two main optimization problems in software defined networks' traffic engineering, selecting conventional nodes to upgrade to SDN nodes, and finding a routing technique that minimize link utilization. While the second problem is almost solved, there are still not many theoretical results for the first problem. The approximation ratio of the only approximation algorithm for these problems is still as large as O(n), when n is the number of nodes. In this paper, we show that the problem is NP-hard, even for the single-source single-sink case. We then develop an algorithm for the case, and prove that our algorithm is kd-approximation algorithm, when k is the number of nodes to upgrade and d is the maximum degree of networks. We strongly believe that our algorithm can be extended to general cases in future.
Year
DOI
Venue
2018
10.1145/3164541.3164600
IMCOM
Keywords
Field
DocType
Networking/ Telecommunications, SDN, Graph Theory
Graph theory,Approximation algorithm,Computer science,Computer network,Upgrade,Degree (graph theory),Software-defined networking,Traffic engineering,Optimization problem,Computer engineering
Conference
ISBN
Citations 
PageRank 
978-1-4503-6385-3
0
0.34
References 
Authors
13
2
Name
Order
Citations
PageRank
Xusheng Zhang13913.00
Vorapong Suppakitpaisarn22813.11