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

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

Требования

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

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

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

Описание

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

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

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

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

Описание

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

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

Описание

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

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

1 Оптимальность. Она характеризует способность алгоритма маршрутизации выбирать «наилучший» маршрут.

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

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

4 Быстрая сходимость. Сходимость - это процесс соглашения между всеми маршрутизаторами по оптимальным маршрутам.

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

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

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

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

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

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

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

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

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

4 С интеллектом в главной вычислительной машине или в маршрутизаторе.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Все алгоритмы маршрутизации классифицируются по следующим признакам:

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

Одношаговые алгоритмы в зависимости от способа формирования таблиц маршрутизации делятся на три класса:

Алгоритмы фиксированной (статической) маршрутизации.

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

Алгоритмы простой маршрутизации.

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

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

лавинная маршрутизация , когда пакет широковещательно посылается по всем возможным направлениям, кроме исходного;

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

Алгоритмы адаптивной (динамической) маршрутизации.

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

дистанционно-векторные (Distance Vector Algorithm , DVA ) ;

алгоритмы состояния связей (Link State Algorithm , LSA ) ;

Алгоритмы состояния связей направляют потоки маршрутной информации во все узлы сети. Однако каждый маршрутизатор посылает только ту часть маршрутной таблицы, которая описывает состояние его собственных связей. «Широковещательная» рассылка (передача пакета всем непосредственным соседям маршрутизатора) используется здесь только при изменениях состояния связей, что происходит не так часто. Вершинами графа являются как маршрутизаторы, так и объединяемые ими сети. Распространяемая по сети информация состоит из описания связей различных типов: маршрутизатор – маршрутизатор, маршрутизатор – сеть.

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

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

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

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

Лекция

Тема: Принципы объединения сетей на основе протоколов сетевого уровня.

Цель .

1. Обучающая. Ввести основные понятия. Освоить методы разработки и способы представления элементов сети.

2. Развивающая. Р азвивать логику, умение анализировать, сравнивать, делать выводы, высказывать свою мысль. Развивать внимание и аналитическое мышление.

3. Воспитательная . Воспитывать интерес к языкам программирования, научным достижениям и открытиям. Воспитывать аккуратность, внимательность и дисциплинированность. Формирование самостоятельности и ответственности при повторении пройденного и изучении нового материала. Воспитывать чувство ответственности за напарника при работе в группе.

Межпредметные связи:

· Обеспечивающие: информатика.

· Обеспечиваемые: базы данных.

Методическое обеспечение и оборудование:

1. Методическая разработка к занятию.

2. Рабочая программа.

3. Инструктаж по технике безопасности.

Технические средства обучения: проэктор, компьютер.

Обеспечение рабочих мест:

· Рабочие тетради.

Ход лекции.

Организационный этап.

Анализ и проверка домашнего задания.

Фронтальный опрос по вопросам.

Решите задачи.

Объединение сетей на основе протоколов сетевого уровня

Для объединения нескольких сетей в единую систему, способную передавать данные между любыми узлами объединенной сети, служит сетевой уровень.

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

Компонентами составной сети могут являться как локальные, так и глобальные сети.

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

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

В функции сетевого уровня входит:

−передача пакетов между конечными узлами в составных сетях;

−выбор маршрута передачи пакетов, наилучшего по некоторому критерию;

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

На сетевом уровне необходима собственная система адресации, не зависящая от способов адресации узлов в отдельных подсетях.

Сетевой адрес формируется как пара: номер сети (подсети) и номера узла.

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

Принципы маршрутизации

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

Рассмотрим принципы маршрутизации на примере составной сети, изображенной на рис.1.

Маршрутизаторы имеют по несколько портов (не менее двух), к которым присоединяются сети. Каждый порт маршрутизатора можно рассматривать как отдельный узел сети: он имеет собственный сетевой адрес и собственный локальный адрес в той подсети, которая к нему подключена. Например, маршрутизатор номер 1 имеет три порта:

S1, S2, S3 – сети, подключенные к портам;

М1(1), М1(2), М1(3) – сетевые адреса этих портов;

Порт М1(1) имеет локальный адрес в сети S1;

Порт М1(2) имеет локальный адрес в сети S2;

Порт М1(3) имеет локальный адрес в сети S3;

S1, S2, … S5 – номера сетей, соединенных маршрутизаторами.

Рис. 1. Принцип маршрутизация в составной сети

Маршрутизатор можно рассматривать как совокупность нескольких узлов, каждый из которых входит в свою сеть. Как единое устройство маршрутизатор не имеет отдельного сетевого или локального адреса.

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

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

Табл.1 иллюстрирует пример таблицы маршрутизации для маршрутизатора 4.

Табл. 1. Таблица маршрутизации маршрутизатора 4.

Описание таблицы маршрутизации по столбцам слева направо:

Номер сети назначения;

Сетевой адрес следующего маршрутизатора (то есть адрес соответствующего порта следующего маршрутизатора), на который следует направить пакет, чтобы тот передавался по направлению к сети с данным номером по рациональному маршруту;

Сетевой адрес выходного порта – на какой из собственных портов маршрутизатор должен направить пакет;

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

Под расстоянием понимается значение, определенное при некоторой метрике и используемое в соответствии с заданным в сетевом пакете критерием. Этот критерий иногда называют классом сервиса. Расстояние может измеряться хопами (скачками), временем прохождения пакета по линиям связи, характеристикой надежности связи на данном маршруте и т. п.

Если марщрутизатор поддерживает несколько классов сервиса пакетов, то таблица маршрутов составляется и применяется отдельно для каждого вида сервиса (критерия).

