Алгоритм поиска кратчайшего пути

а) статистическими или динамическими

б) одномаршрутными или многомаршрутными

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

г) с интеллектом в главной вычислительной машине или в роутере

д) с внутридоменными или междоменными

е) алгоритмами состояния канала или вектора расстояний

 

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

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

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

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

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

Надежность – надежность каждого канала сети, обычно описываемой в терминах соотношения бит/ошибка.

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

Полоса пропускания – относится к имеющейся мощности трафика какого-либо канала.

Наиболее широко используемые адаптивные протоколы (методы) маршрутизации - RIP (Routing Information Protocol) и OSPF (Open Shortest Path First). Метод RIP иначе называется методом рельефов. Он основан на алгоритме Беллмана-Форда и используется преимущественно на нижних уровнях иерархии сети. В сетях, работающих в соответствии с методом OSPF, информация о любом изменении в сети рассылается лавинообразно.

Алгоритм Беллмана-Форда относится к алгоритмам DVA (Distance Vector Algorithms). В DVA рельеф Ra(d) - это оценка кратчайшего пути от узла a к узлу d. Оценка (условно назовем ее расстоянием) может выражаться временем доставки, надежностью доставки или числом узлов коммутации (измерение в хопах) на данном маршруте. В ТМ узла, а каждому из остальных узлов отводится одна строка со следующей информацией:

- узел назначения;

- длина кратчайшего  пути;

- номер N ближайшего  узла, соответствующего кратчайшему  пути;

- список рельефов  от а к d через каждый из смежных  узлов.

 

2.2. Характеристики протокола RIP

Протокол RIP представляет собой один из старейших протоколов обмена маршрутной информацией между маршрутизаторами в сети, построенной на базе протокола IP. Помимо версии протокола RIP для сетей IP существует также версия этого протокола для сетей IPX/SPX компании Novell. Сообщения об обновлении таблиц маршрутизации в этом протоколе касаются только устройств, которые разделяют общую сеть. Эти устройства называются соседями. В этом протоколе все сети имеют номера. При этом способ образования номера зависит от используемого в сети протокола сетевого уровня. А все маршрутизаторы имеют свои идентификаторы.

Протокол RIP относится к классу протоколов ЮР. Хотя не существует строгих требований к использованию определенного протокола маршрутизации внутри отдельной автономной системы, протокол RIP стал стандартом де-факто. Однако при этом накладывается существенное ограничение на размер автономной системы (АС) — она должна быть умеренного размера, так как RIP имеет ограничение — наибольший путь в сети не может превышать 15 переходов. Причина такого ограничения будет рассмотрена далее.

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

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

В маршрутизаторе, работающем с протоколом RIP, вся информация хранится в виде записей в таблице маршрутизации, содержащей следующие поля:

1.IP-адрес целевой сети.

2. Количество переходов к целевой  сети.

3. Адрес первого маршрутизатора  в пути к целевой сети.

4. Идентификатор  соседнего маршрутизатора, который  является источником этой информации в таблице маршрутизации.

5. Таймер для отслеживания времени, прошедшего с последнего момента  обновления записи.

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

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

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

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

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

 

 

2.3. Построение  таблиц маршрутизации.

 

Первым рассылку маршрутных таблиц начинает R5

 

Тогда изменение маршрутных таблиц дол момента сходимости будет иметь вид:

 

