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

Для статических ТКС, в которых планирование оптимальных маршрутов производится одновременно для разных пар узлов, особую роль играет алгоритм Флойда [3]. Этот алгоритм вычисляет маршруты минимальных стоимостей между всеми парами узлов ТКС. Пусть узлы графа G(A, R, W) проиндексированы, т.е..

Лемма 6.2. Пусть d_k (a_i, a_j) – минимальная стоимость маршрутов из a_i в a_j, причем индексы промежуточных узлов ТКС не превосходят k. Тогда

. (6.5)

Доказательство леммы 6.2. Рассмотрим все маршруты из a_i в a_j, где индексы промежуточных узлов не превосходят k+1. Кратчайший среди них маршрут либо содержит вершину a_k+1, либо нет. Во втором случае, так как вершина a_k+1 роли не играет, то кратчайший маршрут остается тем же, что и при k, и поэтому d_k+1 (a_i, a_j)= d_k (a_i, a_j). В первом случае маршрут можно будет разбить на два подмаршрута: из a_i в a_k+1 и из a_k+1 в a_j. Поскольку индексы промежуточных узлов в этих маршрутах не превосходят k, то

d_k+1 (a_i, a_j)= d_k (a_i, a_k+1)+ d_k (a_k+1 , a_j). (6.6)

Лемма 6.2 доказана.

Таким образом, рекуррентный алгоритм Флойда представляет собой последовательное вычисление по формуле (6.5) стоимостей и определение группы оптимальных маршрутов между всеми парами узлов ТКС. Таким образом, верно следующее равенство:

. (6.7)

Замечание. При настройке таблиц маршрутизации в ТКС удобно пользоваться следующим представлением маршрутов: P=P^{N× N}={ t_ij }, где значение t_ij является индексом следующего (второго) узла кратчайшего маршрута из a_i в а_j. Тогда программная реализация алгоритма Флойда может выглядеть следующим образом:

Begin

for i: =1 to N do

for j: =1 to N do

Begin

d(a_i, a_j): =W(a_i, a_j);

t_ij = j;

End

for k: =1 to N do

for i: =1 to N do

for j: =1 to N do

if d(a_i, a_j) > d(a_i, a_j)+ d(a_i, a_j) then

Begin

d(a_i, a_j): = d(a_i, a_k)+ d(a_k, a_j);

t_ij = t_ik;

End

End.

Сложность алгоритма Флойда характеризуется величиной O(N³).

6.3. Методы оптимальной много-адресной маршрутизации потоков данных

6.3.1. Много-адресный алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда является распределённым алгоритмом оптимальной много-адресной маршрутизации [4]. Его идею можно сформулировать следующим образом: найти оптимальные маршруты передачи данных от данного узла-источника к остальным узлам.

Алгоритм выполняется итеративно на каждом узле сети. На каждой итерации алгоритма вычисляются оптимальные маршруты от узла-источника до остальных узлов, причём число составляющих их рёбер не превосходит номер итерации. Это означает, что на первом шаге будут определяться кратчайшие однозвенные маршруты, на втором – кратчайшие маршруты, содержащие не более двух звеньев, на третьем – не более трёх и т.д.

Рассмотрим описание алгоритма для конкретного узла. Пусть даны:

G(s, f, w) – ориентированный граф;

– узел-источник;

– стоимость ребра : w(i, i) =0; , если узлы i и j не соединены; , если узлы i и j соединены;

h – номер итерации (то есть, рассматриваются маршруты, содержащие не более h каналов связи);

L_h(j, v) – стоимость кратчайшего маршрута от узла j до узла v, содержащего не более h каналов связи.

Требуется построить оптимальные маршруты от узла-источника s₀ до остальных узлов и вычислить их стоимости.

Работа алгоритма:

1. Инициализация.

для всех ;

L_h (s₀, s₀)=0 для всех h;

2. Итерация.

Для каждого узла вычисляем

. (6.8)

