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