R1			R2			R3			R4			R5			R6
Сеть	Перех	Дистан.	Се ть	Перех	Дистан.	Се ть	Перех	Дистан.	Се ть	Перех	Дистан.	Се ть	Перех	Дистан.	Се ть	Перех	Дистан.
12	-	1	12	-	1	34	-	1	14	-	1	15	-	1	16	-	1	Н.У
14	-	1	20	-	1	36	-	1	24	-	1	25	-	1	36	-	1
15	-	1	24	-	1				34	-	1	45	-	1	56	-	1
16	-	1	25	-	1				45	-	1	56	-	1
12	-	1	12	-	1	34	-	1	14	-	1	15	-	1	16	-	1	R5
14	-	1	20	-	1	36	-	1	24	-	1	25	-	1	36	-	1
15	-	1	24	-	1				34	-	1	45	-	1	56	-	1
16	-	1	25	-	1				45	-	1	56	-	1	15	R5	2
15	R5	2	15	R5	2				15	R5	2				25	R5	2
25	R5	2	25	R5	2				25	R5	2				45	R5	2
45	R5	2	45	R5	2				45	R5	2				56	R5	2
56	R5	2	56	R5	2				56	R5	2
12	-	1	12	-	1	34	-	1	14	-	1	15	-	1	16	-	1	R6
14	-	1	20	-	1	36	-	1	24	-	1	25	-	1	36	-	1
15	-	1	24	-	1	16	R6	2	34	-	1	45	-	1	56	-	1
16	-	1	25	-	1	36	R6	2	45	-	1	56	-	1	15	R5	2
25	R5	2	15	R5	2	56	R6	2	15	R5	2	16	R6	2	25	R5	2
45	R5	2	45	R5	2	15	R6	3	25	R5	2	36	R6	2	45	R5	2
56	R5	2	56	R5	2	25	R6	3	56	R5	2	56	R6	2
16	R6	2				45	R6	3				15	R6	3
36	R6	2										25	R6	3
56	R6	2										45	R6	3
15	R6	3
25	R6	3
45	R6	3
12	-	1	12	-	1	34	-	1	14	-	1	15	-	1	16	-	1	R1
14	-	1	20	-	1	36	-	1	24	-	1	25	-	1	36	-	1
15	-	1	24	-	1	16	R6	2	34	-	1	45	-	1	56	-	1
16	-	1	25	-	1	56	R6	2	45	-	1	56	-	1	15	R5	2
25	R5	2	15	R5	2	15	R6	3	15	R5	2	16	R6	2	25	R5	2
45	R5	2	45	R5	2	25	R6	3	25	R5	2	36	R6	2	45	R5	2
56	R5	2	56	R5	2	45	R6	3	56	R5	2	12	R1	2	12	R1	2
36	R6	2	12	R1	2				12	R1	2	14	R1	2	14	R1	2
			14	R1	2				14	R1	2	15	R1	2	15	R1	2
			15	R1	2				15	R1	2	16	R1	2	16	R1	2
			16	R1	2				16	R1	2	25	R1	3	25	R1	3
			25	R1	3				25	R1	3	45	R1	3	45	R1	3
			45	R1	3				45	R1	3	56	R1	3	56	R1	3
			56	R1	3				56	R1	3	36	R1	3	36	R1	3
			36	R1	3				36	R1	3
12	-	1	12	-	1	34	-	1	14	-	1	15	-	1	16	-	1	R2
14	-	1	20	-	1	36	-	1	24	-	1	25	-	1	36	-	1
15	-	1	24	-	1	16	R6	2	34	-	1	45	-	1	56	-	1
16	-	1	25	-	1	56	R6	2	45	-	1	56	-	1	15	R5	2
25	R5	2	15	R5	2	15	R6	3	15	R5	2	16	R6	2	25	R5	2
45	R5	2	45	R5	2	25	R6	3	25	R5	2	36	R6	2	45	R5	2
56	R5	2	56	R5	2	45	R6	3	56	R5	2	12	R1	2	12	R1	2
36	R6	2	14	R1	2				12	R1	2	14	R1	2	14	R1	2
12	R2	2	16	R1	2				16	R1	2	12	R2	2
20	R2	2	36	R1	3				36	R1	3	20	R2	2
24	R2	2							12	R2	2	24	R2	2
25	R2	2							20	R2	2	25	R2	2
15	R2	3							24	R2	2	15	R2	3
45	R2	3							25	R2	2	45	R2	3
56	R2	3							15	R2	3	56	R2	3
14	R2	3							45	R2	3	14	R2	3
16	R2	3							56	R2	3	16	R2	3
36	R2	4							14	R2	3	36	R2	4
									16	R2	3
									36	R2	4

 

 

