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

Материал из Википедии — свободной энциклопедии

Это незавершённая статья о компьютерных сетях. Вы можете помочь проекту, исправив и дополнив её.

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

[править] Классификация

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

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

[править] Требования

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

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

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

[править] Описание

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

[править] Плюсы и минусы

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

[править] Централизированные

[править] Описание

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

[править] Плюсы и минусы

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

[править] Изолированные

[править] Описание

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

[править] Плюсы и минусы

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

[править] Распределенные

[править] Описание

дистанционно-векторный алгоритм, 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 за X_i+m.

[править] Плюсы и минусы

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

[править] Пример

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

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

[править] Алгоритм состояния канала

англ. Link state routing

[править] Описание

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

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

[править] Алгоритм

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

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

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

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

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

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

(англ. broadcast routing) 

[править] Терминология

unicast — 1:1
multicast — 1:n
broadcast — 1:всем

[править] Простые методы

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

[править] Multidestatination Routing

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

[править] Многоадресная рассылка

англ. multicast routing

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

англ. spanning tree 

[править] Описание

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

[править] Reverse path forwarding (Reverse path flooding)

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

[править] 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. сложить все скорости из таблицы для этого ребра

• подсчет задержки для каждого графа по формуле T_i = 1/(μC_i-λ_i).

• Подсчет стоимости каждого ребра по формуле: W_i = λ_i/∑λ_i.

• подсчет общей задержки T_overall = ∑T_i•W_i Получаем: T_overall=162.531msec.

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

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

[править] Описание

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

Алгоритм «затопления»

[править] Эффективность

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

[править] Способы оптимизации

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

[править] Hop counter

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

[править] Flooding with Acknowledge («затопление с подтверждениями»)

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

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

[править] Unique resend

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

[править] Другие алгоритмы

[править] Multipath Routing

[править] Описание

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

[править] Иерархическая маршрутизация

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

[править] Литература

Andrew S. Tanenbaum COMPUTER NETWORKS. — 2002.

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