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

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

Определение

Общая цель задачи RWA — максимизировать количество установленных соединений. Каждому запросу на соединение должен быть указан маршрут и длина волны. Длина волны должна быть постоянной на всем протяжении трассы, если не предполагается использование преобразователей длины волны. Два запроса на соединение могут использовать один и тот же оптический канал при условии, что используется другая длина волны.

Задача RWA может быть формально определена в целочисленной линейной программе (ILP). Приведенная здесь формулировка ILP взята из . ^[1]

Максимизировать:

C_{0}(\rho ,q)=\sum _{i=1}^{N_{sd}}m_{i}

при условии

m_{i}\geq 0,integer,i=1,2,...,N_{sd}

c_{ij}\in {0,1},i=1,2,...,P,j=1,2,...,W

C^{T}B\leq l_{W\times L}

m\leq 1_{W}C^{T}A

m_{i}\leq q_{i}\rho ,i=1,2,...,N_{sd}

$N_{sd}$ - количество пар источник-назначение, а $m_{i}$ — количество соединений, установленных для каждой пары источник-назначение. $L$ это количество ссылок и $W$ это количество длин волн. $P$ — это набор путей для маршрутизации соединений. $A:P\times N_{sd}$ это матрица, показывающая, какие пары источник-назначение активны, $B:P\times L$ это матрица, которая показывает, какие ссылки активны, и $C:P\times W$ — это матрица назначения маршрута и длины волны.

Обратите внимание, что приведенная выше формулировка предполагает, что потребности в трафике известны априори . Этот тип проблемы известен как установление статического светового пути (SLE). Приведенная выше формулировка также не учитывает качество сигнала.

Показано, что задача SLE RWA NP-полна . ^[2] Доказательство предполагает сведение к $n$ -задача о раскраске графа. Другими словами, решение проблемы SLE RWA так же сложно, как и нахождение хроматического числа общего графа. Учитывая, что динамический RWA более сложен, чем статический RWA, должно быть так, что динамический RWA также является NP-полным.

Другое NP-полное доказательство приведено в . ^[3] Это доказательство сводится к проблеме многотоварного потока .

Проблема RWA еще больше усложняется необходимостью учитывать качество сигнала. Многие из оптических нарушений являются нелинейными, поэтому стандартный алгоритм поиска кратчайшего пути не может использоваться для их оптимального решения, даже если мы знаем точное состояние сети. Обычно это небезопасное предположение, поэтому решения должны быть эффективными, используя только ограниченную сетевую информацию.

Методология

Учитывая сложность RWA, существует две общие методики решения проблемы:

Первый метод заключается в том, чтобы сначала решить часть маршрутизации, а затем назначить длину волны. Три типа выбора маршрута: маршрутизация по фиксированному пути, фиксированная альтернативная маршрутизация и адаптивная маршрутизация.
Второй подход заключается в совместном рассмотрении выбора маршрута и назначения длины волны.

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

Алгоритмы маршрутизации

Маршрутизация по фиксированному пути

Маршрутизация по фиксированному пути — это самый простой подход к поиску светового пути. Всегда используется один и тот же фиксированный маршрут для данной пары источника и пункта назначения. Обычно этот путь вычисляется заранее с использованием алгоритма кратчайшего пути, такого как алгоритм Дейкстры . Хотя этот подход очень прост, производительности обычно недостаточно. Если ресурсы по фиксированному пути используются, будущие запросы на подключение будут заблокированы, даже если могут существовать другие пути.

Алгоритм SP-1 (кратчайший путь, 1 зонд) является примером решения для маршрутизации по фиксированному пути. Этот алгоритм вычисляет кратчайший путь, используя количество оптических маршрутизаторов в качестве функции стоимости. Для установления соединения по кратчайшему пути используется один зонд. Время работы — это стоимость алгоритма Дейкстры: $O(m+n\log n)$ , где $m$ количество ребер и $n$ это количество маршрутизаторов. Время выполнения является константой, если используется заранее определенный путь.

В этом определении SP-1 используется количество переходов в качестве функции стоимости . Алгоритм SP-1 можно расширить, чтобы использовать различные функции стоимости, например количество EDFA.

Исправлена альтернативная маршрутизация

Фиксированная альтернативная маршрутизация является расширением маршрутизации с фиксированным путем. Вместо одного фиксированного маршрута для данной пары источника и пункта назначения сохраняется несколько маршрутов. Зонды могут отправляться последовательно или параллельно. Для каждого запроса на соединение исходный узел пытается найти соединение на каждом из путей. Если все пути не работают, соединение блокируется. Если доступно несколько путей, будет использоваться только один из них.

