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

Алгоритмы маршрутизации пытаются разработать таким образом, что­бы обеспечить самый короткий путь с минимальным временем доставки и наиболее полным использованием пропускной способности сети. Однако на эффективность работы алгоритма могут влиять также следующие ситуации: передача пакета в направлении, не обеспечивающем минимальное время доставки из-за перегрузки какого-то узла (перегрузка сети может происхо­дить из-за большого объема служебной информации, которая используется алгоритмом маршрутизации). Неоперативный учет изменения состояния сети, который обусловлен как отказами некоторых узлов и каналов, так и появлением новых узлов в связи с развитием сети. Для эффективной работы алгоритма необходимо каждый маршрутизатор снабжать информацией о текущей топологии сети, пропускной способности каналов. Любой маршру­тизатор работает в режиме неопределенности и пульсирующей нагрузки.

Таким образом, при разработке алгоритмов маршрутизации преследуются следующие цели:

Оптимальность – способность алгоритмов маршру­тизации выбирать «наилучший» маршрут;

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

Живучесть и стабильность – надежность функционирования в случае отказов аппаратуры;

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

Гибкость – умение быстро адаптироваться к изменению полосы, размером очереди.

На рис. 4.7 приведена классификация алгоритмов маршрутизации.

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

Рисунок 4.7

При маршрутизации по предыдущему опыту используется информация, которая накапливается в каждом маршрутизаторе (узле коммутации). Каж­дый пакет снабжен счетчиком, который определяет количество узлов, кото­рое он прошел. Накапливание этих данных позволяет создать таблицу, с помощью которой выбирается соответствующий маршрут. Этот алгоритм позволяет приспособиться к изменению топологии сети, но с большой за­держкой. При фиксированной маршрутизации алгоритм работает на основе анализа таблицы маршрутов, которая, как правило, создается сетевым ад­министратором, причем возможно составление таких таблиц с использова­нием альтернативных путей доставки информации к точке назначения. На­личие альтернативных путей позволяет повысить надежность сети при от­казе какого-либо из путей. Естественно, что статическая маршрутизация не позволяет учитывать изменяющуюся нагрузку сети, что приводит к повы­шению времени доставки пакета, если он попадает в перегруженный узел. Динамическая маршрутизация учитывает изменение топологии и состава сети. В этом случае каждый маршрутизатор получает информацию об из­менении топологии и изменении нагрузки в сети. При локальной маршру­тизации используется информация о состоянии не всей сети, а только опре­деленного конечного числа узлов, информация других узлов не учитывает­ся. Распределенная маршрутизация учитывает информацию, которая посту­пает из соседних узлов. Централизованная маршрутизация учитывает ин­формацию, поступающую из главного узла, причем каждый маршрутизатор передает информацию о своем состоянии в центральный узел, который ана­лизирует ее и передает каждому узлу в виде измененной таблицы маршрутизации. Гибридная маршрутизация предполагает использование как цен­трализованной, так и распределенной маршрутизации, чтобы не перегру­жать сеть служебной информацией.

Помазков Виталий Викторович

Описание

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

1. Определение оптимальных путей

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

1. Информацию о том, какие соединения приводят к определенным группам адресов.

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

3. Правила обработки как обычных, так и особых случаев трафика. Две важные задачи маршрутизаторов:

1. Маршрутизатор гарантирует, что информация не идет туда, где она не нужна.

2. Маршрутизатор гарантирует, что информация дойдет до предполагаемого адресата.

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

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

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

Типы алгоритмов

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

1. Статический и динамический

2. Одноканальный и многоканальный

3. Плоский и иерархический

4. Централизованный и распределенный

5. Host-Intelligent and Router-intelligent

6. Внутри доменный и меж доменный

7. Link-State или Distance-vector

Примерами алгоритмов маршрутизации на расстоянии являются:

· Протокол маршрутизации информации (RIP)

· Протокол маршрутизации внутренних шлюзов (IGRP)

· расширенный протокол маршрутизации внутренних шлюзов (EIGRP)

Примерами алгоритма маршрутизации состояния канала являются:

· Сначала открыть самый короткий путь (OSPF)

· Промежуточная система (IS-IS).

Список литературы :

1. Yashpaul Singh, M.K. Soni, and A.Swamp, «Simulation study of Multipath Routing Algorithm in different situations», IJCSNS International Journal of computer science and network security,Vol.7,No.ll,pp.295-297,2007

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

1 Оптимальность. Она характеризует способность алгоритма маршрутизации выбирать «наилучший» маршрут.

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

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

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

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

Алгоритмы маршрутизации могут быть классифицированы по типам. Например, алгоритмы могут быть:

1 Статическими или динамическими.

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

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

2 Одномаршрутными или многомаршрутными.

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

3 Одноуровневыми или иерархическими.

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

4 С интеллектом в главной вычислительной машине или в маршрутизаторе.

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

5 Внутридоменными и междоменными.

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

6 Алгоритмами состояния канала или вектора расстояний.

Алгоритмы состояния канала (известные также как алгоритмы «первоочередности наикратчайшего маршрута») направляют потоки маршрутной информации во все узлы объединенной сети. Однако каждый router посылает только ту часть маршрутной таблицы, которая описывает состояние его собственных каналов. Алгоритмы вектора расстояния (известные также как алгоритмы Белмана-Форда) требуют от каждого маршрутизатора посылки всей или части своей маршрутной таблицы, но только своим соседям. Алгоритмы состояния каналов фактически направляют небольшие корректировки по всем направлениям, в то время как алгоритмы вектора расстояний отсылают более крупные корректировки только в соседние router.

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

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

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

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

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

5.Внутридоменные или междоменные алгоритмы. Некоторые алгоритмы маршрутизации действуют только в пределах доменов; другие - как в пределах доменов, так и между ними.

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

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

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

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

Сходимость алгоритма – это когда алгоритм после некоторого времени приводит к однозначному результату.

8. Multipath Routing. Основная цель алгоритма - подсчёт альтернативных маршрутов и стоимости маршрутов. Стоимость - это вероятность использования альтернативного маршрута. В зависимости от этого каждый раз будет использоваться другой маршрут, что приведёт к уменьшению количества недоставленных пакетов. Использование этого метода делает компьютерную сеть очень надёжной. Метод чаще всего применяется для мобильных сетей, где состояние сети может часто изменяться и некоторые маршрутизаторы могут выходить из строя.

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

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

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

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

По степени обновляемости маршрутов выделяют:

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

По количеству используемых маршрутов различают:

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

Классификационным признаком алгоритмов может служить используемая структура маршрутизации, при этом:

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

Задачу выбора маршрута решают не только маршрутизаторы, но и оконечные узлы, поэтому выделяют два вида алгоритмов:

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

По способу обмена информацией о маршрутах различают:

• дистанционно-векторные алгоритмы или алгоритмы Бэлмана – Форда, которые обеспечивают пересылку всей или части маршрутной таблицы маршрутизатора своим ближайшим соседям;
• алгоритмы состояния канала, направляющие только ту часть маршрутной таблицы, которая описывает состояние собственных каналов маршрутизатора во все узлы объединенной сети. Их также называют алгоритмами первоочередности наикратчайшего маршрута. Отличительная особенность алгоритмов – более быстрая сходимость, меньшая склонность к образованию петель маршрутизации по отношению к дистанционно-векторным. Однако алгоритмы состояния канала характеризуются более сложными расчетами, требуя большей процессорной мощности и памяти.

Сведения о протоколах маршрутизации

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