18 Понятие маршрутизации пакетов данных. Алгоритмы маршрутизации,

классификация.

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

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

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

Алгоритмы выбора маршрута можно разбить на два основных класса: адаптивные и неадаптивные.

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

Адаптивные алгоритмы, напротив, изменяют решение о выборе маршрутов при изменении топологии и также часто в зависимости от загруженности линий.

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

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

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

4. Маршрутизация с учетом состояния линии.

   1. Обнаружить своих соседей и узнать их сетевые адреса.

   2. Измерять задержку или стоимость связи с каждым из своих соседей.

   3. Создавать пакет, содержащий всю собранную информацию.

   4. Посылать этот пакет всем маршрутизаторам.

   5. Вычислять кратчайший путь ко всем маршрутизаторам.

В результате каждому маршрутизатору высылается полная топология и все измеренные задержек.

19 IP-адресация. IP-маршрутизация. Маршрутизация в глобальной сети Internet. Протоколы маршрутизации в Интернет.

IP-адрес – это уникальный числовой адрес, однозначно идентифицирующий узел, группу узлов или сеть. IP-адрес имеет длину 4 байта и обычно записывается в виде четырех чисел (так называемых «октетов»), разделенных точками – W.X.Y.Z , каждое из которых может принимать значения в диапазоне от 0 до 255, например, 213.128.193.154.

Существует 5 классов IP-адресов – A, B, C, D, E. Принадлежность IP-адреса к тому или иному классу определяется значением первого октета (W).

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

Существуют статические и динамические алгоритмы обновления таблицы маршрутизации:

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

2. Случайная маршрутизация — передача данных из узла в любом, случайным образом выбранном направлении, кроме направления, по которому данные поступили в узел. Данные, совершая «блуждания» по сети с конечной вероятностью когда-либо достигают адресата.

3. Лавинная маршрутизация — передача данных из узла во всех направлениях, кроме того, по которому поступили данные. Очевидно, что хотя бы одно направление обеспечит доставку пакета за минимальное время, т.е. лавинная маршрутизация гарантирует малое время доставки.

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

• IGP (Interior Gateway Protocols) - внутренние протоколы маршрутизации, распространяют маршрутную информацию внутри одной автономной системы. Примеры: RIP, OSPF, IGRP.

• RIP (Routing Information Protocol) - протокол передачи маршрутной информации, маршрутизаторы динамически создают маршрутные таблицы.

• OSPF (Open Shortest Path First) - протокол «Использовать кратчайший путь", является внутренним протоколом маршрутизации. Разработан после RIP, является внутренним протоколом маршрутизации. Разработан после RIP, поддерживает маршрутизацию по нескольким путям, баланс их загрузки.

• EGP (Exterior Gateway Protocols) - внешние протоколы маршрутизации, распространяют маршрутную информацию между автономными системами. Примеры: EGP (Exterior Gateway Protocol, устарел), BGP.

• BGP (Border Gateway Protocol) - протокол граничных маршрутизаторов.

20 ARP-протокол, доставка IP-пакетов.

ARP (Address Resolution Protocol) — протокол сетевого уровня, предназначенный для преобразования IP-адресов (адресов сетевого уровня) в MAC-адреса (адреса канального уровня) в сетях TCP/IP.

Процесс доставки IP пакета

Путь есть две сети, подключенные соответственно к интерфейсам 1 и 2 маршрутизатора. Каждый сетевой интерфейс имеет IP-адрес и MAC-адрес. Пусть IP-модуль узла C направляет пакет узлу D. Протокол IP узла C определил IP-адрес интерфейса следующего маршрутизатора – это IP1. Теперь необходимо определить соответствующий MAC-адрес. Для этого протокол IP обращается у протоколу ARP, который поддерживает на каждом интерфейсе сетевого адаптера или маршрутизатора отдельную ARP-таблицу, в которой в ходе функционирования сети накапливается информация о соответствии между IP-адресами и MAC-адресами других интерфейсов данной сети. Первоначально, при включении компьютера или маршрутизатора в сеть, все его ARP-таблицы пусты.

1. На первом шаге происходит передача от протокола IP протоколу ARP примерно такого сообщения: «Какой MAC-адрес имеет интерфейс с IP₁?»

2. Работа протокола ARP начинается с просмотра ARP-таблицы соответствующего интерфейса. Предположим, что среди содержащихся в ней записей отсутствует запрашиваемый IP-адрес.

3. В этом случае исходящий IP-пакет, для которого оказалось невозможно определить локальный адрес из ARP-таблицы, запоминается в буфере, а протокол ARP формирует ARP-запрос, вкладывает его в кадр протокола Ethernet и широковещательно рассылает.

4. Все интерфейсы сети Ethernet1 получают ARP-запрос и направляют его «своему» протоколу ARP. ARP сравнивает указанный в запросе адрес IP₁ с IP-адресом интерфейса, на который поступил этот запрос. Протокол ARP, который констатировал совпадение (в данном случае это ARP маршрутизатора 1) формирует ARP-ответ.

В ARP-ответе маршрутизатор указывает локальный адрес MAC₁ своего интерфейса и отправляет запрашиваемому узлу (в данном примере узлу C), используя его локальный адрес. Широковещательный ответ в этом случае не требуется, так как формат ARP-запроса предусматривает поля локального и сетевого адресов отправителя.

5