№76 Маршрутизация. Требования, классификация, алгоритмы, протоколы маршрутизации

Маршрутизация

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

1. Общие описание

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

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

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

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

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

Сетевой адрес получателя

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

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

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

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

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

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

Пропускная способность канала связи;

Прогнозируемое суммарное время пересылки;

Стоимость канала связи.

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

Считывает из заголовка пакета, соответствующий сетевому уровню модели OSI, адрес назначения, т.е. сетевой адрес получателя;

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

Заменяет в заголовке пакета, соответствующий канальному уровню модели OSI, свой МАС- адрес на МАС- адрес выбранного транзитного маршрутизатора;

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

 По мере того, как пакет передвигается через сеть, физический адрес (МАС- адрес) его получателя меняется, но логический адрес пункта назначения, соответствующий сетевому уровню модели OSI, остается без изменений.

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

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

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

По оптимизации определенных маршрутов – способности определять наилучший маршрут в зависимости от заданных показателей и их весовых коэффициентов;

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

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

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

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

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

3. Классификация алгоритмов и протоколов маршрутизации

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

Степень динамичности, отражающая наличие или отсутствие гибкости и сходимости;

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

Способ организации маршрутов;

Область влияния;

Способ получения маршрутной информации.

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

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

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

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

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

 По области влияния алгоритмы маршрутизации могут быть внутредоменными и междоменными.

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

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

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

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

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

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

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

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

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

Требования

• точность

• простота

• надёжность

• стабильность

• справедливость

• оптимальность

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

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

Описание

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

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

+возможность динамической адаптации к состоянию сети

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

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

Описание

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

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

+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, то он знает так же, что он может достичь любой маршрутизатор і через X за Xi+m.

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

+самоорганизация

+относительно простая реализация

-плохая конвергенция («сходимость»)

-сложности при расширении сети

Пример

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

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

Маршрутизация по состоянию канала

англ. Link state routing

Описание

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

• рост пропускной способности каналов и отсутствие её учета в дистанционно-векторном алгоритме

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

Алгоритм

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

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

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

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

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

4. рассылка пакетов всем узлам сети (flooding)

5. подсчет маршрутов на основе полученной от других узлов информации

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

(англ. broadcast routing) 

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

unicast — 1:1

multicast — 1:n

broadcast — 1:всем

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

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

• flooding: слишком много повторяющихся пакетов

Multidestination 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

Описание

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

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

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

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

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

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

• Протоколы состояния каналов связи, основаны на Link State Algorithm (LSA).

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

• Междоменной маршрутизации;

• Внутридоменной маршрутизации.

Дистанционно-векторные протоколы

• RIP — Routing Information Protocol;

• IGRP — Interior Gateway Routing Protocol (лицензированный протокол Cisco Systems);

• BGP — Border GateWay Protocol;

• EIGRP — Enhanced Interior Gateway Routing Protocol (на самом деле он гибридный — объединяет свойства дистанционно-векторных протоколов и протоколов по состоянию канала; лицензированный протокол Cisco Systems);

• AODV

Протоколы состояния каналов связи

• IS-IS — Intermediate System to Intermediate System (стек OSI);

• OSPF — Open Shortest Path First;

• NLSP — NetWare Link-Services Protocol (стек Novell);

• HSRP и CARP — протоколы резервирования шлюза в Ethernet-сетях.

• OLSR

• TBRPF

Протоколы междоменной маршрутизации

• EGP;

• BGP;

• IDRP;

• IS-IS level 3;

Протоколы внутридоменной маршрутизации

• RIP;

• IS-IS level 1-2;

• OSPF;

• IGRP;

• EIGRP.