Диссертация (1137145), страница 4
Текст из файла (страница 4)
Параметр принято называть параметромширины репликации (system-wide replication parameter).Так же как и в других децентрализованных peer-to-peer системах, в сетиKademlia поиск узла, чей идентификатор является ближайшим кидентификатору , производится инициатором, путём последовательногоопроса узлов в направлении уменьшения значения XOR-метрики до наосновании таблицы маршрутизации, имеющейся у каждого узла. Впроцессе поиска идентификатора x, узел имеющий идентификатор назапрос узла инициатора сообщает ему IP адрес узла, чей идентификатор ′будет как можно ближе к на основании XOR-метрики среди множестваузлов известных ему узлов.
Если таких узлов нет, то ближайшим узлом к является он сам.Рис. 6 Двоичное дерево пространства идентификаторов Kademlia.201.1.3.1 Таблица маршрутизацииДля поддержания целостности сети и для обеспечения возможностипоиска, каждый узел Kademlia поддерживает таблицу маршрутизации, вкоторой хранится структурированная информация о некоторых другихузлах.Таблица маршрутизации строится и поддерживается так, чтобыобеспечить логарифмическую зависимость числа узлов, опрашиваемых вовремя процедуры поиска, от общего размера системы. Для этого алгоритмиспользуетзначениеидентификаторамиузлов.XOR-метрики(Далеевработевычисляемойподмеждусловосочетанием"расстояние до узла" будет пониматься расстояние до идентификатораэтого узла.Основная идея быстрой навигации в Kademlia заключается в том, чтобысформировать таблицу маршрутизации таким образом, чтобы во времяпроцедуры поиска ближайшего узла к идентификатору , каждый узел могуказать на узел, чей идентификатор имеет общий префикс длиннее, покрайней мере, на один бит, чем общий префикс с его собственным.С этой целью i-я строка таблицы (0 ≤ < 160) хранит информацию обузлах, чьи идентификаторы имеют общий префикс длинной 160 − бит иразличаются в 159 − бите, что соответствует расстоянию от 2+1 до 2 .Таким образом, последняя строка для узла 0011 может содержатьинформацию о любых узлах 1xxx, предпоследний об узлах 01xx, еще науровень ближе — об узлах 000x (см.
рис. 1.3.1). Каждая строка хранит неболее чем записей, и принято её называть - bucket. Обычно вконкретных реализациях = 20.Поддержание такой структуры таблицы в актуальном виде обеспечиваетсложность поиска в сети за логарифмическое число шагов от общего числаузлов в системе (см. доказательство в оригинальной статье).211.1.3.2 Алгоритм поискаТак же как и в других подобных peer-to-peer системах, в том числе и вChord, Kademlia использует жадный алгоритм.
Координацию поискаосуществляет узел инициатор. Он последовательно опрашивает узлы с всёболееуменьшающимсязначениямXOR-метрикидоискомогоидентификатора . Каждый узел на запрос инициатора отвечает списком узлов, чьи идентификаторы являются ближайшими к , или возвращаетинформацию, связанную с ключом , если таковая имеется. Поискостанавливается, когда все опрошенные узлы не знают ни одного узла,который бы был ближе к , чем все ранее опрошенные.На рисунке 7 изображен пример, в котором узел 0011 отыскивает узел1110 последовательного опрашивания наиближайших к запросу известныхему узлов.
После каждого шага инициатор узнает об узле имеющим всёболее длинный общий префикс с искомым.Рис. 7. Узел с уникальным префиксом 0011 отыскивает узел с уникальным префиксом1110221.1.3.3 Типы сообщенийПротокол Kademlia содержит 4 типа сообщений: PING, STORE,FIND_VALUE, FIND_NODE.PING используется для проверки существования конкретного узла всети. Например, он применяется при попытке добавления узла в -bucket,когда тот уже заполнен: опрашиваются существующие узлы, если нетответа, то узел вставляется. Стоит отметить, что более старые узлынаходятся внизу -bucket, это основывается на экспериментальныхданных, говорящих о том, что чем дольше узел остается в сети, темменьше вероятности, что он ее покинет. Поэтому они будут опрошенытолько после более новых.STORE запрос позволяет разместить информацию на заданном узле.Перед выполнением STORE узел должен найти ближайших к ключузначения, которое он собирается опубликовать, а лишь потом отправитькаждому STORE с ключом и своими координатами.
Хранение сразу на узлах позволяет повысить доступность информации.FIND_VALUE запрос, который, зачастую, повторяется для образованияитерации, позволяющий найти значение по ключу. Реализует поискзначения в сети. Возвращает либо ближайших узлов, либо самозначение, в зависимости от достижения узла, хранящего искомые данные.Итерации прекращают как раз либо при возвращении значения (успех),либо при возврате уже опрошенных узлов (значения нет в сети).FIND_NODE запрос используется для поиска -ближайших узлов кзаданному идентификатору (поведение сходно с FIND_VALUE, тольконикогда не возвращает значение, всегда узлы).
Используется, например,при присоединении узла к сети по следующей схеме:— Контакт с bootstrap узлом— Посылка запроса FIND_NODE со своим идентификатором к bs узлу,дальнейшая итеративная рассылка23— Обновление -buckets (при этом обновляются как -buckets новогоузла, так и всех, мимо которых проходил запрос (здесь на рукусимметричность метрики XOR))1.1.4 PastryPastry-этосамоорганизующаясясистемаузловобъединённыхлогической сетью.
Pastry является ещё одной реализацией концепции DHT.Отличительной чертой Pastry является, то, что в ней для построениятаблицы маршрутизации используется информация не только о близостиидентификаторов узлов (numeric metric), но и информации об их подобиив терминах IP протокола, и качества канала связи выраженных в мереподобия (proximity metric).
Использование информации о мере подобияузлов позволяет Pastry существенно сократить время основных операций,за счёт того, что обмен сообщениями в основном происходит междуузлами, имеющими быстрый канал связи. Для этой цели узлы Pastry крометаблицы маршрутизации поддерживают множество узлов ближайших помере подобия (proximity metric), называемое окрестностью (neighborhoodset).В качестве идентификаторов и ключей в Pasty используются 128-битныеидентификаторы.
Узлам идентификаторы назначаются либо случайнымобразом, либо вычисляются как значение хэш-функции от IP адреса узла.Так же как и в Chord в качестве меры близости между узлами используетсямодульразностидвухидентификаторовидлянаглядностиидентификаторы располагают на кольце.1.1.4.1 Таблица маршрутизацииДля эффективной навигации в логической сети, Pastry использует идеюаналогичную Kademlia: каждый раз при поиске ключа X, сообщениепересылается к узлу, чей идентификатор имеет общий префикс с Xминимум на один бит длиннее, чем идентификатор предыдущего узла.Однако для представления идентификаторов используются числа не в24двоичной системе исчисления, а в системе исчисления по основанию 2! ,где - конфигурационный параметр системы, обычно равный от 2-х до 4х.Таблица маршрутизации узла с идентификатором Y состоит из !! строк, в каждой из которых имеется 2! − 1 запись.
В каждой записихранится значение идентификатора IP-адрес, узла на который онауказывает. В -ой строке записи соответствуют узлам, чьи идентификаторыимеют общий префикс c Y длинной , но различающихся + 1 цифрой отY и при возможности отличающихся + 1 знаком между собой, такимобразом, охватывая 2! − 1 возможных различных значений + 1-го знака.Пример таблицы маршрутизации узла с идентификатором "10233102" дляслучая = 2 приведен на рис.
1.4.1В отличие от Chord и Kademlia, узы Pastry поддерживают ещё двадополнительных множества; множество листьев (leaf set) и множествоокрестности (neighborhood set) . Для узла c идентификатором Yмножество листьев хранит ||/2 узлов, чьи идентификаторы являютсяближайшими к Y, но при этом численно больше Y. Другая половинамножества содержит узлы, чьи идентификаторы ближайшие к Y, ночисленно меньше Y.Множество узла Y содержит узлы ближайшие по мере подобия(proximity metric) т.е.
во множестве хранятся узлы имеющее наилучшийканал связи с Y. Далее это множество используется для того, чтобы придобавлении нового узла X в систему, сформировать у него таблицумаршрутизации состоящего из узлов имеющих наилучший канал связи с X.Пример множества листьев и множества окрестности так же приведен нарисунке 8.25Рис. 8. Состояние узла с идентификатором 10233102 в сети Pastry с параметром = 2 и = 8.
Все числа записанны исчисления по основанию 4.1.1.4.2 Алгоритм поискаАналогично Chord и Kademlia, Pastry использует жадный алгоритмпоиска(см.рисунок9),т.е.поисковоесообщениепередаетсянаиближайшему узлу к искомому идентификатору. Однако алгоритмпоиска Pastry имеет небольшое отличие за счёт того, что на узлахподдерживается дополнительное множество листьев (leaf set).Ниже изложено описание процедуры маршрутизации поисковогосообщения ключа для узла . Для описания алгоритма будутиспользоваться следующие обозначения:!! - -я запись в таблице маршрутизации в строке , 0 ≤ < 2! ,0 ≤ < 128/ ;! - -й ближайший узел к из множества листьев , − /2 ≤ ≤ /2 , где отрицательное или положительное значение индексасоответвует меньшему или большему значения едентификатора узла! относительно , соответственно;! - значение бита с номер у ключа ;ℎ , - количество бит в общем префиксе и .2601 if (− L /2 ≤ D ≤ L /2 )02//если D находится в диапазоне множеста листьев03Переслать сообщение L! , для которого |D − L! | → min04 else05//обратиться к таблице маршрутизации R06l:=shl(D, A);!07if (R ! ! ≠ null)!08Переслать сообщение R ! !09else10Переслать сообщение узлу T ∈ L ∪ R ∪ M, такому что11shl T, D ≥ l и T − D < | − |Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