Если таблица маршрутизации в случае крупной сети имеет слишком большой объем, то для сокращения числа записей в таблице используют специальную запись «маршрутизатор по умолчанию» (default). Маршрутизаторы в этом случае хранят строки для соседних сетей. Обо всех остальных сетях в таблице делают одну запись, указывающую на маршрутизатор, через который пролегает путь ко всем остальным сетям. В нашем примере таким маршрутизатором для четвертого маршрутизатора является маршрутизатор 5 (порт М5(1)).То есть путь ко всем остальным сетям большой сети проходит через этот порт маршрутизатора.

Таблица маршрутизации строят также и для конечных узлов. Особенности таблиц маршрутизации на конечных узлах:

− они аналогичны по структуре таблицам, хранящимся в маршрутизаторах;

− используются для оределения того, направляется ли пакет в другую сеть или он адресован какому-либо узлу данной сети;

− эти таблицы маршрутизации чаще строятся вручную.

Табл. 2 содержит пример таблицы маршрутизации для узла А.

Табл2. Таблица маршрутизации конечного узла А.

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

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

Алгоритмы маршрутизации включают процедуры:

− измерение и оценивание параметров сети;

− построение таблиц маршрутизации;

− реализация принятых маршрутных решений.

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

Объединение подсетей для создания более сложной (неоднородной) сети можно осуществлять и средствами канального уровня. Для этого могут быть использованы некоторые типы мостов и коммутаторов. Однако применение средств канального уровня для создания сложных сетей имеет существенные ограничения и недостатки. В табл. 3. проводится сравнение маршрутизаторов и коммутаторов (мостов) с точки зрения их применения для объединения подсетей.

Табл 3. Сравнение маршрутизаторов и коммутаторов (мостов).

Коммутаторы	Маршрутизаторы
Локальные таблицы соответствия IP – адресов МАС – адресам (физическим).	Таблицы маршрутизации с номерами сетей.
Построение таблиц путем пассивного просмотра проходящих кадров.	Обмен служебными пакетами с данными о сетях и маршрутизаторах.
Учитывается только топология сети.	Учет не только топологии, но и пропускной способности и состояния маршрутизаторов.
Простое определение нужного порта по таблице (скорость).	Реализация сложных алгоритмов маршрутизации.
Подвержены широковещательному шторму, проблема с управлением трафиком.	Нет широковещательного шторма, быстрее адаптируются к изменению конфигурации сети, допускают наличие замкнутых контуров в сети.

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

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

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

Одношаговые алгоритмы, в зависимости от способа формирования таблиц маршрутизации делятся на три класса:

§ алгоритмы фиксированной (статической) маршрутизации;

§ алгоритмы простой маршрутизации;

§ алгоритмы адаптивной (динамической) маршрутизации.

Алгоритмы фиксированной маршрутизации :

§ все записи в таблице маршрутизации являются статическими;

§ таблица обычно создается при загрузке и используется без изменений, пока ее не отредактируют вручную (если, например, отказал какой-нибудь маршрутизатор);

§ виды таблиц

− одномаршрутные таблицы, в которых для каждого адресата задан один путь;

− многомаршрутные таблицы, определяющие альтернативные пути для каждого адресата. Должно быть задано правило выбора одного из маршрутов;

§ приемлем в небольших сетях с простой топологией или для работы на магистралях крупных сетей (с простой структурой).

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

− случайная маршрутизация, когда прибывший пакет посылается в случайном направлении, кроме исходного;

− лавинная маршрутизация, когда пакет широковещательно посылается по всем возможным направлениям, кроме исходного;

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

Алгоритмы адаптивной (динамической) являются самыми распространенными и обладают следующими свойствами:

− автоматическое обновление таблиц маршрутизации после изменения конфигурации сети;

− обычно задается интервал времени, в течение которого данный маршрут будет оставаться действительным. Это время называется временем жизни маршрута;

− сбор топологической информации распределен между всеми маршрутизаторами, хотя наметилась тенденция использования сервера маршрутов – протокол NHRP.

− обеспечение достаточно рационального маршрута;

− простые алгоритмы без использования большого объема сетевых ресурсов;

− обладание свойством сходимости – получение однозначного результата за приемлемое время.

Два типа алгоритмов адаптивной маршрутизации:

− дистанционно – векторные алгоритмы;

− алгоритмы состояния связей.

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

Недостатки дистанционно – векторных алгоритмов:

− хорошо работают только в небольших сетях, в больших сетях генерируют интенсивный широковещательный трафик;

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

Наиболее распространенным протоколом, основанным на дистанционно – векторномалгоритме, являетсяRIP (Routing Internet Protocol).

Алгоритмы состояния связей обеспечивают маршрутизатор информацией, достаточной для построения точного графа связей сети. Все маршрутизаторы работают с одинаковыми графами. Вершинами графа являются как маршрутизаторы, так и объединяемые ими сети, Имеется широковещательный трафик, но только при изменении состояния связей и пакетами меньшего объема, чем для алгоритма RIP. В надежных сетях связи изменяются не часто.Одним из протоколов, основанным на алгоритме состояния связей является протокол OSPF (Open Shortest Path First) стека TCP/IP.

Функции маршрутизатора

Функции маршрутизатора могут быть разбиты на 3 группы в соответствии с уровнями модели OSI (рис. 5.3, с. 358).

Уровень интерфейсов

На нижнем уровне маршрутизатор обеспечивает физические интерфейсы для подсоединения локальных и глобальных сетей. Каждый интерфейс (порт) для подключения локальной сети соответствует определенному протоколу канального уровня (FDDI, Ethernet, Token Ring). Интерфейс с глобальной сетью обычно определяет только некоторый стандарт физического уровня, над которым в маршрутизаторе могут работать различные протоколы канального уровня. Например, с интерфейсом V.35 могут работать протоколы: LAP-B (X.25), LAP-F (frame relay), LAP-D(ISDN).

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

©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-10-25