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

Дерево доставки — это структурированный древообразный набор некоторого количества путей, предназначенных для доставки информации и выбираемых таким образом, чтобы пакеты с групповыми адресами доставлялись только тем устройствам, которые хотят их получать. Дерево доставки отличается от дерева кратчайших путей тем, что оно не всегда определяет кратчайший путь достав­ки — определяются возможность и маршрут доставки. В дерево кратчайших путей включаются только кратчайшие пути, а все остальные — не рассмат­риваются. Алгоритмов формирования деревьев доставки существует достаточно много. Среди них можно отметить алгоритмы Flooding, Spanning Tree, Reverse Path Broadcasting, Truncated Reverse Path Broadcasting, Reverse Path Multi­casting, 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 Re­verse 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. Он более эффективно использует ресурсы маршрутизаторов, так как им теперь требуется хранить информацию только для каждой группы в распределенной сети, а не для каждой пары (отправитель, группа-получатель). Кроме того, алгоритм СВТ рациональнее использует пропускную способность сети, поскольку не требует периодической передачи дейтаграмм с групповыми адресами на все маршрути­заторы в распределенной сети.

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

Дата добавления: 2015-07-13