Transiently consistent SDN updates: being greedy is hard

DOI10.1007/978-3-319-48314-6_25MaRDI QIDQ2835039zbMATH OpenOpenAlexFDO

Authors Saeed Akhoondian Amiri, Arne Ludwig, Jan Marcinkowski, Stefan Schmid

Publication date 1 December 2016

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.03158

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Abstract: The software-defined networking paradigm introduces interesting opportunities to operate networks in a more flexible, optimized, yet formally verifiable manner. Despite the logically centralized control, however, a Software-Defined Network (SDN) is still a distributed system, with inherent delays between the switches and the controller. Especially the problem of changing network configurations in a consistent manner, also known as the consistent network update problem, has received much attention over the last years. In particular, it has been shown that there exists an inherent tradeoff between update consistency and speed. This paper revisits the problem of updating an SDN in a transiently consistent, loop-free manner. First, we rigorously prove that computing a maximum (greedy) loop-free network update is generally NP-hard; this result has implications for the classic maximum acyclic subgraph problem (the dual feedback arc set problem) as well. Second, we show that for special problem instances, fast and good approximation algorithms exist.

Recommendations

• Optimal consistent network updates in polynomial time
• Scheduling loop-free network updates: it's good to relax!
• Decentralizing SDN policies
• Automatic synthesis of transiently correct network updates via Petri games
• SDN-actors: modeling and verification of SDN programs

Cites work

• Decentralizing SDN policies
• Scheduling loop-free network updates: it's good to relax!

Cited in

(8)

• Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
• Automatic synthesis of transiently correct network updates via Petri games
• \textit{Renaissance}: a self-stabilizing distributed SDN control plane using in-band communications
• Scheduling loop-free network updates: it's good to relax!
• Decentralizing SDN policies
• Congestion-free rerouting of flows on DAGs
• Optimizing incremental SDN upgrades for load balancing in ISP networks
• Kaki: efficient concurrent update synthesis for SDN

This page was built for publication: Transiently consistent SDN updates: being greedy is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835039)