Групповая маршрутизация с общим деревом

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

Обратите внимание, что в это дерево входят маршрутизаторы, присоединенные хосты которых являются членами данной группы рассылки (то есть маршрутизаторы А, В, Е и F), а также маршрутизаторы, у которых нет хостов, принадлежащих к данной группе рассылки. В идеальном случае можно также задаться дополнительной целью минимизации стоимости дерева. Если каждой линии сети назначена определенная стоимость, как это делалось в случае одноадресной маршрутизации (см. раздел «Основы маршрутизации»), тогда оптимальным деревом для групповой маршрутизации будет дерево с минимальной суммой стоимостей входящих в него линий. На рис. 4.49 оптимальное дерево групповой рассылки (с суммарной стоимостью линий, равной 7) изображено жирными линиями.

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

Несмотря на то что для решения задачи Штайнера существуют хорошие эвристические приближенные методы, интересно отметить, что ни один из применяемых в Интернете алгоритмов групповой маршрутизации не основан на данных методах. Почему? Одна из причин заключается в том, что для нахождения дерева наименьшей стоимости при каждом изменении стоимости линии алгоритм необходимо запускать заново. Кроме того, важную роль в принятии решения о пригодности алгоритма групповой маршрутизации играют другие соображения, такие как возможность использования информации о маршрутах и таблиц продвижения данных, уже рассчитанных для одноадресной маршрутизации. В конце концов, производительность (и оптимальность) — это не все, что нужно учитывать.
Альтернативный подход определения общего многоадресного дерева, используемый в Интернете в нескольких алгоритмах групповой маршрутизации, основан на определении центрального узла (также называемого точкой встречи, или ядром) общего дерева групповой маршрутизации. Сначала для группы рассылки определяется центральный узел. Затем маршрутизаторы, хосты которых принадлежат к группе рассылки, посылают (путем обычной выборочной рассылки) центральному узлу сообщения с запросом о намерении присоединиться к дереву. Эти сообщения принимаются либо центральным узлом дерева, либо маршрутизатором, уже принадлежащим дереву. В любом случае путь, который прошло данное сообщение, определяет ветвь дерева маршрутизации между оконечным маршрутизатором, пославшим сообщение, и центральным узлом. Этот путь можно рассматривать как новую ветвь дерева.

Создание дерева групповой маршрутизации с центральным узлом иллюстрирует рис. 4.50. Пусть маршрутизатор Е выбран в качестве центрального узла дерева.

Сначала к группе рассылки присоединяется узел F, посылая маршрутизатору Е соответствующее сообщение. Линия EF становится начальным деревом группы. Затем к дереву присоединяется узел В, посылая соответствующее сообщение маршрутизатору Е. Предположим, групповой маршрут от маршрутизатора В до маршрутизатора Е проходит через узел D. В этом случае сообщение маршрутизатора В проходит по маршруту BDE, в результате этот маршрут добавляется к дереву. Наконец, к группе рассылки присоединяется узел А, посылая сообщение с запросом об этом маршрутизатору Е. Предположим, что одноадресный маршрут от маршрутизатора А до маршрутизатора Е проходит через узел В. Поскольку узел В уже присоединился к дереву групповой рассылки, сразу по прибытии сообщения от узла А на узел В линия АВ добавляется к дереву.

Ключевым вопросом групповой маршрутизации с центральным узлом является выбор центрального узла.