Маршрутизация в одноранговых сетях

Маршрутизация в одноранговых сетях

Иллюстрации

Показать все

Реферат

Данная заявка испрашивает приоритет под 35 USC §119(e) к U.S. Provisional Application No. 60/559,370, поданному 31 марта 2004.

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

Данное изобретение относится, в общем случае, к одноранговым сетям и, более подробно, к маршрутизации в одноранговых сетях.

УРОВЕНЬ ТЕХНИКИ

Одноранговые сети продолжают увеличивать популярность из-за многих привлекательных особенностей, таких как адаптация, самоорганизация, балансирование загрузки, отказоустойчивость, дешевизна, высокая доступность, масшабируемость и способность обеспечить большой пул ресурсов. Например, одноранговые сети появились как популярный способ совместно использовать большое количество данных, таких как загрузка песен равными устройствами, на которые ссылаются как на доступные для загрузки от другого равного устройства в одноранговой сети.

Традиционная архитектура, которая используется для обеспечения одноранговой сети, однако, не имеет адресации для постоянно увеличивающегося числа членов, то есть узлов, которые могут формировать систему. Например, текущий пример одноранговой сети обеспечивает более чем 230 миллионов загрузок более чем четырем миллионам пользователей. Число членов, однако, как ожидается, будет непрерывно увеличиваться так, что можно столкнуться с ультрабольшой системой, которая имеет более чем один триллион узлов. Поэтому даже при том, что текущая архитектура может адресовать систему, имеющую большое количество узлов, эта текущая архитектура может, однако, оказаться неадекватной при использовании в ультрабольшой системе.

Для определения местонахождения специфического ресурса в одноранговой сети каждый узел в сети, например, может ссылаться на один или более других узлов в сети для определения местонахождения узла, имеющего специфический ресурс, например специфический элемент данных. Поэтому может использоваться ряд «пересылок», поскольку запрос направляется от одного узла до другого до тех пор, пока специфический элемент не будет достигнут. При увеличении число пересылок также увеличивается и использование аппаратных и программных ресурсов узлов, как и сетевых ресурсов системы. Таким образом, увеличение числа пересылок может привести к неэффективному использованию ресурсов системы, а также увеличить время, используемое для определения местонахождения специфического элемента.

Соответственно существует постоянная потребность в улучшенной маршрутизации в одноранговых сетях.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

Описывается маршрутизация, в которой таблица маршрутизации используется для направления сообщений (например, запросов на специфический ресурс и ответы на запрос) в одноранговой сети. Таблица маршрутизации может быть модифицирована через широковещательную рассылку для обновления записей в таблице маршрутизации, которые являются ссылками на узлы в одноранговой сети. В одном из вариантов осуществления бюджет обслуживания, используемый для поддержания таблицы маршрутизации каждого узла, распределен по множеству сегментов ресурсного пространства одноранговой сети с помощью построения компактных записей таблицы маршрутизации для каждого сегмента. Поэтому полный бюджет обслуживания для поддержки таблицы маршрутизации может быть уменьшен, что освобождает аппаратные средства, программное обеспечение и сетевые ресурсы одноранговой сети для обеспечения желательной функциональности по перенаправлению сообщений.

В одном из вариантов осуществления способ включает в себя получение в одном из множества узлов в одноранговой сети индикации относительно изменения в членстве в одноранговой сети другим узлом в одноранговой сети. Сообщение, которое описывает изменение, передается по широковещательной рассылке. Сообщение получается каждым узлом, который упоминается в таблице маршрутизации, включенной в указанный один узел.

В другом варианте осуществления способ включает в себя определение, на узле для включения в одноранговую сеть, доступных ресурсов этого узла для коммуникации в одноранговой сети. Таблица маршрутизации формируется на узле, основываясь на намерении направлять запросы в одноранговой сети.

В дополнительном варианте осуществления способ включает в себя компрессирование данных, которые описывают записи в таблице маршрутизации, используя итерационный фильтр Блюма одним из множества узлов в одноранговой сети. Коммуникация формируется для передачи компрессированных данных к другому указанному узлу.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

Фиг.1 является иллюстрацией примерного осуществления, показывающей среду, которая конфигурирована для обеспечения одноранговой сети.

Фиг.2 является иллюстрацией системы в примерном осуществлении, в которой множество узлов одноранговой сети показаны более детально.