R1			R2			R3			R4			R5			R6
Сеть	Перех	Дистан.	Се ть	Перех	Дистан.	Се ть	Перех	Дистан.	Се ть	Перех	Дистан.	Се ть	Перех	Дистан.	Се ть	Перех	Дистан.
12	-	1	12	-	1	34	-	1	14	-	1	15	-	1	16	-	1	R3
14	-	1	20	-	1	36	-	1	24	-	1	25	-	1	36	-	1
15	-	1	24	-	1	16	R6	2	34	-	1	45	-	1	56	-	1
16	-	1	25	-	1	56	R6	2	45	-	1	56	-	1	15	R5	2
25	R5	2	15	R5	2	15	R6	3	15	R5	2	16	R6	2	25	R5	2
45	R5	2	45	R5	2	25	R6	3	25	R5	2	36	R6	2	45	R5	2
56	R5	2	56	R5	2	45	R6	3	56	R5	2	12	R1	2	12	R1	2
36	R6	2	14	R1	2				12	R1	2	14	R1	2	14	R1	2
20	R2	2	16	R1	2				16	R1	2	20	R2	2	34	R3	2
24	R2	2	36	R1	3				36	R1	3	24	R2	2	36	R3	2
									20	R2	2				16	R3	3
									34	R3	2				56	R3	3
									36	R3	2				15	R3	4
									16	R3	3				25	R3	4
									56	R3	3				45	R3	4
									15	R3	4
									25	R3	4
									45	R3	4
