Bibliographic Details
| Title: |
Loop-Free Route Updates for Software-Defined Networks. |
| Authors: |
Foerster, Klaus-Tycho1, Ludwig, Arne2, Marcinkowski, Jan3, Schmid, Stefan4 |
| Source: |
IEEE/ACM Transactions on Networking. Feb2018, Vol. 26 Issue 1, p328-341. 14p. |
| Subjects: |
Graph algorithms, Traffic engineering software, IP networks, Loop tiling (Computer science), Integer programming |
| Abstract: |
We consider the fundamental problem of updating arbitrary routes in a software-defined network in a (transiently) loop-free manner. Our objective is to compute fast network update schedules which minimize the number of interactions (i.e., rounds) between the controller and the network nodes. We first prove that this problem is difficult in general: The problem of deciding whether a $k$ -round update schedule exists is NP-complete already for $k=3$ , and there are problem instances requiring $\Omega (n)$ rounds, where $n$ is the network size. Given these negative results, we introduce an attractive, relaxed notion of loop-freedom. We show that relaxed loop-freedom admits for much shorter update schedules (up to a factor $\Omega (n)$ in the best case), and present a scheduling algorithm which requires at most $\Theta (\log n)$ rounds. [ABSTRACT FROM AUTHOR] |
|
Copyright of IEEE/ACM Transactions on Networking is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
