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

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