Марк Ш. Левин

Обзорная заметка о задаче размещения контроллеров

В данной обзорной статье рассматривается задача размещения контроллеров в сетях связи: типы задач, модели, стратегии решения. В основном задача базируется на моделях комбинаторной оптимизации: задача кластеризация и задача k-центров (k-медиан). Традиционная схема решения включает следующие стадии: (1) определение оптимального числа контроллеров, (2) размещение контроллеров, (3) определение типов контроллеров, (4) построение связей между элементами исходной сети (присоединение переключателей к контроллерам, построение связей между контроллерами). В задаче размещения контроллеров обычно уделяется внимание вспомогательным задачам комбинаторной оптимизации, например: задача назначения/размещения, задача разбиения исходного графа (сети), задача покрытия исходного графа (сети), задача построения доминирующего множества, задача построения независимого множества, задача о рюкзаке, задача ранжирования. В работе описаны основные формулировки задачи размещения контролеров (включая многокритериальные постановки). Представлены иллюстрации для рассматриваемых задач и схем решения

КЛЮЧЕВЫЕ СЛОВА: системы связи, размещение контроллеров, комбинаторная оптимизация, эвристики, обзор.