Анализ непротиворечивости реконфигурации программно-конфигурируемой сети

Рассматривается задача реконфигурации для программно-конфигурируемых сетей (SDN, software-defined networks), которая предполагает обновление таблиц маршрутизации с учетом свойств корректности (непротиворечивости). Как правило, SDN рассматривается как ориентированный граф, а свойства непротиворечивости могут быть сформулированы различными способами. Задача реконфигурации SDN с соблюдением свойств непротиворечивости в общем случае является NP-трудной задачей. В данной работе рассматривается модель программно-конфигурируемой сети как неориентированного графа, сформулирована задача реконфигурации, обладающая свойством непротиворечивости, которое заключается в отсутствии зацикливания пакетов при реконфигурации сети. Приводится алгоритм, позволяющий построить реконфигурирующую последовательность в худшем случае за квадратичное от числа вершин время.