Systems and Means of Informatics
2017, Volume 27, Issue 3, pp 12-22
CONSISTENCY ANALYSIS OF SOFTWARE-DEFINED NETWORKS RECONFIGURATION
- A. A. Grusho
- I. Yu. Teryokhina
Abstract
The paper studies the software-defined networks (SDN) reconfiguration problem, considering presence of consistency properties while updating the route tables. Generally, SDN is represented as an oriented graph, but consistency properties can be formulated in various ways. The SDN reconfiguration problem with respect to consistency properties is an NP-hard problem for most cases.
The paper defines the SDN model as an undirected graph and formulates the reconfiguration problem for this model that satisfies the loop-free consistency property while the network updates. For the introduced model, the worst-case quadratic algorithm of building the corresponding reconfiguration sequence from one configuration to another is proposed.
[+] References (16)
- Grusho, A., N. Grusho, V. Piskovski, and E. Timonina. 2014. Five SDN-oriented directions in information security. 12th Science and Technology Conference (International) "Modern Networking Technologies." IEEE. 68-71.
- Grusho, A. A., M. I. Zabezhailo, A. A. Zatsarinnyy, and V. O. Piskovski. 2016. Bezopasnaya avtomaticheskaya rekonfiguratsiya oblachnykh vychislitel'nykh sred [Secure automatic reconfiguration of cloudy computing]. Sistemy i Sredstva Informatiki - Systems and Means of Informatics 26(3):83-92.
- Reitblatt, M., N. Foster, J. Rexford, C. Schlesinger, and D. Walker. 2012. Abstractions for network update. ACM SIGCOMM 2012 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication Proceedings.
ACM. 323-334.
- Hong, C.Y., S. Kandula, R. Mahajan, M. Zhang, V. Gill, M. Nanduri, and R. Wattenhofer. 2013. Achieving high utilization with software-drivenWAN. ACM SIGCOMM Comp. Com. 43(4):15-26.
- McGeer, R. 2012. A safe, efficient update protocol for OpenFlow networks. 1st Workshop on Hot Topics in Software Defined Networks Proceedings. ACM. 61-66.
- Reitblatt, M., N. Foster, J. Rexford, and D. Walker. 2011. Software updates in openflow networks: Change you can believe in! HotNets-X: 10th ACM Workshop on Hot Topics in Networks Proceedings. - New York, NY: ACM. Available at: http://www.cs.cornell.edu/~jnfoster/papers/consistent-updates- hotnets11.pdf (accessed April 26, 2017).
- Ito, T., E. Demaine, N. Harvey, Ch. Papadimitriou, M. Sideri, R. Uehara, and Y. Uno. 2011. On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12-14): 1054-1065.
- Forster K. T., R. Mahajan, and R. Wattenhofer. 2016. Consistent updates in software defined networks: On dependencies, loop freedom, and blackholes. IFIP Networking Conference (IFIP Networking) and Workshops. IEEE. 1-9.
- McGeer, R. 2013. A correct, zero-overhead protocol for network updates. 2nd ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking Proceedings. ACM. 161-162.
- Jin, X., H. Liu, R. Gandhi, S. Kandula, R. Mahajan, J. Rexford, R. Wattenhofer, and M. Zhang. 2014. Dynamic scheduling of network updates. ACM SIGCOMM Comput. Com. 44(4):539-550.
- Brandt, S., K.-T. Forster, and R. Wattenhofer. 2016. Augmenting anycast network flows. 17th Conference (International) on Distributed Computing and Networking Proceedings. New York, NY: ACM. 24.
- Brandt S., K.-T. Forster, and R. Wattenhofer. 2016. On consistent migration of flows in SDNs. IEEE INFOCOM 2016: 35th Annual IEEE Conference (International) on Computer Communications. IEEE. 1-9.
- Francois, P., C. Filsfils, J. Evans, and O. Bonaventure. 2005. Achieving sub-second IGP convergence in large IP networks. ACM SIGCOMM Comput. Com. 35(3):35-44.
- Francois P., and O. Bonaventure. 2007. Avoiding transient loops during the convergence of link-state routing protocols. IEEE ACM T. Network. 15(6): 1280-1292.
- Francois, P., and O. Bonaventure. 2011. Loop-free convergence using oFIB. Internet- Draft. IETF. Available at: https://tools.ietf.org/html/draft-francois-ordered-fib-02 (accessed April 26, 2017).
- Garey, M. R., and D. S. Johnson. 1990. Computers and intractability. A guide to the theory of NP-completeness. New York, NY, USA: W. H. Freeman & Co. 351 p.
[+] About this article
Title
CONSISTENCY ANALYSIS OF SOFTWARE-DEFINED NETWORKS RECONFIGURATION
Journal
Systems and Means of Informatics
Volume 27, Issue 3, pp 12-22
Cover Date
2017-09-30
DOI
10.14357/08696527170302
Print ISSN
0869-6527
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
software-defined network; reconfiguration problem; consistency; network updates
Authors
A. A. Grusho  and I. Yu. Teryokhina 
Author Affiliations
Institute of Informatics Problems, Federal Research Center "Computer Science
and Control", Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
Faculty of Computational Mathematics and Cybernetics, M.V. Lomonosov Moscow State University, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation
|