ВЗАИМОДЕЙСТВИЕ МЕЖДУ СОСЕДСТВАМИ В РАМКАХ ОБЪЕДИНЕНИЯ ПО МЕХАНИЗМУ РАНДЕВУ Российский патент 2011 года по МПК G06F15/173 H04L12/28 

Уровень техники

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

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

Поэтому для вычислительных систем были разработаны различные механизмы (например, Система Именования Доменов ("DNS" - Domain Name System), Active Directory (AD), Распределенные Файловые Системы ("DFS" - Distributed File Systems)) для идентификации заранее неизвестных ресурсов (и организации к ним доступа). Однако, вследствие большого количества и разнообразия ресурсов (например, устройств и услуг), которые доступны через разные вычислительные сети, разработчикам часто приходится разрабатывать приложения, которые реализуют различные механизмы идентификации ресурса и организации доступа. Каждый особый механизм может иметь разные требования к кодированию и может не предоставлять разработчику всех функциональных средств, которые необходимы для приложения.

Например, хотя DNS имеет распределенную архитектуру администрирования (т.е. централизованное управление не требуется), DNS не обеспечивает достаточной динамической, самоорганизующейся поддержки нестойкой модели данных и запросов и имеет фиксированный набор корневых объектов. С другой стороны, AD является достаточно динамическим, но для него требуется централизованное администрирование. Более того, аспекты различных механизмов могут быть несовместимы друг с другом. Например, ресурс, идентифицируемый с использованием DNS, может быть несовместим с протоколами маршрутизации DFS. Таким образом, разработчик может быть вынужден выбирать наиболее подходящий механизм и отказываться от преимуществ других механизмов.

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

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

По меньшей мере, один из этих механизмов использует локальные многоуровневые карты соседних элементов на каждом узле в сети для маршрутизации сообщения к узлу назначения. Это по существу приводит к архитектуре, где каждый узел является "корневым узлом" соответствующего дерева узлов (узлов в его карте соседей). Сообщения пошагово маршрутизируются к идентификатору назначения разряд за разрядом (например, ***6=> **46=>, *346=> 2346, где * отражает групповые символы). Эффективность маршрутизации механизмов такого типа равна O(log N) переходов маршрутизации, и требуются узлы для сохранения таблицы маршрутизации размера O(log N).

По меньшей мере, один другой из этих механизмов присваивает узлам уникальный идентификатор (ID), который берется из линейного кольца чисел. Узлы сохраняют таблицы маршрутизации, которые содержат указатели на непосредственно следующий за ними узел (согласно значению идентификатора), и на те узлы, чьи значения идентификаторов представляют собой ближайший последующий элемент относительно значения ID + 2^L. Эффективность маршрутизации механизмов такого типа также равна O(log N) переходов маршрутизации, и требуются узлы для сохранения таблицы маршрутизации размера O(log N).

По меньшей мере, одному из дополнительных механизмов необходимо O(log N^1/d) переходов маршрутизации, и требуются узлы для сохранения таблицы маршрутизации размера O(D). Таким образом, эффективность маршрутизации всех этих механизмов зависит, по меньшей мере частично, от количества узлов в системе.

Дополнительно, так как идентификаторы (по меньшей мере, для некоторых из механизмов) могут быть равномерно распределены по кольцу, всегда есть некоторая вероятность того, что маршрутизация между узлами на кольце приведет к некоторой неэффективности. Например, переходы маршрутизации могут преодолевать обширные географические расстояния, переправляться через более дорогостоящие каналы передачи данных или проходить через небезопасные области и т.д. К тому же, когда маршрутизация сообщения задействует множественные переходы, есть некоторый шанс, что подобные события будут происходить неоднократно. К сожалению, эти механизмы не принимают во внимание соседство узлов (физическое или в ином смысле) по отношению друг к другу. Например, в зависимости от распределения узлов на кольце маршрутизация сообщения от Нью-Йорка до Бостона может задействовать маршрутизацию сообщения от Нью-Йорка до Лондона, до Атланты, до Токио, а затем до Бостона.

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

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

Раскрытие изобретения

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

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

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

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

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

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

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

Фиг. 1 демонстрирует пример инфраструктуры объединения;

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

Фиг. 3 - иллюстративную двоичную зависимость между узлами в инфраструктуре объединения в виде сортированного списка и соответствующего кольца;

Фиг. 4 - иллюстративное кольцо из колец, которое способствует кратчайшей маршрутизации;

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

Фиг. 5A - иллюстративное порожденное соседством дерево разбиения колец, изображенное на Фиг. 5, с дополнительной детализацией в частях дерева разбиения колец, изображенного на Фиг. 5;

Фиг. 6 - подходящую операционную среду для принципов настоящего изобретения;

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

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

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

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

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

Фиг. 12A - пример узла, устанавливающего принадлежность существующему объединению;

Фиг. 12B - пример узлов в инфраструктуре объединения, обменивающихся сообщениями;

Фиг. 13 - иллюстративную схему последовательности операций способа для установления принадлежности инфраструктуре объединения;

Фиг. 14 - иллюстративную схему последовательности операций способа для сохранения принадлежности инфраструктуре объединения;

Фиг. 15 - иллюстративную схему последовательности операций способа для получения информации живучести для другого узла;

Фиг. 16 - пример модели сообщения и сопутствующей модели обработки;

Фиг. 17 - пример целого ряда обменов информацией живучести, которые могут происходить между функциональным уровнем и прикладным уровнем;

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

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

Фиг. 19B - другое представление иллюстративного порожденного соседством дерева разбиения колец, изображенного на Фиг. 19A;

Фиг. 19C - секционированное представление части иллюстративного порожденного соседством дерева разбиения колец, изображенного на Фиг. 19A;

Фиг. 19D - расширенное представление промежуточного кольца из иллюстративного порожденного соседством дерева разбиения колец, изображенного на Фиг. 19A;

Фиг. 19E - еще одно представление иллюстративного порожденного соседством дерева разбиения колец, изображенного на Фиг. 19A;

Фиг. 19F - дополнительное представление иллюстративного порожденного соседством дерева разбиения колец, изображенного на Фиг. 19A;

Фиг. 19G - расширенное представление части Фиг. 19F;

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

Фиг. 21 - иллюстративную схему последовательности операций для способа отправки информационного сообщения между соседствами в дереве колец;

Фиг. 22 - иллюстративную схему последовательности операций для другого способа отправки информационного сообщения между соседствами в дереве колец.

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

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

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

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

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

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

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

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

Архитектура Объединения

Фиг. 1 демонстрирует пример инфраструктуры 100 объединения. Инфраструктура 100 объединения включает в себя узлы 101, 102, 103, которые могут образовывать различные типы партнерств объединения. Например, узлы 101, 102, 103 могут объединяться друг с другом как равноправные, без корневого узла. Каждый из узлов 101, 102 и 103 имеет соответствующий идентификатор 171, 182 и 193 соответственно.

Как правило, узлы 101, 102, 103 могут использовать протоколы объединения для формирования партнерства и обмена информацией (например, информацией о состоянии, касающейся взаимодействий с другими узлами). Формирование партнерств и обмен информацией способствует более эффективному и надежному доступу к ресурсам. Могут существовать другие промежуточные узлы (не показаны) между узлами 101, 102 и 103 (например, узлы, имеющие значения идентификаторов между 171 и 193). Таким образом, сообщение, маршрутизируемое, например, между узлом 101 и узлом 103, может проходить через один или более других промежуточных узлов.

Узлы в инфраструктуре 100 объединения (включающей в себя другие промежуточные узлы) могут включать в себя соответствующие наборы протоколов рандеву. Например, узлы 101, 102 и 103 включают в себя соответствующие наборы протоколов рандеву 141, 142 и 143 соответственно. Каждый из наборов протоколов 141, 142 и 143 включает в себя прикладной уровень (например, прикладные уровни 121, 122 и 123) и другие нижние уровни (например, соответствующие другие нижние уровни 131, 132 и 133). Каждый уровень в наборе протоколов рандеву отвечает за различные функциональные возможности, связанные с организацией рандеву ресурсного запроса с соответствующим ресурсом.

Например, другие нижние уровни могут включать в себя канальный уровень, уровень маршрутизации и функциональный уровень. Как правило, канальный уровень отвечает за надежный перенос сообщения (например, используя протокол WS-ReliableMessaging (протокол надежной доставки сообщений) и Простой Протокол Доступа к Объектам ("SOAP" - Simple Object Access Protocol)) от одной конечной точки к другой (например, от узла 101 к узлу 103). Канальный уровень также отвечает за обработку заголовков для надежного входящего и исходящего обмена сообщениями и сохранение состояния, соотнесенного с сеансами надежного обмена сообщениями.

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

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

Механизмы Объединения

Узлы могут объединяться, используя ряд различных механизмов. Первый механизм объединения включает в себя равноправные узлы, переправляющие информацию на все другие равноправные узлы. Когда узел должен присоединиться к инфраструктуре объединения, этот узел использует протокол обнаружения широковещательной/многоадресной передачи, такой, например, как протокол WS-Discovery (протокол обнаружения сетевых служб), чтобы объявить о своем присутствии, и вызывает широковещательный/групповой поиск для обнаружения других узлов. Затем этот узел создает простое партнерство эстафетной передачи с другими узлами, уже представленными в сети, и принимает новые партнерства с вновь присоединяющимися узлами. После этого узел просто переправляет все специализированные сообщения на все свои партнерские узлы.

Второй механизм объединения включает в себя равноправные узлы, которые наиболее эффективно передают специализированные сообщения к их назначению(ям). Когда новый узел должен присоединиться к инфраструктуре объединения, этот новый узел использует протокол обнаружения широковещательной/многоадресной передачи, такой, например, как протокол WS-Discovery, чтобы объявить о своем присутствии, и вызывает широковещательный/групповой поиск для обнаружения других узлов, которые являются частью инфраструктуры объединения. При обнаружении другого узла новый узел создает партнерство с этим другим узлом. Благодаря созданному партнерству новый узел узнает о присутствии других узлов, уже составляющих инфраструктуру объединения. Затем он создает партнерства с этими вновь узнанными узлами и принимает любые новые поступающие запросы на создание партнерства.

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

Третий механизм объединения включает в себя равноправные узлы, неявно переправляющие все специализированные сообщения к их назначению(ям). В этом третьем механизме узлам присваиваются идентификаторы, такие, например, как 128-битный или 160-битный идентификатор. Узел, ответственный за сохранение регистрации предназначения в данном специализированном сообщении, может быть определен как узел, чей идентификатор является ближайшим к полученной посредством отображения (например, хеширования) идентификационной информации назначения (например, URI - Uniform Resource Identifier - унифицированный идентификатор ресурса) специализированного сообщения для этого 128-битного или 160-битного пространства идентификаторов.

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

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

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

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

Фиг. 2 демонстрирует пример архитектуры 20 вычислительной системы, которая способствует косвенной маршрутизации запроса к партнерам. Архитектура 200 вычислительной системы иллюстрирует различные типы вычислительных систем, и устройства теоретически рассредоточены по множественным локальным областям обнаружения, составляя инфраструктуру объединения.

Рабочая станция 233 может включать в себя экземпляр зарегистрированного средства доступа с поддержкой технологии PnP (Plug-and-Play - автоматическая настройка компонентов). Чтобы сообщить своим партнерам о присутствии этого экземпляра средства доступа с поддержкой технологии PnP, рабочая станция 233 направляет регистрационный запрос 201 через инфраструктуру объединения. Регистрационный запрос 201 первоначально переправляется на портативный компьютер 231, который в свою очередь переправляет регистрационный запрос 201 программе-посреднику 237 для сообщений, которая в свою очередь переправляет регистрационный запрос 201 на шлюз 241 для сообщений. Шлюз 241 для сообщений сохраняет регистрационный запрос 201 регистрационной информации в своей базе данных и возвращает сообщение 204 об успешном выполнении на рабочую станцию 233.

Следующим шагом, другой экземпляр зарегистрированного средства доступа, на этот раз из действующих услуг, возникает в пределах рабочей станции 233. На этот раз узел осведомлен, что шлюз 241 для сообщений отвечает за регистрацию, и переправляет регистрационный запрос 205 непосредственно на шлюз 241 для сообщений. Шлюз 241 для сообщений сохраняет регистрационный запрос 205 регистрационной информации в своей базе данных и возвращает сообщение 206 об успешном выполнении на рабочую станцию 233.

Следующим шагом, печатающее устройство 236 (например, печатающее устройство с поддержкой технологии UPnP (Universal PnP - Универсальная PnP)) включается и отправляет уведомление 207. Узел 234 обслуживания обнаруживает уведомление 207 и направляет регистрационный запрос 208 программе-посреднику 237 для сообщений. Программа-посредник 237 для сообщений переправляет регистрационный запрос 208 на шлюз 241 для сообщений. Шлюз 241 для сообщений сохраняет регистрационный запрос 208 регистрационной информации в своей базе данных и возвращает сообщение 210 об успешном выполнении на узел 234 обслуживания.

Следующим шагом, персональный компьютер 242 выдает поисковый запрос 211 для обнаружения всех устройств. Поскольку персональный компьютер 242 не знает, куда переправлять поисковый запрос 211, он маршрутизирует поисковый запрос 211 через рабочую станцию 243. Поскольку регистрационный и поисковый запросы направляются к одному и тому же назначению, протокол маршрутизации по существу обеспечивает рандеву между двумя запросами, что приводит к тому, что рабочая станция 243 переправляет поисковый запрос 211 на шлюз 241 для сообщений. Шлюз 241 для сообщений просматривает сохраняемую им регистрационную информацию и переправляет поисковый запрос 211 как на рабочую станцию 233, так и на узел 234 обслуживания. Рабочая станция 233 и узел 234 обслуживания отправляют ответные сообщения 214 и 216 соответственно на персональный компьютер 242.

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

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

Взаимосвязь между Узлами в Объединении

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

Каждому узлу объединения может быть присвоен идентификатор (например, при помощи генератора случайных чисел с парным обнаружением) из установленного набора идентификаторов от 0 до некоторого установленного верхнего предела. Таким образом, добавление 1 к идентификатору установленного верхнего предела дает в результате нулевой идентификатор (т.е. перемещение от конца связанного списка обратно к началу связанного списка). В дополнение, задается функция отображения 1:1 области значений именований узлов на сами узлы.

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

Численная_Маршрутизация(V, Msg): При данном значении V из области значений именований узлов и сообщении "Msg" доставляет сообщение на узел X, чье именование может быть отображено на V при использовании функции отображения.

Окрестность(X, S): Окрестность представляет собой множество узлов по обе стороны от узла X с количеством элементов, равным S.

Когда каждый узел в объединении имеет глобальные сведения о кольце, функция Численная_Маршрутизация(V, Msg) реализуется с помощью непосредственной отправки Msg на узел X, чье именование получено путем применения функции отображения к V. С другой стороны, когда узлы имеют ограниченные сведения о других узлах (например, только о непосредственно примыкающих узлах), функция Численная_Маршрутизация(V, Msg) реализуется посредством переправления сообщения по кольцу на следующие друг за другом узлы, пока оно не достигнет узла X назначения.

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

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

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

В некоторых вариантах осуществления узлам объединения присваивается идентификатор из пространства идентификаторов настолько большого, что шансы того, что двум узлам будет присвоен один и тот же идентификатор, являются очень маловероятными (например, при использовании генерирования случайного числа). Например, узлу может быть присвоен идентификатор в области значений от 0 до bⁿ - 1, где b равняется, например, 8 или 16, а n равняется, например, 128-битному или 160-битному эквиваленту цифр. Соответственно, узлу может быть присвоен идентификатор, например, из области значений от 0 до 16⁴⁰ - 1 (или приблизительно 1,461502E48). Область значений от 0 до 16⁴⁰-1 обеспечила бы, например, достаточное число идентификаторов, чтобы присвоить каждому узлу в сети Интернет уникальный идентификатор.

Таким образом, каждый узел в объединении может иметь:

Идентификатор, который является численным значением, равномерно распределенным в области значений от 0 до bⁿ-1; и

Таблицу маршрутизации, в состав которой входят (все арифметические действия выполняются по модулю bⁿ):

Последующий узел (s);

Предшествующий узел (p);

Узлы Окрестности (p_k, …, p₁, p, s, s₁, …, s_j), такие, что s_j.s.id > (id+u/2), j≥v/2-1, и p_k.p.id<(id-u/2), и k≥v/2-1; и

Узлы маршрутизации (r_-(n-1), …, r_-1, r₁, …, r_n-1) такие, что r_±i = Численная_Маршрутизация(id±bⁱ, Msg),

где b является основанием системы счисления, n является длиной поля в количестве разрядов, u является шириной окрестности, v является размером окрестности, и арифметические действия выполняются по модулю bⁿ. Для хорошей эффективности маршрутизации и отказоустойчивости значения для u и v могут быть u=b и v≥max(log₂(N), 4), где N представляет собой общее количество узлов, физически участвующих в объединении. N может оцениваться по количеству узлов, присутствующих на сегменте кольца, длина которого больше или равна b, например, когда имеется равномерное распределение идентификаторов. Типичными значениями для b и n являются b=8 или 16 и n=128-битный или 160-битный эквивалент цифр.

Соответственно, узлы маршрутизации могут формировать логарифмическую индексацию, перекрывающую кольцо. В зависимости от положения узлов на кольце точная логарифмическая индексация возможна, например, когда есть существующий узел для каждого числа во множестве id±bⁱ, где i=(1, 2, …, (n-1)). Однако может быть, что не существует узлов для каждого числа во множестве. В этих случаях в качестве узла маршрутизации может быть выбран узел, ближайший к id±bⁱ. Результирующая логарифмическая индексация не точна и может даже не содержать уникальных узлов маршрутизации для некоторых чисел во множестве.

