71036

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

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

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

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

Русский

2014-11-01

197.5 KB

2 чел.

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

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

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

Лабораторная работа №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 входят все узлы?

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


 

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

59095. Розгортання Національно-визвольної боротьби в 1648-1649 роках. Зборівський мирний договір 56.5 KB
  І тут Хмельницький проявив свої організаторські здібності створивши з розрізнених повсталих загонів дисципліновану добре озброєну армію. Робота з картою Хмельницький повів своє військо назустріч полякам з Маслового Ставу через Паволоч Хмільник і зупинився Пилявцями над Іквою де збудував укріплений табір.
59096. Розпяття серця, сповненого любовю. Психологічне есе Джеймса Джойса Джакомо 36 KB
  Джойса розкрити його світоглядні й естетичні позиції ввести поняття потік свідомості літературна ремінісценція; психологічне есе Джакомо і особистість та творчість письменника; розвивати вміння слухати лекцію та складати тези. Який характер твору Джакомо Автобіографічний.
59097. Розробка уроку з музики 33.5 KB
  Чайковський Танець феї Драже Баба Яга; поспівка Перший клас; пісня Б.Чайковського Танець феї Драже Баба Яга Композитор П.Чайковського з балету Лускунчик у якому задіяні персонажі дівчинка солдатлускунчик казкова фея яка має назву цукерок фея Драже та багато інших і скажіть: до якого названого героя найбільше підходить ця музика Хто з них може танцювати під неї Слухання.Чайковський Танець феї Драже Це танець феї Драже.
59098. Роль Гетьмана Мазепи в українській історії 46 KB
  Мета: розкрити роль і значення гетьмана Івана Мазепи в українській історії. Допомогти учням збагнути патріотичну та героїчну суть діяльності гетьмана. Портрети гетьмана й історичних особистостей його епохи.
59099. Руська трійця у Львові 42 KB
  Вивчення нового матеріалу, формування вмінь та навичок (25 хв.): оголошення нової теми; очікувані результати; мотивація навчальної діяльності; сприйняття і осмислення учнями навчального матеріалу.
59100. Рухова активність і здоровя 43 KB
  Посміхайтеся частіше і будьте здорові та щасливі ІІ. Що ж саме про людину ми зараз вивчаємо на уроках біології А навіщо вам його розгадувати що дадуть вам знання організму людини Знання...
59101. Рушничок для мами 49.5 KB
  Ви мабуть чули слово декорації Де їх можна побачити Звичайно у театрі. Де можна побачити такі орнаменти Їх часто використовують для оздоблення різноманітних частин одягу у вишивці розписах вазонів та інших предметів побуту.
59102. Сім чудес світу 45 KB
  Мета: закріпити і систематизувати знання учнів з історії Стародавнього світу, розглянути матеріали про найвизначніші памятки світової культури; розвивати в учнів логічне мислення та зорову память; виховувати любов до прекрасного, інтерес до історії.
59103. Свято врожаю 70.5 KB
  На столах хліб пиріжки печиво тістечка фрукти кавуни мед компот квіти. Просимо Ласкаво просимо Певне чули ви малята І не раз такі слова: Хліб потрібно шанувати Хліб усьому голова Хлопчик. А тому завжди в пошані Хліб у школі і в садку. Шановні батьки гості запрошуємо вас до нашої господи...