Конспект лекций

Уровни работы маршрутизации

o Уровень маршрутизации. На этом уровне происходит работа с таблицей маршрутизации. Таблица маршрутизации служит для определения адреса (сетевого уровня) следующего маршрутизатора или непосредственно получателя по имеющемуся адресу (сетевого уровня) и получателя после определения адреса передачи выбирается определенный выходной физический порт маршрутизатора. Этот процесс называется определением маршрута перемещения пакета.

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

o Уровень передачи пакетов. Перед тем как передать пакет, необходимо: проверить контрольную сумму заголовка пакета, определить адрес (канального уровня) получателя пакета и произвести непосредственно отправку пакета с учетом очередности, фрагментации, фильтрации и т.д. Эти действия выполняются на основании команд, поступающих с уровня маршрутизации.

В связи с этим можно провести следующую аналогию.

Интерпретация процесса маршрутизации

Маршрутизация бывает

Выделяют два типа маршрутизации : прямую и косвенную. При прямой маршрутизации отправитель в определенной IP-сети может напрямую передавать кадры любому получателю в той же сети. При этом не требуется функциональность IP-маршрутизации.

Косвенная маршрутизация происходит в том случае, если отправитель и получатель находятся в разных IP-сетях. Косвенная маршрутизация требует, чтобы отправитель передавал пакеты маршрутизатору для доставки их через распределённую сеть.

На рисунке, если узел 10.2.2.1 захочет послать пакет узлу в пределах сети 10, например, 10.2.2.2, то это будет прямая маршрутизация, а при отправке пределов в сеть, скажем, 192.168.1 – косвенная.

Прямая маршрутизация

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

Узлу 10.1.1.1 необходимо передать пакет узлу 10.2.2.2. Первое, что он делает - определяет , находится ли IP-адрес получателя в одной с ним сети. Для этого сравнивает свой номер сети 10 с номером сети получателя 10. Делает вывод, что узел-получатель находится в одном с ним сегменте сети.

С помощью протокола APR определяет MAC-адрес узла-получателя и посылает пакет по этому адресу.

Косвенная маршрутизация

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

1.Изучение адреса показывает, что узел назначения находится не а одной с предающим узлом сети. Узел 10.1.1.1 сконфигурирован так, что любые пакеты, требующие косвенной маршрутизации, передаются его шлюзу по умолчанию - маршрутизатору 1.

2.Чтобы доставить пакет маршрутизатору 1, узлу 10.1.1.1 необходим MAC-адрес маршрутизатора 10.3.3.3. Если МАС-адрес узлу 10.1.1.1 неизвестен, он отправляет ARP-запрос, чтобы его получить. Затем

3.Маршрутизатор 1 осознает, что он подсоединен к сети 172.16. и полагает, что узел 172.16.0.1 должен быть частью этой сети. Маршрутизатор 1 реализует свою собственную процедуру прямой маршрутизации и посылает ARP-запрос, ища узел назначения.

При отправке пакета от узла 10.1.1.1 до узла 192.168.1.1 узел-отправитель сравнит номер своей сети с номером сети назначения и выяснит, что получатель находится в другой сети. Пакет будет отпрален шлюзу по умолчанию, в данном случае Маршрутизатору 1. Пусть в таблице маршрутизатора нет записи о сети 192.168.1, но шлюзом по умолчанию является маршрутизатор 2, тогда он перешлет пакет ему, а тот доставит пакет до получателя.

Если же узел 10.1.1.1 попытается отправить пакет узлу 192.164.1.1, то этот пакет будет перенаправлен маршрутизатору 1. Но так как он ничего не знает про сеть 192.164.1 , то будет выполнено одно из самых главных правил маршрутизации: если пакет получен, и таблица маршрутизации не

содержит информации о его сети назначения, пакет следует отбросить.

Таблица маршрутизации для IP-сетей

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

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

Вэтой таблице в столбце

Адрес сети назначения – указываются адреса всех сетей, которым данный маршрутизатор может передавать пакеты

Следующий маршрутизатор в пути – IP-адрес удаленного маршрутизатора, которому необходимо послать пакет для доставки его по назначению

Номер выходного порта – по которому следует отправить пакет

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

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

Подходы к выбору маршрута

В стеке TCP/IP к оптимизации маршрута продвижения пакета

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

Источники записей в таблице маршрутизации

Записи о непосредственно подключенных сетях и маршрутизаторах по умолчанию

Адреса особого назначения

Записи, введенные принудительно администратором сети

Записи, полученные в результате работы протоколов маршрутизации

Маршрутизатор как устройство доставки пакета

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

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

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

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

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

