71036

ФУНКЦИОНИРОВАНИЕ МАРШРУТИЗАТОРОВ НА ОСНОВЕ ПРОТОКОЛА СЕТЕВОГО УРОВНЯ OSPF СТЕКА ПРОТОКОЛОВ TCP/IP

Лабораторная работа

Информатика, кибернетика и программирование

Изучение основных принципов работы маршрутизаторов в сетях ЭВМ на основе протокола OSPF. В результате выполнения лабораторной работы студент получает знания по принципам построения и алгоритмам функционирования маршрутизаторов в сетях ЭВМ и навыки по выбору кратчайших путей в сети на основе протокола OSPF.

Русский

2014-11-01

197.5 KB

1 чел.

Министерство Образования Российской Федерации

Марийский Государственный Технический Университет

Факультет Информатики и Вычислительной Техники

Лабораторная работа №6

ФУНКЦИОНИРОВАНИЕ МАРШРУТИЗАТОРОВ НА ОСНОВЕ ПРОТОКОЛА СЕТЕВОГО УРОВНЯ OSPF

СТЕКА ПРОТОКОЛОВ TCP/IP

Вариант №7

Выполнил:

студент ФИВТ

группы ПС-41

Пастбин К. Ю.

Проверил:

Синельников А. С.

Йошкар-Ола

2004


Цель работы

Изучение основных принципов работы маршрутизаторов в сетях ЭВМ на основе протокола OSPF. В результате выполнения лабораторной работы студент получает знания по принципам построения и алгоритмам функционирования маршрутизаторов в сетях ЭВМ и навыки по выбору кратчайших путей в сети на основе протокола OSPF.

Задание

1. Изучить структуру и алгоритмы работы маршрутизаторов в сетях ЭВМ.

2. Изучить алгоритмы выбора кратчайших путей и функционирование протокола сетевого уровня OSPF.

3. Построить таблицы маршрутизации сети, используя алгоритмы Дейкстры и Флойда.

Исходные данные

Расстояние между соседними узлами графа – l(i,j)

№ графа

№ узла

1, 2

1, 3

1, 4

1, 5

2, 3

2, 4

3, 5

3, 6

3, 7

4, 5

5, 6

6, 7

2

4

3

1

2

1

6

8

7

1

6

4

1

7

Граф исходной сети:

Выбор кратчайших путей и построение таблиц маршрутизации

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

Шаг

N

D(1)

D(2)

D(3)

D(4)

D(5)

D(6)

Начальный

{7}

7

4

1

{6,7}

7

10

4

2

{3,6,7}

11

9

7

10

4

3

{2,3,6,7}

11

9

7

10

10

4

4

{2,3,4,6,7}

11

9

7

10

10

4

5

{2,3,4,5,6,7}

11

9

7

10

10

4

6

{1,2,3,4,5,6,7}

11

9

7

10

10

4

Шаг 0. D(3)=7, D(6)=4. Остальные вершины не соединены непосредственно с вершиной 7.

Шаг 1. Минимальное значение D(6)=4. N = N + {6}.

D(3) = min[D(3), D(6)+l(6,3)] = min[7, 4+8] = 7.

D(5) = min[D(5), D(6)+l(6,5)] = min[∞, 4+6] = 10.

Шаг 2. Минимальное значение D(3)=7. N = N + {3}.

D(1) = min[D(1), D(3)+l(3,1)] = min[∞, 7+4] = 11.

D(2) = min[D(2), D(3)+l(3,2)] = min[∞, 7+2] = 9.

D(5) = min[D(5), D(3)+l(3,5)] = min[10, 7+6] = 10.

D(6) = min[D(6), D(3)+l(3,6)] = min[4, 7+8] = 4.

Шаг 3. Минимальное значение D(2)=9. N = N + {2}.

D(1) = min[D(1), D(2)+l(2,1)] = min[11, 9+2] = 11.

D(3) = min[D(3), D(2)+l(2,3)] = min[7, 9+2] = 7.

D(4) = min[D(4), D(2)+l(2,4)] = min[∞, 9+1] = 10.

Шаг 4. Два минимальных значения D(4)=D(5)=10. N = N + {4} (выбираем случайно между 4 и 5).

D(1) = min[D(1), D(4)+l(4,1)] = min[11, 10+3] = 11.

D(2) = min[D(2), D(4)+l(4,2)] = min[9, 10+1] = 9.

