Алгоритмы построения дерева доставки
Дерево доставки — это структурированный древообразный набор некоторого количества путей, предназначенных для доставки информации и выбираемых таким образом, чтобы пакеты с групповыми адресами доставлялись только тем устройствам, которые хотят их получать. Дерево доставки отличается от дерева кратчайших путей тем, что оно не всегда определяет кратчайший путь доставки — определяются возможность и маршрут доставки. В дерево кратчайших путей включаются только кратчайшие пути, а все остальные — не рассматриваются. Алгоритмов формирования деревьев доставки существует достаточно много. Среди них можно отметить алгоритмы Flooding, Spanning Tree, Reverse Path Broadcasting, Truncated Reverse Path Broadcasting, Reverse Path Multicasting, Core-Based Tree. Некоторые из них реализованы в наиболее распространенных протоколах групповой маршрутизации, таких как DVMRP, MOSPF, PIM.
Протокол IGMP отвечает за заключительную фазу доставки дейтаграмм с групповым адресом от маршрутизатора всем членам группы в подключенной к нему подсети. Однако этот протокол не обеспечивает доставку таких дейтаграмм между соседними маршрутизаторами или через распределенную сеть. Реализовать этот механизм позволяют протоколы групповой маршрутизации, отвечающие за построение деревьев доставки и маршрутизацию дейтаграмм.
Метод доставки группового трафика, заложенный в алгоритме лавинной маршрутизации (Flooding), является самым простым. Он задействуется в тот момент, когда маршрутизатор получает дейтаграмму, адресованную одной из групп. Маршрутизатор определяет, получал ли он эту дейтаграмму ранее. Если нет, она передается на все его порты (отсюда название — лавинная маршрутизация), за исключением принявшего дейтаграмму, — это гарантирует, что дейтаграмма пройдет через все маршрутизаторы в распределенной сети. Если маршрутизатор уже обрабатывал дейтаграмму, он удаляет ее.
Данный алгоритм очень прост в реализации и не требует построения таблиц маршрутизации. Однако лавинная маршрутизация непригодна в больших распределенных сетях и Internet, так как она порождает большой избыточный трафик и приходится изыскивать механизмы ограничения этого трафика.
Более эффективным решением служит алгоритм остового дерева (Spanning Tree). Результатом работы этого алгоритма является древообразная структура, в которой между двумя любыми маршрутизаторами в распределенной сети есть только один активный путь. После построения такой структуры маршрутизатор будет передавать групповой трафик только на те порты, которые являются ее частью, исключая порт, принявший дейтаграмму. Такой подход гарантирует, что групповой трафик не будет зацикливаться и в конечном счете дойдет до всех маршрутизаторов в распределенной сети. Алгоритм прост в реализации и обладает высокой эффективностью, но при его использовании не исключена вероятность выбора не самого быстрого и надежного пути между отправителем и группой получателей в распределенной сети.
Еще более действенным решением, чем формирование одного остового дерева для всей распределенной сети, является создание остового дерева для каждого отправителя в группе, то есть формирование деревьев доставки от источника (Source-Rooted Trees, SRT). Корень такого дерева находится в локальной сети, где располагается отправитель дейтаграмм с групповыми адресами. Эти деревья создаются для каждой активной пары (отправитель, группа-получатель).
Основным алгоритмом для построения дерева доставки от источника является алгоритм вещания по обратному пути Reverse Path Broadcasting (RPB). Маршрутизатор получает дейтаграмму с групповым адресом. По ней он определяет пару (отправитель, группа-получатель). Маршрутизатор вычисляет самый короткий путь назад к отправителю. Если дейтаграмма пришла к нему по этому пути (через соответствующий порт, который называется родительским), он пересылает ее на все свои порты (они называются порожденными), за исключением принявшего (рис. 9.6). Дейтаграммы, поступившие на порожденные порты, удаляются.
Базовый алгоритм RPB может быть расширен для устранения дублирования дейтаграмм. Суть идеи сводится к тому, что маршрутизатор перед отправкой дейтаграммы соседнему маршрутизатору пытается вычислить, что тот сделает с этой дейтаграммой. Если маршрутизатор решает, что его сосед удалит дейтаграмму (это произойдет, если он примет дейтаграмму на порожденный порт), то маршрутизатору нет смысла ее посылать.
Информация, необходимая для принятия такого решения, может быть получена через протокол маршрутизации, основанный на алгоритме состояния канала. Действительно, каждый маршрутизатор управляет топологической базой данных о всем домене маршрутизации. При использовании протокола маршрутизации, работающего на основе алгоритма вектора расстояния, маршрутизатор может сообщить о том, какой маршрутизатор лежит на пути между ним и отправителем (для данной пары), через свои служебные сообщения.
Работа алгоритма RPB иллюстрируется на рис. 9.7. Маршрутизатор А получает групповую дейтаграмму и передает ее в каналы связи 1 и 2 через свои порожденные порты. Маршрутизатор Б получает эту дейтаграмму из канала 1 на свой порт, который является родительским для анализируемой пары (отправитель, группа-получатель), и передает его дальше через каналы 4 и 5. В случае передачи дейтаграммы через канал связи 3, она будет удалена маршрутизатором В, так как порт канала 3 не будет родительским.
Основным достоинством алгоритма является его эффективность и простота реализации. Он не требует, чтобы маршрутизаторы владели информацией о всем остовом дереве, и не подразумевает специальных механизмов остановки процесса передачи, которые требуются в алгоритме Flooding. Одно из главных ограничений алгоритма RPB — в том, что он не учитывает членство в группах для пары. В результате дейтаграммы с групповыми адресами порождают ненужный трафик в сетях, в которых нет членов этой группы.
Для разрешения данной проблемы был разработан алгоритм Truncated Reverse Path Broadcasting (TRPB). Алгоритм использует информацию, собранную с помощью протокола IGMP. При этом маршрутизаторы определяют наличие членов группы в каждой подключенной локальной сети и не передают дейтаграммы в те сети, в которых членов группы нет. Таким образом ненужные ветви дерева доставки как бы обрезаются.
Работа алгоритма TRPB показана на рис. 9.8. Маршрутизатор получает дейтаграммы, адресованные группе Г1, на свой родительский порт. Маршрутизатор передает дейтаграммы на порожденный порт 1, так как в подключенной к нему локальной сети есть члены данной группы, а на порожденный порт 3 дейтаграммы передаваться не будут ввиду отсутствия там членов данной группы. На порожденный порт 2 дейтаграммы будут передаваться только в том случае, если они поступят на родительский порт следующего маршрутизатора.
Этот алгоритм устраняет не все недостатки алгоритма RPB. В частности, он по-прежнему не принимает во внимание членство в группах при формировании дерева доставки.
Этот общий недостаток алгоритмов RPB и TRPB устраняет алгоритм Reverse Path Multicasting (RPM). Он создает дерево доставки, охватывающее только те части распределенной сети, в которые входят члены группы-получателя.
Если маршрутизатор получает дейтаграммы с групповыми адресами для пары (отправитель, группа-получатель), то первая дейтаграмма передается в соответствии с алгоритмом TRPB. Этим гарантируется, что все маршрутизаторы в распределенной сети ее получат. Если члены группы-получателя присутствуют в подключенных к маршрутизаторам подсетях, то дейтаграмма будет доставлена на основании информации, полученной от протокола IGMP. Если же в подсетях нет членов группы-получателя, то маршрутизаторы передают специальные усекающие (prune) сообщения на свои родительские порты вышестоящим маршрутизаторам. Когда те получат эти сообщения, они перестанут посылать групповой трафик для данной пары на свои порожденные порты, принявшие сообщения (рис. 9.9).
Так как членство в группах и сетевая топология могут меняться динамически, то в определенные интервалы времени необходимо проверять правомерность усечения дерева доставки. Для этого информация о том, какие ветви дерева нужно усекать, регулярно удаляется из памяти всех маршрутизаторов. Тогда следующая дейтаграмма передается всем маршрутизаторам в распределенной сети по алгоритму TRPB и усечение дерева доставки проводится заново.
Алгоритм RPM тоже не свободен от недостатков, особенно в большой распределенной сети. В частности, дейтаграммы должны периодически передаваться всем маршрутизаторам в сети. Кроме того, каждому маршрутизатору требуется хранить информацию обо всех группах и каждом отправителе. В больших сетях это достаточно проблематично.
Кроме перечисленных алгоритмов, формирующих деревья доставки для каждой пары (отправитель, группа-получатель), существует алгоритм Core-Based Trees (CBT), который создает одно дерево доставки, используемое для всех членов той или иной группы. То есть групповой трафик посылается и принимается через одно и то же дерево доставки, независимо от отправителя. Дерево доставки, сформированное с помощью алгоритма CBT, может включать в себя один или несколько маршрутизаторов, которые являются узлами дерева. На рис. 9.10 показаны сформированное алгоритмом СВТ дерево доставки и схема передачи через него группового трафика.
Каждое устройство, которому необходимо получать трафик, адресованный группе, должно послать сообщение о своем намерении присоединиться к СВТ-дереву данной группы. Предполагаемому члену группы необходимо знать адрес хотя бы одного работающего маршрутизатора СВТ-дерева. Сообщение о присоединении посылается с использованием обычной адресации. По пути следования данное сообщение обрабатывается всеми промежуточными маршрутизаторами, которые при этом помечают свои порты, получившие сообщение как принадлежащие к дереву доставки данной группы. Эти маршрутизаторы продолжают передачу сообщения до тех пор, пока присоединяющее сообщение не достигнет включенного в дерево маршрутизатора.
Как и другие алгоритмы, СВТ не требует, чтобы отправитель группового трафика был членом группы-получателя. В этом случае дейтаграмма просто передается с помощью единичной адресации до тех пор, пока она не достигнет маршрутизатора, который входит в дерево доставки адресованной группы. После этого дейтаграмма маршрутизируется групповым образом на все порты, за исключением принявшего. Такая схема гарантирует, что данная дейтаграмма достигнет всех маршрутизаторов в дереве доставки.
Алгоритм СВТ имеет ряд преимуществ перед алгоритмом RPM. Он более эффективно использует ресурсы маршрутизаторов, так как им теперь требуется хранить информацию только для каждой группы в распределенной сети, а не для каждой пары (отправитель, группа-получатель). Кроме того, алгоритм СВТ рациональнее использует пропускную способность сети, поскольку не требует периодической передачи дейтаграмм с групповыми адресами на все маршрутизаторы в распределенной сети.
Однако алгоритм СВТ может привести к тому, что трафик сосредоточится около включенных в дерево маршрутизаторов, тем самым вызвав их перегрузку. Кроме того, так как все члены группы имеют одно и то же дерево СВТ, это вызывает увеличение задержки при передаче дейтаграмм, что критично для некоторых мультимедийных приложений.
- Максим Кульгин Технологии корпоративных сетей. Энциклопедия
- Часть I основы корпоративных сетей.
- 1. Базовые сетевые технологии
- Соединения и каналы
- Технологии b-isdn и atm
- Технология Frame Relay
- Технология isdn
- Плезиохронная и синхронная цифровые иерархии
- Технология sonet
- Технология smds
- Технология Ethernet
- Дальнейшее развитие технологии Ethernet
- Технология 100vg-AnyLan
- 2. Методология построения корпоративной сети
- Сравнение современных технологий передачи данных
- Требования к сети
- Архитектура сети
- Магистраль на базе коммутации ячеек
- Маршрутизация
- Коммутация
- Выделение маршрутов
- Сетевые шаблоны
- Сетевой шаблон глобальной сети
- Сетевой шаблон городской сети
- Шаблон городской сети с технологией sonet/sdh
- Шаблон городской сети с передачей atm поверх sonet/sdh
- Шаблон городской сети, как расширенной локальной сети
- Сетевой шаблон центрального офиса
- Реализация доступа и магистрали
- Критерии выбора технологии
- 3. Качество обслуживания в современных сетях
- Характеристики трафика
- Трафик разных приложений
- Качество обслуживания «на самоокупаемости»
- Обзор технологий качества обслуживания
- Обеспечение перекрывающей пропускной способности
- Приоритетные очереди в маршрутизаторах
- Протокол резервирования ресурсов
- Установление приоритетов в виртуальных сетях
- Качество обслуживания в сетях Frame Relay
- Качество обслуживания в сетях atm
- Рекомендации
- 4. Модель и уровни osi
- Эталонная модель osi
- Протоколы и интерфейсы
- Уровни модели osi Физический уровень
- Канальный уровень
- Сетевой уровень
- Транспортный уровень
- Сеансовый уровень
- Уровень представления
- Прикладной уровень
- Назначение уровней модели osi
- 5. Основные типы сетевых устройств
- Витая пара
- Коаксиальный кабель
- Оптоволоконный кабель
- Сетевые адаптеры
- Концентраторы
- Коммутаторы
- Коммутация «на лету»
- Коммутация с буферизацией
- Бесфрагментная коммутация
- Дополнительные функции коммутаторов
- Протокол stp
- Протокол stp и виртуальные сети
- Протокол stp: заключение
- Маршрутизаторы
- Брандмауэры
- Часть II стек протоколов тср/ip
- 6. Ip и другие протоколы нижнего уровня
- Протокол ip
- Протокол arp
- Протокол 1смр
- Протокол udp
- Протокол rtp
- Адресная схема протокола ip
- 7. Протокол tcp
- Формат заголовка
- Состояние системы
- Блок управления передачей
- Установление и закрытие соединений
- Плавающее окно
- Пропускная способность
- Контроль за перегрузками
- Управление потоком данных
- Политики отправки и приема сегментов
- Таймер повторной передачи
- Адаптивный таймер повторной передачи
- Узкие места в сети
- Протокол tcp в сетях atm
- 8. Маршрутицазия протокола ip
- Автономные системы
- Подсети
- Маска подсети
- Протокол rip
- Маска подсети переменной длины
- 9. Протоколы маршрутизации Протокол ospf
- Протоколы igrp и eigrp
- Протоколы политики маршрутизации egp и bgp
- Протокол igmp
- Алгоритмы построения дерева доставки
- Магистраль mbone
- Протоколы групповой маршрутизации Протокол dvmrp
- Протокол mospf
- Протокол рiм
- Бесклассовая междоменная маршрутизация
- Часть III Технология atm
- 10. Введение в технологию атм
- Появление atm
- Форум atm
- Основные компоненты atm
- Уровни atm
- Уровень адаптации atm
- Уровень atm
- Физический уровень
- Прямая передача ячеек
- Использование транспортных кадров
- Использование plcp
- Интерфейсы atm
- Мультиплексирование в сетях atm
- Инверсное мультиплексирование
- Безопасность в сетях atm
- Сигнализация atm
- 11. Основы технологии атм Соединения atm
- Сети без установления соединения
- Сети с установлением соединения
- Виртуальные соединения в сетях atm
- Типы виртуальных соединений
- Виртуальные пути и виртуальные каналы
- Установление соединений atm
- Ячейки atm
- Сети с передачей ячеек
- Формат ячеек atm
- Ячейки формата uni
- Ячейки формата nn1
- Подготовка ячеек к передаче
- Уровень адаптации aal1
- Уровень адаптации aal3/4
- Уровень адаптации aal5
- Адресация atm
- Адрес dcc aesa
- Адреса icd и е.164 aesa
- Управление адресами
- 12. Коммутация и маршрутизация в атм Коммутаторы atm
- Архитектура коммутаторов atm
- Интеграционные функции коммутаторов
- Управляемость
- Маршрутизация в atm
- Протокол маршрутизации запросов pnni
- Протокол сигнализации pnni
- Качество обслуживания
- Протокол tcp
- Протокол udp
- Резервирование ресурсов и протоколы управления потоком данных
- Организация очередей в маршрутизаторе
- Метод явного контроля скорости
- 14. Интегрированные и дифференцированные услуги Качество обслуживания
- Интегрированные услуги
- Сервисные уровни обслуживания
- Сервисное управление нагрузкой
- Гарантируемое обслуживание
- Протокол резервирования ресурсов rsvp
- Стили резервирования
- Развитие сетей с is
- Дифференцированные услуги
- Архитектура системы с предоставлением ds
- Граничные устройства домена ds
- Внутренние устройства домена ds
- Выходные домены
- Использование протокола rsvp в сетях с ds
- 15. Управление трафиком в атм
- Трафик-контракт
- Параметры трафика
- Категории сервиса
- Связь механизмов управления трафиком
- Контроль за установлением соединения
- Контроль за использованием полосы пропускания
- Формирование трафика
- Контроль потока abr
- Контроль приоритетов
- Организация очередей в коммутаторах
- Реализация очередей для службы ubr
- Реализация очередей для службы abr
- Методы отбрасывания пакетов
- Адаптивное управление буферами в коммутаторах
- 16. Интеграция с атм
- Протокол ip поверх atm
- Передача ip-Дейтаграмм по сети atm
- Взаимодействие устройств в одной логической подсети
- Групповая доставка информации в сети atm
- Взаимодействие устройств в разных логических подсетях
- Протокол nhrp
- Оценка потерь при работе протокола ip поверх atm
- Передача ip-дейтаграмм в кадрах sonet
- Технология эмуляции локальной сети — lane
- Концепция lane
- Технология мроа
- Клиент мроа
- Сервер мроа
- Взаимодействие технологий мроа и nhrp
- Масштабируемость в глобальных сетях
- Технология Tag Switching фирмы Cisco
- Технология aris фирмы ibm
- Технология mpls комитета ietf
- Перспективные разработки. Рекомендации
- Взаимодействие технологий atm и Frame Relay
- 17. Интеграция маршрутизации и коммуникации
- Общие вопросы выбора технологий
- Коммутирующие маршрутизаторы
- Коммутация третьего уровня в atm
- Технологии фирм Ipsilon и Toshiba
- Технология FastIp фирмы 3Com
- Технология NetFlow фирмы Cisco
- Технология SecureFast фирмы Cabletron
- Технология Multiprotocol Switched Services фирмы ibm
- 18. Мультимедиа в сети
- Передача видеоинформации
- Технические требования к передаче видеоинформации в сетях atm
- Некоторые рекомендации по созданию сетей atm с видео
- Передача голоса
- Часть V Приложения
- 1. Стандарты стека протоколов tcp/ip
- 2. Порты протоколов tcp и udp
- 3. Выделение ip - подсетей
- 4. Теория очередей и расчет параметров сети
- 5. Организации по стандартизации
- 6 Список фирм - членов Форума атм
- 7. Спецификации Форума атм
- 8. Список терминов
- 9. Список литературы Основная литература
- Дополнительная литература Технология atm и протокол ip поверх atm
- Технология качества обслуживания
- Система ip-адресаиии
- Некоторые ресурсы Internet
- Алфавитный указатель
- Оглавление
- Часть I 3
- Часть II 109
- Часть III Технология atm 207
- Часть IV 269
- Часть V Приложения 402