Базовый алгоритм обновления маршрута в RIP

 

                          

                       нет

                                                                       да

Установить дистанцию = 16

                                                                       да

                     

                нет                                                                                                                                                                      

 

                         нет

 

                                                                      да

 

                       нет

Стереть старый маршрут до сети

                                                                    да

                                                                                               

Записать новый маршрут

                                                                    да                       нет    

Игнорировать новый маршрут

                                                                        

                                                                        

Сбросить таймеры маршрута

                                                                   

 

 

Построение маршрутных таблиц

За исходный примем граф изображенный на рисунке 10.

 

 

Таблица№4- Начальное состояние

R	Сеть назначения	Следующий переход	Дистанция
R1	10 35 45	- - -	1 1 1
R2	15 20 25	- - -	1 1 1
R3	30 40 45 50	- - - -	1 1 1 1
R4	20 30	- -	1 1
R5	25 35 40	- - -	1 1 1
R6	10 15	- -	1 1

Рассылка маршрутных таблиц начинается с 1-го маршрутизатора и далее последовательно по циклу.

 

Таблица №5. R1=>R3R5R6

R	Сеть назначения	Следующий переход	Дистанция
R3	30 40 45 50 10 35 45	- - - - R1 R1 R1	1 1 1 1 2 2 2
R5	25 35 40 10 35 45	- - - R1 R1 R1	1 1 1 2 2 2
R6	10 15 10 35 45	- - R1 R1 R1	1 1 2 2 2

 

Таблица №6. R2=>R4R5R6

R	Сеть назначения	Следующий переход	Дистанция
R4	20 30 15 20 25	- - R2 R2 R2	1 1 2 2 2
R5	25 35 40 10 45 15 20 25	- - - R1 R1 R2 R2 R2	1 1 1 2 2 2 2 2
R6	10 15 35 45 15 20 25	- - R1 R1 R2 R2 R2	1 1 2 2 2 2 2

 

Таблица №7. R3=>R1R4R5

R	Сеть назначения	Следующий переход	Дистанция
R1	10 35 45 30 40 45 50 10 35	- - - R3 R3 R3 R3 R3 R3	1 1 1 2 2 2 2 3 3
R4	20 30 15 25 30 40 45 50 10 35	- - R2 R2 R3 R3 R3 R3 R3 R3	1 1 2 2 2 2 2 2 3 3
R5	25 35 40 10 45 15 20 30 40 45 50 10 35	- - - R1 R1 R2 R2 R3 R3 R3 R3 R3 R3	1 1 1 2 2 2 2 2 2 2 2 3 3

 

Таблица №8. R4=>R2R3

R	Сеть назначения	Следующий переход	Дистанция
R2	15 20 25 20 30 15 25 40 45 50 10 35	- - - R4 R4 R4 R4 R4 R4 R4 R4 R4	1 1 1 2 2 3 3 3 3 3 4 4
R3	30 40 45 50 10 35 20 30 15 25 40 45	- - - - R1 R1 R4 R4 R4 R4 R4 R4	1 1 1 1 2 2 2 2 3 3 3 3

 

Таблица №9. R5=>R1,R2R3.

R	Сеть назначения	Следующий переход	Дистанция
R1	10 35 45 30 40 50 25 35 40 10 45 15 20 30 50	- - - R3 R3 R3 R5 R5 R5 R5 R5 R5 R5 R5 R5	1 1 1 2 2 2 2 2 2 3 3 3 3 3 3
R2	15 20 25 30 40 45 50 10 35 25 35 40 10 45 15 20 30 50	- - - R4 R4 R4 R4 R4 R4 R5 R5 R5 R5 R5 R5 R5 R5 R5	1 1 1 2 3 3 3 4 4 2 2 2 3 3 3 3 3 3
R3	30 40 45 50 10 35 20 15 25 25 35 40 10 45 15 20 30 50	- - - - R1 R1 R4 R4 R4 R5 R5 R5 R5 R5 R5 R5 R5 R5	1 1 1 1 2 2 2 3 3 2 2 2 3 3 3 3 3 3

 

Таблица №10. R6=>R1R2.  R Сеть назначения Следующий переход Дистанция R1 10 35 45 30 40 50 25 15 20 10 15 35 45 20 25 - - - R3 R3 R3 R5 R5 R5 R6 R6 R6 R6 R6 R6 1 1 1 2 2 2 2 3 3 2 2 3 3 3 3 R2 15 20 25 30 40 45 50 10 35 10 15 35 45 20 25 - - - R4 R4 R4 R4 R4 R4 R6 R6 R6 R6 R6 R6 1 1 1 2 3 3 3 4 4 2 2 3 3 3 3

 

Таблица №11. R1=>R3R5R6.

