Размещено на http://www.allbest.ru/

Анализ алгоритмов маршрутизации в вычислительных сетях

Маршрутизация сводится к определению направлений движения пакетов в маршрутизаторах. Цель маршрутизации - доставка пакетов по назначению с максимизацией эффективности. Чаще всего эффективность выражена взвешенной суммой времен доставки сообщений при ограничении снизу на вероятность доставки. Выбор одного из возможных в маршрутизаторе направлений зависит от текущей топологии сети (она может меняться хотя бы из-за временного выхода некоторых узлов из строя), длин очередей в узлах коммутации, интенсивности входных потоков и т.п.[1]

Алгоритмы маршрутизации включают процедуры:

- измерение и оценивание параметров сети;

- принятие решения о рассылке служебной информации;

- расчет таблиц маршрутизации (ТМ); реализация принятых маршрутных решений.

Требования к алгоритмам маршрутизации:

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

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

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

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

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

Все алгоритмы маршрутизации можно классифицировать как:

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

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

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

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

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

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

Протокол RIP

Протокол маршрутизации[2] RIP (Routing Information Protocol) относится к алгоритмам класса «distance vector». Этот алгоритм является одним из первых алгоритмов маршрутизации, которые были использованы в информационно-вычислительных сетях вообще и в сети Internet - в частности. Протокол RIP не обеспечивает решение всех возможных проблем, которые могут возникнуть в процессе определения маршрута в сетях передачи данных. В первую очередь, он предназначен для использования в качестве IGP в гомогенных сетях небольшого размера. Кроме того, использование данного протокола приводит к появлению специфических ограничений на параметры сети, в которой он может быть использован. Использование протокола RIP целесообразно в сетях, самый длинный путь в которых составляет не более 15 переходов (hops). Данное ограничение определяется способом вычисления маршрута, который принят в данном алгоритме, и не может быть преодолено. Использование протокола RIP может в ряде случаев привести к появлению «зацикленных маршрутов». Для предотвращения возникновения подобных ситуаций должны быть использованы специальные меры (poison reverse, split horizon). Для сравнения маршрутов протокол RIP использует достаточно простую «метрику» - число переходов. Однако использование данного критерия в целом ряде случаев не может обеспечить оптимальный выбор маршрута.

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

Протокол OSPF является стандартным протоколом маршрутизации для использования в сетях IP. Основные принципы организации современной версии протокола маршрутизации OSPF изложены в RFC 2328. Протокол OSPF представляет собой классический протокол маршрутизации класса Link-State, который обеспечивает:

· отсутствие ограничений на размер сети,

· поддержку внеклассовых сетей,

· передачу обновлений маршрутов с использованием адресов типа multicast,

· достаточно большую скорость установления маршрута,

· использование процедуры authentication при передаче и получении обновлений маршрутов.

Преимущества использования протокола OSPF:

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

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

2. Распределение нагрузки между параллельными каналами (Load balancing). При использовании протокола маршрутизации OSPF допускается существование нескольких маршрутов в направлении некоторого узла сети. В том случае, если эти маршруты обеспечивают одинаковое качество передачи данных, информационный поток в адрес данного узла может быть направлен по всем этим каналам одновременно, что обеспечит существенное увеличение скорости передачи данных. Динамическое перераспределение трафика между параллельными каналами, которое выполняется пропорционально степени загруженности этих каналов, называется Load balancing.

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

Примечательной особенностью протокола маршрутизации OSPF является использование адресов типа multicast для информационного обмена между маршрутизаторами в процессе определения маршрута. Использование таких адресов позволяет отказаться от использования адресов типа broadcast, что в свою очередь приводит к повышению эффективности использования вычислительных ресурсов сети. Еще одной важной особенностью процесса организации информационного обмена у протокола маршрутизации OSPF является также использование аппарата «назначенных» (designated) маршрутизаторов. Использование этой возможности позволяет существенно сократить объем служебного трафика в том случае, когда несколько маршрутизаторов подключены к одной сети.

· пропускная способность канала,

· величина задержки распространения сигнала в канале,

· надежность канала,

· загруженность канала,

· размер максимального блока данных, который может быть передан через данный канал.

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

