Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 118
Текст из файла (страница 118)
Теперь необходимо узнать имя этого племянника и того, у кого могут быть какие-либо сведения о нем. Как же это сделать, не имея централизованной базы данных? Для решения этой проблемы было предложено несколько различных алгоритмов. Мы рассмотрим метод хордгя (1)аЪек и др., 2001а; 5го1са и др., 2001). Несколько упрощенное объяснение принципа его работы таково. Пусть система состоит из и пользователей. У каждого пз них есть какпе-то записи, и каждый готов хранить биты и части индекса, которые могут быть использованы другими.
У каждого узла есть 1Р-адрес, который может быть закодирован т-битным номером с помощью хэш-функции. В методе хорды используется алгоритм 5НА-1 для вычисления значения хэш-функции. 5НА-1 применяется в криптографии, и мы рассмотрим его в главе 8. А сейчас нам просто надо знать, что это некоторая функция с аргументом в виде строки переменной длины и значением — 160-битным числом высокой степени случайности. Таким образом, любой 1Р-адрес можно закодировать 160-битным числом, называемым идентификатором узла.
Концепция состоит в том, что вообще все 2мь идентификаторов располагаются в возрастающем порядке, образуя большой круг чисел. Некоторые из идентификаторов соответствуют реально существующим узлам, но это лишь малая часть из них. На рис. 5.22 показан круг идентификаторов для т = 5 (на дуги внутри круга пока внимания не обращайте). В этом примере реальным узлам соответствуют идентификаторы 1, 4, 7, 12, 15, 20 и 27. На рисунке кружочки с этими номерами закрашены. Всем остальным идентификаторам нельзя поставить в соответствие какие-либо узлы. Определим функцию определения последователя зяссеззог(я) как идентификатор первого реального узла, следующего после я в описанном нами круге (по часовой стрелке).
Например, зиссеззог(6) = 7, зиссеззог(8) = 12, зпссеззог(22) = 27. Названия записей (например, названия песен, имена предков и т. п.) также обрабатываются хэш-функцией ЬиЬ (с помощью алгоритма 5НА-1) и превраща- Алгоритмы маршрутизации 441 ются в 160-битные числа, называемые ключами. Таким образом, чтобы получить ключ (Ьеу) из названия записи (па)не), необходимо вычислить Ьеу = ЬаэЬ(патле). Такое вычисление является просто локальной процедурой, вызовом функции ЬоэЬ, Если держатель генеалогической записи хочет сделать ее доступной всем, он должен построить кортеж (набор взаимосвязанных величин), состоящий из полей (лате, мой 1Р-адрес), и затем выполнить функцию зиссеээог(ЬаэЬ(лате)) для сохранения кортежа в общепринятой форме.
Если существует несколько записей (на разных узлах) для одного и того же названия, все их кортежи будут храниться на одном и том же узле. То есть индекс распределяется случайным образом между узлами. Во избежание сбоев системы, для хранения кортежей на Р узлах используется р различных хзщ-функций, но далее мы не будем учитывать этот нюанс.
Таблица указателей узла 1 Таблица указателей узла 4 Таблица указателей уию 12 (26 Сйбх (24) (22) (22 Рис. 6.22. Набор иэ 32 идентификаторов узлов, выстроенных по кругу (а). Закрашенные кружочки соотввтствуют реальным узлам. Дугами обозначены указатели с узлов 1, 4 и 12. Подписи на дугах соответствуют индексам таблицы. Примеры таблиц указателей (б) 442 Глава 5. Сетевой уровень Если кто-то из пользователей затем захочет найти название записи (вате), он вычислит значение хэш-функции, получит ключ (1еу) и затем с помощью функции зяссежог(веу) сможет найти !Р-адрес узла, хранящего кортежи индексов. Первый шаг осуществляется довольно просто, не в пример второму.
Для того чтобы можно было найти 1Р-адрес узла, соответствующего какому-либо ключу, каждый узел должен поддерживать определенные служебные структуры данных, Одной из них является 1Р-адрес последователя. Например, на рис, 5,22 последователь узла 4 — это узел 7, а последователь узла 7 — узел 12. Теперь можно начинать поиск. Запрашивающий узел посылает последователю пакет, содержащий его 1Р-адрес и ключ, который он ищет.
Этот пакет пересылается по кругу до тех пор, пока не будет найден искомый узел. На нем проверяется соответствие имеющейся информации ключу, и при положительном результате проверки пакет возвращается напрямую запрашивающему узлу, чей 1Р-адрес содержится в запросе, В качестве первой оптимизации алгоритма предлагается следующее: каждый узел должен знать 1Р-адрес не только последователя, но и предшественника, тогда запрос можно будет распространять одновременно в двух направлениях — по часовой стрелке и против часовой стрелки, в зависимости от того, какой из путей кажется более коротким.
Например, на рис. 5.22 узел 7 может отправить пакет по часовой стрелке, если ищется узел 10. А если ищется узел 3, то логичнее направить пакет против часовой стрелки. Даже с этой возможностью выбора направления линейный поиск остается крайне неэффективным методом для больших равноранговых сетей, поскольку среднее число узлов, которое потребуется обойти для поиска записи, равно пг2, Значительно ускорить поиск позволяет поддерживаемая каждым узлом специальная таблица, которая в методе хорд носит название таблицы указателей.
В ней имеется т записей, пронумерованных от 0 до т — 1. Каждая запись содержит два поля: начало и 1Р-адрес последователя — юссехтог(згагг), как показано на рис. 5.22, б. Значения полей записи (на узле я равны; отагт = в + 2' (тойи!о2'"), 1Р-адрес зиссехтог (йагГ 111). Обратите внимание: на узлах хранится сравнительно небольшое число адресов, и большинство из них расположено довольно близко друг от друга в терминах идентификаторов узлов. С использованием таблицы указателей процесс поиска ключа на узле х выглядит следующим образом.
Если ключ попадает в диапазон между в и ягссеззог(я), значит, он находится, на самом деле, на узле зиссеззог(я), н поиск прекращается В противном случае таблица указателей просматривается на предмет поиска записи, поле начало которой является ближайшим предшественником ключа. Запрос посылается напрямую по 1Р-адресу из таблицы указателей. Узел с этим адРесом просят перенять инициативу поиска. Поскольку искомый ключ находится где-то Рядом, но идентификатор имеет меньшее значение, велика вероятность того, что конечный ответ будет дан очень скоро, спустя всего несколько дополнительных запросов.
Поскольку каждая итерация при поиске вдвое уменьшает Алгоритмы маршрутизации 443 последующую область рассмотрения (то есть оставшееся расстояние до цели), то можно доказать, что среднее число итераций равно 1оя„п. В качестве первого примера рассмотрим поиск ключа яеу = 3 на узле 1. Узел с идентификатором 1 знает, что 3 лежит где-то между ним самим и его последователем — узлом 4. Он делает вывод о том, что ключ находится на узле 4, н поиск прекращается. Результатом является 1Р-адрес узла 4.
Второй пример. Пусть узлу 1 теперь понадобилось найти ключ Йеу = 14. Число 14 не находится между 1 и 4, поэтому необходимо заглянуть в таблицу указателей. Ближайшим предшественником 14 является 9, поэтому запрос направляется на 1Р-адрес, хранящийся в записи с полем начало, равным 9. Конкретно, это узел 12, Последний видит, что 14 находится между ним самим и последователем — узлом 15, поэтому результатом поиска является 1Р-адрес узла 15, Третий пример.
Допустим, узлу 1 нужно найти ключ 1еу = 16. Запрос, как и в предыдущем примере, отправляется на узел 12. Но на этот раз узел не может самостоятельно ответить на него. Он пытается найти тот узел, который находится ближе всего к 16, но имеет меньший идентификатор. Им является узел 14, который ссылается, в свою очередь, на узел 15. Запрос туда и посылается. Узел 15 видит, что 16 находится между ним самим и его последователем (20), поэтому он возвращает 1Р-адрес 20 просителю. Ответ возвращается сразу на узел 1.
Поскольку узлы могут появляться в сети и исчезать из нее в любое время, в методе хорд необходимо как-то обрабатывать подобные ситуации. Мы предполагаем, что когда система начинала работать, она была достаточно небольшой, и узлы могли обмениваться информацией напрямую, выстраивая первичный круг идентификаторов и таблицы указателей. После этого уже необходима автоматизированная процедура. Когда новый узел г собирается войти в сеть, он должен войти в контакт с какой-либо из уже находящихся в сети станций и попросить ее поискать для него 1Р-адрес зиссезтог(г).
Затем новый узел выясняет, кто будет его предшественником (зиссеазог(г) для предшественника). Все это нужно для того, чтобы можно было определить свое место в круге идентификаторов. Например, если узел 24 на рис. 5.22 захочет войти в сеть, он может поинтересоваться у любого узла, чему равно значение зиссеззог(24). Выясняется, что оно равно 27. Затем у узла 27 надо узнать, кто является его предшественником (20).
После того как обоим этим узлам сообщается о существовании нового узла, узел 20 помечает себе, что его последователем становится узел 24, а узел 27 — что этот узел становится его предшественником. Кроме того, узел 27 передает ключи диапазона 21-24 новичку, С этого момента последний считается зарегистрированным в равноранговой сети, Тем не менее, ситуация изменилась, и многие таблицы указателей теперь содержат ошибки.
Чтобы исправить их, все узлы запускают фоновые процессы, которые периодически пересчитывают таблицы указателей, обращаясь к функции зиссехгог. Когда какой-то из этих запросов наталкивается на новый узел, запись таблицы обновляется. Если узел уходит вежливо, он передает свои ключи последователю и информирует предшественника о своем скором отбытии. При этом в цепочке идснтнфикаторного круга предшественник теперь оказывается непосредственным соседом последователя. Однако если с узлом происходит какая-то авария, возникают 444 Глава 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
