Типы записей в таблице маршрутизации

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

1. Маршрут к сети.

Такой маршрут ведет к сети, входящей в объединенную сеть и имеющей указанный код (идентификатор).

2. Маршрут к узлу.

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

3. Маршрут по умолчанию.

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

Структура таблицы маршрутизации

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

1. Код сети.

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

1. Адрес пересылки.

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

1. Интерфейс.

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

1. Метрика

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

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

Общие сведения

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

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

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

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

Примерами внешних протоколов могут служить следующие.

EGP(Exterior Gateway Protocol) предназначен для анонсирования сетей, которые доступны для автономных систем за пределами данной автономной системы. По данному протоколу шлюз одной AS передает шлюзу другой AS информацию о сетях из которых состоит его AS. EGP не используется для оптимизации маршрутов. Считается, что этим должны заниматься протоколы внутренней маршрутизации.

BGP(Border Gateway Protocol) – это другой протокол внешней маршрутизации, который появился позже EGP. В своих сообщениях он уже позволяет указать различные веса для маршрутов, и, таким образом, способствовать выбору наилучшего маршрута. Однако, назначение этих весов не определяется какими-то независимыми факторами типа времени доступа к ресурсу или числом шлюзов на пути к ресурсу. Предпочтения устанавливаются администратором и потому иногда такую маршрутизацию называют политической маршрутизацией, подразумевая, что она отражает техническую политику администрации данной автономной системы при доступе из других автономных систем к ее информационным ресурсам. Протокол BGP используют практически все российские крупные IP -провайдеры, например крупные узлы сети Relcom.

К внутренним протоколам относятся протоколы RIP, HELLO, ISIS (Intermediate System to Intermediate System), SPF(Shortest Path First) и OSPF.

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

В основу алгоритма маршрутизации по протоколу RIP положена простая идея: чем больше шлюзов надо пройти пакету, тем больше времени требуется для прохождения маршрута. При обмене сообщениями маршрутизаторы сообщают в сеть IP -номер сети и число "прыжков" (hops), которое надо совершить, пользуясь данным маршрутом. Надо сразу заметить, что такой алгоритм справедлив только для сетей, которые имеют одинаковую скорость передачи по любому сегменту сети. Часто в реальной жизни оказывается, что гораздо выгоднее воспользоваться оптоволокном с тремя шлюзами, чем одним медленным коммутируемым телефонным каналом.

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

К сожалению, многовариантную маршрутизацию поддерживает не очень много систем. Различные клоны Unix и NT, главным образом ориентированы на протокол RIP. Достаточно посмотреть на программное обеспечение динамической маршрутизации, чтобы убедится в этом. Программа “routed” поддерживает только RIP, программа “gated” поддерживает RIP, HELLO, OSPF, EGP и BGP, в Windows NT поддерживается только RIP.

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

Этот протокол маршрутизации, предназначенный для сравнительно небольших и относительно однородных сетей, реализует алгоритм Беллмана-Форда. Протокол разработан в университете Калифорнии (Беркли), базируется на разработках фирмы Xerox и реализует те же принципы, что и программа маршрутизации “routed”, используемая в ОC UNIX (4BSD). Маршрут здесь характеризуется вектором расстояния до места назначения. Предполагается, что каждый маршрутизатор является отправной точкой нескольких маршрутов до сетей, с которыми он связан. Описание этих маршрутов хранится в специальной таблице, называемой маршрутной. Таблица маршрутизации RIP содержит по записи на каждую обслуживаемую машину (на каждый маршрут). Запись должна включать в себя:

IP -адрес места назначения. Метрика маршрута (от 1 до 15 – число шагов до места назначения). IP -адрес ближайшего маршрутизатора по пути к месту назначения. Таймеры маршрута.

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

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

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

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

Протокол OSPF (алгоритм предложен Дейкстрой) является альтернативой RIP в качестве внутреннего протокола маршрутизации. OSPF представляет собой протокол состояния маршрута (в качестве метрики используется - коэффициент качества обслуживания). Каждый маршрутизатор обладает полной информацией о состоянии всех интерфейсов всех маршрутизаторов (переключателей) автономной системы. Протокол OSPF реализован в демоне маршрутизации “gated”, который поддерживает также RIP и внешний протокол маршрутизации BGP.

Автономная система может быть разделена на несколько областей, куда могут входить как отдельные ЭВМ, так и целые сети. В этом случае внутренние маршрутизаторы области могут и не иметь информации о топологии остальной части AS. Сеть обычно имеет выделенный (designated) маршрутизатор, который является источником маршрутной информации для остальных маршрутизаторов AS. Каждый маршрутизатор самостоятельно решает задачу оптимизации маршрутов. Если к месту назначения ведут два или более эквивалентных маршрута, информационный поток будет поделен между ними поровну. Переходные процессы в OSPF завершаются быстрее, чем в RIP. В процессе выбора оптимального маршрута анализируется ориентированный граф сети. Ниже описан алгоритм Дейкстры по выбору оптимального пути. На иллюстративном рисунке 2.1 приведена схема узлов (A-J) со значениями метрики для каждого из отрезков пути. Анализ графа начинается с узла A (Старт). Пути с наименьшим суммарным значением метрики считаются наилучшими.

