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

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


 

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

20157. Узлы координатных перемещений и измерительные преобразователи КИМ 33.5 KB
  Трехкоординатные измерительные приборы предназначены для измерения и контроля размеров корпусных деталей блоки цилиндров корпуса насосов для контроля штампов прессформ для подготовки программ к станкам с ЧПУ. Измерительные системы координатных перемещений предназначены для отсчета перемещения подвижных узлов ТИП при измерении координат точек. Подавляющее большинство ТИП до 80 оснащено фотоэлектрическими измерительными системами имеющими растровые измерительные линейки штриховые меры.
20158. Устройства взаимодействия с измеряемой деталью КИМ 221.5 KB
  Три группы устройств: жесткие щупы; щуповые головки; оптические и проекционнооптические устройства. Щуповые головки являются одним из основных узлов и они в равной степени с измерительным преобразователем и узлами координатных перемещений участвуют в измерении координат точек и определяют точность универсальность и производительность КИМ. Щуповые головки дают возможность автоматизировать процесс измерения на КИМах. Все щуповые головки по принципу функционирования подразделяются на 2е большие группы: щуповые головки нулевыеголовки...
20159. Приборы для измерения угловых величин. Автоколлиматоры. Гоннометры. ОДГ 308 KB
  Изображение секундной и минутной шкал наблюдается с помощью окуляра 6 через полупентопризму 13 которая из мнимого изображения делает действительное. Неподвижный узел – сетка с минутной шкалой и указателем секундной шкалы. Изображение марки отразившись от зеркала 1 попадает между штрихами минутной шкалы и в процессе измерения его совмещают с ближайшим штрихом минутной шкалы. Смещение Δ измеряется по секундной шкале жестко связанной с линзой относительно указателя на минутной шкале и т.
20160. Приборы для измерения угловых величин. Уровни. Квадранты 480 KB
  Преобразователи угловых перемещений. Преобразователи угловых перемещений. непосредственное измерение углов в угловых величинах по угловым шкалам.
20161. Механические и гидростатические приборы при измерении отклонений от прямолинейности и плоскостности 1.31 MB
  Для более точной оценки просвета используют образец просвета рис. Рис.1 Рис.2 На рис.
20162. Оптико-механические и оптические приборы при измерении отклонений от прямолинейности и плоскостности 393 KB
  При проверке автоколлимационным и коллимационным методами измеряют углы наклона последовательно расположенных участков равных шагу измерения по отношению к исходной прямой заданной оптической осью трубы. Сущность метода визирования заключается в измерении расстояния от проверяемой поверхности до оптической оси зрительной трубы. Визирную ось зрительной трубы устанавливают параллельной прямой проходящей через крайние точки проверяемой поверхности при этом отсчёты в крайних точках должны быть одинаковыми. Этот недостаток можно устранить...
20163. Средства измерения отклонения форм цилиндрических поверхностей 94.5 KB
  К отклонениям формы цилиндрических поверхностей относятся: о отклонение от цилиндричности ; о отклонение от круглости ; = отклонения профиля продольного сечения. f φ 2π = f φ Для анализа отклонения профиля поперечного сечения можно использовать совокупность гармонических составляющих определяемых спектром фазовых углов и спектром амплитуд т. R=f φ х; Для аналитического изображения профиля поперечного сечения пользуются разложением функции погрешностей профиля в ряд Фурье: R0 – R = ∆ = f φ fφ=C0 2 ∑Ck coskφ φ0...
20164. Создание удаленных представлений 827 KB
  При создании системы обработки данных не всегда удается обеспечить их хранение в едином формате. Часто возникает необходимость использования данных из уже работающих приложений ктороые написаны не на VFP. Удаленное представление работает на основе соединения которое используя технологию Open Database Connectivity ODBC описывает условия передачи данных.1 Окно диалога Select connection or Available DataSource В списке перечислены соединения определенные в текущей базе данных.
20165. ИСПОЛЬЗОВАНИЕ КОМПОНЕНТ OLE 68 KB
  1 был введен новый метод передачи информации в виде объектов между 16разрядными приложениями основанный на модели Object Linking and Embedding OLE 1. Протокол OLE 2. OLE 2.