Фиг.3 является иллюстрацией в примерном осуществлении, показывающей снимок множества таблиц с программируемым состоянием маршрутизации множества узлов в системе в одномерном логическом ключевом пространстве.

Фиг.4 является иллюстрацией примерного осуществления, показывающей формирование записей в таблице с программируемым состоянием маршрутизации для данного блока с помощью вращения идентификатора и построения другого кольца.

Фиг.5 является иллюстрацией примерного осуществления, показывающей маршрутизацию, использующую таблицу с программируемым состоянием маршрутизации колец, описанных относительно фиг.4.

Фиг.6 является иллюстрацией примерного осуществления, показывающей часть таблицы с программируемым состоянием маршрутизации и порождение записей в таблице с программируемым состоянием маршрутизации.

Фиг.7 является иллюстрацией примерного осуществления, показывающей итерационный фильтр Блюма.

Фиг.8 является блок-схемой, иллюстрирующей процедуру в примерном осуществлении, в которой узел формирует и посылает сообщение, которое описывает события, полученные тем узлом, который индицирует изменение в членстве в одноранговой сети.

Фиг.9 является блок-схемой, изображающей процедуру в примерном осуществлении, в которой размер таблицы маршрутизации динамически определяется, основываясь на доступных ресурсах узла.

Фиг.10 является иллюстрацией примерного компьютерного устройства, которое может использоваться для обеспечения узла в одноранговой сети.

Одинаковые ссылочные позиции используются в описании и на чертежах ссылаются на подобные компоненты и особенности.

Осуществление изобретения

Краткий обзор

Описывается маршрутизация в одноранговой сети. Как описывалось ранее, желательно такое уменьшение числа пересылок, чтобы уменьшить число используемых узлов для пересылок, таким образом снижая общие затраты в пропускной способности. Описаны технологии маршрутизации для уменьшения числа пересылок, используемых для нахождения ресурсов в ультрабольшой системе (то есть имеющей 1 триллион узлов), но с низким и контролируемым бюджетом обслуживания на один узел.

Таблицы маршрутизации используются узлом для ссылок на другие узлы в одноранговой сети. Традиционное обслуживание таблиц маршрутизации, однако, может использовать неприемлемо большое количество аппаратных средств, программного обеспечения и сетевых ресурсов в ультрабольшой системе. Традиционные технологии обслуживания, например, используют зондирование так, чтобы записи в таблицах маршрутизации были модифицированы, определяя, с помощью посылки запросов и получения ответов на запросы, доступен ли узел, который упоминается в таблице как доступный в настоящее время в системе. Хотя количество аппаратных средств, программного обеспечения и сетевых ресурсов, используемых для каждого зондирования, является относительно небольшим, когда это использование ресурса суммируется по всей системе, количество может стать существенным. Поэтому ультрабольшая система может понести существенную потерю в функциональных возможностях при использовании этих традиционных технологий обслуживания. В технологиях обслуживания, описанных здесь, бюджет обслуживания, используемый для поддержки таблиц маршрутизации, может быть распределен по множеству сегментов пространства ресурсов одноранговой сети с помощью построения плотных записей в таблице маршрутизации для каждого сегмента. Таким образом, полный бюджет обслуживания для поддержки таблицы маршрутизации может быть уменьшен, что освобождает аппаратные средства, программное обеспечение и сетевые ресурсы одноранговой сети для обеспечения требуемых функциональных возможностей маршрутизации запросов и ответов на запросы. Таким образом, таблицы маршрутизации могут быть обслужены, используя меньшее число пересылок в ультрабольшой системе без того, чтобы это приводило к недопустимому бюджету обслуживания. Дальнейшее обсуждение плотных записей маршрутизации и обслуживания таблиц маршрутизации может быть найдено при описании фиг.3.

Дополнительно, хотя предыдущие O(logN) технологии маршрутизации, которые использовались, нашли успех в существующих системах, принятое в настоящее время малое основание (то есть параметр b в O(log _b N)) в предыдущих технологиях больше не является адекватными для ультрабольших систем. Например, когда число узлов «N» в системе - один триллион, наихудшее число пересылок - 20 (когда b - 4 приблизительно с 60 записями) при использовании традиционной технологии маршрутизации O(logN). В осуществлении, которое описано более детально в разделе «Производительность маршрутизации», среднее число маршрутизаций в системе, имеющей один триллион узлов, которая использует технологии маршрутизации, описанные здесь, уменьшено до 5,5 пересылок.

