Введение

Проблема маршрутизации и назначения длин волн (RWA) — это задача в области оптических сетей, целью которой является максимизация числа оптических соединений.

Фиксированная маршрутизация

Фиксированный маршрут — это самый простой подход к поиску светового пути. Для заданной пары источник-назначение всегда используется один и тот же фиксированный маршрут. Обычно этот путь вычисляется заранее с использованием алгоритма поиска кратчайшего пути, такого как алгоритм Дейкстры. Хотя этот подход очень прост, его производительность обычно недостаточна. Если ресурсы на фиксированном пути заняты, будущие запросы на соединение будут отклонены, даже если существуют другие доступные пути. Алгоритм SP 1 (Shortest Path, 1 Probe) является примером решения с фиксированным маршрутом. Этот алгоритм вычисляет кратчайший путь, используя количество оптических маршрутизаторов в качестве функции стоимости. Для установления соединения используется один зонд, использующий кратчайший путь. Время работы алгоритма соответствует сложности алгоритма Дейкстры: , где — количество ребер, а — количество маршрутизаторов. Если используется заранее определенный путь, время работы алгоритма становится константой. В данном определении SP 1 в качестве функции стоимости используется количество переходов (hops). Алгоритм SP 1 может быть расширен для использования различных функций стоимости, например, количества усилителей EDFA.

Фиксированный альтернативный маршрут

Фиксированная альтернативная маршрутизация является расширением маршрутизации по фиксированному пути. Вместо одного фиксированного маршрута для заданной пары источник-назначение, сохраняется несколько маршрутов. Зондирование может выполняться последовательно или параллельно. Для каждого запроса на установление соединения, исходный узел пытается установить соединение по каждому из доступных путей. Если все пути оказываются недоступны, соединение блокируется. Если доступно несколько путей, используется только один из них. Алгоритм SP (Shortest Path, Probes) является примером фиксированной альтернативной маршрутизации. Этот алгоритм вычисляет кратчайшие пути, используя количество оптических маршрутизаторов в качестве функции стоимости. Время работы алгоритма Йена составляет , где – количество ребер, – количество маршрутизаторов, а – количество путей. Если пути вычислены заранее, время работы становится постоянным множителем.

Адаптируемая маршрутизация

Основная проблема как фиксированной маршрутизации, так и фиксированной альтернативной маршрутизации заключается в том, что ни один из этих алгоритмов не учитывает текущее состояние сети. Если предопределенные пути недоступны, запрос на соединение будет заблокирован, даже если существуют другие возможные пути. Фиксированная маршрутизация и фиксированная альтернативная маршрутизация не учитывают качество связи. По этим причинам, большинство исследований в области RWA в настоящее время сосредоточено на адаптивных алгоритмах. Пять примеров адаптивной маршрутизации: LORA, PABR, IA BF, IA FF и AQoS. Адаптивные алгоритмы делятся на две категории: традиционные и учитывающие физические параметры. Традиционные адаптивные алгоритмы не принимают во внимание качество сигнала, в то время как адаптивные алгоритмы, учитывающие физические параметры, – учитывают.

Традиционные адаптивные РВА

В 2001 году был предложен алгоритм лексикографической маршрутизации (LORA). Основная идея LORA заключается в маршрутизации запросов на соединение в обход перегруженных участков сети, что повышает вероятность их принятия. Это достигается путем установки стоимости каждой линии связи равной , где – параметр, который может динамически изменяться в зависимости от нагрузки трафика, а – количество используемых длин волн на данной линии связи. Затем для поиска пути можно использовать стандартный алгоритм поиска кратчайшего пути. Это требует от каждого оптического коммутатора периодической трансляции информации о недавнем использовании ресурсов. Следует отметить, что LORA не учитывает физические ограничения. При значении , равном единице, алгоритм LORA идентичен алгоритму SP. Увеличение значения приведет к большему предпочтению менее загруженных маршрутов. Оптимальное значение можно вычислить с помощью известного алгоритма поиска методом подъема на холме. В предложении оптимальные значения находились в диапазоне от 1,1 до 1,2.

Физически осознаваемые адаптивные RWA

Алгоритм физически осведомленного резервирования (PABR) является расширением LORA. PABR способен повысить производительность двумя способами: учитывая физические искажения и улучшенный выбор длины волны. В процессе поиска оптического пути, пути с неприемлемым качеством сигнала из-за линейных искажений отбрасываются. Иными словами, PABR – это LORA с дополнительным ограничением по качеству. Следует отметить, что PABR может учитывать только линейные искажения. Нелинейные искажения, в свою очередь, невозможно оценить в распределенной среде из-за необходимости обладать информацией о глобальном трафике. PABR также учитывает качество сигнала при выборе длины волны, исключая из рассмотрения все длины волн с неприемлемым уровнем качества сигнала. Этот подход называется "Подбор по качеству в первую очередь" и подробно рассматривается в следующем разделе. Как LORA, так и PABR могут быть реализованы с использованием однократного или многократного зондирования. Максимальное количество зондов обозначается как LORA или PABR. При однократном зондировании маршрут выбирает только один путь. При многократном зондировании несколько путей тестируются параллельно, что повышает вероятность успешного установления соединения.

