Safe, Efficient and Robust SDN Updates by Combining Rule Replacements and Additions

Sun, 07/02/2017 - 13:53 by Olivier Bonaventure


Disruption-free updates are a key primitive to ef- fectively operate SDN networks and maximize the benefits of their programmability. In this paper, we study how to implement this primitive safely (with respect to forwarding correctness and policies), efficiently (in terms of consumed network resources) and robustly to unpredictable factors like delayed message delivery and processing. First, we analyze the fundamental limitations of prior proposals, which either (i) progressively replace initial flow rules with new ones, or (ii) instruct switches to maintain both initial and final rules. Second, we show that safe, efficient and robust updates can be achieved by leveraging a more general approach. We indeed unveil a dualism between rule replacements and additions, that opens new degrees of freedom for supporting SDN updates. Third, we demonstrate how to build upon this du- alism. We propose FLIP, an algorithm that computes operational sequences combining the efficiency of rule replacements with the applicability of rule additions. FLIP identifies constraints on rule replacements and additions that independently prevent safety violations from occurring during the update. Then, it explores the solution space by swapping constraints that prevent the same safety violations, until it reaches a satisfiable set of constraints. Fourth, we perform extensive simulations, showing that FLIP can significantly outperform prior work: In the average case, it guarantees a much higher success rate than algorithms only based on rule replacements, and massively reduces the memory overhead needed by techniques solely using rule additions.

Stefano Vissicchio and Luca Cittadini
IEEE/ACM Transactions on Networking, to appear, 2017.
Available from
Cite it
See here

IEEE Copyright Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

ACM Copyright Notice: Copyright 1999 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page or intial screen of the document. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM Inc., fax +1 (212) 869-0481, or

Springer-Verlag LNCS Copyright Notice: The copyright of these contributions has been transferred to Springer-Verlag Berlin Heidelberg New York. The copyright transfer covers the exclusive right to reproduce and distribute the contribution, including reprints, translations, photographic reproductions, microform, electronic form (offline, online), or any other reproductions of similar nature. Online available from Springer-Verlag LNCS series.