maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2019-1-122-133mais-1167Research ArticleComputer System OrganizationАлгоритм минимизации количества правил маршрутизации в ПКСAlgorithm for Reducing the Number of Forwarding Rules Created by SDN Applicationshttps://orcid.org/0000-0002-7180-6373ПетровИван СергеевичPetrovIvan S.

аспирант

ул. Ленинские горы, 1, строение 52, г. Москва, 119992

PhD student

1, bd. 52 Leninskie gory, Moscow, 119992

ipetrov@cs.msu.ruМосковский государственный университет имени М.В. ЛомоносоваРоссияLomonosov Moscow State UniversityRussian Federation201915032019261122133Copyright © Петров И.С., 20192019Петров И.С.Petrov I.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1167

Архитектура ПКС (программно-конфигурируемые сети) предоставляет новые возможности по управлению сетью при помощи физического разделения уровня передачи данных (Data-Plane) от уровня управления данными (Control-Plane). Такое разделение достигается при помощи передачи функций управления сетью на отдельный сетевой элемент — контроллер. Архитектура ПКС позволяет устанавливать на контроллер сетевые приложения, которые могут использовать протокол OpenFlow для реализации множества различных сетевых функций, например для маршрутизации или анализа сетевой статистики. Анализ сетевой статистики производится при помощи счетчиков, установленных на правилах маршрутизации. Чтобы собирать информацию о числе пакетов в различных потоках, ПКС приложения могут устанавливать дополнительные правила маршрутизации, единственной целью которых является подсчет пакетов с определенными заголовками. Для полноценного анализа сетевой статистики приложения должны устанавливать в сеть большое количество дополнительных правил, что может привести к снижению производительности сети. В силу ограниченного размера таблиц маршрутизации, большое число дополнительных правил может мешать другим приложениям устанавливать свои правила. Таким образом, необходимо разработать алгоритм, который будет минимизировать число дополнительных правил. В данной работе рассмотрена задача минимизации числа дополнительных правил, устанавливаемых на ПКС коммутаторы приложениями для анализа сетевой статистики. Был разработан эвристический алгоритм минимизации количества правил маршрутизации, основанный на алгоритме Блейка нахождения сокращенной дизъюнктивной нормальной формы (ДНФ). Экспериментальные исследования показали, что алгоритм уменьшает число правил более чем в 2.2 раза на равномерно распределенных входных данных.

Software-Defined Networking (SDN) is a network architecture that introduces a physical separation of data-plane from control-plane. It implements a new way of analyzing network statistics through counters installed on forwarding rules. These counters measure the number of packets processed by these rules and represent per-flow network statistics. In order to get information about the number of packets from different flows SDN applications can install additional forwarding rules, sole purpose of which is to count packets with specific headers. But in order to produce a full network statistics analysis these applications may install a large amount of forwarding rules thus limiting the space in the forwarding table for other applications. So we need algorithms to minimize the number of such rules. In this paper, we consider the problem of minimizing the number of forwarding rules installed on SDN switches by applications that analyze network statistics. We introduce a heuristic algorithm that creates a reduced representation for sets of rules installed in the network. The experimental results show that this algorithm reduces the number of rules by at least 2.2 times on uniformly distributed random input.

ПКСсетевая статистикасчетчики правил маршрутизацииSDNnetwork statisticsforwarding rule countersReferencesПетров И. С., Смелянский Р. Л., “Минимизация группового трафика и обеспечение его отказоустойчивости в программно-конфигурируемых сетях”, Известия Российской академии наук. Теория и системы управления, 2018, № 3, 64–75.Petrov I.S., Smeliansky R.L., "Minimization of Multicast Traffic and Ensuring Its Fault Tolerance in Software-Defined Networks", Journal of Computer and Systems Sciences International, 57:3 (2018), 407-419.Petrov I. S., "Mathematical model for predicting forwarding rule counter values in SDN", Young Researchers in Electrical and Electronic Engineering (2018 IEEE Conference of Russian), 1313-1317.Petrov I. S., "Mathematical model for predicting forwarding rule counter values in SDN", Young Researchers in Electrical and Electronic Engineering (2018 IEEE Conference of Russian), 1313-1317.Смелянский Р. Л., “Программно-конфигурируемые сети”, Открытые системы. СУБД, 9 (2012), 15–26.Smeliansky R.L., "Software Defined Network", Open Systems. DBMS, 9 (2012), 15-26, (in Russian).OpenFlow Switch Specification, Version 1.5.1 (Protocol version 0x06), Open Networkig Foundation, 2015.OpenFlow Switch Specification, Version 1.5.1 (Protocol version 0x06), Open Networkig Foundation, 2015.Kazemian P., Varghese G., McKeown N., "Header Space Analysis: Static Checking for Networks", Proceedings of NSDI'12, 2012, 1-14.Kazemian P., Varghese G., McKeown N., "Header Space Analysis: Static Checking for Networks", Proceedings of NSDI'12, 2012, 1-14.Ложкин С. А., Лекции по основам кибернетики, М., 2017.Lozhkin S. A., Lektsii po osnovam kibernetiki, Moscow, 2017, (in Russian).Akyildiz I.F., et al., "A roadmap for traffic engineering in SDN-OpenFlow networks", Computer Networks, 71 (2014), 1-30.Akyildiz I.F., et al., "A roadmap for traffic engineering in SDN-OpenFlow networks", Computer Networks, 71 (2014), 1-30.Pang Chunhui, Yong Jiang, and Qi Li, "FADE: Detecting forwarding anomaly in softwaredefined networks", 2016 IEEE International Conference on Communications (ICC), IEEE, 2016, 1-6.Pang Chunhui, Yong Jiang, and Qi Li, "FADE: Detecting forwarding anomaly in softwaredefined networks", 2016 IEEE International Conference on Communications (ICC), IEEE, 2016, 1-6.Kamisinski A., Carol F., "Flowmon: Detecting malicious switches in software-defined networks", Proceedings of the 2015 Workshop on Automated Decision Making for Active Cyber Defense, ACM, 2015, 39-45.Kamisinski A., Carol F., "Flowmon: Detecting malicious switches in software-defined networks", Proceedings of the 2015 Workshop on Automated Decision Making for Active Cyber Defense, ACM, 2015, 39-45.Chao Tzu-Wei, et al, "Securing data planes in software-defined networks", NetSoft Conference and Workshops (NetSoft), IEEE, 2016, 465-470.Chao Tzu-Wei, et al, "Securing data planes in software-defined networks", NetSoft Conference and Workshops (NetSoft), IEEE, 2016, 465-470.Гайворонская С. А., Петров И. С., “О применимости методов обнаружения шеллкодов платформы x86 для платформы ARM”, Проблемы информационной безопасности. Компьютерные системы, 2014, № 3, 115–122.Gaivoronskaya S.A., Petrov I.S., "Towards Applicability of Shellcode Detection Methods Based on x86 Platform for Arm", Information Security Problems. Computer Systems, 2014, № 3, 115-122, (in Russian).Dhawan M., et al., "SPHINX: Detecting Security Attacks in Software-Defined Networks", NDSS, 2015, 8-11.Dhawan M., et al., "SPHINX: Detecting Security Attacks in Software-Defined Networks", NDSS, 2015, 8-11.

The authors declare that there are no conflicts of interest present.