Протоколы и алгоритмы маршрутизации. Типы алгоритмов

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

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

Рассмотрим некоторые классификационные признаки алгоритмов маршрутизации, которые отражают их свойства и особенности.

По степени обновляемости маршрутов выделяют:

• статические алгоритмы маршрутизации, основанные на ручном составлении таблиц маршрутизации администратором сети до начала маршрутизации. Заданные маршруты сохраняются до тех пор, пока администратор сети не изменит их. Алгоритмы применяются только в небольших сетях с простой топологией связей;
• динамические или адаптивные алгоритмы, в которых таблицы маршрутизации, а следовательно, и сами маршруты постоянно обновляются в соответствии с меняющейся топологией сети.

По количеству используемых маршрутов различают:

• одномаршрутные алгоритмы, обеспечивающие передачу пакетов по одному и тому же маршруту;
• многомаршрутные алгоритмы, в которых каждому из возможных маршрутов в зависимости от его пропускной способности и других показателей назначается приоритет. Пакет пересылается по маршруту, обладающему наивысшим приоритетом. Этот маршрут обычно является основным, а остальные – резервными. Многомаршрутные алгоритмы делают возможной мультиплексную передачу трафика по многочисленным линиям.

Классификационным признаком алгоритмов может служить используемая структура маршрутизации, при этом:

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

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

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

По способу обмена информацией о маршрутах различают:

• дистанционно-векторные алгоритмы или алгоритмы Бэлмана – Форда, которые обеспечивают пересылку всей или части маршрутной таблицы маршрутизатора своим ближайшим соседям;
• алгоритмы состояния канала, направляющие только ту часть маршрутной таблицы, которая описывает состояние собственных каналов маршрутизатора во все узлы объединенной сети. Их также называют алгоритмами первоочередности наикратчайшего маршрута. Отличительная особенность алгоритмов – более быстрая сходимость, меньшая склонность к образованию петель маршрутизации по отношению к дистанционно-векторным. Однако алгоритмы состояния канала характеризуются более сложными расчетами, требуя большей процессорной мощности и памяти.

Сведения о протоколах маршрутизации

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

Помазков Виталий Викторович

Описание

Маршрутизация - это действие перемещения информации по межсетевой сети из источника в маршрутизатор назначения (узел). Маршрутизация обычно выполняется с помощью специального устройства, называемого маршрутизатор. Маршрутизация является ключевой особенностью Интернета (беспроводной сети), поскольку она позволяет передавать сообщения с одного компьютера к другому и, в конечном итоге, достигнет целевой машины. Каждый промежуточный компьютер выполняет маршрутизацию, передавая сообщение на следующий компьютер. Часть этого процесса включает в себя анализ таблицы маршрутизации для определения наилучшего пути. Маршрутизация часто путается с мостом, который выполняет аналогичное ограничение. Основное различие между маршрутизацией и мостом является то, что мосты происходят на уровне 2 (канальный уровень), в то время как маршрутизация происходит на уровне 3 (сетевой уровень) эталонной модели OSI. Другая разница в том, что перемычка происходит на более низком уровне и, следовательно, является скорее аппаратным, тогда как маршрутизация происходит на более высоком уровне, где программный компонент более важен. Маршрутизация включает в себя два основных вида деятельности:

1. Определение оптимальных путей

2. Транспортировка информационных групп (обычно называемых пакетами) через межсетевую сеть. Роутеры рассматриваются как специализированные компьютеры, которые отправляют наши сообщения и тем, что каждый другой пользователь Интернета ускоряет их назначения вдоль тысяч пути. Маршрутизатор - это единственное устройство, которое видит каждое сообщение, отправленное любым компьютером на любой из компьютеров сетей. Таблица конфигурации представляет собой набор информации, в том числе:

1. Информацию о том, какие соединения приводят к определенным группам адресов.

2. Приоритеты для соединений, которые будут использоваться.

3. Правила обработки как обычных, так и особых случаев трафика. Две важные задачи маршрутизаторов:

1. Маршрутизатор гарантирует, что информация не идет туда, где она не нужна.

2. Маршрутизатор гарантирует, что информация дойдет до предполагаемого адресата.

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

· Неадаптивные алгоритмы маршрутизации

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

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

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

1. Статический и динамический

2. Одноканальный и многоканальный

3. Плоский и иерархический

