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

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


 

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

66344. Мы экономим электрическую энергию 37.5 KB
  Человек много лет добывает из земли большое количество энергоресурсов. Слово Экспертам. Слово Корреспондентам Что же включает в себя экономия энергоресурсов Только ли это экономия электрической энергии Мы слышим от взрослых что дом дырявый что это значит...
66345. Моя щаслива планета 77.5 KB
  Мета: узагальнити знання дітей про шляхи і заходи щодо збереження енергії; мотивувати учнів відповідально ставитися до використання енергії у побуті; сприяти формуванню навичок ощадливого використання електроенергії у побуті.
66346. English Traditions and Customs 40 KB
  They also have their traditional Christmas dinner with stuffed turkey and Christmas pudding. The Queen’s speech is on television at three o’clock in the afternoon. There is a big Christmas tree in Trafalgar Square in London.
66347. Игра-викторина «Что ты знаешь о США?» 48.5 KB
  Цели: углубить и конкретизировать страноведческие знания учащихся по теме «США»; продолжить развитие творческих способностей учащихся; учить применять знания, полученные на уроках, в новой ситуации; дальнейшее расширение кругозора учащихся.
66348. Му Family 44 KB
  Мета: повторити раніше вивчені слова та структури, формувати уявлення про звукову систему англійської мови, ввести нові лексичні одиниці з теми "Му Family",вчити впізнавати їх та застосовувати у мовленні; формувати уміння в учнів самостійно працювати над завданнями...
66350. Іграшки. Урок англійської мови у 1 класі 36.5 KB
  Hello, everyone! I’m glad to see you! P: Hello! We are glad to see you too! T: How are you today? Come here and show us a picture with your mood. ( Учні виходять до дошки і обирають малюнок з смайликом, який показує настрій ).P1: I am fine, thank you. P2: I am so-so.
66351. З НОВИМ РОКОМ 38 KB
  Мета: повторити лексичний матеріал теми; ознайомити учнів з новими лексичними одиницями та тренувати їх вживання в усному мовленні; практикувати вживання в усному мовленні структури I see; повторити раніше вивчені літери; ознайомити учнів з літерами...
66352. Numbers. Цифры 127 KB
  Задача урока: Тренировка учащихся в употреблении лексики по теме Цифры в устных видах речевой деятельности; Совершенствование фонетических навыков навыков аудирования чтения и письма. Цели урока: Образовательные: Активизировать навыки чтения монологической и диалогической речи...