<<
>>

Многоадресная рассылка

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

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

В этом разделе будет описан один из способов реализации многоадресной маршрутизации. Дополнительные сведения см. в (Chu и др., 2000; Costa и др., 2001; Kasera и др., 2000; Madruga and Garcia-Luna-Aceves, 2001; Zhang and Ryu, 2001).

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

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

Для многоадресной рассылки каждый маршрутизатор рассчитывает связующее дерево, покрывающее все остальные маршрутизаторы подсети. Например, на рис. 5.15, а мы видим подсеть с двумя группами, 1 и 2. Как показано на рисунке, маршрутизаторы соединены с хостами, принадлежащими к одной или обеим группам. Связующее дерево для самого левого маршрутизатора показано на рис. 5.15, б.

Рис. 5.15. Подсеть (а); связующее дерево для самого левого маршрутизатора (б); многоадресное дерево для группы 1 (в); многоадресное дерево для группы 2 (г)

Когда процесс посылает группе многоадресный пакет, первый маршрутизатор изучает свое связующее дерево и отсекает у него линии, не ведущие к хостам, являющимся членами группы. В нашем примере на рис. 5.15, в изображено усеченное связующее дерево для группы 1. Аналогично, на рис. 5.15, г показано усеченное связующее дерево для группы 2. Многоадресные пакеты рассылаются только вдоль соответствующего их группе усеченного связующего дерева.

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

При маршрутизации по векторам расстояний может быть применена другая стратегия усечения дерева. Для многоадресной рассылки здесь применяется алгоритм продвижения по встречному пути. Когда многоадресное сообщение получает маршрутизатор, у которого нет хостов, входящих в группу, и линий связи с другими маршрутизаторами, он может ответить сообщением PRUNE (отсечь), информируя отправителя, что сообщения для данной группы ему больше посылать не нужно.

Такой же ответ может дать маршрутизатор, у которого нет хостов, входящих в группу, если он получил многоадресное сообщение по всем своим линиям. В результате подсеть постепенно рекурсивно усекается.

Недостаток данного алгоритма заключается в его плохой применимости к большим сетям. Предположим, что в сети есть п групп, каждая из которых в среднем состоит из т членов. Для каждой группы должно храниться т усеченных входных деревьев, то есть тп деревьев для всей сети. При большом количестве групп для хранения всех деревьев потребуется много памяти.

Альтернативный метод использует деревья с основанием в сердцевине (Ballardie и др., 1993). В этом методе для каждой группы рассчитывается единое связующее дерево с корнем (ядром) около середины группы. Хост посылает многоадресное сообщение ядру группы, откуда оно уже рассылается по всему связующему дереву группы. Хотя это дерево не является оптимальным для всех источников, единое дерево для группы снижает затраты на хранение информации о нем в т раз.

<< | >>
Источник: Э. ТАНЕНБАУМ. КОМПЬЮТЕРНЫЕ СЕТИ 4-Е ИЗДАНИЕ. 2003

Еще по теме Многоадресная рассылка:

  1. 3. Новости по почте. Электронной
  2. Новость или репортаж
  3. Как осуществить это на практике?
  4. Мониторинг и новостные поводы
  5. Об авторе
  6. Вариант 1.
  7. 2. Информационные агентства
  8. Как работает притяжение
  9. Передача энергии через печатные материалы
  10. Похвалы
  11. Создайте убежище
  12. Пиарщикам
  13. Отпустить.
  14. ТРИ ВЕЛИЧАЙШИЕ КНИГИ О ПРОЦВЕТАНИИ ВСЕХ ВРЕМЕН
  15. 4. Правовые и этические нормы работы с источниками.
  16. § 4. Постановление кассационной инстанции
  17. 13.2.4. Отношения средств массовой информации с гражданами и организациями
  18. 1. Особенности расчетных обязательств с использованием банковских карт
  19. Теперь я шаг за шагом опишу вам метод ММ.
  20. Таблоиды.