Безопасная реализация виртуальной сети на плоскости данных SDN

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