Протоколы внешней маршрутизации

Протоколы этого типа используются для определения маршрутов передачи данных между различными автономными системами. Такие протоколы обычно относят к классу Exterior Gateway Protocol. В настоящее время существуют два протокола данного типа:

· Border Gateway Protocol

· Exterior Gateway Protocol

Два маршрутизатора, которые обмениваются информацией о маршрутах, называются внутренними соседями в том случае, если они принадлежат к одной автономной системе и внешними - в том случае, если они принадлежат к различным автономным системам. На рисунке 2 маршрутизаторы R2, R4 являются внутренними для автономных систем AS N и AS M соответственно. R1 и R3 совмещают функции внешнего и внутреннего маршрутизаторов. Маршрутизатор R1 представляет для автономной системы AS M маршруты к сетям, которые находятся в автономной системе AS N. Аналогичную функцию выполняет маршрутизатор R3 по отношению к маршрутам AS M.

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

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

Основные принципы построения протокола маршрутизации EGP определены в RFC 904 . Этот протокол маршрутизации имеет три основные черты:

· Использование механизма установления отношений между маршрутизаторами neighbor acquisition.

· Маршрутизаторы EGP используют специальный механизм для определения статуса своих партнеров по протоколу.

· Маршрутизаторы EGP периодически обмениваются информацией о достижимости сетей путем передачи сообщений об обновлениях маршрутов.

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

· Сообщения Neighbor Acquisition Messages,

· Сообщения Neighbor Reach ability Messages,

· Сообщения Poll Request Messages,

· Сообщения Routing Update Messages.

Сообщения об установлении отношений (Neighbor Acquisition). Сообщения этого типа маршрутизатор передает в том случае, когда собирается установить с другим маршрутизатором отношения в соответствии с алгоритмами информационного обмена EGP.

Сообщения проверки состояния соседа Neighbor Reach ability. Сообщения этого типа маршрутизатор передает в том случае, когда хочет установить, в каком состоянии находится соседний маршрутизатор. Когда маршрутизатор находится в активном состоянии, он периодически посылает сообщения Hello вместе с обновлениями маршрутов и ожидает ответа от соседа. Если маршрутизатор находится в пассивном режиме, он может использовать содержимое поля STATUS для определения состояния соседа вместо того, чтобы периодически опрашивать его. Обычно оба маршрутизатора находятся в активном состоянии.

Сообщения проверки состояния маршрута Poll Request. Сообщения этого типа маршрутизатор передает в том случае, когда хочет установить, достижима или нет сеть SOURCE NETWORK.

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

Как уже было выше отмечено, описание метрики маршрута в протоколе EGP указывается относительно общей сети, которая называется SOURCE NETWORK. Это является существенным отличием данного протокола от протоколов класса IGP.

Сообщение Error Response/Indication. Маршрутизатор EGP использует сообщения этого типа для того, чтобы предупредить соседний маршрутизатор о возникновении нештатной ситуации.

Протоколу EGP свойственен ряд существенных недостатков:

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

2. Маршрутизатор EGP не поддерживает внеклассовые сети.

Протокол маршрутизации BGP.

Протокол маршрутизации BGP (Border Gateway Protocol RFC 1771) представляет собой более современный, чем протокол EGP, протокол внешней маршрутизации автономных систем. Оба этих протокола построены по примерно одинаковой схеме, однако протокол BGP имеет ряд существенных преимуществ по отношению к EGP.

· Inter-autonomous system routing - маршруты, которые соединяют данную автономную систему с одной или несколькими другими автономными системами.

· Intra-autonomous system routing - протокол может быть использован для определения маршрута внутри автономной системы, в том случае, когда несколько маршрутизаторов участвуют в процессе определения маршрута BGP.

· Pass-through autonomous system - протокол может быть использован для определения маршрутов, которые проходят через автономную систему, не участвующую в процессе BGP.

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

· Начало сеанса (Open).

· Для периодической проверки состояния соседа (Keep Alive).

· При изменении содержания таблицы маршрутов автономной системы(update).

· При возникновении аварийной ситуации(Notification).