Примерная среда

Фиг.1 является иллюстрацией примерного осуществления, показывающего систему 100, которая сконфигурирована для обеспечения одноранговой сети. Система 100 включает множество клиентов 102(a), где «a» может быть любым целым числом от одного до «A», которой соединено с множеством компьютерных устройств 104(1)-104(B) по сети 106. В этом осуществлении каждый из множества клиентов 102(a) и множества компьютерных устройств 104(1)-104(B) представляет собой узел в сети 106. Об узле можно думать, как о точке подключения для передачи данных, типа точки перенаправления, которая предоставляет данные другим узлам и/или конечной точке, которая является адресатом и/или источником данных.

Множество клиентов 102(a) и множество компьютерных устройств 104(1)-104(B) могут быть сконфигурированы разнообразными способами. Например, клиенты 102(a) и компьютерные устройства 104(1)-104(B) могут быть сконфигурированы как компьютеры, которые имеют возможность связываться по сети 106, такой как беспроводной телефон (например, компьютерное устройство 104(1)), планшетный компьютер (например, компьютерное устройство 104(2)), портативный компьютер (например, компьютерное устройство 104(3)), настольный компьютер (например, компьютерное устройство 104(4)), сервера (например, компьютерное устройства 104(5)-104(6)), универсальный компьютер (например, компьютерное устройство 104(B)) и другие компьютерные устройства типа мобильной станции, прибора для развлечения, компьютерной приставки к телевизору и т.д. Дальнейшее обсуждение примерного компьютерного устройства может быть найдено при описании фиг.10. Таким образом, множество клиентов 102(a) и компьютерные устройства 104(1)-104 B) могут находится в пределах от устройств с полным ресурсом с существенной памятью и процессорными ресурсами (например, персональными компьютерами, телевизионными записывающими устройствами, оборудованными жестким диском) до устройств с малым ресурсом с ограниченной памятью и/или процессорными ресурсами (например, традиционные компьютерные приставки к телевизору). Клиенты 102(a) могут также относиться к персоне и/или объекту, которые используют клиента. Другими словами, клиент 102(a) может описать логического клиента, который включает пользователя и/или машину.

Сеть 106 сконфигурирована как одноранговая сеть. Одноранговая сеть позволяет узлам сети 106 обращаться к общедоступным ресурсам, расположенным на каждом из узлов, то есть множеству клиентов 102(a) и множеству компьютерных устройств 104(1)-104(B). Примеры одноранговых сетей, которые были известны и использовались в прошлом, включают следующее:

● Freenet, как описано. I. Clarke, B. Wiley, O. Sanberg, и T. Hong в “Freenet: A Distributed Anonymous Information Storage and Retrieval System,” Proc. Int. Workshop on Design Issues in Anonymity and Unobservability, Springer Verlag, LNCS 2009, 2001;

● Chord, как описано I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, H. Balakrishnan в “Chord A Scalable Peer-to-peer Lookup Service for Internet Applications,” Proc. ACM SIGCOMM'01, San Diego, California, USA, 2001;

● CAN, как описано S. Ratnasamy, P. Francis, M. Handley, R. Karp, и S. Shenker в “A Scalable Content-Addressable Network,” Proc. ACM SIGCOMM'01, San Diego, California, USA, 2001;

● Pastry, как описано A. Rowstron и P. Druschel в “Pastry: Scalable, Decentralized Object Location and Routing for Large-Scale Peer-to-Peer Systems,” IFIP/ACM Int. Conf. Distributed Systems Platforms (Middleware), 2001; и

● Tapestry, как описано B. Y. Zhao, J. Kubiatowicz, и A. D. Joseph и “Tapestry: An Infrastructure for Fault-tolerant Wide-Area Location and Routing,” Technical Report No. UCB/CSD-01-1141, Univ. of California, Berkeley.

Одноранговые сети могут предложить разнообразные особенностей, например избыточность и отказоустойчивость. Например, данные, сохраненные в одноранговой сети, могут постепенно распространяться как данные, скопированные узлами одноранговой сети. Таким образом, данные могут стать сильно избыточными в одноранговой сети, что может привести к увеличению надежности и доступности данных.

