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