R	Сеть назначения	Следующий переход	Дистанция
R3	30 40 45 50 10 35 20 15 25 10 35 45 30 40 50 25 15 20	- - - - R1 R1 R4 R4 R5 R1 R1 R1 R1 R1 R1 R1 R1 R1	1 1 1 1 2 2 2 3 2 2 2 2 3 3 4 3 3 3
R5	25 35 40 10 45 15 20 30 50 10 35 45 30 40 50 25 15 20	- - - R1 R1 R2 R2 R3 R3 R1 R1 R1 R1 R1 R1 R1 R1 R1	1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 4 4
R6	10 15 35 45 20 25 10 35 45 30 40 50 25 15 20	- - R1 R1 R2 R2 R1 R1 R1 R1 R1 R1 R1 R1 R1	1 1 2 2 2 2 2 2 2 3 3 3 3 4 4

 

Дальнейшее рассмотрение построения маршрутных таблиц не имеет смысла так как сходимость достигнута.

Итоговая таблица маршрутизации будет иметь вид:

 

Таблица №12.

R	Сеть назначения	Следующий переход	Дистанция
R1	10 35 45 30 40 50 25 15 20	- - - R3 R3 R3 R5 R5 R5	1 1 1 2 2 2 2 3 3
R2	15 20 25 30 40 45 50 10 35	- - - R4 R4 R4 R4 R4 R4	1 1 1 2 3 3 3 4 4
R3	30 40 45 50 10 35 20 15 25	- - - - R1 R1 R4 R4 R4	1 1 1 1 2 2 2 3 3
R4	20 30 15 25 40 45 50 10 35	- - R2 R2 R3 R3 R3 R3 R3	1 1 2 2 2 2 2 3 3
R5	25 35 40 10 45 15 20 30 50	- - - R1 R1 R2 R2 R3 R3	1 1 2 2 2 2 2 3 3
R6	10 15 35 45 20 25 30 40 50	- - R1 R1 R2 R2 R1 R1 R1	1 1 2 2 2 2 3 3 3

 

Отключение канала

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

 

Таблица №13.

R	Сеть назначения	Следующий переход	Дистанция
R3	30 40 45 50 10 35 20 15 25	- - - - R1 R1 R4 R4 R4	1 1 1 1 2 2 2 3 3
R4	20 30 15 25 40 45 50 10 35	- - R2 R2 R3 R3 R3 R3 R3	1 1 2 2 2 2 2 3 3

 

Таблица №14. R3=>R1R5.

R	Сеть назначения	Следующий переход	Дистанция
R1	10 35 45 30 40 50 25 15 20 30 40 45 50 10 35 20 15 25	- - - R3 R3 R3 R5 R5 R5 R3 R3 R3 R3 R3 R3 R3 R3 R3	1 1 1 2 2 2 2 3 3 10 2 2 2 3 3 3 4 4
R5	25 35 40 10 45 15 20 30 50 30 40 45 50 10 35 20 15 25	- - - R1 R1 R2 R2 R3 R3 R3 R3 R3 R3 R3 R3 R3 R3 R3	1 1 2 2 2 2 2 3 3 10 2 2 2 3 3 3 4 4

Таблица №15. R4=>R2.

R	Сеть назначения	Следующий переход	Дистанция
R2	15 20 25 30 40 45 50 10 35 20 30 15 25 40 45 50 10 35	- - - R4 R4 R4 R4 R4 R4 R4 R4 R4 R4 R4 R4 R4 R4 R4	1 1 1 2 3 3 3 4 4 2 10 3 3 3 3 3 4 4

 

Таблица №16. R6=>R1,R2.

R	Сеть назначения	Следующий переход	Дистанция
R1	10 35 45 30 40 50 25 15 20 10 15 35 45 20 25 30 40 50	- - - R3 R3 R3 R5 R5 R5 R6 R6 R6 R6 R6 R6 R6 R6 R6	1 1 1 10 2 2 2 3 3 2 2 3 3 3 3 4 4 4
R2	15 20 25 30 40 45 50 10 35 10 15 35 45 20 25 30 40 50	- - - R4 R4 R4 R4 R4 R4 R6 R6 R6 R6 R6 R6 R6 R6 R6	1 1 1 10 3 3 3 4 4 2 2 3 3 3 3 4 4 4

 

Таблица №17. R1=>R3,R5,R6.