Обратимся снова к Фиг. 3. Фиг. 3 демонстрирует пример двоичного отношения между узлами в инфраструктуре объединения в виде сортированного списка 304 и соответствующее кольцо 306. Пространство идентификаторов сортированного списка 304 находится в области значений от 0 до 2⁸-1 (или 255). То есть b=2 и n=8. Таким образом, узлам, изображенным на Фиг. 3, присваиваются идентификаторы в диапазоне от 0 до 255. Сортированный список 304 использует двоичное отношение, которое является рефлексивным, антисимметричным, транзитивным, полным, и определяется по области именований узлов. Оба конца сортированного списка 304 соединяются, тем самым образуя кольцо 306. Это позволяет каждому узлу на Фиг. 3 рассматривать себя как находящегося в середине сортированного списка 304. Сортированный список 304 является двунаправленным, так что любой узел может просматривать сортированный список 304 в любом направлении. Арифметические действия для просмотра сортированного списка 304 (или кольца 306) выполняются по модулю 2⁸. Таким образом, 255 (или конец сортированного списка 304)+1=0 (или начало сортированного списка 304).

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

Таблица маршрутизации дополнительно указывает, что множество узлов окрестности для идентификатора 64 имеет идентификаторы 83, 76, 50 и 46. Множество соседних узлов может представлять собой заданное количество узлов (т.е. размер v окрестности), которые находятся в пределах заданной области значений (т.е. ширины u окрестности) относительно идентификатора 64. Многообразие различных размеров окрестности и вариантов ширины окрестности, таких, например, как V=4 и U=10, потенциально может использоваться для идентификации множества узлов окрестности. Окрестное множество может изменяться, например, когда узлы присоединяются к инфраструктуре объединения или покидают ее или когда изменяется заданное количество узлов или заданная область значений.

Таблица маршрутизации дополнительно указывает, что идентификатор 64 может осуществлять маршрутизацию к узлам, имеющим идентификаторы 200, 2, 30, 46, 50, 64, 64, 64, 64, 76, 83, 98, 135 и 200. Этот список генерируется посредством идентификации узла, наиболее близкого к каждому числу во множестве id±2ⁱ, где i = (1, 2, 3, 4, 5, 6, 7). То есть b=2 и n=8. Например, узел, имеющий идентификатор 76, может быть идентифицирован в результате вычисления ближайшего узла к 64+2³, или 72.

Узел может направлять сообщения (например, запросы на доступ к ресурсам) непосредственно на предшествующий узел, последующий узел, любой узел во множестве узлов окрестности или любой узел маршрутизации. В некоторых вариантах осуществления узлы реализуют функцию численной маршрутизации для маршрутизации сообщения. Таким образом, функция Численная_Маршрутизация(V, Msg) может быть реализована на узле X для доставки Msg на узел Y в объединении, идентификатор которого численно наиболее близок к V, и возвращения идентификатора узла Y узлу X. Например, узел, имеющий идентификатор 64, может реализовать функцию Численная_Маршрутизация(243, Msg), чтобы обусловить маршрутизацию сообщения к узлу, имеющему идентификатор 250. Однако, поскольку идентификатор 250 не является узлом маршрутизации для идентификатора 64, идентификатор 64 может направить сообщение идентификатору 2 (ближайшему к 243 узлу маршрутизации). Узел, имеющий идентификатор 2, может в свою очередь реализовать функцию Численная_Маршрутизация(243, Msg), чтобы обусловить маршрутизацию сообщения (напрямую или через дополнительные посреднические узлы) к узлу, имеющему идентификатор 250. Таким образом, может оказаться, что функция Численная_Маршрутизация рекурсивно вызывается при каждом инициировании маршрутизации сообщения ближе к назначению.

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

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

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

Фиг. 4 демонстрирует кольцо из колец 400, которое способствует кратчайшей маршрутизации. Кольцо 401 может рассматриваться как главное или корневое кольцо и содержит все узлы, содержащиеся в каждом из колец 402, 403 и 404. Каждое из колец 402, 403 и 404 содержит подмножество узлов из кольца 401, которые выделяются на основании заданного критерия соседства. Например, кольцо 401 может быть разделено на основании географического местоположения, при этом кольцо 402 содержит узлы в Северной Америке, кольцо 403 содержит узлы в Европе, а кольцо 404 содержит узлы в Азии.

В численном пространстве, содержащем 65536 (2¹⁶) идентификаторов, маршрутизация сообщения от североамериканского узла, имеющего идентификатор 5345 на азиатский узел, имеющий идентификатор 23345, может включать в себя маршрутизацию сообщения в пределах кольца 402, пока не будет идентифицирован соседний узел для азиатского узла. Тогда соседний узел может направить сообщение на азиатский узел. Таким образом, между североамериканским узлом и азиатским узлом может совершаться единственный переход (в противоположность множественным переходам). Соответственно, маршрутизация выполняется способом с эффективным использованием ресурсов.

Фиг. 5 демонстрирует иллюстративное порожденное соседством дерево 500 разбиения колец, которое способствует кратчайшей маршрутизации. Как изображено, дерево 500 разбиения колец включает в себя некоторое количество колец. Каждое из колец представляет собой разбиение сортированного связанного списка. Каждое кольцо включает в себя множество узлов, имеющих идентификаторы в сортированном связанном списке. Однако, для внесения ясности относительно количества возможных узлов, эти узлы явно не изображены на кольцах (например, пространство идентификаторов дерева 500 разбиения может определяться параметрами b=16 и n=40).

В пределах дерева 500 разбиения корневое кольцо 501 разделяется на множество подколец, включающее в себя подкольца 511, 512, 513 и 514, на основании критерия 571 (первый критерий границы административной области). Например, каждый компонент имени DNS можно рассматривать как критерий соседства с частичным порядком среди них, порожденным порядком их появления при считывании имен DNS справа налево. Соответственно, подкольцо 511 может быть дополнительно разделено на множество подколец, включающее в себя подкольца 521, 522 и 523, на основании критерия 581 (второй критерий границы административной области).

Подкольцо 522 может быть дополнительно разделено на множество подколец, включающее в себя подкольца 531, 532 и 533, на основании критерия 572 (критерий географической границы). Основанный на местоположении критерий соседства может быть частично упорядочен по континентам, странам, почтовым индексам и так далее. Почтовые индексы сами по себе образуют иерархическую структуру, а значит, они могут восприниматься как дополнительное воздействие на частично упорядоченный подсписок критериев соседства.

Подкольцо 531 может быть дополнительно разделено на множество подколец, включающее в себя подкольца 541, 542, 543 и 544, на основании критерия 573 (первый критерий организационных границ). Частично упорядоченный список по критерию соседства может порождаться согласно тому, как организационно построена данная компания, например по отделениям, департаментам и промышленным группам. Соответственно, подкольцо 543 может быть дополнительно разделено на множество подколец, включающее в себя подкольца 551 и 552, на основании критерия 583 (второй критерий организационных границ).

В пределах дерева 500 разбиения каждый узел имеет единственный идентификатор и участвует в кольцах по соответствующему пути разбиения, начиная от корня до концевой вершины. Например, каждый узел, участвующий в подкольце 552, будет также участвовать в подкольцах 543, 531, 522, 511 и в корне 501. Маршрутизация до узла (идентификатора) назначения может быть выполнена посредством реализации функции Кратчайшая_Маршрутизация, следующим образом:

Кратчайшая_Маршрутизация(V, Msg, P): При данных значении V из области именований узлов и сообщении "Msg", доставляет сообщение на узел Y, чье именование может быть отображено на V среди узлов, считающихся эквивалентными в соответствии с критериями P соседства.

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

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

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

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

В некоторых вариантах осуществления узлы реализуют функцию кратчайшей маршрутизации, чтобы маршрутизировать сообщения, исходя из соотношений критериев эквивалентности. Таким образом, при данных числе V и сообщении "Msg" узел может реализовать функцию Кратчайшая_Маршрутизация(V, Msg, P), чтобы доставить сообщение на узел Y, чье именование может быть отображено на V среди узлов, считающихся эквивалентными в соответствии с критерием P соседства. Критерий P соседства идентифицирует самое нижнее кольцо в дереве разбиения, которое является общим родителем для всех узлов, считающихся его ближайшими эквивалентами. Это может быть представлено в виде строки, полученной последовательным соединением критерия соседства, найденного по пути от корневого кольца до кольца, идентифицируемого с помощью отделения его символом '/' разделителя путевого имени. Например, критерий соседства, идентифицирующий подкольцо 542, может быть представлен как "Соседство:/.COM/Corp2/LocationA/Div2". Каждому кольцу в дереве 500 разбиения может быть присвоено уникальное число, например, в результате хеширования его строки представления с использованием алгоритма SHA. Если число 0 резервируется для корневого кольца, можно вывести заключение, что Численная_Маршрутизация(V,Msg)≡ Кратчайшая_Маршрутизация(V,Msg,0).

Например, узел в подкольце 544 может реализовать функцию Кратчайшая_Маршрутизация, чтобы идентифицировать более близкий узел в подкольце 531 (например, для узла в подкольце 513). В свою очередь, подкольцо 531 может реализовать функцию Кратчайшая_Маршрутизация, чтобы идентифицировать более близкий узел в подкольце 522. Аналогично, подкольцо 522 может реализовать функцию Кратчайшая_Маршрутизация, чтобы идентифицировать более близкий узел в подкольце 511. Точно так же подкольцо 511 может реализовать функцию Кратчайшая_Маршрутизация, чтобы идентифицировать более близкий узел в кольце 501. Таким образом, может иметь место, что функция Кратчайшая_Маршрутизация рекурсивно вызывается при каждом инициировании маршрутизации сообщения ближе к назначению.

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

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

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

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

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

Идентификатор, который является численным значением, равномерно распределенным в области значений от 0 до bⁿ - 1.

Таблица маршрутизации, в состав которой входят (все арифметические действия выполняются по модулю bⁿ):

Для каждого кольца, скажем кольца d, в котором узел участвует

Последующий узел (s_d);

Предшествующий узел (p_d);

Узлы Окрестности (p_kd, …, p_1d, p_d, s_d, s_1d, …, s_jd), такие что s_jd.s_d.id>(id+u/2), j≥v/2-1, и p_kd.p_d.id<(id-u/2), и k≥v/2-1;

Узлы маршрутизации (r_-(n-1), …, r_-1, r₁, …, r_n-1), такие что r_±i=Кратчайшая_Маршрутизация(id±bⁱ, Msg_обновления, d), так что s_d≤id+bⁱ≤s_d+1 или p_d+1≤id-bⁱ≤p_d в соответствующих случаях;

где b является основанием системы счисления, n является длиной поля в количестве разрядов, u является шириной окрестности, v является размером окрестности.

Заметим, что подмножество узлов окрестности, сохраняемое данным узлом в кольце "d", может возникнуть снова в качестве узлов окрестности в дочернем кольце "d+1", в котором данный узел также участвует. Собственно, можно получить верхнюю границу общего количества узлов окрестности, сохраняемых данным узлом по всем D кольцам, в которых он участвует, в виде D*max(u,v)/2. Предполагается, что сохраняется только одна ссылка на данный узел, и в худшем случае верхняя граница служит для сбалансированного дерева.

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

Например, портативный компьютер с двумя сетевыми интерфейсными платами (проводной и беспроводной) можно считать ближайшим эквивалентом и для другого беспроводного и для проводного узлов, совместно использующих те же сегменты ЛВС, что и портативный компьютер. Тем не менее, эти два особых критерия соседства могут быть смоделированы в виде подкритериев, которые применимы только после применения другого критерия соседства с более высоким приоритетом, такого, например, как критерий соседства, основанный на принадлежности к организации. Поскольку этот портативный компьютер принадлежит к той же организации, узлы с псевдонимами в этих двух подкольцах, представляющих 1) принадлежность к проводным и 2) принадлежность к беспроводным сегментам ЛВС, сливаются в единый узел в кольце, представляющем организацию, к которой принадлежит этот переносной компьютер. Нужно понимать, что функция Кратчайшая_Маршрутизация работает, как и предполагалось, без каких-либо изменений в случае совмещения имен.

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

Кольцевые параметры, используемые для конфигурирования ближайшего кольца верхнего уровня, в некоторых вариантах осуществления могут наследоваться ближайшими кольцами более низкого уровня. Например, может иметь место, что кольцо 543 наследует некоторые из кольцевых параметров кольца 531 (которое в свою очередь наследует от кольца 522, и т.д.). Следовательно, размер окрестности и ширина окрестности, сопоставленные с кольцом 531, также сопоставляются с кольцом 541.

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

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

Фиг. 8 демонстрирует иллюстративную схему последовательности операций способа 800 для выделения узлов из инфраструктуры объединения. Способ 800 будет описан относительно колец дерева 500 разбиения, изображенного на Фиг. 5. Способ 800 включает в себя этап, на котором организуют доступ к сортированному связанному списку, содержащему идентификаторы узлов, которые были присвоены узлам в инфраструктуре объединения (этап 801). Например, может быть организован доступ к сортированному связанному списку, представленному кольцом 501. Идентификаторы узлов сортированного связанного списка (узлы, изображенные на кольце 501) могут представлять узлы в инфраструктуре объединения (например, в инфраструктуре 100 объединения).

Способ 800 включает в себя этап, на котором организуют доступ к категориям соседства, которые представляют множество различных критериев соседства для разделения сортированного связанного списка (этап 802). Например, может быть организован доступ к критерию соседства, представляющему границы 561 области, географические границы 562 и границы 563 организации. Однако другие критерии соседства, такие как границы доверенной области, также могут быть представлены в критерии соседства, к которому организуется доступ. Категории соседства могут включать в себя предварительно созданные частично упорядоченные списки критериев соседства. Кольцо может быть разделено на основании частично упорядоченных списков критериев соседства.

Способ 800 включает в себя этап, на котором разделяют сортированный связанный список на один или более первых подсписков на основании первого критерия соседства, причем каждый из этих одного или более первых подсписков содержит, по меньшей мере, подмножество идентификаторов узлов из сортированного связанного списка (этап 803). Например, кольцо 501 может быть разделено на подкольца 511, 512, 513 и 514 на основании критерия 571. Каждое из подколец 511, 512, 513 и 514 может содержать отличное подмножество идентификаторов узлов из кольца 501.

Способ 800 включает в себя этап, на котором разделяют первый подсписок, выбранный из числа одного или более первых подсписков, на один или более вторых подсписков на основании второго критерия соседства, причем каждый из этих одного или более вторых подсписков содержит, по меньшей мере, подмножество идентификаторов узлов, содержащихся в первом подсписке (этап 804). Например, подкольцо 511 может быть разделено на подкольца 521, 522 и 523 на основании критерия 581. Каждое из подколец 521, 522 и 523 может содержать отличное подмножество идентификаторов узлов из подкольца 511.

Фиг. 9 демонстрирует иллюстративную схему последовательности операций способа 900 для наполнения таблицы маршрутизации узла. Способ 900 будет описан относительно сортированного связанного списка 304 и кольца 306, изображенных на Фиг. 3. Способ 900 включает в себя этап, на котором вводят предшествующий узел в таблицу маршрутизации, причем этот предшествующий узел предшествует текущему узлу относительно текущего узла в первом направлении сортированного связанного списка (этап 901). Например, узел, имеющий идентификатор 50, может быть введен в таблицу маршрутизации в качестве предшествующего элемента для узла, имеющего идентификатор 64 (текущий узел). При перемещении в направлении 321 по часовой стрелке (от конца A сортированного связанного списка 304 к концу B сортированного связанного списка 304) узел, имеющий идентификатор 50, предшествует узлу, имеющему идентификатор 64. Введение предшествующего узла может установить такое симметричное партнерство между текущим узлом и предшествующим узлом, при котором текущий узел является партнером предшествующего узла, а предшествующий узел является партнером текущего узла.

Способ 900 включает в себя этап, на котором вводят последующий узел в таблицу маршрутизации, причем этот последующий узел следует за текущим узлом относительно текущего узла в первом направлении в сортированном связанном списке (этап 902). Например, узел, имеющий идентификатор 76, может быть введен в таблицу маршрутизации в качестве последующего элемента для узла, имеющего идентификатор 64 (текущий узел). При перемещении в направлении 322 против часовой стрелки узел, имеющий идентификатор 76, следует за узлом, имеющим идентификатор 64. Введение последующего узла может установить такое симметричное партнерство между текущим узлом и последующим узлом, при котором текущий узел является партнером последующего узла, а последующий узел является партнером текущего узла.

Способ 900 включает в себя этап, на котором вводят соответствующие узлы окрестности в таблицу маршрутизации, при этом эти узлы окрестности идентифицируются из сортированного связанного списка и в первом направлении, и во втором противоположном направлении, на основании ширины окрестности и размера окрестности (этап 903). Например, узлы, имеющие идентификаторы 83, 76, 50 и 46, могут быть введены в таблицу маршрутизации в качестве узлов окрестности для узла, имеющего идентификатор 64 (текущий узел). Исходя из ширины окрестности, равной 20, и размера окрестности, равного 4, узлы, имеющие идентификаторы 83 и 76, могут быть идентифицированы в направлении 321 по часовой стрелке, а узлы, имеющие идентификаторы 50 и 46, могут быть идентифицированы в направлении 322 против часовой стрелки (перемещаясь от конца B сортированного связанного списка 304 к концу A сортированного связанного списка 304). Может иметь место, что в некоторых средах соответствующие узлы окрестности не идентифицируются. Введение узла окрестности может установить такое симметричное партнерство между текущим узлом и узлом окрестности, при котором текущий узел является партнером узла окрестности, а узел окрестности является партнером текущего узла.

