Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 117
Текст из файла (страница 117)
Этот счастливый мнг запечатлен на рнс. 5.18, х Обратите внимание: несмотря на то, что мы показали распростране- Алгоритмы маршрутизации 437 иие широковещательного пакета в виде трех стадий, иа самом деле рассылка этого пакета разными узлами никак ие координируется. В ответ па пришедший запрос узел 1 генерирует пакет наличия маршрута ЕООТЕ кЕРЕТ, показанный иа рис. 5.20. Поля Адрес отправителя, Адрес получателя и Счетчик переходов копируются из РООТЕ РЕООЕ5Т, а Порядковый номер получателя берется из собственного счетчика, хранящегося в памяти. Поле Счетчик переходов устанавливается в О.
Поле Время существования используется для управлеиия реализуемостью маршрута. Даипый пакет распространяется методом одно- адресной передачи иа тот узел, с которого пришел запрос маршрута. В данном случае ои уходит иа узел С. Затем, в соответствии с устаиовлеииым обратным путем, оп попадет иа 1) и наконец иа А. При проходе каждого узла Счетчик переходов иикремеитируется, так что узел-отправитель может увидеть, насколько далеко от него находится узел-получатель (1).
Адрес Ащтес Порядковый Счетчик Время отправителя получателя номер получателя переходов существования рис, В.20. Формат пакета йООТЕ ИЕРку Каждый узел, через который проходит пакет иа обратном пути (к А), проверяет его. При выполнении хотя бы одного из трех условий на его основе строится запись в локальной таблице маршрутов о пути к 1. Вот эти условия: 1. Не известен ни один маршрут к 1. 2. Последовательный номер для 1 в пакете РООТЕ РЕРЕТ больше, чем значение в таблице маршрутизации. 3. Последовательиые номера равны, но новый путь короче. Таким образом, все узлы, стоящие на обратном пути к А, совершенно бесплатно получают ииформаци1о о маршруте к узлу 1. Это как бы побочный продукт построения маршрута для А. Узлы, получившие исходный пакет запроса маршрута, ио ис стоящие иа обратном пути (узлы В, С, Е, Г и Н в данном примере) удаляют запись в таблице обратных маршрутов, когда ассоциированный с ией таймер достигает тайм-аута.
В больших сетях алгоритмом генерируется много широковещательных пакетов даже для адресатов, расположенных довольно близко друг к другу. Число этих пакетов может быть уменьшено следующим образом. Время жизни 1р-пакета устанавливается отправителем в значение, соответствующее ожидаемому диаметру сети, и декремеитируется при каждой пересылке. Когда его значение стаиовится равным О, пакет отвергается, а не распространяется дальше. При этом процесс поиска пути немного изменяется. Для обнаружения адресата отправитель рассылает пакет запроса маршрута с Временем жизни, равным 1. Если в течение разумного времени ответ ие приходит, посылается еще один запрос с Временем вкизни, равным 2, и т.
д. Таким образом, поиск, начавшийся в какой-то локальной области, все больше расширяет свой охват. 438 Глава 5. Сетевой уровень Обслуживание маршрута Поскольку узлы могут перемещаться и выключаться, топология сети может изменяться совершенно спонтанно.
Например, если на рис. 5.18 узел б выключится, А не поймет, что путь к 1 (АРИ) больше не может быть реализован. Алгоритму нужно как-то с этим бороться. Периодически все узлы рассылают сообщение приветствия Не(го. Ожидается, что все узлы, будучи истинными джентльменами, ответят на него. Если ответ не приходит, значит, сосед вышел из зоны действия и больше не связан с данным узлом. Аналогичным образом, если он пытается послать пакет соседу, который не отвечает, он узнает, что связь с ним недоступна. Эта информация используется для удаления нерабочих путей.
Для каждого из возможных адресатов каждый узел Аг хранит историю о том, какие соседи снабжали узел пакетами для данных адресатов в течение последних ЬТ секунд. Такие соседи называются активными соседями узла М для данного адресата. Узел Аг осуществляет сбор подобных сведений с помощью таблицы маршрутизации, которая, как известно, в качестве индекса использует адрес назначения. В втой таблице указан тот узел, на который нужно переслать пакет, чтобы он мог дойти до адресата. Кроме того, в ней имеются сведения об оставшемся числе переходов, последнем порядковом номере получателя, а также об активных соседях данного адресата.
Вид возможной таблицы маршрутизации для узла Р при топологии, рассматриваемой в нашем примере, показан на рис. 5.21, а. Следующий переход Активные Прочие Адресат Р поля асстояние Рис. 6.21. Таблица маршрутизации узла Р перед выходом из сети узла 6 (ай граф-схема сети после выхода из нее О (б) Когда какой-либо из соседей узла Аг становится недоступным, проверяется его таблица маршрутизации — ведь теперь нужно понять, к каким адресатам лежал путь через ушедший узел. Всем оставшимся активным соседям сообщается, что такие пути больше нельзя использовать и их следует удалить из таблиц маршрутизации.
Активные соседи передают эти новости своим активным соседям, и так далее, пока все пути, зависевшие от ушедшею узла, не будут удалены из всех таблиц. Алгоритмы маршрутизации 439 Рассмотрим наш предыдущий пример, предположив, что С внезапно выключился. Образовавшаяся в результате этого события топология показана на рис. 5.21, б. Когда .0 обнаруживает, что С ушел из сети, он просматривает свою таблицу маршрутизации и видит, что С стоял на пути к Е, С и Е Обьединением активных соседей для данных адресатов является множество (А, В). Другими словами, А и В содержат записи о маршрутах, проходящих через С, поэтому их нужно проинформировать о том, что эти маршруты больше нс работают.
а сообщает им об этом, посылая специальные пакеты, заставляющие их обновить свои таблицы соответствующим образом. Сам узел а удаляет записи для адресатов Е, С и 1 из таблицы маршрутизации. Из приведенного описания это, может быть, и не очевидно, но основная разница между АО)УН и алгоритмом Беллмана — Форда состоит в том, что узлы не занимаются периодической широковещательной рассылкой пакетов, содержащих полные таблицы маршрутизации.
Благодаря этому более эффективно используется полоса пропускания и увеличивается время работы элементов питания. АООН, впрочем, может также заниматься широковещательной и групповой маршрутизацией. Детали см. в (Регй(пз апд Коуег, 2001). Маршрутизация в специализированных сетях — чрезвычайно популярная сегодня область исследований. Вопросам, связанным с ней, посвящено большое количество материалов. Например, (СЬеп и др., 2002; Нц апб ЯоЬпзоп, 2001; Ы и др., 2001; Ка)ц апд Саго(а-) цпа-Асечез, 2001; КашапагЬап апб Кег)1, 2002; Коуег апд ТоЬ, 1999; Яройп апг( Сагс1а-1цпа-Асечез, 2001; Тзепя и др., 2001; ЕадеЬ и др., 2002).
Поиск узла в равноранговых сетях Относительно новым явлением являются равноранговые сети, в которых большое количество пользователей, имеющих обычно постоянное кабельное соединение с Интернетом, работает с разделяемыми ресурсами. Первым широко известным применением равноранговых сетей стало создание нелегальной системы Ыарзгег, 50 миллионов пользователей которой обменивались звукозаписями без разрешения обладателей авторских прав. Это продолжалось до тех пор, пока сеть Ыарзгег после бурной полемики не была закрыта решением суда. Тем не менее, уравноранговых сетей есть множество интересных и в то же время легальных применений. С ней связаны некоторые проблемы, сходные с проблемой маршрутизации, хотя и не такие же, как мы только что изучили, Сейчас мы их вкратце рассмотрим. Что делает равноранговые системы интересными, так зто их полная распределенность. Все узлы симметричны, никакого единого управления или иерархии не существует.
В типичной разноранговой сети пользователи обладают какой-то информацией, могущей представлять интерес для других. Это может быть бес"латное программное обеспечение, музыка (являющаяся всеоб|цим достоянием), фотографии и т. д. Если пользователей много, они друг о друге ничего не знают и. возможно, никогда не узнают. Но совершенно непонятно, как искать что-то нужное в такой сети! Одним из решений является создание централизованной базы данных, но это может быть неосуществимо при некоторых условиях (напри- 440 Глава 5.
Сетевой уровень мер, в сети нет добровольцев, желающих содержать и обслуживать такую базу), То есть проблема сводится к тому, что пользователю нужен какой-то метод поиска узла, на котором хранится интересующая его информация, в условиях отсутствия централизованной базы данных и даже централизованного индекса, Предположим, что каждый пользователь владеет одной или более единицей информации, такой как песни, программы, фотографии, файлы и тому подобное — все то, чем другие пользователи, возможно, заинтересуются.
У каждого такого объекта имеется строка А5СП, именующая его. Потенциальный пользователь знает только эту строку и стремится найти одного или нескольких пользователей, у которых есть данный объект, и узнать его (их) 1Р-адрес. В качестве примера рассмотрим распределенную генеалогическую базу данных. У каждого генеалога есть онлайновый набор записей о его предках и родственниках, возможно, с фотографиями, аудиозаписями или даже видеозаписями, Понятно, что общий прадедушка был у многих, поэтому запись о нем будет иметься на нескольких узлах сети. Запись идентифицируется по имени человека, записанном в какой-нибудь канонической форме. И тут генеалог обнаруживает в архиве завещание прадедушки, в соответствии с которым золотые карманные часы он передает своему племяннику.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
