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

Формула изобретения

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

получают в узле широковещательную индикацию относительно изменения в членстве в одноранговой сети другого узла; и

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

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

поддерживают таблицу leafset посредством периодического зондирования по меньшей мере одного другого узла; и

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

2. Способ по п.1, содержащий дополнительные этапы, на которых:

передают широковещательное уведомление, которое:

описывает изменение; и

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

3. Способ по п.1, в котором индикация является событием присоединения или ухода относительно другого указанного узла в одноранговой сети.

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

5. Способ по п.1, в котором таблица маршрутизации не делает ссылку на, по меньшей мере, другой указанный узел из множества узлов.

6. Способ по п.1, в котором широковещательная передача выполняется, когда будет достигнуто предопределенное время рассылки.

7. Способ по п.1, в котором каждый указанный узел обеспечивается компьютерным устройством.

8. Способ по п.1, в котором индикация является событием ухода или присоединения.

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

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

11. Способ по п.1, содержащий дополнительные этапы, на которых:

определяют, на узле для включения в одноранговую сеть, доступные ресурсы узла для того, чтобы поддерживать связь в одноранговой сети; и

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

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

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

14. Способ по п.11, в котором определение выполнено, когда узел, для которого доступные ресурсы были определены, присоединяется к одноранговой сети.

15. Способ по п.11, в котором определение выполняется с периодическими интервалами, когда узел, для которого доступные ресурсы были определены, является членом одноранговой сети.

16. Способ по п.11, в котором:

определение дополнительно включает в себя определение доступных ресурсов, по меньшей мере, другого указанного узла в одноранговой сети; и

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

17. Способ по п.1, содержащий дополнительные этапы, на которых:

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

формируют коммуникации для передачи сжатых данных к другому указанному узлу.

18. Способ по п.17, дополнительно включающий в себя передачу итерационного фильтра Блюма другому указанному узлу.

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

20. Компьютерочитаемый носитель, содержащий исполняемые компьютером команды, которые при исполнении компьютером предписывают компьютеру исполнять способ по любому из пп.1-19.

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

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

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

каждый указанный узел включает в себя таблицу маршрутизации программных состояний (SSRT), имеющих множество записей SSRT, которые ссылаются на набор указанных узлов, таблицу leafset, которая определяет хеш-пространство для ресурсов, обеспеченных в одноранговой сети, таблицу направлений, имеющую множество записей таблицы направлений, при этом каждая из указанных записей таблицы направлений ссылается на последовательные дополнительные узлы посредством нижеследующей логарифмической функции, при этом последовательные дополнительные узлы обнаружены посредством инверсии бита идентификатора узла для нахождения последовательного узла идентификатора и затем указания на последовательный узел, имеющий последовательный узел идентификатора, и при этом логарифмическая функция является префиксом алгоритма маршрутизации вида log(N), где N - общее количество узлов в одноранговой сети; и

каждая указанная запись SSRT ссылается на соответствующий указанный узел из набора указанных узлов; и

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

24. Система по п.23, в которой индикация является событием ухода или присоединения.

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

26. Система по п.23, в которой узел дополнительно включает в себя процессор; и

память, сконфигурированную для обслуживания:

таблицы leafset, которая определяет хеш-пространство для ресурсов, предоставленных в одноранговой сети;

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

SSRT-записи, каждая из которых ссылается на соответствующий указанный узел; первую группировку записей SSRT, имеющих первый указанный блок, которые соответствуют один другому; и

вторую группировку записей SSRT, имеющих:

соответствующий первый указанный блок; и

второй указанный блок, которые соответствуют друг другу.

27. Система по п.26, в которой:

таблица leafset и таблица направлений сконфигурированы с возможностью модификации с помощью зондирования; и

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

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

29. Система по п.26, в которой множество записей SSRT в SSRT определяется на основании доступных ресурсов узла.

30. Система по п.26, в которой множество записей SSRT в SSRT определяется на основании доступных ресурсов узла по сравнению с другими указанными узлами в одноранговой сети.

31. Система по п.23, в которой узел дополнительно включает в себя процессор; и

память, сконфигурированную для обслуживания:

таблицы маршрутизации программных состояний (SSRT), имеющей записи SSRT, каждая из которых ссылается на соответствующий указанный узел; и

