Показатели алгоритмов (метрики)

используемые в алгоритмах маршрутизации:

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

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

Надежность

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

Задержка

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

Полоса пропускания

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

Нагрузка

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

Стоимость связи

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

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

Алгоритм Беллмана-Форда был положен ещё в основу первого протокола маршрутизации, созданного для сети ARPANET. Современные протоколы вектора расстояния (distance vector protocols), такие, как RIP, IGRP, BGP, используют те же принципы.

RIP

Протокол Информации Маршрутизации (RIP - Routing Information Protocol) был первоначально разработан в Xerox PARC (Xerox Palo Alto Research Center) и использовался в комплекте протоколов ХNS. RIP для TCP/IP опубликован в 1982 г., когда версию UNIX, называемую Berkeley Standard Distribution (BSD), начали распространять с одной из реализацией RIP, крторую называли "трассируемой" (routed). Протокол RIP, который все еще является очень популярным протоколом маршрутизации в малых сетях, формально определен в публикации "Протоколы транспортировки Internet" XNS (XNS Internet Transport Protocols) (1981 г.) и в (Request for Comments) - RFC 1058 (1988 г.).

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

IP-адрес места назначения.

Метрику маршрута (от 1 до 15; число шагов до места назначения).

IP-адрес ближайшего маршрутизатора (gateway) по пути к месту назначения.

Таймеры маршрута.

Первым двум полям записи мы обязаны появлению термина вектор расстояния (место назначение - направление; метрика - модуль вектора). Периодически (раз в 30 сек) каждый маршрутизатор посылает широковещательно копию своей маршрутной таблицы всем соседям-маршрутизаторам, с которыми связан непосредственно. Маршрутизатор-получатель просматривает таблицу. Если в таблице присутствует новый путь или сообщение о более коротком маршруте, или произошли изменения длин пути, эти изменения фиксируются получателем в своей маршрутной таблице. RIP поддерживает только оптимальные маршруты к пункту назначения. Если новая информация обеспечивает лучший маршрут, то эта информация заменяет старую маршрутную информацию.

Протокол RIP должен быть способен обрабатывать следующие типы ошибок:

1. Циклические маршруты. Так как в протоколе нет механизмов выявления замкнутых маршрутов, необходимо либо слепо верить партнерам, либо принимать меры для блокировки такой возможности.

2. Для подавления нестабильностей RIP должен использовать малое значение максимально возможного числа шагов (<16).

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

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

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

-ограничение числа пересылок,

-расщепление горизонта (split-horizons)

-временные задержки изменений (hold-downs),

-корректировки отмены (poison reverse updates).

Достоинства RIP – простота и быстрая реакция на хорошие новости (появление в сети нового маршрутизатора), а недостаток - очень медленная реакция на плохие известия (исчезновение одного из соседей).

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

Распространение "хорошей" новости в сети.

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

Во время первого обмена узел B узнает, что A заработал и вносит в свою таблицу маршрутизации "1" как расстояние до A; все остальные узлы в этот момент по-прежнему считают A недоступным. При следующем обмене, спустя несколько секунд, узел C также узнает о появлении маршрутизатора A. В результате последовательности таких обменов информация достигнет и узла E, для которого стоимость маршрута до А будет "4".

Таким образом, для сети с максимальной длиной маршрута N сообщение о новом маршрутизаторе дойдет до самого удаленного узла в сети через N-1 циклов обмена таблицами маршрутизации. На этом этапе никаких проблем не возникает.

 

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

Проблема возрастания до бесконечности.

Во время следующего обмена C замечает, что оба его соседа предлагают путь до A стоимостью "3", и немедленно делает поправки в своей таблице. Теперь длина пути от С до A - "4". Если этот процесс не остановить, то он может продолжаться до бесконечности, и никто так и не узнает, что маршрутизатор А давно вышел из строя. Соответственно данные к А будут посылаться и дальше.

Эта проблема алгоритма вектора расстояний получила название проблемы возрастания до бесконечности (count-to-infinity problem). Она является основной причиной задания ограничений на максимальную длину пути во всех протоколах вектора расстояния. Протокол RIP считает маршрут длиной более чем в 15 транзитных узлов бесконечным. Такой путь будет немедленно удален из таблицы маршрутизации. Т. е. в последнем примере узел B поймет, что узел А недоступен, когда получит объявление пути до А со стоимостью "15". К сожалению, такая процедура будет занимать слишком много времени.

 

Расщепление горизонта

Один из методов борьбы с проблемами алгоритма вектора расстояний - расщепления горизонта (split-horizon). Данное простое правило можно сформулировать следующим образом: «Если известно, что путь до узла X лежит через соседний узел Y, то узлу Y не надо посылать объявления маршрута до X".

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

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

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

В начальный момент времени А и B знают, что расстояние до узла D равно "2". После выхода D из строя маршрутизатор C, не получив от D сообщения, определяет, что узел D недоступен. А и В продолжают считать D доступным, но правило расщепления горизонта запрещает им сообщать эту ложную информацию маршрутизатору С. При следующем обмене C уведомляет A и B о недоступности D. Но одновременно с этим узел А получает от В сообщение о пути до D стоимостью "2", а узел В получает аналогичное сообщение от А.

Информация об аварии на D не будет услышана. Проблема возрастания до бесконечности возникла вновь.