Широковещательная маршрутизация

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

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

2. Еще одним очевидным кандидатом является метод заливки. Но при заливке генерируется очень много пакетов и отнимается весьма существенная часть пропускной способности.

3. Третий алгоритм называется многоадресной маршрутизацией. См. далее: Многоадресная рассылка

4. Еще один, четвертый алгоритм широковещательной маршрутизации в явном виде использует корневое дерево или любое другое связующее дерево. Связующее дерево представляет собой подмножество подсети, включающее в себя все маршрутизаторы, но не содержащее замкнутых путей. Если каждый маршрутизатор знает, какие из его линий принадлежат связующему дереву, он может отправить приходящий пакет по всем линиям связующего дерева, кроме той, по которой пакет прибыл. Такой метод оптимальным образом использует пропускную способность сети, порождая минимальное количество пакетов, требующихся для выполнения работы. Проблема: каждому маршрутизатору необходимо обладать информацией о связующем дереве. Иногда такая информация доступна (например, в случае маршрутизации с учетом состояния линий), но иногда — нет (при маршрутизации по векторам расстояний).

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

Пример работы алгоритма продвижения по встречному пути показан на рис. 5.14. Слева изображена подсеть, посередине —входное дерево для маршрутизатора I этой подсети. На первом транзитном участке маршрутизатор I посылает пакеты маршрутизаторам F, H, J и N, являющимся вторым ярусом дерева. Все эти пакеты прибывают к I по предпочитаемым линиям (по пути, совпадающему с входным деревом), что обозначается кружками вокруг символов на рис. 5.14, в. На втором этапе пересылки формируются восемь пакетов — по два каждым маршрутизатором, получившим пакет после первой пересылки. Все восемь пакетов попадают к маршрутизаторам, не получавшим ранее пакетов, а пять из них приходят по предпочитаемым линиям. Из шести пакетов, формируемых на третьем транзитном участке, только три прибывают по предпочитаемым линиям (на маршрутизаторы С, E и К). Остальные оказываются дубликатами. После пяти транзитных участков широковещание заканчивается с общим количеством переданных пакетов, равным 23, тогда как при использовании входного дерева потребовалось бы 4 транзитных участка и 14 пакетов.

Рис, 5.14. Продвижение по встречному пути: подсеть (а); связующее дерево (б); дерево, построенное методом продвижения по встречному пути (в)

---

Дата добавления: 2015-08-09