Алгоритмы маршрутизации в сетях с коммутацией пакетов
Под алгоритмами маршрутизации подразумевают протокол сетевого уровня, который управляет пакетами при их движении по подсети связи до требуемого места назначения.
В зависимости от принципа передачи сообщений от абонента-источника к абоненту-адресату различают несколько модификаций КП, основными из которых являются режим виртуальных сообщений и дейтаграммный режим (в сетях с коммутацией пакетов алгоритм маршрутизации зависит от того, использует ли сеть датаграммную передачу (КП-Д) или виртуальные соединения (КП-В). В первом случае два последовательных пакета одного сообщения могут проходить по разным маршрутам, а во втором случае маршрут выбирается один раз и по нему передаются все пакеты сообщения.)
В режиме виртуальных сообщений абонент-источник перед тем, как послать сообщение абоненту-адресату, посылает специальный пакет виртуального вызова с информацией о величине посылаемого сообщения с целью резервирования ресурса (памяти) абонента-адресата для приема пакетов всего сообщения. Пакет виртуального вызова одновременно фиксирует маршрут передачи пакетов одного и того же сообщения (устанавливает виртуальный канал) и резервирует ресурсы УК для приема следующих друг за другом пакетов этого сообщения. По окончании сеанса связи виртуальный канал разрушается.
При дейтаграммном способе передачи пакетов абонент-источник посылает пакеты сообщения без предварительного уведомления абонента-адресата, при этом пакеты одного и того же сообщения могут передаваться по различным маршрутам.
Сложность алгоритмов маршрутизации определяется рядом причин. Во-первых, маршрутизация требует координации работы всех узлов сети, а не только пары узлов на звене, как в протоколе канального уровня. Во-вторых, система маршрутизации должна справляться с выходом из строя отдельных линий или узлов перенаправлением трафика обходным путем. В-третьих, для достижения наилучших показателей работы сети алгоритм маршрутизации может изменять маршрут при возникновении перегрузок в отдельных областях сети.
Сложность алгоритмов маршрутизации в любой сети во многом зависит от ее технологии. Примером простейших вариантов маршрутизации могут служить алгоритмы маршрутизации в сетях с радиальной, кольцевой структурой и в полносвязных сетях.
В радиальной сети (рис. 1.а) весь трафик проходит через центральный узел, и в таблице маршрутизации этого узла требуется лишь сопоставить номер узла-адресата с номером исходящего канала. В кольцевой сети (рис. 1.б) сообщение может достичь любого узла, двигаясь в одном из двух направлений. Алгоритм маршрутизации в этом случае настолько прост, что не требуется маршрутных таблиц. В полносвязной сети (рис. 1.в) каждый узел имеет прямую связь со всеми остальными. Это самый простой алгоритм, в котором таблица маршрутизации определяет единственный канал, который ведет к заданному узлу. В большинстве реальных сетей имеет место более сложная топология, представляющая собой ячеистые структуры с ячейками неправильной формы или радиально-узловую, иерархическую структуру. Рассмотрим некоторые примеры построения алгоритмов маршрутизации в сетях сложных топологических структур. К простейшим методам маршрутизации, которые не требуют таблиц маршрутизации, относятся метод случайной маршрутизации и лавинная процедура маршрутизации.
Рис. 1. Алгоритмы маршрутизации: а) радиальная сеть; б) кольцевая сеть; в) полносвязная сеть
Узел, работающий по методу случайной маршрутизации, получив очередной пакет и определив, что он не предназначен абоненту данного узла, выбирает случайным образом исходящее направление и посылает пакет дальше. Пакеты, передаваемые так по сети совершают случайные блуждания, "броуновское движение", и в конце концов прибывают к месту назначения. Этот метод весьма привлекателен благодаря двум своим достоинствам: чрезвычайной простоте и полной независимости от знания топологии сети.
При лавинной маршрутизации узел, которому необходимо передать пакет, размножает его в количестве экземпляров, равном числу исходящих из узла направлений без одного и передает эти копии по всем направлениям. Достоинством лавинной маршрутизации является то, что хотя бы одна из копий пакета достигнет адресата по кратчайшему пути.
В отличие от случайной маршрутизации лавинная маршрутизация гарантирует доставку каждого пакета.
Как случайная, так и лавинная маршрутизация могут быть рекомендованы для сетей малой размерности, когда нагрузка на сеть небольшая и требуется устойчивая работа сети при выходе из строя различных ее компонентов.В соответствии с архитектурой цифровых сетей маршрутизация осуществляется на сетевом уровне. При этом процессы маршрутизации, в свою очередь, можно представить в виде трех уровней:
1) передачи пакетов по выбранному маршруту (пути);
2) выбора пути передачи по маршрутным таблицам;
3) коррекции матриц маршрутов.
Методы коррекции матриц для сетей с КП часто называют методами адаптивной маршрутизации. При дейтаграммном режиме необходимость в выполнения процессов первого уровня отпадает, так как перед передачей информационных пакетов никакой маршрут не выбирается и не устанавливается определенный виртуальный канал между источником и потребителем информации. Процесс аналогичен передаче информации по установленному каналу.
Процессы второго уровня (выбор направления передачи по таблице маршрутов) осуществляется в процессе передачи информационных пакетов по сети в случае дейтограммного режима или с помощью специальных пакетов вызова при установлении виртуального канала. Процессы второго уровня аналогичны установлению соединения.
Процессы первого и второго уровней характерны для фиксированной маршрутизации в сетях с КП. Процессы третьего уровня относятся к динамическому управлению распределением потока пакетов.
Коррекция матриц маршрутов как при дейтаграммном режиме, так и при коммутации пакетов с виртуальными каналами может выполняться аналогичными методами.
Первоначально принципы построения и функционирования систем адаптивного (динамического) распределения информационных потоков были сформулированы в 1964 г. В. Г. Лазаревым. Несколько позднее на их основе был разработан метод распределенного управления выбором путей передачи информации, получивший название метода рельефов. Однако, несмотря на тот факт, что научный приоритет идей адаптивного распределения принадлежит нашей стране, практическая реализация была осуществлена в США в сети ARPA (Advanced Research Project’s Agency), созданной управлением перспективных научных исследований (DARPA) в 1968 г.
Основным критерием оптимальной маршрутизации в сетях с КП является среднее время задержки пакета в сети. Поэтому основной проблемой при адаптивной маршрутизации является оценка времени передачи пакетов по различным маршрутам.
В сетях с КП в режиме виртуальных соединений на каждом УК маршрутизация осуществляется с помощью таблицы путевых номеров виртуальных каналов. Указанная таблица сопоставляет номера линий, связанных с данным УК, а номера логических каналов в этих линиях - с номером виртуального канала. С помощью этих таблиц осуществляется выбор пути передачи пакетов в УК.
Существует ряд методов маршрутизации, в которых узлы сети, вначале не имевшие информации о топологии сети и по мере приема пакетов от других узлов приобретали ее. К этой группе методов относятся маршрутизация по предыдущему опыту (метод изучения обратного пути) и метод скорейшей передачи (метод "горячей картошки"). В этих методах требуется в дополнение к адресу узла назначения в каждом пакете иметь адрес узла-источника и счетчик шагов. На основе этой информации формируется маршрутная таблица, и работа системы выходит на стационарный режим. Методы позволяют сравнительно эффективно передавать информационные потоки и избегать блокировок из-за перегрузок. При проектировании сетей сложной топологии разработчики сталкиваются с задачей составления таких таблиц маршрутизации, в которых имелась бы возможность приспосабливаться к постоянно изменяющимся условиям, учитывающая выход из строя и восстановление элементов сети. Было предложено несколько методов адаптивной маршрутизации. Алгоритм работы такой системы складывается из нескольких шагов.
Шаг 1. Оценка способности сети пропускать потоки информации с учетом наличия исправных элементов (узлов, каналов).
Шаг 2. Составление оптимального плана распределения потоком (ПРП).
Шаг 3. Управление коммутационными устройствами узлов по составленному плану распределения потоков (реализация ПРП).
Шаг 4. Коррекция плана распределения потоков с изменением ситуации на сети.
Схема этого алгоритма приведена на рис. 2. Как следует из рисунка, подсистема распределения потоков является замкнутой, адаптивной, самонастраивающейся и может работать в двух режимах:
динамическом – воздействия на сеть следуют сразу же вслед за изменением ситуации на ней;
статическом – воздействие на сеть осуществляется через некоторые промежутки времени (случайные или детерминированные) с учетом изменения ситуации за эти промежутки.
Рис. 2. Схема алгоритма
Основной частью алгоритма является шаг 2 — составление оптимального плана распределения потоков (ПРП). Суть плана состоит в задании стратегии работы управляющих устройств узлов коммутации при обработке ими поступающей нагрузки.
Все методы составления ПРП можно разделить на детерминированные и статистические. В первом случае составление ПРП опирается на знание ситуации на сети в данный момент. При этом возможны фиксированные или альтернативные маршруты. В случае альтернативных маршрутов обязательно указывается очередность выбора того или иного маршрута. Во втором случае, помимо сведений о состоянии сети на данный момент, при составлении ПРП учитываются статистические данные о том или ином направлении передачи (случаи отказа в этом направлении, выхода из строя каналов, появления пиков нагрузки и т.п.). Система управления потоками приспосабливается не только к ситуации, но и к предыдущим состояниям сети.
Если ПРП меняется после обслуживания каждой заявки, то такие методы называются разовыми. В случае изменения ПРП после обслуживания нескольких заявок, метод называют групповым.
Реализация ПРП, составленного тем или иным методом, осуществляется узлами сети, в управляющих устройствах которых заложены маршрутные матрицы. В узлах коммутации каналов они представлены в виде кроссировочных таблиц, замонтированных при строительстве узла. Изменение кроссировочных таблиц происходит лишь при расширении сети либо в случае изменения стратегии движения информации по сети. Работа узла коммутации по управлению потоками в сети происходит следующим образом. При получении адресных признаков сообщения выполняется проба на занятость пучка каналов основного направления. Если в нем свободных каналов нет, то осуществляется поиск свободных каналов в первом обходном направлении, а при неудачной попытке — в пучке каналов второго обходного направления. Если свободных каналов нет ни в одном направлении, заявка теряется, абоненту дается сигнал занятости.
В узлах сети с КС и КП маршрутные матрицы записываются в памяти узлов. После анализа адреса начинается поиск свободных каналов в направлениях, соответствующих номеру выбора ветви. При неудачном исходе сообщение ставится в очередь и обслуживается в соответствии с принятой в данном узле дисциплиной очереди.
Выбор маршрута устанавливаемого виртуального канала
Выбор маршрута устанавливаемого виртуального канала может осуществляться централизованно или быть распределенным.
При централизованном способе информация о состоянии сети (сведения о нагрузке, наличии свободных логических каналов в линиях связи, данных очередей в УК и др.) поступает в специальный центр маршрутизации. На основе этих данных центр, используя алгоритм выбора кратчайших путей по критерию задержки пакета в сети, определяет по заявке от абонента-источника маршрут прохождения виртуального канала. Сведения о маршруте в виде управляющей информации передаются в УК, через которые проходит образованный виртуальный канал. На основе этой информации заполняется таблица путевых номеров указанных УК. Если виртуальный канал невозможно установить, то центр посылает абоненту-источнику отказ в установлении канала, либо запрос ставится в очередь на ожидание. После окончания сеанса связи центр осуществляет разъединение виртуального канала. Таким образом, выбор оптимального маршрута в случае централизованного управления в сетях с КП в режиме виртуального соединения осуществляется в центре на основе методов потока кратчайшего пути, в частности, матричных методов. При этом, каждой линии назначается определенный вес, зависящий от стоимости линии, ее длины, задержки во времени при передаче сигналов, нагрузки в линии, числа ошибок и др.
При распределенном способе выбора маршрутов виртуальных каналов на каждом УК имеется матрица маршрутов, определяющая порядок выбора исходящих линий для связи с УК, к которому включен абонент-адресат. При поступлении пакета-вызова на определенный УК, в заголовке которого указан УК-адресат, по маршрутной матрице в порядке предпочтения отыскиваются свободные логические каналы в исходящих линиях, при этом номер линии и номер логического канала заносятся в таблицу путевых номеров. Таким образом, таблица путевых номеров УК при каждом запросе на установление виртуального канала записывается в соответствии с маршрутной матрицей и с учетом занятости определенных логических каналов. В сетях с КП используются также гибридные методы маршрутизации, сочетающие в себе элементы распределенной и централизованной маршрутизации.