Групповое вещание в IP-сетях

 

 

Министерство образования Российской Федерации

 

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ

УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

 

Кафедра теоретических основ радиотехники (ТОР)

 

 

УТВЕРЖДАЮ

Зав. кафедрой (ТОР)

__________Пуговкин  А.В.

"__" ____________2002г.

 

 

Групповое вещание в IP-сетях

Пояснительная записка к дипломной работе

РТФ ДР. 433561.001 ПЗ

 

СОГЛАСОВАНО

 

Консультант по экономической части ассистент ____________ И.А. Глотова  "__"_________2002 г.	Студент гр. 167 ___________Е.А. Белянкин   "__"_________2002 г.
Консультант по вопросам охраны труда начальник ОТ и ТБ ___________Л.И. Кодолова "__"________2002 г.	Руководитель дипломной работы генеральный директор ООО ГПС «Версия» ____________К.И. Борисов. "__"________2002 г.

 

 

 

2002

 

Реферат

Дипломная работа — 122 страницы, рисунков — 13, таблиц — 11, чертежей — 0,  демонстрационных плакатов — 4.

Протокол управления группами IGMP, алгоритмы перенаправления данных, Multicast, протоколы групповой маршрутизации, служба QoS, алгоритмы управления очередями, профилирование и формирование трафика, RSVP, ведро токенов, DiffServ, Cisco IP/TV, RealSystem, Windows Media, вещание, маршрутизатор, сеть.

 

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

Результаты работы могут быть применены при  внедрении технологии Multicast в сетях провайдеров интернет, а также в корпоративные сети .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Основной целью группового вещания является создание эффективного механизма передачи данных по схеме "один-ко-многим" и "многие-ко-многим". Традиционные механизмы стека TCP/IP доставки пакетов мало пригодны для поддержки группового вещания. Например, использование уникальных адресов (unicast) приводит к необходимости установления многочисленных двухточечных соединений между отправителем и каждым из получателей. Другим способом передачи данных является широковещательная передача, когда станция направляет пакеты, используя широковещательные адреса (broadcast). Пакеты с такими адресами передаются всем конечным узлам указанной сети независимо от того, нужны ли они каждому из них. Во многих ситуациях такой способ передачи также оказывается неэффективным вследствие своей избыточности, которая ведет к чрезмерному росту трафика, особенно в крупных сетях.

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

Технология группового вещания (IP multicast) впервые была введена в докторской диссертации Стива Диринга (Steve Deering) в 1988 году и впервые протестирована в широком масштабе во время "аудиокаста" в 1992 году на собрании IETF в Сан-Диего. Концепция, предложенная Дирингом, описывает, каким образом конечные системы посылают и принимают групповые пакеты. Эта концепция включает как необходимые, так и некоторые косвенные требования.

Источник может посылать пакеты UDP/IP в любое время без необходимости регистрировать или планировать передачи. Так как это пакеты UDP, то в данном случае реализуется сервис "с максимальными усилиями".

■ Открытые группы. Отправители знают только групповой адрес. Они не должны знать членов группы и им не обязательно быть членами той группы, которой они посылают данные. Группа может иметь любое число источников данных и быть образована узлами, принадлежащими к разным IP-сетям и подсетям.

■  Динамические группы. Узлы могут присоединяться или покидать группы без необходимости регистрации, синхронизации или переговоров с каким-либо централизованным элементом группового управления.

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

На основе описанной концепции для стека TCP/IP был разработан ряд протоколов, с помощью которых можно с различной степенью эффективности организовать групповое вещание. Эти протоколы делятся на две категории. В первую входит один протокол — протокол IGMP (Internet Group Management Protocol), с помощью которого маршрутизатор узнает о принадлежности хостов в непосредственно подключенных к нему подсетях к той или иной группе. Протокол IGMP работает в тесном взаимодействии с протоколами второй категории — протоколами групповой маршрутизации. Протоколы групповой маршрутизации опираются на разные подходы, но все они в конечном итоге сводятся к построению графа, связывающего все хосты в определенной группе, причем между двумя хостами существует только один путь. Такой граф называют покрывающим деревом (Spanning Tree). Протоколы групповой маршрутизации осуществляют постоянный мониторинг покрывающего дерева и время от времени отсекают те его ветви, которые из-за изменения состояния сети уже не ведут к членам той или иной группы.

Ниже приведены наиболее распространенные протоколы групповой маршрутизации:

• Distance Vector Multicast Routing Protocol (DVMRP);
• Multicast Open Shortest Path First (MOSPF);
• Protocol Independent Multicast (PIM).

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Групповая адресация в IP.

 

2. Компоненты групповой адресации.

 

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

Групповая адресация на базе IP - это не автономное приложением. Она применяется на той же самой рабочей станции, которая служит нам сегодня для доступа к приложениям, использующим протокол IP и/или Internet. Групповая адресация мирно сосуществует с  IP-приложениями.

Групповая IP-адресация обычно не функционирует в одиночку; существуют другие протоколы, которые работают вместе с ней для реализации передачи VVD (голос, видео, данные) поверх протокола IP. Примеры таких протоколов: протоколы реального времени (RTP) и управления в реальном времени (RТСР), потоков данных реального времени (RTSP) и резервирования ресурсов (RSVP). То же самое можно сказать и об IP. В сети, использующей TCP/IP, существует множество компонентов, и IP - просто один из них. Он обеспечивает доставку датаграмм. Групповая IP-адресация - это также один из многих компонентов.

 

3. Формат адреса.

 

Технология IP-Multicast использует адреса с 224.0.0.0 до 239.0.0.0. Этот диапазон адресов относится к классу D. Класс D – это специальные адреса, известные как адреса групповой рассылки. Адреса такого типа присваиваются группе сетевых станций и не предназначены для использования в качестве индивидуальных. Они применяются для рассылки датаграмм группам, но не всем узлам сети. У групповой рассылки есть множество применений, включая использование при адресации сообщений, обновляющих маршрутную информацию, а также доставку данных, видео и звука поверх протокола IP. Использование группового адреса - это более эффективный способ широковещательной рассылки, нежели использование широковещательного адреса. В этом случае не происходит прерывания работы программного обеспечения по прибытии каждого широковещательного пакета. Групповая рассылка отличается от широковещательной. При последней каждая станция, которая получает пакет, автоматически передает его программному обеспечению верхнего уровня независимо от адреса. Станция, получившая широковещательный пакет, должна обработать его.

При использовании группового адреса каждая отдельная IP-станция должна решить, принять ли ей данные от конкретного IP-адреса групповой рассылки перед тем, как прервать работу программного обеспечения транспортного уровня. В каждой сетевой карте (NIC) зарегистрирован адрес групповой рассылки уровня MAC. Он является обычным персональным адресом. Таким образом, сетевой адаптер может отбрасывать пакет, не прерывая работы программного обеспечения верхнего уровня. Сетевая карта уже запрограммирована на прием широковещательного пакета. Это пакет с адресом FF-FF-FF-FF-FF-FF.

Существует RFC 1700, в котором полностью описывается отображение адресов класса D на МАС-адреса, а также указываются присвоенные групповые адреса и зарегистрированные групповые адреса.

 Базовый адрес, 224.0.0.0, зарезервирован  и не может быть присвоен  никакой группе, кроме того, зарезервирован диапазон 224.0.0.1 – 224.0.0.255 для протоколов маршрутизации, определения топологии и управления. Ни  одному маршрутизатору, получившему датаграмму с адресом из этого диапазона, не позволено перенаправлять ее. Он должен либо принять ее, либо отбросить.

224.0.0.0      -      базовый адрес   [RFC1112]

224.0.0.1      -      все системы данной подсети   [RFC1112]

224.0.0.2      -      все маршрутизаторы данной подсети

224.0.0.3      -      не присвоен

224.0.0.4      -      DVMRP  (маршрутизаторы)   [RFC1075]

224.0.0.5      -      OSPFIGP (все маршрутизаторы OSPFIGP)   [RFC1583]

224.0.0.6      -      OSPFIGP (ответственные маршрутизаторы OSPFIGP)

224.0.0.7      -      ST-маршрутизаторы   [RFC1190]

224.0.0.8      -      ST-узлы   [RFC1190]

224.0.0.9      -      маршрутизаторы RIP2   [RFC1723]

224.0.0.10    -      маршрутизаторы IGMP  [Cisco]

224.0.0.11    -      мобильные агенты

224.0.0.12    -      сервер DHCP/служба ретрансляции   [RFC1884]

224.0.0.13 - 224.0.0.255 не присвоены

Остальные адреса динамически используются приложениями

 

4. Отображение группового IP-адреса на Ethernet, или МАС-адрес IEEE 802.X

 

