Протоколы и алгоритмы маршрутизации

Лекция

Тема: Принципы объединения сетей на основе протоколов сетевого уровня.

Цель.

1. Обучающая.Ввести основные понятия. Освоить методы разработки и способы представления элементов сети.

2. Развивающая. Развивать логику, умение анализировать, сравнивать, делать выводы, высказывать свою мысль. Развивать внимание и аналитическое мышление.

3. Воспитательная. Воспитывать интерес к языкам программирования, научным достижениям и открытиям. Воспитывать аккуратность, внимательность и дисциплинированность. Формирование самостоятельности и ответственности при повторении пройденного и изучении нового материала. Воспитывать чувство ответственности за напарника при работе в группе.

Межпредметные связи:

  • Обеспечивающие: информатика.
  • Обеспечиваемые: базы данных.

Методическое обеспечение и оборудование:

1. Методическая разработка к занятию.

2. Рабочая программа.

3. Инструктаж по технике безопасности.

Технические средства обучения: проэктор, компьютер.

Обеспечение рабочих мест:

  • Рабочие тетради.

Ход лекции.

Организационный этап.

Анализ и проверка домашнего задания.

Фронтальный опрос по вопросам.

Решите задачи.

Объединение сетей на основе протоколов сетевого уровня

Для объединения нескольких сетей в единую систему, способную передавать данные между любыми узлами объединенной сети, служит сетевой уровень.

На сетевом уровне вычислительной сетью будем называть совокупность компьютеров, соединенных между собой в соответствии с одной из стандартных типов топологий и использующих для передачи данных один из протоколов канального уровня, определенный для этой топологии.

Компонентами составной сети могут являться как локальные, так и глобальные сети.

Основная идея введения сетевого уровня состоит в том, чтобы оставить технологии, используемые в объединяемых сетях в неизменном в виде, но добавить в кадры всех сетей дополнительную информацию — заголовок сетевого уровня, который позволил бы находить на основании этой информации адресата в сети любого типа. Заголовок пакета сетевого уровня имеет унифицированный формат, не зависящий от форматов кадров канального уровня тех сетей, которые могут входить в интерсеть.

Внутри сети доставка данных обеспечивается канальным уровнем, а доставкой данных между сетями занимается сетевой уровень. Он выбирает правильный маршрут передачи, чтобы данные достигли нужной сети. Сети соединяются между собой маршрутизаторами. Сообщения сетевого уровня называют пакетами.

В функции сетевого уровня входит:

?передача пакетов между конечными узлами в составных сетях;

?выбор маршрута передачи пакетов, наилучшего по некоторому критерию;

?согласование разных протоколов канального уровня, использующихся в смежных подсетях.

На сетевом уровне необходима собственная система адресации, не зависящая от способов адресации узлов в отдельных подсетях.

Сетевой адрес формируется как пара: номер сети (подсети) и номера узла.

Основным полем заголовка пакета на сетевом уровне является номер сети – адресата. Благодаря нумерации подсетей сетевой уровень может составлять точную карту межсетевых связей и выбирать рациональные маршруты.

Принципы маршрутизации

Важнейшей задачей сетевого уровня является маршрутизация – организация доставки пакетов по назначению.

Рассмотрим принципы маршрутизации на примере составной сети, изображенной на рис.1.

Маршрутизаторы имеют по несколько портов (не менее двух), к которым присоединяются сети. Каждый порт маршрутизатора можно рассматривать как отдельный узел сети: он имеет собственный сетевой адрес и собственный локальный адрес в той подсети, которая к нему подключена. Например, маршрутизатор номер 1 имеет три порта:

S1, S2, S3 – сети, подключенные к портам;

М1(1), М1(2), М1(3) – сетевые адреса этих портов;

Порт М1(1) имеет локальный адрес в сети S1;

Порт М1(2) имеет локальный адрес в сети S2;

Порт М1(3) имеет локальный адрес в сети S3;

Протоколы и алгоритмы маршрутизации

S1, S2, … S5 – номера сетей, соединенных маршрутизаторами.

Рис. 1. Принцип маршрутизация в составной сети

Маршрутизатор можно рассматривать как совокупность нескольких узлов, каждый из которых входит в свою сеть. Как единое устройство маршрутизатор не имеет отдельного сетевого или локального адреса.

Маршрут – это последовательность марщрутизаторов, которые должен пройти пакет. В сложных сетях обычно существует несколько альтернативных маршрутов.

Каждый маршрутизатор выбирает маршрут дальнейшего следования пакета. Для этого он использует таблицу маршрутизации и указанный критерий выбора маршрута.

Табл.1 иллюстрирует пример таблицы маршрутизации для маршрутизатора 4.

Табл. 1. Таблица маршрутизации маршрутизатора 4.

