Loading...
Please wait, while we are loading the content...
Similar Documents
Don’t disturb my Flows: Algorithms for Consistent Network Updates in Software Defined Networks
| Content Provider | Semantic Scholar |
|---|---|
| Author | Foerster, Klaus-Tycho |
| Copyright Year | 2016 |
| Abstract | In this dissertation, we consider the problem of finding efficient methods and complexity classifications for the consistent network update problem, with special focus on Software Defined Networks (SDNs). While the original and updated set of rules might both be consistent, disseminating the rule updates is an inherently asynchronous process, resulting in potentially inconsistent states. We study two fundamental consistency properties, first, loop freedom of forwarding rules, and second, consistent flow migration. For the consistency property of loop freedom, we focus on hardness results. We start with longest prefix matching rules, and show that both maximizing the number of rules updated at once and finding the fastest update schedule is an NP-complete problem. Our results are then extended by proving that deciding if a sublinear schedule exists is also NP-complete already for two destinations. For single-destination routing, the number of rules updated at once can be approximated well in polynomial time, but finding an optimal update set is NP-complete too. We also consider related problems, specifically the hardness of fast blackhole-free updates under memory restrictions, the use of labeling schemes for local loop-free updates, and flipping the approach by generating efficient failure scenarios for reachability testing of a SDN controller. For the consistent migration of flows, we show that for most scenarios involving splittable flows, the problem is in P, but NP-complete to decide for unsplittable flows. Specifically, we start by considering the standard flow migration model, where the bandwidth of every edge should be respected, no matter if each individual flow is in its old or its new state. We then extend this model in three ways: First, we develop non-mixing flow migration, where each packet respects waypointing and service chains. Second, we show the standard model to be susceptible to packet loss, and develop a lossless flow migration model. Third and last, we decouple the flow migration problem from a fixed new set of paths, and just consider the new set of demands: For the case of multi-commodity flows with one destination, this change allows to greatly improve the number of updates needed in the worst case. For all of these models, we present the first algorithms that can decide if a consistent flow migration for splittable flows exists, and also provide an implicit schedule. On the hardness side, we show the decision problems for unsplittable flows to be NP-complete, whereas previous work only considered fastest update schedules. |
| File Format | PDF HTM / HTML |
| DOI | 10.3929/ethz-a-010733901 |
| Alternate Webpage(s) | https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/121315/eth-49749-01.pdf |
| Alternate Webpage(s) | https://ktfoerster.github.io/paper/ETH23703.pdf |
| Alternate Webpage(s) | https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/121315/eth-49749-01.pdf?isAllowed=y&sequence=2 |
| Alternate Webpage(s) | https://doi.org/10.3929/ethz-a-010733901 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
