Организация стыковки запросов на ресурс с соответствующими ресурсами

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

 

Перекрестная ссылка на родственные заявки

Эта заявка является продолжением заявки на патент США с регистрационным номером 10/971.451, поданной 22 октября 2004 и озаглавленной "Rendezvousing Resource Requests With Corresponding Resources", полностью включенной в данное описание по ссылке.

1. Область техники, к которой относится изобретение

Настоящее изобретение относится к доступу к ресурсам и более конкретно к организации стыковки запросов на ресурс с соответствующими ресурсами.

2. Предшествующий уровень техники

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

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

Соответственно, для вычислительных систем были разработаны различные механизмы (например, Служба Доменных Имен ("DNS"), Активный Каталог (Active Directory, "AD") (продукт компании Microsoft, предназначенный для обеспечения управления, защиты, доступа и разработки компонентов сети), Распределенные Файловые Системы ("DFS")) для идентификации ранее неизвестных систем (и доступа к ним). Однако из-за количества и многообразия ресурсов (например, устройств и служб), которые доступны через различные вычислительные сети, разработчикам часто требуется разрабатывать приложения, которые реализуют разнообразные различные механизмы идентификации ресурса и доступа к ресурсу. Каждый особый механизм может иметь особые требования на кодирование и не может обеспечить разработчика всеми функциональными возможностями, которые необходимы в приложении.

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

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

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

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

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

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

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

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

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

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

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

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

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

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

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

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

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

ПЕРЕЧЕНЬ ЧЕРТЕЖЕЙ

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

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

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

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

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

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

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

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

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

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

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

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

ПОДРОБНОЕ ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отношение между узлами в объединении

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

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

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

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

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

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

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

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

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

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

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

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

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

Узла-последователя (s);

Узла-предшественника (p);

Узлов окрестности (p_k, …, p₁, p, 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-i), …, r_-1, r₁, …, r_n-1) таких, что r_± = RouteNumerically (id ± bⁱ, Msg),

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

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

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

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

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

Таблица маршрутизации дополнительно указывает, что ID 64 может осуществлять маршрутизацию в узлы, имеющие ID 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. Например, при вычислении узла, наиболее близкого к 64 + 2³, или 72, может быть идентифицирован узел, имеющий ID 76.

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

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

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

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

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

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

Фиг.5 иллюстрирует возможное дерево 500 разбиения колец, выведенное в соответствие с близостью, обеспечивающее проксимальную маршрутизацию. Как изображено, дерево 500 разбиения колец включает в себя несколько колец. Каждое из колец представляет разбиение связного сортированного списка. Каждое кольцо включает в себя несколько узлов, имеющих идентификаторы ID в связном сортированном списке. Однако для ясности из-за количества возможных узлов, узлы на кольцах явно не изображены (например, пространством ID дерева 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 разбиения каждый узел имеет единственный ID и участвует в кольцах по соответствующему пути разбиений, начинающемуся от корня, к концевой вершине (листу). Например, каждый узел, участвующий в подкольце 552, должен участвовать также в подкольцах 543, 531, 522, 511 и в корне 501. Маршрутизация в узел-адресат (ID) может быть выполнена посредством применения функции RouteProximally следующим образом:

RouteProximally(V, Msg, P): При заданном значении V из области идентификаторов узлов и сообщении "Msg" осуществляется доставка сообщения в узел Y, идентификатор которого может быть отображен в V, из числа узлов, рассматриваемых как эквивалентные в соответствии с критериями близости P.

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

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

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

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

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

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

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

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

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

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

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

ID, который является численным значением, равномерно распределенным в диапазоне от 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 = RouteProximally (id ± bⁱ, updateMsg, 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. Здесь предполагается, что поддерживается только одна ссылка на заданный узел и худшей верхней границей является граница для сбалансированного дерева.

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

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

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

Параметры кольца, используемые для конфигурирования проксимального кольца более высокого уровня, в некоторых вариантах осуществления могут наследоваться проксимальными кольцами нижнего уровня. Например, кольцо 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 может содержать разное подмножество ID узлов из подкольца 511.

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

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

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

Способ 900 включает действие внесения в таблицу маршрутизации соответствующих узлов маршрутизации, при этом узлы маршрутизации идентифицируются из связного сортированного списка и в первом, и во втором направлениях на основе основания системы счисления и размера поля пространства ID для инфраструктуры объединения, узлы маршрутизации представляют логарифмический показатель связного сортированного списка и в первом и во втором направлениях (действие 904). Например, узлы, имеющие ID 200, 2, 30, 46, 50, 64, 64, 64, 64, 64, 76, 83, 98, 135 и 200, могут быть внесены в таблицу маршрутизации как узлы маршрутизации для узла, имеющего ID 64. На основе основания системы счисления в 2 и размера поля в 8, в направлении 321 могут быть идентифицированы узлы, имеющие ID 64, 64, 76, 83, 98, 135 и 200, а в направлении 322 могут быть идентифицированы узлы, имеющие ID 64, 64, 50, 46, 30, 2 и 200. Как изображено внутри кольца 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. Соответствующие узлы маршрутизации могут быть внесены на основе следующего выражения(ий):

if (если) Y.s_d.id < Y.id + bⁱ < Y.S s_d+1id true (истинно), then (то)

использовать кольцо d; или

if (если) Y.p_d.id < Y.id - bⁱ < Y.p_d+1.id true (истинно), then (то)

использовать кольцо d.

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

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

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

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

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

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

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

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

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

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

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

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

Вычислительная система 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”) или интерфейс (стандарта) Института инженеров по электротехнике и электронике (“IEEE”) 1394 (т.е. интерфейс FireWire (последовательной шины IEEE)) или даже может логически представлять комбинацию различных интерфейсов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

39. Система по п.38, в которой трафик сообщений ограничен верхним кольцом узлов.

40. Система по п.38, в которой трафик сообщений ограничен первым нижним кольцом узлов.

41. Система по п.38, в которой трафик сообщений ограничен вторым нижним кольцом узлов.

42. Система по п.38, при этом система сконфигурирована так, что сообщение, направленное в узел-адресат в верхнем кольце узлов, осуществляет максимально возможное продвижение в направлении к узлу-адресату в первом нижнем кольце узлов до того, как маршрутизация сообщения продолжится в верхнем кольце узлов.

43. Система по п.38, при этом система сконфигурирована так, что сообщение, направленное в узел-адресат в верхнем кольце узлов, осуществляет максимально возможное продвижение в направлении к узлу-адресату во втором нижнем кольце узлов до того, как маршрутизация сообщения продолжится в верхнем кольце узлов.

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

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

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

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

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

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

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