Используя одноранговую сеть, можно обмениваться разнообразными ресурсами, например данными, циклами обработки, хранилищами данных и тому подобное. Таким образом, одноранговая сеть может использоваться для усиления коллективной мощности множества клиентов 102(a) и множества компьютерных устройств 104(1)-104(B). Одноранговая модель является моделью связи, в который каждый узел, то есть «член», может связаться непосредственно с другим членом и/или через посредничество компьютерного устройства. Клиенты 102(a) и компьютерные устройства 104(1)-104(B) могут связываться по сети 106, используя сообщения, такие как запросы и ответы. Хотя проиллюстрированы семь компьютерных устройств 104(1)-104(B), в среде может быть осуществлено широкое разнообразие компьютерных устройств. Дополнительно множество клиентов 102(a) может также быть сконфигурировано как «равные устройства», то есть члены в одноранговой сети.

Сеть 106 включает распределенную хеш-таблицу 108 (DHT), которая действует как интерфейс для направления сообщений между клиентами 102(a) и множеством компьютерных устройств 104(1)-104(B). DHT 108 можно рассматривать как распределенную версию структуры данных хеш-таблицы, которая хранит пары (ключ, значение). Например, ключ может соответствовать имени файла, а значение может соответствовать содержанию файла. Каждое равное устройство в сети 106, например компьютерные устройства 104(1)-104(B), хранит подмножество пар (ключ, значение). Поэтому DHT 108 используется для того, чтобы найти узел, ответственный за соответствующий ключ. Другими словами, DHT 108 отображает ключ к узлу для направления сообщений между клиентами 102(a) и множеством компьютерных устройств 104(1)-104(B). «Поверх» DHT 108 может быть построено множество служб, например службы совместного использования файлов, службы архивирования (например Web-архивирование), базы данных, системы имен, службы поиска, оповещения уровня группы приложений, уведомление о событии, службы интерактивной переписки, коммуникации на основе встреч, запрос и индексация, публикация/подписка данных и так далее.

DHT 108 разделяет ресурсы, обеспеченные множеством компьютерных устройств 104(1)-104(B), на множество зон 110(1)-110(8), то есть «областей памяти». Каждая из множества зон 110 (1)-110 (8) может рассматриваться как часть всех ресурсов, находящихся в общем доступе в системе 100. Например, как описывалось ранее, DHT 108 ассоциирует ресурсы с ключами. Ключ является хешированным для нахождения определенной одной из множества зон 110(1)-110(8), использующих DHT 108. Множество зон 110(1)-110(8) может быть обеспечено разными путями. Например, зона 110(1) представлена наглядно на фиг.1 как обеспеченная компьютерным устройством 104(1). Аналогично, каждая зона 110(2), 110(3), 110(4), 110(5), 110(6) обеспечена соответствующим компьютерным устройством 104(2), 104(3), 104(4), 104(5), 110(6). Дополнительно компьютерное устройство может обеспечить больше чем одну зону, которые представлены наглядно на фиг.1 как зоны 110(7), 110(8), обеспеченные компьютерным устройством 104(B).

DHT 108 показана как использующая архитектуру с тремя уровнями, которая включает leafset 112, таблицу 114 направлений и таблицу 116 программного состояния маршрутизации (SSRT). Leafset 112 используется для гарантии целостности пространства ключей. Например, leafset 112 может использовать непротиворечивое хеширование для разделения пространства ресурсов и пространства ответа узла в одну или более из множества зон 110(1)-110(8), как это описывалось ранее.

Таблица 114 направлений, то есть средний уровень, может использоваться для осуществления алгоритма маршрутизации, основанного на префиксе, типа префикса алгоритма маршрутизации O(logN), где «N» - общее количество узлов. Каждый узел, например, может включить таблицу 114 направлений, которая имеет записи, то есть направления, которые указывают на другие узлы в системе 100. Записи таблицы 114 направлений могут следовать логарифмической функции к ссылке на последовательные «дополнительные» узлы в системе 100. Записи таблицы 114 направлений могут быть созданы инверсией бита идентификатора соответствующего узла и указания на узел, который сохраняет результирующие ключи. Периодическая выдача маркера может использоваться для того, чтобы модифицировать и leafset 112, и записи в таблице 114 направлений, используя, например, механизм зондирования. Таким образом, leafset 112 и таблица 114 направлений могут обеспечить производительность O(logN) для DHT 108.

