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

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


 

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

30473. Система сдержек и противовесов в форме правления США 15.06 KB
  Влиятельная фигура в ранней Америке Джон Адамс говорил что целью конституционного правительства является создание правительства законов а не правительства людей. Для Адамса великой идеей к наделению широкими полномочиями правительства и в то же время подчинению его букве закона стал принцип разделения правительственных полномочий. Эта концепция разделения властей исторически ассоциируемая со школой французского философа Монтескье предотвратила злоупотребление властью путем отказа от концентрации власти в одной ветви или одном...
30474. Особенности конституционного права Соединенного королевства 16.64 KB
  Британский конституционализм представляет собой весьма своеобразное явление правовой действительности. Древние и крепкие корни парламентаризма англосаксонская правовая система монархическая форма правления все это делает фактическую и юридическую конституцию Великобритании уникальной. Эта страна по сей день не имеет в качестве основного закона единого писаного нормативного правового акта. Возводимое в течение многих столетий здание британского конституционализма имеет в качестве прочного и надежного фундамента общее право...
30475. Британский парламент, его взаимоотношения с Королевой и Правительством 16.23 KB
  Законодательная власть в Великобритании принадлежит парламенту но по точному смыслу британской конституции парламент триединое учреждение: оно включает главу государства монарха палату лордов исторически палату знати и высшего духовенства и палату общин исторически палату простолюдинов. Это понятие связано с тем что закон становится таковым если он принят двумя палатами есть некоторые исключения из этого правила в пользу нижней палаты и подписан монархом. Теоретически монарх в Великобритании считается...
30476. Реформа политико-территориального устройства Соединенного Королевства 14.64 KB
  Поэтому для других трех регионов в большей или меньшей степени всегда были свойственны стремление к усилению самоуправления или даже сепаратизм. право первичного законодательства в сферах здравоохранения образования местного самоуправления и политикоадминистративного деления жилищного и коммунального хозяйства окружающей среды и т. В каждой Местной единице действуют органы местного самоуправления: выборные непосредственно населением советы и исполнительные органы. Компетенция органов местного самоуправления традиционна однако...
30477. Особенности французского конституционного права 17.34 KB
  В конституции отсутствует обычная для современных актов глава о правах и свободах. и к преамбуле конституции 1946 г. Конституционный совет в своих решениях указывал на Декларацию и преамбулу конституции 1946 г. как на составные части действующей конституции и включил их в тот блок законов соответствие которому он проверяет.
30478. Форма правления и государственный режим во Франции 15.08 KB
  Принцип республики: Правление народа по воле народа и для народа ст. Указанный характер республики определяется: глава государства президент избирается помимо парламента а премьерминистр назначается президентом без согласия высшего представительного органа признаки президентской республики; в то же время правительство несет ответственность перед нижней палатой парламента парламентская форма правления. Элементами президентской республики во Франции являются непарламентский способ избрания президента наличие у него...
30479. Трехмерные и динамические метафоры в визуализации программного обеспечения параллельных и распределенных вычислений 42 KB
  Существенным недостатком современных систем отладки параллельных и распределенных вычислений является отсутствие отображения динамики программных процессов. Причем каких-либо вариантов представления последовательности кода
30480. GESTURE-BASED INTERFACE: TECHNOLOGY AND APPLICATION 35.5 KB
  Recently gesture-based interfaces are becoming more widely used. There are many advantages of gesture-based interfaces such as small learning time, wide availability (if they done properly), and, in some cases, the lack of manipulators, which is important for mobile devices
30481. ФИЗИОЛОГИЯ СПИННОГО МОЗГА И ГОЛОВНОГО МОЗГА. НЕРВНАЯ РЕГУЛЯЦИЯ ВЕГЕТАТИВНЫХ ФУНКЦИЙ 53.89 KB
  Объем функций, осуществляемых спинным мозгом, чрезвычайно велик. В нем находят центры всех двигательных рефлексов (за исключением мускулатуры головы), всех рефлексов мочеполовой системы и прямой кишки, рефлексов, обеспечивающих терморегуляцию, регулирующих метаболизм тканей