Покрытие графов циклами и быстрое восстановление оптоволоконных сетей.
News
Покрытие графов циклами и быстрое восстановление оптоволоконных сетей.
Abstract
В данной статье мы рассматриваем технологию защиты сетей с помощью циклов (P-cycle technology), основанную на нахождении замкнутых путей (п-циклов) в топологиях оптоволоконных сетей. Задача нахождения оптимального набора п-циклов может быть сформулирована как задача целочисленного линейного программирования (ЦЛП), в которой переменные соответствуют циклам оптимизируемой сети. Стандартный подход заключается в использовании алгоритмов целочисленного линейного программирования, но проблема заключается в очень большом, зачастую экспоненциальном (от размера сети) числе переменных (циклов).
Мы предлагаем гибкий подход для генерации выделенного набора циклов, если множество всех циклов велико. Выделенный набор циклов имеет ограниченный размер и включает наряду с короткими циклами некоторое количество длинных циклов, полученных с помощью простых эвристических алгоритмов на графах и их случайных локальных преобразованиях. Представлена реализация и результаты тестирования для нового эффективного алгоритма генерации циклов в планарном графе. Предложены алгоритмы целочисленного линейного программирования, основанные на быстром извлечении относительно небольшого набора “важных” переменных, с помощью приближенного или вероятностного решения линейной релаксации исходной задачи ЦЛП. Разработана программная система «RingOptimizer», предназначенная для моделирования и решения этих задач. Проведенное тестирование показало эффективность предложенных алгоритмов.
Edition
Proceedings of the Institute for System Programming, vol. 5 (in Russian), 2004, Стр. 249-268.
ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).
For citation
Full text of the paper in pdf (in Russian)
Back to the contents of the volume