4. Централизованный и распределенный

5. Host-Intelligent and Router-intelligent

6. Внутри доменный и меж доменный

7. Link-State или Distance-vector

Примерами алгоритмов маршрутизации на расстоянии являются:

· Протокол маршрутизации информации (RIP)

· Протокол маршрутизации внутренних шлюзов (IGRP)

· расширенный протокол маршрутизации внутренних шлюзов (EIGRP)

Примерами алгоритма маршрутизации состояния канала являются:

· Сначала открыть самый короткий путь (OSPF)

· Промежуточная система (IS-IS).

Список литературы :

1. Yashpaul Singh, M.K. Soni, and A.Swamp, «Simulation study of Multipath Routing Algorithm in different situations», IJCSNS International Journal of computer science and network security,Vol.7,No.ll,pp.295-297,2007

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

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

Требования

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

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

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

Описание

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

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

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

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

Описание

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

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

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

Описание

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

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

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

Примеры

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

Описание

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

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

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

Описание

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

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

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

Примеры

• Shortest Path
• Flow based
• Flooding

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

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

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

Описание

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

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

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

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

Backward learning

Описание

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

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

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

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

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

Описание

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

Алгоритм

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

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

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

Пример

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

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

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

Описание

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

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

Алгоритм

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

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

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

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

Пример

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

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

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

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

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

Multidestatination Routing

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

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

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

Описание

