Остовые деревья (Spanning Trees)
В системе сетей выбирается корневой маршрутизатор, после этого из графа системы выделяется подграф-дерево, соединяющий корневой маршрутизатор со всеми остальными маршрутизаторами системы ("остовое дерево", рис. 8.3.1). Эта процедура производится на этапе инициализации системы – в процессе работы дерево не изменяется.
После построения остового дерева каждый маршрутизатор должен хранить для каждого из своих интерфейсов только флаг "этот интерфейс принадлежит/не принадлежит дереву". Групповая дейтаграмма от любого узла распространяется следующим образом: полученная маршрутизатором дейтаграмма ретранслируется через все интерфейсы, принадлежащие остовому дереву, кроме того интерфейса, с которого она была получена.
Рис. 8.3.1. Рассылка групповой дейтаграммы по остовому дереву
S – источник, A-F – маршрутизаторы;
ветви дерева обозначены сплошными линиями; метрики всех сетей, кроме явно указанных, равны 1
Метод остовых деревьев несколько лучше веерной рассылки – в том смысле, что теперь дейтаграммы распространяются по строго определенным маршрутам и в каждую сеть попадает только один экземпляр дейтаграммы. Также существенно уменьшена нагрузка на маршрутизаторы, которым больше не требуется хранить "исторические" таблицы дейтаграмм.
Однако групповые дейтаграммы по-прежнему рассылаются во все сети независимо от наличия в них получателей, кроме того:
