Совершенные множества путей в полном графе коммутаторов SDN-сети
Игорь Борисович БУРДОНОВ,
Евгений Максимович ВИНАРСКИЙ,
Нина Владимировна ЕВТУШЕНКО,
Александр Сергеевич КОСАЧЕВ https://doi.org/10.15514/ISPRAS-2020-32(4)-18
Аннотация
В статье исследуется задача виртуализации сети на плоскости данных программно-конфигурируемой сети, моделируемой графом физических связей между узлами сети. Виртуальная сеть задается как множество упорядоченных пар хостов (отправитель, получатель), а реализуется множеством путей хост-хост, однозначно определяющим настройки коммутаторов. Множество путей совершенное, если любое подмножество связываемых им пар хостов связывается соответствующим подмножеством путей без возникновения бесконечного движения пакетов по циклу, без дублирующих путей, когда хост получает один и тот же пакет несколько раз, и без непредусмотренных путей, когда хост получает пакет, ему не предназначенный. Для случая, когда подграф, порождённый коммутаторами, является полным графом, устанавливаются достаточные условия существования наибольшего совершенного множества путей, связывающего все пары различных хостов. Предлагаются алгоритмы построения такого наибольшего совершенного множества и даются оценки их сложности. Приводятся результаты компьютерных экспериментов.
Ключевые слова
программно-конфигурируемые сети,
виртуализация сети,
совершенные множества путей,
полный граф коммутаторов
При поддержке: Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 20-07-00338-a
Об авторах
Игорь Борисович БУРДОНОВ
Институт системного программирования им. В.П. Иванникова РАН
Россия
доктор физико-математических наук, ведущий научный сотрудник
Россия
доктор физико-математических наук, ведущий научный сотрудник
Евгений Максимович ВИНАРСКИЙ
Московский Государственный Университет им. М.В. Ломоносова
Россия
студент магистратуры, кафедра математической кибернетики факультета ВМК
Россия
студент магистратуры, кафедра математической кибернетики факультета ВМК
Нина Владимировна ЕВТУШЕНКО
Институт системного программирования им. В.П. Иванникова РАН,
Национальный исследовательский университет «Высшая школа экономики»
Россия
доктор технических наук, профессор, главный научный сотрудник ИСП РАН, профессор ВШЭ
Россия
доктор технических наук, профессор, главный научный сотрудник ИСП РАН, профессор ВШЭ
Александр Сергеевич КОСАЧЕВ
Институт системного программирования им. В.П. Иванникова РАН
Россия
кандидат физико-математических наук, ведущий научный сотрудник
Россия
кандидат физико-математических наук, ведущий научный сотрудник
Список литературы
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.
Рецензия
Для цитирования:
БУРДОНОВ И.Б., ВИНАРСКИЙ Е.М., ЕВТУШЕНКО Н.В., КОСАЧЕВ А.С. Совершенные множества путей в полном графе коммутаторов SDN-сети. Труды Института системного программирования РАН. 2020;32(4):245-260. https://doi.org/10.15514/ISPRAS-2020-32(4)-18
For citation:
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
Послать статью по эл. почте 