Arne Ludwig
Stefan Schmid
ABSTRACT
We consider the problem of updating arbitrary routes in a software-defined network in a (transiently) loop-free manner. We are interested in fast network updates, i.e., in 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 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 prove that O(log n)-round relaxed loop-free schedules always exist, and can also be computed efficiently.
- M. Canini, P. Kuznetsov, D. Levin, and S. Schmid. A distributed and robust sdn control plane for transactional network updates. In Proc. 34th IEEE Conference on Computer Communications (INFOCOM), 2015.Google Scholar
Cross Ref
- M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. McKeown, and S. Shenker. Ethane: Taking control of the enterprise. In Proc. ACM SIGCOMM, 2007. Google ScholarDigital Library
- S. K. Fayazbakhsh, V. Sekar, M. Yu, and J. C. Mogul. Flowtags: Enforcing network-wide policies in the presence of dynamic middlebox actions. In Proc. ACM SIGCOMM HotSDN, 2013. Google ScholarDigital Library
- N. Feamster, J. Rexford, and E. Zegura. The road to sdn. Queue, 11(12):20:20--20:40, 2013. Google ScholarDigital Library
- S. Ghorbani and B. Godfrey. Towards correct network virtualization. In Proc. ACM HotSDN, pages 109--114, 2014. Google ScholarDigital Library
- A. Greenberg, G. Hjalmtysson, D. A. Maltz, A. Myers, J. Rexford, G. Xie, H. Yan, J. Zhan, and H. Zhang. A clean slate 4d approach to network control and management. SIGCOMM Comput. Commun. Rev., 35(5):41--54, 2005. Google ScholarDigital Library
- A. Gupta, L. Vanbever, M. Shahbaz, S. P. Donovan, B. Schlinker, N. Feamster, J. Rexford, S. Shenker, R. Clark, and E. Katz-Bassett. Sdx: A software defined internet exchange. In Proc. ACM SIGCOMM, pages 551--562, 2014. Google ScholarDigital Library
- X. Jin, H. Liu, R. Gandhi, S. Kandula, R. Mahajan, J. Rexford, R. Wattenhofer, and M. Zhang. Dionysus: Dynamic Scheduling of Network Updates. In Annual Conference of the ACM Special Interest Group on Data Communication (SIGCOMM), Chicago, Illinois, USA, August 2014. Google ScholarDigital Library
- P. Kazemian, M. Chang, H. Zeng, G. Varghese, N. McKeown, and S. Whyte. Real time network policy checking using header space analysis. In Proc. 10th USENIX Conference on Networked Systems Design and Implementation (NSDI), pages 99--112, 2013. Google ScholarDigital Library
- M. Kuzniar, P. Peresini, and D. Kostic. What you need to know about sdn flow tables. In Proc. Passive and Active Measurements Conference (PAM), 2015.Google ScholarCross Ref
- H. H. Liu, X. Wu, M. Zhang, L. Yuan, R. Wattenhofer, and D. A. Maltz. zUpdate: Updating Data Center Networks with Zero Loss. In Annual Conference of the ACM Special Interest Group on Data Communication (SIGCOMM), Hong Kong, August 2013. Google ScholarDigital Library
- A. Ludwig, M. Rost, D. Foucard, and S. Schmid. Good network updates for bad packets: Waypoint enforcement beyond destination-based routing policies. In Proc. ACM Workshop on Hot Topics in Networks (HotNets), 2014. Google ScholarDigital Library
- R. Mahajan and R. Wattenhofer. On Consistent Updates in Software Defined Networks. In Proc. 12th ACM Workshop on Hot Topics in Networks (HotNets), 2013. Google ScholarDigital Library
- J. Martins, M. Ahmed, C. Raiciu, V. Olteanu, M. Honda, R. Bifulco, and F. Huici. Clickos and the art of network function virtualization. In Proc. 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI), pages 459--473, 2014. Google ScholarDigital Library
- J. McClurg, H. Hojjat, P. Cerny, and N. Foster. Efficient synthesis of network updates. In Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2015. Google ScholarDigital Library
- C. Monsanto, J. Reich, N. Foster, J. Rexford, and D. Walker. Composing Software Defined Networks. In Proc. NSDI, 2013. Google ScholarDigital Library
- M. Reitblatt, N. Foster, J. Rexford, C. Schlesinger, and D. Walker. Abstractions for network update. In Proc. ACM SIGCOMM, pages 323--334, 2012. Google ScholarDigital Library
Index Terms
- Scheduling Loop-free Network Updates: It's Good to Relax!
Recommendations
Dynamic scheduling of network updates
SIGCOMM'14We present Dionysus, a system for fast, consistent network updates in software-defined networks. Dionysus encodes as a graph the consistency-related dependencies among updates at individual switches, and it then dynamically schedules these updates based ...
Transiently Secure Network Updates
Performance evaluation reviewComputer networks have become a critical infrastructure. Especially in shared environments such as datacenters it is important that a correct, consistent and secure network operation is guaranteed at any time, even during routing policy updates. In ...
Transiently Secure Network Updates
SIGMETRICS '16: Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer ScienceComputer networks have become a critical infrastructure. Especially in shared environments such as datacenters it is important that a correct, consistent and secure network operation is guaranteed at any time, even during routing policy updates. In ...
Comments