Основные термины 1Р-маршрутизации. Автономные системы

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

Рисунок 59. Структурная схема информационного взаимодействия на основе автономныхсистем.

 

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

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

• определение маршрута внутри автономной системы

• определение маршрута между автономными системами

Для обеспечения этого взаимодействия коммуникационные узлы автономной системы должны предоставлять информацию о состоянии маршрутов к сетям данной автономной системы. Кроме того, коммуникационные узлы должны обеспечивать предоставление информации о маршрутах, по которым должны быть переданы данные для достижения компонентов, расположенных в других автономных системах. В том случае, когда автономная система использует несколько физических каналов для организации информационного обмена с остальным миром, такая задача является особенно актуальной. В зависимости от своего расположения в общей структуре Интернет автономная система может быть тупиковой (stub) - имеющей связь только с одной АС, или многопортовой (multihomed), т.е. имеющей связи с несколькими АС. Если административная политика автономной системы позволяет передавать через свои сети транзитный трафик других АС, то такую автономную систему можно назвать транзитной (transit). Внедрение идеологии автономных систем сделали возможным существенно облегчить процедуру маршрутизации, сократить требуемое число IP-адресов и создать гибкую и эффективную схему описания маршрутной политики.

Метрики, используемые алгоритмами маршрутизации

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

1. Длина маршрута является наиболее общим показателем маршрутизации. Единица измерения длины маршрута в числе промежуточных узлов, включая также узел назначения - это количество хопов (от англ. hop - "скачок"). Длина маршрута от себя до себя равна 0, от себя до другого узла в этой же сети - 1 хоп. Как правило, чем меньше величина скачков, тем лучше путь.

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

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

5. Загрузка - объем действий, выполняемый сетевым ресурсом, например маршрутизатором или каналом:

• процент пакетов, сброшенных из-за нехватки памяти в буферах;

• средняя длина очередей в системе;

• число пакетов, для которых наступил тайм-аут и для которых были сделаны повторные передачи;

• средняя задержка пакета при доставке и среднее отклонение задержки при доставке пакета.

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

2.3. Свойства алгоритма маршрутизации

Алгоритм маршрутизации должен обладать рядом свойств:

1. Корректность.

2. Оптимальность.

3. Простота и низкие непроизводительные затраты.

4. Живучесть и стабильность.

5. Справедливость.

6. Быстрая сходимость.

7. Гибкость.

Если корректность комментариев не требуют, то остальные свойства надо разъяснить.

Оптимальность

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

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

 

 

Рисунок 60. (а) Подсеть. (Ь) Дерево погружения длямаршрутизатора В.

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

Простота и низкие непроизводительные затраты

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

Живучесть и стабильность

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

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

Справедливость

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

Рисунок 61. Конфликт между справедливостью и оптимальностью.

 

Трафики между А-А", В-В", С-С" могут уже забить канал между Х-Х". Поэтому вместо кратчайшего маршрута между X и X" надо будет выбирать какой-то другой маршрут.

Быстрая сходимость

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

Гибкость

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

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

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

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

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

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

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

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

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

Статические или динамические алгоритмы

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

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

Немаловажный недостаток динамической маршрутизации - она имеет тенденцию к полной открытости всей информации о сети.

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

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

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

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

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

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

Внутридоменные или междоменные алгоритмы

Некоторые алгоритмы маршрутизации действуют только в пределах доменов (автономных систем). Такие алгоритмы называются внутридоменными и относятся к классу interior gateway protocol - ЮР. Другие алгоритмы маршрутизации используются для определения маршрута за пределами домена (автономной системы). Данные алгоритмы называются междоменными и относятся к классу exterior gateway protocol - EGP. Природа этих двух типов алгоритмов различная. Поэтому понятно, что оптимальный алгоритм внутридоменной маршрутизации не обязательно будет оптимальным алгоритмом междоменной маршрутизации.

Алгоритмы с маршрутизацией от источника или в роутере

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

Алгоритмы (протоколы) вектора расстояния или состояния канала

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

• Протоколы вектора расстояния (Distance Vector).

• Протоколы состояния канала (Link State).

• Гибридный подход, объединяющий аспекты алгоритмов с определением вектора расстояния и оценки состояния канала.

4. Алгоритмы маршрутизации
4.1. Алгоритмы вектора расстояния

Алгоритмы вектора расстояния построены на основе алгоритмов Бэлмана-Форда и Форда-Фолкерсона. В основе их лежит идея, что у каждого маршрутизатора в подсети есть:

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

• Кроме этого, каждый маршрутизатор в подсети постоянно замеряет задержки до своих соседей.

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

Рисунок 62. Работа алгоритма вектора расстояния.

 

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

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

• предусматривают передачу информации о маршрутах периодически через установленные интервалы времени.

Опишем проблемы, характерные для всех протоколов, базирующихся на векторе расстояния, и способы их решения:

1. Проблема бесконечного счетчика.

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

Рисунок 63. Проблема бесконечного счетчика.

 

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

Теперь рассмотрим обратную ситуацию на рисунке 63 (Ь). Здесь изначально все маршрутизаторы и линии были работоспособны. Пусть в какой-то момент времени линия между А и В разрушена. В перестает видеть А, но С говорит В: «Не беспокойся у меня есть маршрут до А». При этом В не подозревает, что маршрут от С до А идет через него же. При этом маршрутизаторы D и Е своих таблиц не меняют. Их расстояния до А на единицу больше, чем у С. Плохая весть будет распространяться медленно пока счетчики задержек не примут значения бесконечности для данной сети. Только после этого станет ясно, что А не достижимо ни через С, ни через D, ни через Е. Сколько времени на это потребуется, зависит от конкретного значения бесконечности в данной подсети.

Алгоритм Split Horizon (разделение направлений) предназначен для решения выше описанной проблемы. Маршрутизатор, используя данное правило, разделяет свои маршруты на столько групп, сколько у него есть активных интерфейсов. Далее обновления (вектора) для маршрутов, которые были получены через некоторый интерфейс, не должны передаваться через этот же интерфейс. Если теперь рассмотреть, как будет работать подсеть на рисунке 63 (Ь), то там проблем возникать не будет. Однако, рассмотрим подсеть на рисунке 64. Если линия между С и D будет разрушена, то С сообщит об этом А и В. Однако, А знает что у В есть маршрут до D, а В знает

Рисунок 64. Пример неработоспособности алгоритма Split Horizon.

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

 

Алгоритм Poison Reverse (отравленный реверс) является другим способ решения проблемы бесконечного счетчика (или маршрутной петли). Алгоритм гласит – однажды изучив маршрут через какой-либо интерфейс, объявляй этот маршрут как «недоступный» обратно через тот же самый интерфейс.

2. Проблема циклических маршрутов.

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

4.2. Алгоритмы состояния канала

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

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

Рисунок 65. Первые пять шагов, используемые при вычислении кратчайшего пути от А до D.

 

Расстояние можно измерять в скачках, а можно в километрах. Тогда маршрут ABC длиннее маршрута ABE. Возможны и другие меры. Например, дуги графа могут быть размечены величиной средней задержки для пакетов. В графе с такой разметкой наикратчайший путь - наибыстрейший путь, который не обязательно имеет минимальное число скачков или километров.

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

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

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

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

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

Алгоритмы состояния канала характеризуются следующим:

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

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