D(5) = min[D(5), D(4)+l(4,5)] = min[10, 10+1] = 10.

Шаг 5. Минимальное значение D(5)=10. N = N + {5}.

D(1) = min[D(1), D(5)+l(5,1)] = min[11, 10+1] = 11.

D(3) = min[D(3), D(5)+l(5,3)] = min[7, 10+6] = 7.

D(4) = min[D(4), D(5)+l(5,4)] = min[10, 10+1] = 10.

D(6) = min[D(6), D(5)+l(5,6)] = min[4, 10+6] = 4.

Шаг 6. Минимальное значение D(1)=6. N = N + {1}.

D(2) = min[D(2), D(1)+l(1,2)] = min[9, 11+2] = 9.

D(3) = min[D(3), D(1)+l(1,3)] = min[7, 11+4] = 7.

D(4) = min[D(4), D(1)+l(1,4)] = min[10, 11+3] = 10.

D(5) = min[D(5), D(1)+l(1,5)] = min[10, 11+1] = 10.

Результирующее дерево сети и таблица маршрутизации для узла-источника 7:

Узел-отправитель

Направление передачи (узел)

1

3

2

3

3

3

4

3

5

6

6

6

Алгоритм Флойда

Шаг

Узел

1

2

3

4

5

6

Начальный

(●,∞)

(●,∞)

(●,∞)

(●,∞)

(●,∞)

(●,∞)

1

(●,∞)

(●,∞)

(7,7)

(●,∞)

(3,13)

(7,4)

2

(3,11)

(3,9)

(7,7)

(2,10)

(6,10)

(7,4)

Шаг 0. D(7)=0. Остальные узлы отмечаем (●,∞).

Шаг 1.

D(3) = min[D(7)+l(7,3)] = 0+7 = 7.

D(5) = min[D(3)+l(3,5)] = 7+6 = 13.

D(6) = min[D(7)+l(7,6)] = 0+4 = 4.

Шаг 2.

D(1) = min[D(3)+l(3,1); D(5)+l(5,1)] = min[11; 14] = 11 (из узла 3).

D(2) = min[D(1)+l(1,2); D(3)+l(3,2)] = min[13; 9] = 9 (из узла 3).

D(3) = min[D(1)+l(1,3); D(2)+l(2,3); D(5)+l(5,3); D(6)+l(6,3); D(7)+l(7,3)] =

min[15; 11; 19; 12; 7] = 7 (из узла 7).

D(4) = min[D(1)+l(1,4); D(2)+l(2,4); D(5)+l(5,4)] = min[14; 10; 14] = 10 (из узла 2).

D(5) = min[D(1)+l(1,5); D(3)+l(3,5); D(4)+l(4,5); D(6)+l(6,5)] =

min[12; 13; 11; 10] = 10 (из узла 6).

D(6) = min[D(3)+l(3,6); D(5)+l(5,6); D(7)+l(7,6)] = min[15; 16; 4] = 4 (из узла 7).

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

Моделирование работы протокола OSPF

После инициализации модуля OSPF (например, после подачи питания на маршрутизатор) через все интерфейсы, включенные в OSPF-систему, начинают рассылаться Hello-сообщения. Задача Hello-протокола - обнаружение соседей и установление с ними отношений смежности. Каждый маршрутизатор отправляет своим соседям приветственные пакеты и получает от них такие же пакеты. На рисунке представлена часть обменов Hello-пакетами.

Обмен Hello-сообщениями

Формат Hello-сообщений:

Общий заголовок OSPF (Тип=1)

Маска подсети (32 бита)

Hello-интервал

Опции (8 бит)

Приоритет (8 бит)

Интервал отказа маршрутизатора (32 бита)

Адрес DR (32 бита)

Адрес BDR (32 бита)

Адрес соседа (32 бита)

. . .

Адрес соседа (32 бита)

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

После установления отношений смежности для каждой пары смежных маршрутизаторов происходит синхронизация их баз данных. Синхронизация баз данных происходит с помощью протокола обмена (Exchange protocol).

Сначала маршрутизаторы обмениваются только описаниями своих баз данных (Database Description), содержащими идентификаторы записей и номера их версий, это позволяет избежать пересылки всего содержимого БД, если требуется синхронизировать только несколько записей.

Формат сообщения” Описание базы данных (Database Description):

Общий заголовок OSPF (Тип=2)

0 (16 бит)

Опции (8 бит)

0 (5 бит)

IMMS (3 бита)

Порядковый номер данного сообщения (32 бита) (DDSN)

LSA заголовок

. . .

IMMS (3 бита) - последние 3 бита октета, следующего за полем "Options": I - Initialize, бит 5; M - More, бит 6, MS - Master/Slave, бит 7. Остальная часть октета, где находятся эти биты, обнулена.

LSA Header (20 октетов) - описание (набор идентификаторов) записи из БД состояния связей, представляющее собой заголовок "Объявления о состоянии связей".

Обмен начинается с выяснения, кто из двух маршрутизаторов будет играть главную роль, а кто подчиненную. Маршрутизатор, желающий начать обмен на правах главного, отправляет пустое сообщение с установленными битами IMMS и произвольным, но не использованным в обозримом прошлом номером DDSN. Второй маршрутизатор подтверждает, что согласен играть подчиненную роль: он отправляет обратно также пустое сообщение с тем же DDSN, c установленными битами I и M и сброшенным битом MS.

После того, как роли распределены, начинается обмен описаниями БД. Главный отправляет подчиненному сообщения с описаниями своей БД; номера DDSN увеличиваются с каждым сообщением, бит I сброшен, бит МS установлен, бит M установлен во всех сообщениях, кроме последнего.

Подчиненный отправляет подтверждения на каждое полученное от главного сообщения. Эти подтверждения представляют собой сообщения того же типа, содержащие описание базы данных подчиненного маршрутизатора. Номер DDSN равен номеру подтверждаемого сообщения, биты I и MS сброшены, бит М установлен во всех сообщениях, кроме последнего.

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

На этом процедура обмена описаниями БД заканчивается.

Обмен описаниями БД

Во время этого обмена каждый маршрутизатор формирует список записей, содержимое которых он должен запросить, и соответственно отправляет пакеты запросов о состоянии связей (Link State Request). В ответ он получает содержимое последних версий нужных ему записей в пакетах типа "Обновление состояния связей (Link State Update)".

Отправление сообщения "Запрос состояния связи" и получение

в ответ сообщения "Обновление состояния связей"

Формат сообщения” Запрос состояния связи (Link State Request)”:

Общий заголовок OSPF (Тип=3)

Тип связи (связей) (Link State Type)

Идентификатор связи (связей) (Link State ID)

Адрес маршрутизатора (32 бита)

. . .

Формат сообщения” Обновление состояния связей (Link State Update)”:

Общий заголовок OSPF (Тип=4)

Число LSA  в сообщении (32 бита)

Объявление о состоянии связей (LSA)

. . .

После синхронизации баз данных производится построение маршрутов. Первым шагом является создание карты сетевой топологии. Далее маршрутизатор формирует дерево кратчайших путей ко всем возможным получателям. Каждый маршрутизатор строит своё дерево независимо от других. Далее маршрутизатор строит таблицу маршрутизации.

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

Подпротокол OSPF, выполняющий эту задачу, называется протоколом затопления (Flooding protocol). При работе этого протокола пересылаются сообщения типа "Обновление состояния связей (Link State Update)", получение которых подтверждается сообщениями типа "Link State Acknowledgment".

Отправление сообщения " Обновление состояния связи" и получение

в ответ сообщения " Подтверждение приема сообщения о состоянии связей"

Формат сообщения”Подтверждение приема сообщения о состоянии связей (Link State Acknowledgment)”:

Общий заголовок OSPF (Тип=5)

Заголовок LSA

. . .

Сообщение содержит одно или несколько подтверждений, каждое подтверждение состоит из заголовка LSA, получение которого подтверждается.

Формат заголовка LSA:

Возраст связи (16 бит)

Опции (8 бит)

Тип LSA (8 бит)

Идентификатор связи (32 бита)

Адрес маршрутизатора, ответственного за объявление и поддержку связи (связей), содержащихся в данном LSA (32 бита)

Порядковый номер (версия) состояния связи (связей) (32 бита)

Контрольная сумма (16 бит)

Длина LSA в байтах, включая 20 байт заголовка LSA

Построим графсхему алгоритма Флойда для выбора кратчайших путей.

S – узелполучатель.

Построим графсхему алгоритма функционирования маршрутизатора согласно протоколу OSPF.

Выводы

В результате выполнения лабораторной работы были изучены алгоритмы функционирования маршрутизаторов в сетях ЭВМ и алгоритмы выбора кратчайших путей в сети на основе протокола OSPF.

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

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

Также были построены графсхемы алгоритмов выбора кратчайших путей в сети и функционирования маршрутизатора по протоколу OSPF.

LSA

LSU

7

4

3

6

2

1

LSU

LSR

LSR

LSU

LSR

7

5

4

3

2

1

2

2

v := v + 1

Обновляем метку

на (w, min D(v))

Нет

Да

v ≠ S

1

Нет

Да

v > кол-ва узлов

v := 1

DD

DD

DD

DD

DD

7

5

4

3

6

2

Завершение алгоритма

2

Завершение алгоритма Флойда

1

7

5

4

D(S)=0, а остальные узлы отмечаем (●,∞)

1

Нет

Да

3

Происходят изменения в метках узлов?

6

2

1

(0)

(2)

(5)

(3)

(4)

(1)

(6)

7

5

2

1

8

4

1

6

1

3

4

7

6

7

5

2

4

3

6

1

2

Алгоритм Флойда

2

Рассылка пакетов LSU и получение пакетов LSA

Изменение своей БД

Нет

Да

Образование новой связи или обрыв?

Строим  дерево кратчайших путей

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

Отправление пакетов LSR и получение пакетов LSU

Обмен 2х смежных маршрутизаторов описаниями своих БД

1

Выбор выделенного и запасного выделенного маршрутизаторов

Нет

Да

Получено Hello-сообщение?

Рассылка Hello-сообщений

Инициализации модуля OSPF

1

Нет

Да

Отношения смежности установлены?

Алгоритм функционирования маршрутизатора

1

4

3

6

2

1

Завершение алгоритма Дейкстры

N={S}

1

1

Включаем узел w в множество N

Находим узел w, не принадлежащий N, с минимальным D(w)

Нет

Да

В множество N входят все узлы?

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


 

А также другие работы, которые могут Вас заинтересовать

58270. Начало Французской революции. Свержение монархии. Якобинская диктатура 147.5 KB
  И сразу начались затяжные споры по различным вопросам: о способах проверки полномочий депутатов о совместных и раздельных заседаниях о задачах Генеральных штатов о правах третьего сословия завтрашнем дне страны о будущем Франции.
58271. ЕКОНОМІКА ВЕЛИКОБРИТАНІЇ 40 KB
  У самому справі Великобританії можуть вижити тільки виробництва і торгівлі. За винятком вугілля низькосортна залізна руда природний газ і нафта у Великобританії є кілька природних ресурсів. Вугілля була замінована у Великобританії більше 300 років.
58272. Контроль витрат і стимулювання економії ресурсів. Система обліку витрат 199.5 KB
  Контроль витрат є важливою складовою системи управління витратами, без якої неможлива повноцінна реалізація інших її функцій. До основних завдань контролю витрат відносять: моніторинг - систематичне відстежування динаміки витрат і факторів, які на неї впливають...
58274. Ознайомлення з підручником. Предмет. Фігура. Лічба предметів 36 KB
  Мета: ознайомити учнів з підручником Математика; з’ясувати чи вміють діти лічити числа й називати їх; дати уявлення про предмети геометричні фігури; прищеплювати зацікавленість вивченням математики.
58275. За квітами у пошуках щастя (за новелою Богдана Лепкого «Цвіт щастя») 31.5 KB
  Мета. Удосконалювати вміння переказувати твір; проаналізувати твір Цвіт щастя дослідити реальне і уявне в новелірозкрити образ маленького хлопчикапоказати внутрішній стан; розвивати логічне мислення память творчу уяву...
58276. Лічба предметів. Порівняння груп предметів за величиною 33 KB
  Скільки всього помідорів Скільки огірків Скільки бурячків Скільки всього овочів II. Як легше визначити однакова кількість чи неоднакова Чого більше На скільки більше Чого менше На скільки Що треба зробити щоб кількість трикутників й квадратиків стала однаковою...
58278. Порядкова лічба. Поняття зліва — направо, справа — наліво, решта, кожний, вищий — нижчий. Підготовка до написання цифр 33.5 KB
  Ознайомлення учнів з поняттями зазначеними в темі уроку На столі стоять чотири кубики різного кольору червоний синій жовтий зелений. Якого кольору останній кубик Якого кольору кубик що стоїть попереду кубик якого кольору стоїть між синім і зеленим...