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

Автор: Пользователь скрыл имя, 10 Марта 2015 в 16:48, курсовая работа

Краткое описание

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

Оглавление

Введение 3
1. Алгоритм поиска кратчайшего пути. 4
. Алгоритм Дейкстры 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

Скачать в ZIP (927.90 Кб) Сколько стоит заказать работу?
Файлы: 1 файл

Курсовой Передача Дискретной Информации.docx

— 933.33 Кб (Скачать)

 

 

R1

R2

R3

R4

R5

R6

  

Сеть

Перех

Дистан.

Се

ть

Перех

Дистан.

Се

ть

Перех

Дистан.

Се

ть

Перех

Дистан.

Се

ть

Перех

Дистан.

Се

ть

Перех

Дистан.

                 

14

R3

3

      

14

R3

3

 

 

R3

                 

24

R3

3

      

24

R3

3

                 

12

R3

4

      

12

R3

4

                 

45

R3

3

      

45

R3

3

12

-

1

12

-

1

34

-

1

14

-

1

15

-

1

16

-

1

 

 

 

 

 

 

 

 

 

 

R4

14

-

1

20

-

16

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

16

16

R1

2

24

R4

2

16

R1

2

20

R2

16

34

R3

2

24

R2

2

36

R1

3

12

R4

3

20

R2

16

24

R2

2

20

R5

3

34

R4

2

34

R4

2

45

R4

2

36

R3

2

34

R4

2

24

R5

3

14

R4

2

14

R4

2

14

R4

2

      

14

R4

2

      

24

R4

2

24

R4

2

24

R4

2

      

24

R4

2

      

34

R4

2

34

R4

2

34

R4

2

      

34

R4

2

      

45

R4

2

45

R4

2

45

R4

2

      

45

R4

2

      

15

R4

3

15

R4

3

15

R4

3

      

15

R4

3

      

25

R4

3

25

R4

3

25

R4

3

      

25

R4

3

      

56

R4

3

56

R4

3

56

R4

3

      

56

R4

3

      

12

R4

3

12

R4

3

12

R4

3

      

12

R4

3

      

16

R4

3

16

R4

3

16

R4

3

      

16

R4

3

      

20

R4

16

20

R4

16

20

R4

16

      

20

R4

16

      

36

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

-

16

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

16

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

16

16

R1

2

24

R4

2

16

R1

2

20

R2

16

34

R3

2

24

R2

2

36

R1

3

12

R4

3

20

R2

16

24

R2

2

20

R5

3

34

R4

2

34

R4

2

45

R4

2

36

R3

2

34

R4

2

24

R5

3

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

16

R5

3

16

R5

3

      

16

R5

3

      

16

R5

3

36

R5

3

36

R5

3

      

36

R5

3

      

36

R5

3

12

R5

3

12

R5

3

      

12

R5

3

      

12

R5

3

14

R5

3

14

R5

3

      

14

R5

3

      

14

R5

3

20

R5

16

20

R5

16

      

20

R5

16

      

20

R5

16

24

R5

3

24

R5

3

      

24

R5

3

      

24

R5

3

34

R5

3

34

R5

3

      

34

R5

3

      

34

R5

3

12

-

1

12

-

1

34

-

1

14

-

1

15

-

1

16

-

1

 

Уст

Зна

че

ние

14

-

1

20

-

16

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

16

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

16

16

R1

2

24

R4

2

16

R1

2

20

R2

16

34

R3

2

24

R2

2

36

R1

3

12

R4

3

20

R2

16

24

R2

2

20

R5

16

34

R4

2

34

R4

2

45

R4

2

36

R3

2

34

R4

2

24

R5

3


 

 

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

12

-

1

12

-

1

34

-

1

14

-

1

15

-

1

16

-

1

 

 

 

О

Б

Р

Ы

В

14

-

1

20

-

1

36

-

1

24

-

16

25

-

1

36

-

1

15

-

1

24

-

16

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

16

24

R2

2

20

R5

3

34

R4

2

34

R4

16

45

R4

2

36

R3

2

34

R4

2

24

R5

3

12

-

1

12

-

1

34

-

1

14

-

1

15

-

1

16

-

1

 

 

 

 

 

 

 

 

 

 

 

R2

14

-

1

20

-

1

36

-

1

24

-

16

25

-

1

36

-

1

15

-

1

24

-

16

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

16

24

R2

2

20

R5

3

34

R4

2

34

R4

16

45

R4

2

36

R3

2

34

R4

2

24

R5

3

12

R2

2

                  

12

R2

2

      

20

R2

2

                  

20

R2

2

      

24

R2

16

                  

24

R2

16

      

25

R2

2

                  

25

R2

2

      

15

R2

3

                  

15

R2

3

      

45

R2

3

                  

45

R2

3

      

56

R2

3

                  

56

R2

3

      

14

R2

3

                  

14

R2

3

      

16

R2

3

                  

16

R2

3

      

36

R2

4

                  

36

R2

4

      

34

R2

16

                  

34

R2

16

      

12

-

1

12

-

1

34

-

1

14

-

1

15

-

1

16

-

1

 

 

 

 

 

 

 

 

R3

14

-

1

20

-

1

36

-

1

24

-

16

25

-

1

36

-

1

15

-

1

24

-

16

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

16

36

R1

3

12

R4

3

20

R2

16

24

R2

16

20

R5

3

34

R4

2

34

R4

16

45

R4

2

36

R3

2

34

R4

2

24

R5

3

                 

34

R3

2

      

34

R3

2

                 

36

R3

2

      

36

R3

2

                 

16

R3

3

      

16

R3

3

                 

56

R3

3

      

56

R3

3

                 

15

R3

4

      

15

R3

4

                 

25

R3

<span class="Normal_0020Table__Char" style=" font-size: 9pt; text-decorat



Информация о работе Алгоритм поиска кратчайшего пути