SSRT 116, когда коэффициент смешивания μ является малым (например, когда узлы присоединяются или уходят из системы 100), дает список узлов, которые являются членами системы 100. Таким образом, SSRT 116 может использоваться для того, чтобы быстро определить местонахождение желательного узла. Конструкция SSRT 116 может быть выполнена, используя направления всех узлов в системе 100, которые формируют граф широковещательной рассылки с адекватной избыточностью. Для целей данного обсуждения широковещательная рассылка обращается к распространению данных в графе, в котором вершина, называемая инициатором, распределяет данные по всем другим вершинам, помещая ряд запросов на ребра графа. Однажды проинформированные, другие вершины помогают инициатору в распространении сообщения. Граф широковещательной рассылки является графом, в котором рассылка может быть достигнута за “” единиц времени.

Фиг.2 является иллюстрацией системы 200 в примерном осуществлении, в котором множество узлов 202(x), где «x» может быть любым целым числом от одного до «X», одноранговой сети показаны с большей детализацией. Узел 202(x) может быть тем же самым или отличным от узлов в системе 100 из фиг.1, например компьютерные устройства 104(1)-104(H) и клиенты 102(a). Узел 202(x) проиллюстрирован как включающий соответствующий DHT 108(x), имеющий leafset 112(x), таблицу 114(x) направлений и SSRT 116(x), которые пронумерованы так, чтобы указать, что эти таблицы являются версией DHT 108, leafset 112, таблицы 114 направлений и SSRT 116 из фиг.1 для этого определенного узла 202(x).

Узел 202(x) может контролировать членство других узлов leafset 112(x) через получение одного или более событий, полученных от соответствующего узла, которые описывают изменение в членстве типа события «ухода» или «присоединения». Когда узел 202(x) наблюдает изменение в членстве, узел 202(x) вставляет один или более из множества событий 204(c), например событие «ухода», в сообщение 206(x). Сообщение 206(x) передается параллельно через каждое направление узла 202(x), описанное таблицей 114(x) направления в предопределенном интервале широковещательной рассылки. Каждое из множества узлов 202(x) может исполнить ту же самую операцию с помощью построения сообщения, которое описывает события, которые узел наблюдал, и также описание событий, полученных от других узлов в системе 200, минус те события, которые были уже описаны узлом 202(x). Таким образом, предлагается алгоритм лавинного распространения, обеспечивающий адекватный избыток (O(logN)) для предоставления надежной широковещательной рассылки с высокой скоростью распространения (в среднем O(logN)).

Для управления стоимостью обслуживания события могут быть буферизированы внутри в очереди 208(x), если квота превышена. Дополнительно DHT 108 может адаптивно управлять ошибкоустойчивостью, используя одно или более правил. Например, чтобы гарантировать, что записи SSRT 116(x) имеют высокое качество (например, записи SSRT 116(x) описывают текущее членство системы 100 из фиг.1), события «ухода», которые описывают, что определенный узел покинул систему 100, отправляются до других событий, например событий «присоединения». Этим способом система 100 сохраняет знание о том, когда ресурсы от определенных узлов не доступны, которые оставили систему перед тем, как быть уведомленным относительно того, когда другой узел присоединился к системе 100, что используется для того, чтобы восстановить равновесие системы 100. Дальнейшее обсуждение равновесия системы может быть найдено в разделе «Адаптации».

В устойчивом состоянии число правильных записей SSRT 116(x) М может быть найдено решением следующего уравнения:

Q=4μ·E·М·logN

где E является размером события. В реализации событие имеет размер 34 байта и включает данные, описывающие тип события, временную метку, адрес IP и идентификатор узла. Константа «4» в уравнении учитывает стоимость пропускной способности и для посылки и для получения, также на одну операцию присоединения и одну операцию ухода для каждого сеанса.

Таким образом, DHT 108(x) может сделать экстенсивным использование объединения, которое осуществляется и во временной (например, пакетные события в сообщениях), и пространственной (например, взаимодействие с Olog ₂ N узлами) областях. Дополнительно, используя широковещательную рассылку для сообщения об изменении в членстве, даже при том, что поддерживается полный кластер, когда нет никакого события, которое будет передано, есть небольшой трафик в сети, что приводит к увеличенной сетевой эффективности.

DHT

В этом разделе использование архитектуры 108 DHT будет описано в динамической среде для системы, имеющей ультрабольшой масштаб. DHT 108 обеспечивает эффект O(log _b N) пересылок с очень большим b (например, b равняется приблизительно 4000), который не требует активного зондирования каждой из записей. Как описывалось ранее, в то время как потребность в пропускной способности может быть маленькой для того, чтобы послать и/или ответить на зондирование, обновление записей в DHT 108, посылая и отвечая на большое количество зондирований, может привести к существенному перерасходу, когда это затрачивает всю или часть системы 100 по фиг.1. Кроме того, уменьшение частоты зондирования может быть нежелательно, потому что определение потери является дорогостоящим, например потеря может привести к переходу на случайные IP для определения местонахождения желательного ресурса в системе.

