Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

Подписываем
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
35
Лабораторная работа № 4
Выбор рациональной длины пакета сети ЭВМ
1. Цель работы
Изучение методики расчета рациональной длины пакета в сети ЭВМ. В результате выполнения лабораторной работы студент получает знания по влиянию длины пакета на характеристики сети ЭВМ и навыки по определению рациональной длины пакета.
2. Задание
2.1. Изучить влияние длины пакета на характеристики сети ЭВМ.
2.2. Изучить методику расчета рациональной длины пакета сети ЭВМ.
2.3. Определить рациональную длину пакета сети ЭВМ.
2.4. Исследовать зависимость эффективной скорости передачи данных от длины пакета для основного цифрового канала связи и канала связи тональной частоты при различных вероятностных характеристиках передачи.
3. Рабочее место
Работа выполняется на ПЭВМ.
4. Теоретическая часть
4.1. Методика выбора рациональной длины пакета
При исследовании моделей в первых трех лабораторных работах данного сборника было установлено, что длина передаваемого по сети кадра (пакета) в значительной степени влияет на пропускную способность сети. Однако на практике длина пакетов выбирается постоянной. Разумный выбор этой величины позволяет повысить пропускную способность сети и уменьшить нагрузку в ней.
Длина пакета не может быть слишком малой, поскольку при фиксированной длине служебной части (заголовка) пакета снижается доля информации сообщения, передаваемой в одном пакете. Кроме того, увеличиваются временные затраты ЭВМ на сборку (разборку) сообщений и объем памяти на хранение описателей пакетов и их заголовков. При большой длине пакета и заданной достоверности передачи данных в канале связи повышаются вероятность передачи пакета с ошибкой и, следовательно, частота повторной передачи пакета, что снижает эффективность сети ЭВМ, а также возрастает доля потерь памяти из-за незаполненности информацией пространства, отводимого под последний пакет сообщения (под каждый пакет в памяти ЭВМ отводится страница фиксированного размера).
Рациональная длина пакета данных, передаваемого в сети ЭВМ, определяется выражением
, (4.1)
где 2 - рациональная длина пакета с точки зрения экономии памяти и минимизации системных издержек процессора при сборке (разборке) сообщения; 3 - рациональная длина пакета, обеспечивающая максимальную скорость передачи данных при заданной достоверности канала связи.
Полученное значение * округляется до ближайшего значения, равного 2m, где m - целое число.
Если считать, что длина передаваемого сообщения в сети ЭВМ распределена по экспоненциальному закону с математическим ожиданием, равным l (бит), то с точки зрения экономии памяти рациональный размер буфера, отводимого под пакет, а, следовательно, и рациональную длину пакета рассчитывают так:
, (4.2)
где С - длина заголовка пакета в битах.
С учетом системных издержек ЭВМ на сборку (разборку) сообщения, которые возрастают с уменьшением длины пакета, а также учитывая тенденцию на увеличение длины передаваемых сообщений, целесообразно рациональную длину пакета определять выражением
, (4.3)
где K1=1,3-1,5 - коэффициент, учитывающий системные издержки на сборку сообщений.
Эффективная скорость передачи пакета по каналу связи рассчитывается следующим образом:
, (4.4)
где - длина пакета (бит); SН - номинальная скорость передачи данных по каналу (бит/с); М - вероятность ошибки в пакете, М=1-(1-В), В - вероятность искажения одного бита передачи.
Длина пакета 3 рассчитывается с помощью (4.4) перебором вариантов с учетом вероятностных характеристик канала связи, задержек, вносимых оборудованием при изменении направления передачи, числа служебных символов для управления обменом данными (заголовок пакета) и т.п. Значение , при котором эффективная скорость передачи данных Sэ максимальна, и соответствует длине пакета 3.
4.2. Пример расчета рациональной длины пакета
Расчет производится для следующих исходных данных:
средняя длина передаваемого сообщения l=7700 бит;
длина заголовка пакета С=192 бит;
коэффициент, учитывающий системные издержки на сборку сообщения, К1=1,4;
время изменения направления передачи tп=0, tп=0,02;
номинальная скорость передачи данных по каналу: для основного цифрового канала связи SН=56 000 бит/с, для канала связи тональной частоты SН=4800 бит/с;
вероятность искажения одного бита передачи В=10-5, В=10-6;
длина пакета =102416 384 бит.
При С=192 .
Оптимальная длина пакета определяется выражением (4.1), где 3 определяется по графику зависимости эффективной скорости передачи от длины пакета (его нужно построить), при которой SЭ принимает максимальное значение.
На рис.4.1 приведена зависимость вероятности М от длины пакета и от вероятности В. С использованием М рассчитываются зависимости эффективной скорости передачи от длины пакета. Значение , при котором SЭ принимает максимальное значение, является величиной 3. Значения 3 и * для различных исходных данных приведены в табл.4.1.
Таблица 4.1
Расчетные значения 1, 2, 3, * при различных SН, С, В, tп
SН, бит/с, С, бит |
В |
tп |
1, бит |
2, бит |
3, бит |
*, бит |
56 000, 192 |
10-5 |
0 |
2623 |
3673 |
5120 |
4096 |
10-5 |
0,02 |
2623 |
3673 |
11264 |
4096 |
|
10-6 |
0 |
2623 |
3673 |
13312 |
4096 |
|
10-6 |
0,02 |
2623 |
3673 |
16384 |
4096 |
|
4800, 192 |
10-5 |
0 |
2623 |
3673 |
5120 |
4096 |
10-5 |
0,02 |
2623 |
3673 |
11264 |
4096 |
|
10-6 |
0 |
2623 |
3673 |
11264 |
4096 |
|
10-6 |
0,02 |
2623 |
3673 |
16384 |
4096 |
Результаты расчетов показали, что для цифрового канала связи и канала связи тональной частоты с достоверностью 10-5 или 10-6 на бит рациональная длина пакета составила 4096 бит (512 байт).
5. Порядок выполнения работы
5.1. Изучить теоретический материал по методике определения рациональной длины пакета сети ЭВМ.
5.2. Определить исходные данные для расчета рациональной длины пакета в соответствии с вариантом (табл. 4.2).
Таблица 4.2
Исходные данные для выбора рациональной длины пакета
№ варианта |
l, бит |
С, бит |
K1 |
t2n, с |
Sн, бит/с |
В |
||
1 |
2 |
1 |
2 |
|||||
1 |
7500 |
192 |
1,3 |
0,02 |
56000 |
4800 |
10-4 |
10-5 |
2 |
6000 |
96 |
1,4 |
0,01 |
70000 |
5600 |
10-4 |
10-6 |
3 |
8000 |
320 |
1,5 |
0,03 |
70000 |
3200 |
10-3 |
10-5 |
4 |
8500 |
168 |
1,3 |
0,025 |
50000 |
6400 |
10-3 |
10-4 |
5 |
9000 |
192 |
1,4 |
0,015 |
75000 |
4800 |
10-4 |
10-5 |
6 |
8700 |
96 |
1,5 |
0,04 |
60000 |
6400 |
10-3 |
10-5 |
7 |
5700 |
320 |
1,3 |
0,02 |
56000 |
3200 |
10-4 |
10-6 |
8 |
5500 |
22 |
1,4 |
0,01 |
77000 |
6400 |
10-3 |
10-4 |
9 |
9500 |
168 |
1,5 |
0,03 |
70000 |
4800 |
10-5 |
10-6 |
10 |
9300 |
192 |
1,3 |
0,025 |
50000 |
5600 |
10-5 |
10-6 |
11 |
7500 |
96 |
1,4 |
0,015 |
75000 |
3200 |
10-4 |
10-5 |
12 |
5000 |
320 |
1,5 |
0,04 |
60000 |
6400 |
10-4 |
10-5 |
13 |
8000 |
168 |
1,3 |
0,02 |
56000 |
5600 |
10-3 |
10-4 |
14 |
8500 |
22 |
1,4 |
0,01 |
56000 |
5600 |
10-4 |
10-6 |
15 |
9000 |
96 |
1,5 |
0,03 |
70000 |
3200 |
10-3 |
10-4 |
16 |
8700 |
192 |
1,3 |
0,025 |
50000 |
6400 |
10-5 |
10-6 |
17 |
5700 |
320 |
1,4 |
0,015 |
75000 |
4800 |
10-4 |
10-5 |
18 |
6500 |
22 |
1,5 |
0,04 |
60000 |
5600 |
10-4 |
10-5 |
19 |
9500 |
168 |
1,3 |
0,02 |
56000 |
3200 |
10-4 |
10-6 |
20 |
9300 |
192 |
1,4 |
0,01 |
70000 |
6400 |
10-5 |
10-6 |
21 |
8000 |
96 |
1,5 |
0,03 |
70000 |
4800 |
10-3 |
10-4 |
22 |
8700 |
22 |
1,3 |
0,025 |
50000 |
5600 |
10-4 |
10-5 |
23 |
6000 |
320 |
1,4 |
0,015 |
75000 |
3200 |
10-3 |
10-5 |
24 |
5700 |
168 |
1,5 |
0,04 |
60000 |
6400 |
10-5 |
10-6 |
25 |
6700 |
96 |
1,3 |
0,02 |
56000 |
4800 |
10-4 |
10-5 |
Примечание. SН(1) - номинальная скорость передачи данных для основного цифрового канала связи; SН(2) - для канала связи тональной частоты; для всех вариантов t1n=0 и изменяется в диапазоне 102416384 бит.
5.3. Построить график зависимости вероятности ошибки в пакете М от длины пакета с шагом 2048 бит.
5.4. Определить, исходя из аналитических выражений, длину пакета 1 и 2. Построить графики:
1) зависимости SЭ от с шагом 2048 бит для цифрового канала связи при четырех различных сочетаниях исходных значениях: В и tп (четыре кривые на одном графике);
2) зависимости SЭ от с шагом 2048 бит для канала связи тональной частоты при четырех различных сочетаниях исходных значениях: В и tп (четыре кривые на одном графике).
5.5. По графикам определить величину 3. Заполнить таблицу расчетных значений и по (4.1) определить рациональную длину пакета для основного цифрового канала связи и для канала связи тональной частоты.
5.6. Сделать выводы по результатам расчетов и полученным графикам.
6. Содержание отчета
6.1. Цель работы, задание.
6.2. Исходные данные для определения рациональной длины пакета сети ЭВМ.
6.3. Расчетная таблица.
6.4. Таблицы и графики полученных зависимостей.
6.5. Выводы по результатам работы.
7. Контрольные вопросы
7.1. Какие вероятностные характеристики канала связи и сети ЭВМ в целом влияют на выбор рациональной длины пакета?
7.2. Что такое рациональная длина пакета и от чего она зависит?
7.3. Объясните методику выбора рациональной длины пакета.
7.4. Как изменяется эффективная скорость передачи пакета по каналу связи от длины пакета в зависимости: а) от вероятности искажения одного бита передачи; б) времени изменения направления передачи; г) номинальной скорости передачи по каналу?
7.5. Как выбирается рациональная длина пакета с точки зрения экономии памяти ЭВМ?
7.6. Как системные издержки влияют на выбор рациональной длины пакета в сети ЭВМ?
Лабораторная работа № 5
Функционирование мостов и коммутаторов
на основе протокола канального уровня STP
стека протоколов TCP/IP
1. Цель работы
Изучение основных принципов работы мостов и коммутаторов в сетях ЭВМ на основе протокола STP. В результате выполнения лабораторной работы студент получает знания по принципам построения и алгоритмам функционирования мостов и коммутаторов в сетях ЭВМ и навыки по устранению активных петель в сети при помощи протокола STP.
2. Задание
2.1. Изучить структуру и алгоритмы работы мостов в сетях ЭВМ.
2.2. Изучить структуру и алгоритмы работы коммутаторов в сетях ЭВМ.
2.3. Изучить алгоритм устранения активных петель в сетях ЭВМ при помощи протокола канального уровня STP.
2.4. Пользуясь алгоритмом устранения активных петель, скорректировать заданную сеть для случаев: а) устранения активных петель; б) обрыва линии связи между узлами сети.
3. Рабочее место
Работа выполняется на ПЭВМ.
4. Теоретическая часть
4.1. Структура и принципы работы мостов
Объединение современных сетей осуществляется как с помощью маршрутизаторов, так и с помощью мостов и коммутаторов. Основное различие между ними заключается в том, что объединение сетей с помощью мостов и коммутаторов происходит на канальном уровне эталонной модели взаимосвязи открытых систем (ВОС, англоязычная аббревиатура - OSI), а маршрутизатор использует сетевой уровень; кроме того, эти устройства поддерживают различные алгоритмы при перемещении информации по сети.
Мост - это устройство, обеспечивающее взаимосвязь нескольких локальных сетей посредством передачи кадров из одной сети в другую. В отличие от концентраторов, которые проверяют электрические сигналы, мост проверяет только кадры. Мосты не повторяют шумы, ошибки или испорченные кадры. Мост выступает по отношению к каждой из соединяемых им сетей в качестве конечного узла. Он принимает кадр, сохраняет его в буферной памяти, анализирует адрес назначения кадра. В случае принадлежности кадра к сети, из которой он получен, мост на этот кадр не реагирует. Если необходимо передать кадр в другую сеть, мост должен получить доступ к ее разделяемой среде передачи данных в соответствии с теми же правилами, что и обычный узел.
Существует два основных типа мостов - локальные и глобальные (удаленные). Они отличаются своими сетевыми портами. Локальные мосты оборудуются портами для подключения к ЛВС. Типичными для такой среды носителями являются коаксиальный или волоконно-оптический кабель, а также витая пара проводов. Важным свойством локальных мостов является их способность соединять сети, использующие разные среды. Например, с их помощью можно подключить сеть на коаксиальном кабеле к сети с волоконно-оптическим кабелем или любую из них к сети на витой паре.
Глобальные мосты - это те мосты, порты которых согласуются со средами для передачи информации на большие расстояния. У глобальных мостов могут быть интерфейсы как для передачи на большие расстояния, так и локальные.
По своему принципу действия мосты подразделяются на два основных типа. Мосты первого типа выполняют так называемую маршрутизацию от источника. B такой сети мостам не требуется содержать адресную базу данных. Они определяют путь прохождения кадра, исходя из информации, хранящейся в самом кадре.
Мосты второго типа называются «прозрачными». Прозрачные мосты, в свою очередь, делятся на три подтипа:
прозрачные мосты - используются для объединения сетей с идентичными протоколами на канальном и физическом уровнях модели ВОС (Ethernet - Ethernet, Token Ring - Token Ring и т.д.);
транслирующие мосты - используются для объединения сетей с разными протоколами на канальном и физическом уровне;
инкапсулирующие мосты - предназначены для объединения сетей с одинаковыми протоколами (например, Ethernet) на канальном и физическом уровне через сеть с другими протоколами (например, FDDI).
Прозрачные мосты являются наиболее распространенным типом. Для них сеть представляется наборами физических адресов устройств, используемых на канальном уровне. Мосты ориентируются на эти адреса для принятия решения о передаче кадра. При этом кадр записывается во внутренний буфер моста. Мосты не имеют доступа к информации об адресах сетей, относящейся к сетевому уровню. Они ничего «не знают» о топологии связей сегментов или сетей между собой.
При передаче кадров внутри прозрачного моста происходит их регенерация и трансляция с одного порта на другой. Мост использует адрес отправителя для автоматического построения своей базы данных адресов устройств, называемой также таблицей физических адресов. В этой таблице устанавливается принадлежность адреса станции к какому-либо порту моста. Все операции, которые выполняет мост, связаны с этой базой данных. Внутренняя структура моста показана на рис. 5.1.
Все порты моста работают в так называемом неразборчивом режиме захвата кадров, то есть все поступающие на порт кадры сохраняются в его буферной памяти. С помощью такого режима мост следит за всем трафиком, передаваемым в присоединенных к нему сегментах, и использует проходящие через него кадры для изучения состава сети.
Функциональную основу мостов составляют следующие функции: обучение, фильтрация, передача и широковещание.
Когда мост получает кадр, он проверяет его целостность и контрольную сумму. Некорректные кадры при этом отбрасываются. Затем мост сравнивает адрес отправителя с имеющимися в базе данных адресами. Если адреса отправителя еще нет в базе данных, то он добавляется в нее. Таким образом, мост узнает адреса устройств в сети, и происходит процесс его обучения (рис. 5.2). Благодаря способности моста к обучению к сети могут добавляться новые устройства без необходимости реконфигурации моста.
Кроме адреса отправителя мост анализирует и адрес получателя. Мост сравнивает адрес получателя кадра с адресами, хранящимися в его базе. Если адрес получателя принадлежит тому же сегменту, что и адрес отправителя, то мост «фильтрует» кадр, то есть удаляет его из своего буфера и никуда не передает. Эта операция помогает предохранить сеть от «засорения» ненужным трафиком. Если адрес получателя присутствует в базе данных и принадлежит другому сегменту, то мост определяет, какой из его интерфейсов связан с нужным адресом. После этого мост должен получить доступ к среде передачи этого сегмента и передать в него кадр. Если адрес получателя отсутствует в базе или он является широковещательным, то мост передает кадр на все свои порты, за исключением порта, принявшего кадр. Такой процесс называется широковещанием.
Так как существует возможность перемещения станции из одного сегмента в другой, то мосты должны периодически обновлять содержимое своих адресных баз. Для обеспечения этой функции записи в адресной базе делятся на два типа - статические и динамические. С каждой динамической записью связан таймер неактивности. При получении кадра с адресом отправителя, который соответствует имеющейся в адресной базе записи, соответствующий таймер неактивности сбрасывается в исходное состояние. Если от какой-либо станции долгое время не поступают кадры, то таймер неактивности исчерпывает заданный интервал и соответствующая ему запись удаляется из адресной базы. Например, у мостов NetBuilder II фирмы 3Com таймер неактивности выставляется по умолчанию и равен 300 секундам.
Рис. 5.2 иллюстрирует алгоритм функционирования моста.
Кроме основных функций мосты могут поддерживать дополнительные сервисы, например: настраиваемые фильтры, расширенные возможности по защите данных и обработка кадров по классам. Настраиваемые фильтры позволяют администратору сетей производить фильтрацию на основе любого компонента кадра, например, типа протокола верхнего уровня, адреса отправителя или получателя, типа кадра или даже информационной его части.
Технология прозрачных мостов стандартизована и описана в документе IEEE 802.1d. На рис. 5.3 показано «место» мостов в эталонной модели ВОС.
4.2. Структура и принципы работы коммутаторов
Коммутатор - это устройство, конструктивно выполненное в виде сетевого концентратора и действующее как высокоскоростной многопортовый мост; встроенный механизм коммутации позволяет осуществить широковещательное сегментирование локальной сети, а также выделить полосу пропускания к конечным станциям в сети.
Под коммутацией обычно понимают четыре различные технологии: конфигурационную коммутацию (коммутацию каналов), коммутацию кадров, коммутацию ячеек и преобразование между кадрами и ячейками. В основе конфигурационной коммутации лежит определение соответствия между конкретным портом коммутатора и внутренним сегментом сети. Это назначение портов производится удаленным образом посредством программного управления сетью при подключении или перемещении пользователей в сети. Технология конфигурационной коммутации основана на отказе от использования разделяемых линий связи между всеми узлами сегмента и использовании коммутаторов, позволяющих одновременно передавать пакеты между всеми его парами портов. Новшество заключалось в параллельной обработке поступающих кадров.
Структурная схема коммутатора фирмы Kalpana EtherSwitch показана на рис. 5.4. Системный модуль поддерживает общую адресную таблицу коммутатора. Коммутационная матрица предназначена для передачи кадров между портами. Каждый порт имеет свой процессор пакетов. При поступлении кадра в один из портов процессор пакетов буферизует несколько первых байтов кадра для прочтения адреса назначения. После получения адреса процессор принимает решение о передаче кадра, не дожидаясь прихода остальных байтов. Для этого анализируется адресная таблица. Если адрес существует в таблице, то выбирается соответствующий выходной порт. Выбор порта и формирование соединения производятся коммутационной матрицей. Если адреса нет в таблице, то заводится новая строка в адресной таблице, а кадр передается широковещательным методом через все порты, за исключением принявшего.
В настоящее время различают три типа коммутаторов: с коммутационной матрицей, с общей шиной и с разделяемой многовходовой памятью.
Коммутаторы с коммуникационной матрицей за счет параллельной обработки данных позволяют реализовать наиболее быстрый способ взаимодействия портов. Эта реализация возможна только для определенного числа портов. Причем сложность схемы возрастает пропорционально квадрату количества портов коммутатора. Основным недостатком данной технологии является отсутствие возможности буферизации данных внутри коммутационной матрицы.
В коммутаторах с общей шиной в режиме разделения времени используется высокоскоростная шина для связи процессоров портов. В этой архитектуре активную роль играют специализированные процессоры портов. Высокоскоростная шина играет пассивную роль. Для того чтобы шина не была узким местом коммутатора, ее производительность должна быть в несколько раз выше скорости поступления данных на входные порты. Для уменьшения задержек при передаче кадр должен передаваться по шине небольшими частями. Размер этих частей определяется производителем коммутатора. Шина так же, как и коммутационная матрица, не может осуществлять промежуточную буферизацию.
В коммутаторах с разделяемой многовходовой памятью (рис. 5.5) входные блоки процессоров портов соединяются через переключатели входа с разделяемой памятью, а выходные блоки этих же процессоров соединяются с этой памятью через переключатели выхода. Переключением входа и выхода разделяемой памяти управляет блок управления портами. Он организует в разделяемой памяти несколько очередей данных, по одной для каждого выходного порта. Входные блоки процессоров передают блоку управления запросы на запись данных в очередь того порта, который соответствует адресу назначения пакета. Блок управления портами по очереди подключает вход памяти к одному из входных блоков процессора, и тот переписывает часть данных в очередь определенного выходного порта. По мере заполнения очередей блок управления производит поочередное подключение выходов разделяемой многовходовой памяти к выходным портам, и данные из очереди переписываются в выходной буфер процессора.
Некоторые производители используют в своих коммутаторах различные приемы управления потоком кадров для предотвращения потерь при перегрузках в сети. Существует два способа реализации снижения интенсивности трафика: агрессивное поведение порта и метод обратного давления.
Агрессивное поведение порта коммутатора может быть реализовано путем захвата среды передачи данных или после коллизии в сети (для сети Ethernet). Например, в первом случае коммутатор окончил передачу очередного кадра и сделал технологическую паузу в 9,1 мкс вместо положенной паузы в 9,6 мкс. При этом компьютер, сделав ту же паузу в 9,6 мкс, не смог захватить среду передачи данных. Во втором случае кадры коммутатора и компьютера столкнулись, и была зафиксирована коллизия. Компьютер делает стандартную паузу после коллизии в 51,2 мкс, а коммутатор - в 50 мкс. И в этом случае среда передачи остается за коммутатором.
В основе второго метода лежит передача компьютеру фиктивных кадров при отсутствии в буфере коммутатора кадров для передачи по данному порту. В этом случае коммутатор может не нарушать алгоритм доступа, однако интенсивность передачи кадров в коммутатор в среднем уменьшается вдвое.
Существует два способа передачи пакетов коммутаторами: со сквозной обработкой и с буферизацией. Коммутатор со сквозной обработкой кадров считывает только физический адрес назначения, а сам кадр передается без проверки его содержимого. Этот способ представляет собой, по сути, конвейерную обработку кадров с частичным совмещением этапов передачи. Передача кадров происходит в такой последовательности:
1) прием первых байтов кадра (включая байт адреса назначения);
2) поиск адреса назначения в адресной таблице;
3) построение коммутируемого пути;
4) прием остальных байтов кадра;
5) прием всех байтов кадра выходным портом через коммутационную матрицу;
6) получение доступа к среде передачи;
7) передача кадра в сеть.
Использование сквозной коммутации может дать значительный выигрыш в производительности, но за счет снижения надежности.
При коммутации с буферизацией происходит проверка содержимого кадра: если в кадре содержится ошибка, то он отбраковывается.
Коммутаторы, наряду с основными функциями по передаче кадров с порта на порт, могут реализовывать дополнительные функции, например поддержку протокола STP (Spanning Tree) - построение остова дерева. Алгоритм Spanning Tree позволяет коммутаторам автоматически определять древовидную конфигурацию связей в сети при произвольном соединении портов между собой. Поддержка мостами и коммутаторами этой функции важна для обеспечения работоспособности сложных сетей.
4.3. Протокол SPT для мостов и коммутаторов
Функции обучения, фильтрации и передачи основаны на существовании одного логического пути между любыми двумя узлами сети. Наличие нескольких путей между устройствами, известных также как «активные петли», создает проблемы для сетей, построенных на основе мостов и коммутаторов. Под «активными петлями» понимаются логические и физические петли. Логические петли могут создаваться администратором сети специально для образования резервных связей.
Протокол STP [2] (в некоторых технических документах может встретиться название Spanning Tree Algorithm - STA) был разработан Digital Equipment Corporation, а впоследствии опубликован комитетом IEEE 802 в спецификации IEEE 802.1d. Основная цель разработки протокола была в устранении логических и физических петель в сетях, построенных с использованием мостов. Кроме того, протокол автоматически переконфигурирует сетевую топологию в случае обрывов линий связи или при аппаратных ошибках оборудования.
Принцип действия протокола STP рассмотрим на примере сети на рис. 5.6. Предположим, что станция А генерирует широковещательное сообщение. Оно будет получено коммутаторами Б и В и передано соответственно друг другу, как показано стрелками. После получения сообщения эти коммутаторы вновь перешлют его коммутатору А, и весь цикл повторится вновь. Похожая проблема возникает и в случае не широковещательного трафика, если коммутаторы еще не построили своих адресных таблиц. Решением проблемы является удаление всех петель из сетевой топологии с сохранением только одного пути между каждыми двумя станциями.
Для того чтобы протокол STP построил свободную от петель сетевую топологию, необходима поддержка стандарта IEEE 802.1d всеми коммутаторами и мостами, работающими в сети. Для функционирования протокола STP должен существовать способ обмена информацией между коммутаторами. Это достигается с помощью специальных пакетов Bridge Protocol Data Unit (BPDU), которые помещаются внутрь кадров канального уровня, например кадров Ethernet или FDDI. При этом желательно, чтобы все коммутаторы могли поддерживать общий групповой адрес, с помощью которого кадры, содержащие пакет BPDU, могут одновременно передаваться всем заинтересованным коммутаторам в сети. Иначе эти кадры рассылаются широковещательно. Формат пакета BPDU показан на рис. 5.7.
Поля пакета BPDU имеют следующие значения:
ИД протокола - идентификатор протокола. Поле имеет нулевое значение;
версия - поле имеет нулевое значение. Коммутаторы в сети должны поддерживать одну и ту же версию протокола, иначе может быть сформирована конфигурация с петлями;
тип сообщения - содержит нулевое значение при нормальной работе протокола. Поле устанавливается в значение 80h при извещении об изменениях в сетевой топологии;
флаги - используются только два бита. Первый бит сигнализирует об изменениях в сетевой топологии и обозначается ТС. Восьмой бит используется для подтверждения приема пакета BPDU с установленным битом ТС. Он имеет обозначение ТСА. Остальные шесть битов этого байта не используются;
корневой ИД - идентификатор корневого коммутатора. Два первых байта поля - идентификатор коммутатора, оставшиеся шесть байтов - его физический адрес;
стоимость пути до корня - характеризует суммарную стоимость пути до корневого коммутатора;
ИД коммутатора - идентификатор коммутатора, отправляющего сообщение;
ИД порта - идентифицирует порт коммутатора, из которого отправлено сообщение;
возраст сообщения - время, прошедшее с момента отправки корневым коммутатором сообщения об обнаружении изменений в сетевой топологии;
максимальный возраст - указывает время удаления из обращения текущего сообщения;
время приветствия - промежуток времени между рассылками сообщений корневым коммутатором;
задержка перехода - задержка, которую коммутаторы должны выждать перед переходом в новое состояние после изменения сетевой топологии. Такая задержка необходима, чтобы уменьшить вероятность временного возникновения петель во время реконфигурации.
Для построения предполагаемой топологии сетевой администратор должен задать два параметра: идентификатор коммутатора и стоимости портов. Идентификатор коммутатора - это уникальное восьмибайтовое число, задаваемое следующим образом: берется физический адрес устройства (шесть байт) и в начало добавляется определяемое сетевым администратором двухбайтовое число. Стоимость портов может назначаться либо сетевым администратором, либо автоматически по умолчанию. Сетевой администратор может назначить любое число в пределах от 0 до 65 535. По умолчанию это число устанавливается пропорционально поддерживаемой скорости передачи и вычисляется по следующей формуле:
Стоимость порта = (1000)/(Скорость передачи в порте в Мбайт/с).
Первым шагом работы протокола STP является выбор корневого коммутатора. Это достигается широковещательной рассылкой всеми коммутаторами пакетов BPDU на все порты. Сначала каждый коммутатор рекламирует самого себя в качестве корневого, помещая свой идентификатор в два поля: «Корневой ИД» и «ИД коммутатора» (см. рис. 5.8). При получении каким-либо коммутатором пакета, содержащего меньший идентификатор поля «Корневой ИД», чем его собственный, данный коммутатор перестает рассылать собственный идентификатор и начинает рассылать пакеты, содержащие меньший идентификатор. Состязание за право быть корневым коммутатором заканчивается, когда один из коммутаторов получит свой собственный BPDU-пакет, не измененный при прохождении через другие коммутаторы. Такой коммутатор считается корневым. В ситуации, показанной на рис. 5.8, корневым становится коммутатор А как имеющий наименьший идентификатор.
Выбранный корневой коммутатор начинает рассылку пакетов BPDU на все свои порты. В этих пакетах в поле «Стоимость пути до корня» содержится информация о стоимости портов. Корневой коммутатор при рассылке устанавливает содержимое этого поля в ноль, а следующие коммутаторы добавляют свою стоимость портов к этому числу и рассылают пакеты дальше. Эти пакеты воспринимаются корневыми портами коммутаторов. В этой роли выступают порты, через которые можно попасть в корневой коммутатор с наименьшей суммарной стоимостью портов.
В примере коммутаторы Б и В добавляют свои стоимости портов - числа 25 и 30 соответственно - и пересылают сообщения друг другу. После анализа этих сообщений коммутатор с наибольшей стоимостью пути до корня переводит свой порт в блокированное состояние. В примере этим коммутатором является коммутатор В с портом 2. Порт, находящийся в блокированном состоянии, не передает кадры через себя, однако он продолжает принимать и обрабатывать пакеты BPDU. У коммутатора Б порт 2 становится назначенным, и только через него происходит передача кадров в подключенный сегмент сети. Таким образом, хотя коммутатор Б будет продолжать передавать кадры данных через свой порт 2, они не пройдут дальше коммутатора В, который будет их отсекать, устраняя петлю, существовавшую ранее. У корневого коммутатора все порты являются назначенными.
У коммутатора, работающего по стандарту IEEE 802.1d, может существовать четыре состояния каждого порта:
1. Блокированное - в этом состоянии порт не участвует в нормальных операциях обучения, фильтрации и передачи. Пользовательский трафик не передается от коммутатора в сегмент, подключенный к этому порту, и обратно. Корневые и назначенные порты никогда не переходят в блокированное состояние. Порт в этом состоянии воспринимает пакеты BPDU, не передавая их далее. Если эти сообщения порт не получит в заданный период времени, он переходит в следующее состояние состояние прослушивания.
2. Прослушивания - порт, находясь в этом состоянии, слушает пакеты BPDU для определения необходимости перехода в блокированное состояние или в состояние обучения. В этом состоянии порт не участвует в обучении местоположению станций, фильтрации или передачи пользовательской информации. Это состояние предназначено для минимизации получения некорректной информации о расположении станций при переконфигурации протокола STP. Время нахождения в этом состоянии равно значению параметра поля «Задержка перехода» и по умолчанию составляет 15 секунд.
3. Обучения - порт готовится к переходу в состояние передачи. Происходят процессы запоминания расположения станций и обновления адресной таблицы данного коммутатора. Длительность периода обучения порта равна длительности периода прослушивания.
4. Передачи - в этом состоянии порт участвует во всех функциях коммутатора. Только корневые и назначенные порты коммутаторов могут находиться в этом состоянии.
Сетевая топология, полученная в результате работы протокола STP на локальной сети приведенного выше примера, показана на рис. 5.9. После создания новой сетевой топологии корневой коммутатор начинает периодическую рассылку пакетов BPDU. Интервал между рассылками задается администратором при настройке и помещается в поле «Время приветствия» (по умолчанию выставляется 2 секунды). Остальные коммутаторы, получая эти пакеты, увеличивают содержимое поля «Возраст сообщения» и передают их дальше по сети. Если значение этого поля достигнет значения поля «Максимальный возраст», также задаваемого администратором, то сообщение будет удалено из обращения. Хотя после выбора корневого коммутатора остальные коммутаторы работают с его временными настройками, рекомендуется, чтобы все коммутаторы в сети имели эти значения одинаковыми.
Протокол STP будет производить изменение конфигурации сети в случаях выхода из строя корневого коммутатора или обрыва линии связи.
Если корневой коммутатор вышел из строя, то остальные своевременно не получат пакеты BPDU на свои корневые порты. Каждый коммутатор ожидает хотя бы одно сообщение от корневого коммутатора до истечения его временной настройки «Максимальный возраст». По истечении этого времени будет произведено изменение конфигурации сети с выбором нового корневого коммутатора.
Если произошел обрыв линии связи, коммутаторы на «дальнем» конце сети будут извещать о том, что пакеты BPDU не были получены на их корневые порты. Протокол STP также может производить реконфигурацию при следующих условиях:
если у корневого порта коммутатора истекло время ожидания, другой порт может быть выбран корневым;
если своевременно не обновляется информация от текущего корневого коммутатора, один из коммутаторов сделает попытку стать корневым;
если у некорневого порта коммутатора истекло время ожидания, этот порт будет пытаться стать назначенным портом для сегмента, который к нему подключен. Этот коммутатор будет передавать пакеты BPDU, полученные от корневого коммутатора в этот сегмент.
Таким образом, в случае выхода из строя коммутатора или обрыва линии связи, протокол STP будет производить реконфигурацию сетевой топологии. Все коммутаторы перестают передавать кадры, очищают свои адресные таблицы, перевыбирают корневой коммутатор, определяют корневые, назначенные и блокированные порты и вновь начинают нормально функционировать. Приостановка передачи кадров на время реконфигурации производится во избежание образования временных петель коммутации. Время приостановки передачи определяется значением параметра в поле «Задержка перехода».
Проиллюстрируем это на примере. Предположим, что произошел обрыв линии связи между коммутаторами А и Б (рис. 5.9). В этом случае коммутатор Б своевременно не получит на свой корневой порт сообщения от корневого коммутатора и активизирует процесс реконфигурации, рассылая пакеты BPDU с содержимым поля «Тип сообщения», равным 80h, означающим реконфигурацию. После этого процессы выбора корневого коммутатора назначенных и блокированных портов коммутаторов повторятся вновь, но уже с учетом отсутствия связи между коммутаторами А и Б. В результате реконфигурации получится последовательное соединение коммутаторов А, В и Б и порт 2 коммутатора Б станет корневым.
Для повышения надежности сетей, построенных на основе коммутаторов, применяют либо метод введения резервных линий связи между коммутаторами, либо метод введения резервных коммутаторов.
В целом протокол STP имеет следующие достоинства:
позволяет создавать большие, сложные и строить устойчивые к сбоям и отказам локальные сети на коммутаторах;
предоставляет только один путь передачи данных между любыми двумя станциями, который: а) гарантирует доставку данных в том порядке, в котором они были отправлены; б) устраняет размножение широковещательных пакетов; в) устраняет бесконечную циркуляцию широковещательных пакетов; г) устраняет циркуляцию пакетов с неизвестным адресом назначения;
работает прозрачно для конечных станций;
использует небольшой процент полосы пропускания.
В качестве недостатков можно отметить следующие моменты:
коммутаторы, поддерживающие протокол STP, имеют повышенную стоимость;
для введения резервных линий связи должны быть задействованы дополнительные порты коммутатора;
введение резервного оборудования существенно увеличивает стоимость сети в целом;
в моменты реконфигурации топологии сеть становится неработоспособной;
между двумя любыми станциями в сети может быть не более семи коммутаторов или мостов (в сетях на базе Ethernet 10 Мбит/с).
5. Порядок выполнения работы
5.1. Изучить структуру и алгоритмы работы мостов и коммутаторов в сетях ЭВМ.
5.2. Изучить теоретический материал по алгоритму устранения активных петель в сетях ЭВМ на основе протокола канального уровня STP.
5.3. Для сети, согласно варианту (табл. 5.1, рис. 5.10), поэтапно промоделировать работу протокола STP, поясняя действия рисунками и форматами служебных сообщений, для случаев: а) устранения активных петель; б) обрыва линии связи.
5.4. Построить граф-схему алгоритма устранения активных петель в сетях ЭВМ.
5.5. Сделать выводы по результатам моделирования.
Таблица 5.1
Исходные данные для моделирования работы протокола STP
№ вари- анта |
Коммутаторы |
№ гра- фа |
№ лин. обр. |
|||||||||
А |
Б |
В |
Г |
Д |
||||||||
IDк |
Sп |
IDк |
Sп |
IDк |
Sп |
IDк |
Sп |
IDк |
Sп |
|||
1 |
7400 |
20 |
7500 |
30 |
7700 |
40 |
- |
- |
- |
- |
1 |
1 |
2 |
7500 |
40 |
7400 |
50 |
7700 |
60 |
- |
- |
- |
- |
1 |
2 |
3 |
7700 |
25 |
7500 |
10 |
7400 |
30 |
- |
- |
- |
- |
1 |
3 |
4 |
7300 |
10 |
8000 |
20 |
9000 |
40 |
- |
- |
- |
- |
1 |
1 |
5 |
6000 |
25 |
9000 |
15 |
5000 |
30 |
- |
- |
- |
- |
1 |
2 |
6 |
7400 |
20 |
7800 |
10 |
7000 |
30 |
- |
- |
- |
- |
1 |
3 |
7 |
5000 |
10 |
7000 |
20 |
7500 |
30 |
4000 |
25 |
- |
- |
2 |
1 |
8 |
5000 |
20 |
7500 |
10 |
7000 |
25 |
4000 |
30 |
- |
- |
2 |
2 |
9 |
5000 |
30 |
4000 |
20 |
7000 |
25 |
7500 |
10 |
- |
- |
2 |
3 |
10 |
4000 |
30 |
5000 |
25 |
7500 |
10 |
7000 |
20 |
- |
- |
2 |
4 |
11 |
7000 |
25 |
7500 |
20 |
4000 |
30 |
5000 |
10 |
- |
- |
2 |
1 |
12 |
7500 |
25 |
7000 |
10 |
5000 |
40 |
4000 |
30 |
- |
- |
2 |
2 |
13 |
3000 |
15 |
4000 |
20 |
3500 |
30 |
4200 |
25 |
- |
- |
3 |
1 |
14 |
4200 |
10 |
3000 |
15 |
3500 |
20 |
4000 |
30 |
- |
- |
3 |
2 |
15 |
4000 |
25 |
3500 |
15 |
3000 |
10 |
4200 |
20 |
- |
- |
3 |
3 |
16 |
3500 |
15 |
4200 |
10 |
4000 |
20 |
3000 |
25 |
- |
- |
3 |
4 |
17 |
4000 |
25 |
3000 |
20 |
4200 |
10 |
3500 |
15 |
- |
- |
3 |
1 |
18 |
3000 |
10 |
4200 |
15 |
4000 |
20 |
3500 |
25 |
- |
- |
3 |
2 |
19 |
3600 |
25 |
4000 |
10 |
5000 |
35 |
2000 |
20 |
- |
- |
3 |
3 |
20 |
1500 |
15 |
1200 |
10 |
1600 |
20 |
1400 |
25 |
1700 |
40 |
4 |
1 |
21 |
1400 |
20 |
1500 |
30 |
1200 |
35 |
1600 |
40 |
1700 |
15 |
4 |
2 |
22 |
1200 |
30 |
1400 |
35 |
1500 |
20 |
1700 |
15 |
1600 |
40 |
4 |
3 |
23 |
1600 |
35 |
1700 |
40 |
1400 |
15 |
1200 |
30 |
1500 |
20 |
4 |
4 |
24 |
1700 |
40 |
1600 |
15 |
1500 |
20 |
1400 |
35 |
1200 |
30 |
4 |
5 |
25 |
1400 |
15 |
1700 |
20 |
1600 |
25 |
1200 |
40 |
1500 |
30 |
4 |
1 |
Примечание. IDк - идентификатор коммутатора; Sп - стоимость портов коммутатора; в последнем столбце таблицы указан номер линии обрыва.
6. Содержание отчета
6.1. Цель работы, задание.
6.2. Исходные данные и исходный граф сети.
6.3. Граф-схема алгоритма устранения активных петель в сетях ЭВМ.
6.4. Итоговые графы сети.
6.5. Иллюстрации, отражающие этапы работы протокола STP, форматы служебных сообщений.
6.6. Выводы по результатам работы.
7. Контрольные вопросы
7.1. Объясните основные структурные и функциональные различия между мостом и коммутатором.
7.2. В чем заключается прозрачность моста?
7.3. На каком-либо примере с использованием граф-схемы алгоритма работы моста объясните принцип работы мостов и коммутаторов в режиме обучения, фильтрации, передачи и широковещания.
7.4. Какие способы снижения интенсивности трафика в сети Вы знаете? Объясните эти способы. Ответ проиллюстрируйте временными диаграммами работы коммутаторов.
7.5. При использовании какого из двух способов передачи пакетов коммутаторами: со сквозной обработкой или с буферизацией, повышается надежность сети? За счет чего это достигается?
7.6. Что такое "активные петли" в сети, как они возникают и каким образом их наличие сказывается на функционировании сети?
7.7. Объясните назначение и принцип функционирования протокола канального уровня STP.
7.8. В какие состояния, согласно протоколу STP, в зависимости от ситуации в сети могут переходить порты мостов и коммутаторов? С учетом пребывания портов коммутатора во всех этих состояниях нарисуйте для него конечный автомат.
7.9. Какие параметры служебного пакета BPDU может вручную устанавливать администратор сети?
7.10. Какие действия, согласно протоколу STP, предусмотрены в случаях: а) образования "активной петли"; б) обрыва сетевого кабеля между коммутаторами; в) выхода из строя корневого коммутатора?
Лабораторная работа № 6
Функционирование маршрутизаторов на основе
протокола сетевого уровня OSPF
стека протоколов TCP/IP
1. Цель работы
Изучение основных принципов работы маршрутизаторов в сетях ЭВМ на основе протокола OSPF. В результате выполнения лабораторной работы студент получает знания по принципам построения и алгоритмам функционирования маршрутизаторов в сетях ЭВМ и навыки по выбору кратчайших путей в сети на основе протокола OSPF.
2. Задание
2.1. Изучить структуру и алгоритмы работы маршрутизаторов в сетях ЭВМ.
2.2. Изучить алгоритмы выбора кратчайших путей в сетях ЭВМ и функционирование протокола сетевого уровня OSPF.
2.3. Построить таблицы маршрутизации сети, используя алгоритмы Э.Дейкстра и Флойда.
3. Рабочее место
Работа выполняется на ПЭВМ.
4. Теоретическая часть
4.1. Структура и принципы работы маршрутизаторов
Маршрутизатор - это устройство третьего уровня эталонной модели ВОС, использующее одну или более метрик для определения оптимального пути передачи трафика на основе информации сетевого уровня.
Маршрутизаторы - это чаще всего специализированные, с устройствами ввода-вывода, компьютеры со специальным программным обеспечением. Маршрутизатор может быть программным, т.е. с программным обеспечением, работающим на компьютере общего назначения, как правило, на сетевом сервере.
Основная функция всех маршрутизаторов - маршрутизация трафика. Кроме того, они могут выполнять ряд дополнительных функций. Процесс маршрутизации можно представить двумя иерархически связанными компонентами:
1. Создание и сопровождение таблиц маршрутизации. Основная функция таблицы маршрутизации - в установлении соответствия между адресом сетевого уровня получателя и адресом сетевого уровня следующего транзитного узла. Этим двум адресам ставится в соответствие определенный выходной физический порт. Такой процесс можно назвать определением маршрута для перемещения пакета.
2. Передача пакетов. При этом проводится проверка контрольной суммы заголовка пакета, определяется получатель пакета с адресом канального уровня и производится отправка пакета с выполнением процедур очередности, фрагментации, фильтрации и т.д.
Исходя из данного описания процесса маршрутизации, функциональная схема маршрутизатора представлена на рис. 6.1. Приведенная функциональная схема носит условный характер и необходима для иллюстрации принципов работы маршрутизатора.
Уровень передачи пакетов реализован на алгоритмах коммутации и в основном одинаков для большинства протоколов маршрутизации. Отправитель, имея адрес маршрутизатора, посылает ему пакет, адресованный специально в физический адрес этого маршрутизатора, но с адресом протокола (сетевой уровень) получателя. После проверки адреса получателя пакета маршрутизатор определяет, «знает» ли он, как передать этот пакет следующему маршрутизатору в пути. Если знает, то пакет отсылается путем замены физического адреса получателя на физический адрес следующего маршрутизатора. Если не знает, то пакет игнорируется. По мере прохождения пакета через сеть его физический адрес меняется, а адрес протокола сетевого уровня остается неизменным.
В случае, если маршрутизатор получает пакеты быстрее, чем может отправить их через данный порт, он помещает их в очередь. Простейший способ организации очереди - постановка пакетов в очередь и отправка их в порядке поступления, по принципу FIFO. Такой алгоритм довольно эффективен, но далеко не оптимален.
Случайное раннее обнаружение (Random Early Detection RED) представляет собой альтернативу очередям FIFO. Оно позволяет смягчить эффект от потери трафика даже при очень больших нагрузках. Такая очередь по-прежнему использует принцип FIFO, но трафик отбрасывается статически, когда средняя длина очереди за данный промежуток времени превосходит установленное значение. Этим достигается оптимизация заполнения очереди. Наряду с бесприоритетной дисциплиной обслуживания очередей (FIFO и случайная выборка из очереди) используется и дисциплина с относительными приоритетами.
Основная задача уровня передачи пакетов - переключение трафика. В этот процесс входят функции приема пакетов, выбора подходящего маршрута дальнейшего следования и отправки их по этому маршруту. Выбор маршрута осуществляется с использованием классических методик: ищется адрес получателя в маршрутной таблице, выбирается один из возможных транзитных узлов, определенных протоколом маршрутизации, формируется выходной заголовок канального уровня и осуществляется посылка пакетов. На этом этапе могут быть задействованы дополнительные возможности, например, фрагментация пакетов, обработка опций и проверка контрольной суммы.
Определение маршрута (уровень маршрутизации) реализовано програм-мными методами. Реализации этой функции носят названия протоколов маршрутизации. Алгоритмы, заложенные в протоколы маршрутизации, описывают процесс определения наиболее предпочтительного маршрута движения информации к адресату на основании информации в таблицах маршрутизации. Алгоритмы маршрутизации базируются на различных показателях или их комбинациях. Простейшие алгоритмы маршрутизации выбирают маршрут с наименьшим числом промежуточных (транзитных) узлов. Более сложные учитывают задержку передачи пакетов, пропускную способность каналов связи или стоимость связи. Основным результатом работы алгоритма маршрутизации является инициализация и поддержка таблицы маршрутизации, в которой содержится вся маршрутная информация. Содержание таблицы маршрутизации зависит от типа используемого протокола. Таблица маршрутизации может содержать следующую информацию:
действительный адрес или множество действительных адресов в сети;
информацию, вычисленную протоколом маршрутизации или необходимую для его функционирования;
информацию, необходимую для пересылки пакетов на один маршрутизатор ближе к получателю.
Алгоритмы маршрутизации должны обладать рядом свойств. К ним относятся: а) оптимальность при выборе маршрута; б) простота реализации; в) живучесть и стабильность; г) быстрая сходимость; д) гибкость. Свойство живучести указывает на то, что алгоритмы должны выбирать альтернативные маршруты при потере связи, функционировать в условиях высоких нагрузок и при некорректных построениях сетевой топологии. Сходимость алгоритма - это длительность процесса соглашения между всеми маршрутизаторами по выбору оптимального маршрута. Если определенное событие в сети приводит к тому, что маршруты либо отвергаются, либо становятся доступными, маршрутизаторы рассылают сообщения об обновлении маршрутизации, которые проходят по всей сети. После получения такой информации на маршрутизаторах происходит переназначение оптимальных маршрутов. Соглашение всех маршрутизаторов должно быть выработано быстро, иначе могут появиться активные петли, и даже может произойти выход сети из строя.
Алгоритмы маршрутизации должны быстро и правильно учитывать изменения состояния сети, например, отказ узла, сегмента сети. Это указывает на гибкость алгоритма.
Алгоритмы маршрутизации могут быть: 1) статическими или динамическими; 2) одномаршрутными или многомаршрутными; 3) одноуровневыми или иерархическими; 4) внутридоменными или междоменными; 5) одноадресными или групповыми.
При применении статических (неадаптивных) алгоритмов выбор маршрутов осуществляется заранее и заносится вручную в таблицу маршрутизации, где хранится информация о том, на какой порт отправить пакет с соответствующей адресной информацией. Протоколы, разработанные на базе статических алгоритмов, называют также немаршрутизируемыми протоколами. В случае динамических алгоритмов таблица маршрутизации меняется автоматически при изменении топологии сети или трафика в ней.
Алгоритмы маршрутизации могут функционировать в сетях двух типов архитектуры: одноуровневой и иерархической. В одноуровневой сети нет различия между разными ее частями. Все сегменты сети находятся на одном логическом уровне. Иерархическая сеть, как правило, состоит из двух частей. Маршрутизаторы нижнего уровня обычно служат для связи с определенными конкретными частями сети, ее сегментами. Маршрутизаторы верхнего уровня образуют особую часть сети, называемую магистральной (опорной). Маршрутизаторы магистральной сети передают пакеты между сетями нижнего уровня.
Одноадресные алгоритмы маршрутизации строят один или несколько маршрутов к одному получателю. Многоадресные алгоритмы способны осуществить передачу информации многим получателям одновременно.
Существует три основные группы протоколов маршрутизации. Деление на группы определяется типом реализуемого алгоритма определения оптимального маршрута. К этим группам относятся: протоколы длины вектора; протоколы состояния канала; протоколы политики маршрутизации.
Протоколы длины вектора самые простые и самые распространенные. Маршрутизатор с определенной периодичностью копирует адреса получателей и метрику из своей таблицы маршрутизации и помещает эту информацию в рассылаемые соседям сообщения об обновлении. Соседние маршрутизаторы сверяют полученные данные со своими собственными таблицами маршрутизации и вносят необходимые изменения. После этого они сами рассылают сообщения об обновлении. Таким образом, каждый маршрутизатор владеет информацией о маршрутах во все сети. Этот алгоритм может работать наиболее эффективно только в небольших сетях. Это связано с тем, что крупные сети не могут функционировать без периодического обмена сообщениями для описания сетевой топологии, и большинство из них избыточны.
Протоколы состояния канала впервые предложены в 1970 году Эдсгером Дейкстрой. Они значительно сложнее, чем протоколы длины вектора. Вместо рассылки соседям содержимого своих таблиц маршрутизации каждый маршрутизатор осуществляет широковещательную рассылку списка маршрутизаторов, с которыми он имеет непосредственную связь, и списка напрямую подключенных к нему локальных сетей. Эта информация является частью данных о состоянии канала и рассылается в специальных сообщениях. Кроме того, маршрутизатор рассылает сообщения о состоянии канала только в случае изменения информации о них или по истечении заданного интервала времени. Протоколы состояния канала трудны в реализации и нуждаются в значительном объеме памяти для хранения информации о состоянии каналов.
К третьей группе протоколов относятся протоколы политики (правил) маршрутизации. Они наиболее эффективно решают задачу доставки получателю информации по разрешенным путям. Эта категория протоколов используется при маршрутизации в сети Internet и позволяет операторам получать информацию о маршрутизации от соседних операторов на основании специальных критериев. Алгоритмы, используемые для политики маршрутизации, опираются на алгоритмы длины вектора, но информация о показателях путей базируется на списке операторов магистрали.
Маршрутизаторы не вносят никаких ограничений в топологию сети и при этом используют все активные маршруты. Активные петли не представляют проблему для маршрутизаторов, так как маршрутизаторы всегда определяют наиболее подходящий путь.
Основным недостатком маршрутизаторов по сравнению с коммутаторами и мостами является то, что последние требуют гораздо меньше усилий по администрированию. Для маршрутизаторов администраторам сетей необходимо задавать целое множество конфигурационных параметров. При этом параметры каждого маршрутизатора должны быть согласованы с параметрами других маршрутизаторов в сети. Маршрутизаторы функционируют на третьем уровне эталонной модели ВОС (см. рис. 6.2).
4.2. Алгоритмы выбора кратчайших путей
B некоторых сетях выбор маршрутов выполняется централизованно, т.е. установление путей между узлами источника и получателя осуществляется в центре управления сетью, а затем полученная в результате информация распределяется по всем узлам сети. В других сетях применяется децентрализованный выбор маршрутов, и в этом случае каждый узел обменивается информацией о стоимости линии связи и маршрутах со своими соседними узлами в ходе взаимодействия с ними до тех пор, пока в узлах не сформируются таблицы маршрутов с необходимыми данными о кратчайших путях.
В данном разделе описаны два алгоритма вычисления кратчайших путей [7]: алгоритм, предложенный Э.Дейкстрой (алгоритм А), и алгоритм Флойда (алгоритм В). Оба эти алгоритма, являющиеся централизованными, или их версии применяются в различных действующих сетях для выполнения функций выбора маршрутов.
Большинство алгоритмов основано на учете меры «стоимости», приписываемой каждой линии (или, может быть, даже каждому узлу) в сети. «Стоимость» может быть величиной фиксированной и относится к таким параметрам, как длина линии, скорость передачи или ширина полосы (пропускная способность), безопасность, задержка при передаче сигнала, или к некоторому сочетанию таких параметров. Стоимость может отражать среднюю нагрузку, ожидаемую в заданный час дня, она может включать изменяемые оценки нагрузки линии, занятости накопителей, характеристики ошибок в линии и т.д.
Алгоритм А. Рассмотрим сеть на рис.6.3, в узлах которой располагаются маршрутизаторы. Числа, проставленные у каждой линии, указывают ее стоимость (ради простоты стоимость в обоих направлениях предполагается одинаковой; однако в более общем случае стоимость передачи в разных направлениях может и различаться). Алгоритм А позволяет найти кратчайшие пути от источника ко всем узлам сети. Для этого требуется знание структуры сети, т. е. списка всех узлов сети и их взаимосвязей, а также стоимости каждой линии. Таким образом, алгоритм А служит для централизованных вычислений с полной информацией о структуре сети, имеющейся на центральной базе данных.
В примере на рис. 6.3 целью является нахождение кратчайшего пути от узла 1, являющегося источником, ко всем остальным узлам сети. Алгоритм решает эту задачу поэтапно, строя дерево кратчайших путей с корнем в узле-источнике (в данном примере в узле 1), пока не будет охвачен самый удаленный узел. На k-м шаге вычисляются кратчайшие пути к k-узлам, ближайшим к источнику. Они определяются как находящиеся внутри множества N. Опишем алгоритм неформально. Обозначим через D(v) расстояние (сумму весов каналов вдоль данного пути) от источника 1 до узла v. Пусть l(i,j) - заданная стоимость пути между узлами i и j. Алгоритм состоит из двух частей: начального шага и итераций, повторяющихся до завершения алгоритма.
1. Начальный шаг. Устанавливаем N={1}. Для каждого узла v, не принадлежащего множеству N, устанавливаем D(v)=l(i,v). (Расстояние до узлов, не соединенных с узлом 1, принимаем равным ; практически можно принять любое число, большее максимальной стоимости или расстояния.)
2. Каждый последующий шаг. Находим не принадлежащий множеству N узел w, для которого D(w) минимально, и включаем w в множество N. Затем обновляем значения D(w) для всех остальных узлов, не принадлежащих N путем вычисления
D(v)Min[D(v),D(w)+l(w,v)].
Шаг 2 повторяется, пока в множество N не войдут все узлы.
Таблица 6.1
Применение алгоритма А к сети, граф которой показан на рис. 6.3
Шаг |
N |
D(2) |
D(3) |
D(4) |
D(5) |
D(6) |
Начальный |
{1} |
2 |
5 |
1 |
|
|
1 |
{1,4} |
2 |
4 |
1 |
2 |
|
2 |
{1,4,5} |
2 |
3 |
1 |
2 |
4 |
3 |
{1,2,4,5} |
2 |
3 |
1 |
2 |
4 |
4 |
{1,2,3,4,5} |
2 |
3 |
1 |
2 |
4 |
5 |
{1,2,3,4,5,6} |
2 |
3 |
1 |
2 |
4 |
Применение алгоритма А к сети на рис. 6.3 иллюстрируется последовательными шагами, указанными в табл. 6.1. Полужирным курсивом в столбцах обозначены минимальные значения D(w) на каждом шаге (при равных расстояниях выбор производится случайным образом). После каждого шага соответствующий узел w добавляется к множеству N. Затем величины D(v) обновляются. Например, после начального шага во время шага 1 к множеству N добавляется узел 4, имеющий минимальное значение D(4)=1. На шаге 2 в N включается узел 5 при D(5)=2 и т. д. После шага 5 все узлы оказываются включенными в множество N, и алгоритм завершается.
По мере работы алгоритма, приводящего к результатам, показанным в табл.6.1, в то же самое время строится дерево кратчайших путей с корнем в узле 1: при включении узла во множество N он соединяется с соответствующим узлом, уже принадлежащим N. Результирующее дерево для сети (см. рис. 6.3) показано на рис. 6.4, а. Цифры в скобках у каждого узла указывают шаг, на котором этот узел был включен в дерево. С помощью дерева кратчайших путей для узла 1 можно получить таблицу маршрутов для узла 1, показывающую исходящий путь, по которому нужно направлять пакеты к узлу назначения. Подобная таблица маршрутов может быть составлена для каждого узла, являющегося источником сообщений. В случае централизованных вычислений каждая таблица маршрутов затем может быть направлена в соответствующий узел.
Алгоритм В также состоит из двух частей: начального шага и расчетов кратчайших расстояний, которые повторяются до завершения алгоритма. Здесь кратчайшее расстояние представляет собой расстояние до данного узла от узла 1, например, рассматриваемого как узел назначения. Алгоритм заканчивается, когда для всех узлов фиксируется их расстояние до узла 1 (узла получателя) и отмечаются следующие узлы по направлению к узлу назначения по кратчайшему пути. Построение таблицы маршрутов с использованием алгоритма В требует повторного или параллельного применения этого алгоритма для каждого узла назначения, что дает в результате набор меток для каждого узла, причем каждая метка дает информацию о маршруте (следующем узле) и расстоянии до конкретного узла назначения.
Дадим опять только неформальное описание алгоритма. Каждый узел v имеет метку (n,D(v)), где D(v) представляет текущую величину кратчайшего расстояния от узла до получателя, а n - номер следующего узла по текущему рассчитанному кратчайшему пути.
1. Начальный шаг. Если узел назначения - узел 1, то устанавливаем D(1)=0 и отмечаем все остальные узлы (,).
2. Отметка кратчайшего расстояния для всех узлов. Для каждого узла v1 выполняется следующее действие: обновляются величины D(v) путем использования текущего значения D(w) для каждого соседнего узла w и вычисления D(w)+l(w,v) с последующим выполнением операции
D(v)min[D(w)+l(w,v)]. (6.1)
w
Метка v обновляется путем замены n номером смежного узла, что минимизирует (6.1), и путем замены D(v) вновь полученным значением. Операция повторяется для каждого узла, пока не прекратятся дальнейшие изменения. Тогда алгоритм завершается, и во всех узлах фиксируются метки как об их кратчайших расстояниях от узла 1, так и до следующего соседнего узла по кратчайшему пути.
Простой пример опять можно рассмотреть на рис. 6.3. Обращаясь ко второй части алгоритма и применяя ее в циклическом порядке для узлов 2 - 6, находим, что алгоритм завершается после двух циклов. Эти циклы и полученные в результате метки в конце каждого цикла приводятся в табл. 6.2 (любой другой порядок обхода узлов приводит к тому же самому окончательному результату).
Таким образом, в цикле 1 нужно отметить, что узел 2 является «ближайшим» к его соседу 1. Его результирующая новая стоимость равна D(v)=D(l)+l(i,2)=2. Следовательно, метка (см. табл. 6.2) имеет вид (1,2). Переходя к узлу 3, приходим к необходимости выбора стоимостей между D(2)+l(2,3)=5 или D(1)+l(1,3)=5. Выбирая произвольно D(1)+l(1,3), получим метку (1,5), что показано в таблице (при другом выборе получится тот же результат). Аналогично получаются другие метки. В цикле 2 узел 3 имеет теперь пять соседних узлов с конечными значениями D(w), между которыми нужно произвести выбор. Минимальное значение D(w)+l(w,3) равно D(5)+l(5,3)=3, и метка узла 3, как показано, меняется на (5,3). Другие узлы не меняют своих меток, и алгоритм завершается. Опять же дерево кратчайших путей с корнем в узле 1 (см. рис. 6.4, а) может быть получено путем обхода меток каждого узла. В результате, узел 2 соединяется с узлом 1, узел 3 - с узлом 5, узел 4 - с узлом 1, узел 5 - с узлом 4 и узел 6 - с узлом 5. Иначе, таблица маршрутов или значение следующего узла в каждом узле по направлению к узлу 1 в точности является первым числом каждой двузначной метки, что и указывалось выше. Для получения полной таблицы маршрутов в каждом узле алгоритм В должен быть повторен для каждого узла, принимаемого в качестве узла назначения.
4.3. Протокол маршрутизации OSPF
Спецификация протокола OSPF (Open Shortest Path First) [2] - иерархического протокола маршрутизации, при котором маршрут выбирается на основании информации о состоянии канала - описана в документе RFC 1247. Этот протокол вычисляет маршруты в сетях на базе протокола IP, сохраняя при этом другие протоколы обмена маршрутной информацией. OSPF является протоколом маршрутизации с объявлением состояния канала связи. Это означает, что он требует отправки данных о состоянии канала на все маршрутизаторы, находящиеся в одном домене. Сообщения протокола OSPF передаются в IP-дей-таграммах со значением поля «Протокол» заголовка дейтаграммы, равным 89.
После инициализации каждый маршрутизатор передает сообщения LSA (Link-State Advertisement) - описание локального состояния маршрутизатора - на все свои порты. Данное сообщение позволяет уникально идентифицировать передающий маршрутизатор и состояние каждого из его портов. Сообщение LSA содержит параметры каждого порта маршрутизатора, такие как:
IP-адрес;
маска подсети;
метрика, присвоенная каналу связи порта;
статус канала связи.
Данное сообщение LSA будет передаваться во всем домене маршрутизации, и, соответственно, все маршрутизаторы получат его и будут обладать информацией о состоянии каналов всех других маршрутизаторов в домене. Каждый маршрутизатор собирает индивидуальные сообщения LSA и затем формирует с их помощью базу данных состояний каналов. Все маршрутизаторы в одном домене маршрутизации будут управлять идентичными базами данных состояний каналов.
После того как все базы данных на маршрутизаторах синхронизированы, каждый маршрутизатор начинает создавать свою таблицу маршрутизации. Эта таблица базируется на информации, содержащейся в базе данных состояний каналов. Первым шагом является создание карты сетевой топологии. Для построения карты сетевой топологии каждый маршрутизатор помещает информацию из полученных сообщений LSA в свою память. Непосредственно связанные маршрутизаторы в спецификации протокола OSPF называются «соседями». Каждый маршрутизатор хранит информацию о том, в каком состоянии, по его мнению, находится сосед. Маршрутизатор передает соседям дейтаграммы только в том случае, если он уверен, что они полностью работоспособны.
После того как карта сетевой топологии построена, маршрутизатор формирует дерево кратчайших путей ко всем возможным получателям. Данное дерево строится так, что путь от корня маршрутизатора, формирующего дерево, до конечных объектов - целевых сетей - выбирается с наименьшей стоимостью. При построении дерева маршрутизатор помещает себя в его корень. В результате каждый маршрутизатор формирует свое дерево независимо от других маршрутизаторов, но с учетом того, что они все имеют идентичную базу данных состояний канала.
В случае если любой из маршрутизаторов обнаружит изменения в состоянии своих каналов, он должен разослать сообщения LSA всем своим соседям.
Область действия протокола OSPF - это логическая часть общей сети. Обычно сети масштаба предприятия разделяются на части, которые соответствуют зданиям, корпусам и т.д. Маршрутизаторы внутри одной области OSPF не обмениваются информацией с маршрутизаторами в другой области. Когда добавляются каналы связи в одной области, информация об изменении в топологии распространяется только между маршрутизаторами в данной области. Это уменьшает объем служебного трафика маршрутизаторов, распространяемого в сети, и размер баз данных в каждом из маршрутизаторов.
Области действия протокола OSPF связываются друг с другом с помощью маршрутизаторов, которые должны содержать базу данных с информацией обеих областей. Эти маршрутизаторы называются граничными маршрутизаторами областей. Они работают как фильтры для служебных сообщений, которые проходят между областями. Граничные маршрутизаторы взаимодействуют между собой, используя специальный тип сообщений LSA, которые содержат краткую информацию о топологии в их областях. Граничные маршрутизаторы сохраняют эти сообщения в специальной базе данных, которая используется для определения способа маршрутизации трафика между областями.
Для упрощения процесса синхронизации базы данных в протоколе OSPF используется понятие «назначенного» маршрутизатора (DR) и его резервного напарника (BDR). При этом оба маршрутизатора будут единственными, с которыми новый маршрутизатор должен синхронизовать свою базу. После синхронизации базы с назначенным маршрутизатором новый маршрутизатор будет синхронизован со всеми маршрутизаторами данной сети. Остальные маршрутизаторы просто объявляют о своей связи с назначенным маршрутизатором. Резервный маршрутизатор занимает место назначенного в случаях, когда последний выходит из строя.
Достоинство выбора DR в том, что это значительно уменьшает количество маршрутной информации, передаваемой по сети. Если каждые соседние маршрутизаторы обмениваются информацией друг с другом и в сети существует N маршрутизаторов, то количество таких обменов будет достигать [N*[N-1)]/2. Это будет вызывать значительный объем трафика. При использовании DR это число уменьшается до [N-1], а если учитывать обмен информации и с BDR - то до 2*[N-1].
Все сообщения протокола OSPF начинаются с одного общего заголовка (см. рис.6.5), поля в котором имеют следующие значения:
поле «Версия» указывает на версию протокола OSPF. Текущая версия 2;
поле «Тип» указывает на тип используемого протокола;
поле «Длина сообщения» - длина сообщения в байтах;
поле «Идентификатор маршрутизатора» - это может быть IP-адрес;
поле «Идентификатор области» используется для идентификации данной области протокола OSPF. Обычно выбирают IP-адреса в качестве идентификации областей;
поле «Контрольная сумма» содержит контрольную сумму, вычисляемую для всего сообщения, исключая 8-байтовое общее поле «Аутентификация», используя классический алгоритм;
поле «Идентификатор алгоритма аутентификации» указывает, какой алгоритм используется для аутентификации сообщений. Для этого поля могут быть определены только два значения: 0 -аутентификация не используется и 1 - простая аутентификация.
Аутентификация (или идентификация) прав пользователей - это процесс разграничения доступа различных пользователей (чаще всего на основе паролей) к фрагментам распределенной информации в сети, а также к набору выполняемых над ними операций.
При использовании простой аутентификации поле «Аутентификация» содержит пароль, состоящий из восьми байт. Администратор может настроить различные пароли для каждой сети. Это является хорошей гарантией защиты от случайных ошибок, например, от некорректной настройки маршрутизатора. Однако это не очень надежный метод защиты от намеренного вмешательства.
Протокол OSPF состоит из трех внутренних протоколов: Hello, Exchange и Flooding. Внутренний протокол Hello генерирует при своей работе одноименные сообщения.
Соседние маршрутизаторы обнаруживаются динамически на широковещательных и не широковещательных сетях, используя сообщения Hello. Для этого через все порты маршрутизатора посылаются сообщения, содержащие:
приоритет маршрутизатора, который затем используется для выбора DR и BDR;
интервал посылки сообщений Hello в секундах;
интервал отказа маршрутизатора;
список маршрутизаторов, от которых сообщения Hello были недавно получены;
указания на маршрутизаторы, которые в настоящий момент являются DR и BDR.
Интервал посылки сообщения Hello и интервал отказа маршрутизатора являются наиболее важными. В сообщениях Hello маршрутизатор передает свои рабочие параметры и говорит, кого он рассматривает в качестве своих ближайших соседей. Маршрутизаторы с разными рабочими параметрами игнорируют сообщения Hello друг друга, поэтому маршрутизаторы с некорректно настроенными параметрами не будут влиять на работу сети. Маршрутизаторы посылают сообщения Hello каждому своему соседу по крайней мере один раз на протяжении интервала Hello. Если интервал отказа маршрутизатора истекает без получения сообщения Hello от соседа, то считается, что сосед неработоспособен, и рассылается новое объявление о сетевых связях для того, чтобы в сети произошел пересчет маршрутов.
Формат сообщения Hello показан на рис. 6.6. Поле «Маска подсети» устанавливается в значение маски подсети, ассоциирующейся с портом, через который посылается сообщение. Сообщения протокола Hello посылаются маршрутизатором периодически, через определенный интервал. Поля «Hello-интервал» и «Интервал отказа» - это значения параметров, устанавливаемых администратором. Поле «Приоритет» используется в процессе выбора DR и BDR. Каждый маршрутизатор настраивается с приоритетом в пределах от 0 до 255. В результате выбирается маршрутизатор, имеющий наибольший приоритет. Если маршрутизатор с наибольшим приоритетом выходит из строя или просто выключается, выбирается другой. Новый выбранный маршрутизатор будет оставаться в состоянии DR, даже если маршрутизатор с наибольшим приоритетом вновь будет функционировать. Маршрутизаторы, у которых приоритет равен нулю, никогда не будут избраны назначенными.
Начальная синхронизация баз данных нового маршрутизатора и DR выполняется с помощью протокола Exchange. Упрощенно работу данного протокола можно представить в два этапа. На первом этапе определяются роли двух маршрутизаторов: один выбирается как доминирующий, другой - как доминантный. После этого на втором этапе происходит взаимный обмен описаниями их баз данных с помощью специальных пакетов. После установления начальной синхронизации с помощью протокола Exchange ответственность за поддержку режима синхронизации баз данных состояния каналов связи всех маршрутизаторов несет протокол Flooding.
На широковещательных сетях и сетях с соединениями типа «точка-точка» сообщения протокола Hello посылаются соседям с использованием групповой адресации протокола IP. В этом случае соседние маршрутизаторы обнаруживаются динамически. В сети, у которой широковещательная передача не поддерживается, посылка сообщений Hello осуществляется на базе списка адресов всех маршрутизаторов в сети. Данный список настраивается на маршрутизаторе, который имеет потенциальную возможность стать назначенным (DR). Протокол Hello отвечает также за выбор DR, но только не в сетях типа «точка-точка». В данных сетях выбор DR не производится.
Для распространения по сети данных о состоянии каналов связи маршрутизаторы обмениваются специальным типом сообщений LSA. Они обмениваются не только своими, но и чужими объявлениями о связях, получая, в результате, информацию о состоянии всех связей в сети. Эта информация и образует граф связей сети, который является единственным для всех маршрутизаторов. Кроме информации о соседях, маршрутизатор в своем объявлении перечисляет IP- подсети, с которыми он связан непосредственно. Поэтому вычисление маршрута до каждой из подсетей производится по графу связей с использованием алгоритма Дейкстры. Маршрутизатор вычисляет путь не до подсети, а до маршрутизатора, к которому эта подсеть подключена. Каждый маршрутизатор имеет уникальный идентификатор, который передается в объявлении о состоянии связей.
Протокол OSPF использует групповую адресацию в целях обмена маршрутной информацией между маршрутизаторами в сети. Для этого зарезервированы два IP-адреса:
224.0.0.5 - все маршрутизаторы, работающие по протоколу OSPF, должны поддерживать передачу и получение дейтаграмм с данным групповым адресом;
224.0.0.6 - все маршрутизаторы DR и BDR должны поддерживать получение дейтаграмм с данным групповым адресом.
Для небольших и средних сетей базовые услуги протокола OSPF работают хорошо. Но в очень больших сетях огромное число передаваемой маршрутной информации может вызывать проблемы. Например, в смешанной сетевой топологии с сотнями маршрутизаторов изменение состояния одного канала связи (например, обрыв) вызывает распространение тысяч сообщений LSA через всю сеть от маршрутизатора к маршрутизатору. База данных состояния канала каждого маршрутизатора может быть увеличена в объеме до нескольких мегабайт.
В то же время при изменениях в сетевой топологии каждый маршрутизатор должен вновь сформировать таблицу маршрутизации. В очень больших сетях время сходимости может значительно увеличиваться, так как маршрутизаторы будут заняты обменом сообщениями по обновлению своих баз данных и вычислением новых маршрутов.
Совместно с протоколом OSPF могут использоваться другие протоколы маршрутизации, такие как EGP, BGP, RIP IP или собственные протоколы производителей.
Стек протоколов TCP/IP. Протокол OSPF и рассмотренный в лабораторной работе №5 протокол STP относятся к набору (стеку) взаимодействующих протоколов TCP/IP. Основным протоколом этого стека является протокол сетевого уровня IP (рис. 6.7). Так как стек протоколов TCP/IP был разработан до появления эталонной модели ВОС, то соответствие его уровней уровням модели ВОС достаточно условное. На практике взаимодействие уровней стека организовано гораздо сложнее, чем на рисунке.
Рассмотренный в лабораторной работе №5 протокол STP относится к уровню сетевого интерфейса (уровень IV). В стеке протоколов TCP/IP этот уровень не регламентирован. Уровень сетевого интерфейса отвечает за прием дейтаграмм и передачу их по конкретной сети. Интерфейс с сетью может быть реализован драйвером устройства или сложной системой, которая использует свой протокол канального уровня (коммутатор, маршрутизатор).
Сетевой уровень (уровень III) - это уровень межсетевого взаимодействия, управляющий взаимодействием между пользователями в сети. На этом уровне инкапсулируется пакет в дейтаграмму, заполняется ее заголовок и при необходимости используется алгоритм маршрутизации, кроме того, обрабатываются приходящие дейтаграммы и проверяется правильность поступившей информации. К этому уровню относятся все протоколы, которые создают, поддерживают и обновляют таблицы маршрутизации, в том числе и протокол OSPF.
Подробную информацию об основных протоколах стека TCP/IP можно получить из специальной литературы, в частности [2].
5. Порядок выполнения работы
5.1. Изучить основные принципы маршрутизации в сетях ЭВМ.
5.2. Изучить структуру и алгоритмы работы маршрутизаторов в сетях ЭВМ.
5.3. Изучить теоретический материал по алгоритмам поиска кратчайших путей в сетях ЭВМ и особенностям протокола сетевого уровня OSPF.
5.4. Для сети, согласно варианту (табл. 6.3, рис. 6.8), построить таблицы маршрутизации, пользуясь централизованными алгоритмами А и В. Поэтапно промоделировать работу протокола OSPF, поясняя действия рисунками и форматами служебных сообщений.
5.5. Построить граф-схемы алгоритмов выбора кратчайших путей и обобщенную граф-схему алгоритма функционирования маршрутизатора, согласно протоколу OSPF.
5.6. Сделать выводы по результатам моделирования.
Таблица 6.3
Исходные данные для построения таблицы маршрутизации
№ варианта |
Расстояние между соседними узлами графа - l(i,j) |
№ графа |
№ узла |
|||||||||||||||
1,2 |
1,3 |
1,4 |
1,5 |
2,3 |
2,4 |
3,5 |
3,6 |
3,7 |
4,5 |
5,6 |
6,7 |
1,6 |
2,6 |
3,4 |
5,7 |
|||
1 |
5 |
2 |
2 |
1 |
3 |
4 |
1 |
1 |
2 |
3 |
6 |
4 |
- |
- |
- |
- |
1 |
1 |
2 |
6 |
2 |
2 |
3 |
3 |
3 |
1 |
1 |
1 |
2 |
4 |
5 |
- |
- |
- |
- |
1 |
2 |
3 |
4 |
6 |
4 |
5 |
1 |
1 |
4 |
2 |
2 |
1 |
1 |
3 |
- |
- |
- |
- |
1 |
3 |
4 |
2 |
1 |
2 |
1 |
2 |
3 |
4 |
6 |
2 |
5 |
4 |
1 |
- |
- |
- |
- |
1 |
4 |
5 |
2 |
1 |
3 |
2 |
4 |
5 |
1 |
2 |
4 |
3 |
2 |
1 |
- |
- |
- |
- |
1 |
5 |
6 |
2 |
3 |
4 |
1 |
5 |
6 |
6 |
1 |
2 |
3 |
1 |
2 |
- |
- |
- |
- |
1 |
6 |
7 |
2 |
4 |
3 |
1 |
2 |
1 |
6 |
8 |
7 |
1 |
6 |
4 |
- |
- |
- |
- |
1 |
7 |
8 |
2 |
1 |
1 |
2 |
4 |
3 |
6 |
4 |
8 |
5 |
4 |
3 |
- |
- |
- |
- |
1 |
1 |
9 |
1 |
2 |
1 |
1 |
1 |
2 |
2 |
3 |
8 |
4 |
6 |
1 |
- |
- |
- |
- |
1 |
2 |
10 |
3 |
1 |
1 |
4 |
2 |
2 |
3 |
6 |
1 |
4 |
2 |
6 |
- |
- |
- |
- |
1 |
3 |
11 |
5 |
4 |
1 |
6 |
2 |
4 |
4 |
2 |
2 |
3 |
1 |
1 |
- |
- |
- |
- |
1 |
4 |
12 |
3 |
1 |
6 |
2 |
2 |
1 |
4 |
3 |
6 |
1 |
2 |
1 |
- |
- |
- |
- |
1 |
5 |
13 |
4 |
6 |
1 |
4 |
2 |
3 |
5 |
8 |
1 |
2 |
3 |
3 |
- |
- |
- |
- |
1 |
6 |
14 |
2 |
- |
- |
- |
1 |
8 |
6 |
- |
3 |
4 |
1 |
2 |
1 |
1 |
6 |
3 |
2 |
1 |
15 |
3 |
- |
- |
3 |
2 |
1 |
- |
3 |
4 |
8 |
6 |
5 |
4 |
2 |
1 |
2 |
2 |
|
16 |
5 |
- |
- |
- |
4 |
3 |
2 |
- |
1 |
2 |
3 |
3 |
1 |
1 |
1 |
1 |
2 |
3 |
17 |
2 |
- |
- |
- |
2 |
4 |
3 |
- |
2 |
4 |
8 |
5 |
6 |
6 |
1 |
2 |
2 |
4 |
18 |
2 |
- |
- |
- |
3 |
4 |
5 |
- |
6 |
7 |
1 |
2 |
1 |
3 |
3 |
3 |
2 |
5 |
19 |
6 |
- |
- |
2 |
3 |
1 |
- |
2 |
3 |
1 |
2 |
3 |
1 |
3 |
2 |
2 |
6 |
|
20 |
1 |
- |
- |
- |
6 |
5 |
4 |
- |
3 |
2 |
1 |
2 |
3 |
4 |
5 |
6 |
2 |
7 |
21 |
1 |
- |
- |
- |
4 |
2 |
3 |
- |
2 |
1 |
6 |
3 |
1 |
2 |
1 |
4 |
2 |
1 |
22 |
4 |
- |
- |
- |
2 |
1 |
8 |
- |
7 |
6 |
2 |
2 |
3 |
4 |
4 |
3 |
2 |
2 |
23 |
1 |
- |
- |
- |
1 |
1 |
2 |
- |
2 |
3 |
3 |
4 |
1 |
2 |
8 |
7 |
2 |
3 |
24 |
6 |
- |
- |
- |
4 |
4 |
3 |
- |
3 |
2 |
1 |
2 |
3 |
1 |
1 |
6 |
2 |
4 |
25 |
3 |
- |
- |
- |
3 |
3 |
2 |
- |
2 |
1 |
8 |
6 |
4 |
8 |
1 |
5 |
2 |
5 |
Примечание. Номер узла указывает на узел сети, для которого строится таблица маршрутизации.
6. Содержание отчета
6.1. Исходные данные и исходный граф сети.
6.2. Граф-схемы алгоритмов выбора кратчайший путей в сетях ЭВМ и обобщенная граф-схема алгоритма функционирования маршрутизатора, согласно протоколу OSPF.
6.3. Итоговый граф сети.
6.4. Расчетные таблицы и таблицы маршрутизации.
6.4. Иллюстрации, отражающие этапы работы протокола OSPF, форматы служебных сообщений.
6.5. Выводы по результатам моделирования.
7. Контрольные вопросы
7.1. На каком уровне эталонной модели ВОС работают мосты, коммутаторы и маршрутизаторы? Какие функции, согласно своему положению они выполняют? Укажите основные различия этих устройств.
7.2. Опишите структуру маршрутизатора, согласно реализуемым в этом устройстве функциям.
7.3. Каким образом происходит отправка сообщений через маршрутизатор, если таблица маршрутизации уже построена?
7.4. Какую информацию содержит таблица маршрутизации? Какими свойствами характеризуются алгоритмы маршрутизации?
7.5. На какие группы делятся протоколы маршрутизации? В чем заключаются их различия?
7.6. Какой информацией должен владеть маршрутизатор в сети, чтобы для него можно было построить таблицу маршрутизации централизованным и децентрализованным алгоритмами?
7.7. Что означает сходимость алгоритма маршрутизации? Какой из алгоритмов (А или В) обладает лучшей сходимостью? Ответ обоснуйте на примере.
7.8. Какими средствами, согласно протоколу OSPF, осуществляется синхронизация базы данных маршрутизатора?