Реализация распределённых и параллельных вычислений в сети SDN

В статье рассматривается выполнение на плоскости данных SDN, моделируемой конечным связным неориентированным графом физических связей, программы задания, которая понимается в духе парадигмы объектно-ориентированного программирования как состоящая из объектов и сообщений, которыми объекты могут обмениваться. Объекты реализуется в хостах, причём в одном хосте может быть реализовано несколько разных объектов, а один и тот же объект может быть реализован в нескольких хостах. Сообщения между объектами, реализованными в разных хостах, помещаются в пакеты, маршрутизацию которых исполняют коммутаторы на основе идентификаторов, присвоенных пакетам и помещаемых в заголовки пакетов как набор значений некоторых параметров пакетов. В работе решаются две задачи: 1) минимизация числа идентификаторов, 2) настройка коммутаторов для реализации путей, которые должны проходить пакеты. Эти задачи решаются в двух случаях: A) пакет, предназначенный для некоторого объекта, должен попасть ровно в один хост, в котором реализован этот объект, B) пакет может попадать в несколько хостов, но в одном и только одном из них должен быть реализован нужный объект. Показано, что задача 1 в случае A эквивалентна задаче о покрытии множества, а минимальное число идентификаторов в наихудшем случае равно $\min\{ n, m \}$, где $n$ число объектов, а $m$ число хостов, реализующих объекты. В случае B задача является специальной модификацией задачи о покрытии множества, высказывается гипотеза о том, что минимальное число идентификаторов в наихудшем случае равно $\min\{\lfloor lb(n + 1)\rfloor, m\}$. Пока получена верхняя оценка $O( \min \{ \ln (\min \{ n, m \}) \cdot \ln ( n, m ) \})$. Для решения задачи 2 в случаях A и B предложены алгоритмы настройки коммутаторов сложности, соответственно, $O( m )$ и $O( k m )$, где $m$ число рёбер графа физических связей, а $k$ результат решения задачи 1 в случае B как число требуемых идентификаторов пакетов.