В следующем осуществлении задублирована производительность b=4000 маршрутизаций на основе префикса, когда N равен одному триллиону. Для целей следующего обсуждения бюджет широковещательной рассылки Q - 5kb/s и коэффициент μ смешивания приняты равным 1/(3 часа). Эти параметры разрешают полному кластеру размером 4 КБ быть сформированными, используя DHT 108. Очевидно, что к разнообразным бюджетам широковещательных рассылок и коэффициентов смешивания можно обратиться способами маршрутизации, описанными здесь.

Пример технологии маршрутизации, которая может использоваться для получения такой производительности, включает два компонента. Первый компонент включает в себя формирование перемычки для подобласти вместо целого ресурсного пространства, используя одну четверть бюджета широковещательной рассылки, то есть Q/4. Второй компонент проектирует механизм для использования четырех таких перемычек для вращения 40 битов при маршрутизации. Каждый из этих компонентов описан в свою очередь в следующих разделах.

Формирование перемычки подобласти

Полное ресурсное пространство T может быть разделено на t/2 ⁱ области для некоторого целого числа «i». Например, деление может быть таким, что в среднем каждая область М содержит приблизительно одну тысячу узлов. Для произвольного узла x сделаем R(x) областью, к которой он принадлежит, и сделаем beamers(x) подмножеством направлений x, которые попадают в пределы R, то есть той точки к другим узлам в этой области R. Таким образом, для всех узлов, которые совместно используют одну и ту же R, соответствующие beamers все вместе формируют граф широковещательной рассылки, который охватывает R и имеет высокую степень избыточности. Применяя тот же самый протокол рассылки в DHT 108 через beamers, каждый из этих узлов может быть снабжен соответствующей SSRT, которая охватывает соответствующую область R. Стоимость пропускной способности может быть рассчитана следующим образом: 4μ·E·М·logM. Таким образом, для текущего осуществления, где E=34B и μ=1/(3 часа), стоимость пропускной способности - приблизительно один килобайт в секунду. Таким образом, первый компонент выполнен, то есть используя меньше чем Q/4 для формирования кластера, который может разрешить самые короткие 10 направлений с основанием 2 за один переход. В сущности, кластер подобласти может быть расценен как leafset узлов размером 1 КБ. Например, если ключ поиска попадает в пределы этого диапазона, будет достаточно одного перехода для нахождения желаемого ресурса.

R может быть оценено различными способами. Например, каждый узел может вычислить средний размер зоны, используя информацию его соответствующего leafset. Следующий узел может тогда сделать свою оценку области R как на 10 битов далее чем . Как предварительно заявлялось, beamers являются направлениями в пределах оценки области. Граница может быть дополнительно предписана с помощью сбрасывания события объединения, посланного узлами, которые лежат вне оценки области. Таким образом, SSRT узла не будет засорено записями от соседних областей.

Фиг.3 является иллюстрацией, показывающей одномерное логическое ключевое пространство 300, который изображает SSRTs в виде нескольких узлов в системе, осуществленной в одноранговой сети. Первая область 302 из одномерного логического ключевого пространства 300 может быть описана с помощью SSRT первого из множества узлов 202(x) из фиг.2, вторая область 304 из одномерного логического ключевого пространства 300 может быть описана с помощью SSRT второго из множества узлов 202(x) из фиг.2 и т.д. Пунктирные линии, проиллюстрированные на фиг.3, представляют теоретические границы разделения областей. Таким образом, как показано на фиг.3, SSRTs заполнены записями, охватывающими соответствующую область соответствующего узла.

Разрешение множественных блоков

В целях нижеследующего обсуждения примем длину идентификатора каждого узла как 160 битов, и десятибитовый сегмент идентификатора назовем «блоком». Так описывалось ранее, идентификатор можно рассматривать как адрес узла в одноранговой сети. Маршрутизация на основе префикса с b=4К разрешает поиск одного блока в один момент. В данном примере системы с одним триллионом узлов всего имеется четыре десятибитовых блоков, которые будут разрешаться.

