Сборники трудов ИСП РАН


Покрытие графов циклами и быстрое восстановление оптоволоконных сетей.

Н.Н. Кузюрин, С.А. Фомин.

Аннотация

В данной статье мы рассматриваем технологию защиты сетей с помощью циклов (P-cycle technology), основанную на нахождении замкнутых путей (п-циклов) в топологиях оптоволоконных сетей. Задача нахождения оптимального набора п-циклов может быть сформулирована как задача целочисленного линейного программирования (ЦЛП), в которой переменные соответствуют циклам оптимизируемой сети. Стандартный подход заключается в использовании алгоритмов целочисленного линейного программирования, но проблема заключается в очень большом, зачастую экспоненциальном (от размера сети) числе переменных (циклов).

Мы предлагаем гибкий подход для генерации выделенного набора циклов, если множество всех циклов велико. Выделенный набор циклов имеет ограниченный размер и включает наряду с короткими циклами некоторое количество длинных циклов, полученных с помощью простых эвристических алгоритмов на графах и их случайных локальных преобразованиях. Представлена реализация и результаты тестирования для нового эффективного алгоритма генерации циклов в планарном графе. Предложены алгоритмы целочисленного линейного программирования, основанные на быстром извлечении относительно небольшого набора “важных” переменных, с помощью приближенного или вероятностного решения линейной релаксации исходной задачи ЦЛП. Разработана программная система «RingOptimizer», предназначенная для моделирования и решения этих задач. Проведенное тестирование показало эффективность предложенных алгоритмов.

Издание

Труды Института системного программирования РАН, том 5, 2004, стр. 249-268.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

Полный текст статьи в формате pdf Вернуться к содержанию тома