Номер сети Адрес следующего маршрутизатора Адрес выходного порта Расстояние до сети
S1 M1(2) M4(1)
S2 M4(1) 0 (подс.)
S3 M1(2) M4(1)
S4 M2(1) M4(1)
S5 M4(2) 0 (подс.)
Умолчание M5(1) M4(2)

Описание таблицы маршрутизации по столбцам слева направо:

— номер сети назначения;

— сетевой адрес следующего маршрутизатора (то есть адрес соответствующего порта следующего маршрутизатора), на который следует направить пакет, чтобы тот передавался по направлению к сети с данным номером по рациональному маршруту;

— сетевой адрес выходного порта – на какой из собственных портов маршрутизатор должен направить пакет;

— расстояние до сети назначения – используется, если в таблице маршрутизации есть несколько строк, соответствующих некоторому адресу сети назначения.

Под расстоянием понимается значение, определенное при некоторой метрике и используемое в соответствии с заданным в сетевом пакете критерием. Этот критерий иногда называют классом сервиса. Расстояние может измеряться хопами (скачками), временем прохождения пакета по линиям связи, характеристикой надежности связи на данном маршруте и т. п.

Если марщрутизатор поддерживает несколько классов сервиса пакетов, то таблица маршрутов составляется и применяется отдельно для каждого вида сервиса (критерия).

Если таблица маршрутизации в случае крупной сети имеет слишком большой объем, то для сокращения числа записей в таблице используют специальную запись «маршрутизатор по умолчанию» (default). Маршрутизаторы в этом случае хранят строки для соседних сетей. Обо всех остальных сетях в таблице делают одну запись, указывающую на маршрутизатор, через который пролегает путь ко всем остальным сетям. В нашем примере таким маршрутизатором для четвертого маршрутизатора является маршрутизатор 5 ( порт М5(1)).То есть путь ко всем остальным сетям большой сети проходит через этот порт маршрутизатора.

Таблица маршрутизации строят также и для конечных узлов. Особенности таблиц маршрутизации на конечных узлах:

? они аналогичны по структуре таблицам, хранящимся в маршрутизаторах;

? используются для оределения того, направляется ли пакет в другую сеть или он адресован какому-либо узлу данной сети;

? эти таблицы маршрутизации чаще строятся вручную.

Табл. 2 содержит пример таблицы маршрутизации для узла А.

Табл2. Таблица маршрутизации конечного узла А.

Номер сети Адрес следующего маршрутизатора Адрес выходного порта Расстояние до сети
S4 MA
S3 M3(2) MA
Умолчание M2(2) MA

Протоколы и алгоритмы маршрутизации

Цель маршрутизации – доставка пакетов по назначению с максимизацией эффективности. Маршрут выбирается на основании имеющейся у маршрутизаторов информации о конфигурации (топологии) сети, длин очередей в узлах коммутации, интенсивности входных потоков и других факторов, а также на основании заданного критерия выбора маршрута.

Алгоритмы маршрутизации включают процедуры:

? измерение и оценивание параметров сети;

? принятие решения о рассылке служебной информации;

? построение таблиц маршрутизации;

? реализация принятых маршрутных решений.

Таблицы маршрутизации создаются в основном автоматически, но могут корректироваться и дополняться вручную. Для автоматического построения таблиц маршрутизаторы обмениваются информацией о связях в сети. При этом используются специальные служебные протоколы, называемые протоколами маршрутизации. Протоколы маршрутизации помещают свои служебные пакеты в поле данных пакетов сетевого или транспортного уровня, то есть используют соответствующие протоколы для транспортировки своих сообщений. Формально эти протоколы можно отнести к более высокому уровню, чем сетевой.

Объединение подсетей для создания более сложной (неоднородной) сети можно осуществлять и средствами канального уровня. Для этого могут быть использованы некоторые типы мостов и коммутаторов. Однако применение средств канального уровня для создания сложных сетей имеет существенные ограничения и недостатки. В табл. 3. проводится сравнение маршрутизаторов и коммутаторов (мостов) с точки зрения их применения для объединения подсетей.

Табл 3. Сравнение маршрутизаторов и коммутаторов (мостов).

Коммутаторы Маршрутизаторы
Локальные таблицы соответствия IP – адресов МАС – адресам (физическим). Таблицы маршрутизации с номерами сетей.
Построение таблиц путем пассивного просмотра проходящих кадров. Обмен служебными пакетами с данными о сетях и маршрутизаторах.
Учитывается только топология сети. Учет не только топологии, но и пропускной способности и состояния маршрутизаторов.
Простое определение нужного порта по таблице (скорость). Реализация сложных алгоритмов маршрутизации.
Подвержены широковещательному шторму, проблема с управлением трафиком. Нет широковещательного шторма, быстрее адаптируются к изменению конфигурации сети, допускают наличие замкнутых контуров в сети.

Протоколы маршрутизации могут быть построены на основе разных алгоритмов, отличающихся способами построения таблиц маршрутизации, способами выбора наилучшего маршрута и др.

