Тестирование правил настройки сетевого коммутатора программно конфигурируемой сети

В настоящее время SDN-технология активно используется в виртуальных сетях для реализации различных служебных сервисных функций. В основе сети лежит связный неориентированных граф физических связей (англ. Resource Network Connectivity Topology, RNCT), вершинами которого являются сетевые коммутаторы (switches) и хосты (hosts). В настоящей работе рассматривается топология, когда каждый хост соединен ровно с одним коммутатором. Коммутаторы работают по таблицам правил, которые настраиваются централизованно с помощью контроллера, работающего независимо от сетевого оборудования. Настройка коммутаторов сети предназначена для обеспечения передачи пакетов из начальных хостов в конечные хосты в зависимости от значений параметров пакетов. В статье обсуждается связь настроек коммутаторов и множества реализуемых ими путей передачи пакетов в зависимости от свойств графа физических связей. Исследуется задача тестирования настройки коммутаторов. Под целью тестирования понимается подача пакетов, позволяющих «пройти» по каждому правилу каждого коммутатора хотя бы один раз, подав пакет с необходимыми параметрами. Показывается, что в общем случае не любая настройка любого коммутатора проверяема. Возможности тестирования зависят от принимаемых гипотез о работе коммутатора. В статье рассматриваются две гипотезы: гипотеза о коммутаторе предполагает, что работа коммутатора не зависит от настроек других коммутаторов; более сильная гипотеза о правиле, кроме этого, предполагает, что работы коммутатора по данному правилу не зависит от других правил в настройке этого коммутатора. После введения, в разд. 2 вводятся необходимые определения и обозначения. Раздел 3 посвящен взаимосвязи путей в сети и правил в коммутаторах. В разд. 4 рассматривается тестирование на основе гипотезы о правиле, доказываются необходимые и достаточные условия возможности проверки заданного правила заданного коммутатора. В разд. 5 рассматривается тестирование на основе гипотезы о коммутаторе и доказывается необходимое (но не достаточное) условие и достаточное (но не необходимое) условие проверяемости любой настройки коммутатора. В заключении обсуждаются проблемы, возникающие при установлении необходимого и достаточного условия проверяемости любой настройки коммутатора, а также ставится задача определения таких условий для заданной настройки коммутатора.