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

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

1. Н.Н. Кузюрин. Обобщенные покрытия и их аппроксимации. Труды ИСП РАН, том 6, 2004 г., стр. 85-100 / N.N. Kuzyurin. Generalized covers and their approximations. Trudy ISP RAN/Proc. ISP RAS, vol. 6, 2004, pp. 85-100 (in Russian).

2. Н.Н. Кузюрин. О сложности построения асимптотически оптимальных покрытий и упаковок. Доклады Академии наук, том 363, no. 1., 1998 г., стр. 11-13 / N. N. Kuzyurin, On the complexity of asymptotically optimal coverings and packing. Doklady Mathematics, vol. 58, no. 3, 1998, pp, 345-346.

3. А.В. Еремеев, Л.А. Заозерская, А.А. Колоколов. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования, Дискретный анализ и исследование операций, том 7, вып. 2, 2000 г., стр. 22-46 / A.V. Eremeev, L.A. Zaozerskaya, A.A. Kolokolov. The set covering problem: complexity, algorithms, and experimental investigations. Discrete Analysis and Operations Research, vol. 7, issue 2, 2000, pp. 22-46 (in Russian).

4. D. Lazarev. On MAX Monotonous XSAT, Exact Cover by Sets of Subsets and Parallel Computations in Software-Defined Network. Moscow Journal of Combinatorics and Number Theory, 2023 (in print).

5. И.Б. Бурдонов, Н.В. Евтушенко, А.С. Косачев. Тестирование правил настройки сетевого коммутатора программно конфигурируемой сети. Труды ИСП РАН, том 30, вып. 6, 2018 г., стр. 69-88. DOI: 10.15514/ISPRAS-2018-30(6)-4 / I.B. Burdonov, N.V. Yevtushenko, A.S. Kossatchev. Testing switch rules in software defined networks. Trudy ISP RAN/Proc. ISP RAS, vol. 30, issue 6, 2018, pp. 69-88 (in Russian).

6. I. Burdonov, A. Kossachev et al. Preventive Model-based Verification and Repairing for SDN Requests. In Proc. of the 16th International Conference on Evaluation of Novel Approaches to Software Engineering 2021, pp. 421-428.