Новый маршрут до узла v получается из кратчайшего маршрута от узла j до узла v, на котором достигается минимум и ребра (s₀, j). При этом старый маршрут до узла v выбрасывается.

6.3.2. Много-адресный алгоритм Дейкстры

Алгоритм Дейкстры используется для построения деревьев кратчайших маршрутов от узла-источника ко всем остальным узлам и выполняется итеративно. На каждой итерации алгоритм определяет кратчайший маршрут до ближайшего из необработанных узлов (то есть, до узла, стоимость кратчайшего маршрута до которого не больше стоимостей кратчайших маршрутов от узла-источника до других узлов), после чего данный узел считается обработанным алгоритмом. Изначально все узлы, кроме узла-источника, считаются необработанными.

Алгоритм состоит в следующем. Пусть даны:

G(s, f, w) – ориентированный граф,;

–узел-источник;

– множество узлов, обработанных алгоритмом;

()– множество узлов, обрабатываемых алгоритмом;

–остальные узлы;

– стоимость ребра ; w(i, j) =0; , если эти два узла не соединены непосредственно; , если эти два узла непосредственно соединены;

L(j) –если , то это оценка алгоритмом стоимости маршрута от узла-источника s₀ до узла n; если , то это стоимость кратчайшего маршрута от s₀ до n. Для остальных j это значение не определено.

Требуется построить дерево кратчайших маршрутов от узла-источника s₀ до остальных узлов и вычислить их стоимости.

Работа алгоритма:

1. Инициализация.

T₁ - пусто, T₁ ={ s₀ }, т.е. вначале множество обработанных узлов состоит только из узла-источника. Узлу-источнику сопоставляется пустой маршрут.

L (n)= w(s₀, n) для , т.е. начальные стоимости маршрутов к соседним узлам – это веса соответствующих рёбер графа G, L(s₀)=0.

2. Шаг алгоритма.

Берём из T₁ узел с минимальной оценкой стоимости маршрута и помещаем его в T₀ ( а также обозначаем соответствующий ему маршрут как кратчайший ). Иными словами,

находим такой, что

. (6.9)

При этом рассматриваем все рёбра с начальным узлом x. Для каждого ребра (x, j) выполняется одно из трёх действий:

А) если , то никаких действий не производится;

Б) если , то j переводится из множества T₂ в T₁, причём ей сопоставляются значение

, (6.10)

а также маршрут, состоящий из кратчайшего маршрута до x и ребра (x, j).

В) если , то производится новая оценка

, (6.11)

и узлу j сопоставляется соответствующий оценке маршрут (либо прежний, либо как в Б)).

Итерации повторяются до тех пор, пока T₀ не станет равно s. По окончании работы алгоритма для каждого узла x будет определен кратчайший маршрут к нему от узла-источника, а значение L(x) будет соответствовать стоимости этого маршрута.

Алгоритм Дейкстры имеет сложность O(N²), где N – число узлов в ТКС.

6.4. Особенности маршрутизации в динамических компьютерных сетях

Необходимость в адаптивной маршрутизации (АМ) возникает при непредсказуемых изменениях структуры (узлов и каналов связи) и параметров (весов) ТКС или при перегрузке буферов узлов или каналов связи ТКС. По существу речь идёт о маршрутизации в динамических (нестационарных) глобальных ТКС с переменной структурой.

Причинами изменения структуры ТКС могут быть как добавление или отказ (выход из строя) отдельных узлов и каналов связи, так и сетевые перегрузки, препятствующие передаче потоков данных по запрещённым (перегруженным) узлам и каналам. Поэтому маршрутизаторы должны планировать и корректировать оптимальные маршруты передачи пакетов данных, адаптируя их к возможным изменениям ТКС, происходящим в реальном времени. Для этого необходима обратная связь о текущем состоянии узлов и каналов связи ТКС, которая может быть организована путём обмена информацией между узлами ТКС.

Отличительными чертами адаптивной маршрутизации по сравнению со статической или динамической маршрутизацией являются следующие особенности:

- алгоритмы адаптивной маршрутизации требуют учёта и обработки текущей информации о реальном состоянии ТКС, что делает их более сложными и увеличивает время определения оптимального маршрута;

- передача информации о состоянии или структурных изменениях в ТКС к адаптивным маршрутизаторам дополнительно загружает сеть и приводит к задержкам (запаздыванию);

- увеличение сетевой нагрузки и времени запаздывания может приводить к колебаниям или автоколебаниям и увеличению числа шагов при определении оптимального маршрута.

Адаптивная маршрутизация потоков данных в глобальных ТКС имеет ряд преимуществ по отношению к неадаптивной (статической или динамической) маршрутизации, а именно:

- обеспечивает работоспособность и надёжность ТКС при непредсказуемых изменениях их структуры или параметров;

- приводит к более равномерной загрузке узлов и каналов связи ТКС за счёт «выравнивания» нагрузки;

- упрощает управление передачей потоков данных и облегчает адаптацию к сетевым перегрузкам;

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

Достижение этих преимуществ в значительной степени зависит от используемых принципов и алгоритмов адаптивной маршрутизации потоков данных в ТКС с непредсказуемо изменяющейся структурой и заранее неизвестным трафиком.

Как отмечается в 6-ом издании монографии [1], «адаптивная маршрутизация – это задача, которую весьма трудно решить должным образом. Доказательством этого может служить тот факт, что наиболее крупные сети с пакетной коммутацией (такие, как ARPANET и её «наследники», TYMNET и сетевые архитектуры IBM и DEC) неоднократно претерпели значительные изменения принципов маршрутизации».

Принципы алаптивной маршрутизации можно разбить на три класса в зависимости от используемой информации о реальной (текущем) состоянии ТКС, т.е. от характера сигналов обратной связи:

- локальная информация (обратная связь) от одного узла ТКС;

- локальная информация (обратная связь) от узла и его «соседей» в ТКС;

- глобальная информация (обратная связь) от всех узлов ТКС;

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

Более эффективные принципы адаптивной маршрутизации основываются на передаче в начальный узел локальной информации (обратной связи) от соседних узлов или глобальной информации от узлов ТКС. В качестве такой информации могут использовываться, например, данные об отказах или задержках в узлах или каналах связи в ТКС.

В зависимости от используемых способов обработки локальной или глобальной информации (обратной связи) принципы адаптивной маршрутизации можно разбить на три класса:

- централизованная (иерархическая одноуровневая) маршрутизация;

- децентрализованная (распределённая) маршрутизация;

- мульти-агентная (много-адресная) маршрутизация.

Принцип централизованной маршрутизации (ЦМ) заключается в том, что каждый узел ТКС сначала передает информацию о своем состоянии (задержки или пропускные способности выходных каналов и т.п.) центральному узлу-маршрутизатору. Затем этот маршрутизатор вычисляет оптимальный маршрут на основе полученной глобальной информации о текущем состоянии м передает его обратно всем узлам ТКС. После этого начинается управляемая передача пакетов от узла-источника к узлу-получателю ТКС по спланированному оптимальному маршруту.

Принцип децентрализованной маршрутизации (ДМ) основывается на распределённом обмене локальной информацией между узлами ТКС и использовании этой информации о текущем состоянии узлов и каналов связи ТКС для вычисления оптимального маршрута. По мере вычисления последовательных участков этого маршрута осуществляется распределённо-управляемая передача пакетов от узла-источника к узлу-получателю ТКС.

Принцип мульти-агентной маршрутизации (МАМ) является своеобразным компромиссом между принципами централизованной и децентрализованной маршрутизации [29, 69]. Он основывается на многоадресной маршрутизации и анализе возможных сетевых конфликтов с целью их предотвращения или разрешения в процессе управляемой передачи пакетов по множеству оптимальных маршрутов от узлов-источников к узлам-получателям. Более подробно принцип и конкретные методы мульти-агентной маршрутизации будут рассмотрены в следующем разделе.