итерационный фильтр Блюма для сжатия записей SSRT для передачи другому указанному узлу.

32. Система по п.31, в которой итерационный фильтр Блюма включает в себя множество фильтров Блюма.

Описание изобретения к патенту

Данная заявка испрашивает приоритет под 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_bN )) в предыдущих технологиях больше не является адекватными для ультрабольших систем. Например, когда число узлов «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_bN) пересылок с очень большим 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_A(k) указывает на лоток, который не пуст, тогда девять наиболее значимых битов могут быть решены, используя SSRT_A(x), оставляя еще один переход для решения использования обычного «направления» из таблицы направлений перед началом использования SSRT_B другого узла.

Пусть P_i будет вероятностью того, что по меньшей мере i битов могут быть решены. Чтобы вычислять P_b, пространство разделяется на 2ⁱ лотков и 2¹⁰ шаров вбрасываются в пространство. 1-P_i является таким образом (1-2^-i)¹⁰²⁴, другими словами, может быть случайно выбран лоток, в котором не найдены никакие шары и который может быть приблизительно e^{-2^(10-i)} , так что P_i=1-e^{-2^(10-i)} .

В этой точке может быть рассчитано ожидаемое число переходов. Пусть p_i=P_i -P_i+1 для i 9, где p_i - вероятность того, что точно i битов решено, используя SSRT_A. Может быть получено следующее:

H=1·p₉ +2·p₈+3·p₇

=1·(p₉ -p₁₀)+2·(p₈-p ₉)+3·(p₇-p₈)

=e^-1+e^-2 +e^-4

=0,52

Поэтому решение блока A (или любой из других блоков кроме самого последнего блока, который занимает один переход) занимает в среднем 1,52 перехода. Таким образом, если N равно одному триллиону, усредненная маршрутизация занимает приблизительно 5,5 переходов.

Эффективность была описана со ссылкой на систему с одним триллионом узлов. Вообще, средняя эффективность ограничена ·1,52+1. Поэтому, если N=256000, эффективность самого плохого случая - 2,02 вместо 2,52 с высокой вероятностью. Например, SSRT_A может просто разрешить 8 битов с ожидаемым счетчиком переходов 1,02. В этой точке полная перемычка, сформированная с оставшимися десятью направлениями, предоставит заключительный переход. Точно так же, если N=256 миллионов, эффективность будет в границе 3,54 перехода с высокой вероятностью.

Стоимость обслуживания и ошибкоустойчивость

Как описывалось ранее, общая стоимость поддержки одной тысячи узлов регионального кластера в одном кольце с коэффициентом смешивания =1/(3 часа) равна приблизительно 1 килобайту в секунду. Поддержание SSRT четырех колец использует приблизительно в четыре раза большую стоимость. Таким образом, каждый узел будет потреблять всего 4 kb/s для обслуживания SSRT. Другие затраты включают периодическое зондирование среди leafset членов и направлений всех четырех колец, которое имеет, в сравнении, относительно маленькую стоимость. Необходимо отметить, что это дает среднюю маршрутизацию в одном триллионе систем узла в 5,5 переходов.

Адаптация

С пиками в потреблении пропускной способности можно все же столкнуться, даже когда среднее потребление пропускной способности, описанное в предыдущих примерных технологиях маршрутизации, соответствует бюджету пропускной способности Q. Поэтому, как описывалось ранее относительно фиг.2, события могут быть буферизированы внутри очереди 208(x) из фиг.2, до тех пор пока дополнительная пропускная способность не становится доступной. Другие различные технологии адаптации также могут использоваться для управления качеством SSRT, когда происходят динамические изменения в системе. Например, могут использоваться технологии адаптации для постепенной деградации эффективности маршрутизации при увеличении нагрузки и возвращения впоследствии к нормальному состоянию маршрутизации.

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