СП- $p$ (Кратчайший путь, $p$ Зонды, $p>1$ ) является примером фиксированной альтернативной маршрутизации. Этот алгоритм вычисляет $p$ кратчайшие пути с использованием количества оптических маршрутизаторов в качестве функции стоимости. Время работы по алгоритму Йена ^[4] является $O(pn(m+n\log n))$ где $m$ количество ребер, $n$ количество маршрутизаторов, а $p$ это количество путей. Время выполнения является постоянным фактором, если пути рассчитаны заранее.

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

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

Адаптивные алгоритмы делятся на две категории: традиционные и физически осведомленные. Традиционные адаптивные алгоритмы не учитывают качество сигнала, однако адаптивные алгоритмы с физическим учетом учитывают это.

Традиционный адаптивный RWA

Алгоритм лексикографической маршрутизации (LORA) был предложен в. ^[5] Основная идея LORA состоит в том, чтобы направлять запросы на подключение из перегруженных областей сети, увеличивая вероятность того, что запросы на подключение будут приняты. Это достигается путем установки стоимости каждой ссылки $cost(l)=\beta ^{usage(l)}$ где $\beta$ параметр, который можно динамически регулировать в зависимости от транспортной нагрузки и $usage(l)$ количество длин волн, используемых в канале связи $l$ . Затем для поиска пути можно использовать стандартный алгоритм кратчайшего пути. Для этого каждый оптический коммутатор должен периодически передавать информацию о недавнем использовании. Обратите внимание, что LORA не учитывает какие-либо физические нарушения.

Когда $\beta$ равен единице, алгоритм LORA идентичен алгоритму SP. Увеличение стоимости $\beta$ увеличит перекос в сторону менее используемых маршрутов. Оптимальное значение $\beta$ можно рассчитать с помощью известного алгоритма восхождения на холм . Оптимальные значения $\beta$ в предложении были между 1,1 и 1,2.

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

Физически осознанный алгоритм обратного резервирования (PABR) является расширением LORA. PABR способен улучшить производительность двумя способами: с учетом физических недостатков и улучшенным выбором длины волны. Поскольку PABR ищет оптический путь, пути с неприемлемым качеством сигнала из-за линейных искажений отсекаются. Другими словами, PABR — это LORA с дополнительным ограничением качества.

Обратите внимание, что PABR может учитывать только линейные нарушения. С другой стороны, нелинейные нарушения невозможно оценить в распределенной среде из-за необходимости знания глобального трафика.

PABR также учитывает качество сигнала при выборе длины волны. Это достигается за счет исключения из рассмотрения всех длин волн с неприемлемым уровнем качества сигнала. Этот подход называется «Quality First Fit» и обсуждается в следующем разделе.

И LORA, и PABR могут быть реализованы как с однозондовым, так и с многоканальным зондированием. Максимальное количество зондов $p$ обозначается как ЛОРА- $p$ или ПАБР- $p$ . При одиночном зондировании при выборе маршрута выбирается только один путь. При множественном зондировании несколько путей пробуются параллельно, что увеличивает вероятность успешного соединения.

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

IA-BF — алгоритм наилучшего соответствия с учетом нарушений (IA-BF) был предложен в . ^[6] Этот алгоритм представляет собой распределенный подход, который зависит от большого объема коммуникаций и использует глобальную информацию, чтобы всегда выбирать кратчайший доступный путь и длину волны. Это достигается за счет использования последовательного многократного зондирования. Сначала предпринимается попытка использовать кратчайший доступный путь и длину волны, а в случае неудачи - второй кратчайший доступный путь и длину волны. Этот процесс продолжается до тех пор, пока не будут найдены успешный путь и длина волны или пока не будут испробованы все длины волн.

Многозондовый подход позволит IA-BF превзойти как PABR-1, так и LORA-1. Однако по мере увеличения количества зондов производительность алгоритмов становится одинаковой.

IA-FF – First Fit с учетом нарушений (IA-FF) – это простое расширение IA-BF. Вместо того, чтобы выбирать длины волн с точки зрения минимальной стоимости, длины волн выбираются в порядке их индекса. IA-BF имеет тенденцию превосходить IA-FF в большинстве сценариев.