Для сетевых карт не имеет значения адресация третьего уровня. Они получают и передают данные посредством протокола MAC (управления доступом к среде) или аппаратных адресов. Тем не менее сетевая карта играет важную роль в приеме групповых пакетов. В любом случае требуется МАС-адрес, соответствующий групповому, но использование одного адреса для всех групповых пакетов неэффективно. Нужно иметь в виду, что вплоть до 32 различных адресуемых IP-групп могут быть приведены к одному и тому же МАС-адресу. Пять старших бит IP-адреса игнорируются. На самом деле это выглядит как 9 бит, но первые четыре бита адреса класса D всегда равны 1110 (что составляет 224 в десятичной системе, начальное значение адресов класса D). Так как рассматриваются первые 9 бит, то в действительности игнорируются только следующие 5.

При использовании группового IP-адреса в сети Ethernet, или IEEE 802, его 23 младших бита размещаются в 23 младших битах группового сетевого адреса протоколов Ethernet, или IEEE 802. IANA выделила зарезервированный блок адресов уровня доступа к среде. Таким образом, групповой МАС-адрес всегда начинается с 01-00-5Е-00-00-00 и заканчивается 01-00-5Е-7F-FF-FF (шестнадцатеричное значение).

Отобразим IP-адрес 224.0.1.88  на МАС-адрес, преобразованный в шестнадцатеричную форму (см. рис.1). Во-первых, IP-адрес должен быть преобразован в шестнадцатеричную форму. Адрес 224 - это Е0 в шестнадцатеричной системе 0 - 00, 1 - 01, а 88 - 58. Однако используются только младшие 23 бита. Таким образом, IP-адрес 224.0.1.88 преобразуется в МАС-адрес 01-00-5Е-00-01-58.

 

                                       Не исполь-

                                        зуется                           23 бита    

                                      1110 0000 0000 0000 0000 0001 0101 1000  

  0000 0001 0000 0000 0101 1110 0xxx xxxx xxxx xxxx xxxx xxxx

       бит группового                      0 = групповая

         адреса Ethernet                    рассылка Internet

 

0000 0001 0000 0000 0101 1110 0000 0000 0000 0001 0101 1000

т.о. IP-адрес, преобразованный в формат МАС-адреса: 01-00-5Е-00-01-58

 

Рисунок 1.

 

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

■  JoinLocalGroup (отображенный групповой адрес) - подключиться к локальной группе; позволяет канальному уровню принимать групповые пакеты для определенной группы узлов;

■ LeaveLocalGroup (отображенный групповой адрес) - выйти из состава локальной группы; позволяет канальному уровню прекратить прием групповых пакетов от определенной группы узлов.

Преобразованный групповой адрес - это МАС-адрес, который получается из группового адреса группы узлов.

2. Протокол группового управления IGMP.

 

2.1. Общие сведения.

 

Чтобы заставить работать групповую адресацию, требуется несколько протоколов. Не имеет значения, какой протокол типа «маршрутизатор-маршрутизатор» функционирует, один протокол используется вместе со всеми ними: протокол управления группами Internet (IGMP). Для поддержки IGMP узел должен при инициализации присоединиться к группе «все узлы» (адрес 224.0.0.1) на каждом сетевом интерфейсе и оставаться членом группы, пока узел активен. Таким образом, существует, по крайней мере, один групповой адрес, членом группы которого должен быть любой групповой узел.

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

Чтобы интерфейс смог принять групповую датаграмму, его надо предварительно настроить на прием и обработку групповых датаграмм. Так как IGMP не работает с транспортным уровнем, таким как TCP или UDP, значение поля IP протокола задается равным 2 (в соответствии с зарезервированным IANA значением в RFC 1700) для идентификации процесса (IGMP), прибегающего к услугам IP. Таким образом, перед приемом любых групповых пакетов, программному обеспечению верхнего уровня следует удостовериться, что интерфейсы IP- и МАС-уровней настроены на прием групповых датаграмм. Узел может быть членом не только одной группы; более того, не существует верхнего предела для количества групп (за исключением верхнего предела группового IP-адреса). Сетевые карты обладают весьма ограниченными возможностями по приему групповых пакетов. Другими словами, устанавливая версию IP для групповых взаимодействий, пользователь должен также быть в состоянии настроить сетевую карту на прием групповых пакетов. Каждая группа узлов будет иметь уникальный групповой адрес, и следовательно, он также будет отображен на групповой МАС-адрес. Не исключено, что сетевая карта сумеет поддерживать лишь ограниченное количество групповых адресов. В этом случае необходимо посоветоваться с производителем.

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

 

2. Заголовок IGMP.

 

Как  и любая другая часть уровня IP, протокол IGMP использует для передачи данных дейтаграммы протокола IP (рис. 2.1.). Сообщения протокола IGMP обозначаются в поле идентификатора протокола дейтаграммы IP значением 2.

                                            Дейтаграмма IP

Заголовок IP