Способ 900 включает в себя этап, на котором вводят соответствующие узлы маршрутизации в таблицу маршрутизации, при этом узлы маршрутизации идентифицируются из сортированного связанного списка и в первом, и во втором направлениях, исходя из основания системы счисления и длины поля пространства идентификаторов для инфраструктуры объединения, причем узлы маршрутизации отображают логарифмическую индексацию сортированного связанного списка и в первом, и во втором направлениях (этап 904). Например, узлы, имеющие идентификаторы 200, 2, 30, 46, 50, 64, 64, 64, 64, 64, 76, 83, 98, 135 и 200, могут быть введены в таблицу маршрутизации в качестве узлов маршрутизации для узла, имеющего идентификатор 64. Исходя из основания 2 системы счисления и длины поля, равной 8, узлы, имеющие идентификаторы 64, 64, 76, 83, 98, 135 и 200, могут быть идентифицированы в направлении 321, а узлы, имеющие идентификаторы 64, 64, 50, 46, 30, 2 и 200, могут быть идентифицированы в направлении 322. Как изображено в пределах кольца 306, узлы маршрутизации отображают логарифмическую индексацию сортированного связанного списка 304 и в направлении 321 по часовой стрелке, и в направлении 322 против часовой стрелки. Введение узла маршрутизации может установить такое симметричное партнерство между текущим узлом и узлом маршрутизации, при котором текущий узел является партнером узла маршрутизации, а узел маршрутизации является партнером текущего узла.

Фиг. 7 демонстрирует иллюстративную схему последовательности операций способа 700 для наполнения таблицы маршрутизации узла, который учитывает критерии соседства. Способ 700 будет описан относительно колец, изображенных на Фиг. 5. Способ 700 включает в себя этап, на котором вводят предшествующий узел для каждого иерархически разделенного кольца маршрутизации, в котором участвует текущий узел, в таблицу маршрутизации (этап 701). Каждый предшествующий узел предшествует текущему узлу в первом направлении (например, по часовой стрелке) в пределах каждого иерархически разделенного кольца маршрутизации, в котором участвует текущий узел. Иерархически разделенные кольца маршрутизации разделяются согласно соответствующим критериям соседства и содержат, по меньшей мере, подмножества двунаправленного связанного списка (а возможно весь двунаправленный связанный список). Например, может иметь место, что определенный узел участвует в корневом кольце 501 и в подкольцах 511, 522, 523, 531 и 542. Следовательно, предшествующий узел выбирается для определенного узла изнутри каждого из колец 501 и подколец 511, 522, 523 531 и 542.

Способ 700 включает в себя этап, на котором вводят последующий узел для каждого иерархически разделенного кольца маршрутизации, в котором участвует текущий узел, в таблицу маршрутизации (этап 702). Каждый последующий узел следует за текущим узлом в первом направлении в пределах каждого иерархически разделенного кольца маршрутизации, в котором участвует текущий узел. Например, последующий узел выбирается для определенного узла изнутри каждого из колец 501 и подколец 511, 522, 523, 531 и 542.

Способ 700 включает в себя этап, на котором вводят соответствующие узлы окрестности для каждого иерархически разделенного кольца маршрутизации, в котором участвует текущий узел, в таблицу маршрутизации (этап 703). Узлы окрестности могут идентифицироваться и в первом направлении (например, по часовой стрелке), и во втором противоположном направлении (например, против часовой стрелки), на основании ширины окрестности и размера окрестности, из иерархически разделенных колец маршрутизации, в которых участвует текущий узел. Например, узлы окрестности могут идентифицироваться для определенного узла изнутри каждого из колец 501 и подколец 511, 522, 523, 531 и 542.

Способ 700 включает в себя этап, на котором вводят соответствующие узлы маршрутизации для каждого иерархически разделенного кольца маршрутизации, в котором участвует текущий узел, в таблицу маршрутизации (этап 704). Например, узлы маршрутизации могут идентифицироваться для определенного узла изнутри каждого из колец 501 и подколец 511, 522, 523, 531 и 542.

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

если Y.s_d.id<Y.id+bⁱ<Y.s_d+1.id истинно, то используется кольцо d; или

если Y.p_d.id<Y.id-bⁱ<Y.p_d+1.id истинно, то используется кольцо d.

Если кольцо не было идентифицировано на предыдущем этапе, используется ведущее (например, кольцо 501) кольцо в качестве кольца d. Теперь, кольцо d является кольцом соседства, в котором узел Y должен искать партнера по маршрутизации, ближайшего к z.

Фиг. 10 демонстрирует иллюстративную схему последовательности операций способа 1000 для маршрутизации сообщения к узлу назначения. Способ 1000 будет описан относительно сортированного связанного списка 304 и кольца 306, изображенных на Фиг. 3. Способ 1000 включает в себя этап, на котором принимающий узел принимает сообщение наряду с числом, указывающим назначение (этап 1001). Например, узел, имеющий идентификатор 64, может принимать сообщение, указывающее назначение 212.

Способ 1000 включает в себя этап, на котором определяют, что принимающий узел является, по меньшей мере, или численно более отдаленным от назначения, чем соответствующий предшествующий узел, или численно более отдаленным от назначения, чем соответствующий последующий узел (этап 1002).

Например, в направлении 322 идентификатор 64 является более отдаленным от назначения 212, чем идентификатор 50, и в направлении 321 идентификатор 64 является более отдаленным от назначения 212, чем идентификатор 76. Способ 1000 включает в себя этап, на котором определяют, что назначение находится вне пределов окрестного множества узлов, соответствующего принимающему узлу (этап 1003). Например, узел с идентификатором 64 может определить, что назначение 212 находится вне пределов окрестного множества из 83, 76, 50 и 46.

Способ 1000 включает в себя этап, на котором идентифицируют промежуточный узел из таблицы маршрутизации, соответствующей принимающему узлу, причем этот промежуточный узел является численно более близким к назначению, чем другие узлы маршрутизации в соответствующей таблице маршрутизации (этап 1004). Например, узел, имеющий идентификатор 64, может идентифицировать узел маршрутизации, имеющий идентификатор 200, как являющийся численно более близким к назначению 212, чем другие узлы маршрутизации. Способ 1000 включает в себя этап, на котором отправляют сообщение на промежуточный узел (этап 1005). Например, узел, имеющий идентификатор 64, может отправить сообщение на узел, имеющий идентификатор 200.

Фиг. 11 демонстрирует иллюстративную схему последовательности операций способа 1100 для маршрутизации сообщения к узлу назначения на основании критериев соседства. Способ 1100 будет описан относительно колец, изображенных на Фиг. 4 и Фиг. 5. Способ 1100 включает в себя этап, на котором на принимающий узел принимают сообщение наряду с числом, указывающим назначение, и критерий соседства (этап 1101). Критерий соседства определяет один или более классов узлов. Принимающий узел принимает сообщение в виде части текущего класса узлов, выбранного из одного или более классов узлов на основании критерия соседства. Например, узел, имеющий идентификатор 172, может принимать сообщение, указывающее назначение 201, и критерий соседства, указывающий, что узел назначения является частью классов, представленных кольцом 401. Узел, имеющий идентификатор 172, может принимать сообщение в виде части кольца 404.

Способ 1100 включает в себя этап, на котором определяют, что принимающий узел является, по меньшей мере, или численно более отдаленным от назначения, чем соответствующий предшествующий узел, или численно более отдаленным от назначения, чем соответствующий последующий узел, из числа узлов в выбранном классе узлов (этап 1102). Например, в пределах кольца 404 узел с идентификатором 172 является более отдаленным от назначения 201, чем узел, имеющий идентификатор 174, в направлении по часовой стрелке, и является более отдаленным от назначения 201, чем узел, имеющий идентификатор 153, в направлении против часовой стрелки.

Способ 1100 включает в себя этап, на котором определяют, что назначение находится вне пределов окрестного множества узлов принимающего узла для любого из одного или более классов узлов, определенных в соответствии с критерием соседства (этап 1103). Например, узел, имеющий идентификатор 172, может определить, что назначение 201 не находится в соответствующем окрестном множестве в кольце 404 или в кольце 401.

Способ 1100 включает в себя этап, на котором идентифицируют промежуточный узел из таблицы маршрутизации принимающего узла, причем этот промежуточный узел является численно более близким к назначению, чем другие узлы маршрутизации в таблице маршрутизации (этап 1104). Например, узел, имеющий идентификатор 172, может идентифицировать узел, имеющий идентификатор 194, как являющийся численно более близким к назначению 201, чем другие узлы маршрутизации в кольце 404. Способ 1100 включает в себя этап, на котором отправляют сообщение на промежуточный узел (этап 1105). Например, узел, имеющий идентификатор 172, может отправить принятое сообщение на узел, имеющий идентификатор 194. Узел, имеющий идентификатор 172, может отправить принятое сообщение на узел, имеющий идентификатор 194 для соблюдения предварительно заданного частично упорядоченного списка критериев соседства.

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

Однако в других вариантах осуществления пошаговое ослабление критериев соседства, приводящее к перемещению на следующее более высокое кольцо, продолжается, пока может совершаться дальнейшая маршрутизация (или пока не встретится корневое кольцо). То есть происходит множество переходов на более высокие кольца прежде, чем сможет быть совершено дальнейшее выполнение маршрутизации. Например, обратимся теперь к Фиг. 5, если никакое дальнейшее выполнение маршрутизации не может быть совершено на кольце 531, критерии соседства могут быть ослаблены достаточно для перемещения на кольцо 511 или даже на корневое кольцо 501.

Фазы Узлов

Узел, участвующий в инфраструктуре объединения, может работать в различных эксплуатационных фазах. Допустимые фазовые значения для узла могут быть определены так, чтобы быть членами упорядоченного множества. Например, {Идентификатор_Узла}.{Идентификаторы_Экземпляров}.{Фазовое Значение[Значения Фазового Состояния: Введение, Синхронизация, Маршрутизация, Эксплуатация].[Индикатор Неизвестная.Фаза: известная во время передачи фаза, неизвестная во время передачи фаза]}, определяет одно возможное упорядоченное множество, отображающее фазовое пространство данного узла в пределах инфраструктуры объединения. Экземпляр узла может переходить (или продвигаться вперед) через фазовые состояния узла от Введения к Синхронизации, к Маршрутизации, к Эксплуатации по порядку. Дополнительно, в некоторых вариантах осуществления экземпляр узла может быть сконфигурирован так, чтобы этот экземпляр узла был лишен возможности перехода обратно к предшествующему фазовому состоянию узла. В некоторых вариантах осуществления узел увеличивает свой идентификатор экземпляра каждый раз при достижении узла.

Например, экземпляру узла может быть запрещен переход от Маршрутизации назад к Синхронизации (или назад к Введению) и т.д. Соответственно, в некоторых вариантах осуществления, если известно, что данный экземпляр узла (например, идентифицируемый по (Идентификатор_Узла, Идентификатор_Экземпляра)), продвинулся к конкретному фазовому состоянию узла (например, Эксплуатация), то также известно, что данный экземпляр узла вряд ли будет (а в некоторых вариантах осуществления не будет) возвращаться к предшествующему фазовому состоянию узла (например, назад к Маршрутизации, Синхронизации или Введению). Таким образом, есть существенная вероятность, что любой экземпляр узла в фазе узла, предшествующей конкретному фазовому состоянию узла, является новым (и увеличенным) экземпляром узла.

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

Время от времени узлы могут перезагружаться или терять связь друг с другом, как, например, при первом запуске, из-за постепенного выхода, или в результате аварийного завершения (фатальный сбой). Таким образом, для узла в любом фазовом состоянии узла есть вероятность перезагрузки или потери связи с другими узлами. Например, фатальный сбой может привести к перезагрузке узла в фазовом состоянии Маршрутизация. Во время перезагрузки или потери связи может не быть возможности для определения, в каком фазовом состоянии узла находится узел. Соответственно, когда узел перезагружается или связь с узлом потеряна, [Индикатор Неизвестная.Фаза] может быть установлен на указание того, что фазовое состояние для узла в настоящее время не известно. Однако любое ранее отраженное и/или обнаруженное фазовое состояние для узла может быть сохранено и не потеряно.

[Индикатор Неизвестная.Фаза] может использоваться для указания, было фазовое состояние известно во время передачи значения фазового состояния (например, фазовое значение для неизвестная.фаза не установлено), или фазовое состояние представляет собой ранее отраженное фазовое состояние, и фазовое состояние не было известно во время передачи фазового состояния (например, фазовое значение для неизвестная.фаза установлено). Таким образом, фаза узла (его фазовое значение) может быть представлена с использованием и значения фазового состояния, и индикатора неизвестная.фаза.

Протокол Присоединения

Время от времени узлы могут присоединяться к существующим объединениям и выходить из них. Узлы могут реализовывать соответствующие протоколы для присоединения к объединениям и выхода из них. Например, узел может реализовать функцию Присоединение(), чтобы стать частью существующего объединения. Узел, реализующий функцию Присоединение(), может проходить через три упорядоченных фазовых состояния: фазовое состояние введения, фазовое состояние синхронизации и фазовое состояние маршрутизации, перед достижением заключительного фазового состояния эксплуатации. В других вариантах осуществления эти определенные фазовые состояния порядка могут отсутствовать и в то же время могут быть определены другие. Фиг. 12A демонстрирует пример узла, устанавливающего принадлежность к инфраструктуре объединения. Фиг. 12B демонстрирует пример узлов в инфраструктуре объединения, обменивающихся сообщениями.

Фаза Введения: узел, Y, входит в это фазовое состояние, порождая сообщение присоединения, включающее в себя, по меньшей мере, его идентификатор узла и обозначающее действие присоединения к объединению. Сообщение присоединения может быть сообщением маршрутизации, отправленным вновь присоединяющимся узлом (узел Y), с установкой характеристик его назначения на именование вновь присоединяющегося узла. В этом фазовом состоянии вновь присоединяющийся узел вводится между своими предшествующим и последующим узлами в объединении. Фазовое состояние введения может быть реализовано согласно следующему алгоритму (все арифметические действия выполняются по модулю bⁿ):

ФВ 1. Y идентифицирует существующий узел, который уже является частью самого нижнего кольца, от которого присоединяющийся узел желает участвовать в объединении. Это может или быть статически конфигурироваться или динамически обнаруживаться с использованием протокола динамического конфигурирования узла (DHCP - Dynamic Host Configuration Protocol) и/или DNS, и/или протокола WS-Discovery, или (теоретически известной) постоянной. Допустим, этим существующим узлом объединения является E.

ФВ 2. Y вызывает функцию E.Численная_Маршрутизация(Y, Msg_присоединения) для определения узла X, чей идентификатор численно наиболее близок к Y.id в каждом кольце соседства, в котором узел Y участвует. Это может включать в себя направление сообщения присоединения на множественные узлы.

ФВ 3. Определяют численные последующий (s) и предшествующий (p) узлы. (Заметим, что данные, необходимые для выполнения последующего введения, могут переноситься в сообщении присоединения и в отклике на него. В этой связи не требуются дополнительные полные обходы дерева.)

Случай 1: X.id>Y.id

Y.s=X, Y.p=X.p, X.p.s=Y, и X.p=Y

Случай 2: X.id<Y.id

Y.p=X, Y.s=X.s, X.s.p=Y, и X.s=Y

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

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

Фиг. 16 изображает пример модели сообщения и сопутствующей модели 1600 обработки. Как изображено на Фиг. 16, узел может отправлять и принимать сообщения запроса синхронизации. Например, сообщение 1601 запроса синхронизации может быть принято на функциональном уровне 1651 от вновь введенного узла (например, узла на Фиг. 12B, имеющего идентификатор 144). Прикладные данные 1602 (например, подписки пространства имен) могут передаваться совместно с сообщениями 1601 запроса синхронизации. Функциональный уровень 1651 может сообщать прикладному уровню 1652 о любых прикладных данных, включенных в состав сообщений запроса синхронизации. Например, функциональный уровень 1651 может инициировать событие 1603 синхронизации состояния окрестности, включающее в себя прикладные данные 1602, на прикладной уровень 1652. Запрос 1631 синхронизации, включающий в себя прикладные данные 1607, также может быть отправлен на другой узел, который обрабатывает запрос 1631 синхронизации аналогично обработке для запроса 1601 синхронизации в модели 1600 обработки.

В ответ на некоторое событие функционального уровня (например, сообщение 1601 запроса синхронизации, ответное сообщение 1641 синхронизации или сообщение 1612 проверки связи) функциональный уровень 1651 может инициировать функцию 1604 запроса состояния окрестности на прикладном уровне 1652. Запрос 1604 состояния окрестности представляет собой запрос к прикладному уровню для получения состояния, которое должно быть распространено на окрестность. В ответ на запрос 1604 состояния окрестности прикладной уровень 1652 может доставить состояние 1606 окрестности, включающее в себя дополнительные прикладные данные 1607, на функциональный уровень 1651. С другой стороны, прикладной уровень 1652 может отправить состояние 1606 окрестности, включающее в себя дополнительные прикладные данные 1607 в ответ на некоторое событие прикладного уровня. Используя внутренние механизмы, подобные вышеупомянутому, функциональный уровень 1651 может отправить ответное сообщение 1608 синхронизации, включающее в себя дополнительные прикладные данные 1607, для распространения состояния окрестности прикладного уровня.

