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

Содержание

 

 Введение           3

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

1. . Алгоритм Дейкстры       5

1.2. Алгоритм Беллмана-Форда      8

1.3. Расчет пути с минимальным  количеством переходов  9

1.4. Сравнение алгоритмов       10

2. Маршрутизация         11

2.1. Основы маршрутизации       11

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

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

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

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

2.4.2. Отключение тупиковой сети     22

2.4.3. Отключение канала      25

2.4.4. Отключение  маршрутизатора     29

Заключение          33

Список  литературы         34

 

Введение.

 

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

 

Вариант№ 757

 

Матрица смежности:

 

V1 V2 V3 V4 V5 V6

V1   0    6    0    3    1    1

V2   6    0    0    8    1    0

V3   0    0    0    6    0    3

V4   1    8    6    0    3    0

V5   5    8    0    5    0    5

V6   7    0    8    0    6    0

    

 

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

 

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

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

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

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

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

 

1. Алгоритм Дейкстры

 

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

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

В первый момент времени во множестве вершин, уже обработанных алгоритмом находится только вершина V1. Соответственно от нее можно достичь вершин V4,V2,V5 и V6. На втором шаге добавляется вершина V2, однако это не влияет на стоимости путей от вершины V1. При добавлении во множество обработанных вершин вершины V4 появляется путь до вершины V3, через V4. При добавлении вершины V3, ничего в таблице не изменяется. Но когда во множество Т добавляется вершина V5, то алгоритм находит более короткий путь от V1 до V6. Это путь 1-5-6. Таким образом, на этом шаге происходит изменение связующего дерева, которое приобретает окончательный вид (при добавлении V6 изменений не происходит).

 

h	T	L(2)	Путь	L(3)	Путь	L(4)	Путь	L(5)	Путь	L(5)	Путь
1	{1}	6	1-2	∞	-	3	1-4	1	1-5	1	1-6
2	{1,2}	6	1-2	∞	-	3	1-4	1	1-5	1	1-6
3	{1,2,4}	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6
4	{1,2,3,4}	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6
5	{1,2,3,4,5}	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6
6	{1,2,3,4,5,6}	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6

 

T= {1}

 

T= {1,2}

 

T= {1,2,4}

T= {1,2,3,4}

 

T= {1,2,3,4,5}

 

T= {1,2,3,4,5,6}

 

 

     Алгоритм завершает работу, когда все вершины добавлены к множеству Т. Таким образом, для работы алгоритма требуется 6 итераций. К моменту окончания работы алгоритма значение L(x), поставленное в соответствие каждой вершине Х представляет собой минимальную стоимость (длину) пути от вершины V1 до вершины Х. Кроме того, дерево представляет собой связующее дерево исходного ориентированного графа, определяющее пути с минимальной стоимостью от вершины S до всех остальных вершин.

 

1.2 Алгоритм Беллмана-Форда

 

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

Этот алгоритм также работает поэтапно: на каждом шаге алгоритм находит путь с минимальной стоимостью, максимальное число ретрансляционных участков в котором равно h. То есть на первом шаге, когда h=0 можно сказать только о существовании узла V1, так как количество переходов равно 0. При h=1, алгоритм находит кратчайшие пути до всех узлов в пределах одного перехода. То есть до узлов V4,V2,V5,V6. При h=2 , алгоритм находит кратчайшие пути до всех узлов в пределах двух переходов. На данном этапе “открывается” узел V3,  и изменяется путь к узлу V6 (с учетом стоимости путей). При дальнейшем увеличении количества переходов, полученные значения не изменяются.

 

h	L(2)	Путь	L(3)	Путь	L(4)	Путь	L(5)	Путь	L(6)	Путь
0	∞	-	∞	-	∞	-	∞	-	∞	-
1	6	1-2	∞	-	3	1-4	1	1-5	1	1-6
2	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6
3	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6
4	6	1-2	9	1-4-3	3	1-4	1	1-5	1	1-6

 

h=1

 

 

h=2

 

Следует заметить, что конечные результаты, полученные алгоритмами Дейкстры и Беллмана-Форда, совпадают. А так же совпадают и связующие деревья.

 

1.3 Расчет пути с минимальным  количеством переходов.

 

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

Произведем расчет полученного графа с помощью алгоритма Беллмана-Форда.

h	L(2)	Путь	L(3)	Путь	L(4)	Путь	L(5)	Путь	L(6)	Путь
0	∞	-	∞	-	∞	-	∞	-	∞	-
1	1	1-2	∞	-	1	1-4	1	1-5	1	1-6
2	1	1-2	2	1-4-3	1	1-4	1	1-5	1	1-6
3	1	1-2	2	1-4-3	1	1-4	1	1-5	1	1-6
4	1	1-2	2	1-4-3	1	1-4	1	1-5	1	1-6

 

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

 

 

 

1.4 Сравнение  алгоритмов 

 

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

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

 

 

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

2.1. Основы маршрутизации

В общественном значении слово маршутизация означает передвижение информации от источника к пункту назначения через объединенную сеть. Маршрутизация отличается от объединения сетей с помощью моста, тем, что объединение с помощью моста имеет место на уровне 2 эталонной модели ISO, в то время как маршрутизация встречается на уровне 3. Эта разница объясняется тем, что маршрутизация и объединение по мостовой схеме используют различную информацию в процессе ее перемещения от источника к месту назначения и выполняют свои задачи разными способами.  Маршрутизация включает в себя два основных компонента: определение оптимальных трактов маршрутизации и транспортировка информационных групп через объединенную сеть (коммутация). Для облегчения процесса определения маршрута алгоритмы маршрутизации инициализируют и поддерживают таблицы маршрутизации, в которых содержится маршрутная информация. Маршрутная информация изменяется в зависимости от используемого алгоритма маршрутизации. Алгоритм маршрутизации заполняют маршрутные таблицы неким множеством информации. “Показатели” обеспечивают информацию о желательности какого-либо канала или тракта.

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

Наиболее широко используемые адаптивные протоколы (методы) маршрутизации - 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 переходов, это значение на единицу больше, чем максимально возможная метрика, которую маршрутизатор ожидает увидеть в любом сообщении об обновлении маршрутизации.