Маршрутизация переходит на кластер области с помощью сравнения одного бита адреса одновременно с направлениями, до тех пор, пока адресат не попадет в пределы диапазона, охваченного самыми короткими десятью направлениями. В этой точке SSRT предоставляет доступ к ресурсу за один переход. Фактически эти последние десять направлений могут быть расширены в 2¹⁰ SSRT записей для расширения этого доступа. Другими словами, направления, расположенные в других ведущих блоках, расширяются в SSRT записи для включения в тот же самый префиксный диапазон.

В системе из одного триллиона узлов каждый узел имеет в среднем 40 направлений. Для целей нижеследующего обсуждения Ring₀, будет использоваться для обозначения основного кольца. Дополнительно для целей нижеследующего обсуждения идентификатор узла разделен на блоки по десять битов, которые поименованы в алфавитном порядке, как показано на фиг.4. Хотя показаны блоки по десять битов, могут использовать блоки с различным количеством битов. Например, каждый блок может иметь два или более бита, может иметь пять или более битов и так далее.

Например, рассмотрим блок A 402 на фиг.4. Чтобы сформировать SSRT записи блока A 402, идентификатор ID 404 поворачивает вправо для получения нового ID_A 406, в котором блок A 402' находится в 4-ом блоке. Каждый узел использует ID_A 406 для соединения с другим кольцом, обозначенном как Ring_A. Ring_A сформирован способом, идентичным Ring₀, с своим собственным leafset и направлений. Вдобавок ко всему также применен алгоритм кластеризации подобласти. Поэтому узел приобретает SSRT_A 408 в Ring_A размером 1 КБ, и записи являются узлами, чей ID_A является общим с этими основными тремя блоками (то есть N|O|P), но отличается по 4-ому блоку, то есть блоку A 402'.

Отношения ID 404 и ID_A 406 означают, что эти четыре узла, в свою очередь, являются теми, которые совместно используют последние три блока идентификатора, но разные по блоку A в Ring₀. Поэтому задача расширения 10 направлений с основанием 2 в блоке A в 2¹⁰ SSRT записей решена. Подобные размещения могут быть выполнены для блоков B, C и D (например, SSRT_D 410). Сходная схема помогает сформировать SSRT записи, которые охватывают соответствующий блок.

В целом в этом примере сформированы четыре кольца. Для целей нижеследующего обсуждения SSRT записи для блока A обозначены как SSRT_A, SSRT записи для блока B обозначены как SSRT_B, и так далее. Конечный SSRT является комбинацией четырех меньших SSRT (например, SSRT_A, SSRT_B, SSRT_C, SSRT_D) и имеет размер приблизительно 4Кb. Маршрутизация, использующая DHT, может переходить в такую, где биты сравниваются настолько агрессивно, насколько это возможно для продолжения через промежуточные переходы.

Маршрутизация

Фиг.5 является иллюстрацией примерного осуществления 500 показанной маршрутизации, выполненной, используя таблицу SSRT, которая расположена на каждом узле системы 100 из фиг.1. Ключ 502 поиска используется вместе с SSRT 504 для определения местонахождения узла, имеющего определенный адрес 506. Как описывалось в предыдущем разделе, SSRT 504 включает записи, которые ссылаются на узлы, имеющие адреса, которые имеют различные уровни подобия.

SSRT 504, например, может быть составлена из множества частей 508, 510, 512, 514, имеющих соответствующие SSRT записи 516, 518, 520, 522. Первая часть 508 включает SSRT_A 516 записи, которые ссылаются на каждый узел, имеющий различные адреса, которые могут быть описаны в блоке A 524. Вторая часть 510 включает SSRT_B записи 518, которые ссылаются на каждый узел, имеющий адреса, которые соответствуют один другому, для адресного блока A. Вторая часть 510, однако, ссылается на каждый узел, имеющий соответственно другой адрес, который может быть описан в блоке B 524. Другими словами, все записи в SSRT_B 518 имеют соответствующий блок A, который соответствует один другому, но имеет другой блок B. Аналогично третья часть 512 включает SSRT_C записи 520, которые ссылаются на каждый узел, имеющий соответствующие блоки адреса А и B, которые соответствуют один другому. Третья часть 512, однако, ссылается на каждый узел, имеющий каждый из отличных адресов, которые могут быть описаны в блоке C. Поэтому все записи в SSRT_C 520 имеют соответствующие блоки соответствия А и B, но другой блок C. Наконец, четвертая часть 514 включает SSRT_D записи 522, которые ссылаются на каждый узел, имеющий соответствующие блокам адреса A, B и C. Четвертая часть 514, однако, ссылается на каждый узел, имеющий один из отличных адресов, которые могут быть описаны в блоке D. Таким образом, все записи в SSRT_D 518 имеют блоки соответствия A, B, и C, но другой блок D, который обеспечивает «один переход», направляющий на соответствующий узел. Таким образом, каждый SSRT, который поддерживается соответствующими узлами, может обеспечить описание различной иерархии узлов, имеющих подобные адреса для обеспечения эффективной маршрутизации в одноранговой сети.