Примерная вторая технология такой адаптации полагается на первую технологию адаптации, где SSRT становится перемычкой, охватывающей часть полного ресурсного пространства, как показано относительно фиг.3. Первая и вторая технология адаптации могут быть объединены для формирования SSRT, включенной в каждый узел так, что при объединении SSRT каждого из узлов получается многоуровневая архитектура, объединяющая эти две оптимизации. Например, может использоваться двухуровневая архитектура, где первый уровень охватывает полное ресурсное пространство и второй уровень обеспечивает региональные перемычки. В другом примере может использоваться четырехуровневая архитектура, как описывалось для фиг.5. С этим гибридным подходом O(1) может быть достигнуто для системы, имеющей большое число узлов, и все-таки без превышения бюджета пропускной способности Q.

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

Для достижения этой цели фильтрация может использовать разнообразные правила, примеры которых показаны ниже:

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

2. Если событие не собирается изменять состояние, оно не размножается.

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

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

Согласование набора

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

SSRT, например, может быть сохранено в стабильном хранилище при фоновой работе, и его список членства (например, записи, имеющие пару <ID, IP> всех других узлов) включает то, что узел узнал везде в своей прошлой истории. Узел, который является полностью новым для системы, может скопировать SSRT во время своего первого присоединения. Поэтому, когда система работает в течение достаточного периода времени, набор списка членства в SSRT будет вообще непротиворечив для всей системы.

Когда ранее ушедший узел возвращается в одноранговую сеть (например, присоединяется к одноранговой сети), присоединяющийся узел, однако, не может знать о состоянии других узлов, зарегистрированных в его соответствующей SSRT. Поэтому присоединяющийся узел может сбросить каждую из записей в SSRT к состоянию автономных и затем пробовать обучиться от одного или более существующих узлов в одноранговой сети. Например, если SSRTs этих двух узлов синхронизированы друг с другом, существующий узел может послать вектор с каждым битом вектора, представляющего состояние других узлов от SSRT существующего узла. Когда коэффициент смешивания , высок, и число записей в активном состоянии мало, например, практически осуществляется копирование eSSRT. Например, может потребоваться приблизительно восемь секунд для передачи записей приблизительно в 4 КБ, каждая имеющая 32 байта по связи 128 kb/s. Однако это не может быть устойчивым решением, когда коэффициент смешивания мал или в ультрабольшой системе.

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

В фильтре Блюма, например, список n элементов может быть сжат в m битов, то есть b=m/n на элемент, в котором «b» представляет «параметр фильтра». Для каждого элемента применяется набор хеш-функций, диапазон которых относится к [0.. m], и устанавливает соответствующий бит в m-битовый вектор. Побочным эффектом фильтра Блюма является то, что может произойти положительная ошибка, то есть узел получения может ошибочно включить некоторые элементы, которые лежат вне первоначального списка. Такая вероятность показывает (0,6185)^b, и если m=8n, тогда вероятность является не более чем 0.02.

Если размер элемента - E байтов, то вместо того, чтобы посылать список из nE байтов, с размером фильтра при b=8, равным 8n бит (то есть n байт), результирующее отношение сжатия 1/E. Например, чтобы передать идентификатор узла ID и адрес IP, но не временную метку, E может быть равно приблизительно 32 байтам, и таким образом результирующий 1/32 коэффициент сжатия значителен. В осуществлении первый протокол применяет фильтр Блюма по записям, которые не являются подключенными к сети. Положительная ошибка фильтра Блюма тогда подразумевала бы, что 2% сетевых узлов зарегистрированы как автономные в конце получения.

Точность может быть дополнительно улучшена в другом осуществлении, используя «итерационный фильтр Блюма». Например, посылающий узел, то есть узел, который отправляет данные, для модификации SSRT узла получения сначала вычисляет фильтр сетевых узлов P(PRESENT) с малым параметром фильтра a. Посылающий узел тогда идентифицирует набор положительно ошибочных узлов , и применяет фильтр добавления с параметром фильтра b. Оба фильтра тогда посылают получающему узлу, то есть узлу, запрашивающему данные для обновления SSRT. Говоря о качестве, это приводит к консервативному подходу, потому что некоторые из сетевых узлов будут пропущены. Говоря о статистике, число таких записей то же самое, что и для одноуровневого фильтра Блюма, потому что норма ошибки фильтра Блюма зависит только от параметра фильтра.

Примерный итерационный фильтр 700 Блюма изображен на фиг.7. Итерационный фильтр 700 Блюма изображен, как включающий набор трех фильтров 702(1)-702(3) Блюма. P 704 и А 706 являются набором ошибочно-положительных записей для каждого фильтра.