Фаза Синхронизации: После обработки ответного сообщения присоединения узел Y переходит из фазового состояния введения к фазовому состоянию синхронизации (Синхронизация). В фазовом состоянии синхронизации вновь введенный узел Y синхронизирует информацию с узлами в окрестности. Вообще, Узел Y может отправить сообщения синхронизации, по меньшей мере, своим предшествующему и последующему узлам, идентифицированным в фазовом состоянии введения. Эти узлы, обрабатывающие сообщения синхронизации, могут возвратить отклики на синхронизацию, которые указывают соответствующие окрестность и партнерские узлы маршрутизации этих узлов обработки. В более конкретном примере фазовое состояние синхронизации может быть реализовано согласно следующему алгоритму (все арифметические действия выполняются по модулю bⁿ):

ФС1. Вычисляют Окрестность(Y), исходя из совокупности узлов Окрестности(Y.s) и Окрестности(Y.p) в каждом кольце соседства, в котором узел Y участвует. Вычисление совокупности может быть сделано следующим образом:

(s_j, …, s₁, s, p, p₁, …, p_k) так, что s_j.s.id>(Y.id+u/2), j≥v/2-1, p_k.p.id<(Y.id-u/2), и k≥v/2-1

ФС2. Обратимся ненадолго к Фиг. 16, запрашивают локальный прикладной уровень узла Y (например, прикладной уровень 1652) посредством запроса состояния окрестности (например, запроса состояния окрестности 1604), чтобы получить дополнительные специализированные данные окрестности (например, специализированные данные 1607).

ФС3. Отправляют сообщение синхронизации, по меньшей мере, на ближайшие последующий и предшествующий узлы, включающее в себя, по меньшей мере, информацию о состоянии живучести каждой ближайшей окрестности и партнерском узле маршрутизации с позиции узла Y. Любые дополнительные специализированные данные окрестности (например, прикладные данные 1607), к которым получен доступ на этапе ФС2, включаются в состав запроса 1631 синхронизации.

ФС3. Y принимает ответные сообщения синхронизации обратно от тех узлов, которые обработали сообщения синхронизации, отправленные на этапе ФС2. Например, узел Y может обмениваться сообщениями синхронизации (запрос/отклик) с одним или более узлами в пределах своей вычисленной окрестности. После обмена сообщениями синхронизации, по меньшей мере, с одним, а возможно, и всеми соседними узлами узла Y узлы вычисленной окрестности могут обмениваться дополнительными сообщениями, чтобы распространить синхронизированные данные. Сообщение синхронизации (запрос или отклик) может быть сообщением, не являющимся сообщением маршрутизации, отправленным узлом, чтобы заранее синхронизировать свои данные с целевым узлом, а именно, например, в окрестности узлов.

ФС4. Когда принимается ответное сообщение синхронизации на этапе ФС3 (например, ответное сообщение 1641 синхронизации), любые дополнительные специализированные данные окрестности, представленные в этих принятых ответных сообщениях синхронизации (например, прикладные данные 1622), могут быть предоставлены прикладному уровню 1652 узла Y посредством события 1603 синхронизации состояния окрестности.

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

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

ФМ1, если фазовое состояние маршрутизации выполняется как часть балансирующей процедуры (раскрывается позже), убеждаются, что последующий узел (Y.s) и предшествующий узел (Y.p) активны в каждом кольце соседства, в котором узел Y участвует. Если тот или другой не активен, определяют замещающий узел для недействующего узла(ов), выбирая следующий наилучший последующий или предшествующий узел среди узлов окрестности в рассматриваемом кольце.

ФМ2. Для 1≤i≤n-1

ФМ2a. Вычисляют z=Y.id±bⁱ

ФМ2b. Если кольцо d не эквивалентно наиболее соответствующему соседству, находят кольцо d, в котором участвует узел Y и выполняется условие Y.s_d.id<Y.id+bⁱ<Y.s_d+1.id или Y.p_d.id<Y.id-bⁱ<Y.p_d+1.id. Иначе формируют кольцо d, наиболее соответствующее кольцу соседства. Кольцо d является кольцом соседства, в котором узел Y должен искать партнера маршрутизации, наиболее близкого к z. Допустим, Q является узлом, численно наиболее близким к z между Y.s_d.r_±i и Y.p_d.r_±i. Если |Q.id-z| находится в пределах настраиваемого процентного соотношения относительно bⁱ (обычно 20%), просто полагают Y.r_±i=Q. Если Q.id ближе к z, чем или (Y.s_d.id±bⁱ), или (Y.p_d.id±bⁱ), это означает, что узел Y является лучшим партнерским узлом маршрутизации для узла Q в кольце d соседства, чем Y.S_d или Y.p_d. Следовательно, отправляют Msg_обновления на узел Q, если оно уже не отправлено, доставляя i и узел Y как параметры, чтобы узел Q мог установить узел Y в качестве своего партнерского узла маршрутизации при r._i.

ФМ2c. Если это фазовое состояние выполняется как часть балансирующей процедуры и если Y.s_d.r_±i.id=Y.p_d.r_±i.id, существует только один узел в числовом диапазоне между (Y.s_d.id±bⁱ) и (Y.p_d.id±bⁱ). Этим узлом является тот, на который указывает узел маршрутизации r_±i последующего (или предшествующего) узла. Поэтому просто полагают Y.r_±i=Y.s_d.r_±i._±i.

ФМ2d. В противном случае вычисляют партнера Y.r_±i маршрутизации, вызывая функцию Кратчайшая_Маршрутизация на узле Q с использованием критерия соседства, установленного для того же кольца d. Отсюда вытекает Y.r_±i=Q.Кратчайшая_Маршрутизация(z, Msg_обновления, d).

ФМ3. На данном этапе узел Y может обрабатывать не только сообщения, предназначенные для него, но может также и направлять сообщения.

ФМ4. Подписываются на уведомляющие события живучести, отправляемые от прикладного уровня для идентификаторов конечной точки партнерских узлов маршрутизации, если это уже не было сделано. Кроме того, аннулируют любые подписки на события живучести, созданные ранее с прикладным уровнем, для узлов, которые больше не являются партнерскими узлами маршрутизации. Например, запросы на подписку и/или аннулирование могут проходить вплоть до прикладного уровня (например, прикладного уровня 121), который реализует логическую схему публикации по подписке для соответствующего приложения (например, приложения пространства имен). Когда последовательные специализированные сообщения живучести (например, те, которые возникают в результате подписок на пространства имен) принимаются на прикладном уровне, уведомления (события) могут быть спущены на другие нижние уровни (например, другие нижние уровни 131) для обработки.

Фиг. 17 изображает пример целого ряда обменов информацией живучести, которые могут происходить между функциональным уровнем 1751 и прикладным уровнем 1752. Как изображено на Фиг. 17, конечные точки являются, например, разделами публикации/подписки (например, представленные URL или URI), представляющими различные узлы, и могут быть, например, узлами инфраструктуры объединения. Подписка На Событие Живучести 1701 может быть вызвана с функционального уровня 1751 на прикладном уровне 1752, чтобы подписаться на событие живучести (например, на раздел публикации/подписки). Аннулирование Подписки На Живучесть 1702 может быть вызвано с функционального уровня 1751 на прикладном уровне 1752, чтобы аннулировать подписку на событие живучести. Снижение Конечной Точки 1703 может отправляться с прикладного уровня 1752 на функциональный уровень 1751, чтобы указать, что конечная точка может быть снижена, и обеспечить функциональный уровень 1751 дополнительной замещающей конечной точкой. Событие 1703 Снижения Конечной Точки может отправляться асинхронно на основании предшествующей подписки (например, Подписки На Событие Живучести 1701).

Снижение Узла 1704 может быть вызвано с функционального уровня 1751 на прикладном уровне 1752, чтобы указать, что функциональный уровень 1751 (или какой-нибудь другой нижний уровень) обнаружил недействующий узел и дополнительно обеспечивает прикладной уровень 1752 замещающим узлом. Прикладной уровень 1752 может впоследствии распространить сведения, что был обнаружен потенциально недействующий узел, другим заинтересованным сторонам. Событие 1704 Снижения Узла может отправляться асинхронно всякий раз, когда функциональный уровень 1751 или какой-либо другой нижний уровень обнаруживает потенциально недействующий узел. Отправка живучести 1706 может быть вызвана с прикладного уровня 1752 на функциональном уровне 1751, когда прикладной уровень 1752 обнаруживает, что узел снижается (например, на основании события 1704 снижения узла или на основании какого-либо другого внешнего механизма). Событие 1706 отправки живучести может вызвать отправку функциональным уровнем 1751 сообщения живучести. Событие 1706 отправки живучести также может вызываться асинхронно всякий раз, когда прикладной уровень 1752 обнаруживает, что узел снижается, и независимо от каких-либо предшествующих установленных подписок (посредством подписки на живучесть).

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

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

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

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

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

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

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

Вернемся к Фиг. 16, сообщение 1609 проверки связи может быть принято на функциональном уровне 1651 от узла окрестности. Прикладные данные 1612 (например, подписки пространства имен) могут передаваться совместно с сообщением 1609 проверки связи. Функциональный уровень 1651 может сообщать прикладному уровню 1652 о любых прикладных данных, включенных в состав сообщения проверки связи. Аналогично, функциональный уровень 1651 может сообщать прикладному уровню 1652 о любых прикладных данных, включенных в состав сообщений Запроса Синхронизации. Оба этих варианта передачи могут быть выполнены посредством отправки события 1603 синхронизации состояния окрестности, включающего в себя прикладные данные 1612, на прикладной уровень 1652.

В ответ на какое-либо событие функционального уровня (например, принятое сообщение 1609 проверки связи) функциональный уровень 1651 может отправить запрос 1604 состояния окрестности на прикладной уровень 1652. Запрос 1604 состояния окрестности вызывается на прикладном уровне 1652 для получения состояния, которое должно быть дополнительно распространено в окрестности. В ответ на запрос 1604 состояния окрестности прикладной уровень 1652 может возвратить состояние 1606 окрестности, включающее в себя дополнительные прикладные данные 1607, на функциональный уровень 1651. Функциональный уровень 1651 может отправить сообщение 1611 проверки связи, включающее в себя дополнительные прикладные данные 1607 для распространения информации о живучести узлов окрестности и партнерских узлов маршрутизации, а также дополнительное состояние окрестности прикладного уровня. Функциональный уровень 1651 может также отправить отклик 1608 на синхронизацию, включающий в себя дополнительные прикладные данные 1607 для распространения структуры приложения.

Протокол Выхода

Если для узла целесообразно выйти из объединения, узел может реализовать функцию Выхода, чтобы быть мягко выведенным из объединения. Узел выходит из существующего объединения, отправляя сообщение выхода одному или более своим непосредственным ближайшим предшествующему и последующему узлам, а возможно, другим узлам в этой же ближайшей окрестности. Таким образом, в зависимости от модели распространения выхода (т.е. от того, каким узлам отправляются сообщения выхода) информация, связанная с выходящим узлом, распространяется на другие узлы на кольце в пределах окрестности выходящего узла. Сообщение выхода представляет собой однонаправленное сообщение, порождаемое мягко выходящим узлом для сообщения одному или более другим узлам в пределах, по меньшей мере, одной из его ближайших окрестностей о своем предстоящем выходе. Выходящий узел распространяет сообщение выхода (например, в пределах своей окрестности) способом, подобным распространению сообщений проверки связи. Например, узел, имеющий идентификатор 30, может отправить сообщения 1219 выхода на узлы, имеющие идентификаторы 17 и 40. Узел, имеющий идентификатор 30, может затем вывести себя из инфраструктуры объединения с точки зрения данного ближайшего кольца. Заметим, возможно, что узел выводит себя из одной ближайшей окрестности, но не из других, к которым он может принадлежать.

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

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

Живучесть

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

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

[Узел]: Идентифицирует узел, состояние живучести которого представляется. Узел может быть идентифицирован на основании [Свойств Ссылки], что дополнительно включает в себя [Идентификатор Экземпляра].

[Свойства Ссылки]: единицы информации Элемента, определяемые в спецификации WS-адресации. WS-адресация задает свойство ссылки [Идентификатор Экземпляра] для включения в состав набора свойств ссылки.

[Идентификатор Экземпляра]: число, которое идентифицирует конкретный экземпляр узла. Счетчик загрузки с приращением может использоваться в качестве идентификатора экземпляра узла.

[Фаза]: Передает фазу идентифицированного узла.

[Значение Фазового состояния]: Передает наивысшее фазовое состояние (введение, синхронизация, маршрутизация, эксплуатация), о котором известно, что оно было достигнуто идентифицированным экземпляром узла.

[Индикатор Неизвестная.Фаза]: Указатель, который передается, если текущая фаза известна или неизвестна.

[Свежесть]: Передает свежесть информации и ее значение находится в пределах от 0 до Максимальная_Свежесть. Чем больше значение, тем более свежая информация, причем 0 означает отсутствие информации, а Максимальная_Свежесть является протокольной заданной постоянной.

[Цвет]: Идентифицирует класс эквивалентности соседству, которому принадлежит узел. Два узла с одинаковым значением цвета всегда считаются наиболее близкими, поскольку они оба принадлежат одному и тому же классу эквивалентности, идентифицируемому значением цвета. Количество классов эквивалентности соседству может со временем возрастать, по мере того, как дополнительные узлы присоединяются к объединению.

[Вес]: Доставляет показатель возможностей узла и его значение находится в пределах от 0 до Максимальный_Вес. Он измеряет требуемые характеристики узла объединения, такие как широкие вычислительные возможности, высокая пропускная способность сети и продолжительное время безотказной работы. Чем выше значение, тем больше возможность узла стать более желательным с точки зрения партнерства.

В некоторых средах свойства [Узел] и [Свежесть] узла или неявно или явно передаются в большем контексте, таком как заголовки сообщений [Источник] и [Отправитель], и по существу включение вышеупомянутых свойств еще раз в состав заголовков живучести будет дублирующим. Например, отправителю сообщения требуется передать только свою информацию о текущей фазе, цвете и весе, поскольку его идентификатор, Идентификатор Экземпляра доставляется в заголовках адресации сообщений, а его Свежесть неявно подразумевается.

Состояние живучести можно, по меньшей мере, частично упорядочить на основании двоичного отношения "<", определяемого следующим образом:

"L1<L2" является истинным, если

1. "L1.[Узел].[Имя] == L2.[Узел].[Имя]" является истинным, и одно из следующего является истинным с критериями, выполненными и замкнутыми накоротко в указанном порядке:

L1.[Узел].[Свойства Ссылки].[Идентификатор Экземпляра] < L2.[Узел].[Свойства Ссылки].[Идентификатор Экземпляра]

L1.[Индикатор Неизвестная.Фаза]!=истина И L2.[Индикатор Неизвестная.Фаза]!=истина И L1.[Фазовое состояние] < L2.[Фазовое состояние]

L1.[Свежесть] < L2.[Свежесть]

2. Или "L1.[Цвет] == L2.[Цвет]" является истинным, и одно из следующего является истинным с критериями, выполненными и замкнутыми накоротко в указанном порядке:

L1.[Фазовое состояние] < L2.[Фазовое состояние]

L1.[Вес] < L2.[Вес]

Дополнительно, "спускающееся" сообщение живучести можно отправить на определенный узел, когда обнаружено или предполагается, что определенный узел стал недоступным (например, снизился). В качестве примера, когда прикладной уровень (например, прикладной уровень 121) обнаруживает, что другой прикладной уровень (например, прикладной уровень 123) или узел, размещающийся на этом другом прикладном уровне, снижается, обнаруживший это прикладной уровень может уведомить другие нижние уровни (например, другие нижние уровни 131), что узел, возможно, снизился, например, в соответствии с моделью сообщений и соотнесенными моделями 1600 и/или 1700 обработки. Такое уведомление может вызвать отправку другими нижними уровнями, такими, например, как функциональный уровень 1651, спускающегося сообщения живучести. Это является только одним примером управляющего воздействия для генерирования спускающегося сообщения живучести.

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

Балансирующая Процедура

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

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

Было принято заданное количество сообщений живучести, описанных выше.

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

Изменилась окрестность в том смысле, что в ней появились некоторые новые узлы или ее покинули некоторые присутствовавшие узлы.

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

Этапы ФМ2b, ФМ2d и ФМ4 в сочетании с 1) поиском самого близкого узла маршрутизации для числа, 2) протоколом выхода с последующим мягким выводом узлов из объединения и 3) балансирующей процедурой с последующим приемом узлами сообщений живучести дают в результате систему с более быстрым восстановлением, когда узлы объединения присоединяются к сети и выходят из нее довольно быстро и в больших числах.

Сообщения Состояния

Сообщение состояния представляет собой ненаправленное сообщение, отправляемое принимающим узлом на передающий узел, чтобы сообщить об успехе/неудаче маршрутизации соотнесенного сообщения, которое передающий узел ранее переслал на принимающий узел. Фиг. 18 изображает пример того, как сообщения, формирующие часть модели обмена сообщениями запроса-отклика, маршрутизируются через узлы на кольце. Сообщение состояния может включать в себя заголовки, которые идентифицируют исходное соотнесенное сообщение, состояние маршрутизации которого сообщается. Кроме того, сообщения состояния могут использоваться между узлами для указания, что сообщение было успешно направлено от одного узла следующему. Например, сообщение 1811 запроса маршрутизации от узла 1801 на узел 1806 включает в себя запрос 1811 отправки через узлы 1802, 1803, 1804 и 1805. Соответствующие каскадные сообщения о благоприятном состоянии (состоянии 1817, 1818, 1819, 1820 и 1821) могут быть отправлены от узла 1806 на узел 1805, от узла 1805 на узел 1804, от узла 1804 на узел 1803, от узла 1803 на узел 1802 и от узла 1802 на узел 1801 соответственно. В ответ на запрос 1811 отклик 1816 может быть отправлен сквозным маршрутом от узла 1807 на узел 1801. Отклик 1816 необязателен и может отсутствовать в однонаправленной модели обмена сообщениями.

Фиг. 13 демонстрирует иллюстративную схему последовательности операций способа 1300 для узла, чтобы присоединиться к инфраструктуре объединения. Способ 1300 будет описан относительно кольца 1206, изображенного на Фиг. 12A и 12B. Способ 1300 включает в себя этап, на котором передают сообщение присоединения в инфраструктуру объединения (этап 1301). Например, узел, имеющий идентификатор 144, может породить присоединение 1201 к инфраструктуре объединения, включающей в себя кольцо 1206. Способ 1300 включает в себя этап, на котором принимают сообщение присоединения от присоединяющегося узла (этап 1308). Например, узел, присутствующий в инфраструктуре объединения, включающей в себя кольцо 1206, может принять присоединение 1201.

Способ 1300 включает в себя этап, на котором направляют сообщение присоединения на узел обработки (этап 1309). Узел обработки может быть узлом, имеющим идентификатор, который численно ближе к идентификатору присоединяющегося узла, чем другие активные узлы в инфраструктуре объединения во время маршрутизации сообщения присоединения. Например, присоединение 1201 может быть сначала принято на узле, имеющем идентификатор 64, направлено на узел, имеющий идентификатор 135, и направлено на узел, имеющий идентификатор 151.

Способ 1300 включает в себя этап, на котором вычисляют один или более предшествующих узлов и один или более последующих узлов для присоединяющегося узла (этап 1310). Например, узел, имеющий идентификатор 151, может вычислить непосредственно предшествующий узел и непосредственно последующий узел для узла, имеющего идентификатор 144. В пределах кольца 1206 узел, имеющий идентификатор 151, может вычислить, что узел, имеющий идентификатор 135, является непосредственно предшествующим узлом, и что узел, имеющий идентификатор 151, является непосредственно последующим узлом. Подобные вычисления могут быть проделаны для других ближайших колец.

Способ 1300 включает в себя этап, на котором вычисляют один или более узлов маршрутизации для присоединяющегося узла (этап 1311). Например, узел, имеющий идентификатор 151, может вычислить узлы маршрутизации (с позиции узла, имеющего идентификатор 151) для узла, имеющего идентификатор 144. В пределах кольца 1206 узел, имеющий идентификатор 151, может вычислить, например, что узлы, имеющие идентификаторы 218 и 40, являются узлами маршрутизации для узла, имеющего идентификатор 144. Подобные вычисления могут быть проделаны для других ближайших колец.

Способ 1300 включает в себя этап, на котором отправляют отклик на присоединение на присоединяющийся узел (этап 1312). Отклик на присоединение может идентифицировать все предшествующие и последующие узлы окрестности и партнерские узлы маршрутизации для присоединяющегося узла, которое вычислено узлом обработки с учетом его текущего представления об инфраструктуре объединения. Например, отклик 1202 на присоединение может идентифицировать, по меньшей мере, узел, имеющий идентификатор 135, как непосредственно предшествующий узел для узла, имеющего идентификатор 144, может идентифицировать узел, имеющий идентификатор 151, как непосредственно последующий узел для узла, имеющего идентификатор 144, и может идентифицировать любые узлы маршрутизации (для узла, имеющего идентификатор 144), вычисленные на узле, имеющем идентификатор 151, для идентификатора 144 узла (вновь присоединяющийся узел).

Способ 1300 включает в себя этап, на котором принимают отклик на присоединение от узла объединения, который обработал сообщение присоединения (этап 1302). Например, узел, имеющий идентификатор 144, может принять отклик 1202 на присоединение от узла, имеющего идентификатор 151.

Способ 1300 включает в себя этап, на котором отправляют запрос синхронизации, по меньшей мере, и на непосредственно ближайшие предшествующие узлы, и на непосредственно ближайшие последующие узлы (этап 1303). Например, обращаясь теперь к Фиг. 12B, узел, имеющий идентификатор 144, может отправить запросы 1203 синхронизации на узлы, имеющие идентификаторы 135 и 151. Запрос 1203 синхронизации может включать в себя идентификацию любых узлов окрестности узла, имеющего идентификатор 144, и/или идентификацию любых партнеров по маршрутизации узла, имеющего идентификатор 144.

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

Способ 1300 включает в себя этап, на котором принимают отклик на синхронизацию и от ближайших предшествующих, и от ближайших последующих узлов (этап 1304). Например, узел, имеющий идентификатор 144, может принять отклики 1204 на синхронизацию от узлов, имеющих идентификаторы 135 и 151. Отклик 1204 на синхронизацию может включать в себя информацию живучести для одного или более узлов на кольце 1206 или других кольцах в инфраструктуре объединения. Отклик 1204 на синхронизацию может также идентифицировать любые предполагаемые партнерские узлы маршрутизации для узла, имеющего идентификатор 144.

Способ 1300 включает в себя этап, на котором вычисляют соседние узлы (этап 1305). Например, узел, имеющий идентификатор 144, может вычислить соответствующие узлы окрестности, исходя из совокупности узлов окрестности для узлов, имеющих идентификаторы 135 и 151. Узлы окрестности могут быть вычислены на основании суммарного представления из ответного сообщения присоединения и любых ответных сообщений синхронизации.

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

Способ 1300 включает в себя этап, на котором обмениваются, по меньшей мере, информацией об узлах окрестности с вычисленными партнерами по маршрутизации (этап 1307). Например, узел, имеющий идентификатор 144, и узел, имеющий идентификатор 218 (вычисленный партнер по маршрутизации), могут обменяться информацией о состоянии (например, идентификатор экземпляра, фазовое состояние и т.д.), связанной с их соответствующими узлами окрестности. Эти обмены выполняются вновь присоединяющимся узлом, создающим (маршрутизирующим) сообщение Обновления, по меньшей мере, с каждым однозначно определенным вычисленным партнером по маршрутизации, как описано выше в разделе Фазовое состояние Маршрутизации. Узлы, обрабатывающие сообщение Обновления, отправят соответствующее ответное сообщение Обновления в ответ на получение этих сообщений обновления от вновь присоединяющегося узла. Отклик на Обновление включает в себя, по меньшей мере, информацию живучести для себя и своих узлов окрестности.

Способ 1300 может также включать в себя этап, на котором инициируют начальное распространение таблиц маршрутизации, по меньшей мере, на один узел окрестности. Например, узел, имеющий идентификатор 144, может включить вычисленные узлы окрестности и партнерские узлы маршрутизации в состав сообщения проверки связи и отправлять сообщение проверки связи на узел, имеющий идентификатор 174 (например, один из вычисленных узлов окрестности). Узел, имеющий идентификатор 174, может принять сообщение проверки связи и обновить соответствующую таблицу маршрутизации, используя информацию живучести, порожденную узлом, имеющим идентификатор 144. Узел, имеющий идентификатор 174, может также включить свою соответствующую таблицу маршрутизации в состав второго сообщения проверки связи и отправить второе сообщение проверки связи в некоторую перспективную точку по направлению к узлу, имеющему идентификатор 144. Узел, имеющий идентификатор 144, может принять второе сообщение проверки связи и может обновить свою соответствующую таблицу маршрутизации, используя узлы в информации живучести, включенной во второе сообщение проверки связи (т.е. узлы в таблице маршрутизации относительно узла, имеющего идентификатор 174). Узел, имеющий идентификатор 144, может повторить отправку сообщений проверки связи в отношении других узлов окрестности в кольце 1206.

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

Дополнительно, хотя способ 1300 был описан относительно отдельного кольца (кольцо 1206), нужно понимать, что в некоторых вариантах осуществления узел, который присоединяется к одному кольцу, по существу, также присоединяется к одному или более другим кольцам. Например, вернемся ненадолго к Фиг. 5, узел при присоединении к кольцу 551, по существу, присоединяется также к кольцам 543, 531, 522, 511 и 501. Таким образом, способ 1300 может быть реализован для присоединения к множеству колец. В других вариантах осуществления некоторые или все этапы в способе 1300 могут повторяться при присоединении к множественным кольцам. Например, обращаясь снова к Фиг. 5, один или более этапов способа 1300 могут повторяться, когда узел присоединяется и к кольцу 551, и к кольцу 514 (например, совмещение имен). В любом случае идентификатор присоединяющегося узла может быть доступен и использоваться для идентификации присоединяющегося узла в сортированном связанном списке, а также в соответствующих иерархически разделенных подсписках, в которых присоединяющийся узел должен участвовать. Принимающий узел идентифицируется из сортированного связанного списка и каждого разделенного подсписка. Сообщение присоединения направляется на узел обработки (например, исходя из идентификатора) в сортированном связанном списке и каждом разделенном подсписке. Отклик на присоединение принимается от узла обработки в сортированном связанном списке и каждом разделенном подсписке.

Фиг. 14 демонстрирует иллюстративную схему последовательности операций способа 1400 для узла, чтобы сохранять принадлежность к инфраструктуре объединения. Способ 1400 будет описан относительно кольца 1206. Способ 1400 включает в себя этап, на котором отправляют первое сообщение проверки связи на узел окрестности (этап 1401). Первое сообщение проверки связи указывает, что текущий узел, отправляющий первое сообщение проверки связи, является соседом узла окрестности. Первое сообщение проверки связи может также включать в себя состояние партнерского узла маршрутизации и узла окрестности текущего узла. Например, узел, имеющий идентификатор 144, может отправить сообщение проверки связи на узел, имеющий идентификатор 151. После приема первого сообщения проверки связи, узел, имеющий идентификатор 151, получает сведения о том, что узел, имеющий идентификатор 144, является соседом узла, имеющего идентификатор 151. Узел 151 может также обнаружить новейшую информацию живучести (для других узлов на кольце 1206) от узла 144 как побочный эффект этого этапа.

Сообщения проверки связи могут периодически повторяться с определенной частотой, исходя, например, из конфигурационной структуры, соотнесенной с ближайшим кольцом, в которое сообщение проверки связи должно быть отправлено. Частота может быть различной в зависимости от конфигурационной структуры. Например, заданная частота проверки связи для ГВС может быть отличной от заданной частоты для ЛВС. Сообщения проверки связи могут также отправляться в соответствии с моделью распространения проверки связи. Модель распространения проверки связи для вызывающего узла может указывать, что сообщения проверки связи должны быть отправлены на узлы окрестности в обоих направлениях на кольце. Например, узел, имеющий идентификатор 144, может отправить сообщения проверки связи и в направлении узла, имеющего идентификатор 135, и в направлении узла, имеющего идентификатор 151. Модели распространения проверки связи и частоты могут изменяться. Например, для каждого кольца соседства.

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

Принятое сообщение проверки связи может периодически повторяться/переправляться на другие узлы в пределах ближайшей окрестности, в которой проверка связи была порождена (отправлена вызывающим узлом). Переправляемые сообщения проверки связи могут также отправляться в соответствии с моделью распространения проверки связи. Модель распространения проверки связи для переправляющего узла может указывать, что сообщения проверки связи должны быть отправлены на узлы окрестности в направлении удаления от вызывающего узла. Например, узел, имеющий идентификатор 1151, может переправить сообщение проверки связи, порожденное на узле, имеющем идентификатор 144, в направлении узла, имеющего идентификатор 174. Модель распространения переправления проверки связи может изменяться, например, для каждого кольца соседства.

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

Способ 1400 включает в себя этап, на котором осуществляют кратчайшую маршрутизацию сообщения запроса обновления до идеального узла маршрутизации (этап 1403). Сообщение запроса обновления указывает узлу маршрутизации, принимающему такой направленный запрос обновления, что текущий узел участвует как партнер по маршрутизации принимающего узла маршрутизации. Сообщение запроса обновления может также включать в себя, по меньшей мере, именования узлов окрестности текущего узла (например, в форме информации живучести). Например, узел, имеющий идентификатор 144, может направить сообщение 1216 обновления на узел, имеющий идентификатор 208 (идеальный партнер по маршрутизации смещается на 64 от 144). Поскольку узел 210 (ранее вычисленный узел маршрутизации) является ближайшим к 208, он примет и обработает направленный запрос обновления. После приема сообщения 1216 обновления, узел, имеющий идентификатор 210, получит (или подтвердит) сведения о том, что узел, имеющий идентификатор 144, является партнером по маршрутизации узла, имеющего идентификатор 210.

Способ 1400 включает в себя этап, на котором принимают ответное сообщение обновления от обрабатывающего (принимающего) узла маршрутизации (этап 1404). Отклик на обновление указывает текущему узлу, что обрабатывающий узел маршрутизации участвует как партнер по маршрутизации текущего узла. Ответное сообщение обновления может также включать в себя, по меньшей мере, именования узлов окрестности обрабатывающего партнера по маршрутизации. Например, узел, имеющий идентификатор 210, может отправить отклик 1207 на обновление на узел, имеющий идентификатор 144. После приема отклика 1207 на обновление, узел, имеющий идентификатор 144, получает сведения о том, что узел, имеющий идентификатор 210, является партнером по маршрутизации узла, имеющего идентификатор 144.

Способ 1400 может также включать в себя этап, на котором соответственно обновляют информацию об узле, чтобы указать, что текущий узел и узел окрестности участвуют как соседи и что текущий узел и узел окрестности участвуют как партнеры по маршрутизации. Например, узел, имеющий идентификатор 144, может обновить информацию об узле, соответствующую узлу, имеющему идентификатор 151, чтобы указать, что узлы, имеющие идентификаторы 144 и 141, участвуют в (ближайшей) окрестности. Точно так же узел, имеющий идентификатор 144, может обновить информацию об узле, соответствующую узлу, имеющему идентификатор 210, чтобы указать, что узлы, имеющие идентификаторы 144 и 210 участвуют как партнеры по маршрутизации.

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

Идентификатор Экземпляра (например, целое число без знака) объекта владения. Должен быть, по меньшей мере, монотонно (>1) возрастающим.

Идентификатор последовательности (например, URI), идентифицирующий конкретную последовательность, генерируемую владельцем. Эта компонента дает возможность одному и тому же владельцу генерировать множественные независимые последовательности.

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

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

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

Фиг. 15 демонстрирует иллюстративную схему последовательности операций способа 1500 для обнаружения информации живучести для другого узла. Способ 1500 будет описан относительно кольца 1206, изображенного на Фиг. 12A и 12B. В общем случае, любое сообщение, такое, например, как синхронизации 1203, отклика 1204 на синхронизацию, обновления 1216, отклика 1207 на обновление и т.д., может включать в себя, по меньшей мере, один заголовок живучести. В некоторых вариантах осуществления заголовок живучести включает в себя <идентификатор узла, идентификатор экземпляра, фазу [значение фазового состояния].[индикатор неизвестная.фаза], значение свежести, значение цвета (соседства) и значение веса> для узла. В других вариантах осуществления заголовок живучести включает в себя <фазу [значение фазового состояния].[индикатор неизвестная.фаза], значение свежести, значение цвета (соседства) и значение веса>. В этих других вариантах осуществления заголовки живучести могут использоваться для дополнения заголовков адресации, которые уже включают в себя идентификатор узла и идентификатор экземпляра для отправляющего узла и узла-источника. Поскольку заголовки адресации уже включают в себя идентификатор узла и идентификатор экземпляра, эта информация может быть исключена из заголовка живучести.

Способ 1500 включает в себя этап, на котором принимают заголовок живучести, отображающий информацию о состоянии для узла, участвующего в инфраструктуре объединения (этап 1501). Заголовок живучести включает в себя, по меньшей мере, принятый идентификатор участвующего узла, принятый идентификатор экземпляра узла, принятое фазовое значение и принятое значение свежести. Например, узел, имеющий идентификатор 144, может принять первый заголовок живучести в отклике 1204 на синхронизацию от узла, имеющего идентификатор 151. Первый заголовок живучести может включать в себя <идентификатор участвующего узла, идентификатор экземпляра, фазовое значение [значение фазового состояния].[индикатор неизвестная.фаза], значение свежести, значение цвета (соседства) и значение веса> для узла, имеющего идентификатор 174. Значение фазового состояния (например, Введение, Синхронизация, Маршрутизация, Эксплуатация) идентифицирует отраженную фазу узла, имеющего идентификатор 174, на период первого значения свежести. Фазовое значение (например, фазовое состояние: [Введение, синхронизация, Маршрутизация, Эксплуатация], и неизвестная.фаза) идентифицирует отраженную и/или обнаруженную фазовую информацию узла, имеющего идентификатор 174, на период указанного первого значения свежести.

Однако значение свежести может снижаться из-за задержки связи. Кроме того, значение свежести может ослабляться с течением времени. Кривые спада для значения свежести могут отличаться (и могут не быть линейными или симметричными) для различных фазовых состояний (в том числе неизвестного). Таким образом, в различных фазах узла ослабление значения свежести может быть нелинейным и/или асимметричным.

Способ 1500 включает в себя этап, на котором организуют доступ, по меньшей мере, к идентификатору текущего экземпляра, текущему фазовому значению и текущему значению свежести для участвующего узла, сохраняемым на текущем узле (этап 1502). Например, узел, имеющий идентификатор 144, может получить доступ к ранее принятым и сохраненным идентификатору экземпляра, фазовому значению [значение фазового состояния].[индикатор неизвестная.фаза] и значению свежести для узла, имеющего идентификатор 174.

Способ 1500 включает в себя этап, на котором сравнивают, по меньшей мере, принятый идентификатор экземпляра, принятое фазовое значение и принятое значение свежести с текущим идентификатором экземпляра, текущим фазовым значением и текущим значением свежести соответственно на текущем узле (этап 1503). Например, узел, имеющий идентификатор 144, может сравнивать ранее принятые и сохраненные идентификатор экземпляра, фазовое значение [значение фазового состояния].[индикатор неизвестная.фаза] и значение свежести для узла, имеющего идентификатор 174, с идентификатором экземпляра, фазовым значением [значение фазового состояния].[индикатор неизвестная.фаза] и значением свежести, принятыми в заголовке живучести.

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

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

В некоторых вариантах осуществления может быть обнаружено, что связь с участвующим узлом, возможно, была потеряна. Например, узел, имеющий идентификатор 144, может обнаружить, что связь с узлом, имеющим идентификатор 151, была потеряна. Обратимся ненадолго к Фиг. 17, в ответ на предварительную подписку на события живучести 1701 (с конечной точкой узла, имеющего идентификатор 151) прикладной уровень 1752 может отправить событие 1703 снижения конечной точки (с конечной точкой узла, имеющего идентификатор 151) на функциональный уровень 1751. В этих вариантах осуществления такие обнаруженные условия живучести могут быть указаны в информации живучести с использованием индикатора Неизвестная.Фаза, устанавливаемого в значение истинно, наряду с последним известным значением Фазового состояния.

Способ 1500 может дополнительно включать в себя этап, на котором принимают сообщение, которое включает в себя второй заголовок живучести, от второго отличного узла в инфраструктуре объединения. Например, узел, имеющий идентификатор 144, может принять сообщение состояния (от узла, имеющего идентификатор 103, или какого-либо другого узла кольца 1206), которое включает в себя второй заголовок живучести. Второй заголовок живучести может включать в себя <идентификатор участвующего узла, второй идентификатор экземпляра, второе фазовое значение [значение фазового состояния].[индикатор неизвестная.фаза], второе значение свежести, второе значение цвета (соседства) и второе значение веса> для узла, имеющего идентификатор 174. Второе фазовое значение (например, фазовое состояние: [Введение, Синхронизация, Маршрутизация, Эксплуатация], и индикатор неизвестная.фаза) идентифицирует отраженную/обнаруженную фазу узла, имеющего идентификатор 174, на период второго значения свежести.

С другой стороны, вслед за приемом первого заголовка живучести, узел, имеющий идентификатор 144, может попытаться установить связь непосредственно с узлом, имеющим идентификатор 174. Если связь успешно установлена, узел, имеющий идентификатор 174, может возвратить сообщение (например, отклик на синхронизацию), содержащее идентификатор узла и второй идентификатор экземпляра в заголовке адресации и содержащее заголовок живучести, включающий в себя <второе фазовое значение, второе значение свежести, второе значение цвета (соседства) и второе значение веса>. Если обнаруживается сбой, узел, имеющий идентификатор 144, генерирует внутреннее изменение состояния живучести (например, свежесть = максимум, а индикатор неизвестная.фаза = истина) и обрабатывает изменение состояния, как будто изменение состояния было принято от другого узла. Такое изменение состояния имеет наибольшее значение свежести.

Способ 1500 может также включать в себя этап, на котором сравнивают второй идентификатор экземпляра, второе фазовое значение и второе значение свежести с текущим идентификатором экземпляра, текущим фазовым значением и текущим значением свежести соответственно (этап 1506). Например, после приема сообщения состояния от узла, имеющего идентификатор 103, узел, имеющий идентификатор 144, может определить, что текущая информация о состоянии для узла, имеющего идентификатор 151, устарела, на основании того, что (по порядку) второй идентификатор экземпляра больше, чем первый идентификатор экземпляра, вторая фаза является более продвинутой, чем первое фазовое значение, или второе значение свежести больше, чем первое фазовое значение.

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

В некоторых вариантах осуществления фазовые значения сравниваются в ситуации равных значений цвета. Как ранее описано, узел может участвовать во множественных кольцах соседства. Участие во множественных кольцах соседства может иметь место как результат участия в более частном кольце, подразумевающем участие в более общем кольце (по общему хребту). Например, возвращаясь к Фиг. 5, участие узла в кольце 532 также подразумевает, что узел участвует в кольцах 522, 511 и 501. Таким образом, цвет для более частного кольца отражает также все родительские ближайшие кольца. Кроме того, как ранее описано, участие во множественных кольцах соседства может иметь место, когда узел в одном кольце имеет псевдоним в одном или более других кольцах (возможно по различным хребтам). Например, по-прежнему обращаясь к Фиг. 5, узел, участвующий в кольце 532, может иметь псевдоним в кольце 531 (или даже кольце 541, что подразумевало бы участие в кольцах 531, 522, 511 и 501). Таким образом, цвет для одного кольца (например, кольца 531) может рассматриваться как равноправный цвет (или соседство) другого кольца (например, кольца 532).

Если узел участвует во множестве колец соседства с совмещением имен, есть некоторая вероятность, что фазовые значения (например, значения фазового состояния и/или индикаторы неизвестная.фаза) для узла будут различаться между разными кольцами соседства. Таким образом, узел, который принимает информацию о состоянии для другого узла, идентифицирует соответствующее кольцо соседства для информации о состоянии (цвет) перед определением, должна ли быть обновлена текущая информация о состоянии для такого узла и цвета. Например, узел, имеющий идентификатор 144, может идентифицировать соответствующее кольцо соседства для принятой информации о состоянии, соответствующей узлу, имеющему идентификатор 174, перед сравнением принятой информации о состоянии с текущей информацией о состоянии.

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

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

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

Механизмы Начальной Загрузки

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

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

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

Чтобы предоставить данные присутствия, поступления и организованные выходы первичных узлов могут регистрироваться в качестве постоянного узла входа при точке рандеву в каждой их окрестности. Например, регистрационные сообщения могут направляться на фиксированный URI, чей идентификатор назначения является результатом хеширования с использованием алгоритма SHA-1 строки "Соседство:/". В то время как в одном варианте осуществления первичные узлы выполняют функцию постоянных узлов входа, которые регистрируются таким способом, существуют другие варианты осуществления, где выбранные не являющиеся первичными узлы также могут регистрироваться таким же образом и с использованием таких же или подобных протоколов, описанных здесь для первичного узла. Когда постоянный узел входа (такой, как первичный узел) регистрируется, постоянный узел входа может указывать каждое кольцо, элементом которого он является. Таким образом, информация, сохраняемая в точке рандеву, идентифицируемой этим фиксированным URI, по существу является списком постоянных узлов входа и их принадлежности их соответствующим кольцам. Соответственно, любой узел может обратиться к точке рандеву, идентифицируемой этим фиксированным URI, чтобы получить список доступных постоянных узлов входа и их принадлежности их кольцам.

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

Продвижение данных присутствия постоянного узла входа по направлению к корневому кольцу позволяет другим узлам в объединении отыскать, по меньшей мере, один узел входа в каждой окрестности. Поиск Узла Входа может быть облегчен посредством маршрутизации сообщения поиска узла по направлению к вышеупомянутой определенной точке рандеву в Низшем Общем Родительском Кольце ("НОРК") концевого кольца узла, выполняющего поиск, и искомого кольца соседства. Например, обращаясь к Фиг. 5, узел в кольце 541 может пожелать установить связь с узлом в кольце 533. Однако узел в кольце 541 может не обладать полными сведениями о любом узле в кольце 533. Поэтому узел в кольце 541 может отправить Сообщение Поиска Узла в кольцо 522 (НОРК кольца 541 и кольца 533). Узел точки рандеву в кольце 522, который обрабатывает информацию присутствия узла входа (например, обусловливающую существование в системе в силу регистрационного сообщения, порожденного этим узлом входа), может возвратить Ответное Сообщение Поиска с контактной информацией, по меньшей мере, для зарегистрированного постоянного узла входа в кольце 533.

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

Взаимодействие Между Соседствами

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

Как изображено на Фиг. 5A, дополнение дерева 500 разбиения колец включает в себя различные подкольца под кольцом 513. Каждое из дополнительных подколец представляет часть сортированного связанного списка. Как ранее описано относительно Фиг. 5, в пределах дерева 500 разбиения корневое кольцо 501 разделяется на множество подколец, включающее в себя подкольца 511, 512, 513 и 514, на основании критерия 571 (первый критерий границы административной области). Кроме того, ранее описано относительно Фиг. 5, подкольцо 511 может быть дополнительно разделено на множество подколец, включающее в себя подкольца 521, 522 и 523, на основании критерия 581 (второй критерий границы административной области). Другие подкольца под подкольцом 522 дополнительно разделяются на основании другого критерия.

Как ранее описано, в пределах дерева 500 разбиения каждый узел имеет единственный идентификатор и участвует в кольцах по соответствующему пути разбиения (хребет), начиная от корня до концевой вершины. Например, каждый узел, участвующий в подкольце 552, также будет участвовать в подкольцах 543, 531, 522, 511 и в корне 501.

На Фиг. 5A подкольцо 513 также может быть дополнительно разделено на множество подколец, включающее в себя подкольца 561 и 562, на основании другого критерия, такого, например, как юрисдикция штата. Подкольцо 562 может быть дополнительно разделено на множество подколец, включающее в себя подкольца 571 и 572, на основании другого критерия, такого, например, как юрисдикция города. Соответственно, на Фиг. 5A взаимодействие между соседствами может использоваться, чтобы отправить сообщение от узла кольца 541 на узел кольца 572, не требуя установления восходящей связи по хребту от кольца 541 до корневого кольца 501, а затем обратной нисходящей связи от корневого кольца 501 до кольца 572.

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

Фиг. 19A демонстрирует иллюстративное порожденное соседством дерево разбиения колец 1900, которое облегчает взаимодействие между соседствами. В пределах дерева разбиения колец 1900 корневое кольцо 1901 разделяется на множество подколец, включающее в себя подкольца 1, 2, 3 и 4, на основании выбранного критерия (например, первый критерий границы административной области). Подкольцо 1 дополнительно разделяется на подкольца 11, 21, 31 и 41. Подкольцо 11 дополнительно разделяется на подкольца 111, 211 и 311. Подкольцо 21 дополнительно разделяется на подкольца 121, 221, 321, 421 и 521. Хотя явно не изображено, другие подкольца, такие, например, как подкольца 2, 3, 4, 31 и 41, также могут быть дополнительно разделены.

Правило нумерации колец в порожденном соседством дереве разбиения колец 1900 выбрано так, что любые цифры после первой цифры обозначают родительское кольцо кольца. Например, "11" в кольце "311" означает, что кольцо 11 является родительским кольцом для кольца 311. Точно так же "1" в кольце "41" означает, что кольцо 1 является родительским кольцом для кольца 41. Общее кольцо 1901 является родительским кольцом для любых колец, пронумерованных единственной цифрой, таких, например, как кольца 1, 2, 3 и 4. Подобно порожденному соседством дереву разбиения колец 500, изображенному на Фиг. 5A, дерево разбиения колец 1900 может быть разделено, на основании различных критериев соседства.

В настоящем описании и последующей формуле изобретения комментарий R["<число>"] используется для указания номера кольца. Например, R["11"] относится к кольцу 11. В настоящем описании и последующей формуле изобретения комментарий N[<номер>] используется для указания номера узла. Например, N[1311] относится к узлу 1311.

Для облегчения взаимодействия в дереве колец, узлы могут сохранять таблицу входов, которая сопоставляет кольца с соответствующими узлами входа в этих кольцах. Как ранее описано, исходя из конфигурации дерева разбиения колец 1900, родительское кольцо содержит все узлы из каждого из своих дочерних колец. Например, кольцо 11 содержит все узлы из R["111"], R["211"] и R["311"]. Таким образом, отправка сообщения в кольцо 11 достаточна для получения сообщения на любом узле в кольце R["111"], R["211"] и R["311"]. Соответственно, в некоторых вариантах осуществления таблица входа узла может сводиться к входам для тех колец, которые относительно отличаются с позиции кольца, в котором располагается узел. Например, N[1111] может просто сохранять вход для R["21"] - N[1121], поскольку сохранение входов для множественных дочерних колец или R["21"] было бы избыточно.

Создание и Сохранение Множества Боковых Колец

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

Таким образом, например, по-прежнему обращаясь к Фиг. 19A, R["211"] является боковым кольцом для R["111"], так как R["211"] является равноправным относительно R["111"]. R ["211"] также является боковым кольцом для любого узла, входящего в R["111"], такого, например, как N[1311]. Дополнительно, R["21"] является боковым кольцом для R["111"], так как R["21"] является равноправным относительно R["11"] (т.е. родителя R["111"]). R["21"] также является боковым кольцом для любого узла, входящего в R["111"], такого, например, как N[1111].

В настоящем описании и последующей формуле изобретения "множество боковых колец" ("МБК") определяется как набор из одного или более боковых колец с позиции определенного кольца или узлов в пределах определенного кольца. Например, на Фиг. 19A множество боковых колец для R["221"], а также для любых узлов в R["221"], таких, например, как N[8221], включает в себя R["11"], R["121"], R["31"], R["41"], R["2"], R["3"] и R["4"].

Таким образом, чтобы облегчить взаимодействие между соседствами, узел может сохранять таблицу входов МБК, которая включает в себя одно или более боковых колец и один или более соответствующих узлов входа в эти одно или более боковых колец. Таблица входов МБК может быть структурой данных, включающей в себя один или более элементов вида <боковое кольцо, 1 - N узлов входа>, где N является некоторым целым числом. Например, структура данных может иметь формат <боковое кольцо_01, узел входа_01, узел входа_02, …>, где многоточие обозначает один или более дополнительных узлов входа в боковое кольцо_01.

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

Узел может использовать локальные сведения, такие, например, как информация таблицы маршрутизации, от всех уровней колец, в которых узел участвует. Например, по-прежнему обращаясь к Фиг. 19, N[1121] может быть соседом N[1311] в R["1"]. Одним боковым кольцом для N[1311] с позиции N[1121] является R["21"]. Соответственно, N[1311] может ввести пару (R["21"], N[1121]) (в этом случае элемент, имеющий единственный узел входа) в таблицу входов МБК узла N[1121]. Используя локальные сведения такого типа, узел может ввести входы в таблицу входов МБК.

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

Например, когда узел обменивается сообщениями Проверки Связи/Обновления Рандеву со своими соседними/партнерскими узлами (например, на уровне протокола рандеву), узел может также делиться (по меньшей мере, частью, а возможно всей) своей таблицей входов МБК и использовать структуру таблицы входов МБК, принятую от своих соседей/партнеров, для обновления своей собственной таблицы. Предположим, например, что N[1311] не имеет предварительных сведений о каком-либо узле в R["3"] (в пределах контекста или кольца 1901). Однако N[1311] имеет соседа N[8221] (в R["1"]), и таблица входов МБК узла N[8221] содержит вход (R["3"], N[8223]). По меньшей мере, поскольку N[1311] и N[8221] являются соседями, N[1311] и N[8221] могут время от времени отправлять друг другу сообщения проверки связи. N[8221] может включать (по меньшей мере, часть, а возможно всю) свою таблицу входов МБК в состав сообщений проверки связи, которые отправляются на N[1311]. Таким образом, когда N[1311] принимает сообщение проверки связи от N[8221], сообщение проверки связи может включать в себя таблицу входов МБК узла N[8221]. Благодаря таблице входов МБК узла N[8221] N[1311] может идентифицировать элемент <R["3"], N[8223], …> и включить элемент <R["3"], N[8223], …>) в состав своей собственной таблицы входов МБК. N[1311] также может идентифицировать другие элементы для других колец в своем МБК и включать эти другие элементы в состав своей собственной таблицы входов МБК.

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

Структура таблицы входов МБК также может быть получена в сообщениях, которые содействуют определенным моделям связи (например, широковещания, группового вещания и вещания любому из группы получателей) в дереве колец. Например, для широковещания сообщения на каждый узел в дереве колец, алгоритм широковещания может использовать различные типы сообщений, которые являются специализированными для широковещания. Узлы, которые отправляют эти специализированные сообщения широковещания, могут вкладывать структуру таблицы входов МБК в специализированные сообщения широковещания. Аналогично, когда при групповом вещании сообщения на каждый узел в группе узлов алгоритм группового вещания может использовать различные типы сообщений, которые являются специализированными для группового вещания. Узлы, которые отправляют эти специализированные сообщения группового вещания, могут вкладывать структуру таблицы входов МБК в специализированные сообщения группового вещания. Точно так же при вещании любому из группы получателей сообщения, по меньшей мере, на один узел алгоритм вещания любому из группы получателей может использовать различные типы сообщений, которые являются специализированными для вещания любому из группы получателей. Узлы, которые отправляют эти специализированные сообщения вещания любому из группы получателей, могут вкладывать структуру таблицы входов МБК в специализированные сообщения вещания любому из группы получателей. Узлы, которые принимают специализированные для модели связи сообщения, могут идентифицировать соответствующие входы (например, элементы вида <боковое кольцо, узлы входа>) и включать некоторые или все структуры из этих входов в состав своей собственной таблицы входов МБК.

Структура МБК также может быть получена в сообщениях прикладных компонентов, обмен которыми происходит между приложениями. Обратимся ненадолго к Фиг. 1, прикладные уровни 121, 122 и/или 123 могут обмениваться сообщениями прикладных компонентов, которые включают в себя структуру МБК. После приема сообщения прикладных компонентов, включающего в себя структуру МБК, прикладной уровень может передать структуру МБК вниз на соответствующие другие нижние уровни, такие, например, как уровень протокола рандеву, для дополнения существующей структуры МБК.

Структура МБК может быть предусмотренным и/или аппаратно реализованным приложением и конфигурируемым с помощью узлов в дереве колец.

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

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

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

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

Таблица входов МБК может быть или не быть полной. Полная таблица входов МБК включает в себя, по меньшей мере, один узел входа для каждого кольца в МБК узла. Например, полная таблица входов МБК для узла 1311 включала бы в себя, по меньшей мере, один узел входа в каждое из колец 111, 211, 21, 31, 41, 2, 3 и 4.

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

Однако в других распределенных сетевых средах динамическая природа кольца и/или задержка при обмене структурой, связанной с таблицей входов, могут препятствовать составлению полной таблицы входов. Иными словами, в этих других средах могут существовать одно или более колец из множества боковых колец для кольца или узла, о которых эти узел или кольцо не знают в данное время. Например, обращаясь снова к Фиг. 19A, предположим, что N[8004] только что присоединился и до этого не существовало узла, принадлежащего R["4"], большинство узлов не будут обладать узлом входа для R["4"] до обмена сообщениями (например, сообщениями Проверки Связи/Обмена) или других действий, приводящих к распространению этой информации на всю кольцевую инфраструктуру. Таким образом, сохранение полной таблицы входов МБК на узле не всегда возможно вследствие динамизма сети (например, из-за отказов узлов, сбоев связи, задержек связи, добавлений узлов и т.д.). Соответственно, во многих средах узел сохраняет частичную таблицу входов МБК, включающую в себя узлы входа не для всех колец в МБК узла.

Взаимодействие Между Соседствами С Использованием
Таблицы Входов МБК

Узел может использовать информацию в таблице входов МБК для отправки информационного сообщения между соседствами (например, без необходимости направления сообщения в НОРК отправляющего кольца и кольца назначения). По-прежнему обращаясь к Фиг. 19A, на основании соответствующих входов в таблице входов МБК N[1311] (например, узел издателя) может иметь возможность отправить информационное сообщение между соседствами непосредственно в одно или более из R["111"], R["211"], R["21"], R["31"], R["41"], R["2"], R["3"] и R["4"]. Например, в некоторый момент времени таблица входов МБК для N[1311] может включать в себя следующие входы:

R["2"]:N[1112]

R["3"]:N[8223]

R["21"]:N[1121]

R["31"]:N[1131]

R["111"]:N[1111]

R["211"]:N[1211].

Эти входы могут использоваться для прямой связи с R["111"], R["211"], R["21"], R["31"], R["2"] и R["3"]. Например, N[1311] может отправить информационное сообщение 52 в R["111"], N[1311] может отправить информационное сообщение 51 в R["211"], N[1311] может отправить информационное сообщение 53 в R["21"] (N[1121] принадлежит и R["21"] и R["221"]), N[1311] может отправить информационное сообщение 56 в R["31"], N[1311] может отправить информационное сообщение 57 в R["2"] и N[1311] может отправить информационное сообщение 58 в R["3"]. С течением времени N["1311"] может идентифицировать входы (например, элементы вида <боковое кольцо, узел входа>) для R["41"] и R["4"]. Эти входы могут быть идентифицированы, исходя из обновленных локальных сведений, из таблиц входов МБК, содержащихся в сообщениях протокола рандеву (например, сообщениях проверки связи, сообщении обновления и откликах на обновление), при помощи структуры таблицы входов МБК, содержащейся в специализированных для модели связи сообщениях, и при помощи других механизмов, таких, например, как прикладной компонент.

Нисходящий Алгоритм Маршрутизации

В объединении с поддержкой механизма рандеву (с использованием или без таблиц входов МБК) возможно, что сообщение должно быть направлено на узел, ближайший к заданному идентификатору узла в пределах определенного кольца соседства, которое не является родителем (или располагается внутри) концевого кольца, где было порождено сообщение (в дальнейшем именуется как "нисходящая маршрутизация"). Один пример этого содействует взаимодействию между соседствами со стороны узла в вызывающем кольце к боковому кольцу, когда узлу в вызывающем кольце неизвестен узел входа для бокового кольца. Фиг. 19B демонстрирует другое представление иллюстративного порожденного соседством дерева разбиения колец 1900. Например, обращаясь теперь к Фиг. 19B, возможно, что N[1311] должен отправить информационное сообщение, предназначенное для узла в R["4"] или R["41"].

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

Маршрутизация_Вниз(М, P, Идентификатор): объединение должно доставить сообщение М на узел, ближайший к Идентификатору в соседстве P. Соседство P может быть любым кольцом соседства в объединении (концевой или промежуточной вершиной), которое не является родителем (или располагается внутри) концевого кольца вызывающего узла.

В некоторых вариантах осуществления сообщение М никогда не маршрутизируется выше узлов в пределах НОРК концевого кольца вызывающего узла и целевого кольца P соседства. Например, чтобы реализовать нисходящую маршрутизацию от N[1311] к R["41"], может отсутствовать необходимость в маршрутизации сообщения выше R["1"] (НОРК для R["311"] и R["41"]). Однако в других вариантах осуществления при необходимости сообщение может маршрутизироваться выше НОРК.

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

Отправляющий узел может использовать локальные сведения, такие, например, как конфигурация или локально сохраненная в кэш-памяти информация (например, в дополнение к таблице входов МБК), для идентификации узла входа для целевого кольца соседства. Например, N[1311] может иметь доступ к содержимому кэш-памяти и конфигурации 1902, которые включают в себя конфигурацию или локально сохраненную в кэш-памяти информацию о кольцах в дереве колец 1900. В некоторых средах локальные сведения об объединении получаются при помощи внешних для объединения механизмов (т.е. извне). Локальные сведения могут использоваться для идентификации каких-либо узлов строго в целевом кольце P соседства. Если какие-либо узлы строго в целевом кольце P соседства найдены, сообщение M может быть переправлено на один из них. Например, N[1311] может иметь возможность использовать кэш-память и конфигурацию 1902 для идентификации N[8004] и переправлять сообщение 1903 в R["4"].

Отправляющий узел может использовать таблицу входов МБК для обнаружения местоположения каких-либо узлов входа в целевое кольцо P соседства. Если какие-либо узлы входа в целевое кольцо соседства найдены, сообщение М может быть переправлено на узел входа в целевое кольцо P соседства. Например, когда N[7521] является назначением для сообщения 1903, N[1311] может идентифицировать N[6521] как узел входа для R["521"]. Соответственно, сообщение 1903 может быть направлено на N[6521] (или в R["521"]). Затем внутри R["521"] N[6521] может попытаться направить сообщение 1903 на N[7521], используя связь внутри кольца. Таким образом, если отправляющий узел в состоянии идентифицировать узел входа для целевого кольца соседства, он переправляет сообщение строго в целевое кольцо соседства. Например, если N["6521"] в состоянии идентифицировать узел входа для R["21"], он переправляет сообщение 1903 в R["21"] (пунктирная линия).

С другой стороны, когда отправляющий узел неспособен идентифицировать какие-либо узлы входа целевого соседства назначения (например, из локальных сведений или таблицы входов МБК), отправляющий узел может проверить свою таблицу входов МБК для определения местоположения узлов входа для каких-либо родительских колец по отношению к целевому кольцу соседства. Например, возможно, что N[1311] попытается отправить сообщение на узел в R["121"], однако N[1311] может быть не в состоянии идентифицировать узел входа для R["121"]. Соответственно, N[1311] может обратиться к таблице 1904 входов МБК, чтобы определить местонахождение N[6521] (узла входа в R["21"]). N[1311] может переправить сообщение на N[6521], который теперь становится отправляющим узлом для сообщения.

Логически рассуждая, сообщение 1903 может теперь рассматриваться как находящееся "в" R["21"], так как N[6521] также является узлом кольца R[21]. Затем N[6521] может попытаться идентифицировать узел входа в R[221] (целевое соседство). Например, N[6521] может обратиться к локальным сведениям, таблице входов МБК, и/или может (рекурсивно) применить алгоритм Маршрутизация_Вниз. Возможно, что N[6521] идентифицирует N[3221] как узел входа в R[221]. Соответственно, N[6521] может отправить сообщение 1903 на N[3221]. Затем N[3321] может направить сообщение 1903 на соответствующий узел в R[221], используя связь внутри кольца.

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

Отправляющий узел может также направить Запрос Поиска Узла Входа, содержащий, по меньшей мере, целевое соседство запроса, справочному механизму узлов входа, такому, например, как используемый для начальной загрузки объединения. Маршрутизация Запроса Поиска Узла Входа может быть ограничена НОРК отправляющего узла и целевого кольца. Например, N[1311] может направить Запрос Поиска 1906 в точку 7651 рандеву, чтобы запросить узлы входа для R["31"]. Справочный механизм узлов входа может возвратить список вероятных узлов входа. Например, точка 7651 рандеву может возвратить список вероятных узлов входа (в том числе N[8431]) и, по меньшей мере, первичные узлы, зарегистрированные в этой точке рандеву для целевого соседства в отклике 1907 на поиск.

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

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

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

Если какой-либо из вышеупомянутых механизмов идентифицирует множественные узлы "следующего перехода", может быть выбран единственный узел. При выборе единственного узла (например, обрывая соединение) могут быть выбраны узлы, которые находятся ближе к целевому соседству P, затем могут быть выбраны узлы с более высоким весом, затем узлы могут быть выбраны, которые находятся ближе к идентификатору назначения сообщения М. Если механизмы не дают в результате выбор, то узел может быть выбран случайным образом. Если произошла неудачная попытка отправить сообщение M при наличии множественных кандидатов, переотправка может предприниматься повторно, пока имеются не признанные неисправными узлы-кандидаты.

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

Фиг. 19C демонстрирует секционированное представление части иллюстративного порожденного соседством дерева разбиения колец 1900. Фиг. 19D демонстрирует расширенное представление кольца 11 из иллюстративного порожденного соседством дерева разбиения колец 1900. Фиг. 20 демонстрирует иллюстративную схему последовательности операций способа 2000 для сохранения множества боковых колец для узла в дереве колец. Способ 2000 будет описан относительно колец, узлов, сообщений и данных, изображенных на Фиг. 19C и 19D.

Способ 2000 включает в себя этап, на котором организуют доступ узла к таблице входов множества боковых колец, сконфигурированной для хранения входов множества боковых колец для узла (этап 2001). Каждый вход множества боковых колец сконфигурирован для указания бокового кольца этого узла и, по меньшей мере, одного соответствующего узла входа в боковое кольцо для этого узла. Например, N[1311] может получить доступ к таблице 1904 входов МБК, которая сконфигурирована для хранения входов множества боковых колец, в формате <боковое кольцо, 1-N узлов входа>, где N является некоторым целым числом, для N[1311]. Таким образом, таблица 1904 входов МБК может включать в себя ноль или более элементов вида <боковое кольцо, узел входа>, причем каждый содержащийся элемент обозначает боковое кольцо для N[1311] и один или более соответствующих узлов входа в это боковое кольцо. Например, как изображено на Фиг. 19C, таблица 1904 входов МБК включает в себя вход МБК <R["51"], N[8651], …> указывающий, что N[8651] является одним из 1-N узлов входа в R[51] (боковое кольцо для N[1311] и R["311"]).

Способ 2000 включает в себя этап, на котором получают информацию таблицы входов множества боковых колец из доступных ресурсов, которые сохраняют информацию, связанную с конфигурацией дерева колец (этап 2002). Например, N[1311] может получить информацию таблицы входов множества боковых колец из источников, которые сохраняют информацию, связанную с конфигурацией дерева колец 1900. Как ранее описано, узлу могут быть доступны различные другие источники информации таблицы входов МБК. Например, узел может иметь доступ к локальным сведениям, таким, например, как локальная конфигурация и информация в кэш-памяти, может иметь доступ к связанному с МБК состоянию, включенному в состав сообщений протокола рандеву, таких, например, как сообщения проверки связи, сообщения обновления и отклики на обновление, используемые для распространения состояния в дереве колец, может иметь доступ к связанному с МБК состоянию, включенному в состав прикладных сообщений, и может иметь доступ к связанному с МБК состоянию из сообщений, используемых для содействия определенным моделям связи, таким, например, как широковещание, групповое вещание и вещание любому из группы получателей, в дереве колец.

Итак, на Фиг. 19C, возможно, что N[1311] имеет доступ к локальной конфигурации 1921. Благодаря локальной конфигурации 1921 N[1311] может обнаружить вход МБК <R["111"], N[1111], …>, указывающий, что N[1111] является, по меньшей мере, одним из узлов входа в R["111"] (боковое кольцо для N[1311] и R["311"]). N[1311] может также принять прикладное сообщение 1971. Благодаря прикладному сообщению 1971 N[1311] может обнаружить информацию 1972 МБК. Информация 1972 МБК может содержать или не содержать структуру МБК для Колец в МБК узла N[1311]. N[1311] может также принять специализированное для модели связи сообщение 1973. Благодаря специализированному для модели связи сообщению 1973 N[1311] может обнаружить структуру 1974 МБК. Структура 1974 МБК может содержать или не содержать структуру МБК для Колец в МБК узла N[1311].

Обратимся теперь к Фиг. 19D, N[1311] может обнаруживать и обмениваться структурой МБК в сообщениях протокола рандеву. Поскольку N[1111] принадлежит R["111"], N[1211] принадлежит R["211"] и N[1311] принадлежит R["311"], каждый из узлов N[1111], N[1211], N[1311] также принадлежит R["11"]. Как ранее описано, узлы, которые принадлежат общему кольцу, могут обмениваться сообщениями проверки связи, сообщениями обновления и откликами на обновление для сохранения информации таблицы маршрутизации. Следовательно, узлы кольца R["11"] могут обмениваться сообщениями проверки связи, сообщениями обновления и откликами на обновление для сохранения информации таблицы маршрутизации для R["11"]. Структура МБК может быть включена в состав обменных сообщений проверки связи, сообщений обновления и откликов на обновление, а также других сообщений протокола рандеву и прикладных сообщений потока информационного обмена между узлами.

Например, N[A11] (сосед N[1311] в R["11"]) может отправить сообщение 1931 проверки связи, включающее в себя структуру 1932 МБК, на N[1311]. Благодаря структуре 1932 МБК N[1311] может обнаружить вход МБК <R["31"], N[1131]>, указывающий, что N[1131] является узлом входа в R["31"] (боковое кольцо для N[1311] и R["311"]). Входы 1932 МБК могут представлять собой полный или частичный список входов МБК в таблице входов МБК узла N[A11]. N[1311] может также отправить сообщения проверки связи, включающие в себя структуру МБК, своим соседям. Например, N[1311] может отправить сообщение 1945 проверки связи, включающее в себя структуру 1934 МБК, на N[E11] (сосед N[1311] в R["11"]). Входы 1934 МБК могут включать в себя полный или частичный список входов МБК из таблицы 1904 входов МБК.

N[1311] может также отправлять и принимать сообщения обновления и отклики на обновление, которые включают в себя связанную с МБК информацию. Например, N[1311] может отправить сообщение 1933 обновления, включающее в себя входы 1934 МБК, на N[D11] (партнер по маршрутизации для N[1311] в R["11"]). N[D11] может ответить путем отправки отклика 1937 на обновление, включающего в себя входы 1938 МБК, на N[1331]. Входы 1938 МБК могут представлять собой полный или частичный список входов МБК в таблице входов МБК узла N[D11]. Аналогично, N[1311] может принять сообщение 1941 обновления, включающее в себя входы 1942 МБК, от N[C11] (партнера по маршрутизации для N[1311] в R["11"]). Входы 1942 МБК могут представлять собой полный или частичный список входов МБК в таблице входов МБК узла N[C11]. N[1331] может ответить путем отправки отклика 1943 на обновление, включающего в себя входы 1934 МБК, на N["C11"].

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

Способ 2000 включает в себя этап, на котором обновляют таблицу входов множества боковых колец в зависимости от соответствующей структуры входов множества боковых колец, на основании полученной информации таблицы входов множества боковых колец (этап 2003). Каждая соответствующая структура входов множества боковых колец включает в себя боковое кольцо узла и, по меньшей мере, один соответствующий узел входа в боковое кольцо узла. Например, N[1311] может включить любые принятые входы МБК, как изображено на Фиг. 19C и 19D, в таблицу 1904 входов МБК. N[1311] может также удалить любые входы МБК из таблицы 1904 входов МБК, которые обозначены (например, в конфигурации, сообщениях протокола рандеву, прикладных сообщениях или специализированных для модели связи сообщениях) как возможно больше не являющиеся подходящими. Соответственно, таблица входов МБК узла может быть обновлена, чтобы надлежащим образом отражать изменяющееся строение объединения с поддержкой механизма рандеву.

Фиг. 19E демонстрирует еще одно представление иллюстративного порожденного соседством дерева разбиения колец 1900. На Фиг. 19E изображена Таблица 1904 входов МБК, которая может быть заполнена, исходя из структуры МБК, обмен которой изображен на Фиг. 19C и 19D. Фиг. 21 демонстрирует иллюстративную схему последовательности операций способа 2100 для отправки информационного сообщения между соседствами в дереве колец. Способ 2100 будет описан относительно узлов, колец, сообщений и данных, изображенных на Фиг. 19F.

Способ 2100 включает в себя этап, на котором определяют, что узел должен отправить сообщение в боковое кольцо этого узла (этап 2101). Например, N[1311] может принять указание, что он должен отправить сообщение 1976 в R["2"]. Указание, что сообщение должно быть отправлено боковому кольцу, может быть принято от другого узла, что подразумевается функцией логики маршрутизации, приложения на N[1311], средства группового вещания, средства широковещания, средства вещания любому из группы получателей и т.д.

Способ 2100 включает в себя этап, на котором организуют доступ узла к таблице входов множества боковых колец, сконфигурированной для хранения входов множества боковых колец для этого узла (этап 2102). Каждый вход множества боковых колец сконфигурирован для указания бокового кольца этого узла и, по меньшей мере, одного соответствующего узла входа в боковое кольцо для этого узла. Например, N[1311] может получить доступ к таблице 1904 входов МБК. Каждый вход МБК в таблице 1904 входов МБК может указывать боковое кольцо для N[1311] и, по меньшей мере, один соответствующий узел входа в это боковое кольцо для N[1311]. Например, вход <R["111"], N[1111], …> указывает, что R["111"] является боковым кольцом для N[1311], и N [1111] является одним из, по меньшей мере, одного узлов входа в R["111"].

Способ 2100 включает в себя этап, на котором идентифицируют, по меньшей мере, один вход множества боковых колец для бокового кольца из таблицы входов множества боковых колец узла (этап 2103). Каждый, по меньшей мере, один вход множества боковых колец указывает, по меньшей мере, один узел входа бокового кольца. Например, N[1311] может идентифицировать вход <R["2"], N[1112], …> для R["2"] из таблицы 1094 входов МБК. Вход <R["2"], N[1112], …> указывает, что N[1112] (а возможно, и другие узлы) является узлом входа для R["2"].

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

Способ 2100 включает в себя этап, на котором отправляют сообщение, по меньшей мере, на один указанный узел входа (этап 2104). Например, N[1311] может отправить сообщение 1976 на N[1112]. Отправка сообщения, по меньшей мере, на один узел может включать в себя отправку сообщения на все узлы входа во множестве узлов, на каждый узел входа в выделенном соответствующем подмножестве узлов входа или на единственный соответствующий узел входа. В некоторых вариантах осуществления, когда происходит сбой передачи сообщения для одного узла входа, могут быть опробованы один или более других узлов входа. Кроме того, имеется возможность для отправляющего узла идентифицировать новые узлы в результате сбоя.

Фиг. 22 демонстрирует иллюстративную схему последовательности операций для способа 2200 для отправки информационного сообщения между соседствами в дереве колец. Способ 2200 будет описан относительно узлов, колец, сообщений и данных, изображенных на Фиг. 19F и 19G.

Способ 2200 включает в себя этап, на котором определяют, что вызывающий узел намеревается направить сообщение на узел назначения, который является ближайшим к заданному идентификатору узла в целевом кольце соседства в пределах дерева колец (этап 2201). Целевое кольцо соседства может быть боковым кольцом вызывающего узла или подкольцом бокового кольца вызывающего узла. Например, N[1311] может принять указание, что он должен направить сообщение 1998 в R["1221"] (целевое кольцо соседства) по направлению к идентификатору 30. Указание того, что сообщение должно быть отправлено для бокового кольца или подкольца бокового кольца, может быть принято от другого узла, приложения, связанного с N[1311], средства группового вещания, средства широковещания, средства вещания любому из группы получателей и т.д.

Способ 2200 включает в себя этап, на котором идентифицируют один или более узлов входа, являющихся узлами, принадлежащими, по меньшей мере, или целевому кольцу соседства, или родительскому кольцу целевого кольца соседства (этап 2202). Например, N[1311] может идентифицировать N[41221], имеющий идентификатор 56 узла, как узел входа в R["1221"]. Для идентификации N[41221] может использоваться ряд различных механизмов. N[1311] может обратиться к локальным сведениям, чтобы попытаться идентифицировать узел входа в целевое кольцо соседства. Например, N[1311] может обратиться к содержимому кэш-памяти и конфигурации 1902, чтобы попытаться идентифицировать узел входа в R["1221"].

N[1311] может также обратиться к таблице входов МБК, чтобы идентифицировать узлы входа в родительские кольца целевого кольца соседства (например, когда узел входа в целевое кольцо соседства не идентифицирован). Возможно, что подкольцо R["321"] предоставляет N[4321] в качестве узла входа в R["21"]. Точно так же, возможно, что R["2221"] предоставляет узел N[12221] в качестве узла входа в R["221"]. Если узел входа в R[1221] не идентифицирован, N[1311] может попытаться идентифицировать узел входа в R["221"], такой, например, как N[12221]. N[1331] также может попытаться идентифицировать узел входа в R["21"], такой, например, как N[4321].

Возможно, что узел попытается идентифицировать узлы входа в более ближние родительские кольца перед попыткой идентифицировать узлы входа для более отдаленных родителей с позиции определенного целевого соседства, если узел входа в целевое соседство не идентифицирован. Например, если узел входа в R["1221"] не идентифицирован, N[1311] может сначала попытаться идентифицировать узел входа в R["221"]. Если узел входа в R["221"] не идентифицирован, N[1311] может затем попытаться идентифицировать узел входа в R["21"].

Кроме того, N[1311] может использовать механизмы начальной загрузки, такие, например, как первичные узлы. Например, N[1311] может направить запрос поиска узла входа в известную точку рандеву, такую, например, как точка рандеву N[7651], запрашивая известные (зарегистрированные) узлы входа (первичные узлы, являющиеся примером). В ответ на запрос поиска точка рандеву может возвратить (отправить) ответное сообщение поиска, включающее в себя любые известные узлы входа. Например, отклик 1997 на поиск может быть возвращен от точки рандеву N[7651] на N[1311]. Отклик 1997 на поиск может включать в себя местоположения любых узлов входа, зарегистрированных в точке рандеву N[7651].

Один или более из этих механизмов может идентифицировать N[4221] в качестве узла входа в R["221"].

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

Способ 2200 включает в себя этап, на котором отправляют сообщение на идентифицированный узел входа (этап 2203). Сообщение указывает, что узел входа должен привести сообщение к узлу, который имеет идентификатор узла, ближайший к указанному узлу назначения в целевом кольце соседства. Например, как обозначено сплошной линией, N[1311] может отправить сообщение 1998 на N[41221] (узел входа в R["1221"] и имеющий Идентификатор 56 Узла) с указанием, что сообщение должно быть приведено к идентификатору 30 узла. N[41221] может получить доступ к своей таблице маршрутизации и/или окрестности для определения ближайшего идентификатора узла к идентификатору 30 узла, чтобы узнать, что им является N[61221], имеющий идентификатор 25 узла. Точно так же N[61221] может получить доступ к своей таблице маршрутизации и/или окрестности для определения ближайшего идентификатора узла к идентификатору 30 узла, чтобы узнать, что им является N[71221], имеющий идентификатор 28 узла. N[71221] может обратиться к своей таблице и/или окрестности для определения, что его идентификатор узла, идентификатор 28 узла, является ближайшим известным идентификатором узла по отношению к идентификатору 30 узла, и доставить сообщение.

Ранее описанные алгоритмы маршрутизации также могут использоваться для маршрутизации сообщения 1998 в пределах R["221"].

Когда сообщение отправляется на идентифицированный узел входа, который принадлежит родительскому кольцу или целевому кольцу соседства, способ 2200 может рекурсивно применяться на идентифицированном узле входа. То есть идентифицированный узел входа в родительское кольцо может в свою очередь попытаться идентифицировать узел входа в целевое кольцо соседства. Например, как обозначено пунктирными линиями, возможно, что применение способа 2200 приведет к отправке сообщения 1998 на узел входа N[12221] (узел входа для R["221"], который предоставлен подкольцом R["2221"]). N[12221] (с позиции R["2221"]) может затем идентифицировать узел входа в R["1221"]. Таким образом, рекурсивное применение способа 2200 на N[12221] может привести к отправке сообщения 1998 на N[41221].

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

Например, как обозначено пунктирными линиями, возможно, что применение способа 2200 приводит к отправке сообщения 1998 на узел входа N[4321] (узел входа для R["21"], который предоставлен подкольцом R["321"]). Однако N[4321] (с позиции R["321"]) может быть не в состоянии идентифицировать узел входа в R["1221"]. Следовательно, N[4321] (с позиции R["321"]) может идентифицировать узел входа в R["221"]. Соответственно, первое рекурсивное применение способа 2200 на N[4321] может привести к отправке сообщения 1998 на N[12221]. Второе рекурсивное применение способа 2200 на N[12221] может затем привести к отправке сообщения 1998 на N[41221].

Однако, если бы N[4321] идентифицировал узел входа в R["1221"], он мог бы отправить сообщение 1998 непосредственно на этот узел входа. Таким образом, узел входа в родительское кольцо может отправить сообщение в целевое кольцо соседства или на узел входа ближнего родительского кольца целевого кольца соседства (которое, как правило, входит в МБК переправляющего узла входа), в зависимости от ситуации. Как описано, затем узел входа в ближнее родительское кольцо может переправить сообщение в целевое кольцо соседства или в еще более ближнее родительское кольцо целевого кольца соседства (которое, как правило, входит в МБК переправляющего "еще более ближнего" узла входа), в зависимости от ситуации. Этот процесс может повторяться (например, посредством рекурсивного применения способа 2200), пока узел входа целевого кольца соседства не будет достигнут.

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

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

Обратимся к Фиг. 6, иллюстративная система для реализации настоящего изобретения включает в себя универсальное вычислительное устройство в форме вычислительной системы 620, включающее в себя обрабатывающее устройство 621, системную память 622 и системную шину 623, которая соединяет различные системные компоненты, в том числе системную память 622 и обрабатывающее устройство 621. Обрабатывающее устройство 621 может исполнять исполняемые на компьютере инструкции, разработанные для реализации возможностей вычислительной системы 620, в том числе признаки настоящего изобретения. Системная шина 623 может быть любого из нескольких типов шинных структур, включающих в себя шину памяти или устройство управления памятью, шину периферийных устройств и локальную шину, использующую любую из множества шинных архитектур. Системная память включает в себя постоянное запоминающее устройство ("ПЗУ") 624 и оперативное запоминающее устройство ("ОЗУ") 625. Базовая система 626 ввода/вывода (БСВВ), содержащая основные процедуры, которые помогают передавать информацию между элементами внутри вычислительной системы 620, например, во время запуска, может храниться в ПЗУ 624.

Кроме того, вычислительная система 620 может включать в себя накопитель 627 на магнитных жестких дисках для считывания и записи на магнитный жесткий диск 639, накопитель 628 на магнитных дисках для считывания или записи на сменный магнитный диск 629 и накопитель 630 на оптических дисках для считывания или записи на сменный оптический диск 631, такой, к примеру, как CD-ROM или другой оптический носитель. Накопитель 627 на магнитных жестких дисках, накопитель 628 на магнитных дисках и накопитель 630 на оптических дисках подсоединяются к системной шине 623 с помощью интерфейса 632 для накопителя на жестких дисках, интерфейса 633 для накопителя на магнитных дисках и интерфейса 634 для оптического накопителя соответственно. Накопители и соотнесенные с ними машиночитаемые носители обеспечивают энергонезависимое хранение исполняемых на компьютере инструкций, структур данных, программных модулей и других данных для вычислительной системы 620. Хотя иллюстративная среда, приведенная в настоящем описании, использует магнитный жесткий диск 639, сменный магнитный диск 629 и сменный оптический диск 631, для хранения данных могут использоваться машиночитаемые носители других типов, в том числе магнитные кассеты, карты памяти с групповой перезаписью, универсальные цифровые диски, кассеты Бернулли, ОЗУ, ПЗУ и т.п.

Программные средства, содержащие один или более программных модулей, могут сохраняться на жестком диске 639, магнитном диске 629, оптическом диске 631, в ПЗУ 624 или ОЗУ 625, включают в себя операционную систему 635, одну или более прикладных программ 636, другие программные модули 637 и программные данные 638. Пользователь может вводить команды и информацию в вычислительную систему 620 посредством клавиатуры 640, координатно-указательного устройства 642 или других устройств ввода (не показаны), таких, например, как микрофон, координатный манипулятор, игровой планшет, сканирующее устройство и тому подобное. Эти и другие устройства ввода могут соединяться с обрабатывающим устройством 621 посредством интерфейса 646 ввода/вывода, подсоединенного к системной шине 623. Интерфейс 646 ввода/вывода логически представляет собой любой из широкого выбора различных интерфейсов, таких, например, как интерфейс для последовательного порта, интерфейс PS/2, интерфейс для параллельного порта, интерфейс Универсальной Последовательной Шины ("USB" - Universal Serial Bus) или интерфейс стандарта Института Инженеров по Электротехнике и Электронике ("IEEE" - Institute of Electrical and Electronics Engineers) 1394 (т.е. интерфейс FireWire), или даже может логически представлять собой комбинацию различных интерфейсов.

Монитор 647 или другое устройство отображения также соединяется с системной шиной 623 через видеоинтерфейс 648. Динамики 669 или другое устройство звукового вывода также соединяются с системной шиной 623 через звуковой интерфейс 649. Другие внешние устройства вывода (не показаны), такие, например, как печатающие устройства, также могут быть соединены с вычислительной системой 620.

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

Вычислительная система 620 включает в себя сетевой интерфейс 653, посредством которого вычислительная система 620 принимает данные от внешних источников и/или передает данные на внешние источники. Как изображено на Фиг. 6, сетевой интерфейс 653 способствует обмену данными с удаленной вычислительной системой 683 по каналу 651 связи. Сетевой интерфейс 653 может логически представлять собой один или более модулей программного обеспечения и/или аппаратного обеспечения, такие, например, как сетевая интерфейсная плата и соответствующее стековое запоминающее устройство, отвечающее Спецификации Стандартного Интерфейса Сетевых Адаптеров ("NDIS" - Network Driver Interface Specification). Канал 651 связи представляет собой часть сети (например, сегмент сети Ethernet), а удаленная вычислительная система 683 представляет собой узел сети.

Аналогично, вычислительная система 620 включает в себя интерфейс 646 ввода/вывода, посредством которого вычислительная система 620 принимает данные от внешних источников и/или передает данные на внешние источники. Интерфейс 646 ввода/вывода соединяется с модемом 654 (например, стандартным модемом, кабельным модемом или модемом цифровой абонентской линии ("DSL" - Digital Subscriber Line)) по каналу 659 связи, посредством которого вычислительная система 620 принимает данные от внешних источников и/или передает на них данные. Как изображено на Фиг. 6, интерфейс 646 ввода/вывода и модем 654 способствует обмену данными с удаленной вычислительной системой 693 по каналу 652 связи. Канал 652 связи представляет собой часть сети, а удаленная вычислительная система 693 представляет собой узел сети.

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

В соответствии с настоящим изобретением узлы, прикладные уровни и другие нижние уровни, а также соотнесенные данные, включающие в себя таблицы маршрутизации и идентификаторы узлов, могут сохраняться, и быть доступными с любых машиночитаемых носителей, соотнесенных с вычислительной системой 620. Например, части таких модулей и части соотнесенных программных данных могут быть включены в состав операционной системы 635, прикладных программ 636, программных модулей 637 и/или программных данных 638, для сохранения в системной памяти 622.

Когда запоминающее устройство большой емкости, такое, например, как магнитный жесткий диск 639, присоединяется к вычислительной системе 620, такие модули и соотнесенные программные данные тоже могут сохраняться на запоминающем устройстве большой емкости. В сетевой среде программные модули, изображенные относительно вычислительной системы 620, или их части могут сохраняться на удаленных запоминающих устройствах, таких как системная память и/или запоминающие устройства большой емкости, связанные с удаленной вычислительной системой 683 и/или удаленной вычислительной системой 693. Исполнение таких модулей может выполняться в распределенной среде, как описано ранее.

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

Изобретение относится к вычислительной технике. Технический результат заключается в повышении эффективности передачи данных между узлами сети посредством применения механизма рандеву. Способ отправки сообщения в инфраструктуре объединения в вычислительной системе, причем инфраструктура объединения представлена связанным списком узлов, связанный список узлов разделен на иерархическое дерево колец, в котором: принимают сообщение в подкольце; определяют, что узел, имеющий принадлежность подкольцу, должен отправить сообщение к другому подкольцу; используют внутрикольцевое взаимодействие в пределах подкольца, чтобы идентифицировать следующий узел с таблицей входов набора боковых колец; используют межкольцевое взаимодействие для посылки сообщения от следующего узла к дополнительному подкольцу на том же определенном уровне подколец, чтобы обойти корневое кольцо, включающий в себя этап, на котором следующий узел осуществляет доступ к узлу входа в дополнительное подкольцо из таблицы входов набора боковых колец следующего узла, и этап, на котором следующий узел посылает сообщение к узлу входа в дополнительное подкольцо. 4 н. и 33 з.п. ф-лы, 30 ил.

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

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

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

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

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

6. Способ по п.5, дополнительно содержащий
этап, на котором выделяют из множества узлов входа соответствующее подмножество узлов входа.

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

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

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

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

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

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

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

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

15. Способ по п.14, в котором этап приема указания в другом сообщении содержит этап приема указания в сообщении от другого узла в сетевой инфраструктуре.

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

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

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

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

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

21. Способ по п.20, дополнительно содержащий:
этап, на котором узел в родительском подкольце обращается к локальным сведениям для идентификации каких-либо узлов в подкольце.

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

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

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

25. Способ по п.24, в котором этап, на котором принимают отклик на поиск узла входа, соответствующий запросу поиска, содержит этап, на котором принимают отклик на поиск узла входа из точки рандеву.

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

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

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

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

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

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

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

33. Машиночитаемый носитель по п.32, представляющий собой системную память.

34. Машиночитаемый носитель по п.32, представляющий собой магнитный диск.

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

36. Машиночитаемый носитель по п.35, представляющий собой системную память.

37. Машиночитаемый носитель по п.35, представляющий собой магнитный диск.