МЕТОД РЕШЕНИЯ ЗАДАЧИ ДИНАМИЧЕСКОГО ВЫБОРА МАРШРУТОВ И НАЗНАЧЕНИЯ ДЛИН ВОЛН В СЕТЯХ WDM С УЧЕТОМ ЯВЛЕНИЯ ЧЕТЫРЕХВОЛНОВОГО СМЕШИВАНИЯ
Д.В. Агеев, А.А. Переверзев
УДК 621.391
МЕТОД РЕШЕНИЯ ЗАДАЧИ ДИНАМИЧЕСКОГО ВЫБОРА МАРШРУТОВ И НАЗНАЧЕНИЯ ДЛИН ВОЛН В СЕТЯХ WDM С УЧЕТОМ ЯВЛЕНИЯ ЧЕТЫРЕХВОЛНОВОГО СМЕШИВАНИЯ
Д.В. Агеев, А.А. Переверзев
Решается задача динамического выбора маршрутов и назначения длин волн в сетях WDM. Задача является актуальной для управления сетью WDM при обслуживании запросов на установку кратковременных соединений и передачу избыточного трафика. Предлагаемый метод решения задачи является эвристическим и усовершенствует ранее известный метод за счет учета влияния четырехволнового смешивания и использования новой метрики на этапе поиска потенциальных для использования маршрутов. Это позволило уменьшить вероятность блокировки вызовов при установке соединений в среднем на 13% и значение Q-фактора на 0,812. Ключевые слова: маршрут, RWA, световой путь, проектирование, четырехволновое смешивание, вероятность блокировки.
Введение
Постоянно растущая потребность в увеличении пропускной способности современных телекоммуникационных систем при развертывании транспортных сетей приводит к необходимости использования технологии спектрального уплотнения каналов (Wavelength-division multiplexing, WDM). Передача информации в WDM-сетях производится вдоль световых путей. Под световым путем будем понимать последовательность оптических каналов, которые используются для передачи потока от источника к получателю с использованием одной и той же длины волны. Указанное ограничение на использование одной длины волны вдоль всего пути может привести к уменьшению количества установленных соединений и неэффективному использованию имеющихся длин волн. Таким образом, задача выбора маршрутов и назначения длин волн в WDM-сетях является важной [1].
Рассмотрим задачу: необходимо выбрать маршрут между парой источник–получатель и назначить ему длину волны таким образом, чтобы обеспечить максимум количества устанавливаемых соединений. Эта задача известна как маршрутизация и распределение длин волн (Routing and Wavelength Assignment, RWA) [2–4]. В зависимости от периодичности решения задачи RWA можно выделить статическое и динамическое распределение.
Задача статического распределения решается в основном на этапе проектирования телекоммуникационной сети, а наиболее часто используемыми критериями оптимальности являются максимум количества установленных соединений или минимум вероятности блокировки.
Задача динамического распределения возникает при управлении потоками в телекоммуникационной сети. Важным фактором при выборе метода решения является его вычислительная сложность и близость получаемого результата к оптимальному.
При построении WDM-сетей возникает нелинейное явление четырехволнового смешивания (ЧВС), что повышает уровень битовых ошибок (Bit Error Rate, BER). Таким образом, при выборе маршрутов для установки соединения необходимо учитывать явление ЧВС.
Одним из перспективных направлений развития современных сетей доступа является совместное использование беспроводных и оптических технологий. Преимущество таких сетей заключается в возможности использования лучших черт обеих технологий. Для беспроводных технологий – это мобильность, высокая скорость развертывания. Оптические технологии позволяют обойти такие недостатки беспроводных сетей, как ограниченность частотного ресурса, проблемы электромагнитной совместимости и другие явления, связанные с особенностями распространения радиоволн.
Использование оптических сетей в качестве транспортной среды позволяет обеспечить передачу радиосигналов между базовыми станциями непосредственно на высокой частоте. Данная технология известна в международной литературе как RoF (Radio over Fiber) [5, 6]. При больших размерностях сетей доступа на основе технологии RoF (более сотни базовых станций) возникает явление всплесков трафика на небольшом промежутке времени. Это связано с увеличением количества ресурсов, запрашиваемых мобильными абонентами в некоторых сотах. В связи с этим возникает необходимость в использовании новых или перераспределении уже выделенных частотных ресурсов. Эта задача получила название MSCA (maximal service channel allocation) [7]. При ее решении производится распределение имеющихся свободных ресурсов сети WDM на непродолжительный промежуток времени, что требует решения задачи динамического выбора маршрутов и назначения длин волн (Dynamic Routing and Wavelength Assignment, DRWA).
Для решения задачи DRWA используются эвристические методы решения, которые базируются на фиксированной, фиксированной альтернативной и адаптивной маршрутизациях.
При использовании фиксированной маршрутизации для установки соединения между заданной парой источник–получатель используется заранее определенный маршрут. Как правило, этот маршрут является кратчайшим путем. Достоинством такого подхода является отсутствие потребности в сборе ин-
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
29
МЕТОД РЕШЕНИЯ ЗАДАЧИ ДИНАМИЧЕСКОГО ВЫБОРА МАРШРУТОВ...
формации о состоянии сети. К его недостаткам можно отнести то, что при невозможности установки соединения по фиксированному маршруту запрос на установку соединения блокируется.
В случае фиксированной альтернативной маршрутизации для установки соединения используется список фиксированных кратчайших маршрутов. Вначале алгоритм производит установку соединения по первому маршруту в списке, если на маршруте нет свободных длин волн, то установка соединения происходит по следующему маршруту в списке. Недостаток такого подхода аналогичен предыдущему: если во всех маршрутах, содержащихся в списке, отсутствуют свободные длины волн, то запрос блокируется.
Адаптивная маршрутизация находит маршрут для заданного запроса установки соединения динамически, однако для этого необходимы мониторинг и учет текущего состояния сети. Преимуществом данного подхода является гибкость и низкий уровень вероятности блокировки по сравнению с методами, которые приведены выше. Таким образом, наиболее целесообразным является использование адаптивной маршрутизации [8].
Изложенный в работах [9, 10] метод адаптивной маршрутизации наименее загруженного маршрута (Least Load Routing, LLR) является одним из представителей распределенной модели управления. Основной идеей LLR является выбор маршрута, который включает в себя наибольшее количество свободных длин волн.
Метод адаптивной маршрутизации фиксированного наименее загруженного маршрута (Fixed Paths Least Congestion routing, FPLC) базируется на выборе фиксированного маршрута с наименьшим количеством задействованных вдоль него длин волн [11]. Результаты показали, что FPLC-алгоритм может значительно улучшить производительность по сравнению с другими фиксированными альтернативными алгоритмами маршрутизации. Однако, если в телекоммуникационной сети находится оптический конвектор, методы LLR и FPLC работают неэффективно, потому что при выборе маршрута они учитывают только распределение свободных длин волн, а длина маршрута не учитывается.
В основе метода, который базируется на расчете весовой функции и выборе наименее загруженного маршрута (Weighted Least-Congestion Routing First-Fit, WLCR-FF) [12], лежит выбор маршрута с наибольшим весом, рассчитываемым как
W (R) F(R) , h(R)
где W (R) – взвешенный коэффициент для маршрута R ; F(R) – количество свободных длин волн на R -
ом маршруте; h(R) – количество узлов на маршруте R . Данный метод учитывает не только пропускную
способность маршрутов, но и их длину. Большинство известных методов адаптивной маршрутизации выбирает маршруты из заранее за-
данного множества. Как правило, альтернативные пути для каждой пары источник–получатель, которые включены в это множество, являются реберно-непересекающимися кратчайшими путями [13]. При установке соединения маршрут передачи выбирается из заданного множества, базируясь на значении весовой функции для этого пути. При отсутствии свободных длин волн вдоль заранее заданных путей алгоритм пытается найти новый путь, содержащий свободные длины волн, и если такой путь найти не удается, то вызов блокируется.
Одним из представителей описанного выше класса методов адаптивной маршрутизации, который характеризуется достаточно высокой производительностью и высокой степенью близости получаемого решения к оптимальному, является метод динамической маршрутизации длин волн (Dynamic Wavelength Routing, DWR) [14]. Метод DWR предусматривает применение на первом этапе алгоритма выбора путей, базирующегося на использовании наименее загруженного пути с наименьшей степенью узлов (Least Congestion with Least Nodal-degree Routing algorithm, LCLNR) и алгоритма динамической маршрутизации длин волн с двух концов (Dynamic two-end wavelength routing algorithm, DTWR). Алгоритм маршрутизации с двух концов требует больших затрат времени. Кроме того, при расчете весов маршрутов не учитывается явление четырехволнового смешивания, что приводит к установке соединений, не удовлетворяющих требованиям по допустимой вероятности битовой ошибки.
Для устранения указанных недостатков требуется проведение дополнительных исследований, разработка новых и модернизация существующих методов решения задачи динамического выбора маршрутов и назначения длин волн в сетях WDM. Таким образом, целью данной работы является снижение вероятности блокировки вызовов при установке соединений и уменьшении вероятности битовой ошибки (BER) вследствие увеличения значения Q-фактора.
Математическая постановка задачи распределения длин волн в транспортной сети WDM
При решении задачи маршрутизации топологию сети будем описывать связным графом G(N, L) ,
где N ni – множество узлов сети; L {lgu } – множество каналов связи оптической сети, где
lgu (ng , nu ) . Математическая постановка задачи приведена ниже.
30 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)
Д.В. Агеев, А.А. Переверзев
Пусть ns – узел источника при передаче трафика; nd – узел получателя при передаче трафика;
N s – соседние узлы узла источника; Nd – соседние узлы узла получателя; W – множество длин волн,
использование которых допустимо в рамках используемой технологии оптической сети;
K sd
{K
i sd
}
–
множество маршрутов между узлами ns и nd .
Введем следующие обозначения: hsid
K
i sd
–1 – количество узлов на i-ом маршруте от ns
к nd ;
Wsid – множество свободных длин волн на i-ом маршруте; isd – количество свободных длин волн на
маршруте
K
i sd
,
где
isd Wsid
;
xi sd
– установка соединения с использованием
-ой длины волны по
маршруту
K
i sd
;
gu
– количество свободных длин волн в
lgu -оптическом канале связи; Wgu
– множест-
во свободных длин волн в lgu -оптическом канале связи; deg(ni ) – степень вершины ni в графе
G(N, L) ;
isd
– количество длин волн, доступных для использования вдоль маршрута
K
i sd
;
sd Ksd
–
выбранный маршрут при установке соединения между парой ns , nd ; O(sd ) – функция, определяющая
целесообразность выбора маршрута sd . Решение задачи сводится к необходимости найти:
sd – маршрут передачи оптического сигнала между узлами ns , nd ;
sd – длину волны, используемую вдоль маршрута sd . Критерий оптимальности – минимум вероятности блокировки:
Ksd
K
i sd
Z Blocking
iK
K sd
min .
Метод DWR базируется на использовании двух алгоритмов – LCLNR и DTWR. Суть алгоритма LCLNR заключается в том, что при выборе светового пути между узлами выбирается наименее загруженный световой путь, тем самым уменьшая вероятность блокировки. Список kкратчайших путей для каждой пары (s, d) вычисляется с помощью модифицированного алгоритма Дейкстры [15]. Выбор маршрута из списка k-кратчайших путей осуществляется на основе коэффициента целесообразности, вычисляемого как
O(sd
)
w h
.
Данное выражение учитывает пропускную способность маршрута и количество узлов, через которые проходит маршрут. После этого будет выбран маршрут с максимальным значением коэффициента целесообразности. Если существует несколько маршрутов, то будет выбран маршрут с минимальной суммой степеней узлов вдоль маршрута,
nd
min deg(ni ) . i ns
Если после выполнения данного условия число маршрутов более 1, то маршрут будет выбран случайным образом. Псевдокод алгоритма LCLNR приведен ниже:
Входные данные: граф сети G(N, L) и множество предоопределенных K кратчайших
маршрутов,
Ksid , i [1, k ]
для соединений
е {s, d}
и
sd
K
i sd
,i
[1, k ]
Вычисление функции O(Ksid )
O(Ksid ) wi / hi ,i [1, K ]
if
O
(
K
i sd
)
0, i
[1,
K
]
then
блокировка
вызова
на
установку
соединения;
return;
else end if
sd
maxi{1..k}
O(
K
i sd
),
sd
Temp;
if Temp 2 , then вычисляется sd min p[1,P]
deg(ni ), P Ksd .
ni PTemp j
if P 2 then маршрут выбирается случайным образом из множества Temp
end if end if
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
31
МЕТОД РЕШЕНИЯ ЗАДАЧИ ДИНАМИЧЕСКОГО ВЫБОРА МАРШРУТОВ...
Далее происходит установка соединения по выбранному маршруту и назначается длина волны
xi sd
с помощью использования метода first-fit [3].
Если не удается установить соединение с помощью алгоритма LCLNR, то применяется алгоритм
DTWR. Алгоритм DTWR рассматривает три сценария.
Сценарий А. Отсутствуют свободные длины волн в оптических каналах связи от узлов источников и
соседних узлов.
Сценарий В. Есть некоторое количество свободных длин волн в оптических каналах связи от узлов
источников и соседних узлов.
Сценарий С. Есть свободные длины волн между узлами источниками смежными, но отсутствуют
свободные длины волн на промежуточных узлах на световом маршруте.
Алгоритм DTWR работает только при сценариях В и С. Первый шаг алгоритма DTWR – опреде-
ление сценария. Если сценарий – не А, то выполняется удаление ребер из графа, которые не содержат
свободных длин волн. После этого выполняется поиск кратчайшего маршрута с помощью алгоритма
Дейкстры. На последнем шаге происходит передача этого маршрута на рассмотрение алгоритму LCLNR.
Псевдокод алгоритма DTWR приведен ниже.
while sd ;
do вычислить nsnv , nd nc , Wnsnv и Wnd nc
if (Wnsnv 0 ) или (Wndnc 0 ) then вызов блокируется; return;
else if
i,
ni
Wsi
N s
i,
ni
Wid
N d
then
вызов на запрос установки соединения блокируется; return;
else удаляются ребра с графа G(N , L) , где nsnv nd nc 0 ; генерируется
граф G(N , L)
end if
Вычисляется множество путей
K i ns nd
с помощью алгоритма Дейкстры;
if
K i ns nd
return;
then
K
i sd
,
вызов
на
установку
соединения
блокируется
else
K
i sd
K i ns nd
,
переход
к
алгоритму
LCLNR
end if
end while.
При исследовании метода решения задачи DRWA были обнаружены следующие недостатки:
при использовании алгоритма DTWR возникают большие временные затраты на этапе проверки условий сценариев. Этот фактор является критичным при решении задачи DRWA;
алгоритмом LNCLR при выборе светового маршрута не учитывается такое нелинейное искажение в волоконно-оптических сетях, как четырехволновое смешивание (ЧВС);
метод назначения длин волн first-fit неэффективен при наличии ЧВС [16].
Разработка метода устранения приведенных недостатков
Последствием ЧВС является появление побочных сигналов, в том числе на длинах волн, соответствующих другим рабочим каналам, что может привести к росту ошибок и ухудшению эффективности системы WDM. Для учета влияния данного явления при выборе маршрута была использована [17] следующая формула расчета мощности помехи ЧВС:
Pijk
(
fi ,
fj,
fk
)
9
D22 Pi Pj Pk eL
(1 eL )2
2
,
где Pi , Pj , Pk – мощности входных канальных сигналов на частотах fi , f j , fk соответственно; D ко-
эффициент вырожденности; коэффициент затухания оптического волокна; L длина отрезка оптического волокна.
Коэффициент нелинейности на длине волны рассчитывается по формуле
γ
2 πn2 λ Aэфф
,
где n2 коэффициент нелинейности показателя преломления; Aэфф эффективная площадь оптического волокна.
32 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)
Д.В. Агеев, А.А. Переверзев
Эффективность ЧВС описывается следующим выражением:
2
2 2
1
4eL
sin
2
L 2
(1 eL )
.
Коэффициент фазового согласования зависит от хроматической дисперсии Dc () и описывается следующим выражением:
2
2 k
c
fik f jk
Dc
(
)
2 k
2c
(fik
f jk )
d
Dc ( d
)
,
где интервал между каналами fik | fi fk | , f jk | f j fk | ; c скорость света.
Мощность помехи ЧВС на частоте fm равна сумме мощностей всех комбинационных продуктов:
NN
PЧВС ( fm )
Pijk ( fi, f j , fk ) ,
i 1 j 1
где N – количество каналов.
Проведем расчет мощности усиленного спонтанного излучения (ASE) с помощью выражения Pase 2nsp (G 1)hfm f0 ,
где nsp – коэффициент спонтанной эмиссии усилителя; h – постоянная Планка; f0 – ширина полосы
пропускания оптического фильтра демультиплексора WDM; G – коэффициент усиления усилителя. Допустим, что все участки имеют одинаковую длину, следовательно, мощность усиленного спон-
танного излучения на входе приемного оптического модуля (ПрОМ) равна сумме соответствующих мощностей на выходе всех усилителей:
Pase Pase (Nус 1) ,
где N ус – количество усилителей. Тогда мощность ЧВС на входе ПрОМ равна
PЧВС PЧВС G( N ус 1) .
На выходе фотоприемника оптический шум ЧВС и ASE соответственно формируют электриче-
ский сигнал с мощностями
PeЧВС
2z 2 Pвх
P ЧВС
8
,
P ease
4z 2 Pвх
P ease
fe f0
,
где fe – полоса пропускания электрического усилителя ПрОМ.
Чувствительность фотоприемника равна
z
e hfm
,
где – квантовая эффективность фотодетектора; e – заряд электрона.
Q-фактор и связанная с ним вероятность ошибки рассчитываются по формулам
Q
Pвх Pease PeЧВС
,
(1)
Pош
1
e
x2 2
dx
.
2π Q
где PeЧВС
– суммарная мощность ЧВС,
Pвх
– входная мощность;
P ease
– суммарная мощность ASE.
Полученное выражение (1) используется при расчете целевой функции на этапе выбора светового мар-
шрута алгоритмом LCLNR следующим образом:
O(sd
)
w
FMP(R) h
,
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
33
МЕТОД РЕШЕНИЯ ЗАДАЧИ ДИНАМИЧЕСКОГО ВЫБОРА МАРШРУТОВ...
где FMP(R) – коэффициент, который уменьшает значение O(sd ) , если вероятность ошибки для мар-
шрута R превысила допустимое значение. На этапе расчета коэффициента целесообразности выбора маршрута для установки соединения
происходит сравнение рассчитанного значения Q-фактора на каждом оптическом канале, через который проходит рассматриваемый маршрут, с допустимым значением Q-фактора. Если значение Q-фактора превышает допустимую норму, то значение целевой функции уменьшается.
Как показали исследования, использование алгоритма DTWR приводит к большим временным за-
тратам, поэтому в работе предлагается вместо него использовать алгоритм Дейкстры для поиска крат-
чайшего маршрута между заданной парой источник–получатель с использованием следующей метрики:
ln(
P(
K
i sd
))
ln(1
wsn W
)
...
ln m
(1
wkd W
)
,
где wsn – количество занятых длин волн в оптическом канале между узлами s и n. Данная метрика
характеризует вероятность успешной установки соединения, так как величина
P
K
i sd
пропорциональна
вероятности не блокирования маршрута.
Методика исследования эффективности предложенных методов базируется на имитационном
моделировании. На вход имитационной модели поступал простейший поток заявок на установку
соединения по световому пути. В дальнейшем производился выбор маршрута и назначение ему длины
волны. В случае успешной установки соединения в модели соответствующие ресурсы помечались как
занятые. В имитационной модели также моделировалась длительность соединения, после которого
занятые соединением сетевые ресурсы освобождались. При проведении эксперимента использовалась
топология оптической сети с 20 узлами, ранг каждого узла в сети – не меньше 3. Эксперимент проводил-
ся при различных интенсивностях поступления запросов на установку соединения, интервалы поступле-
ния запросов и время удержания ресурсов являлись случайными величинами, распределенными по
экспоненциальному закону. Величина загруженности сети изменялась в пределах (0,2–0,9).
Для назначения длин волн световому маршруту в предложенном методе использовался метод
random, а в базовом – first-fit. В результате проведения эксперимента были получены следующие резуль-
таты, показанные на рис. 1.
100
Вероятность блокировки
80 60 40
20
0
0,4
0,6 0,8
1
1,2 1,4 1,6 1,8 2
Интенсивность трафика, с–1
Базовый
Модифицированный
Рис. 1. Зависимость вероятности блокировки от интенсивности трафика для базового и модифицированного методов алгоритмов
В ходе анализа полученных результатов (рис. 1) установлено, что наибольший выигрыш вероятности блокировки (19%) соответствует интенсивности трафика 1,5. При интенсивности трафика 1 вероятность блокировки снижается на 14%, при 0,8 – на 8%. В эксперименте с интенсивностью трафика 0,4 из-за низкой вероятности блокировки не было зафиксировано ни одного заблокированного вызова.
На рис. 2 показаны значения Q-фактора базового и модифицированного методов при различных интенсивностях поступления запросов на установку соединения.
Анализируя полученные результаты, можно увидеть, что выигрыш Q-фактора растет с уменьшением интенсивности поступления запросов на установку соединения.
34 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)
Д.В. Агеев, А.А. Переверзев
6 5,5 5
Q-фактор
4,5
4
3,5 0,4
0,6 0,8
1
1,2 1,4 1,6 1,8 2
Интенсивность трафика, с–1
Базовый
Модифицированный
Рис. 2. Зависимость значений Q-фактора от интенсивности трафика для базового и модифицированного методов алгоритмов
При совместном анализе рисунков 1, 2 можно сделать вывод, что предложенные изменения в методе адаптивной маршрутизации по сравнению с базовым методом позволяют снизить вероятность блокировки и вероятность битовых ошибок (которая является функцией Q-фактора) и требуют меньшего числа вычислительных итераций. Наибольший выигрыш по уменьшению вероятности блокировки имеет место при средней интенсивности поступления вызовов. В случае низкой интенсивности трафика быстрее освобождаются ресурсы сети, и необходимость использования алгоритма DTWR уменьшается. Наибольший выигрыш для Q-фактора, напротив, получается при низкой интенсивности поступления вызовов.
Заключение
В работе проведен анализ методов решения задачи динамической маршрутизации и назначения длин волн (DRWA). Показано, что наиболее эффективным является метод адаптивной маршрутизации, как обеспечивающий гибкость и низкий уровень вероятности блокировки. В работе был рассмотрен метод адаптивной маршрутизации на основе использования алгоритмов LCLNR и DTWR. Показано, что использование алгоритма DTWR приводит к большим временным затратам на стадии проверки условий сценария, что является критичным при решении задачи DRWA. Не учитываются нелинейные искажения в волоконно-оптических сетях, такие как ЧВС, при выборе светового маршрута с помощью алгоритма LNCLR. Метод назначения длин волн first-fit неэффективен в случае наличия в каналах нелинейных явлений.
Для устранения данных недостатков предложена модификация алгоритма: вместо использования алгоритма DTWR предложен алгоритм Дейкстры с использованием метрики, которая основывается на пропускной способности маршрутов; введены математические выражения для учета ЧВС при расчете вероятности выбора светового маршрута; использован метод random при назначении длин волн световым маршрутам вместо first-fit.
Проведен эксперимент с использованием средств имитационного моделирования на искусственно синтезируемой топологии сети. При моделировании решалась задача RWA при различных интенсивностях поступлений вызовов на установку соединения. В ходе анализа полученных результатов было выявлено, что модифицированный метод адаптивной маршрутизации имеет наибольшую эффективность при интенсивности в 1,5 единицы, при этом выигрыш составляет 19%, тогда как среднее значение выигрыша составляет 13%. Наибольшее значение Q-фактора наблюдалось при самой низкой интенсивности трафика (0,4), так как в этом случае задействовано наименьшее число длин волн в оптических каналах. Средний выигрыш Q-фактора составил 0,812.
Литература
1. Gangxiang S., Rodney S.T. Translucent Optical Networks: The Way Forward // IEEE Communications Magazine. – 2007. – V. 45. – P. 48–54.
2. Ramesh G., Sundaravadivelu S. Reliable Routing and Wavelength Assignment for Optical WDM Networks // European Journal of Scientific Research. – 2010. – V. 48. – № 1. – P. 85–96.
3. Leonardi E., Mellia M., Marsan M.A. Algorithms for the logical topology design in WDM all-optical networks // Optical Networks. – 2000. – V. 1. – P. 35–46.
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
35
ПРОГНОЗИРОВАНИЕ КАЧЕСТВА ИЗОБРАЖЕНИЙ КОСМИЧЕСКИХ ОБЪЕКТОВ...
4. Mokhtar A., Azizoglu M. Adaptive wavelength routing in all-optical networks // IEEE/ACM Transactions on Networking. – 1998. – V. 6. – № 2. – P. 197–206.
5. Jianjun Yu. Radio-over-optical-fiber networks: introduction to the feature issue // Journal of Optical Networking. – 2009. – V. 8 (5). – P. 481–488.
6. Gomes P.H., Fonseca da N.L.S., Branquinho O.C. Optimization of the use of Radio Resource of Radio-OverFiber Access Networks // Global Telecommunications Conference (GLOBECOM 2010). – 2010. – P. 1–5.
7. Mirosław Klinkowski, Marek Jaworski, Davide Careglio. Channel Allocation in Dense Wavelength Division Multiplexing Radio-over-Fiber Networks // 12th International Conference on Transparent Optical Networks. – 2010. – P. 1–5.
8. Zang H., Jue J. P., Mukherjee B. A review of routing and wavelength assignment approaches for wavelengthrouted optical networks // Optical Network Magazine. – 2000. – V. 1. – № 1. – P. 47–60.
9. Karasan E., Ayanoglu E. Effects of wavelength routing and selection algorithms on wavelength conversion gain in WDM optical networks // IEEE/ACM Transactions on Networking. – 1998. – V. 6. – № 2. – P. 186– 196.
10. Birman A. Computing Approximate Blocking Probabilities for a Class of All-Optical Networks // IEEE Journal on Selected Areas in Communications. – 1996. – V. 14. – № 5. – P. 852–857.
11. Li L., Somani A.K. Dynamic Wavelength Routing Using Congestion and Neighborhood Information // IEEE/ACM Transactions on networking. – 1999. – V. 7. – № 5. – P. 779–786.
12. Xiaowen Chu, Bo Li, Zhensheng Zhang. A Dynamic RWA Algorithm in a Wavelength-Routed All-Optical Network with Wavelength Converters // INFOCOM. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies. – 2003. – V. 3. – P. 1795–1804.
13. Yates J.M., Rumsewicz M.P. Wavelength converters in dynamically-reconfigurable WDM networks // IEEE Communications Surveys & Tutorials. – 1999. – V. 2. – № 2. – P. 2–15.
14. Kungmang Lo, Daryoush Habibi, Quoc Viet Phung, Hoang Nghia Nguyen. Dynamic Wavelength routing in all optical meshnetwork // Proceedings of Asia Pacific Conference on Communications. – 2005. – P. 178–182.
15. Bhandari R. Survivable Networks: Algorithms for Diverse Routing. – Kluwer Academic Publishers, 1999. – 200 p.
16. Агеев Д.В., Ковальчук В.К., Переверзев А.А. Планирование распределения длин волн при проектировании транспортной сети DWDM // Восточно-европейский журнал передовых технологий. – 2011. – № 5/3 (53). – С. 25–29.
17. Педяш В.В., Решетников О.С. Оптимізація потужності лінійного сигналу системи DWDM // Цифрові Технології. – 2009. – № 5. – C. 27–33.
Агеев Дмитрий Владимирович Переверзев Александр Анатольевич
– Харьковский национальный университет радиоэлектроники, доктор технических наук, профессор, dm@ageyev.in.ua
– Харьковский национальный университет радиоэлектроники, аспирант, pereverzev_aa@mail.ru
36 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)
УДК 621.391
МЕТОД РЕШЕНИЯ ЗАДАЧИ ДИНАМИЧЕСКОГО ВЫБОРА МАРШРУТОВ И НАЗНАЧЕНИЯ ДЛИН ВОЛН В СЕТЯХ WDM С УЧЕТОМ ЯВЛЕНИЯ ЧЕТЫРЕХВОЛНОВОГО СМЕШИВАНИЯ
Д.В. Агеев, А.А. Переверзев
Решается задача динамического выбора маршрутов и назначения длин волн в сетях WDM. Задача является актуальной для управления сетью WDM при обслуживании запросов на установку кратковременных соединений и передачу избыточного трафика. Предлагаемый метод решения задачи является эвристическим и усовершенствует ранее известный метод за счет учета влияния четырехволнового смешивания и использования новой метрики на этапе поиска потенциальных для использования маршрутов. Это позволило уменьшить вероятность блокировки вызовов при установке соединений в среднем на 13% и значение Q-фактора на 0,812. Ключевые слова: маршрут, RWA, световой путь, проектирование, четырехволновое смешивание, вероятность блокировки.
Введение
Постоянно растущая потребность в увеличении пропускной способности современных телекоммуникационных систем при развертывании транспортных сетей приводит к необходимости использования технологии спектрального уплотнения каналов (Wavelength-division multiplexing, WDM). Передача информации в WDM-сетях производится вдоль световых путей. Под световым путем будем понимать последовательность оптических каналов, которые используются для передачи потока от источника к получателю с использованием одной и той же длины волны. Указанное ограничение на использование одной длины волны вдоль всего пути может привести к уменьшению количества установленных соединений и неэффективному использованию имеющихся длин волн. Таким образом, задача выбора маршрутов и назначения длин волн в WDM-сетях является важной [1].
Рассмотрим задачу: необходимо выбрать маршрут между парой источник–получатель и назначить ему длину волны таким образом, чтобы обеспечить максимум количества устанавливаемых соединений. Эта задача известна как маршрутизация и распределение длин волн (Routing and Wavelength Assignment, RWA) [2–4]. В зависимости от периодичности решения задачи RWA можно выделить статическое и динамическое распределение.
Задача статического распределения решается в основном на этапе проектирования телекоммуникационной сети, а наиболее часто используемыми критериями оптимальности являются максимум количества установленных соединений или минимум вероятности блокировки.
Задача динамического распределения возникает при управлении потоками в телекоммуникационной сети. Важным фактором при выборе метода решения является его вычислительная сложность и близость получаемого результата к оптимальному.
При построении WDM-сетей возникает нелинейное явление четырехволнового смешивания (ЧВС), что повышает уровень битовых ошибок (Bit Error Rate, BER). Таким образом, при выборе маршрутов для установки соединения необходимо учитывать явление ЧВС.
Одним из перспективных направлений развития современных сетей доступа является совместное использование беспроводных и оптических технологий. Преимущество таких сетей заключается в возможности использования лучших черт обеих технологий. Для беспроводных технологий – это мобильность, высокая скорость развертывания. Оптические технологии позволяют обойти такие недостатки беспроводных сетей, как ограниченность частотного ресурса, проблемы электромагнитной совместимости и другие явления, связанные с особенностями распространения радиоволн.
Использование оптических сетей в качестве транспортной среды позволяет обеспечить передачу радиосигналов между базовыми станциями непосредственно на высокой частоте. Данная технология известна в международной литературе как RoF (Radio over Fiber) [5, 6]. При больших размерностях сетей доступа на основе технологии RoF (более сотни базовых станций) возникает явление всплесков трафика на небольшом промежутке времени. Это связано с увеличением количества ресурсов, запрашиваемых мобильными абонентами в некоторых сотах. В связи с этим возникает необходимость в использовании новых или перераспределении уже выделенных частотных ресурсов. Эта задача получила название MSCA (maximal service channel allocation) [7]. При ее решении производится распределение имеющихся свободных ресурсов сети WDM на непродолжительный промежуток времени, что требует решения задачи динамического выбора маршрутов и назначения длин волн (Dynamic Routing and Wavelength Assignment, DRWA).
Для решения задачи DRWA используются эвристические методы решения, которые базируются на фиксированной, фиксированной альтернативной и адаптивной маршрутизациях.
При использовании фиксированной маршрутизации для установки соединения между заданной парой источник–получатель используется заранее определенный маршрут. Как правило, этот маршрут является кратчайшим путем. Достоинством такого подхода является отсутствие потребности в сборе ин-
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
29
МЕТОД РЕШЕНИЯ ЗАДАЧИ ДИНАМИЧЕСКОГО ВЫБОРА МАРШРУТОВ...
формации о состоянии сети. К его недостаткам можно отнести то, что при невозможности установки соединения по фиксированному маршруту запрос на установку соединения блокируется.
В случае фиксированной альтернативной маршрутизации для установки соединения используется список фиксированных кратчайших маршрутов. Вначале алгоритм производит установку соединения по первому маршруту в списке, если на маршруте нет свободных длин волн, то установка соединения происходит по следующему маршруту в списке. Недостаток такого подхода аналогичен предыдущему: если во всех маршрутах, содержащихся в списке, отсутствуют свободные длины волн, то запрос блокируется.
Адаптивная маршрутизация находит маршрут для заданного запроса установки соединения динамически, однако для этого необходимы мониторинг и учет текущего состояния сети. Преимуществом данного подхода является гибкость и низкий уровень вероятности блокировки по сравнению с методами, которые приведены выше. Таким образом, наиболее целесообразным является использование адаптивной маршрутизации [8].
Изложенный в работах [9, 10] метод адаптивной маршрутизации наименее загруженного маршрута (Least Load Routing, LLR) является одним из представителей распределенной модели управления. Основной идеей LLR является выбор маршрута, который включает в себя наибольшее количество свободных длин волн.
Метод адаптивной маршрутизации фиксированного наименее загруженного маршрута (Fixed Paths Least Congestion routing, FPLC) базируется на выборе фиксированного маршрута с наименьшим количеством задействованных вдоль него длин волн [11]. Результаты показали, что FPLC-алгоритм может значительно улучшить производительность по сравнению с другими фиксированными альтернативными алгоритмами маршрутизации. Однако, если в телекоммуникационной сети находится оптический конвектор, методы LLR и FPLC работают неэффективно, потому что при выборе маршрута они учитывают только распределение свободных длин волн, а длина маршрута не учитывается.
В основе метода, который базируется на расчете весовой функции и выборе наименее загруженного маршрута (Weighted Least-Congestion Routing First-Fit, WLCR-FF) [12], лежит выбор маршрута с наибольшим весом, рассчитываемым как
W (R) F(R) , h(R)
где W (R) – взвешенный коэффициент для маршрута R ; F(R) – количество свободных длин волн на R -
ом маршруте; h(R) – количество узлов на маршруте R . Данный метод учитывает не только пропускную
способность маршрутов, но и их длину. Большинство известных методов адаптивной маршрутизации выбирает маршруты из заранее за-
данного множества. Как правило, альтернативные пути для каждой пары источник–получатель, которые включены в это множество, являются реберно-непересекающимися кратчайшими путями [13]. При установке соединения маршрут передачи выбирается из заданного множества, базируясь на значении весовой функции для этого пути. При отсутствии свободных длин волн вдоль заранее заданных путей алгоритм пытается найти новый путь, содержащий свободные длины волн, и если такой путь найти не удается, то вызов блокируется.
Одним из представителей описанного выше класса методов адаптивной маршрутизации, который характеризуется достаточно высокой производительностью и высокой степенью близости получаемого решения к оптимальному, является метод динамической маршрутизации длин волн (Dynamic Wavelength Routing, DWR) [14]. Метод DWR предусматривает применение на первом этапе алгоритма выбора путей, базирующегося на использовании наименее загруженного пути с наименьшей степенью узлов (Least Congestion with Least Nodal-degree Routing algorithm, LCLNR) и алгоритма динамической маршрутизации длин волн с двух концов (Dynamic two-end wavelength routing algorithm, DTWR). Алгоритм маршрутизации с двух концов требует больших затрат времени. Кроме того, при расчете весов маршрутов не учитывается явление четырехволнового смешивания, что приводит к установке соединений, не удовлетворяющих требованиям по допустимой вероятности битовой ошибки.
Для устранения указанных недостатков требуется проведение дополнительных исследований, разработка новых и модернизация существующих методов решения задачи динамического выбора маршрутов и назначения длин волн в сетях WDM. Таким образом, целью данной работы является снижение вероятности блокировки вызовов при установке соединений и уменьшении вероятности битовой ошибки (BER) вследствие увеличения значения Q-фактора.
Математическая постановка задачи распределения длин волн в транспортной сети WDM
При решении задачи маршрутизации топологию сети будем описывать связным графом G(N, L) ,
где N ni – множество узлов сети; L {lgu } – множество каналов связи оптической сети, где
lgu (ng , nu ) . Математическая постановка задачи приведена ниже.
30 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)
Д.В. Агеев, А.А. Переверзев
Пусть ns – узел источника при передаче трафика; nd – узел получателя при передаче трафика;
N s – соседние узлы узла источника; Nd – соседние узлы узла получателя; W – множество длин волн,
использование которых допустимо в рамках используемой технологии оптической сети;
K sd
{K
i sd
}
–
множество маршрутов между узлами ns и nd .
Введем следующие обозначения: hsid
K
i sd
–1 – количество узлов на i-ом маршруте от ns
к nd ;
Wsid – множество свободных длин волн на i-ом маршруте; isd – количество свободных длин волн на
маршруте
K
i sd
,
где
isd Wsid
;
xi sd
– установка соединения с использованием
-ой длины волны по
маршруту
K
i sd
;
gu
– количество свободных длин волн в
lgu -оптическом канале связи; Wgu
– множест-
во свободных длин волн в lgu -оптическом канале связи; deg(ni ) – степень вершины ni в графе
G(N, L) ;
isd
– количество длин волн, доступных для использования вдоль маршрута
K
i sd
;
sd Ksd
–
выбранный маршрут при установке соединения между парой ns , nd ; O(sd ) – функция, определяющая
целесообразность выбора маршрута sd . Решение задачи сводится к необходимости найти:
sd – маршрут передачи оптического сигнала между узлами ns , nd ;
sd – длину волны, используемую вдоль маршрута sd . Критерий оптимальности – минимум вероятности блокировки:
Ksd
K
i sd
Z Blocking
iK
K sd
min .
Метод DWR базируется на использовании двух алгоритмов – LCLNR и DTWR. Суть алгоритма LCLNR заключается в том, что при выборе светового пути между узлами выбирается наименее загруженный световой путь, тем самым уменьшая вероятность блокировки. Список kкратчайших путей для каждой пары (s, d) вычисляется с помощью модифицированного алгоритма Дейкстры [15]. Выбор маршрута из списка k-кратчайших путей осуществляется на основе коэффициента целесообразности, вычисляемого как
O(sd
)
w h
.
Данное выражение учитывает пропускную способность маршрута и количество узлов, через которые проходит маршрут. После этого будет выбран маршрут с максимальным значением коэффициента целесообразности. Если существует несколько маршрутов, то будет выбран маршрут с минимальной суммой степеней узлов вдоль маршрута,
nd
min deg(ni ) . i ns
Если после выполнения данного условия число маршрутов более 1, то маршрут будет выбран случайным образом. Псевдокод алгоритма LCLNR приведен ниже:
Входные данные: граф сети G(N, L) и множество предоопределенных K кратчайших
маршрутов,
Ksid , i [1, k ]
для соединений
е {s, d}
и
sd
K
i sd
,i
[1, k ]
Вычисление функции O(Ksid )
O(Ksid ) wi / hi ,i [1, K ]
if
O
(
K
i sd
)
0, i
[1,
K
]
then
блокировка
вызова
на
установку
соединения;
return;
else end if
sd
maxi{1..k}
O(
K
i sd
),
sd
Temp;
if Temp 2 , then вычисляется sd min p[1,P]
deg(ni ), P Ksd .
ni PTemp j
if P 2 then маршрут выбирается случайным образом из множества Temp
end if end if
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
31
МЕТОД РЕШЕНИЯ ЗАДАЧИ ДИНАМИЧЕСКОГО ВЫБОРА МАРШРУТОВ...
Далее происходит установка соединения по выбранному маршруту и назначается длина волны
xi sd
с помощью использования метода first-fit [3].
Если не удается установить соединение с помощью алгоритма LCLNR, то применяется алгоритм
DTWR. Алгоритм DTWR рассматривает три сценария.
Сценарий А. Отсутствуют свободные длины волн в оптических каналах связи от узлов источников и
соседних узлов.
Сценарий В. Есть некоторое количество свободных длин волн в оптических каналах связи от узлов
источников и соседних узлов.
Сценарий С. Есть свободные длины волн между узлами источниками смежными, но отсутствуют
свободные длины волн на промежуточных узлах на световом маршруте.
Алгоритм DTWR работает только при сценариях В и С. Первый шаг алгоритма DTWR – опреде-
ление сценария. Если сценарий – не А, то выполняется удаление ребер из графа, которые не содержат
свободных длин волн. После этого выполняется поиск кратчайшего маршрута с помощью алгоритма
Дейкстры. На последнем шаге происходит передача этого маршрута на рассмотрение алгоритму LCLNR.
Псевдокод алгоритма DTWR приведен ниже.
while sd ;
do вычислить nsnv , nd nc , Wnsnv и Wnd nc
if (Wnsnv 0 ) или (Wndnc 0 ) then вызов блокируется; return;
else if
i,
ni
Wsi
N s
i,
ni
Wid
N d
then
вызов на запрос установки соединения блокируется; return;
else удаляются ребра с графа G(N , L) , где nsnv nd nc 0 ; генерируется
граф G(N , L)
end if
Вычисляется множество путей
K i ns nd
с помощью алгоритма Дейкстры;
if
K i ns nd
return;
then
K
i sd
,
вызов
на
установку
соединения
блокируется
else
K
i sd
K i ns nd
,
переход
к
алгоритму
LCLNR
end if
end while.
При исследовании метода решения задачи DRWA были обнаружены следующие недостатки:
при использовании алгоритма DTWR возникают большие временные затраты на этапе проверки условий сценариев. Этот фактор является критичным при решении задачи DRWA;
алгоритмом LNCLR при выборе светового маршрута не учитывается такое нелинейное искажение в волоконно-оптических сетях, как четырехволновое смешивание (ЧВС);
метод назначения длин волн first-fit неэффективен при наличии ЧВС [16].
Разработка метода устранения приведенных недостатков
Последствием ЧВС является появление побочных сигналов, в том числе на длинах волн, соответствующих другим рабочим каналам, что может привести к росту ошибок и ухудшению эффективности системы WDM. Для учета влияния данного явления при выборе маршрута была использована [17] следующая формула расчета мощности помехи ЧВС:
Pijk
(
fi ,
fj,
fk
)
9
D22 Pi Pj Pk eL
(1 eL )2
2
,
где Pi , Pj , Pk – мощности входных канальных сигналов на частотах fi , f j , fk соответственно; D ко-
эффициент вырожденности; коэффициент затухания оптического волокна; L длина отрезка оптического волокна.
Коэффициент нелинейности на длине волны рассчитывается по формуле
γ
2 πn2 λ Aэфф
,
где n2 коэффициент нелинейности показателя преломления; Aэфф эффективная площадь оптического волокна.
32 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)
Д.В. Агеев, А.А. Переверзев
Эффективность ЧВС описывается следующим выражением:
2
2 2
1
4eL
sin
2
L 2
(1 eL )
.
Коэффициент фазового согласования зависит от хроматической дисперсии Dc () и описывается следующим выражением:
2
2 k
c
fik f jk
Dc
(
)
2 k
2c
(fik
f jk )
d
Dc ( d
)
,
где интервал между каналами fik | fi fk | , f jk | f j fk | ; c скорость света.
Мощность помехи ЧВС на частоте fm равна сумме мощностей всех комбинационных продуктов:
NN
PЧВС ( fm )
Pijk ( fi, f j , fk ) ,
i 1 j 1
где N – количество каналов.
Проведем расчет мощности усиленного спонтанного излучения (ASE) с помощью выражения Pase 2nsp (G 1)hfm f0 ,
где nsp – коэффициент спонтанной эмиссии усилителя; h – постоянная Планка; f0 – ширина полосы
пропускания оптического фильтра демультиплексора WDM; G – коэффициент усиления усилителя. Допустим, что все участки имеют одинаковую длину, следовательно, мощность усиленного спон-
танного излучения на входе приемного оптического модуля (ПрОМ) равна сумме соответствующих мощностей на выходе всех усилителей:
Pase Pase (Nус 1) ,
где N ус – количество усилителей. Тогда мощность ЧВС на входе ПрОМ равна
PЧВС PЧВС G( N ус 1) .
На выходе фотоприемника оптический шум ЧВС и ASE соответственно формируют электриче-
ский сигнал с мощностями
PeЧВС
2z 2 Pвх
P ЧВС
8
,
P ease
4z 2 Pвх
P ease
fe f0
,
где fe – полоса пропускания электрического усилителя ПрОМ.
Чувствительность фотоприемника равна
z
e hfm
,
где – квантовая эффективность фотодетектора; e – заряд электрона.
Q-фактор и связанная с ним вероятность ошибки рассчитываются по формулам
Q
Pвх Pease PeЧВС
,
(1)
Pош
1
e
x2 2
dx
.
2π Q
где PeЧВС
– суммарная мощность ЧВС,
Pвх
– входная мощность;
P ease
– суммарная мощность ASE.
Полученное выражение (1) используется при расчете целевой функции на этапе выбора светового мар-
шрута алгоритмом LCLNR следующим образом:
O(sd
)
w
FMP(R) h
,
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
33
МЕТОД РЕШЕНИЯ ЗАДАЧИ ДИНАМИЧЕСКОГО ВЫБОРА МАРШРУТОВ...
где FMP(R) – коэффициент, который уменьшает значение O(sd ) , если вероятность ошибки для мар-
шрута R превысила допустимое значение. На этапе расчета коэффициента целесообразности выбора маршрута для установки соединения
происходит сравнение рассчитанного значения Q-фактора на каждом оптическом канале, через который проходит рассматриваемый маршрут, с допустимым значением Q-фактора. Если значение Q-фактора превышает допустимую норму, то значение целевой функции уменьшается.
Как показали исследования, использование алгоритма DTWR приводит к большим временным за-
тратам, поэтому в работе предлагается вместо него использовать алгоритм Дейкстры для поиска крат-
чайшего маршрута между заданной парой источник–получатель с использованием следующей метрики:
ln(
P(
K
i sd
))
ln(1
wsn W
)
...
ln m
(1
wkd W
)
,
где wsn – количество занятых длин волн в оптическом канале между узлами s и n. Данная метрика
характеризует вероятность успешной установки соединения, так как величина
P
K
i sd
пропорциональна
вероятности не блокирования маршрута.
Методика исследования эффективности предложенных методов базируется на имитационном
моделировании. На вход имитационной модели поступал простейший поток заявок на установку
соединения по световому пути. В дальнейшем производился выбор маршрута и назначение ему длины
волны. В случае успешной установки соединения в модели соответствующие ресурсы помечались как
занятые. В имитационной модели также моделировалась длительность соединения, после которого
занятые соединением сетевые ресурсы освобождались. При проведении эксперимента использовалась
топология оптической сети с 20 узлами, ранг каждого узла в сети – не меньше 3. Эксперимент проводил-
ся при различных интенсивностях поступления запросов на установку соединения, интервалы поступле-
ния запросов и время удержания ресурсов являлись случайными величинами, распределенными по
экспоненциальному закону. Величина загруженности сети изменялась в пределах (0,2–0,9).
Для назначения длин волн световому маршруту в предложенном методе использовался метод
random, а в базовом – first-fit. В результате проведения эксперимента были получены следующие резуль-
таты, показанные на рис. 1.
100
Вероятность блокировки
80 60 40
20
0
0,4
0,6 0,8
1
1,2 1,4 1,6 1,8 2
Интенсивность трафика, с–1
Базовый
Модифицированный
Рис. 1. Зависимость вероятности блокировки от интенсивности трафика для базового и модифицированного методов алгоритмов
В ходе анализа полученных результатов (рис. 1) установлено, что наибольший выигрыш вероятности блокировки (19%) соответствует интенсивности трафика 1,5. При интенсивности трафика 1 вероятность блокировки снижается на 14%, при 0,8 – на 8%. В эксперименте с интенсивностью трафика 0,4 из-за низкой вероятности блокировки не было зафиксировано ни одного заблокированного вызова.
На рис. 2 показаны значения Q-фактора базового и модифицированного методов при различных интенсивностях поступления запросов на установку соединения.
Анализируя полученные результаты, можно увидеть, что выигрыш Q-фактора растет с уменьшением интенсивности поступления запросов на установку соединения.
34 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)
Д.В. Агеев, А.А. Переверзев
6 5,5 5
Q-фактор
4,5
4
3,5 0,4
0,6 0,8
1
1,2 1,4 1,6 1,8 2
Интенсивность трафика, с–1
Базовый
Модифицированный
Рис. 2. Зависимость значений Q-фактора от интенсивности трафика для базового и модифицированного методов алгоритмов
При совместном анализе рисунков 1, 2 можно сделать вывод, что предложенные изменения в методе адаптивной маршрутизации по сравнению с базовым методом позволяют снизить вероятность блокировки и вероятность битовых ошибок (которая является функцией Q-фактора) и требуют меньшего числа вычислительных итераций. Наибольший выигрыш по уменьшению вероятности блокировки имеет место при средней интенсивности поступления вызовов. В случае низкой интенсивности трафика быстрее освобождаются ресурсы сети, и необходимость использования алгоритма DTWR уменьшается. Наибольший выигрыш для Q-фактора, напротив, получается при низкой интенсивности поступления вызовов.
Заключение
В работе проведен анализ методов решения задачи динамической маршрутизации и назначения длин волн (DRWA). Показано, что наиболее эффективным является метод адаптивной маршрутизации, как обеспечивающий гибкость и низкий уровень вероятности блокировки. В работе был рассмотрен метод адаптивной маршрутизации на основе использования алгоритмов LCLNR и DTWR. Показано, что использование алгоритма DTWR приводит к большим временным затратам на стадии проверки условий сценария, что является критичным при решении задачи DRWA. Не учитываются нелинейные искажения в волоконно-оптических сетях, такие как ЧВС, при выборе светового маршрута с помощью алгоритма LNCLR. Метод назначения длин волн first-fit неэффективен в случае наличия в каналах нелинейных явлений.
Для устранения данных недостатков предложена модификация алгоритма: вместо использования алгоритма DTWR предложен алгоритм Дейкстры с использованием метрики, которая основывается на пропускной способности маршрутов; введены математические выражения для учета ЧВС при расчете вероятности выбора светового маршрута; использован метод random при назначении длин волн световым маршрутам вместо first-fit.
Проведен эксперимент с использованием средств имитационного моделирования на искусственно синтезируемой топологии сети. При моделировании решалась задача RWA при различных интенсивностях поступлений вызовов на установку соединения. В ходе анализа полученных результатов было выявлено, что модифицированный метод адаптивной маршрутизации имеет наибольшую эффективность при интенсивности в 1,5 единицы, при этом выигрыш составляет 19%, тогда как среднее значение выигрыша составляет 13%. Наибольшее значение Q-фактора наблюдалось при самой низкой интенсивности трафика (0,4), так как в этом случае задействовано наименьшее число длин волн в оптических каналах. Средний выигрыш Q-фактора составил 0,812.
Литература
1. Gangxiang S., Rodney S.T. Translucent Optical Networks: The Way Forward // IEEE Communications Magazine. – 2007. – V. 45. – P. 48–54.
2. Ramesh G., Sundaravadivelu S. Reliable Routing and Wavelength Assignment for Optical WDM Networks // European Journal of Scientific Research. – 2010. – V. 48. – № 1. – P. 85–96.
3. Leonardi E., Mellia M., Marsan M.A. Algorithms for the logical topology design in WDM all-optical networks // Optical Networks. – 2000. – V. 1. – P. 35–46.
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 3 (85)
35
ПРОГНОЗИРОВАНИЕ КАЧЕСТВА ИЗОБРАЖЕНИЙ КОСМИЧЕСКИХ ОБЪЕКТОВ...
4. Mokhtar A., Azizoglu M. Adaptive wavelength routing in all-optical networks // IEEE/ACM Transactions on Networking. – 1998. – V. 6. – № 2. – P. 197–206.
5. Jianjun Yu. Radio-over-optical-fiber networks: introduction to the feature issue // Journal of Optical Networking. – 2009. – V. 8 (5). – P. 481–488.
6. Gomes P.H., Fonseca da N.L.S., Branquinho O.C. Optimization of the use of Radio Resource of Radio-OverFiber Access Networks // Global Telecommunications Conference (GLOBECOM 2010). – 2010. – P. 1–5.
7. Mirosław Klinkowski, Marek Jaworski, Davide Careglio. Channel Allocation in Dense Wavelength Division Multiplexing Radio-over-Fiber Networks // 12th International Conference on Transparent Optical Networks. – 2010. – P. 1–5.
8. Zang H., Jue J. P., Mukherjee B. A review of routing and wavelength assignment approaches for wavelengthrouted optical networks // Optical Network Magazine. – 2000. – V. 1. – № 1. – P. 47–60.
9. Karasan E., Ayanoglu E. Effects of wavelength routing and selection algorithms on wavelength conversion gain in WDM optical networks // IEEE/ACM Transactions on Networking. – 1998. – V. 6. – № 2. – P. 186– 196.
10. Birman A. Computing Approximate Blocking Probabilities for a Class of All-Optical Networks // IEEE Journal on Selected Areas in Communications. – 1996. – V. 14. – № 5. – P. 852–857.
11. Li L., Somani A.K. Dynamic Wavelength Routing Using Congestion and Neighborhood Information // IEEE/ACM Transactions on networking. – 1999. – V. 7. – № 5. – P. 779–786.
12. Xiaowen Chu, Bo Li, Zhensheng Zhang. A Dynamic RWA Algorithm in a Wavelength-Routed All-Optical Network with Wavelength Converters // INFOCOM. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies. – 2003. – V. 3. – P. 1795–1804.
13. Yates J.M., Rumsewicz M.P. Wavelength converters in dynamically-reconfigurable WDM networks // IEEE Communications Surveys & Tutorials. – 1999. – V. 2. – № 2. – P. 2–15.
14. Kungmang Lo, Daryoush Habibi, Quoc Viet Phung, Hoang Nghia Nguyen. Dynamic Wavelength routing in all optical meshnetwork // Proceedings of Asia Pacific Conference on Communications. – 2005. – P. 178–182.
15. Bhandari R. Survivable Networks: Algorithms for Diverse Routing. – Kluwer Academic Publishers, 1999. – 200 p.
16. Агеев Д.В., Ковальчук В.К., Переверзев А.А. Планирование распределения длин волн при проектировании транспортной сети DWDM // Восточно-европейский журнал передовых технологий. – 2011. – № 5/3 (53). – С. 25–29.
17. Педяш В.В., Решетников О.С. Оптимізація потужності лінійного сигналу системи DWDM // Цифрові Технології. – 2009. – № 5. – C. 27–33.
Агеев Дмитрий Владимирович Переверзев Александр Анатольевич
– Харьковский национальный университет радиоэлектроники, доктор технических наук, профессор, dm@ageyev.in.ua
– Харьковский национальный университет радиоэлектроники, аспирант, pereverzev_aa@mail.ru
36 Научно-технический вестник информационных технологий, механики и оптики,
2013, № 3 (85)