P2P: различия между версиями

'''Сеть с адресуемым содержимым'''

Сеть с адресуемым содержимым (CAN) [31], разработанная в ICSI, строит сеть как виртуальное <math>d</math>-мерное пространство, присваивая каждому узлу <math>d</math>-мерный идентификатор. Топология маршрутизации напоминает <math>d</math>-мерный тор. Маршрутизация осуществляется по евклидовым координатам в каждом измерении, что дает стратегию маршрутизации с <math>dn^{1/d}</math> переходов. Параметр <math>d</math> может быть настроен администратором сети. Отметим, что при <math>d = log \; n</math> характеристики CAN такие же, как и в Chord, а именно: логарифмическая степень и логарифмическое число переходов маршрутизации.

Один из недостатков сетей с распределенной хэш-таблицей (DHT) заключается в том, что они поддерживают только точный поиск ключей, а значит, плохо решают задачи поиска диапазона ключей или нечеткого поиска, например, поиска любого ключа, соответствующего некоторому префиксу. '''SkipGraphs''' [4] и схема '''SkipNet''' [19] от Microsoft (проект Herald) независимо друг от друга разработали аналогичную сеть DHT на основе рандомизированного списка пропусков [28], которая поддерживает запросы по диапазону в распределенной сети. Подход в обеих этих сетях заключается в объединении объектов в двухсвязный список, отсортированный по именам объектов, над которым строятся «короткие» указатели. Указатели от каждого объекта переходят на геометрическую последовательность расстояний в отсортированном списке, то есть первый указатель переходит через два элемента, второй – через четыре, и так далее, вплоть до указателя <math>log \; n - 1</math>, который переходит через половину списка. Логарифмический, сбалансированный по нагрузке поиск достигается в этой схеме таким же образом, как и в Chord. Поскольку пространство идентификаторов сортируется по именам объектов, а не по хэш-идентификаторам, диапазоны объектов можно эффективно сканировать, просто переходя к наименьшему значению в диапазоне; остальные узлы диапазона располагаются смежно вдоль кольца.