Для вычисления, приведет ли итерационный подход к сохранению пропускной способности, положим N_a и N_p как число автономных и сетевых узлов соответственно. Для одноуровневого b-битового фильтра Блюма полный размер сообщения - bN_a бит. Первый фильтр итерационного метода имеет сообщение размера aN_p. Размер A, то есть число ошибочно-положительных записей, является N_a(0,6185)^a . Поэтому фильтр добавления имеет размер N_a b(0,6185)^a, возвращающее полный размер S сообщения, который может быть представлен следующим образом:

S=N_ab(0,6185) ^a+ aN_p

Чтобы получить минимальный размер сообщения, вычислим следующее:

Поскольку «a» - неотрицательное целое число, уравнение может быть разложено на два следующих:

В вышеупомянутом примерном осуществлении, когда параметр фильтра b равен восьми и для случаев, когда N_a является меньшим, чем 25% N_p , может быть применен одноуровневый фильтр Блюма. Примерный псевдокод для этого показан следующим образом:

OnSetReconcileRequest()
Np=SSRT.OnlineSet.Size
Na=SSRT.OfflineSet.Size
If (Np<0,4805·N a·b)
a=log(Np/(0,4805· Na·b))/log(0,6185)
F1=BloomFilterPack(SSRT.OnlineSet, a )
P=BloomFilterUnpack(SSRT,F1)
A=P-SSRT.OnlineSet
F2=BloomFilterPack(A, b)
Send(F1, F2);
else
F1=BloomFilterPack(SSRT.OfflineSet, b )
Send(F1, 0)
OnSetReconcileAck(F1, F2)
foreach(entry SSRT)
if InBloomFilter(entry, F1)
ifF2==0 or not InBloomFilter(entry , F2)
entry.status=online

В вышеупомянутом псевдокоде согласования набора b предопределено (например, 8), и записи SSRT при получении заканчивают все начатые с состоянием автономно.

Иллюстративные Процедуры

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

Фиг.8 является блок-схемой, иллюстрирующей процедуру 800 в примерном осуществлении, в котором узел формирует и передает уведомление, которое описывает события, полученные этим узлом, которые указывают на изменение в членстве в одноранговой сети. В блоке 802 узел получает событие, указывающее на изменение в членстве в одноранговой сети. Например, первый узел может выбрать случайный идентификатор ID и провести поиск для определения того, включен ли уже этот идентификатор в одноранговую сеть. Об идентификаторе можно думать как об адресе первого узла в одноранговой сети. Если идентификатор ID еще не включен в одноранговую сеть, первый узел тогда может определить местонахождение узла «преемника», имеющего следующий самый высокий идентификатор, обозначенный как ID', и уведомлять узел преемника, что первый узел присоединился к одноранговой сети. Уведомление может быть выполнено передачей события «присоединение» узлу преемника.

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

Если узел ранее не получал событие (блок 804), то в решающем блоке 808 определяется, был ли превышен порог для передачи событий другим узлам. Если порог был превышен (блок 808), то событие добавляется к очереди (блок 810). Таким образом процедура 800 может управлять затратами на обслуживание в одноранговой сети, сообщая не более чем предопределенное число событий за данный период времени.

Если порог не был превышен (блок 808) или после того, как событие добавляется к очереди (блок 810), в решающем блоке 812 определяется, было ли предопределенное время широковещательной рассылки достигнуто. Например, каждый узел в одноранговой сети может разослать события, полученные этим узлом, с различными предопределенными интервалами для «расширения» стоимости в сетевых ресурсах, которые используются для передачи событий. Если предопределенное время широковещательной рассылки не было достигнуто (блок 812), процедура 800 возвращается к блоку 802 для того, чтобы получить дополнительные события, если они есть.

Когда предопределенное время широковещательной рассылки для этого узла было достигнуто (блок 812), формируется уведомление, которое включает события. Например, узел может объединить события, полученные от множества узлов так, чтобы использовать одну передачу для отправки имеющихся событий. Событие может быть получено от очереди событий, которая была сохранена в блоке 810 и/или от другого хранилища, которое использовалась для хранения событий, полученных узлом.