Связующее дерево(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

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

Line	λ i (packts/sec)	μC i (packts/sec)	T i (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

• Подсчет стоимости каждой грани по формуле: W i = λ i /∑λ i .

Line	λ i (packts/sec)	μC i (packts/sec)	T i (msec)	W i
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

• подсчет общей задержки T overall = ∑T i W i Получаем: T overall =162.531msec .

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

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

Flooding with Acknowledge

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

Unique resend

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

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

Multipath Routing

Описание

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

Таблица маршрутизации

Маршрутизация. Задача маршрутизации

Маршрутизация пакетов включает в себя две основные задачи:

Определение оптимального маршрута пересылки пакета по составной сети;

Собственно пересылка пакета по сети.

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

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

Информация, ставящая в соответствие конечному адресу на­значения пакета адрес маршрутизатора, на который нужно даль­ше отправить пакет для достижения адреса назначения, хранится в специальной таблице маршрутов, которая размещается на маршрутизаторе.

Таблица маршрутизации, создаваемая по умолчанию на компьютере с Windows Server 2003 (одна сетевая карта, IP-адрес: 192.168.1.1, маска подсети: 255.255.255.0), имеет следующий вид:

В приведенной таблице имеются следующие поля:

Network Destination (адрес назначения) – адрес хоста или подсети, для которых задан маршрут в таблице;

Netmask (маска подсети) – маска подсети для адреса назначения;

Gateway (шлюз – другое название маршрутизатора) – адрес для передачи пакета;

Interface (интерфейс) – адрес собственного порта маршрутизатора (сетевой карты), на который следует передать пакет. Любой маршрутизатор содержит не менее двух портов. В компьютере в роли маршрутизатора с Windows Server 2003 портами являются сетевые карты;

Metric (метрика) – число маршрутизаторов (число хопов), которые необходимо пройти для достижения хоста назначения. Для двух маршрутов с одинаковыми адресами назначения выбирается маршрут с наименьшей метрикой. Значение 20 в таблице соответствует 100-мегабитной сети Ethernet.

Кратко опишем записи в таблице по умолчанию.

0.0.0.0 – маршрут по умолчанию (default route). Эта запись выбирается в случае отсутствия совпадений с адресом назначения. В приведенной таблице маршруту по умолчанию соответствует шлюз 192.168.1.2 – это адрес порта маршрутизатора, который связывает данную подсеть с другими подсетями;

127.0.0.0 – маршрут обратной связи (loopback address), все пакеты с адресом, начинающимся на 127, возвращаются на узел-источник;

192.168.1.0 – адрес собственной подсети узла;

192.168.1.1 – собственный адрес узла (совпадает с маршрутом обратной связи);

192.168.1.255 – адрес широковещательной рассылки (пакет с таким адресом попадает всем узлам данной подсети);

224.0.0.0 – маршрут для групповых адресов;

255.255.255.255 – адрес ограниченной широковещательной

Алгоритмы маршрутизации могут различаться по нескольким характеристикам:

По задачам, решаемым алгоритмом;

По принципу сбора и представления информации о сети;

По методу расчета оптимального маршрута.

Кроме того, алгоритмы маршрутизации должны максимально удовлетворять следующим требованиям:

Выбираемый маршрут должен быть наиболее оптимальным;

Реализация алгоритма должна быть простой, а его функцио­нирование не требовательным к вычислительным мощностям;

Алгоритм должен обладать высокой отказоустойчивостью;

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

Таким образом, алгоритмы маршрутизации можно классифи­цировать следующим образом:

По актуальности используемых маршрутов:

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

По принципу обмена маршрутной информацией:

состояния канала; дистанционно-векторные.

По количеству определенных маршрутов:

одномаршрутные; многомаршрутные;

По используемой структуре маршрутизации:

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

По отношению к домену:

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

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

В динамических или адаптивных алгоритмах таблицы мар­шрутизации, и соответственно, сами маршруты постоянно обнов­ляются в соответствии с меняющейся топологией сети.

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

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

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

Алгоритмы маршрутизации пытаются разработать таким образом, что­бы обеспечить самый короткий путь с минимальным временем доставки и наиболее полным использованием пропускной способности сети. Однако на эффективность работы алгоритма могут влиять также следующие ситуации: передача пакета в направлении, не обеспечивающем минимальное время доставки из-за перегрузки какого-то узла (перегрузка сети может происхо­дить из-за большого объема служебной информации, которая используется алгоритмом маршрутизации). Неоперативный учет изменения состояния сети, который обусловлен как отказами некоторых узлов и каналов, так и появлением новых узлов в связи с развитием сети. Для эффективной работы алгоритма необходимо каждый маршрутизатор снабжать информацией о текущей топологии сети, пропускной способности каналов. Любой маршру­тизатор работает в режиме неопределенности и пульсирующей нагрузки.

Таким образом, при разработке алгоритмов маршрутизации преследуются следующие цели:

Оптимальность – способность алгоритмов маршру­тизации выбирать «наилучший» маршрут;

Простота и низкие, непроизводительные затраты. Алгоритмы маршру­тизации должны выполнять свои функциональные возможности с минимальными затратами программного обеспечения;

Живучесть и стабильность – надежность функционирования в случае отказов аппаратуры;

Быстрая сходимость – обеспечение быстрого процесса соглашения между маршрутизаторами при обновлении маршрута

Гибкость – умение быстро адаптироваться к изменению полосы, размером очереди.

На рис. 4.7 приведена классификация алгоритмов маршрутизации.

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

Рисунок 4.7

При маршрутизации по предыдущему опыту используется информация, которая накапливается в каждом маршрутизаторе (узле коммутации). Каж­дый пакет снабжен счетчиком, который определяет количество узлов, кото­рое он прошел. Накапливание этих данных позволяет создать таблицу, с помощью которой выбирается соответствующий маршрут. Этот алгоритм позволяет приспособиться к изменению топологии сети, но с большой за­держкой. При фиксированной маршрутизации алгоритм работает на основе анализа таблицы маршрутов, которая, как правило, создается сетевым ад­министратором, причем возможно составление таких таблиц с использова­нием альтернативных путей доставки информации к точке назначения. На­личие альтернативных путей позволяет повысить надежность сети при от­казе какого-либо из путей. Естественно, что статическая маршрутизация не позволяет учитывать изменяющуюся нагрузку сети, что приводит к повы­шению времени доставки пакета, если он попадает в перегруженный узел. Динамическая маршрутизация учитывает изменение топологии и состава сети. В этом случае каждый маршрутизатор получает информацию об из­менении топологии и изменении нагрузки в сети. При локальной маршру­тизации используется информация о состоянии не всей сети, а только опре­деленного конечного числа узлов, информация других узлов не учитывает­ся. Распределенная маршрутизация учитывает информацию, которая посту­пает из соседних узлов. Централизованная маршрутизация учитывает ин­формацию, поступающую из главного узла, причем каждый маршрутизатор передает информацию о своем состоянии в центральный узел, который ана­лизирует ее и передает каждому узлу в виде измененной таблицы маршрутизации. Гибридная маршрутизация предполагает использование как цен­трализованной, так и распределенной маршрутизации, чтобы не перегру­жать сеть служебной информацией.