Алгоритмы маршрутизации

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

Содержание


Классификация

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

  • адаптивные и неадаптивные
  • глобальные и децентрализованные
  • статические и динамические

Требования

  • точность
  • простота
  • надежность
  • стабильность
  • справедливость
  • оптимальность

Типы алгоритмов

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

Описание

принимают во внимание актуальное состояние линии

Плюсы и минусы

+возможность адаптации к актуальному состоянию сети
-необходимо постоянно пересчитывать таблицы маршрутизации

Централизированные

Описание

адаптивный централизированный алгоритм

Плюсы и минусы

+RCC обладает всей информацие о состоянии сети, что позволяет принимать оптимальные решения
+узлы освобождены от подсчета таблиц маршрутизации
-низкая надежность
-узлы получают таблицы маршрутизации в различное время
-концентрация траффика возле RCC

Изолированные

Описание

Узел получает информацию из полученных пакетов.

Плюсы и минусы

+нет перегрузок
-ограниченная адоптация к актуальному состоянию сети

Примеры

Backward learning а

Распределенные

Описание

дистанционно-векторный алгоритм,link state routing

Плюсы и минусы

+лучшая адаптация
-перегрузки

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

Описание

не принимают во внимание актуальное состояние сети, все маршруты рассчитываются до начала использования сети. Они в свою очередь подразделяются на алгоритмы, учитывающие топологию сети(spanning tree, flow based routing), а так же её не учитывающие(flooding).

Плюсы и минусы

+простота
+хорошие результаты при неизменной топологии и нагрузке
-невозможность реагирования на изменения
-низкая скорость в неоднородных сетях

Примеры

  • Shortest Path
  • Flow based
  • Flooding

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

Централизированный

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