В блоке 816 исследуется таблица маршрутизации для определения того, где уведомление будет передаваться. В блоке 818 уведомление передается параллельно каждому узлу, который упоминается в таблице маршрутизации. Таблица маршрутизации и рассылка в соответствующих блоках 816, 818 могут быть выполнены разными способами. Например, таблица маршрутизации может быть сконфигурирована как таблица 114 направлений из фиг.1, которая использует логарифмическую функцию для описания множества других узлов. Таблица 114 направлений может быть модифицирована с помощью зондирования узлов, соответствующих записям. Как описывалось ранее, «направления» таблицы 114 направлений из фиг.1 формируют граф рассылки с такой адекватной избыточностью, что уведомление будет передано узлам в той области, в которой узел постоянно находится. В другом осуществлении также могут использоваться направления для рассылки уведомлений другим узлам, которые лежат вне области.

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

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

Фиг.9 является блок-схемой, изображающей процедуру 900 в примерном осуществлении, в котором размер таблицы маршрутизации динамически определяется, основываясь на доступных ресурсах узла. В некотором осуществлении одноранговой сети каждый из узлов сети может не иметь доступ к эквивалентным аппаратным средствам, программному обеспечению, и/или сетевым ресурсам. Например, как показано на фиг.1, компьютерное устройство 104(B) может иметь существенное количество аппаратных и программных ресурсов, в то время как компьютерное устройство 104(1), возможно, ограниченно по аппаратным и программным ресурсам, потому что компьютерное устройство 104(1) предназначено быть мобильным. Дополнительно узлы могут иметь различные пропускные способности для соединения с сетью, например, один узел может использовать подключение по модемной связи, в то время как другой узел может использовать цифровую абонентскую линию (DSL). Таблицы маршрутизации каждого из этих узлов могут быть динамически сконфигурированы, основываясь на доступных ресурсах узла так, чтобы узел был сконфигурирован для обработки маршрутизации в одноранговой сети тем способом, который является совместимым с доступными ему ресурсами.

В блоке 902, например, узел присоединяется к одноранговой сети. Узел, например, может сгенерировать случайный идентификатор, как описывалось ранее. В блоке 904 узел определяет свои доступные аппаратные средства, программное обеспечение и/или сетевые ресурсы. Например, узел может выполнить программный модуль, который производит определение возможности узла по памяти и ресурсу обработки. Программный модуль после выполнения может также определить доступную пропускную способность сетевого подключения, определяя, например, время, которое требуется для получения ответа от известного сетевого адресата, и так далее.

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

В другом примере программный модуль может сравнивать доступные аппаратные средства, программное обеспечение и/или сетевые ресурсы узла с другими узлами в сети для того, чтобы достигнуть такого размера таблицы маршрутизации, который находится в соответствии с другими размерами таблицы маршрутизации в одноранговой сети. Например, когда узел присоединяется к одноранговой сети, узел может определить местонахождение узла преемника, как описывалось ранее. После локализации узел может сделать запрос к узлу преемника, чтобы определить размер таблицы маршрутизации, который был создан, основываясь на аппаратных средствах, программном обеспечении и/или сетевых ресурсах узла преемника. Узел может тогда сравнить свои доступные ресурсы с таковыми из узла преемника и сконфигурировать таблицу маршрутизации так, чтобы иметь число записей, основываясь на сравнении. Например, если узел имеет больше ресурсов, чем узел преемника, то узел может сконфигурировать таблицу маршрутизации так, чтобы иметь больше записей, чем таблица маршрутизации узла преемника. Могут использоваться различные алгоритмы для сравнения ресурсов и конфигурации таблиц маршрутизации соответственно.

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

Примерное компьютерное устройство

Различные компоненты и функциональные возможности, описанные здесь, осуществляются на множестве отдельных компьютеров. Фиг.10 показывает компоненты типичного примера компьютерной среды 1000, включая компьютер, обозначенный ссылочной позицией 1002, что является подходящим для установки узла в одноранговой сети. Компьютер 1002 может быть тем же самым или отличным от множества клиентов 102(a) и множества компьютерных устройств 104(1)-104(B) фиг.1. Компоненты, показанные на фиг.10, являются только примерами и не предназначены для любых ограничений относительно объема функциональных возможностей изобретения; изобретение не обязательно зависит от особенностей, показанных на фиг.10.

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

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