12	-	1	12	-	1	34	-	1	14	-	1	15	-	1	16	-	1	R4
14	-	1	20	-	1	36	-	1	24	-	1	25	-	1	36	-	1
15	-	1	24	-	1	16	R6	2	34	-	1	45	-	1	56	-	1
16	-	1	25	-	1	56	R6	2	45	-	1	56	-	1	15	R5	2
25	R5	2	15	R5	2	15	R6	3	15	R5	2	16	R6	2	25	R5	2
45	R5	2	45	R5	2	25	R6	3	25	R5	2	36	R6	2	45	R5	2
56	R5	2	56	R5	2	45	R6	3	56	R5	2	12	R1	2	12	R1	2
36	R6	2	14	R1	2	14	R4	2	12	R1	2	14	R1	2	14	R1	2
20	R2	2	16	R1	2	24	R4	2	16	R1	2	20	R2	2	34	R3	2
24	R2	2	36	R1	3	34	R4	2	20	R2	2	24	R2	2
14	R4	2	14	R4	2	45	R4	2	36	R3	2	14	R4	2
24	R4	2	24	R4	2	15	R4	3				24	R4	2
34	R4	2	34	R4	2	25	R4	3				34	R4	2
45	R4	2	45	R4	2	56	R4	3				45	R4	2
15	R4	3	15	R4	3	12	R4	3				15	R4	3
25	R4	3	25	R4	3	16	R4	3				25	R4	3
56	R4	3	56	R4	3	20	R4	3				56	R4	3
12	R4	3	12	R4	3	36	R4	3				12	R4	3
16	R4	3	16	R4	3							16	R4	3
20	R4	3	20	R4	3							20	R4	3
36	R4	3	36	R4	3							36	R4	3
12	-	1	12	-	1	34	-	1	14	-	1	15	-	1	16	-	1	R5
14	-	1	20	-	1	36	-	1	24	-	1	25	-	1	36	-	1
15	-	1	24	-	1	16	R6	2	34	-	1	45	-	1	56	-	1
16	-	1	25	-	1	56	R6	2	45	-	1	56	-	1	15	R5	2
25	R5	2	15	R5	2	15	R6	3	15	R5	2	16	R6	2	25	R5	2
45	R5	2	45	R5	2	25	R6	3	25	R5	2	36	R6	2	45	R5	2
56	R5	2	56	R5	2	20	R4	3	56	R5	2	12	R1	2	12	R1	2
36	R6	2	14	R1	2	14	R4	2	12	R1	2	14	R1	2	14	R1	2
20	R2	2	16	R1	2	24	R4	2	16	R1	2	20	R2	2	34	R3	2
24	R2	2	36	R1	3	12	R4	3	20	R2	2	24	R2	2	15	R5	2
34	R4	2	34	R4	2	45	R4	2	36	R3	2	34	R4	2	25	R5	2
15	R5	2	15	R5	2				15	R5	2				45	R5	2
25	R5	2	25	R5	2				25	R5	2				56	R5	2
45	R5	2	45	R5	2				45	R5	2				16	R5	3
56	R5	2	56	R5	2				56	R5	2				36	R5	3
16	R5	3	16	R5	3				16	R5	3				12	R5	3
36	R5	3	36	R5	3				36	R5	3				14	R5	3
12	R5	3	12	R5	3				12	R5	3				20	R5	3
14	R5	3	14	R5	3				14	R5	3				24	R5	3
20	R5	3	20	R5	3				20	R5	3				34	R5	3
24	R5	3	24	R5	3				24	R5	3
34	R5	3	34	R5	3				34	R5	3
R1			R2			R3			R4			R5			R6
Сеть	Перех	Дистан.	Се ть	Перех	Дистан.	Се ть	Перех	Дистан.	Се ть	Перех	Дистан.	Се ть	Перех	Дистан.	Се ть	Перех	Дистан.
12	-	1	12	-	1	34	-	1	14	-	1	15	-	1	16	-	1	Уст Зна че ние
14	-	1	20	-	1	36	-	1	24	-	1	25	-	1	36	-	1
15	-	1	24	-	1	16	R6	2	34	-	1	45	-	1	56	-	1
16	-	1	25	-	1	56	R6	2	45	-	1	56	-	1	15	R5	2
25	R5	2	15	R5	2	15	R6	3	15	R5	2	16	R6	2	25	R5	2
45	R5	2	45	R5	2	25	R6	3	25	R5	2	36	R6	2	45	R5	2
56	R5	2	56	R5	2	20	R4	3	56	R5	2	12	R1	2	12	R1	2
36	R6	2	14	R1	2	14	R4	2	12	R1	2	14	R1	2	14	R1	2
20	R2	2	16	R1	2	24	R4	2	16	R1	2	20	R2	2	34	R3	2
24	R2	2	36	R1	3	12	R4	3	20	R2	2	24	R2	2	20	R5	3
34	R4	2	34	R4	2	45	R4	2	36	R3	2	34	R4	2	24	R5	3

 

 

 

2.4. Адаптация к изменениям состояния  сети.

 

2.4.1. Проблема адаптации RIP.

 

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

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

Все маршрутизаторы, участвующие в обмене сообщениями об обновлении маршрутизации протокола RIP, посылают эти сообщения через определенный интервал, который по умолчанию составляет 30 секунд. Если маршрутизатор не получит сообщение от маршрутизатора, который являлся источником определенной записи в таблице маршрутизации, через временной интервал, равный увеличенному в шесть раз установленному значению (30 секунд), а в случае, если это значение установлено по умолчанию, оно будет равно 180 секунд, он может предположить, что либо его соседний маршрутизатор вышел из строя, либо нарушилась связь между ними. Затем маршрутизатор будет помечать существующий маршрут как некорректный и в конечном счете удалит его из своей таблицы маршрутизации. Когда маршрутизатор получит информацию о новом маршруте от другого его соседа, этот новый маршрут будет использоваться вместо старого, удаленного.

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

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