Маршрутизация – это процесс определения в коммуникационной сети пути, по которому вызов либо блок данных может достигнуть адресата. Маршрутом в информационной сети именуют путь, по которому осуществляется передача данных из одного порта в другой.
Наиболее удобной формой представления маршрута является граф. Маршрутизация обеспечивает преобразование адреса объекта назначения в перечень каналов, по которым этот блок следует к адресату. Маршрутизация является распределенным процессом и выполняется всеми узлами коммутации сети с маршрутизацией данных. Для этого каждый узел определяет канал, по которому необходимо направить вызов либо блок данных. Выполняя такие действия, в каждом узле обеспечивается передача вызова либо блока данных от системы-отправителя к системе-адресату, возможно, по оптимальному маршруту.
Последний изменяется в зависимости от выхода из строя отдельных каналов, их загрузки и протяженности.
На рисунке стрелками показаны возможные направления передачи данных через коммуникационную сеть от абонентской системы А до абонентской системы B.
При коммутации каналов прокладка маршрута через коммуникационную сеть осуществляется только в момент начала сеанса взаимодействия абонентских систем. Для этой цели система-инициатор сеанса передает через сеть вызов. Он проходит через узлы коммутации, каждый из которых вносит свою лепту в маршрутизацию. В результате создается последовательность каналов, соединяющих две взаимодействующие в течении сеанса системы.
При осуществлении коммутации пакетов маршрутизация происходит в течение всего сеанса взаимодействия. Через сеть не передается сигнальная информация и не создается постоянная (на все время сеанса) последовательность каналов. Здесь узлы коммутации осуществляют маршрутизацию блоков данных по адресам их назначения.
В сетях используются различные методы маршрутизации:
Селективная маршрутизация характеризуется тем, что блоки данных посылаются сразу по нескольким направлениям, исходя из того, что они достигнут адресата. Пример ѕ лавинный алгоритм: основан на рассылке копий пакета по всем направлениям. Пакеты сбрасываются, если в данном узле копия уже проходила. Лавинный алгоритм обеспечивает надёжную доставку, но порождает значительный трафик, поэтому используется для передачи пакетов большой ценности.
Вероятностная маршрутизация предполагает случайный выбор пути блоков данных, при этом считается, что они обязательно достигнут адресата.
Фиксированная (статическая) маршрутизация предусматривает составление таблиц маршрутов, указывающих наиболее эффективные пути предполагаемого трафика сети. Здесь маршрут выбирается заранее и не зависит от состояния сети.
Адаптивная маршрутизация отличается от фиксированной тем, что таблицы маршрутов обновляются в зависимости от колебаний трафика. Пример ѕ алгоритм “кратчайшей очереди”: пакет посылается по направлению, в котором наименьшая очередь в данном узле.
Блоки данных не всегда прибывают в пункты назначения в том же порядке, в котором отправляются. Это происходит по следующим причинам:
В результате для того, чтобы восстанавливать сообщение, передаваемое последовательностями блоков, последнее необходимо обрабатывать в пунктах назначения.
Составление таблицы маршрутов для фиксированной (статической) маршрутизации осуществляется администрацией сети при проектировании или модификации сети. Однако такой принцип маршрутизации во многих случаях может оказаться неэффективным, т.к. на сети могут оказаться повреждения или перегрузки. Поэтому целесообразно корректировать план распределения информации в зависимости от текущей топологии сети, длин очередей в узлах коммутации, интенсивности входных потоков и т.д.
Цель маршрутизации – доставка пакетов по назначению с максимизацией эффективностью. Чаще всего эффективность выражена взвешенной суммой времени доставки сообщений при ограничении снизу на вероятность доставки.
Алгоритмы маршрутизации включают процедуры:
В зависимости от того, используется при выборе направления информация о состоянии только данного узла или всей сети, различают алгоритмы изолированные и глобальные.
Простейший алгоритм – это изолированный статический.
В алгоритмах маршрутизации используется много различных показателей. Сложные алгоритмы маршрутизации при выборе маршрута могут базироваться на множестве показателей, комбинируя их таким образом, что в результате получается один отдельный (гибридный) показатель.
Ниже перечислены показатели, которые используются в алгоритмах маршрутизации:
Наиболее широко используемые протоколы маршрутизации: RIP (метод рельефов) и OSPF.
Рельеф – это оценка кратчайшего пути от узла A до узла B. Оценка (расстояние) может выражаться временем доставки, надёжностью доставки или числом узлов коммутации на данном маршруте.
В таблице маршрутизации узла А каждому из основных узлов отводится одна строка со следующей информацией: узел назначения, длина кратчайшего пути, номер N ближайшего узла, соответствующего кратчайшему пути, список рельефов от A до В через каждый из смежных узлов.
Например, для узла а строка для d выглядит так (зная, что из узла а можно попасть в узел d через узлы j и k):
Пусть изменилась задержка Rak(d) так, что она стала меньше, чем Raj(d). Тогда в строке d таблицы маршрутизации узла a корректируется Ra(d), N(d) изменяется на k, и кроме того всем соседям узла а посылается сообщение об изменённом Ra(d). Например, в некотором соседнем узле l при этом будет изменено значение Rla(d)=Ra(d)+Rl(a). Мы видим, что возникает итерационный процесс корректировки маршрута информации в узлах коммутации.
Хотя данный алгоритм сходится медленно, для относительно небольших сетей он вполне приемлем.
Возможен упрощенный вариант формирования рельефов. Он заключается в следующем: пусть i – это произвольный узел коммутации сети связи. i-рельефом называется процедура присвоения значений числовой функции каждой линии связи. Он строится следующим образом: из i-ого узла коммутации по всем исходящим линиям связи передается число “1”. Все узлы коммутации, в которые поступило число 1, передают по всем исходящим линиям связи, кроме тех, по которым поступила 1, число 2. Далее узлы коммутации, по которым поступило число 2, передают 3, и т.д. до тех пор, пока все линии связи не будут пронумерованы. Говорят, что линия связи имеет n высоту, если она обозначена числом n в i-рельефе.
Указанным способом формируется рельеф из каждого узла коммутации сети связи. В результате линия связи с минимальной высотой является исходящей линией связи первого выбора. Линии связи с большими высотами соответственно являются линиями связи 2, 3, и т.д. выбора.
Пример формирования 4-рельефа:
Чтобы найти кратчайший маршрут коммутации к узлу A, достаточно в каждом узле коммутации выбирать линию связи с меньшим весом. Например, кратчайший маршрут от N до A будет следующий:
Он основан на использовании в каждом маршрутизаторе информации о состоянии всей сети. Рассмотрим алгоритм применительно к формированию маршрутной таблицы узла A графа, изображенного на рисунке:
Обозначим кратчайшее расстояние от a к i через Ri. Разделим узлы на 3 группы:
|
№ итерации |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
b |
3,a |
3 |
|
|
|
|
|
|
|
|
c |
1,a |
|
|
|
|
|
|
|
|
|
d |
|
8,c |
5,b |
|
|
|
|
|
|
|
e |
|
|
7,b |
7 |
7 |
|
|
|
|
|
f |
|
13,c |
13 |
7,d |
7 |
7 |
|
|
|
|
g |
|
|
|
6,d |
|
|
|
|
|
|
h |
|
|
|
|
9,g |
9 |
9 |
|
|
|
k |
|
|
|
|
|
11,e |
11 |
11 |
|
|
n |
|
|
|
|
|
17,e |
17 |
12,h |
12 |
Итерационный процесс начинается с отнесения узла a к группе перманентных. Далее определяются узлы, смежные с узлом a. Это узлы b и c, которые включаются в группу пробных. Включение в группу пробных отмечается указанием в клетке таблицы, рядом с оценкой, расстояния также имени узла, включаемого в этом шаге в число перманентных. На следующем шаге узел с минимальной оценкой (c) включается в группу перманентных, а узлы, смежные с ним, в группу пробных, и для них оцениваются расстояния Rd=8 и Rf=13. Теперь среди пробных узлов минимальную оценку имеет узел b. Он включается в группу перманентных узлов, узел e в группу пробных, и для всех пробных узлов, смежных с b, рассчитываются оценки. Это, в частности, приводит к уменьшению оценки узла d с 8 на 5. В таблице это отражено, во-первых подчеркиванием, а во-вторых заменой у узла d метки c на b. Если же новая оценка оказывается больше прежней, то она игнорируется. Этот процесс продолжается пока все узлы не окажутся в группе перманентных. Теперь виден кратчайший путь от a к любому другому узлу x, или что тоже самое – от x к a. Это последовательность конечных отметок в строках таблицы, начиная с последнего узла x. Так для узла x=n, имея в строке n отметку h, в строке h отметку g, и окончательно кратчайший путь есть: a-b-d-g-h-n.
Кроме рассмотренных, существуют также и другие методы формирования таблицы маршрутизации, иногда их называют планами распределения информации: игровой, логический, логико-игровой.
Таблица. Устройства, реализующие функции маршрутизации
|
Наименование устройства |
Характеристика и функции устройства |
Пример схемы включения |
|
1. Повторитель |
Выполняет функции регенерации сигналов. Принимает сигналы от пользователя или из конечного узла коммутации и побитно синхронно передает их другому повторителю или пользователю, тем самым улучшается форма, мощность, синхронизация сигналов, и т.д. |
|
|
2. Концентратор |
Выполняет функции повторителя, который имеет несколько портов и объединяет трафик нескольких пользователей и узлов коммутации. Таким образом выполняет функции повторителя, мультиплексора и демультиплексора, устройств защиты сети от несанкционированного доступа (НСД). |
|
|
3. Мост |
Осуществляет выбор исходящих линий связи (формирует таблицы коммутации). Делит сеть на независимые подсети. Разрешает передачу сообщения пользователей из одной подсети в другую только в том случае, если такая передача необходима, тем самым изолирует трафик подсетей с целью уменьшения возможности несанкционированного доступа. |
|
|
4. Коммутатор |
Осуществляет выбор исходящей линии связи (формирует таблицы коммутации). |
|
|
5. Маршрутизатор |
Выполняет все функции маршрутизации: формирование плана распределения информации (таблиц маршрутизации), выбор дополнительных линий связи. Дополнительные функции: связывает в единую сеть подсети, построенные с использованием различных сетевых технологий. Выполняет буферизацию, фильтрацию передаваемых пакетов. Осуществляет приоритетную обработку трафика. |
|
|
6. Сервер маршрутов |
Собирает и анализирует информацию о топологии сети, затем по запросам передает ее в маршрутизаторы, которые освобождены от функции создания плана распределения информации. |
|
|
|
 |