Другие подходы к маршрутизации

В IA BF был предложен алгоритм "Осознание нарушений наилучшей пригодности" (IA BF). Этот алгоритм представляет собой распределенный подход, зависящий от большого объема обмена информацией для использования глобальных данных и постоянного выбора кратчайшего доступного пути и длины волны. Это достигается посредством последовательного многозондового поиска. Сначала предпринимается попытка использования кратчайшего доступного пути и длины волны, а в случае неудачи – второго по кратчайшему доступного пути и длины волны. Этот процесс продолжается до тех пор, пока не будет найден подходящий путь и длина волны, или не будут исчерпаны все доступные длины волн. Многозондовый подход позволит IA BF превзойти алгоритмы PABR 1 и LORA 1. Однако, с увеличением числа зондов, производительность алгоритмов становится сопоставимой. IA FF – алгоритм "Осознание нарушений первого подходящего" (IA FF) является простым расширением IA BF. Вместо выбора длин волн на основе минимальной стоимости, они выбираются в порядке их индекса. В большинстве сценариев IA BF показывает лучшие результаты, чем IA FF. AQoS – адаптивное качество обслуживания (AQoS) был предложен в. Этот алгоритм уникален в нескольких аспектах. Во-первых, каждый узел поддерживает два счетчика: и. Цель каждого счетчика – определить, какой фактор оказывает большее влияние на блокировку: доступность пути и длины волны или требования к качеству. Алгоритм выбирает маршруты по-разному, в зависимости от наиболее значимого фактора. Другая особенность заключается в том, что AQoS использует Q-фактор в качестве стоимости канала. Стоимость канала рассчитывается по формуле, где – количество световых путей на канале, а – измерения коэффициента качества светового пути в исходном и конечном узлах канала соответственно. Многократные оценки Q-фактора требуют значительных вычислительных ресурсов. Этот алгоритм использует однозондовый поиск. Многозондовый подход, который в статье назван ALT AQoS (альтернативный AQoS), является простым расширением той же базовой идеи.

Присвоение длины волны

Два наиболее распространенных метода назначения длин волн – First Fit и Random Fit. First Fit выбирает доступную длину волны с наименьшим индексом. Random Fit определяет, какие длины волн доступны, и затем случайно выбирает одну из них. Временная сложность обоих алгоритмов составляет , где – количество длин волн. First Fit работает лучше, чем Random Fit. Расширение для First Fit и Random Fit было предложено в работах и "Относительная потеря пропускной способности". "Наиболее используемые" значительно превосходят "наименее используемые" и незначительно превосходят First Fit. Алгоритмы Min Product, Least Loaded, Max Sum и Relative Capacity Loss стремятся выбрать длину волны, которая минимизирует вероятность блокировки будущих запросов. Существенным недостатком этих алгоритмов является необходимость значительного объема коммуникаций, что делает их непрактичными для реализации в сетях с децентрализованной структурой.

Совместное маршрутизация и назначение длины волны

Альтернативный подход к выбору маршрута и длины волны по отдельности заключается в рассмотрении их совместно. Эти подходы, как правило, более теоретические и менее практичные. Поскольку это NP-полная задача, любое точное решение, скорее всего, будет невозможно. Методы аппроксимации обычно также не очень полезны, поскольку они требуют централизованного управления и, как правило, заранее определенных требований к трафику. Два совместных подхода – это формулировка ILP и метод Island Hopping. Приведенная выше формулировка ILP может быть решена с помощью традиционного решателя ILP. Обычно это делается путем временного ослабления целочисленных ограничений, оптимального решения задачи и преобразования вещественного решения в целочисленное. Можно добавлять дополнительные ограничения и повторять процесс неопределенно долго, используя метод ветвей и границ. В статье авторы сообщают об алгоритме, который можно использовать для эффективного и оптимального решения ограниченной задачи RWA. Авторы изучают ограниченную задачу маршрутизации и назначения спектра (RSA), которую можно свести к ограниченной задаче RWA, запросив один срез. Ограничение ограничивает длину пути. В статье авторы сообщают об обобщенном алгоритме Дейкстры, который можно использовать для эффективного и оптимального решения задач RWA, RSA и задач маршрутизации, модуляции и назначения спектра (RMSA) без ограничения длины пути.