Реферат: Алгоритмы и протоколы маршрутизации
1. Общие описание
Основнымиформами каждого маршрутизатора, реализуемым в соответствии с протоколами маршрутизации,являются:
Определениенаилучших маршрутов до возможных пунктов назначения и сохранение полученнойинформации в таблице маршрутизации;
Передачапакетов по оптимальным путям, выбранным из таблицы маршрутизации на основеадресов получателей.
Современныепротоколы маршрутизации предусматривают автоматическое формирование таблицмаршрутизации и поддержание их виртуального состояния на основе взаимодействиямаршрутизаторов друг с другом. На каждом маршрутизаторе функции определяютпрограммы опроса и прослушивания, с помощью которых он обменивается информациейс другими маршрутизаторами. Полученная информация используется для построения иобновления таблицы маршрутизации.
Таблицамаршрутизации, иногда называемая базой банных маршрутизации, включает набороптимальных путей, используемых маршрутизатором при передаче пакетов в данныймомент времени. Каждая строка этой таблицы содержит, по крайней мере, следующеюинформацию:
Сетевой адрес получателя
Адресследующего маршрутизатора, пересылка к которому соответствует оптимальному путидо пункта назначения;
Характеристикупути, например, пропускная способность канала связи и отметку времени, когдаэта характеристика была определена;
Информациюо способе пересылки, например, номер выходного порта.
Водной строке таблицы могут храниться данные о нескольких возможных следующихтранзитных маршрутизаторах, задающих различные критерии оптимальности пути.Способ выбора транзитного маршрутизатора зависит от используемой схемыпротокола маршрутизации.
Определениеоптимальности путей при формировании и обновлении таблицы маршрутизации можетпроизводиться в соответствии с такими критериями или их комбинациями, как:
Длинамаршрута, измеренная количеством маршрутизаторов, через которое необходимопройти до пункта назначения;
Пропускнаяспособность канала связи;
Прогнозируемоесуммарное время пересылки;
Стоимостьканала связи.
Приналичии таблицы маршрутизации функцию передачи пакетов по оптимальным путяммаршрутизатор реализует достаточно просто. Для отправки пакета через маршрутизаторузел локальной сети помещает в заголовок пакета на сетевом уровне мадуля OSI адрес действительного получателя, а наканальном уровне – MAC- адрес маршрутизатора. После полученияочередного пакета маршрутизатор выполняет следующие действия:
Считываетиз заголовка пакета, соответствующий сетевому уровню модели OSI, адрес назначения, т.е. сетевой адресполучателя;
Потаблице маршрутизации определяется адрес следующего транзитного маршрутизатора,пересылка к которому соответствует оптимальному пути до пункта назначения;
Заменяетв заголовке пакета, соответствующий канальному уровню модели OSI, свой МАС- адрес на МАС- адрес выбранноготранзитного маршрутизатора;
Отсылаетпакет выбранному транзитному маршрутизатору.
Помере того, как пакет передвигается через сеть, физический адрес (МАС- адрес)его получателя меняется, но логический адрес пункта назначения, соответствующийсетевому уровню модели OSI, остаетсябез изменений.
2. Требования к алгоритму маршрутизации
Алгоритмы,положенные в основу формирования и обновления таблицы маршрутизации, называюталгоритмами маршрутизации. В соответствии с данными алгоритмами и определяютсянаилучшие маршруты до возможных пунктов назначения. Алгоритмы передачи пакетовпо оптимальным путям, выбранным из таблицы маршрутизации, называютсяалгоритмами коммутации.
Алгоритмыкоммутации, задающие порядок транспортировки пакетов через сеть при известныхоптимальных маршрутах, являются достаточно простыми. Сложными и наиболееважными являются алгоритмы маршрутизации, которые и составляют основупротоколов маршрутизации. К данным алгоритмам предъявляют следующиефункциональные требования:
Пооптимизации определенных маршрутов – способности определять наилучший маршрут взависимости от заданных показателей и их весовых коэффициентов;
Погибкости – способность быстро и точно адаптироваться к изменениям структуры иусловий функционирования сети;
Посходимости – способности достичь быстрого соглашения между маршрутизаторнамисети по оптимальным маршрутам.
Впротоколах маршрутизации показатель оптимальности маршрута часто называютметрикой. Оптимальным считается кратчайший путь. При этом метрика, т.е. мерадлины пути задается определенной формулой, в качестве переменных, которой могутвыступать любые характеристики маршрута, например, общее число транзитныхмаршрутизаторов и суммарное время пересылки.
Требованияк алгоритмам маршрутизации по гибкости и сходимости взаимосвязаны друг сдругом. Когда в сети происходит какие- либо изменения, влияющие на выбороптимальных маршрутов, например, перегрузка какого- либо участка сети илипоявления нового канала связи, узнавшие первыми об этих измененияхмаршрутизаторы должны переопределить свои оптимальные маршруты, адаптируясь квозникшим изменениям. Кроме того, они должны разослать сообщения об измененияхдругим маршрутизаторам. Данные сообщения пронизывают сети, стимулируя пересчетоптимальных маршрутов. В конечном итоге все маршрутизаторы должны прийти кобщему соглашению по оптимальным маршрутам.
Алгоритмымаршрутизации, не обладающие высокой гибкостью и быстрой сходимостью, приводятк образованию петель маршрутизации и даже выхода сети из строя.
3. Классификация алгоритмов и протоколовмаршрутизации
Признакиклассификации алгоритмов и протоколов маршрутизации в большинстве случаев совпадаютдруг с другом. Наиболее важными признаками являются:
Степеньдинамичности, отражающая наличие или отсутствие гибкости и сходимости;
Количествоодновременно поддерживаемых маршрутов к одному пункту назначения;
Способорганизации маршрутов;
Областьвлияния;
Способполучения маршрутной информации.
Постепени гибкости и сходимости различают статические и динамические алгоритмымаршрутизации.
Статическиеалгоритмы представляют собой свод правил по запоминанию и использованиюстатических таблиц маршрутизации, которые не изменяются в автоматическомрежиме. Данные таблицы формируются и обновляются администратором, который самдолжен отслеживать все изменения в сети. Статические алгоритмы не обеспечиваютгибкость и сходность. Их целесообразно использовать только в простых инебольших сетях, где трафик является предсказуемым.
Динамическиеалгоритмы маршрутизации обеспечивают автоматическое формирование и обновлениетаблиц маршрутизации в масштабе реального времени. В соответствии с даннымиалгоритмами между маршрутизаторами осуществляется обмен сообщениями. Приотсутствии маршрутной информации маршрутизаторы запрашивают ее друг у друга. Вслучае возникновения изменений в сети мершрутизаторы уведомляют друг друга.Полученные друг от друга сообщения стимулируют пересчет оптимальных маршрутов иобновление таблиц маршрутизации в масштабе реального времени. Без динамическихалгоритмов маршрутизации администрирование больших и сложных сетей существеннозатрудняется. Все перечисленные ниже протоколы маршрутизации основаны надинамических алгоритмах:
Поколичеству одновременно поддерживаемых маршрутов к одному пункту назначенияалгоритмы маршрутизации могут иметь одномаршрутными или многомаршрутными.
Поспособу организации маршрутов различают алгоритмы одноуровневой и иерархическойорганизации.
Пообласти влияния алгоритмы маршрутизации могут быть внутредоменными имеждоменными.
Поспособу получения маршрутной информации различают алгоритмы вектора расстоянияи алгоритмы состояния канала.
Список литературы
ДжонВакка. Секреты безопасности в Internet.Перевод с английского. – Киев; Диалектика, 1997г.
ДжеймсСаймино. Сети интранет: внутреннее движение. Превод с английского. – М.: ООО«Бук Медиа Паблишер». 1997г.
ВладимирЗима. Безопасность глобальных сетевых технологий /В.М. Зима, А.А. и Н.А.Молдавян. СПб и др.: БХВ – Санкт – Петербург, 2000 г.
Дляподготовки данной работы были использованы материалы с сайта www.ed.vseved.ru/