маршрутизаторов. Протоколы бесклассовой маршрутизации используют механизм наибольшего соответствия при выборе маршрута. Поэтому если маршрутизатор R1 будет знать маршруты на 172.16.6.0/24, 172.16.9.0/24 и суммарный маршрут на 172.16.0.0/16, он сможет правильно маршрутизировать трафик к маршрутизаторам R2 и R3. Трафик до R3 будет использовать маршруты до подсетей 172.16.6.0/24 и 172.16.9.0/24, а трафик до маршрутизатора R2 будет отправляться по суммарному маршруту 172.16.0.0/16.
3.5 Категории алгоритмов маршрутизации
Большинство алгоритмов маршрутизации может быть отнесено к одной из трех категории:
–дистанционно-векторные протоколы;
–протоколы с учетом состояния канала;
–сбалансированные гибридные протоколы.
Дистанционно-векторный протокол (distance vector routing protocol) определяет направление, или вектор, и расстояние до нужного узла объединенной сети.
Протокол с учетом состояния канала (link-state routing protocol), также называется алгоритмом выбора кратчайшего пути (shortest path first – SPF), воссоздает топологию сети на каждом маршрутизаторе.
Сбалансированный гибридный протокол (balanced hybrid routing protocol) соединяет в себе определенные черты обоих предыдущих типов алгоритмов.
3.5.1 Особенности дистанционно-векторных протоколов
При использовании дистанционно-векторных алгоритмов между маршрутизаторами происходит периодическая пересылка копий таблиц маршрутизации друг друга. В таких регулярных обновлениях маршрутизаторы сообщают друг другу об изменениях в топологии сети. Дистанционно-векторные алгоритмы маршрутизации также называются алгоритмами Белламана–Форда (Bellaman–Ford).
На рисунке 3.13 каждый маршрутизатор получает таблицу маршрутизации от соседних маршрутизаторов. В частности маршрутизатор R2 получает информацию от маршрутизатора R1. Маршрутизатор R2 добавляет значение вектора расстояния, количества переходов, что увеличивает результирующий вектор расстояния. После этого маршрутизатор R2 передает свою новую таблицу маршрутизации своему соседу, маршрутизатор R3. Такой пошаговый процесс происходит на всех соседних маршрутизаторах.
56
R2
R3 |
R1 |
R4
R4 |
R3 |
R2 |
R1 |
Рисунок 3.13 – Концепция дистанционно-векторной маршрутизации
В дистанционно-векторном алгоритме накапливаются расстояния в сети, что позволяет поддерживать базу данных, содержащую информацию о топологии сети. Однако дистанционно-векторные алгоритмы не предоставляют маршрутизаторам точную топологию всей сети, поскольку каждому маршрутизатору известны только соседние с ним маршрутизаторы.
Каждый маршрутизатор, использующий дистанционно-векторную маршрутизацию, начинает свою работу с определения соседних маршрутизаторов.
W |
|
X |
|
Y |
Z |
R1 |
|
R2 |
|
R3 |
|
Таблица |
|
Таблица |
|
Таблица |
|
маршрутизации |
|
маршрутизации |
|
маршрутизации |
|
W |
0 |
X |
0 |
Y |
0 |
X |
0 |
Y |
0 |
Z |
0 |
Y |
1 |
Z |
1 |
X |
1 |
Z |
2 |
W |
1 |
W |
2 |
Рисунок 3.14 – Процесс построения структуры сети в дистанционно-векторной маршрутизации
На рисунке 3.14 проиллюстрировано формирование вектора расстояния. Для каждого интерфейса, ведущего к непосредственно подключенной сети, вектор расстояния устанавливается равным нулю. По мере того, как процесс расчета вектора расстояния продолжается маршрутизаторы находят наилучший маршрут к сетям получателям на основе информации, которую они получили от своих соседей.
57
Применение дистанционно-векторной маршрутизации накладывает жесткие ограничения по диаметру сети передачи данных. Такие протоколы маршрутизации не предназначены для функционирования в больших объединенных сетях с множеством каналов связи, где маршрутизаторы соединяют сотни или даже тысячи сетей. Максимальный диаметр сети определяет расстояние, на которое можно передать пакет, после чего пункт назначения считается недостижимым. Это максимальное расстояние измеряется числом пересылок от отправителя к получателю. Правило максимального расстояния гласит: Между двумя нельзя установить соединение, если они находятся на расстоянии более чем X пересылок.
Для протоколов RIP v1 и v2 максимальное число пересылок равно 15. Это означает, что диаметр сети не должен превышать 15 маршрутизаторов.
Еще одним важным понятием в дистанционно-векторных алгоритмах маршрутизации является сходимость сети. Сходимость достигается, когда все маршрутизаторы внутри домена маршрутизации имеют согласованную информацию о доступных маршрутах. Дистанционно-векторные протоколы требуют рассылки маршрутизаторами своей таблицы маршрутизации всем своим соседям. Частотой рассылки управляют таймеры. Когда маршрутизатор получает обновление маршрутной информации, он, прежде чем передавать трафик, должен произвести пересчет всех маршрутов и обновить таблицу маршрутизации.
Дистанционно-векторные протоколы отличаются медленной сходимостью, и поэтому весьма подвержены возникновению петель маршрутизации. Время, которое требуется, для того чтобы все маршрутизаторы обработали обновление маршрутной информации и обновили свои таблицы маршрутизации, называется временем сходимости. Это очень важный параметр сети, поскольку при отказе канала или маршрутизатора данные не передаются в объединенной сети до тех пор, пока все таблицы маршрутизации не будут полностью обновлены.
3.5.2 Маршрутизация по состоянию канала
Вторым базовым алгоритмом маршрутизации является алгоритм выбора маршрута по состоянию канала. Такие алгоритмы известны как алгоритмы Дейкстры (Dijkstra) или как алгоритмы выбора кратчайшего пути (Shortest Path First – SPF). Они поддерживают сложную базу топологии сети. Дистан- ционно-векторные алгоритмы не содержат определенной информации об удаленных сетях и маршрутизаторах, алгоритмы с использованием состояния канала поддерживают полную информацию об удаленных маршрутизаторах и их соединениях друг с другом. Одним из самых широко распространенных протоколов маршрутизации с учетом состояния канала является протокол OSPF. Ключевыми понятиями алгоритмов по состоянию канала являются:
58
–сообщение о состоянии канала (Link-State Advertisement - LSA). Эти объявления представляют собой небольшие пакеты, которые содержат информацию об известных маршрутизатору каналах связи;
–база данных топологии (Topological Database). Эта база данных содержит информацию, полученную в сообщениях LSA;
–алгоритм выбора кратчайшего пути (Shortest Path First – SPF). Алгоритм осуществляет вычисления над базой данных топологии сети, результатом чего является построение связующего дерева протокола SPF.
На рисунке 3.15 проиллюстрированы основные операции алгоритма маршрутизации на основе состояния канала.
|
A |
S |
|
L |
|
L S A
L
S
A
База данных топологии сети
SPF
|
A |
S |
|
L |
|
Дерево SPF
Таблица
маршрутизации
Рисунок 3.15 – Основные действия алгоритма маршрутизации на основе состояния канала
Маршрутизаторы обмениваются сообщениями LSA, начиная с непосредственно подключенных сетей. Каждый маршрутизатор параллельно с остальными создает свою базу данных топологии сети, состоящую из информации, полученной из сообщений LSA.
Алгоритм SPF вычисляет доступность сетей. Маршрутизатор строит логическую топологию в виде дерева, корнем которого является он сам, а ветвями - все возможные маршруты ко всем сетям, входящим в домен маршрутизации. Потом алгоритм SPF удаляет излишние связи в дереве, оставшееся дерево является деревом кротчайших путей ко всем известным сетям домена маршрутизации, в который входит данный маршрутизатор. Полученные маршруты до сетей получателей вносятся в таблицу маршрутизации.
59
Если маршрутизатор узнает об изменении состояния канала, он рассылает эту информацию остальным маршрутизаторам домена маршрутизации с тем, чтобы они смогли отразить ее в своих базах топологии сети. При получении маршрутизатором пакета LSA его база топологии сети обновляется в соответствии с последней полученной информацией. При получении каждого пакета LSA, содержащего изменения состояний каналов, алгоритм SPF заново вычисляет наилучшие маршруты и обновляет таблицу маршрутизации.
Время сходимости протоколов маршрутизации с учетом состояния каналов связи значительно меньше, чем у дистанционно-векторных протоколов маршрутизации. Это связано с тем, что каждый маршрутизатор в домене маршрутизации имеет информацию о реальной топологии сети и может самостоятельно производить пересчет маршрутов к сетям получателям при получении пакетов LSA с изменениями топологии сети. Фактически временем сходимости сети будет время необходимое для расчета нового SPF дерева после получения изменений топологии сети.
При использовании протоколов состояния канала возникают две основные проблемы:
–перегрузка процессора служебной информацией;
–повышение требований к оперативной памяти.
Маршрутизаторы, на которых работают протоколы маршрутизации с учетом состояния канала, требуют большего объема памяти и выполняют больший объем обработки данных, чем при использовании дистанционновекторных протоколов маршрутизации.
Как показано на рисунке 3.16, маршрутизаторы должны иметь достаточно памяти для сохранения большого объема информации в базе топологии сети.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
База данных |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
SPF |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
топологии сети |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
маршрутизации |
||||
Дерево SPF
Рисунок 3.16 – Проблемы протоколов состояния канала
60