Perfect sets of paths in the full graph of SDN network switches
Igor Borisovich BURDONOV,
Evgeny Maksimovich VINARSKY,
Nina Vladimirovna YEVTUSHENKO,
Alexander Sergeevitch KOSSATCHEV https://doi.org/10.15514/ISPRAS-2020-32(4)-18
Abstract
The paper investigates the implementation of virtual networks on the SDN data plane which is modeled by a graph of physical connections between network nodes. A virtual network is defined as a set of ordered host pairs (sender, receiver), and it is implemented by a set of host-host paths that uniquely determine the switch settings. A set of paths is perfect if any subset of its paths can be loop-free implemented, i.e., can be implemented without the occurrence of an endless movement of packets in a loop, without duplicate paths, when the host receives the same packet several times, and without unintended paths when the host receives the packet that was directed to another host. For the case when the switchgraph is a complete graph, sufficient conditions for the existence of the largest perfect set of paths connecting all pairs of different hosts are established. Algorithms for constructing such a largest perfect set are proposed with the estimates of their complexity. The paper also has the preliminary results of computer experiments which show that proposed sufficient conditions are not necessary conditions.
Keywords
software defined networking,
network virtualization,
perfect sets of paths,
complete graph of switches
Supporting agencies: This work was supported by the Russian Foundation for Basic Research, project 20-07-00338-a
About the Authors
Igor Borisovich BURDONOV
Ivannikov Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Doctor of Physical and Mathematical Sciences, Leading Researcher
Russian Federation
Doctor of Physical and Mathematical Sciences, Leading Researcher
Evgeny Maksimovich VINARSKY
Lomonosov Moscow State University
Russian Federation
Master's student, Department of Mathematical Cybernetics, Faculty of CMC
Russian Federation
Master's student, Department of Mathematical Cybernetics, Faculty of CMC
Nina Vladimirovna YEVTUSHENKO
Ivannikov Institute for System Programming of the Russian Academy of Sciences,
National Research University Higher School of Economics
Russian Federation
doctor of technical sciences, professor, a leading researcher at ISP RAS, professor at HSE
Russian Federation
doctor of technical sciences, professor, a leading researcher at ISP RAS, professor at HSE
Alexander Sergeevitch KOSSATCHEV
Ivannikov Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Candidate of Physical and Mathematical Sciences, Leading Researcher
Russian Federation
Candidate of Physical and Mathematical Sciences, Leading Researcher
References
1. Sezer S., Scott-Hayward S., Chouhan P.K., Fraser B., Lake D., Finnegan J., Viljoen N., Miller M. and Rao N. Are we ready for sdn? Implementation challenges for software-defined networks. IEEE Communications Magazine, vol. 51, no. 7, 2013, pp. 36-43.
2. López J., Kushik N., Yevtushenko N. and Zeghlache D. Analyzing and Validating Virtual Network Requests. In Proc. of the 12th International Conference on Software Technologie, 2017, pp 441-446.
3. Yevtushenko N, Kossatchev A, Lopez J, Kushik N and Zeghlache D. Test Derivation for the Software Defined Networking Platforms: Novel Fault Models and Test Completeness. In Proc. of the IEEE East-West Design and Test Symposium, 2018, pp 1-6.
4. Бурдонов И.Б., Евтушенко Н.В., Косачев А.С. Тестирование правил настройки сетевого коммутатора программно конфигурируемой сети. Труды ИСП РАН, том 30, вып. 6, 2018 г., стр. 69-88. DOI: 10.15514/ISPRAS-2018-30(6)-4 / Burdonov I.B., Yevtushenko N.V. and Kossatchev.A.S. Testing switch rules in software defined networks. Trudy ISP RAN/Proc. ISP RAS, vol 30, issue 6, 2018, pp 69-88 (in Russian).
5. Burdonov I., Kossatchev A., Yevtushenko N., López J., Kushik N., and Zeghlache D. Verifying SDN Data Path Requests. arXiv:1906.03101, 2019.
6. Boufkhad Y., De La Paz R., Linguaglossa L., Mathieu F., Perino D., and Viennot L, Forwarding tables verification through representative header sets. arXiv:1601.07002, 2016.
7. Burdonov I., Yevtushenko N., and Kossatchev A. Implementing a virtual network on the SDN data plane. Accepted at the 2020 IEEE East-West Design and Test Symposium.
8. Кулямин В.В., Петухов А.А. Обзор методов построения покрывающих наборов. Программирование, том 37, № 3, стр. 3-41 / V.V. Kuliamin, A.A. Petukhov. A survey of methods for constructing covering arrays. Programming and Computer Softwareб vol. 37, № 3, 2011, article no. 121. https://doi.org/10.1134/S0361768811030029.
9. Kleitman Daniel J. and Spencer Joe. Families of k-independent sets. Discrete mathematics, vol. 6, 1973, pp. 255-262.
10. Choi Soohak, Kim Hyun Kwang, Oh Dong Yeol. Structures and lower bounds for binary covering arrays. Discrete mathematics, vol. 312, 2012, pp. 2958-2968.
11. Верещагин Н К, Шень А. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления. МЦНМО, 2012, 240 стр. / Vereshchagin N.K., Shen A. Lectures on mathematical logic and theory of algorithms. Part 2. Languages and Calculus. Moscow center for continuous mathematical education, 2012, 240 p.
12. Yurichev D. SAT/SMT by Example. URL; https://yurichev.com/SAT_SMT.html, accessed 20,07.2020.
13. Vinarskii E. perfect_set. URL: https://github.com/vinevg1996/perfect_set, accessed 20,07.2020.
Review
For citations:
BURDONOV I.B., VINARSKY E.M., YEVTUSHENKO N.V., KOSSATCHEV A.S. Perfect sets of paths in the full graph of SDN network switches. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2020;32(4):245-260. (In Russ.) https://doi.org/10.15514/ISPRAS-2020-32(4)-18
Email this article 