Алгоритмы управления маршрутизацией

Алгоритмы маршрутизации можно разделить на:

адаптивные и неадаптивные;

глобальные и децентрализованные;

статические и динамические.

Алгоритмы маршрутизации могут быть классифицированы по типам. Например, алгоритмы могут быть:

Статическими или динамическими;

Одномаршрутными или многомаршрутными;

Одноуровневыми или иерархическими;

Внутридоменными и междоменными;

Алгоритмами состояния канала или вектора расстояний.

Статические или динамические алгоритмы

Распределение статических таблиц маршрутизации устанавливается администратором сети до начала маршрутизации. Оно не меняется, если только администратор сети не изменит его. Алгоритмы, использующие статические маршруты, просты для разработки и хорошо работают в окружениях, где трафик сети относительно предсказуем, а схема сети относительно проста.

Динамические алгоритмы маршрутизации подстраиваются к изменяющимся обстоятельствам сети в масштабе реального времени. Они выполняют это путем анализа поступающих сообщений об обновлении маршрутизации. Если в сообщении указывается, что имело место изменение сети, программы маршрутизации пересчитывают маршруты и рассылают новые сообщения о корректировке маршрутизации. Динамические алгоритмы маршрутизации могут дополнять статические маршруты там, где это нужно.

Одномаршрутные или многомаршрутные алгоритмы

Некоторые сложные протоколы маршрутизации обеспечивают множество маршрутов к одному и тому же пункту назначения. Такие многомаршрутные алгоритмы делают возможной мультиплексную передачу трафика по многочисленным линиям; одномаршрутные алгоритмы не могут делать этого. Преимущества многомаршрутных алгоритмов - они могут обеспечить большую пропускную способность и надежность.

Одноуровневые или иерархические алгоритмы

Некоторые алгоритмы маршрутизации оперируют в одноуровневом пространстве, в то время как другие используют иерархию маршрутизации. В одноуровневой системе маршрутизации все маршрутизаторы равны по отношению друг к другу. В иерархической системе маршрутизации некоторые маршрутизаторы формируют то, что составляет основу (базу) маршрутизации. Например, те, которые находятся на высокоскоростных магистралях. Пакеты из не базовых маршрутизаторов перемещаются к базовым маршрутизаторам и перемещаются через них до тех пор, пока не достигнут общей области пункта назначения. Начиная с этого момента, они перемещаются от последнего базового маршрутизатора через один или несколько не базовых маршрутизаторов до конечного пункта назначения. Системы маршрутизации часто устанавливают логические группы узлов, называемых доменами или областями. В иерархических системах одни маршрутизаторы какого-либо домена могут сообщаться с маршрутизаторами других доменов, в то время как другие маршрутизаторы этого домена могут поддерживать связь с маршрутизаторами только в пределах своего домена. В очень крупных сетях могут существовать дополнительные иерархические уровни. Маршрутизаторы наивысшего иерархического уровня образуют базу маршрутизации. Основным преимуществом иерархической маршрутизации является то, что она имитирует организацию большинства компаний и, следовательно, очень хорошо поддерживает их схемы трафика. Большая часть сетевого трафика компании сосредоточена в пределах своего домена, следовательно, внутридоменным маршрутизаторам необходимо иметь информацию только о других маршрутизаторах в пределах своего домена, поэтому их алгоритмы маршрутизации могут быть упрощенными. Соответственно, может быть уменьшен и трафик обновления маршрутизации, зависящий от используемого алгоритма маршрутизации.

Внутридоменные или междоменные алгоритмы

Некоторые алгоритмы маршрутизации действуют только в пределах доменов; другие - как в пределах доменов, так и между ними. Природа этих двух типов алгоритмов различная. Поэтому понятно, что оптимальный алгоритм внутридоменной маршрутизации не обязательно будет оптимальным алгоритмом междоменной маршрутизации.

Алгоритмы состояния канала или вектора расстояния

Алгоритмы состояния канала (известные также как алгоритмы «первоочередности наикратчайшего маршрута») направляют потоки маршрутной информации во все узлы объединенной сети. Однако каждый роутер посылает только ту часть маршрутной таблицы, которая описывает состояние его собственных каналов. Алгоритмы вектора расстояния (известные также как алгоритмы Бэлмана-Форда) требуют от каждого роутера посылки всей или части своей маршрутной таблицы, но только своим соседям. Алгоритмы состояния каналов фактически направляют небольшие корректировки по всем направлениям, в то время как алгоритмы вектора расстояний отсылают более крупные корректировки только в соседние роутеры.