Сообщение IGMP

                                    20 байт                                        8 байт

 

Рисунок 2.1.

 

Маршрутизатор, использующий протокол IGMP, посылает запросы в свои подсети, и узлы, которые принадлежат группе, обозначенной в запросе, отвечают на него. Формат заголовков IGMP для версий 1 и 2 показан на рисунке 2.2. Поле типа (Туре) может содержать одно из следующих значений:

11h- запрос о членстве;

16h - отчет о членстве версии 2;

17h - выход из состава группы;

12h - отчет о членстве версии 1.

IGMP версии 2 имеет отличный от первой версии заголовок. Поля типа и версии (Version) в заголовке версии 1 совмещены в одном поле, называемом полем типа. Чтобы групповому маршрутизатору было легче выявить различие между двумя версиями, для версии 2 было создано новое поле типа - отчетное сообщение о членстве (Membership Report Message). Маршрутизаторы

 

           0               3         7                              15                                             31

Версия	Тип	Не используется	Контрольная сумма
Групповой адрес

                Версия 1

 

             0                          7                              15                                             31

Тип	Максимальное время ожидания	Контрольная сумма
Групповой адрес

                Версия 2

Рисунок 2.2.

 

IGMP версий 1 и 2 могут сосуществовать. Маршрутизатор с установленным на нем протоколом IGMP версии 2 должен быть способен функционировать, как маршрутизатор с IGMP версии 1. Для обеспечения этого поле максимального времени ожидания ответа (Max Response Time) задается равным 0 во всех запросах (оно отображается на неиспользуемое в версии 1 поле).

Пакет запроса о членстве может быть двух типов: общий запрос (General Query), служащий для нахождения членов любой группы в подключенной сети, и запрос конкретной группы (Group Specific Query) с помощью которого определяются члены конкретной группы.

Разницу между ними можно установить по групповому адресу в заголовке IGMP. В случае общего запроса в поле группового адреса (Group Address) будут одни нули, а в точном запросе присутствует данный групповой адрес. Оба сообщения отсылаются с помощью адреса 224.0.0.1 в IP-заголовке и отображаются на МАС-адрес 01-00-5Е-00-00-01 (используя метод преобразования, описанный ранее).

Сообщение о выходе из состава группы (LeaveGroup) является нововведением в IGMP версии 2. Оно позволяет маршрутизатору мгновенно выяснить, остались ли еще члены в группе его интерфейса, получившего сообщение LeaveGroup.

 

3. Функции маршрутизации в IGMP.

 

Групповые маршрутизаторы с помощью IGMP определяют, члены каких групп подключены к каждому из интерфейсов маршрутизатора. Эта информация, в свою очередь, служит при построении деревьев групповой адресации в процессе перенаправления групповых данных. Для информации о членстве в каждой группе имеется таймер. Маршрутизатор, на котором работает IGMP, тоже является членом любой непустой группы узлов на одном или нескольких своих интерфейсах. Групповой маршрутизатор постоянно следит за информацией о членстве для всех своих интерфейсов, а не за отдельными узлами, принадлежащими к этим группам. На самом деле следить за узлами нет необходимости. Все просто: если хотя бы один узел интерфейса маршрутизатора желает присоединиться к группе, маршрутизатор должен направлять групповые датаграммы в этот интерфейс. Неважно, сколько узлов находится на интерфейсе - 100 или 1; маршрутизатор также должен быть членом данной группы и направлять групповые датаграммы в тот же интерфейс. Групповой маршрутизатор будет узнавать, остались ли члены группы в интерфейсе, посылая туда пакет запроса.

В IGMP версии 2 маршрутизатор исполняет одну из следующих двух ролей: запрашивающего (querier) или пассивного объекта (nonquerier). Все групповые маршрутизаторы при инициализации принимают на себя функции запрашивающего маршрутизатора. Так как групповые маршрутизаторы периодически отсылают запрос на определение узлов в группах, новый маршрутизатор, в конце концов, получит запрос о том, предоставляет ли какой-либо еще маршрутизатор эту функцию. Если маршрутизатор получает еще одно сообщение запроса от другого маршрутизатора, который имеет меньший IP-адрес, то новый маршрутизатор начинает выступать в роли пассивного объекта. Если же у нового маршрутизатора будет меньший IP-адрес, то он примет на себя обязанности запрашивающего маршрутизатора, а другой маршрутизатор станет пассивным объектом.

При получении запроса узел установит таймеры задержек для каждой группы, к которой он принадлежит (задается значение из интервала между нулем и значением, указанным в поле максимального времени ожидания ответа принятого запроса).

На узле, имеющем более одного интерфейса, каждый интерфейс поддерживает свой собственный таймер. По истечении времени узел отвечает отчетом о членстве (Membership Report) версии 2. Поле TTL в заголовке IP будет содержать 1. Это гарантирует, что пакет не окажется перенаправлен за пределы локальной сети, в которую он передается. Узел, получивший отчет от другого узла той же группы, остановит свой таймер и не отошлет отчет. Это позволяет сохранить пропускную способность и время обработки и избежать дублирования отчетов в сети. Все осуществляется при помощи групповой адресации. 224.0.0.2 - групповой адрес всех маршрутизаторов, а 224.0.0.1 - групповой адрес всех узлов.

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

 

 

4. Присоединение узла к группе

 

Когда узел присоединяется к адресуемой группе, он немедленно передает два или три раза отчет о членстве версии 2 (т.к. IGMP не использует ICMP или TCP). Так происходит в случае, если данный узел является первым членом группы, и этот процесс повторяется при потере или повреждении первого отчета.

Покидая группу (IGMPv2), узел передает сообщение о выходе из группы (LeaveGroup). Будет ли узел в состоянии определить, является ли он последним членом группы, - вопрос памяти и вычислительных ресурсов на стороне разработчика. Если узел способен сделать это, он передаст сообщение о выходе из группы, если нет - то либо отошлет такое сообщение, либо нет. Групповой маршрутизатор в любом случае выяснит, существуют ли узлы в группе, при помощи сообщения запроса. Получив данное сообщение, групповой маршрутизатор отошлет точный запрос покидаемой группе. Если ответ не придет, маршрутизатор будет считать, что в группе не осталось членов, и не станет направлять для нее никаких групповых датаграмм через этот интерфейс.

В основном, протокол IGMPv2 содержит возможность сохранения пропускной способности канала и предоставляет узлу выбор - принимать или не принимать поток данных от отдельных источников (IP-адресов) адресуемой группы, а также позволяет указать, от каких источников узел не желает принимать информацию. В любой группе может быть множество источников, В IGMP версий 1 и 2 узел обязан принимать всю информацию группы, членом которой он является, независимо от того, какой источник передает ее. Кроме того, расширены возможности сообщения о выходе из группы, так что узел в состоянии указать, от каких источников он больше не будет принимать информацию. Групповой маршрутизатор получит сообщение и, возможно, прекратит отправку информации в эту группу от данного источника.

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

 

 

 

3. Маршрутизация Multicast.

Одним из необходимых требований для передачи трафика Multicast через маршрутизируемые сети является наличие маршрутного протокола Multicast. В настоящее время известны 3 таких протокола – DVMRP, MOSPF и PIM. Назначение каждого из них заключается в нахождении внутри сети маршрута для следования группового трафика и обеспечение доставки этого трафика каждому заинтересованному участнику сети. Но перед тем как перейти к рассмотрению этих протоколов, ознакомимся с алгоритмами которые ими используются.

 

2. Алгоритмы перенаправления данных.

 

Фактически существует три алгоритма перенаправления данных, которые могут быть применены при групповой IP-адресации:

• лавинообразная рассылка (Flooding);
• остовое дерево (Spanning Tree):
• простое остовое дерево (Simple Spanning Tree);
• широковещательная рассылка по обратному пути (Reverse Path Broadcasting пути);
• групповая рассылка по обратному пути (Reverse Path Multicasting), получила наиболее широкое распространение;
• центрированное дерево (Core-Based Tree, сокращенно СВТ) - при использовании в разреженных средах (не обладающих плотной популяцией узлов) СВТ представляет собой разновидность алгоритма связующего дерева, но достаточно сильно отличается от него, чтобы попасть в отдельную категорию.

Цель всех алгоритмов - построить дерево групповой адресации для перенаправления групповых датаграмм. Некоторые алгоритмы (СВТ и иногда PIM-SM) создают только одно дерево, которое совместно используют все члены группы, даже если это дерево не предоставляет самого эффективного маршрута (кратчайшего пути) между всеми членами группы. Другие алгоритмы формируют деревья кратчайших путей, что делает возможным применение кратчайшего пути для всех членов группы (DVMRP, OSPF). Эти деревья строятся динамически, когда от источника приходит первая групповая датаграмма (за исключением MOSPF).

Групповые датаграммы не обязательно следуют по пути индивидуально адресуемой датаграммы. Формируемое дерево групповой адресации - это динамическое логическое дерево, которое маршрутизатор создает для направления датаграммы ее адресатам.

 

1. Лавинообразная рассылка

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