On the Consistent Migration of Unsplittable Flows: Upper and Lower Complexity Bounds

Klaus-Tycho Förster

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

9 Citationer (Scopus)

Abstract

In consistent flow migration, the task is to change the paths the flows take in the network, but without inducing congestion during the  update process. Even though the rise of Software Defined Networks allows for centralized control of path changes, the execution is still performed in an inherently asynchronous system, the switches distributed over the network.
To this end, a multitude of scheduling systems have been proposed since the initial papers of Reitblatt et al. (Abstractions for Network Update, SIGCOMM ’12) and Hong et al. (SWAN, SIGCOMM ’13). While the the complexity of consistently migrating splittable flows is well understood, for the practically more relevant unsplittable flows, few non-heuristic results are known – and upper complexity bounds are missing.
We give a dynamic programming algorithm for unsplittable flows, showing the containment in EXPTIME, for both computation time and schedule length. In particular, there are cases where flows must switch between paths back and forth repeatedly: as thus, flow migration is not just an ordering problem. We also study lower bounds and show NP-hardness already for two flows, via reduction from edge-disjoint path problems. Lastly, we also discuss some practical application cases for our dynamic programming algorithm, furthermore showing how it can be extended to min-max load considerations.
OriginalsprogEngelsk
TitelNetwork Computing and Applications (NCA), 2017 IEEE 16th International Symposium on
ForlagIEEE
Publikationsdatodec. 2017
ISBN (Elektronisk)978-1-5386-1465-5
DOI
StatusUdgivet - dec. 2017
Begivenhed Network Computing and Applications - Cambridge, USA
Varighed: 30 okt. 20171 nov. 2017
Konferencens nummer: 16
http://www.ieee-nca.org/2017

Konference

Konference Network Computing and Applications
Nummer16
Land/OmrådeUSA
ByCambridge
Periode30/10/201701/11/2017
Internetadresse

Fingeraftryk

Dyk ned i forskningsemnerne om 'On the Consistent Migration of Unsplittable Flows: Upper and Lower Complexity Bounds'. Sammen danner de et unikt fingeraftryk.

Citationsformater