 |
|
Методы маршрутизации. Стохастические алгоритмы.
Если состояние сети меняется достаточно быстро, то централизованное управление может оказаться неэффективным. Во избежание этого создаются системы гибридной адаптивной маршрутизации, например, алгоритм дельта-маршутизации. При таком алгоритме центральный узел следит за общей ситуацией, а остальные узлы могут самостоятельно реагировать на локальные колебания трафика. В этом алгоритме центральный узел рассылает маршрутные таблицы, но они используются в сочетании с анализом длин очередей в каждом узле. При увеличении размеров сети возможны 2 случая:
1. Увеличение размеров достигается увеличением числа узлов
2. Узлы объединяемых сетей связываются общим каналом.
В обоих случаях возникают проблемы маршрутизации, но, как правило, эти проблемы связаны с использованием таблиц маршрутизации в узлах. Чтобы устранить этот недостаток, были разработаны простейшие алгоритмы маршрутизации без таблиц. Они работают следующим образом:
1. При стохастической маршрутизации пакеты, передаваемые по сети, направляются к случайным узлам и не имеют определенного направления. Пакеты снабжаются счетчиками пройденных узлов и уничтожаются, если их значение превышает установленную величину. Достоинства такого подхода – полное независимость от информации о состоянии сети и отсутствие таблиц. Недостаток – отсутствие гарантии того, что пакет вообще достигнет адресата.
2. При лавинной маршрутизации пакет, поступивший в узел, передается на все выходные каналы узла. В этом случае также применяется счетчик шагов. Достоинства – по крайней мере одна копия пакета достигнет адресата по кратчайшему пути, отсутствуют таблицы маршрутизации.
Однако в большинстве алгоритмов маршрутизации используется маршрутная таблица и фиксированная стратегия распределения потоков. Алгоритмы фиксированной маршрутизации легко можно приспособить к изменениям трафика и перейти в адаптивной маршрутизации. Алгоритм адаптивной маршрутизации рекомендуется применять в сетях с небольшой нагрузкой и при повреждениях в сети. К подобным алгоритмам относятся алгоритмы локальной и распределенной адаптивной маршрутизации. Локальный алгоритм мало увеличивает пропускную способность сети, он слишком медленно реагирует на изменение трафика, ведущие к перегрузке. Однако, важно то, что сеть оказывается устойчивой. Распределенная маршрутизация учитывает указанный недостаток и обеспечивает минимальное время задержи передаваемого трафика. При таком подходе каждый узел формирует таблицы маршрутов и передает их всем узлам назначения с указанием времени передачи к каждому адресату. После обмена таблицами задержек каждый узел приступает к пересчету задержек, учитывая длины собственных очередей. Эти расчеты показывают, к какому из узлов следует направить пакет, чтобы достичь его с минимальными задержками.