- •Содержание
- •1 Алгоритмы поиска кратчайшего пути
- •1.1 Исходные данные
- •1.2 Алгоритм дейкстры
- •1.3 Алгоритм Беллмана-Форда
- •1.4 Расчёт пути с минимальным количеством переходов
- •1.5 Выводы по главе 1
- •2 Маршрутизация
- •2.1 Основы маршрутизации
- •2.2 Протокол rip
- •2.3. Схема сети
- •2.4. Построение маршрутных таблиц
- •2.5 Адаптация к изменениям состояния сети
- •2.5.1 Проблема адаптации rip
- •2.5.2 Отключение тупиковой сети
- •2.6 Технологии ускорения сходимости
- •2.7 Выводы по главе 2
- •Список использованной литературы
2.3. Схема сети
Схема сети, построенная по исходным данным, изображена ниже где узлы графа - это маршрутизаторы, ребра графа – это сети. Двузначный номер сети образуется из номеров узлов, соединенных этой сетью, 1ая цифра – номер узла с меньшим номером. Сеть 40 – тупиковая.
Рисунок 18. Схема сети
2.4. Построение маршрутных таблиц
В начальный момент маршрутизаторы знают только о своих непосредственно подключенных сетях. Рассылку начинает маршрутизатор R1.
Таблица 4. Маршрутная таблица в начальный момент времени
Маршрутизатор |
Сеть назначения |
Переход |
Дистанция |
R1 |
14 |
- |
1 |
16 |
- |
1 |
|
R2 |
23 |
- |
1 |
24 |
- |
1 |
|
25 |
- |
1 |
|
R3 |
23 |
- |
1 |
34 |
- |
1 |
|
36 |
- |
1 |
|
R4 |
14 |
- |
1 |
24 |
- |
1 |
|
34 |
- |
1 |
|
40 |
- |
1 |
|
R5 |
25 |
- |
1 |
56 |
- |
1 |
|
R6 |
16 |
- |
1 |
36 |
- |
1 |
|
56 |
- |
1 |
Таблица 5. R1R4, R6
Маршрутизатор |
Сеть назначения |
Переход |
Дистанция |
R4 |
14 |
- |
1 |
24 |
- |
1 |
|
34 |
- |
1 |
|
40 |
- |
1 |
|
14 |
R1 |
2 |
|
16 |
R1 |
2 |
|
R6 |
16 |
- |
1 |
36 |
- |
1 |
|
56 |
- |
1 |
|
14 |
R1 |
2 |
|
16 |
R1 |
2 |
Таблица 6. R2R3, R4, R5
Маршрутизатор |
Сеть назначения |
Переход |
Дистанция |
R3 |
23 |
- |
1 |
34 |
- |
1 |
|
36 |
- |
1 |
|
23 |
R2 |
2 |
|
24 |
R2 |
2 |
|
25 |
R2 |
2 |
|
R4 |
14 |
- |
1 |
24 |
- |
1 |
|
34 |
- |
1 |
|
40 |
- |
1 |
|
16 |
R1 |
2 |
|
23 |
R2 |
2 |
|
24 |
R2 |
2 |
|
25 |
R2 |
2 |
|
R5 |
25 |
- |
1 |
56 |
- |
1 |
|
23 |
R2 |
2 |
|
24 |
R2 |
2 |
|
25 |
R2 |
2 |
Таблица 7. R3R2, R4, R6
Маршрутизатор |
Сеть назначения |
Переход |
Дистанция |
R2 |
23 |
- |
1 |
24 |
- |
1 |
|
25 |
- |
1 |
|
23 |
R3 |
2 |
|
34 |
R3 |
2 |
|
36 |
R3 |
2 |
|
24 |
R3 |
3 |
|
25 |
R3 |
3 |
|
R4 |
14 |
- |
1 |
24 |
- |
1 |
|
34 |
- |
1 |
|
40 |
- |
1 |
|
16 |
R1 |
2 |
|
23 |
R2 |
2 |
|
25 |
R2 |
2 |
|
23 |
R3 |
2 |
|
34 |
R3 |
2 |
|
36 |
R3 |
2 |
|
24 |
R3 |
3 |
|
25 |
R3 |
3 |
|
R6 |
16 |
- |
1 |
36 |
- |
1 |
|
56 |
- |
1 |
|
14 |
R1 |
2 |
|
23 |
R3 |
2 |
|
34 |
R3 |
2 |
|
36 |
R3 |
2 |
|
24 |
R3 |
3 |
|
25 |
R3 |
3 |
Таблица 8. R4R1, R2, R3
Маршрутизатор |
Сеть назначения |
Переход |
Дистанция |
R1 |
14 |
- |
1 |
16 |
- |
1 |
|
14 |
R4 |
2 |
|
24 |
R4 |
2 |
|
34 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R4 |
3 |
|
23 |
R4 |
3 |
|
25 |
R4 |
3 |
|
36 |
R4 |
3 |
|
R2 |
23 |
- |
1 |
24 |
- |
1 |
|
25 |
- |
1 |
|
34 |
R3 |
2 |
|
36 |
R3 |
2 |
|
14 |
R4 |
2 |
|
24 |
R4 |
2 |
|
34 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R4 |
3 |
|
23 |
R4 |
3 |
|
25 |
R4 |
3 |
|
36 |
R4 |
3 |
|
R3 |
23 |
- |
1 |
34 |
- |
1 |
|
36 |
- |
1 |
|
24 |
R2 |
2 |
|
25 |
R2 |
2 |
|
14 |
R4 |
2 |
|
24 |
R4 |
2 |
|
34 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R4 |
3 |
|
23 |
R4 |
3 |
|
25 |
R4 |
3 |
|
36 |
R4 |
3 |
Таблица 9. R5R2, R6
Маршрутизатор |
Сеть назначения |
Переход |
Дистанция |
R2 |
23 |
- |
1 |
24 |
- |
1 |
|
25 |
- |
1 |
|
34 |
R3 |
2 |
|
36 |
R3 |
2 |
|
14 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R4 |
3 |
|
34 |
R4 |
3 |
|
25 |
R5 |
2 |
|
56 |
R5 |
2 |
|
23 |
R5 |
3 |
|
24 |
R5 |
3 |
|
R6 |
16 |
- |
1 |
36 |
- |
1 |
|
56 |
- |
1 |
|
14 |
R1 |
2 |
|
23 |
R3 |
2 |
|
34 |
R3 |
2 |
|
24 |
R3 |
3 |
|
25 |
R3 |
3 |
|
25 |
R5 |
2 |
|
56 |
R5 |
2 |
|
23 |
R5 |
3 |
|
24 |
R5 |
3 |
Таблица 10. R6R1, R3, R5
Маршрутизатор |
Сеть назначения |
Переход |
Дистанция |
R1 |
14 |
- |
1 |
16 |
- |
1 |
|
24 |
R4 |
2 |
|
34 |
R4 |
2 |
|
40 |
R4 |
2 |
|
23 |
R4 |
3 |
|
25 |
R4 |
3 |
|
36 |
R4 |
3 |
|
16 |
R6 |
2 |
|
36 |
R6 |
2 |
|
56 |
R6 |
2 |
|
14 |
R6 |
3 |
|
23 |
R6 |
3 |
|
34 |
R6 |
3 |
|
24 |
R6 |
4 |
|
25 |
R6 |
3 |
|
R3 |
23 |
- |
1 |
34 |
- |
1 |
|
36 |
- |
1 |
|
24 |
R2 |
2 |
|
25 |
R2 |
2 |
|
14 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R4 |
3 |
|
16 |
R6 |
2 |
|
36 |
R6 |
2 |
|
56 |
R6 |
2 |
|
14 |
R6 |
3 |
|
23 |
R6 |
3 |
|
34 |
R6 |
3 |
|
24 |
R6 |
4 |
|
25 |
R6 |
3 |
|
R5 |
25 |
- |
1 |
56 |
- |
1 |
|
23 |
R2 |
2 |
|
24 |
R2 |
2 |
|
16 |
R6 |
2 |
|
36 |
R6 |
2 |
|
56 |
R6 |
2 |
|
14 |
R6 |
3 |
|
23 |
R6 |
3 |
|
34 |
R6 |
3 |
|
24 |
R6 |
4 |
|
25 |
R6 |
3 |
Таблица 11. R1R4, R6
Маршрутизатор |
Сеть назначения |
Переход |
Дистанция |
R4 |
14 |
- |
1 |
24 |
- |
1 |
|
34 |
- |
1 |
|
40 |
- |
1 |
|
16 |
R1 |
2 |
|
23 |
R2 |
2 |
|
25 |
R2 |
2 |
|
36 |
R3 |
2 |
|
14 |
R1 |
2 |
|
16 |
R1 |
2 |
|
24 |
R1 |
3 |
|
34 |
R1 |
3 |
|
40 |
R1 |
3 |
|
23 |
R1 |
4 |
|
25 |
R1 |
4 |
|
36 |
R1 |
3 |
|
56 |
R1 |
3 |
|
R6 |
16 |
- |
1 |
36 |
- |
1 |
|
56 |
- |
1 |
|
14 |
R1 |
2 |
|
23 |
R3 |
2 |
|
34 |
R3 |
2 |
|
24 |
R3 |
3 |
|
25 |
R5 |
2 |
|
14 |
R1 |
2 |
|
16 |
R1 |
2 |
|
24 |
R1 |
3 |
|
34 |
R1 |
3 |
|
40 |
R1 |
3 |
|
23 |
R1 |
4 |
|
25 |
R1 |
4 |
|
36 |
R1 |
3 |
|
56 |
R1 |
3 |
Таблица 12. R2R3, R4, R5
Маршрутизатор |
Сеть назначения |
Переход |
Дистанция |
R3 |
23 |
- |
1 |
34 |
- |
1 |
|
36 |
- |
1 |
|
24 |
R2 |
2 |
|
25 |
R2 |
2 |
|
14 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R6 |
2 |
|
56 |
R6 |
2 |
|
23 |
R2 |
2 |
|
24 |
R2 |
2 |
|
25 |
R2 |
2 |
|
34 |
R2 |
3 |
|
36 |
R2 |
3 |
|
14 |
R2 |
3 |
|
40 |
R2 |
3 |
|
16 |
R2 |
4 |
|
56 |
R2 |
3 |
|
R4 |
14 |
- |
1 |
24 |
- |
1 |
|
34 |
- |
1 |
|
40 |
- |
1 |
|
16 |
R1 |
2 |
|
23 |
R2 |
2 |
|
25 |
R2 |
2 |
|
36 |
R3 |
2 |
|
56 |
R1 |
3 |
|
23 |
R2 |
2 |
|
24 |
R2 |
2 |
|
25 |
R2 |
2 |
|
34 |
R2 |
3 |
|
36 |
R2 |
3 |
|
14 |
R2 |
3 |
|
40 |
R2 |
3 |
|
16 |
R2 |
4 |
|
56 |
R2 |
3 |
|
R5 |
25 |
- |
1 |
56 |
- |
1 |
|
23 |
R2 |
2 |
|
24 |
R2 |
2 |
|
16 |
R6 |
2 |
|
36 |
R6 |
2 |
|
14 |
R6 |
3 |
|
34 |
R6 |
3 |
|
23 |
R2 |
2 |
|
24 |
R2 |
2 |
|
25 |
R2 |
2 |
|
34 |
R2 |
3 |
|
36 |
R2 |
3 |
|
14 |
R2 |
3 |
|
40 |
R2 |
3 |
|
16 |
R2 |
4 |
|
56 |
R2 |
3 |
Таблица 13. R3R2, R4, R6
Маршрутизатор |
Сеть назначения |
Переход |
Дистанция |
R2 |
23 |
- |
1 |
24 |
- |
1 |
|
25 |
- |
1 |
|
34 |
R3 |
2 |
|
36 |
R3 |
2 |
|
14 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R4 |
3 |
|
56 |
R5 |
2 |
|
23 |
R3 |
2 |
|
34 |
R3 |
2 |
|
36 |
R3 |
2 |
|
24 |
R3 |
3 |
|
25 |
R3 |
3 |
|
14 |
R3 |
3 |
|
40 |
R3 |
3 |
|
16 |
R3 |
3 |
|
56 |
R3 |
3 |
|
R4 |
14 |
- |
1 |
24 |
- |
1 |
|
34 |
- |
1 |
|
40 |
- |
1 |
|
16 |
R1 |
2 |
|
23 |
R2 |
2 |
|
25 |
R2 |
2 |
|
36 |
R3 |
2 |
|
56 |
R1 |
3 |
|
23 |
R3 |
2 |
|
34 |
R3 |
2 |
|
36 |
R3 |
2 |
|
24 |
R3 |
3 |
|
25 |
R3 |
3 |
|
14 |
R3 |
3 |
|
40 |
R3 |
3 |
|
16 |
R3 |
3 |
|
56 |
R3 |
3 |
|
R6 |
16 |
- |
1 |
36 |
- |
1 |
|
56 |
- |
1 |
|
14 |
R1 |
2 |
|
23 |
R3 |
2 |
|
34 |
R3 |
2 |
|
24 |
R3 |
3 |
|
25 |
R5 |
2 |
|
40 |
R1 |
3 |
|
23 |
R3 |
2 |
|
34 |
R3 |
2 |
|
36 |
R3 |
2 |
|
24 |
R3 |
3 |
|
25 |
R3 |
3 |
|
14 |
R3 |
3 |
|
40 |
R3 |
3 |
|
16 |
R3 |
3 |
|
56 |
R3 |
3 |
Таблица 14. R4R1, R2, R3
Маршрутизатор |
Сеть назначения |
Переход |
Дистанция |
R1 |
14 |
- |
1 |
16 |
- |
1 |
|
24 |
R4 |
2 |
|
34 |
R4 |
2 |
|
40 |
R4 |
2 |
|
23 |
R4 |
3 |
|
25 |
R4 |
3 |
|
36 |
R4 |
2 |
|
56 |
R6 |
2 |
|
14 |
R4 |
2 |
|
24 |
R4 |
2 |
|
34 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R4 |
3 |
|
23 |
R4 |
3 |
|
25 |
R4 |
3 |
|
36 |
R4 |
3 |
|
56 |
R4 |
4 |
|
R2 |
23 |
- |
1 |
24 |
- |
1 |
|
25 |
- |
1 |
|
34 |
R3 |
2 |
|
36 |
R3 |
2 |
|
14 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R4 |
3 |
|
56 |
R5 |
2 |
|
14 |
R4 |
2 |
|
24 |
R4 |
2 |
|
34 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R4 |
3 |
|
23 |
R4 |
3 |
|
25 |
R4 |
3 |
|
36 |
R4 |
3 |
|
56 |
R4 |
4 |
|
R3 |
23 |
- |
1 |
34 |
- |
1 |
|
36 |
- |
1 |
|
24 |
R2 |
2 |
|
25 |
R2 |
2 |
|
14 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R6 |
2 |
|
56 |
R6 |
2 |
|
14 |
R4 |
2 |
|
24 |
R4 |
2 |
|
34 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R4 |
3 |
|
23 |
R4 |
3 |
|
25 |
R4 |
3 |
|
36 |
R4 |
3 |
|
56 |
R4 |
4 |
Таблица 15. R5R2, R6
Маршрутизатор |
Сеть назначения |
Переход |
Дистанция |
R2 |
23 |
- |
1 |
24 |
- |
1 |
|
25 |
- |
1 |
|
34 |
R3 |
2 |
|
36 |
R3 |
2 |
|
14 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R4 |
3 |
|
56 |
R5 |
2 |
|
25 |
R5 |
2 |
|
56 |
R5 |
2 |
|
23 |
R5 |
3 |
|
24 |
R5 |
3 |
|
16 |
R5 |
3 |
|
36 |
R5 |
3 |
|
14 |
R5 |
4 |
|
34 |
R5 |
4 |
|
40 |
R5 |
4 |
|
R6 |
16 |
- |
1 |
36 |
- |
1 |
|
56 |
- |
1 |
|
14 |
R1 |
2 |
|
23 |
R3 |
2 |
|
34 |
R3 |
2 |
|
24 |
R3 |
3 |
|
25 |
R5 |
2 |
|
40 |
R1 |
3 |
|
25 |
R5 |
2 |
|
56 |
R5 |
2 |
|
23 |
R5 |
3 |
|
24 |
R5 |
3 |
|
16 |
R5 |
3 |
|
36 |
R5 |
3 |
|
14 |
R5 |
4 |
|
34 |
R5 |
4 |
|
40 |
R5 |
4 |
Таблица 16. R6R1, R3, R5
Маршрутизатор |
Сеть назначения |
Переход |
Дистанция |
R1 |
14 |
- |
1 |
16 |
- |
1 |
|
24 |
R4 |
2 |
|
34 |
R4 |
2 |
|
40 |
R4 |
2 |
|
23 |
R4 |
3 |
|
25 |
R4 |
3 |
|
36 |
R4 |
2 |
|
56 |
R6 |
2 |
|
16 |
R6 |
2 |
|
36 |
R6 |
2 |
|
56 |
R6 |
2 |
|
14 |
R6 |
3 |
|
23 |
R6 |
3 |
|
34 |
R6 |
3 |
|
24 |
R6 |
4 |
|
25 |
R6 |
3 |
|
40 |
R6 |
4 |
|
R3 |
23 |
- |
1 |
34 |
- |
1 |
|
36 |
- |
1 |
|
24 |
R2 |
2 |
|
25 |
R2 |
2 |
|
14 |
R4 |
2 |
|
40 |
R4 |
2 |
|
16 |
R6 |
2 |
|
56 |
R6 |
2 |
|
16 |
R6 |
2 |
|
36 |
R6 |
2 |
|
56 |
R6 |
2 |
|
14 |
R6 |
3 |
|
23 |
R6 |
3 |
|
34 |
R6 |
3 |
|
24 |
R6 |
4 |
|
25 |
R6 |
3 |
|
40 |
R6 |
4 |
|
R5 |
25 |
- |
1 |
56 |
- |
1 |
|
23 |
R2 |
2 |
|
24 |
R2 |
2 |
|
16 |
R6 |
2 |
|
36 |
R6 |
2 |
|
14 |
R6 |
3 |
|
34 |
R6 |
3 |
|
40 |
R2 |
3 |
|
16 |
R6 |
2 |
|
36 |
R6 |
2 |
|
56 |
R6 |
2 |
|
14 |
R6 |
3 |
|
23 |
R6 |
3 |
|
34 |
R6 |
3 |
|
24 |
R6 |
4 |
|
25 |
R6 |
3 |
|
40 |
R6 |
4 |
Сходимость достигнута, так как каждый маршрутизатор знает обо всех сетях. Время сходимости – два цикла маршрутизации.
