Выбор кратчайших путей.
Большинство сетей с коммутацией пакетов (сообщение разбивается на пакеты фиксированной длины, которые передаются независимо друг от друга, а затем собираются в исходное сообщение приёмником) осуществляют маршрутизацию на сетевом уровне модели OSI с применением различных алгоритмов выбора оптимального пути. Большинство алгоритмов основано на учете меры «стоимости» («сложности»), приписываемой каждой линии и/или каждому узлу. «Сложность» может быть фиксированной и учитывать такие параметры, как длина линии, скорость передачи, безопасность, величина нагрузки на линию, время задержки. «Сложность» может зависеть от вида входящей нагрузки и динамически изменяться с изменением вышеперечисленных параметров. Выбор маршрутов может выполняться централизовано, в узле управления сетью, а затем полученная информация рассылается по всем узлам. Децентрализованный выбор маршрутов предполагает обмен информацией между узлами о сложности и маршрутах до тех пор, пока в узлах не сформируются таблицы маршрутов с необходимыми данными о кратчайших путях.
Р
Рис.1. Пример сети
Рис.1. Пример сети
ассмотрим работу алгоритма централизованного выбора на примере сети (рис. 1). Для реализации алгоритма требуется знание глобальной структуры сети, т. е. списка всех узлов, и “cложности” линий связи. В примере на рис. 1. Целью является нахождение кратчайших путей от узла 1, являющегося источником, ко всем остальным узлам сети. Алгоритм решает эту задачу поэтапно, строя дерево кратчайших путей от узла 1 ко всем остальным узлам. На k-м шаге вычисляются кратчайшие пути к k-узлам, ближайшим к источнику. Эти узлы включаются во множество узлов N уже охваченных алгоритмом.Обозначим через D(v) расстояние (как сумму cложностей) от начального узла (1) до узла V. Пусть l(i,j)- заданная cложность пути между узлами I и J. Алгоритм состоит из двух частей: начального шага и итераций, повторяющихся до завершения алгоритма.
Начальный шаг. Устанавливаем N={1}. Для каждого узла V, не принадлежащего множеству N, устанавливаем D(v)=l(1,v)- cложность от узла 1 до узла v. Расстояние до узлов, не соединенных с узлом 1, принимаем бесконечно большим и обозначается “-“.
К
аждый
последующий шаг. Находим не принадлежащий
множеству N
узел W,
для которого cложность
D(w)
минимальна
и включаем
W
во множество N
{}.
Затем обновляем значения D(w)для
всех остальных узлов не принадлежащих
N
путем вычисления
,
находится минимальное значение из:
D(w)=l(1, w)- cложности от узла 1 до узла w (напрямую);
D(v)+ l(w, v)= l(1, v) + l(w, v) - cложности от узла 1 до узла w (через узел v).
Шаг 2 повторяется, пока во множество N не войдут все узлы. На каждом шаге во множество N добавляется станция, имеющая минимальную cложность от начального узла. Применение алгоритма к сети иллюстрируется последовательными шагами, указанными в таблице. В столбцах полужирным шрифтом обозначены и выделены цветом минимальные значения D(w) на каждом шаге. При равных расстояниях выбор производится случайно. После каждого шага соответствующий узел W (с минимальной “cложностью”) добавляется к множеству N, величины D(w) обновляются.
Например, после начального шага к множеству N добавляется узел 4 имеющий минимальное значение D(4)=1. На шаге 3 к множеству N добавляется узел 5 c минимальной сложностью D(5)=2 (т.к. D(3)=4, D(5)=2 и D(5)<D(3)) и т.д. После шага 6 алгоритм завершает свою работу.
На каждом шаге cложность определяется (вычисляется) от начальной станции до всех других (столбцы D(2) – D(6)). В столбце N при этом указывается не путь, а множество станций, до которых уже найдены пути с минимальными cложностями. D(N)- сложность до станции, выбранной на данном шаге в столбец N от начального узла.
По мере работы алгоритма строится дерево кратчайших путей с корнем в узле 1. С помощью дерева можно получить таблицу маршрутов для узла 1, показывающую пути, по которым нужно направлять сообщения к узлам назначения. Таблица 1.
Шаг |
Маршрут |
N |
D(N) |
D(2) |
D(3) |
D(4) |
D(5) |
D(6) |
Нач. |
- |
{1} |
0 |
2 |
-- |
1 |
-- |
-- |
2 |
{1,4} |
{1,4} |
1 |
2 |
4=1+3 |
1 |
2=1+1 |
-- |
3 |
{1,4,5} |
{1,4,5} |
2 |
2 |
3=1+1+1 |
1 |
2 |
4=1+1+2 |
4 |
{1,2} |
{1,2,4,5} |
2 |
2 |
3 |
1 |
2 |
4 |
5 |
{1,4,5,3} |
{1,2,3,4,5} |
3 |
2 |
3 |
1 |
2 |
4 |
6 |
{1,4,5,6} |
{1,2,3,4,5,6} |
4 |
2 |
3 |
1 |
2 |
4 |
Ш
аг
«Нач». Шаг 2. Шаг 3. Шаг 4. Шаг
5. Шаг 6.