TY - JOUR
T1 - Loop-Free Route Updates for Software-Defined Networks
AU - Foerster, Klaus Tycho
AU - Ludwig, Arne
AU - Marcinkowski, Jan
AU - Schmid, Stefan
PY - 2018/2/1
Y1 - 2018/2/1
N2 - 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 Ω (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 Ω (n) in the best case), and present a scheduling algorithm which requires at most Θ (log n) rounds.
AB - 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 Ω (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 Ω (n) in the best case), and present a scheduling algorithm which requires at most Θ (log n) rounds.
KW - Graph algorithms
KW - NP-hardness
KW - Scheduling
KW - Software-defined networking
U2 - 10.1109/TNET.2017.2778426
DO - 10.1109/TNET.2017.2778426
M3 - Journal article
AN - SCOPUS:85038807241
SN - 1063-6692
VL - 26
SP - 328
EP - 341
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 1
ER -