Команды и/или программные компоненты сохраняются в разное время на различных читаемых компьютером носителях, которые или являются частью компьютера, или могут читаться компьютером. Программы обычно распространяются, например, на гибких дисках, CD-ROM, DVD или на некой форме коммуникационных носителей, например модулируемого сигнала. Оттуда они устанавливаются или загружаются во вторичную память компьютера. При исполнении они загружаются, по меньшей мере, частично в первичную электронную память компьютера.

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

Обратимся к фиг.10, где компоненты компьютера 1002 могут включать, но не ограничены этим, процессорный модуль 1004, системную память 1006 и системную шину 1008, которая соединяет различные системные компоненты, включая системную память, с процессорным модулем 1004. Системная шина 1008 может быть любой из нескольких типов шинных структур, включая шину памяти или контроллер памяти, периферийную шину и локальную шину, использующие любую из разнообразия шинных архитектур.

Компьютер 1002 обычно включает разнообразные читаемые компьютером носители. Читаемые компьютером носители могут быть любыми доступными носителями, к которым можно обратиться компьютером 1002, и включают энергозависимые и энергонезависимые носители, сменные и несменные носители. В качестве примера, но не ограничения читаемые компьютером носители могут включать компьютерные носители данных и коммуникационные носители. «Компьютерные носители данных» включают энергозависимые и энергонезависимые, сменные и несменные носители, осуществляющие любой способ или технологию для хранения информации, например читаемых компьютером команд, структур данных, программных модулей или других данных. Компьютерные носители данных включают, но не ограничены этим, оперативную память RAM, постоянную память ROM, электронно-перепрограммируемую постоянную память EEPROM, флэш-память или другую технологию памяти, CD-ROM, цифровые видеодиски (DVD) или другую оптическую память на диске, магнитные кассеты, магнитную ленту, магнитную память на диске или другие магнитные запоминающие устройства, или любой другой носитель информации, который может использоваться для хранения желаемой информации и к которой можно обратиться компьютером 1002. Коммуникационные носители обычно воплощают читаемые компьютером команды, структуры данных, программные модули или другие данные в модулируемом сигнале данных, например несущей или другом транспортном механизме, и включают любые информационные носители для доставки информации. Термин «модулированный сигнал данных» означает сигнал, который имеет одну или более своих характеристик установленных или измененных таким способом, чтобы кодировать информацию в сигнале. В качестве примера, но не ограничения, коммуникационные носители включают проводные носители типа проводной сети или прямого проводного подключения, и беспроводных носителей типа акустического, радиочастотного, инфракрасного и других беспроводных носителей. Комбинации любого из вышеупомянутого может также быть включены в читаемые компьютером носители.

Системная память 1006 включает компьютерные носители данных в форме энергозависимой и/или энергонезависимой памяти типа постоянного запоминающего устройства 1010 (ROM) и оперативной памяти 1012 (RAM). Базовая система 1014 ввода-вывода (BIOS) содержит основные подпрограммы, которые помогают передавать информацию между элементами в пределах компьютера 1002, например во время запуска, и обычно сохраняется в ROM 1010. Оперативная память 1012 обычно содержит данные и/или программные компоненты, которые являются непосредственно доступными и/или могут быть обработаны процессорным модулем 1004. В качестве примера, но не ограничения, фиг.10 иллюстрирует операционную систему 1016, приложения 1018, программные компоненты 1020 и программные данные 1022.

Компьютер 1002 может также включать другие извлекаемые/неизвлекаемые, энергозависимые/энергонезависимые компьютерные носители данных. Только в качестве примера фиг.10 иллюстрирует жесткий диск 1024, который читает или пишет на несменные, энергонезависимые магнитные носители, дисковод 1026 магнитных дисков, который читает или пишет на сменный, энергонезависимый магнитный диск 1028, и оптический дисковод 1030, который читает или пишет на сменный, энергонезависимый оптический диск 1032 типа CD-ROM или другие оптические носители. Другие извлекаемые/неизвлекаемые, энергозависимые/ энергонезависимые компьютерные носители данных, которые могут использоваться в примерной среде, включают, но не ограничены этим, кассеты магнитной ленты, платы флэш-памяти, цифровые универсальные диски, цифровую видеоленту, твердотельную оперативную память, твердотельный ROM и т.п. Жесткий диск 1024 обычно подключается к системной шине 1008 через интерфейс несменной памяти, например носители данных связывают с помощью интерфейса 1034, и магнитный дисковод 1026, и оптический дисковод 1030 обычно подключаются к системной шине 1008 с помощью интерфейса сменной памяти.

Диски и их соответствующие компьютерные носители данных, обсужденные выше и проиллюстрированные на фиг.10, обеспечивают хранение читаемых компьютером команд, структур данных, программных компонентов и других данных для компьютера 1002. На фиг.10, например, жесткий диск 1024 проиллюстрирован как хранилище операционной системы 1016', приложения 1018', программных компонент 1020' и программных данных 1022'. Обратите внимание, что эти компоненты могут или быть теме же самыми или отличными от операционной системы 1016, приложения 1018, программных компонент 1020 и программных данных 1022. Операционная система 1016', приложения 1018', программные компоненты 1020' и программные данные 1022' имеют здесь различные номера для иллюстрации того, что они, как минимум, являются различными копиями. Пользователь может ввести команды и информацию в компьютер 1002 через устройства ввода данных типа клавиатуры 1036 и устройства позиционирования (не показанные здесь), обычно называемые мышью, координатным шаром или сенсорной клавиатурой. Другие устройства ввода данных могут включать устройства источников (типа микрофона 1038 или камеры 1040, которые предоставляют поток данные), джойстик, игровую клавиатуру, спутниковую антенну, сканер или подобные им. Эти и другие устройства ввода данных часто подключаются к процессорному модулю 1002 через интерфейс 1042 ввода - вывода (I/O), который соединен с системной шиной, но может быть связан с помощью другого интерфейса и шинных структур, например параллельного порта, игрового порта или универсальной последовательной шины (USB). Монитор 1044 или другой тип устройства отображения также связан с системной шиной 1008 через интерфейс типа видеоадаптера 1046. В дополнение к монитору 1044 компьютеры могут также включить другие устройства визуализации (например, динамики) и один или более принтеров, которые могут быть связаны через интерфейс 1042 I/O.

Компьютер может работать в сетевой среде, используя логические подключения к одному или более удаленных компьютеров, например удаленному устройству 1050. Удаленное устройство 1050 может быть персональным компьютером, готовым к использованию в сети устройством, сервером, маршрутизатором, сетевым PC, одноранговым устройством или другим обычным сетевым узлом и обычно включает многие или все элементы, описанные выше по отношению к компьютеру 1002. Логические подключения, изображенные на фиг.10, включают местную локальную сеть 1052 (LAN) и глобальную сеть 1054 (WAN). Хотя глобальная сеть 1054, показанная на фиг.10, является сетью Internet, глобальная сеть 1054 может также включать другие сети. Такие сетевые среды являются обычными в офисах, компьютерных сетях масштаба предприятия, интранет и т.п.

При использовании в среде работы с сетями LAN компьютер 1002 связан с LAN 1052 через сетевой интерфейс или адаптер 1056. При использовании в среде работы с WAN компьютер 1002 обычно включает модем 1058, или другие средства для установления связи через Internet 1054. Модем 1058 который может быть внутренним или внешним, может быть связан с системной шиной 1008 через интерфейса 1042 I/O или другой соответствующий механизм. В сетевой среде программные модули, изображенные по отношению к компьютеру 1002 или его частям, могут сохранятся в удаленном устройстве 1050. В качестве примера, но не ограничения фиг.10 иллюстрирует удаленные программные компоненты 1060, постоянно находящиеся на удаленном устройстве 1050. Необходимо оценить, что показанные сетевые подключения являются образцовыми и могут использовать другие средства установления связи между компьютерами.

Заключение

Хотя изобретение было описано на языке, определенном по своим структурным особенностям и/или методологическим действиям, необходимо понимать, что изобретение, определенное в прилагаемой формуле изобретения, не обязательно ограничено определенными особенностями или описанными действиями. Скорее определенные особенности и действия раскрыты как примерные формы осуществления данного изобретения.