Характеризуемые далее протоколы маршрутизации EIGRP и BGP представляют собой дальнейшее развитие протоколов класса IGP и EGP, соответственно.

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

Протокол IGRP предназначен для определения маршрутов, которые расположены внутри автономных систем и относится поэтому к классу протоколов Interior Gateway Protocol. По способу сбора информации о маршрутах внутри автономной системе этот протокол относится к типу distant-vector.

· Flash updates - управляемые обновления передаются в момент возникновения изменений в сети

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

· Split horizon - для предотвращения возникновения циклов обновления для маршрутов, которые были получены с определенного направления, не должны передаваться в этом направлении.

· Poison reverse - возрастание метрики маршрута обычно является следствием существования петли маршрутизации. Для блокирования маршрутов, метрика которых начинает неуклонно расти, им обычно присваивается значение метрики, которое соответствует бесконечности.

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

При пропадании канала, который связывает центральный маршрутизатор с глобальной сетью, этот маршрутизатор формирует управляемые обновления для данной сети и переходит в режим hold down, в котором он не может принимать информацию о маршрутах для этой сети. Его ближайшие соседи в соответствии с принципом Split Horizon не должны передавать ему обновления для данного маршрута. Для того, чтобы исключить этот маршрут из таблиц маршрутизации соседей следующего уровня, маршрутизаторы могут использовать функцию Poison Reverse.

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

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

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

Протокол маршрутизации Enhanced IGRP был разработан специалистами компании Cisco и представляет собой дальнейшее развитие принципов, которые были заложены в IGRP. В частности, по отношению к протоколу IGRP обеспечиваются следующие дополнительные возможности:

· Поддержка внеклассовых IP сетей.

· Передача частичных обновлений таблицы маршрутов.

· Поддержка различных протоколов сетевого уровня.

Формально протокол EIGRP относится к алгоритмам маршрутизации типа distant - vector, однако этот протокол сочетает в себе лучшие качества протокола типа linkstate и поэтому может быть отнесен к особому типу протоколов маршрутизации - к гибридным протоколам.

Для сокращения временного интервала, отделяющего изменение, которое произошло в структуре сети, от соответствующего изменения информации о маршрутах в системе в протоколе маршрутизации EIGRP, используется несколько специальных механизмов передачи частичных обновлений  и алгоритм DUAL - Diffuse Update Algorithm. Данный алгоритм был разработан в SRI International доктором J.J. Garcia - Luna - Aceves. Использование данного алгоритма предполагает определение для представления маршрута для каждой сети двух специальных маршрутизаторов - successor и feasible successor.

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

· Advertised Distance - представляемая дистанция,

· Feasible Distance - ожидаемая дистанция.

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

Ожидаемая дистанция представляет собой метрику, которая соответствует значению Advertised Distance для данного маршрута, увеличенную на стоимость последнего участка маршрута - от представляющего маршрутизатора до конечного.

Последующим маршрутизатором (successor) для сети считается тот маршрутизатор из числа непосредственных соседей, через который проходит маршрут до данной сети, которому соответствует минимальное значение Advertised Distance. Этот маршрутизатор  используется в качестве next hop для доставки пакетов в данную сеть.

Потенциальным последующим маршрутизатором (feasible successor) для сети считается тот маршрутизатор из числа непосредственных соседей, через который проходит маршрут до данной сети, которому соответствует значение Advertised Distance меньшее, чем значение Feasible Distance маршрута, проходящего через Successor.

Маршрут, который проходит через Feasible Successor, используется в системе в качестве резервного маршрута. В том случае, если маршрут через successor по каким - либо причинам не может быть использован для передачи данных, маршрутизатор должен произвести переключение на резервный маршрут.

Литература

маршрутизация алгоритм непроизводительный

1. Отвагин А. В. Параметры и классы протоколов маршрутизации // А.В. Отвагин. - Режим доступа: [http://skif.bas-net.by/bsuir/base/node360.html 2002.12.16].

2. Филимонов А.Ю. Протоколы маршрутизации // Сети ЭВМ и телекоммуникации. - Режим доступа [http://lectures.by.ru/tcpip/ 23.09.2004].

Размещено на Allbest.ru