R	Сеть назначения	Следующий переход	Дистанция
R3	30 40 45 50 10 35 20 15 25 10 35 45 30 40 50 25 15 20	- - - - R1 R1 R4 R4 R4 R1 R1 R1 R1 R1 R1 R1 R1 R1	10 1 1 1 2 2 2 3 3 2 2 2 5 3 3 3 4 4
R5	25 35 40 10 45 15 20 30 50 10 35 45 30 40 50 25 15 20	- - - R1 R1 R2 R2 R3 R3 R1 R1 R1 R1 R1 R1 R1 R1 R1	1 1 2 2 2 2 2 10 3 2 2 2 5 4 3 3 4 4
R6	10 15 35 45 20 25 30 40 50 10 35 45 30 40 50 25 15 20	- - R1 R1 R2 R2 R1 R1 R1 R1 R1 R1 R1 R1 R1 R1 R1 R1	1 1 2 2 2 2 3 3 3 2 2 2 5 3 3 3 4 4

 

Таблица №18. R5=>R1,R2,R3.

R	Сеть назначения	Следующий переход	Дистанция
R1	10 35 45 30 40 50 25 15 20 25 35 40 10 45 15 20 50 30	- - - R3 R3 R3 R5 R5 R5 R5 R5 R5 R5 R5 R5 R5 R5 R5	1 1 1 2 2 2 2 3 3 2 2 3 3 3 3 3 4 4
R2	15 20 25 30 40 45 50 10 35 25 35 40 10 45 15 20 50 30	- - - R4 R4 R4 R4 R4 R4 R5 R5 R5 R5 R5 R5 R5 R5 R5	1 1 1 2 3 3 3 4 4 2 2 3 3 3 3 3 4 4
R3	30 40 45 50 10 35 20 15 25 25 35 40 10 45 15 20 50 30	- - - - R1 R1 R4 R4 R4 R5 R5 R5 R5 R5 R5 R5 R5 R5	10 1 1 1 2 2 2 3 3 2 2 3 3 3 3 3 4 4

 

Таблица №19. R2=>R4,R5,R6.

R	Сеть назначения	Следующий переход	Дистанция
R4	20 30 15 25 40 45 50 10 35 15 20 25 30 40 45 50 10 35	- - R2 R2 R3 R3 R3 R3 R3 R2 R2 R2 R2 R2 R2 R2 R2 R2	1 1 2 2 2 2 2 3 3 2 2 2 3 4 4 4 5 5
R5	25 35 40 10 45 15 20 30 50 15 20 25 30 40 45 50 10 35	- - - R1 R1 R2 R2 R3 R3 R2 R2 R2 R2 R2 R2 R2 R2 R2	1 1 2 2 2 2 2 10 3 2 2 2 3 4 4 4 5 5
R6	10 15 35 45 20 25 40 50 30 15 20 25 30 40 45 50 10 35	- - R1 R1 R2 R2 R1 R1 R1 R2 R2 R2 R2 R2 R2 R2 R2 R2	1 1 2 2 2 2 3 3 5 2 2 2 3 4 4 4 5 5

 

Таблица №20. R3=>R1R5.

R	Сеть назначения	Следующий переход	Дистанция
R1	10 35 45 30 40 50 25 15 20 30 40 45 50 10 35 20 15 25	- - - R3 R3 R3 R5 R5 R5 R3 R3 R3 R3 R3 R3 R3 R3 R3	1 1 1 2 2 2 2 3 3 10 1 1 1 2 2 2 3 3
R5	25 35 40 10 45 15 20 30 50 30 40 45 50 10 35 20 15 25	- - - R1 R1 R2 R2 R3 R3 R3 R3 R3 R3 R3 R3 R3 R3 R3	1 1 2 2 2 2 2 10 3 10 1 1 1 2 2 2 3 3

Итоговая таблица маршрутизации будет иметь вид:

Таблица №21.

R	Сеть назначения	Следующий переход	Дистанция
R1	10 35 45 30 40 50 25 15 20	- - - R3 R3 R3 R5 R5 R5	1 1 1 2 2 2 2 3 3
R2	15 20 25 30 40 45 50 10 35	- - - R4 R4 R4 R4 R4 R4	1 1 1 2 3 3 3 4 4
R3	30 40 45 50 10 35 20 15 25	- - - - R1 R1 R4 R4 R4	10 1 1 1 2 2 2 3 3
R4	20 30 15 25 40 45 50 10 35	- - R2 R2 R3 R3 R3 R3 R3	1 1 2 2 2 2 2 3 3
R5	25 35 40 10 45 15 20 30 50	- - - R1 R1 R2 R2 R3 R3	1 1 2 2 2 2 2 10 3
R6	10 15 35 45 20 25 40 50 30	- - R1 R1 R2 R2 R1 R1 R1	1 1 2 2 2 2 3 3 5

 

Заключение

 

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

Список использованной литературы

 

1 Кульгин М. В. Коммутация и маршрутизация IР/IРХ-трафика

2. Столлингс В. Современные компьютерные сети. – 2003. (Глава 14. Теория графов и поиск путей с минимальной стоимостью)