Preview

Труды Института системного программирования РАН

Расширенный поиск

Совершенные множества путей в полном графе коммутаторов SDN-сети

https://doi.org/10.15514/ISPRAS-2020-32(4)-18

Полный текст:

Аннотация

В статье исследуется задача виртуализации сети на плоскости данных программно-конфигурируемой сети, моделируемой графом физических связей между узлами сети. Виртуальная сеть задается как множество упорядоченных пар хостов (отправитель, получатель), а реализуется множеством путей хост-хост, однозначно определяющим настройки коммутаторов. Множество путей совершенное, если любое подмножество связываемых им пар хостов связывается соответствующим подмножеством путей без возникновения бесконечного движения пакетов по циклу, без дублирующих путей, когда хост получает один и тот же пакет несколько раз, и без непредусмотренных путей, когда хост получает пакет, ему не предназначенный. Для случая, когда подграф, порождённый коммутаторами, является полным графом, устанавливаются достаточные условия существования наибольшего совершенного множества путей, связывающего все пары различных хостов. Предлагаются алгоритмы построения такого наибольшего совершенного множества и даются оценки их сложности. Приводятся результаты компьютерных экспериментов.

Об авторах

Игорь Борисович БУРДОНОВ
Институт системного программирования им. В.П. Иванникова РАН
Россия
доктор физико-математических наук, ведущий научный сотрудник


Евгений Максимович ВИНАРСКИЙ
Московский Государственный Университет им. М.В. Ломоносова
Россия
студент магистратуры, кафедра математической кибернетики факультета ВМК


Нина Владимировна ЕВТУШЕНКО
Институт системного программирования им. В.П. Иванникова РАН, Национальный исследовательский университет «Высшая школа экономики»
Россия
доктор технических наук, профессор, главный научный сотрудник ИСП РАН, профессор ВШЭ


Александр Сергеевич КОСАЧЕВ
Институт системного программирования им. В.П. Иванникова РАН
Россия
кандидат физико-математических наук, ведущий научный сотрудник


Список литературы

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

Просмотров: 48


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)