Именно они оказываются выбранными в результате рассмотрения графа (“кратчайшие пути“).

Ниже дается формальное описание алгоритма. Сначала вводим некоторые определения.

Пусть D(v) равно сумме весов связей для данного пути.
Пусть C(i,j) равно весу связи между узлами с номерами i и j.

Далее следует последовательность шагов, реализующих алгоритм.

1. Устанавливаем множество узлов N = {1}.

2. Для каждого узла v не из множества N устанавливаем D(v)= c(1,v).

3. Для каждого шага находим узел w не из множества N, для которого D(w) минимально, и добавляем узел w в множество N.

4. Актуализируем D(v) для всех узлов не из множества N
D(v)=min{D(v), D(v)+c(w,v)}.

5. Повторяем шаги 2-4, пока все узлы не окажутся в множестве N.

 

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

 

Рисунок 7.1 Иллюстрация работы алгоритма Дейкстры.

 

Таблица 7.1 Реализация алгоритма

	Множество	Метрика связи узла A с узлами
Шаг	N	B	C	D	E	F	G	H	I	J
	{A}		-		-	-	-	-	-	-
	{A,B}	(3)				-		-	-	-
	{A,B,C}		(4)						-
	{A,BC,D}			(6)
	{A,B,C,D,E}				(6)
	{A,B,C,D,E,H}							(8)
	{A,B,C,D,E,H,I}								(9)
	{A,B,C,D,E,H,I,F}					(10)
	{A,B,C,D,E,H,I,F,G}						(10)
	{A,B,C,D,E,H,I,F,G,J}									(14)

 

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

1) пропускной способностью канала;

2) задержкой (время распространения пакета);

3) числом дейтаграмм, стоящих в очереди для передачи;

4) загрузкой канала;

5) требованиями безопасности;

6) типом трафика;

7) числом шагов до цели;

8) возможностями промежуточных связей (например, многовариантность

достижения адресата).

Определяющими являются три характеристики: задержка, пропускная способность и надежность. OSPF имеет свой код (89) в протокольном поле IP -заголовка. Код TOS (Type Of Service) в IP -пакетах, содержащих OSPF -сообщения, равен нулю, значение TOS здесь задается в самих пакетах OSPF. Маршрутизация в этом протоколе определяется IP -адресом и типом сервиса. Автономная система может быть поделена на отдельные области, каждая из которых становится объектом маршрутизации, а внутренняя структура снаружи не видна. Этот прием позволяет значительно сократить необходимый объем маршрутной базы данных. В OSPF используется термин опорной сети (backbone) для коммуникаций между выделенными областями. Протокол работает лишь в пределах автономной системы. В пределах выделенной области может работать свой протокол маршрутизации.

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

Протокол IGRP(Interior Gateway Routing Protocol) разработан фирмой CISCO для своих многопротокольных маршрутизаторов в середине 80-х годов. Хотя этот протокол и не является стандартным, считаем возможным включить его описание, так как маршрутизаторы этой фирмы относятся к наиболее массовым. IGRP представляет собой протокол, который позволяет большому числу маршрутизаторов координировать свою работу. Основные достоинства протокола:

· стабильность маршрутов даже в очень больших и сложных сетях;

· быстрый отклик на изменения топологии сети;

· минимальная избыточность, поэтому IGRP не требует дополнительной пропускной способности каналов для своей работы;

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

· учет частоты ошибок и уровня загрузки каналов;

· возможность реализовать различные виды сервиса для одного и того же набора информации.

Сегодняшняя реализация протокола ориентирована на TCP/IP. Однако, базовая конструкция системы позволяет использовать IGRP и с другими протоколами. IGRP имеет некоторое сходство со старыми протоколами, например с RIP и Hello. Здесь маршрутизатор обменивается маршрутной информацией только с непосредственными соседями. Поэтому задача маршрутизации решается всей совокупностью маршрутизаторов, а не каждым отдельно.

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

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

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

1) время задержки;

2) пропускную способность самого слабого сегмента пути (в битах в сек);

3) загруженность канала (относительную);

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

3. Описание используемого в лабораторной работе протокола динамической маршрутизации на базе алгоритма поиска кратчайшего пути в графе

Для реализации алгоритма Дейкстры (см. раздел 2.3) использован язык программирования высокого уровня Borland C++ Builder 5.02 и приняты следующие соглашения.

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

· Один маршрутизатор может иметь любое количество соединений с другими такими же маршрутизаторами.

· Между двумя любыми маршрутизаторами можно провести одну и только одну прямую связь (соединение).

· Маршрутизатор нельзя замыкать на себя, т. е. не допустимо соединение маршрутизатора самим с собой.

· IP -адрес маршрутизатора задается только в момент соединения двух маршрутизаторов (используется классовая модель IP -адресации).

Программная реализация протокола маршрутизации на базе использования алгоритма Дейкстры для поиска кратчайшего пути в графе представляет собой приложение (Рис.7.2).

 

Рисунок. 7.2. Исходный вид приложения с загрузкой конфигурации сети из файла

После запуска приложения пользователь может создать маршрутизаторы, установив режим редактирования на , и поставить маршрутизатор в любое место на белом поле формы (Рис. 7.3).

Рисунок 7.3. Вид приложения после установки маршрутизаторов