AQoS — Адаптивное качество обслуживания (AQoS) было предложено в. ^[7] Этот алгоритм уникален во многих отношениях. Во-первых, каждый узел поддерживает два счетчика: $N_{BER}$ и $N_{wave}$ . Цель каждого счетчика — определить, какая проблема является более важным фактором при блокировке: доступность канала и длины волны или требования к качеству. Алгоритм выбирает маршруты по-разному в зависимости от более крупной проблемы.

Еще одно отличие состоит в том, что AQoS использует Q-фактор в качестве стоимости канала. Стоимость $i_{th}$ ссылка рассчитывается по этой формуле $D_{i}={\frac {\sum _{j=1}^{N_{i}}10\log[Q_{i,j}^{(s)}/Q_{i,j}^{(d)}]}{N_{i}}}$ где $N_{i}$ количество световых путей на $i_{th}$ связь, $Q_{i,j}^{(s)}$ и $Q_{i,j}^{(d)}$ являются измерениями добротности $j_{th}$ световой путь в узлах источника и назначения $i_{th}$ ссылку соответственно. Повторные оценки коэффициента качества требуют очень больших вычислительных затрат.

Этот алгоритм представляет собой метод одиночного зондирования. Подход с множественным зондированием, который в статье назван ALT-AQoS (альтернативный AQoS), представляет собой простое расширение той же базовой идеи.

Назначение длины волны

Двумя наиболее распространенными методами назначения длины волны являются «первая подгонка» и «случайная подгонка». First Fit выбирает доступную длину волны с наименьшим индексом. Функция Random Fit определяет доступные длины волн, а затем случайным образом выбирает среди них. Сложность обоих алгоритмов $O(w)$ , где $w$ это количество длин волн. First Fit превосходит Random Fit.

Расширение методов первой подгонки и случайной подгонки было предложено в ^[5] учитывать качество сигнала. Quality First Fit и Quality Random Fit исключают из рассмотрения длины волн, которые имеют неприемлемое качество сигнала. Однако сложность этих алгоритмов выше, так как до $w$ требуются вызовы для оценки Q-фактора.

Существует несколько других алгоритмов назначения длин волн: «Наименее используемый», «Наиболее используемый», «Минимальный продукт», «Наименее загруженный», «Максимальная сумма», ^[8] и относительная потеря мощности. ^[9] Наиболее часто используемые показатели значительно превосходят наименее используемые и немного превосходят показатели первой подгонки. «Минимальный продукт», «Наименее загруженная», «Максимальная сумма» и «Относительная потеря мощности» — все они пытаются выбрать длину волны, которая минимизирует вероятность того, что будущие запросы будут заблокированы.

Существенным недостатком этих алгоритмов является то, что они требуют значительных затрат на связь, что делает их непрактичным для реализации, если у вас нет централизованной сетевой структуры.

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

Альтернативный подход к выбору маршрута и длины волны по отдельности — рассматривать их совместно. Эти подходы, как правило, носят скорее теоретический, а не практический характер. Поскольку это NP-полная задача, точное решение, скорее всего, невозможно. Методы аппроксимации обычно также не очень полезны, поскольку требуют централизованного управления и, как правило, заранее определенных требований к трафику. Двумя совместными подходами являются формулирование ПДОДИ и переход между островами .

Перечисленную выше формулировку ILP можно решить с помощью традиционного решателя ILP. Обычно это делается путем временного ослабления целочисленных ограничений, оптимального решения задачи и преобразования реального решения в целочисленное. Могут быть добавлены дополнительные ограничения, и процесс повторяется бесконечно, используя подход ветвей и границ .

В ^[10] авторы сообщают об алгоритме, который можно использовать для эффективного и оптимального решения проблемы RWA с ограничениями. Авторы изучают проблему ограниченной маршрутизации и распределения спектра (RSA), которую можно свести к проблеме ограниченного RWA, запросив один срез. Сужение ограничивает длину пути.

В ^[11] авторы сообщают об обобщенном алгоритме Дейкстры, который можно использовать для эффективного и оптимального решения задач RWA, RSA, а также проблем маршрутизации, модуляции и распределения спектра (RMSA) без ограничения длины пути.

Ссылки

