tanenbaum_seti_all.pages (525408), страница 117
Текст из файла (страница 117)
Узлы, получившие исходный пакет запроса маршрута, но не стоящие на обратном пути (узлы В, С, Е, г и О в дашюм примере) Удаляют запись в таблице обратных маршрутов, когда ассоциированный с ней таймер достигает тайм-аута. В больших сетях алгоритмом генерируется много широковещательных пакетов даже для адресатов, расположенных довольно близко друг к другу. Число зтих пакетов может быть уменьшено следующим образом. Время жизни 1Р-пакета устанавливается отправителем в значение, соответствующее ожидаемому диаметру сети, и декрементируется при каждой пересылке. Когда его значение становится равным О, пакет отвергается, а не распространяется дальше. При атом процесс поиска пути немного изменяется.
Для обнаружения адресата отправитель рассылает пакет запроса маршрута с Временем жизни, равным 1. Если в течение разумного времени ответ не приходит, посылается еще один запрос с Временем жизни, равным 2, и т. д. Таким образом, поиск, начавшийся в какой-то локальной области, все больше расширяет свой охват. 43а Глава 5. Сетевой уровень Следующий переход Активные Прочие Адресат асстоиние Рис. 5.21. Таблица маршрутизации узла О перед выходом из сети узла 6 (а(; граф-схема сети после выхода из нее 6 (б] Когда какой-либо из соседей узла (т'становится недоступным, проверяется его таблица маршрутизации — ведь теперь нужно понять, к каким адресатам лежал путь через ушедший узел.
Всем оставшимся активным соседям сообщается, что такие пути больше нельзя использовать и их следует удалить из таблиц маршрутизации. Активные соседи передают эти новости своим активным соседям, и так далее, пока все пути, зависевшие от ушедшего узла, не будут удалены иэ всех таблиц. Обслуживание маршрута Поскольку узлы могут перемешаться и выключаться, топология сети может изменяться совершенно спонтанно.
Например, если на рис. 5.18 узел С выключится, у( не поймет, что путь к 1(АРСГ> больше не может быть реализован. Алгоритму нужно как-то с этим бороться. Периодически все узлы рассылают сообщение приветствия Не!!о. Ожидается, что все узлы, будучи истинными джентльменами, ответят на него. Если ответ не приходит, значит, сосед вышел нз зоны действия и больше не связан с данным узлом.
Аналогичным образом, если он пытается послать пакет соседу, который не отвечает, он узнает, что связь с ним недоступна. Эта информация используется для удаления нерабочих путей. Для каждого из возможных адресатов каждый узел Аг хранит историю о том, какие соседи снабжали узел пакетами для данных адресатов в течение последних АТ секунд. Такие соседи называются активными соседями узла Ат для данного адресата. Узел Аг осуществляет сбор подобных сведений с помощью таблицы маршрутизации, которая, как известно, в качестве индекса использует адрес назначения.
В этой таблице указан тот узел, на который нужно переслать пакет, чтобы он мог дойти до адресата. Кроме того, в ней имеются сведения об оставшемся числе переходов, последнем порядковом номере получателя, а также об активных соседях данного адресата. Вид возможной таблицы маршрутизации для узла Р при топологии, рассматриваемой в нашем примере, показан на рис. 5.21, а. Алгоритмы маршрутизации 439 Рассмотрим наш предыдущий пример, предположив, что С внезапно выключился. Образовавшаяся в результате этого события топология показана на рис, 5.21, б, Когда 0 обнаруживает, что С ушел из сети, он просматривает свою таблицу маршрутизации и видит, что С стоял на пути к Е, С и Е Объединением активных соседей для данных адресатов является множество (А, В).
Другими словами, А и В содержат записи о маршрутах, проходящих через С, поэтому их нужно проинформировать о том, что эти маршруты больше не работают. 1) сообщает им об этом, посылая специальные пакеты, заставляющие их обновить свои таблицы соответствующим образом. Сам узел 0 удаляет записи для адресатов Е, С и! из таблицы маршрутизации. Из приведенного описания это, может быть, и не очевидно, но основная разница между АО1)Ъ' и алгоритмом Беллмана — Форда состоит в том, что узлы не занимаются периодической широковещательной рассылкой пакетов, содержащих полные таблицы маршрутизации. Благодаря этому более эффективно используется полоса пропускания и увеличивается время работы элементов питания. АО1)Ч, впрочем, может также заниматься широковещательной и групповой маршрутизацией.
Детали см. в (Регй(пз апб Коуег, 2001). Маршрутизация в специализированных сетях — чрезвычайно популярная сегодня область исследований, Вопросам, связанным с ней, посвящено большое количество материалов. Например, (СЬеп и др., 2002; Ни апд 3оЬпзоп, 2001; 1.1 и др., 2001; Ка)п апг) багс1а-1ппа-Асеуез, 2001; Кашапагйап апг) Кег(1, 2002; Коуег апб ТоЬ, 1999; БроЬп апб Оагс(а-Ецпа-Асеуез, 2001; Тзепя и др., 2001; 2аг)еЬ и др., 2002). Поиск узла в равноранговых сетях Относительно новым явлением являются разноранговые сети, в которых большое количество пользователей, имеющих обычно постоянное кабельное соединение с Интернетом, работает с разделяемыми ресурсами.
Первым широко известным применением разноранговых сетей стало создание нелегальной системы Харзгег, 50 миллионов пользователей которой обменивались звукозаписями без разрешения обладателей авторских прав. Это продолжалось до тех пор, пока сеть Ыарзсег после бурной полемики не была закрыта решением суда. Тем не менее, у разноранговых сетей есть множество интересных и в то же время легальных применений. С ней связаны некоторые проблемы, сходные с проблемой маршрутизации, хотя и не такие же, как мы только что изучили.
Сейчас мы их вкратце рассмотрим. Что делает равноранговые системы интересными, так это их полная распределенность. Все узлы симметричны, никакого единого управления или иерархии не существует, В типичной разноранговой сети пользователи обладают какой-то информацией, могущей представлять интерес для других. Это может быть бесплатное программное обеспечение, музыка (являющаяся всеобщим достоянием), фотографии и т. д. Если пользователей много, они друг о друге ничего не знают и, возможно, никогда не узнают.
Но совершенно непонятно, как искать что-то нужное в такой сети! Одним из решений является создание централизованной базы данных, но это может быть неосуществимо при некоторых условиях (напри- 440 Глава 6. Сетевой уровень мер, в сети нет добровольцев, желающих содержать и обслуживать такую базу). То есть проблема сводится к тому, что пользователю нужен какой-то метод поиска узла, на котором хранится интересующая его информация, в условиях отсугствия централизованной базы данных и даже централизованного индекса. Предположим, что каждый пользователь владеет одной или более единицей информации, такой как песни, программы, фотографии, файлы и тому подобное — все то, чем другие пользователи, возможно, заинтересуются.
У каждого такого объекта имеется строка АБСП, именующая его. Потенциальный пользователь знает только эту строку и стремится найти одного или нескольких пользователей, у которых есть данный объект, и узнать его (их) 1р-адрес. В качестве примера рассмотрим распределенную генеалогическую базу данных. У каждого генеалога есть онлайновый набор записей о его предках и родственниках, возможно, с фотографиями, аудиозаписями или даже видеозаписями. Понятно, что общий прадедушка был у многих, поэтому запись о нем будет иметься на нескольких узлах сети. Запись идентифицируется по имени человека, записанном в какой-нибудь канонической форме. И тут генеалог обнаруживает в архиве завещание прадедушки, в соответствии с которым золотые карманные часы он передает своему племяннику. Теперь необходимо узнать имя этого племянника и того, у кого могут быть какие-либо сведения о нем.
Как же это сделать, не имея централизованной базы данных? Для решения этой проблемы было предложено несколько различных алгоритмов. Мы рассмотрим метод хорды (!)аЪе!с и др., 2001а; 5го!са и др., 2001). Несколько упрощенное объяснение принципа его работы таково. Пусть система состоит нз л пользователей. У каждого из них есть какие-то записи, и каждый готов хранить биты и части индекса, которые могут быть использованы другими, У каждого узла есть 1Р-адрес, который может быть закодирован т-битным номером с помощью хэш-функции. В методе хорды используется алгоритм 5НА-1 для вычисления значения хэш-функции.
БНА-1 применяется в криптографии, и мы рассмотрим его в главе 8. А сейчас нам просто надо знать, что это некоторая функция с аргументом в виде строки переменной длины и значением — 160-битным числом высокой степени случайности. Таким образом, любой 1Р-адрес можно закодировать 160-битным числом, называемым идентификатором узла. Концепция состоит в том, что вообще все 2"" идентификаторов располагаются в возрастающем порядке, образуя большой круг чисел. Некоторые из идентификаторов соответствуют реально существующим узлам, но зто лишь малая часть из ннх. На рис.
5.22 показан круг идентификаторов для и = 5 (на дуги внутри круга пока внимания не обращайте). В этом примере реальным узлам соответствуют идентификаторы 1, 4, 7, 12, 15, 20 и 27. На рисунке кружочки с этими номеРами закрашены. Всем остальным идентификаторам нельзя поставить в соответствие какие-либо узлы. Определим функцию определения последователя зиссеззог(я) как идентификатор первого реального узла, следующего после 1 в описанном нами круге (по часовой стрелке). Например, зиссеззог(6) = 7, зиссеззог(8) = 12, зиссезгог(22) = 27. Названия записей (например, названия песен, имена предков и т.
и.) также обрабатываются хэш-функцией Ьпзл (с помощью алгоритма БНА-1) и превраща- Алгоритмы маршрутизации 441 ются в 160-битные числа, называемые ключами. Таким образом, чтобы получить ключ (Ьеу) из названия записи (ватле), необходимо вычислить Ьеу = ЬазЬ(ватле). Такое вычисление является просто локальной процедурой, вызовом функции ЬазЬ, Если держатель генеалогической записи хочет сделать ее доступной всем, оп должен построить кортеж (набор взаимосвязанных величин), состоящий из полей (петле, мой 1Р-адрес), и затем выполнить функцию зиссеззог(Ьай(лагле)) для сохранения кортежа в общепринятой форме. Если существует несколько записей (на разных узлах) для одного и того же названия, все их кортежи будут храниться на одном и том же узле.
То есть индекс распределяется случайным образом между узлами. Во избежание сбоев системы, для хранения кортежей на р узлах используется р различных хэщ-функций, но далее мы не будем учитывать этот нюанс. Таблица указателей узла 1 Таблица указателей узла 4 ®, ' "';;1зу .1?) (,'(в) %9 Таблица указателей узла 12 (2В, ф ® ~гэ) (22ч Рис. 6.22. Набор из 32 идентификаторов узлов, выстроенных по кругу (в). Закрашенные кружочки соответствуют реальным узлам. Дугами обозначены указатели с узлов 1, 4 и 12. Подписи на дугах соответствуют индексам таблицы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
