Лекции по "Основы построения телекоммуникационных систем"

Лекция 15. Протоколы  маршрутизации 

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

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

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

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

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

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

Параметры и  классы протоколов маршрутизации

1. Оптимальность алгоритма. Она характеризует способность алгоритма маршрутизации выбирать "наилучший" маршрут. Наилучший маршрут зависит от показателей и от "веса" этих показателей, используемых при проведении расчета.
2. Низкие непроизводительные затраты. Алгоритмы маршрутизации разрабатываются как можно более простыми. То есть алгоритм маршрутизации должен эффективно обеспечивать свои функциональные возможности с минимальными затратами программного обеспечения.
3. Стабильность работы. Алгоритмы должны обладать устойчивостью в работе. Они должны четко функционировать в случае непредвиденных обстоятельств, таких как отказы аппаратуры, высокая нагрузка, ошибки реализации. Стабильность очень важна, поскольку маршрутизаторы являются узловыми точками взаимодействия сетей и их ошибки могут приводить к проблемам в рамках всей глобальной сети.
4. Быстрая сходимость алгоритма. Сходимость - это процесс соглашения между всеми роутерами по оптимальным маршрутам. Когда какое-нибудь событие в сети приводит к тому, что маршруты или отвергаются, или становятся доступными, роутеры рассылают сообщения об обновлении маршрутизации. Сообщения об обновлении маршрутизации пронизывают сети, стимулируя пересчет оптимальных маршрутов и, в конечном итоге, вынуждая все роутеры придти к соглашению по этим маршрутам. Алгоритмы маршрутизации, которые сходятся медленно, могут привести к образованию петель маршрутизации или выходам из строя сети.
5. Гибкость алгоритма. Алгоритмы маршрутизации должны быстро и точно адаптироваться к разнообразным обстоятельствам в сети. Например, предположим, что сегмент сети отвергнут. Многие алгоритмы маршрутиэации, после того как они узнают об этой проблеме, быстро выбирают следующий наилучший путь для всех маршрутов, которые обычно используют этот сегмент. Алгоритмы маршрутизации могут быть запрограммированы таким образом, чтобы они могли адаптироваться к изменениям полосы пропускания сети, размеров очереди к роутеру, величины задержки сети и других переменных.

Все алгоритмы маршрутизации  можно классифицировать как:

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

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

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

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

RIP

Алгоритм маршрутизации  протокола RIP (Routing Information Protocol) принадлежит к классу дистанционно-векторных алгоритмов (маршрутизация по вектору состояния). С 1988 года RIP был повсеместно принят производителями персональных компьютеров для использования в их изделиях передачи данных по сети. Алгоритм построен на обмене небольшими блоками информации из таблиц маршрутизации между соседними маршрутизаторами.

  Вектор расстояния представляет собой набор пар чисел, являющихся номерами сетей и расстояний до них.

Каждая запись в базе данных маршрутизации состоит из:

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

Рассмотрим сеть рис. 1

A (Новый)
A	0(-)
B	5(B)
C	6(C)
D	9(B)
E	11(B)
F	16(C)

 

 

B
A	6(A)
B	0(-)
C	12(E)
D	4(D)
E	6(E)
F	13(E)

C
A	4(A)
B	11(A)
C	0(-)
D	5(D)
E	6(E)
F	10(D)

   

                                                                                           

       

     

Рис. 1 Маршрутизация по вектору  расстояния

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

В примере сети, показанном на рисунке, для узлов В и С  требуется 10 и 12 единиц времени, чтобы  ответить и послать их текущие  векторы расстояния узлу А. Узел А  может сделать вывод, что для  путешествия пакета к узлам В и С требуется 5 и 6 единиц времени соответственно. Оценки 6 и 4  в таблицах узлов В и С игнорируются, поскольку оценки 5 и 6 считаются более свежими. После этого получение для узла А новой таблицы является относительно простой задачей.

Рассмотрим случай определения  маршрута от узла А к узлу D. Узел А оценивает, что если он направит пакет, предназначенный для D, прямо к узлу В, то потребуется 5(АВ) плюс 4 (С-D)= 9 единиц времени. Оценка для направления пакета через узел С дает 6(АС) плюс 5(С-D) =11, так что принимается первый выбор – направление через узел В. Процедура повторяется для всех других, несмежных узлов сети. Трафик между АЕ направляется через узел В с суммарным расстоянием 11 (5+6), а не через узел С с суммарным расстоянием12 (6+6). Наконец, пакеты, предназначенные для узла F, отправляются не через узел В (маршрут с расстоянием 18), а через более короткий путь, проходящий через узел С за 16 временных единиц.

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

Протокол состояния  связей OSPF

OSPF (Open Shortest Path First – «кратчайший путь первым») является иерархическим протоколом маршрутизации с объявлением состояния о канале соединения (link-state). Он был спроектирован как протокол работы внутри сетевой области - AS (Autonomous System), которая представляет собой группу маршрутизаторов и сетей, объединенных по иерархическому принципу и находящихся под единым управлением и совместно использующих общую стратегию маршрутизации. В качестве транспортного протокола для маршрутизации внутри AS OSPF использует IP-протокол.

Для различных типов IP-сервиса (видов услуг высшего уровня, которые  определяются значением поля TOS IP-пакета), OSPF может рассчитывать свои оптимальные  маршруты на основании параметров, наиболее критичных для данного  вида сервиса. Например, какая-нибудь прикладная программа может включить требование о том, что определенная информация является срочной. Если OSPF имеет в своем распоряжении каналы с высоким приоритетом, то они могут быть использованы для транспортировки срочных дейтаграмм. Маршрутизация по состоянию связей имеет значительные преимущества по сравнению по вектору расстояния.

Протокол OSPF вычисляет  маршруты в IP-сетях, сохраняя при этом другие протоколы обмена маршрутной информацией.

Непосредственно связанные (то есть достижимые без использования промежуточных маршрутизаторов) маршрутизаторы называются "соседями". Каждый маршрутизатор хранит информацию о том, в каком состоянии по его мнению находится сосед. Маршрутизатор полагается на соседние маршрутизаторы и передает им пакеты данных только в том случае, если он уверен, что они полностью работоспособны. Для выяснения состояния связей маршрутизаторы-соседи достаточно часто обмениваются короткими сообщениями HELLO.