^ Х. Занг, Дж. Джу и Б. Мукерджи, « Обзор подходов к маршрутизации и назначению длины волны для оптических сетей WDM с маршрутизацией по длине волны », {\it Журнал Optical Networks}, январь 2000 г.
^ И. Кламтак, А. Ганц и Г. Карми, «Связь по световому пути: подход к оптическим глобальным сетям с высокой пропускной способностью», {\it IEEE Transactions on Communications}, Том 40, № 7, стр. 1171-1182, июль 1992 г. .
^ С. Эван, А. Итай и А. Шамир, «О сложности расписания и проблем многотоварных потоков», SIAM Journal on Computing, том 5, стр. 691-703, 1976.
^ М. Паскоаль и Э. Мартинс. « Новая реализация алгоритма ранжирования беспетлевых путей Йена ». 4OR – Ежеквартальный журнал бельгийских, французских и итальянских обществ исследования операций, 2003 г.
^ Jump up to: ^а ^б В. Лин, «Физически осведомленные гибкие оптические сети», доктор философии. Диссертация, Государственный университет Монтаны, Бозман, июль 2008 г.
^ Ю. Хуанг, Дж. Херитэдж и Б. Мукерджи, « Обеспечение соединения с учетом ухудшения передачи в оптических сетях WDM с высокоскоростными каналами », Журнал Lightwave Technology, Том 23, № 3, март 2005 г.
^ Т. Денг и С. Субраманиам, «Адаптивная маршрутизация QoS в оптических сетях с динамической маршрутизацией по длине волны», Broadband Networks 2005, стр. 184–193, 2005 г.
^ Р. Барри и С. Субраманиам, «Алгоритм назначения длины волны MAX-SUM для кольцевых сетей WDM», Материалы конференции по оптическому волокну, февраль 1997 г.
^ X. Чжан и К. Цяо, « Назначение длины волны для динамического трафика в многоволоконных сетях WDM », Труды Международной конференции по коммуникациям , Том 1, стр. 406-410, июнь 1997 г.
^ Иренеуш Щесняк и Божена Возна-Щесняк, « Адаптированный и ограниченный Дейкстра для эластичных оптических сетей », Материалы 20-й конференции по проектированию и моделированию оптических сетей, Картахена, Испания, май 2016 г.
^ Иренеуш Щесняк, Анджей Яйщик и Божена Возна-Щесняк, « Общий Дейкстра для оптических сетей », октябрь 2018 г.

[1] Х. Занг, Дж. Джу и Б. Мукерджи, « Обзор подходов к маршрутизации и назначению длины волны для оптических сетей WDM с маршрутизацией по длине волны », {\it Журнал Optical Networks}, январь 2000 г.

[2] И. Кламтак, А. Ганц и Г. Карми, «Связь по световому пути: подход к оптическим глобальным сетям с высокой пропускной способностью», {\it IEEE Transactions on Communications}, Том 40, № 7, стр. 1171-1182, июль 1992 г. .

[3] С. Эван, А. Итай и А. Шамир, «О сложности расписания и проблем многотоварных потоков», SIAM Journal on Computing, том 5, стр. 691-703, 1976.

[4] М. Паскоаль и Э. Мартинс. « Новая реализация алгоритма ранжирования беспетлевых путей Йена ». 4OR – Ежеквартальный журнал бельгийских, французских и итальянских обществ исследования операций, 2003 г.

[W._Lin_2008-5] Jump up to: ^а ^б В. Лин, «Физически осведомленные гибкие оптические сети», доктор философии. Диссертация, Государственный университет Монтаны, Бозман, июль 2008 г.

[6] Ю. Хуанг, Дж. Херитэдж и Б. Мукерджи, « Обеспечение соединения с учетом ухудшения передачи в оптических сетях WDM с высокоскоростными каналами », Журнал Lightwave Technology, Том 23, № 3, март 2005 г.

[7] Т. Денг и С. Субраманиам, «Адаптивная маршрутизация QoS в оптических сетях с динамической маршрутизацией по длине волны», Broadband Networks 2005, стр. 184–193, 2005 г.

[8] Р. Барри и С. Субраманиам, «Алгоритм назначения длины волны MAX-SUM для кольцевых сетей WDM», Материалы конференции по оптическому волокну, февраль 1997 г.

[9] X. Чжан и К. Цяо, « Назначение длины волны для динамического трафика в многоволоконных сетях WDM », Труды Международной конференции по коммуникациям , Том 1, стр. 406-410, июнь 1997 г.

[10] Иренеуш Щесняк и Божена Возна-Щесняк, « Адаптированный и ограниченный Дейкстра для эластичных оптических сетей », Материалы 20-й конференции по проектированию и моделированию оптических сетей, Картахена, Испания, май 2016 г.

[11] Иренеуш Щесняк, Анджей Яйщик и Божена Возна-Щесняк, « Общий Дейкстра для оптических сетей », октябрь 2018 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]