Отличаясь более быстрой сходимостью, алгоритмы состояния каналов несколько меньше склонны к образованию петель маршрутизации, чем алгоритмы вектора расстояния. С другой стороны, алгоритмы состояния канала характеризуются более сложными расчетами в сравнении с алгоритмами вектора расстояний, требуя большей процессорной мощности и памяти, чем алгоритмы вектора расстояний. Вследствие этого, реализация и поддержка алгоритмов состояния канала может быть более дорогостоящей. Несмотря на их различия, оба типа алгоритмов хорошо функционируют при самых различных обстоятельствах.

3. Примеры алгоритмов

Алгоритм связующего дерева (Адаптивные алгоритмы).

Связующее дерево (Spanningtree) : граф, не содержащий петель. Связующее дерево известно всем узлам. В соответствии с этим каждый узел рассылает копии пакетов.

Reverse path forwarding (Reverse path flooding)

Алгоритм является самым простым и неадаптивным вариантом. Каждый полученный пакет пересылается по всем линиям, за исключением той, через которую он был получен. При этом только отправитель должен знать все связующее дерево. Алгоритм: Каждый маршрутизатор знает путь, который он должен использовать для unicast-пакетов. При получении пакета проверяется, был ли пакет получен по линии, которая обычно используется и пересылается по всем линиям, за исключением той, через которую он был получен. В противном случае пакет отбрасывается.

Reversepathbroadcast

В отличие от Reversepathforwarding пакеты отправляются только по линиям, по которым другие узлы принимают данные.

ShortestPath Routing

Данный алгоритм подсчитывает наименьший маршрут от корня дерева до узлов. Смысл заключается в создании пучка узлов Q, для которых уже был определен оптимальный маршрут. Оператор генерирует таблицы маршрутизации, которые загружаются при его инициализации и более не изменяются. Основывается наалгоритме Дейкстры.

Алгоритм:

наименьшее расстояние от A до D;

узел A помечается как рассматриваемый;

присвоить всем соседним узлам значение с дистанцией до рассматриваемого узла B (2, A), G (6, A) и добавить их в список кандидатов;

выбрать из списка кандидатов узел с наименьшей дистанцией B (2, A) ;

пометить этот узел как рассматриваемый и добавить его в дерево;

перейти к пункту 2.

Неадаптивные алгоритмы.

Flow-Based Routing

Данный алгоритм является одним из неадаптивных алгоритмов. Он учитывает не только дистанцию между маршрутизаторами, но и загрузку сети. Полезен для нахождения маршрута для больших дистанций с большими задержками в доставке пакетов

Пример

Дан граф для мощности и матрица трафика.

Рисунок 3.1 Граф для мощности Рисунок 3. 2 Матрица трафика

Подсчет загрузки каждой линии:

взять одно из ребер графа;

найти, где оно встречается в таблице;

сложить все скорости из таблицы для этого ребра.

Подсчет задержки для каждого графа по формуле Ti = 1/ (мCi-лi).

Подсчет стоимости каждого ребра по формуле: Wi = лi/?лi.

Подсчет общей задержки Toverall = ?Ti*Wi. Получаем: Toverall=162. 531msec.

Так как полученное значение слишком велико, то его можно уменьшить за счет замены пути с самой большой задержкой DF (Ti, max = 1000msec) на путь D->G->F.

Flooding (алгоритм «затопления»)

Является самым простым алгоритмом маршрутизации для распространения информации по сети. При получении пакета каждый узел пересылает его соседним узлам за исключением того, от которого пришёл пакет.

Рисунок 3.3Алгоритм «затопления»

Данный алгоритм обладает низкой эффективностью из-за повышенной загрузки сети.

Способы оптимизации:

Для улучшения эффективности алгоритма используются следующие способы:

Hopcounter

В этом случае к каждому пакету прибавляется счетчик хопов. Отправитель устанавливает этот счетчик и каждый узел сети, который его пересылает, уменьшает этот счетчик на 1.

FloodingwithAcknowledge («затопление с подтверждениями»)

Одной из проблем простого алгоритма «затопления» является то, что отправитель не знает о том, достиг ли пакет всех узлов сети. Каждый из узлов сети отправляет подтверждение о получении, если он получил подтверждение от всех узлов, которым он отправлял пакеты.

Рисунок 3.4Алгоритм «затопления» с подтверждениями

Uniqueresend

Каждая станция запоминает пересланные пакеты и не посылает их ещё раз. Данный метод оптимизации очень продуктивен в сетях с топологией, отличной от дерева.