SSRT 504, например, может использоваться для нахождения определенного ресурса, исследуя SSRT 504, используя ключ 502 поиска. Если блоки А 524, B 526, C 528, и D 530 из ключа 502 поиска совпадают с соответствующими блоками A, B, C и D, описанный в SSRT_D записях 522 таблицы SSRT 504, SSRT 504 может использоваться для направления запроса непосредственно к соответствующему исходному узлу 506, то есть на один переход.

В другом примере, если блоки А и B 524, 526 ключа 502 поиска совпадают с блоками А и B SSRT 504, а блок C нет, то ключ 502 поиска сравнивается с SSRT_C 520 для перехода к соответствующему узлу, который описывает узлы, имеющие соответствующие блоки A, B и C. Соответствующий узел может тогда иметь SSRT, имеющую четвертую часть, которая может использоваться в одном переходе для определения местонахождения исходного узла 506. Подобные поиски могут быть выполнены, используя первые и вторые части 508, 510, основываясь на том, сколько из ключа поиска соответствует записям в SSRT 504. Таким образом, каждый узел включает SSRT, которая может использоваться для быстрого определения местонахождения узла в ультрабольшой системе.

Фиг. 6 является иллюстрацией примерного осуществления 600 показанной маршрутизации, выполняемой, используя SSRT таблицу фиг.6, которая расположена на каждом узле системы 100 из фиг.1. Как описывалось ранее относительно фиг.4, SSRT может быть создана из множества колец, которые ссылаются на местонахождение каждого узла в одноранговой сети, с помощью вращения идентификатора каждого узла. Например, ring_A 602 может иметь SSRT_A 604, имеющей множество записей. В этом примере каждая запись в SSRT_A 604 имеет три начальных блока (которые иллюстрированы на фиг.6 как «N|O|P»), которые соответствуют один другому. Четвертый блок «A» в SSRT_A 604 описывает каждое местоположение в системе, имеющей соответствующий адрес для этого четвертого блока. Для создания записи для SSRT_A 604 идентификатор, то есть адрес узла в одноранговой сети, «вращается». Например, адрес 606 «110|∙∙∙ N|O|P|» вращается 608 для формирования идентификатор ID 610 «N|O|P|110|∙∙∙», который включен в SSRT_A 604. Этим способом может быть создана SSRT, что уменьшает количество переходов, которые выполняются для определения местонахождения желаемого ресурса в ультрабольшой системе.

Эффективность маршрутизации

В вышеупомянутом описанном осуществлении разрешающая способность маршрутизация в высоких блоках требует немного более чем один переход для каждого блока, исключая адресат, который находится в пределах диапазона, охваченного самыми короткими десятью направлениями. Например, рассмотрим систему с одним триллионом узлов, как показано на фиг.5. Когда узел x начинает поиск, ключ адресата k является случайным. Пусть addr_A (k) будет блоком k (то есть десять наиболее значимых битов), поэтому addr_A (k) имеет 2¹⁰ возможных значений. Как описывалось ранее, 1 Кбайтные SSRT_A(x) записи являются узлами, идентификаторы которых совместно используют последние три блока ID(x), но другой блок A. Поскольку ID узла случаен, не гарантируется, что «A» блоки записей SSRT_A(x) также содержат 2¹⁰ возможных значений addr_A(k).

Вышеупомянутая описанная проблема эквивалентна делению полного ресурсного пространства приблизительно на одну тысячу лотков, и затем узлы в SSRT_A(x) так же, как и сам x, являются шарами, беспорядочно брошенными в эти лотки. Поиск в блоке A может быть решен с одним переходом, если и только если лоток, индексированный addr_A(k), не пуст, как показано на фиг.6. Точно так же, если пространство разделено на 512 лотков, и addr