Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 115
Текст из файла (страница 115)
Для использования этого метода маршрутизаторам не нужна никакая дополнительная информация о связующих деревьях. Не требуются и дополнительные расходы на список получателей или бит-карту в каждом распространяемом пакете, как в случае многоадресной рассылки. Также не требуется никакого специального механизма для прекращения процесса, как, например, в методе заливки (либо счетчик транзитных участков в каждом пакете и априорные сведения о диаметре сети, либо список уже встречавшихся пакетов от каждого источника).
Многоадресная рассылка В некоторых приложениях сильно разделенные процессы работают совместными группами. Например, в виде группы процессов может быть реализована распределенная база данных. Часто одному процессу бывает необходимо послать сообщение всем остальным членам группы. Если группа невелика, то можно просто послать каждому члену группы отдельное сообщение. Если же группа достаточно большая, такая стратегия окажется весьма дорогостоящей. Иногда может быть использовано широковещание, но применять его для информирования 1000 машин в сети, состоящей из миллиона узлов, неэффективно, поскольку большинство получателей будут не заинтересованы в данном сообщении (или, что еще хуже, явно заинтересованы, но было бы крайне желательно от них эту информацию скрыть).
Таким образом, требуется способ рассылки сообщений строго определенным группам, довольно большим по численности, но небольшим по сравнению со всей сетью. Передача сообщения членам такой группы называется многоадресной рассьшкой, а алгоритм маршрутизации этой операции — многоадресной маршрутизацией.
В этом разделе будет описан один из способов реализации многоадресной маршрутизации. Дополнительные сведения см. в (СЬи и др., 2000; Созга и др., 2001; Казега и др., 2000; (т4айгийа апд Саге(а-1лпа-Асеуез, 2001; Х)таня апт) Куп, 2001). длго итмм ма ш изации 429 Многоадресной рассылке требуется управление группами, то есть способ соз. дания и удаления групп, присоедннепия процесса к группе и ухода процесса из группы. Реализация данных задач, однако, не интересует алгоритм маршрутизации, Зато он заинтересован в том, чтобы процесс информировал свой хост о присоединении к какой-нибудь группе. Вюкно, чтобы маршрутизаторы знали, какой хост к какой группе принадлежит.
Для етого либо хост должен сообщать своим маршрутизаторам об изменении в составе групп, либо маршрутизаторы должны сами периодически опрашивать свои хосты, В любом случае маршрутизаторы узнают, какие из их хостов к каким группам принадлежат. Маршрутизаторы сообщают об атом своим соседям, и таким образом зта информация распространяется по всей подсети. Для многоадресной рассылки кюкдый маршрутизатор рассчитывает связующее дерево, покрывающее все остальные маршрутизаторы подсети, Например, на рис. 5,15, а мы видим подсеть с двумя группами, 1 и 2. Как показано на рисунке, маршрутизаторы соединены с хостами, принадлежащими к одной или обеим груп» пам. Связующее дерево для самого левого маршрутизатора показано на рис.
5.15, 6, 1 в г рнс. в.1в. подсеть (е); связующее дерево для самого левого маршрутизатора (б); многоадресное дерево для группы 1 (в); многоадресное дерево для группы 2 (г) Когда процесс посылает группе многоадресный пакет, первый маршрутизатор изучает свое связующее дерево и отсекает у него линии, ие ведуитие к хостам, являющимся членами группы. В нашем примере иа рис.
5.15, в изображено усеченное связующее дерево для группы 1. Аналогично, на рис. 5.15, г показано усеченное связующее дерево лля группы 2. Многоадресные пакеты рассылаются только вдоль соответствующего их группе усеченного связующего дерева. 430 Глава Б. Сетевой уровень Существует несколько способов усечения связующего дерева Простейший способ может применяться при использовании маршрутизации с учетом состояния линий, когда каждому маршрутизатору известна полная топология подсети, в том числе и состав групп. При этом из связующего дерева могут быть удалены маршрутизаторы, не принадлежащие к данной группе, начиная с конца каждого пути вплоть до корня дерева.
При маршрутизации по векторам расстояний может быть применена другая стратегия усечения дерева. Для многоадресной рассылки здесь применяется алгоритм продвижения по встречному пути. Когда многоадресное сообщение получает маршрутизатор, у которого нет хостов, входящих в группу, и линий связи с другими маршрутизаторами, он может ответить сообщением РВОвс (отсечь), информируя отправителя, что сообщения для данной группы ему больше посылать не нужно.
Такой же ответ может дать маршрутизатор, у которого нет хостов, входящих в группу, если он получил многоадресное сообщение по всем своим линиям. В результате подсеть постепенно рекурсивно усекается. Недостаток данного алгоритма заключается в его плохой применимости к большим сетям. Предположим, что в сети есть я групп, каждая из которых в среднем состоит из и членов. Для каждой группы должно храниться и усеченных входных деревьев, то есть тп деревьев для всей сети, При большом количестве групп для хранения всех деревьев потребуется много памяти. Альтернативный метод использует деревья с основанием в сердцевине (ВаПагб!е и др., 1993).
В этом методе для каждой группы рассчитывается единое связующее дерево с корнем (ядром) около середины группы. Хост посылает многоадресное сообщение ядру группы, откуда оно уже рассылается по всему связующему дереву группы. Хотя это дерево не является оптимальным для всех источников, единое дерево для группы снижает затраты на хранение информации о нем в т раз. Алгоритмы маршрутизации для мобильных хостов Сегодня миллионы людей обладают переносными компьютерами, и большинство из них желает читать свою электронную почту и получать доступ к нормальным файловым системам, находясь при этом в любой точке земного шара. Мобильные хосты привносят новое усложнение в и без того непростое дело выбора маршрутов в различных вычислительных сетях — чтобы направить пакет к мобильному хосту, его нужно сначала найти. Вопрос включения мобильных хостов в сети появился не так давно, но в данном разделе мы рассмотрим некоторые проблемы и приведем их возможные решения.
Молель мира, обычно используемая разработчиками сетей, показана на рис. 5,16 Здесь мы видим глобальную сеть, состоящую из маршрутизаторов и хостов. С глобальной сетью соединены локальные и региональные сети и беспроводные соты, которые рассматривались в главе 2. Хосты, которые никогда не перемещаются, называются стационарными. Они соединены с сетью медными поводами или оптическими кабелями.
Мы же будем различать две другие категории хостов. Мигрируюшие хосты являются, в основном, стационарными пользователями, но время от времени перемещаются с од- 432 Глава б, Сетевой овень 2, Мобильный хост регистрируется в данной области, сообщая внешнему агенту свой домашний адрес, текущий адрес уровня передачи данных, а тавке информацию, подтверждающую его подлипкость.
3. Внешний агент связывается с внутренним агентом мобильного пользователя и сообщает ему: «Один из ваших хостов находится в нашей областям Это сообщение содержит адрес сети внешнего агента, а также информацию, подтверждающую подлипкость мобильного хоста. Это позволяет убедить вкутрениего агента в том, что мобильный хост действительно находится здесь, 4.
Впутренкий агент проверяет переданный ему идентификатор безопасности мобильного хоста, содержащий времеккой штамп, доказывающий, что иден. тификатор был создан буквально несколько секунд назад, Если проверка подлинности хоста проходит успешно, внутренний агент разрешает внешнему агенту продолжать связь. 5, Получив подтверждение от внутреннего агента, внешний агент заносит сведения о мобильном хосте в свою таблицу и сообшает ему, что он зарегистрирован. В идеальном случае, покидая область, пользователь также должен сообщить об этом внешнему агенту, однако на практике многие пользователи, закончив свои дела, просто выключают свои компьютеры.
Когда пакет посылается мобильному пользователю, он направляется в его домашнюю локальную сеть на домашний адрес пользователя На рис, 5.17 это действие показано как этап 1. Здесь отправитель из северо-западного города Сиэтла хочет отправить пакет хосту, который обычно находится по другую сторону США в Нью-Йорке. Пакеты, посланные в домашнюю локальную сеть мобильного хоста (Нью-Йорк), перехватываются внутренним агентом, который узнает новое (временное) расположение мобильной станции (например, Лос-Анджелес) и адрес внешнего агента локальной сети, в которой она в данный момент находится. Затем внутренний агент выполняет дза действия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
