71031

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

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

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

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

Русский

2014-11-01

209 KB

2 чел.

Цель работы

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

Задание

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

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

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

Исходные данные для моделирования работы протокола OSPF

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

№ графа

№ узла

1,2

2,3

2,4

3,5

3,7

4,5

5,6

6,7

1,6

2,6

3,4

5,7

1

6

5

4

3

2

1

2

3

4

5

6

2

7

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

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

Рассмотрим первый алгоритм – алгоритм Дейкстры.

Применение алгоритма Дейкстры к заданной сети.

Шаг

N

D(1)

D(2)

D(3)

D(4)

D(5)

D(6)

Начальный

{7}

3

6

2

1

{6,7}

5

6

3

3

2

2

{3,6,7}

5

6

3

8

3

2

3

{3,5,6,7}

5

6

3

5

3

2

4

{1,3,5,6,7}

5

6

3

5

3

2

5

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

5

6

3

5

3

2

6

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

5

6

3

5

3

2

На начальном шаге имеем D(3)=3, D(5)=6, D(6)=2. Остальные вершины не соединены непосредственно с вершиной 7.

Шаг 1. Имеем минимальное значение D(w) – D(6)=2. Поэтому включаем вершину 6 в множество N. Далее обновляем значения D(w).

D(1) = min[D(1), D(6)+l(6,3)] = min[∞, 2+3] = 5.

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

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

Шаг 2. Имеем минимальное значение D(w) – D(3)=3. Поэтому включаем вершину 3 в множество N. Далее обновляем значения D(w).

D(4) = min[D(4), D(3)+l(3,4)] = min[∞, 3+5] = 8.

Шаг 3. Минимальное значение D(w) – D(5)=3. Поэтому включаем вершину 5 в множество N. Далее обновляем значения D(w).

D(4) = min[D(4), D(5)+l(4,5)] = min[8, 3+2] = 5.

Шаг 4. Минимальное значение D(w) – D(1)=5. Поэтому включаем узел 1 в множество N.

Шаг 5. Имеем минимальное значение D(w) – D(4)=5. Поэтому включаем вершину 4 в множество N.

Шаг 6. Минимальное значение D(w) – D(2)=6. Поэтому включаем узел 2 в множество N.

В результате получаем следующее дерево для сети:

А таблица маршрутизации выглядит следующим образом:

Узел-получатель

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

1

6

2

6

3

3

4

6

5

6

6

6

Рассмотрим второй алгоритм – алгоритм Флойда.

Применение алгоритма Флойда к заданной сети.

Шаг

Узел

1

2

3

4

5

6

Начальный

(●,∞)

(●,∞)

(●,∞)

(●,∞)

(●,∞)

(●,∞)

1

(●,∞)

(●,∞)

(7,3)

(3,8)

(7,6)

(7,2)

2

(6,5)

(6,6)

(7,3)

(3,8)

(6,3)

(7,2)

3

(6,5)

(6,6)

(7,3)

(5,5)

(6,3)

(7,2)

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

Шаг 1.

Узел 3 является соседним по отношению к узлу 7. Поэтому обновляем величину D(v):

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

Далее для узла 4 имеем D(4) = min[D(3)+l(4,3)] = 3+5 = 8.

Для узла 5 имеем D(5) = min[D(7)+l(5,7)] = 0+6 = 6.

И для узла 6 D(6) = min[D(7)+l(6,7)] = 0+2 = 2.

Шаг 2.

Для узла 1 имеем D(1) = min[D(6)+l(1,6)] = 2+3 = 5.

Далее для узла 2 имеем

D(2) = min[D(6)+l(2,6), D(1)+l(2,1), D(3)+l(2,3), D(4)+l(2,4)] = min[2+4, 5+1, 3+6, 8+5] = 6.

Для узла 3

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

Для узла 4 D(4) = min[D(2)+l(4,2), D(3)+l(4,3), D(5)+l(4,5)] = min[6+5, 3+5, 6+2] = 8.

Для узла 5

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

Шаг 3.

Для узла 1 имеем D(1) = min[D(2)+l(1,2), D(6)+l(1,6)] = min[6+1, 2+3] = 5.

Для узла 2 имеем

D(2) = min[D(1)+l(2,1), D(3)+l(2,3), D(4)+l(2,4), D(6)+l(2,6)] = min[5+1, 3+6, 8+5, 2+4] = 6.

Для узла 3

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

Для узла 4 D(4) = min[D(2)+l(4,2), D(3)+l(4,3), D(5)+l(4,5)] = min[6+5, 3+5, 3+2] = 5.

Для узла 5

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

Так как далее узлы не меняют своих значений, то алгоритм завершается.

В результате получаем дерево, аналогичное построенному по алгоритму Дейкстры. Его мы получаем путём обхода меток каждого узла: узел 1 соединяется с узлом 6, узел 2 – с узлом 6, узел 3 – с узлом 7, узел 4 – с узлом 5, узел 5 – с узлом 6, узел 6 – с узлом 7.

Таблица маршрутов для случая, когда узел 7 является узлом назначения, выглядит следующим образом:

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

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

1

6

2

6

3

7

4

4

5

6

6

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 – узелисточник.

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

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

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

Выводы

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

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

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

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

11


(3)

DD

(6)

(5)

(0)

(4)

Нет

DD

LSU

D

LSR

7

5

LSR

4

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

2

2

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

Нет

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

Да

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

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

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

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

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

1

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

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

1

Нет

Да

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

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

LSA

LSU

7

5

4

3

6

2

1

DD

DD

7

5

4

3

6

2

1

LSU

LSR

7

5

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

4

3

6

2

7

5

1

4

2

2

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

1

1

3

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

v := 1

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

Да

1

Нет

Да

1

Нет

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

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

Нет

Да

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

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

1

v := v + 1

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

на (w, min D(v))

N={S}

6

2

v ≠ S

Нет

Да

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

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

5

7

1

6

5

4

3

6

2

1

4

3

2

1

2

3

4

5

6

3

6

2

1

(1)

(2)

Да

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

1

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


 

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

35610. Новогодняя игрушка. Творческий проект 25.18 KB
  Нитки Шарики Клей ПВА Технологический процесс. Затем шерстяные нитки обмочим в клее ПВА и начинаем наматывать на шарик. Смачиваем шерстяные нитки в клее ПВА. Затем аккуратно начинаем наматывать на шарик нитки.
35612. Ассоль. (техника- вышивка гладью) 384.5 KB
  Правила безопасности во время работы Во время работы ножницы должны лежать справа на столе с сомкнутыми лезвиями кольцами к работающему. Брать и передавать ножницы нужно сомкнутыми лезвиями к себе кольцами вперёд. Иглы булавки ножницы наперсток хранят в специальной шкатулке с крышкой. Выравнивание краев ткани Ткань размером 30x40 Измерение Линейка карандаш ножницы.
35613. Профессия графический дизайнер. Творческий проект 2 MB
  Мой логотип Визитная карточка Мои проекты и работы Разработка подарочной упаковки для фирмы diva Упаковка играет сегодня огромную роль в развитии потребительского рынка являясь важной составляющей имиджа брендов. Этапы разработки упаковки На начальном этапе разработки упаковки осуществляется выбор материала определение формы размера цветового решения разработка текста изображения и конструкции упаковки. При разработке оформления упаковки индивидуальный образ фирмы был сохранен так как подарочная упаковка создавалась именно по...
35614. Пошив юбки. Разработка творческого проекта 1.89 MB
  Юбки запаски тканые с поперечными полосами. Развивала свои творческие способности и художественное виденье предметов с помощью изготовления юбки. Идеально подходит для юбки-солнца на мой взгляд крепсатин.
35616. ШКОЛА ТВОРЧЕСКОЙ ЖИЗНИ. ПРОЕКТ 221 KB
  По его вине Древо Жизни утратило крону. ПРОЕКТ ШКОЛА ТВОРЧЕСКОЙ ЖИЗНИ Принцип устойчивости экодеревни Проблемы экодеревень ПУТИ РЕАЛИЗАЦИИ ПРОЕКТА: Экономическая деятельность в поселении Природные виды деятельности Виды деятельности связанные с информационными технологиями Научная деятельность Искусство Народные ремёсла Медицина Туризм Строительство Малые производства Культура Образование Безопасная интеграция в природную среду Топология экологического поселения Проект...
35617. Шарлотка. Творческий проект 68.02 KB
  Тема: Шарлотка. Но от салата я отказалась И решила приготовить пирог шарлотка. Шарлотка фр. Классическая шарлотка это французское сладкое блюдо приготовленное из белого хлеба заварного крема фруктов и ликёра.
35618. Мой выбор. Творческий проект 33.32 KB
  Правильный выбор профессии позволит мне так построить свою будущую карьеру чтобы достичь выдающихся успехов. Можно выделить следующие подпроблемы: Проблемное поле анализа профессиональной деятельности Изучение алгоритма выбора профессии Выявление и анализ личностных и психофизиологических характеристик Изучение требований...