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