При разработке тех или иных алгоритмов к ним применяют следующие требования:

Оптимальность выбора маршрута

Экономичность реализации

Устойчивость

Быстрая сходимость

Гибкость реализации

Оптимальность

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

Как известно понятие оптимальность определяется по какому-то конкретному критерию, в данном случае им может быть

Возможные метрики критерия оптимальности

 Длина маршрута

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

на пути от источника до пункта назначения через устройства объединения сетей (такие как маршрутизаторы).

 Надежность маршрута

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

 Задержка при передаче пакетов

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

 Ширина полосы пропускания

Полоса пропускания относится к имеющейся мощности трафика какого-либо канала. При прочих равных показателях, канал Ethernet 10 Mbps предпочтителен любой арендованной линии с полосой пропускания 64 Кбайт/сек. Хотя полоса пропускания является оценкой максимально достижимой пропускной способности канала, маршруты, проходящие через каналы с большей полосой пропускания, не обязательно будут лучше маршрутов, проходящих через менее быстродействующие каналы.

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

Конфликт между оптимальностью и справедливостью маршрута

Предположим, что трафик между станциями А и А', В и В', а также С и С' настолько интенсивный, что горизонтальные линии связи оказываются

полностью насыщенными. Чтобы максимизировать общий поток данных, трафик между станциями X и X' следовало бы совсем отключить.

Однако, станции X и X', скорее всего, имеют другую точку зрения по этому вопросу.

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

Экономичность реализации

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

Устойчивость

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

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

Сходимость Сходимость – это процесс согласования между маршрутизаторами

информации о топологии сети.

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

Иными словами:

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

Пример сети с петлей маршрутизации

На рисунке изображена петля маршрутизации.

В данном случае, в момент времени t1 к маршрутизатору 1 прибывает пакет. Маршрутизатор 1 уже был обновлен и поэтому он знает, что оптимальный маршрут к пункту назначения требует, чтобы следующей остановкой был маршрутизатор 2. Поэтому Маршрутизатор 1 пересылает пакет в маршрутизатору 2. Маршрутизатор 2 еще не был обновлен, поэтому он полагает, что следующей оптимальной пересылкой должен быть маршрутизатор1. 1. Поэтому маршрутизатор 2 пересылает пакет обратно в маршрутизатору 1. Пакет будет продолжать скакать взад и вперед между двумя маршрутизаторами до тех пор, пока маршрутизатор 2 не получит корректировку маршрутизации, или пока число коммутаций данного пакета не превысит допустимого максимального числа.

Лекция 11. Алгоритмы маршрутизации

Табличные методы маршрутизации, в зависимости от момента формирования таблиц маршрутов выделяют

 Статические и динамические алгоритмы маршрутизации При статической маршрутизации таблицы маршрутов формируются при

генерации сети и в последующем, как правило, не изменяются. И только при

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

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

Статические

В таких алгоритмах все записи в таблице маршрутизации являются фиксированными. Администратор сети сам решает, на какие маршрутизаторы надо передавать пакеты с теми или иными адресами, и вручную(например, с помощью утилиты route ОС Unix или WindowsNT) заносит соответствующие записи в таблицу маршрутизации.

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

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

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

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

Динамические

Эти алгоритмы обеспечивают автоматическое обновление таблиц маршрутизации после изменения конфигурации сети.

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

В таблицах маршрутизации при динамической маршрутизации обычно имеется информация об интервале времени, в течение которого данный маршрут будет оставаться действительным. Это время называют временем жизни маршрута(Time To Live, TTL).

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

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

Динамические алгоритмы в свою очередь делятся на

Дистанционно-векторые алгоритмы

Алгоритмы состояния связей

Принцип работы этих алгоритмов будет подробно рассмотрен в разделе протоколов маршрутизации.

Динамическая маршрутизация

Таким образом, динамическая маршрутизация – это сложный процесс, включающий:

Формирование маршрутов, осуществляемое с помощью алгоритмов маршрутизации путём составления в каждом узле коммутации таблиц маршрутов пакетов

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

Контроль состояния сети, в том числе анализ топологии сети, структуры потоков и задержек в узлах коммутации

Передачу информации о состоянии сети, используемую для корректировки таблиц маршрутов

Корректировку самих маршрутов

По количеству определяемых маршрутов до узла-получателя алгоритмы маршрутизации делятся на

 Одномаршрутные и многомаршрутные

Одномаршрутные и многомаршрутные

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

С целью выравнивания нагрузки на основных(магистральных) каналах передачи данных используют многомаршрутные алгоритмы.