Телекоммуникационные технологии.Сети TCP-IP

       

Остовые деревья (Spanning Trees)


В системе сетей выбирается корневой маршрутизатор, после этого из графа системы выделяется подграф-дерево, соединяющий корневой маршрутизатор со всеми остальными маршрутизаторами системы ("остовое дерево", рис. 8.3.1). Эта процедура производится на этапе инициализации системы – в процессе работы дерево не изменяется.

После построения остового дерева каждый маршрутизатор должен хранить для каждого из своих интерфейсов только флаг "этот интерфейс принадлежит/не принадлежит дереву". Групповая дейтаграмма от любого узла распространяется следующим образом: полученная маршрутизатором дейтаграмма ретранслируется через все интерфейсы, принадлежащие остовому дереву, кроме того интерфейса, с которого она была получена.


Рис. 8.3.1. Рассылка групповой дейтаграммы по остовому дереву
S – источник, A-F – маршрутизаторы;
ветви дерева обозначены сплошными линиями; метрики всех сетей, кроме явно указанных, равны 1

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

Однако групповые дейтаграммы по-прежнему рассылаются во все сети независимо от наличия в них получателей, кроме того:

  • требуется реализация механизма (протокола) выбора корневого узла и построения дерева;
  • весь групповой трафик ложится на одни и те же связи (сети), составляющие, возможно, небольшое подмножество всей системы сетей;
  • для некоторых пар отправитель-получатель путь по установленному дереву будет неоптимальным (например для источника S и получателей, подсоединенных к маршрутизатору Е на рис. 8.3.1).


  • Содержание раздела