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

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


 

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

42244. Программирование на языке JavaScript (данные, функции и управление выполнением программы) 186.5 KB
  Программирование на языке JvScript данные функции и управление выполнением программы 1. Цель работы Целью работы является овладение навыками работы с данными функциями и предложениями управления при создании интерактивных Webстраниц с использованием языка сценариев JvScript. Синтаксис языка JvScript Текст программы на языке JvScript представляет собой последовательность символов в кодировке SCII или Unicode. Комментарии в языке JvScript можно оформлять одним из следующих двух способов: 1.
42245. Программирование на языке JavaScript (встроенные объектные типы) 194.5 KB
  Предложение создания нового объекта имеет следующий синтаксис: vr переменная = new имяобъектноготипа[параметры] Этот оператор создает новый экземпляр объекта заданного объектного типа и присваивает его значение переменной. Пример создание переменной встроенного объектного типа String: vr string1= new String Строка 1 ; Объекту может быть присвоено специальное значение null. Объект который еще не инициализирован также имеет значение null. Свойства объектного типа Mth Свойство Значение E Значение константы Эйлера 2718.
42246. Создание объектов в языке JavaScript, регулярные выражения и обработка ошибок 496.5 KB
  Опции шаблона регулярного выражения Опция Назначение g Глобальный поиск т. Свойства объекта Regulr Expression Имя Значение Тип возвращаемого значения Возможность изменения globl Состояние опции g true включена или flse выключена Только для чтения ignoreCse Состояние опции i true включена или flse выключена Только для чтения multiline Состояние опции m true включена или flse выключена Только для чтения source Копия строки шаблона регулярного выражения Строка Только для чтения lstIndex Позиция того символа в строке с которой...
42247. Программирование на языке JavaScript (использование средств объектной модели документа) 217 KB
  Целью работы является приобретение навыков использования свойств и методов предоставляемых объектной моделью документа DOM и средств обработки событий для создания интерактивных Webстраниц с использованием языка сценариев JvScript. Программное обеспечение: операционная система Windows Webбраузер Internet Explorer версии 6. их представление в виде объектов с заданными свойствами и запрограммированными методами должна выполняться производителем Webбраузера. form select Выделяет содержимое области типа text file или...
42248. Использование форм в Web-страницах. Вставки форм в Web-страницах 267.5 KB
  Использование форм в Webстраницах Целью работы является знакомство с элементами вставки форм в Webстраницах. Программное обеспечение: операционная система Windows Webбраузер Internet Explorer версии 6. Модуль Bsic Forms Формы HTML первоначально были предназначены для пересылки данных от удаленного пользователя к Webсерверу.
42249. Работа с объектом window, анимация. Создание интерактивных Web-страниц с использованием языка сценариев JavaScript 165 KB
  Целью работы является овладение навыками работы с окнами типа window при создании интерактивных Webстраниц с использованием языка сценариев JvScript. Программное обеспечение: операционная система Windows Webбраузер Internet Explorer версии 6. Объект window в JvScript Все Webбраузеры выводят пользователям Webстраницы в окне дисплея. Объект window представляет текущее окно Webбраузера или отдельный фрейм если окно разделено на фреймы.
42250. Організація виконання вантажних операцій 540.5 KB
  Структура управління вантажними операціями на залізничному транспорті. Вибір раціонального варіанта механізації навантажувально-розвантажувальних робіт. Основні параметри вантажно-розвантажувальних машин. Показники надійності вантажно-розвантажувальних машин. Застосування і класифікація навантажувачів...
42251. ЭЛЕКТРОМАГНИТ ПОСТОЯННОГО ТОКА 66 KB
  При протекании тока по обмоткам электромагнита создается электромагнитная сила притягивающая магнитную систему к неподвижному якорю. Сила тяги электромагнита через рамку 6 воздействует на пружину 7 которая действует на индикатор перемещения поворачивая стрелку 8. Питание электромагнита осуществляется от источника 220 В через трансформатор Тр и двухполупериодный выпрямительный мост В. Изучить принципиальную схему электромагнита.
42252. КОНТРОЛЬ МАЛОЙ КЛИНОВИДНОСТИ ПЛАСТИН НА ИНТЕРФЕРОМЕТРЕ ЧАПСКОГО 302 KB
  Рассмотрим возникновение полос равного наклона и определим величину разности хода лучей отраженных под некоторым углом от плоскопараллельной пластины рис. Если поверхности пластины образуют между собой малый угол  то изображения источника 1 в фокальной плоскости 6 разойдутся на расстояние l =n где  фокусное расстояние линзы 5. Первый случай соответствует перемещению пластины в сторону увеличения её толщины второй в сторону уменьшения. Появление или исчезновение кольца соответствует изменению толщины пластины на величину .