Разделы

Авто
Бизнес
Болезни
Дом
Защита
Здоровье
Интернет
Компьютеры
Медицина
Науки
Обучение
Общество
Питание
Политика
Производство
Промышленность
Спорт
Техника
Экономика

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

Маршрутизация. Классификация алгоритмов и протоколов.

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

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

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

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

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

1) Определение наилучших маршрутов до возможных пунктов назначения и сохранение полученной информации в таблице маршрутизации;

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

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

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

1) Сетевой адрес получателя;

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

3) Характеристику пути, например, пропускная способность канала связи и отметку времени, когда эта характеристика была определена;

4) Информацию о способе пересылки, например, номер выходного порта.

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

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

1) Длина маршрута, измеренная количеством маршрутизаторов, через которое необходимо пройти до пункта назначения;

2) Пропускная способность канала связи;

3) Прогнозируемое суммарное время пересылки;

4) Стоимость канала связи.

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

1) Считывает из заголовка пакета, соответствующий сетевому уровню модели OSI, адрес назначения, т.е. сетевой адрес получателя;

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

3) Заменяет в заголовке пакета, соответствующий канальному уровню модели OSI, свой МАС- адрес на МАС- адрес выбранного транзитного маршрутизатора;

4) Отсылает пакет выбранному транзитному маршрутизатору.

По мере того, как пакет передвигается через сеть, физический адрес (МАС- адрес) его получателя меняется, но логический адрес пункта назначения, соответствующий сетевому уровню модели OSI, остается без изменений.

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

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

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

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

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

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

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

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

- лавинная маршрутизация – во все направления, кроме исходного;

- по предыдущему опыту – таблица маршрутизации составляется на основе данных, содержащихся в проходящих через маршрутизатор.

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

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

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

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

- корректность – алгоритм должен быть работоспособным и не содержать логических противоречий

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

- адаптивность к изменениям трафика и топологии – алгоритм должен определять новое множество маршрутов доведения при изменении условий.

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

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

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

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

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

 

Классификация алгоритмов и протоколов маршрутизации

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

1) Степень динамичности, отражающая наличие или отсутствие гибкости и сходимости;

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

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

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

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

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

3) Способ организации маршрутов;

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

4) Область влияния;

По области влияния алгоритмы маршрутизации могут быть внутредоменными и междоменными.

5) Способ получения маршрутной информации.

По способу получения маршрутной информации различают алгоритмы вектора расстояния (алгоритм Беллмана-Форда) и алгоритмы состояния канала (алгоритм Дейкстра).

 

Дата публикации:2014-01-23

Просмотров:501

Вернуться в оглавление:

Комментария пока нет...


Имя* (по-русски):
Почта* (e-mail):Не публикуется
Ответить (до 1000 символов):







 

2012-2018 lekcion.ru. За поставленную ссылку спасибо.