(англ. adaptive centralized routing

Описание

В сети существует так называемый Routing Control Center(RCC), который получает информацию от всех узлов о их соседних узлах, актуальную длину очереди и загрузки линии. В функции RCC входит сбор информации, подсчет оптимальных маршрутов для каждого узла, составление таблиц маршрутизации и рассылка их узлам.

Плюсы и минусы

+RCC обладает всей информацией и может создавать "идеальные" маршруты
+узлы освобождены от необходимости рассчета таблиц маршрутизации
-низкая надежность
-время от времяни требуется перерасчет таблиц маршрутизации
-некорректная работа при разделенных сетях
-IS получают информации в различное время
-концентрация траффика возле RCC

Изолированный

Backward learning

Описание

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

Плюсы и минусы

+легкость имплементации
-проблемы при изменении топологии и нагрузки
-не происходит обмен данными о маршрутизации между узлами

Распределенный

Дистанционно-векторный алгоритм

(англ. distance vector routing

Описание

Также известен как Distributed Bellman Ford Routing или Ford Fulkerson Algorithm. Данный алгоритм является распределенным, итерационным и асинхронным. Его можно представить как: "расскажи своим соседям, как выглядит мир". Каждый узел ведет таблицу маршрутизации с одной записью для каждого маршрутизатора подсети. Таблица представляет собой вектор, содержащий 2 компонента: выбранную линию и дистанцию. Узел оценивает дистанцию(количество хопов, задержку или длину очереди) до каждого соседа и рассылает ее своим соседям, которые в свою очередь выполняют тоже самое. В результате полученной информации каждый узел заново подсчитывает таблицу маршрутизации. Применяется в протоколе маршрутизации RIP. Впервые был применен в ARPANET.

Алгоритм

Предположим, что таблица только что была получена от соседа X, причем Xi является предположением X о том, сколько длится путь до маршрутизатора i. Есле маршрутизатор знает, что передача данных до X длится m, то он знает так же, что он может достичь любой маршрутизатор i через X за Xi+m.

Плюсы и минусы

+самоорганизация
+относительно простая реализация
-плохая конвергенция
-сложности при расширении сети

Пример

При использовании алгоритма возникают проблемы при отключении одного из узлов от сети - Count to Infinity(счет до бесконечности)


Предотвращение: Split Horizon Algorithm - "не говори мне то, что я сказал тебе"

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

англ. Link state routing

Описание

Алгоритм, относящийся к адаптивным алгоритмам и основанный на состоянии линий. Его можно представить как: "расскажи миру о том, кто твои соседи". Сначала узел знает только своих соседей и стоимости линий, соединяющих его с ними. В процессе обмена информацией с соседними узлами узел получает информацию о топологии сети, при этом обменивается только информация о происшедших изменениях. В результате каждый узел знает всю топологию сети. Впервые был применен в ARPANET в 1979 году и пришел на смену дистанционно-векторному алгоритму. Причинами перехода служили:

  • рост пропускной способности каналов и отсутствие ее учета в дистанционно-векторном алгоритме
  • медленность дистанционно-векторного алгоритма, вызванная "счетом до бесконечности"

Алгоритм
  1. определение адресов соседних узлов: новые узлы рассылают приветствие(HELLO mesage), соседние узлы сообщают свои адреса

происходит при помощи рассылки HELLO-запросов

  1. измерение стоимости линий или времяни передачи данных до соседних узлов

происходит в результате рассылки эхо-сообщений

  1. организация собранных данных в пакет, содержащий личный адрес, sequence number(ля избежания повторений), age(для отброса старой информации), дистанцию
  2. рассылка пакетов всем узлам сети(flooding)
  3. подсчет маршрутов на основе полученной от других узлов информации

Плюсы и минусы

Пример

Широковещательна маршрутизация

(англ. broadcast routing

Терминология

уникаст - 1:1
мултикаст - 1:n
бродкаст - 1:всем

Простые методы

  • индивидуальная отправка пакетов каждому получателю, что предявляет определенные требования к сети, излишняя трата bandwith, отправитель должен знать всех полкчателей
  • flooding: слишком много повторяющихся пакетов

Multidestatination Routing

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

Многоадресная рассылка

англ. multicast routing

Алгоритм связующего дерева

англ. spanning tree 

Описание

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

Reverse path forwarding(Reverse path flooding)

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

Reverse path broadcast

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

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

Shortest Path Routing

Описание

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

Алгоритм

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

  1. узел A помечается как рассматриваемый
  2. присвоить всем непосредственно соседним узлам значение с дистанцией до рассматриваемого узла B(2,A), G(6,A) и добавить их в список кандидатов
  3. выбрать из списка кандидатов узел с наименьшей дистанцией B(2,A)
  4. пометить этот узел как рассматриваемый и добавить его в дерево
  5. перейти к пункту 2

Плюсы и минусы

+простота
+хорошие результаты при постоянной топологии сети и нагрузке

Flow-Based Routing

Описание

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

Алгоритм

Псевдокод

Плюсы и минусы

Пример

Данны граф для capacity и матрица траффика

  • Подсчет загрузки каждой линии
  1. взять одну из граней графа
  2. найти где она встречается в таблице
  3. сложить все скорости из таблицы для этой грани
Line λi (packts/sec)
AB 3(AB) + (7ABC) + 7(BAD) + 4(BAF) + 3(BADG) =24
AD 4(AD) + 2(ADE) + 2(ADG) + 5(ADEH) + 7(BAD) + 3(BADG) = 23
AF 5(AF) + 4(BAF) = 9
BC 7(ABC) + 3(BC) + 4(BCH) = 14
BE 3(BE) = 3
CE 7(CED) + 5(CE) + 3(CEDF) = 15
CH 4(BCH) + 5(CHG) + 3(CH) = 12
DE 2(ADE) + 5(ADEH) + 7(CED) + 3(CEDF) + 2(DE)+ 9(DEH) + 3(EDF)+ 9(FDEH) = 40
DF 3(CEDF)+ 9(DF) + 3(EDF)+ 9(FDEH) = 24
EH 5(ADEH)+ 9(DEH)+ 1(EHG)+ 2(EH) + 9(FDEH) = 26
FG 1(FG) = 1
GH 1(GH) + 1(EHG) + 5(CHG) = 7
DG 2(ADG) + 3(BADG) + 2(DG) = 7
  • подсчет задержки для каждого графа по формуле Ti = 1/(μCii).
Line λi (packts/sec) μCi (packts/sec) Ti (msec)
AB 24 50 38.46
AD 23 50 37.04
AF 9 37.5 35.09
BC 14 25 90.91
BE 3 50 21.28
CE 15 75 16.67
CH 12 50 26.32
DE 40 50 100
DF 24 25 1000
EH 26 50 41.67
FG 1 100 10.1
GH 7 62.5 18.02
DG 7 62.5 18.02
  • Подсчет стоимости каждой грани по формуле: Wi = λi/∑λi.
Line λi (packts/sec) μCi (packts/sec) Ti (msec) Wi
AB 24 50 38.46 0.117
AD 23 50 37.04 0.112
AF 9 37.5 35.09 0.044
BC 14 25 90.91 0.068
BE 3 50 21.28 0.015
CE 15 75 16.67 0.073
CH 12 50 26.32 0.059
DE 40 50 100 0.195
DF 24 25 1000 0.117
EH 26 50 41.67 0.127
FG 1 100 10.1 0.005
GH 7 62.5 18.02 0.034
DG 7 62.5 18.02 0.034
  • подсчет общей задержки Toverall = ∑Ti•Wi Получаем: Toverall=162.531msec.

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

Flooding

Описание

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

Эффективность

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

Пример

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

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

Hop counter

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

Flooding with Acknowledge

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

Unique resend

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

Другие алгоритмы

Multipath Routing

Описание

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

Алгоритм

Псевдокод

Плюсы и минусы

Примеры

Иерархическая маршрутизация

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

Routing with Mobility

Литература

Andrew S. Tanenbaum COMPUTER NETWORKS. — 2002.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home