Одношаговые алгоритмы маршрутизации

Каждый маршрутизатор определяет только один шаг маршрута – только следующий (ближайший) маршрутизатор. Окончательный маршрут складывается в результате работы всех маршрутизаторов, через которые проходит данный пакет.

Одношаговые алгоритмы, в зависимости от способа формирования таблиц маршрутизации делятся на три класса:

§ алгоритмы фиксированной (статической) маршрутизации;

§ алгоритмы простой маршрутизации;

§ алгоритмы адаптивной (динамической) маршрутизации.

Алгоритмы фиксированной маршрутизации:

§ все записи в таблице маршрутизации являются статическими;

§ таблица обычно создается при загрузке и используется без изменений, пока ее не отредактируют вручную (если, например, отказал какой-нибудь маршрутизатор);

§ виды таблиц

? одномаршрутные таблицы, в которых для каждого адресата задан один путь;

? многомаршрутные таблицы, определяющие альтернативные пути для каждого адресата. Должно быть задано правило выбора одного из маршрутов;

§ приемлем в небольших сетях с простой топологией или для работы на магистралях крупных сетей (с простой структурой).

В алгоритмах с простой маршрутизацией таблица маршрутизации либо вовсе не используется, либо строится без участия протоколов маршрутизации. Выделяют три типа простой маршрутизации:

? случайная маршрутизация, когда прибывший пакет посылается в случайном направлении, кроме исходного;

? лавинная маршрутизация, когда пакет широковещательно посылается по всем возможным направлениям, кроме исходного;

? маршрутизация по предыдущему мосту, когда маршрут выбирается по таблице, но таблица строится, как у моста, путем анализа адресных полей, поступающих пакетов.

Алгоритмы адаптивной (динамической) являются самыми распространенными и обладают следующими свойствами:

? автоматическое обновление таблиц маршрутизации после изменения конфигурации сети;

? обычно задается интервал времени, в течение которого данный маршрут будет оставаться действительным. Это время называется временем жизни маршрута;

? сбор топологической информации распределен между всеми маршрутизаторами, хотя наметилась тенденция использования сервера маршрутов – протокол NHRP.

? обеспечение достаточно рационального маршрута;

? простые алгоритмы без использования большого объема сетевых ресурсов;

? обладание свойством сходимости – получение однозначного результата за приемлемое время.

Два типа алгоритмов адаптивной маршрутизации:

? дистанционно – векторные алгоритмы;

? алгоритмы состояния связей.

В алгоритмах дистанционно – векторного типа каждый маршрутизатор периодически и широковещательно рассылает по сети вектор, компонентами которого являются расстояния от данного маршрутизатора до всех известных ему сетей. Каждый маршрутизатор наращивает расстояния до указанных в векторе сетей на расстояние до данного соседа. В полученный вектор маршрутизатор добавляет к нему информацию об известных ему других сетях, а затем снова рассылает новое значение вектора по сети. В конце концов, узнает обо всех имеющихся сетях и о расстояниях до них через соседние маршрутизаторы.

Недостатки дистанционно – векторных алгоритмов:

? хорошо работают только в небольших сетях, в больших сетях генерируют интенсивный широковещательный трафик;

? изменения конфигурации могут отрабатываться не всегда корректно, так как маршрутизаторы не владеют точной топологией, а располагают только обобщенной информацией – вектором дистанций.

Наиболее распространенным протоколом, основанным на дистанционно – векторномалгоритме, являетсяRIP (Routing Internet Protocol).

Алгоритмы состояния связей обеспечивают маршрутизатор информацией, достаточной для построения точного графа связей сети. Все маршрутизаторы работают с одинаковыми графами. Вершинами графа являются как маршрутизаторы, так и объединяемые ими сети, Имеется широковещательный трафик, но только при изменении состояния связей и пакетами меньшего объема, чем для алгоритма RIP. В надежных сетях связи изменяются не часто.Одним из протоколов, основанным на алгоритме состояния связей является протокол OSPF (Open Shortest Path First) стека TCP/IP.

Функции маршрутизатора

Функции маршрутизатора могут быть разбиты на 3 группы в соответствии с уровнями модели OSI (рис. 5.3, с. 358).

Уровень интерфейсов

На нижнем уровне маршрутизатор обеспечивает физические интерфейсы для подсоединения локальных и глобальных сетей. Каждый интерфейс (порт) для подключения локальной сети соответствует определенному протоколу канального уровня (FDDI, Ethernet, Token Ring). Интерфейс с глобальной сетью обычно определяет только некоторый стандарт физического уровня, над которым в маршрутизаторе могут работать различные протоколы канального уровня. Например, с интерфейсом V.35 могут работать протоколы: LAP-B (X.25), LAP-F (frame relay), LAP-D(ISDN).

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

Cisco часть I, урок 8. Протокол динамической маршрутизации OSPF


Похожие статьи.

Понравилась статья? Поделиться с друзьями: