Уровень техники
Компьютерные системы и соответствующая технология определяют многочисленные аспекты общественной жизни. Действительно, способность компьютерной системы обрабатывать информацию изменила образ жизни и характер работы людей. В настоящее время компьютерные системы выполняют большое количество задач (например, редактирование текста, составление расписаний и управление базами данных), которые до появления компьютерных систем выполнялись вручную. В последние годы, компьютерные системы начали подключать друг к другу и к другими электронным устройствам с образованием проводных и беспроводных компьютерных сетей, по которым компьютерные системы и другие электронные устройства могут передавать электронные данные. В результате, многие задачи, осуществляемые в компьютерной системе (например, голосовая связь, доступ к электронной почте, управление домашними электронными приборами, навигация в интернете и печать документов), включают в себя обмен электронными сообщениями между несколькими компьютерными системами и/или другими электронными устройствами по проводным и/или беспроводным компьютерным сетям.
Однако, чтобы использовать сетевой ресурс для осуществления компьютеризированной задачи, компьютерная система должна иметь возможность идентификации сетевого ресурса и доступа к нему. Соответственно, ресурсам обычно присваиваются уникальные идентификаторы, например сетевые адреса, которые однозначно идентифицируют ресурсы и которые можно использовать для того, чтобы отличать один ресурс от других ресурсов. Таким образом, компьютерная система, которая желает использовать ресурс, может подключиться к ресурсу с использованием сетевого адреса, который соответствует ресурсу. Однако доступ к сетевому ресурсу может быть затруднен, если компьютерная система заранее не имеет информации о сетевом адресе для сетевого ресурса. Например, компьютерная система не может напечатать документ на сетевом принтере, если компьютерная система (или другая сетевая компьютерная система) не знает сетевого адреса сетевого принтера.
Соответственно, были разработаны различные механизмы (например, [Domain Name System] Система доменных имен (“DNS”), Active Directory (“AD”), [Distributed File System] Распределенная файловая система (“DFS”)), позволяющие компьютерным системам идентифицировать (и осуществлять доступ) к первоначально не известным ресурсам. Однако, в силу количества и разнообразия ресурсов (например, устройств и служб), к которым можно осуществлять доступ через различные компьютерные сети, разработчикам часто требуется создавать приложения, реализующие разнообразные механизмы идентификации и доступа к ресурсам. Разные механизмы могут иметь разные требования к кодированию и могут не обеспечивать разработчика всеми функциями, которые необходимы в приложении.
Например, хотя DNS имеет распределенную архитектуру администрирования (т.е. централизованное управление не требуется), DNS недостаточно динамична, не имеет возможностей самоорганизации, поддерживает слабую модель данных и запросов и имеет фиксированное множество корней. С другой стороны, AD достаточно динамична, но требует централизованного администрирования. Кроме того, аспекты разных механизмов могут быть несовместимы друг с другом. Например, ресурс, идентифицированный с использованием DNS, может быть несовместим с протоколами маршрутизации DFS. Таким образом, разработчику приходится выбирать наиболее подходящий механизм и пренебрегать преимуществами других механизмов.
Механизмы идентификации ресурсов могут составлять особую проблему в одноранговых сетях. DNS обеспечивает службу поиска, в которой имена хостов являются ключами и IP адреса являются значениями и которая опирается на множество особых корневых серверов для реализации запросов поиска. Кроме того, DNS требует управления информацией (записи NS), чтобы клиенты могли осуществлять навигацию по иерархии серверов имен. Таким образом, чтобы ресурс можно было идентифицировать в сети, этот ресурс должен быть введен в DNS. В крупномасштабных сетях, где узлы часто соединяются с и отсоединяются от сети, полагаться на запись информации не всегда практично. Кроме того, DNS специализируется на задаче отыскания хостов или служб и, в целом, не применима к другим типам ресурсов.
Соответственно, были разработаны другие механизмы идентификации и доступа к ресурсам в попытке исправить эти недостатки. Некоторые механизмы включают в себя распределенные протоколы поиска, которые в большей степени масштабируемы, чем DNS. Эти механизмы используют различные конфигурации узлов и алгоритмы маршрутизации для маршрутизации запросов на соответствующие ресурсы и для сохранения информации для поиска.
По меньшей мере, один из этих механизмов использует локальные многоуровневые карты соседей на каждом узле в сети для маршрутизации сообщений на узел назначения. Это, по существу, приводит к архитектуре, где каждый узел является “корневым узлом” соответствующего дерева узлов (узлов в его карте соседей). Сообщения последовательно маршрутизируются в ID пункта назначения цифра за цифрой (например, ***6 => **46 =>, *346 => 2346, где * представляет маску подстановки). Сложность маршрутизации этих типов механизмов составляет O(log N) переходов маршрутизации и требует, чтобы узлы поддерживали таблицу маршрутизации размером O(log N).
По меньшей мере, еще один из этих механизмов присваивает узлам уникальный ID, который берется из линейного кольца чисел. Узлы поддерживают таблицы маршрутизации, содержащие указатели на непосредственно последующий узел (согласно значению ID) и на узлы, значения ID которых являются ближайшими последователями значения ID + 2L. Сложность маршрутизации этих типов механизмов также составляет O(log N) переходов маршрутизации и требует, чтобы узлы поддерживали таблицу маршрутизации размером O(log N).
По меньшей мере, еще один механизм требует O(log N1/d) переходов маршрутизации и требует, чтобы узлы поддерживали таблицу маршрутизации размером O(D). Таким образом, сложность маршрутизации всех этих механизмов зависит, по меньшей мере частично, от количества узлов в системе.
Кроме того, поскольку ID (для, по меньшей мере, некоторых механизмов) могут равномерно распределяться по кольцу, всегда существует возможность того, что маршрутизация между узлами на кольце приведет к некоторой неэффективности. Например, переходы маршрутизации могут преодолевать большие географические расстояния, проходить по более дорогостоящим линиям связи или проходить через незащищенные домены, и т.д. Кроме того, когда маршрутизация сообщений предусматривает множественные переходы, существует вероятность того, что такие события будут происходить много раз. К сожалению, эти механизмы не учитывают близость узлов (физическую или иную) относительно друг друга. Например, в зависимости от распределения узлов на кольце, маршрутизация сообщения из Нью-Йорка в Бостон могут включать в себя маршрутизацию сообщения из Нью-Йорка в Лондон, затем в Атланту, затем в Токио и, наконец, в Бостон.
Соответственно, по меньшей мере, еще один недавно разработанный механизм учитывает близость, определяя близость как единую скалярную метрику близости (например, количество переходов IP маршрутизации или географическое расстояние). Эти механизмы используют условное обозначение выбора на основе близости для записей таблицы маршрутизации. Поскольку существует много “правильных” узлов-кандидатов для каждой записи таблицы маршрутизации, эти механизмы пытаются выбирать проксимально близкий узел среди узлов-кандидатов. Для этих механизмов можно обеспечить функцию, которая позволяет каждому узлу определить “расстояние” от узла с данным IP адресом до себя самого. Сообщения маршрутизируются между более близкими узлами для продвижения к пункту назначения до маршрутизации на более далекий узел. Это позволяет сэкономить некоторые ресурсы и повысить эффективность маршрутизации.
К сожалению, эти существующие механизмы обычно не предусматривают, помимо прочего, симметричных отношений между узлами (т.е., если первый узел считает второй узел своим партнером, то второй узел также считает первый узел своим партнером), маршрутизацию сообщений в обоих направлениях (по часовой стрелке и против часовой стрелки) на кольце, разделение связных списков узлов на основании совокупности метрик близости и маршрутизацию сообщений на основании совокупности метрик близости. Эти трудности могут ограничивать динамический, распределенный и эффективный перенос данных между узлами сети, например, при широковещательной рассылке данных на все узлы сети.
Сущность изобретения
Настоящее изобретение относится к способам, системам и компьютерным программным продуктам для облегчения межблизостной связи в федерации рандеву. В некоторых вариантах осуществления, поддерживается таблица вхождений множества коллатеральных колец для узла. Узел обращается к таблице вхождений множества коллатеральных колец, предназначенной для хранения вхождений множества коллатеральных колец для узла. Каждая запись множества коллатеральных колец способна указывать коллатеральное кольцо узла и, по меньшей мере, один соответствующий узел вхождения в коллатеральное кольцо узла. Выявляется информация таблицы вхождений множества коллатеральных колец из доступных ресурсов, которые поддерживают информацию, относящуюся к конфигурации дерева колец. Таблица вхождений множества коллатеральных колец обновляется надлежащим состоянием записи множества коллатеральных колец на основании выявленной информации таблицы вхождений множества коллатеральных колец. Надлежащее состояние записи множества коллатеральных колец включает в себя коллатеральное кольцо узла и, по меньшей мере, один соответствующий узел вхождения в коллатеральное кольцо узла.
В других вариантах осуществления, межблизостная связь осуществляется в дереве колец. В одном варианте осуществления межблизостной связи, производится определение, что узел должен отправить сообщение в указанное коллатеральное кольцо узла. Узел обращается к таблице вхождений множества коллатеральных колец, предназначенной для хранения вхождений множества коллатеральных колец для узла. Каждая запись множества коллатеральных колец способна указывать коллатеральное кольцо узла и, по меньшей мере, один соответствующий узел вхождения в коллатеральном кольце узла. По меньшей мере, одна запись множества коллатеральных колец для указанного коллатерального кольца идентифицируется из таблицы вхождений множества коллатеральных колец узла. Каждое из, по меньшей мере, одной из вхождений множества коллатеральных колец указывает, по меньшей мере, один узел вхождения указанного коллатерального кольца. Сообщение отправляется на, по меньшей мере, один указанный узел вхождения.
В другом варианте осуществления межблизостной связи, производится определение, что исходный узел намерен маршрутизировать сообщение на узел назначения, ближайший к данному ID узла в целевом кольце близости в дереве колец. Один или несколько узлов вхождения, про которые известно, что они принадлежат, по меньшей мере, одному из целевого кольца близости и кольца, предшествующего целевому кольцу близости, идентифицируются. Сообщение отправляется на идентифицированный узел вхождения. Сообщение указывает, что идентифицированный узел вхождения призван разрешать сообщение на узел, который имеет ID узла, ближайший к указанному узлу назначения в целевом кольце близости.
Эта сущность изобретения призвана в упрощенной форме обозначить идеи, которые будут дополнительно раскрыты ниже в подробном описании. Эта сущность изобретения не призвана идентифицировать ключевые признаки или существенные признаки заявленного изобретения, а также не подлежит использованию для определения объема заявленного изобретения.
Дополнительные признаки и преимущества будут изложены в нижеприведенном описании, и отчасти будут следовать из описания, или смогут быть изучены путем практического применения принципов изобретения. Признаки и преимущества изобретения можно реализовать и получить посредством инструментов и комбинаций, конкретно указанных в прилагаемой формуле изобретения. Признаки настоящего изобретения в полном объеме следуют из нижеследующего описания и прилагаемой формулы изобретения или могут быть изучены путем практического применения изобретения, раскрытого ниже.
Краткое описание чертежей
Для описания, каким образом можно получить вышеописанные и другие преимущества и признаки, более конкретное описание изобретения, кратко описанного выше, будет приведено со ссылкой на конкретные варианты осуществления, проиллюстрированные в прилагаемых чертежах. С учетом того, что эти чертежи изображают лишь типичные варианты осуществления и поэтому не призваны ограничивать его объем, варианты осуществления будут описаны и объяснены в дополнительных деталях и подробностях с использованием прилагаемых чертежей, в которых:
фиг.1 - пример инфраструктуры федерации;
фиг.2 - пример архитектуры компьютера, которая облегчает запрос маршрутизации опосредованно партнерам;
фиг.3 - иллюстративное бинарное отношение между узлами в инфраструктуре федерации в форме сортированного списка и соответствующего кольца;
фиг.4 - иллюстративное кольцо колец, которое облегчает проксимальную маршрутизацию;
фиг.5 - иллюстративное дерево разбиения колец по признаку близости, которое облегчает проксимальную маршрутизацию;
фиг.5A - иллюстративное дерево разбиения колец по признаку близости, показанное фиг.5, где более подробно показаны части дерева разбиения колец, показанного на фиг.5;
фиг.6 - подходящая операционная среда для реализации принципов настоящего изобретения;
фиг.7 - иллюстративная логическая блок-схема способа наполнения таблицы маршрутизации узла с учетом критериев близости;
фиг.8 - иллюстративная логическая блок-схема способа разбиения узлов инфраструктуры федерации;
фиг.9 - иллюстративная логическая блок-схема способа наполнения таблицы маршрутизации узла;
фиг.10 - иллюстративная логическая блок-схема способа численной маршрутизации сообщения на узел назначения;
фиг.11 - иллюстративная логическая блок-схема способа проксимальной маршрутизации сообщения на узел назначения;
фиг.12A - пример узла, устанавливающего принадлежность в существующей федерации;
фиг.12B - пример узлов в инфраструктуре федерации, обменивающихся сообщениями;
фиг.13 - иллюстративная логическая блок-схема способа установления принадлежности в инфраструктуре федерации;
фиг.14 - иллюстративная логическая блок-схема способа поддержания принадлежности в инфраструктуре федерации;
фиг.15 - иллюстративная логическая блок-схема способа выявления информации живучести для другого узла;
фиг.16 - пример модели сообщений и соответствующей модели обработки;
фиг.17 - пример ряда взаимодействий живучести, которые могут происходить между функциональным уровнем и прикладным уровнем;
фиг.18 - пример сообщений, составляющих часть образца обмена сообщениями типа запрос-ответ, маршрутизирующихся между узлами на кольце;
фиг.19A - иллюстративное дерево разбиения колец по признаку близости, которое облегчает межблизостную связь;
фиг.19B - другой вид иллюстративного дерева разбиения колец по признаку близости, показанного на фиг.19A;
фиг.19C - представление разбиения части иллюстративного дерева разбиения колец по признаку близости, показанного на фиг.19A;
фиг.19D - более подробная схема промежуточного кольца из иллюстративного дерева разбиения колец по признаку близости, показанного на фиг.19A;
фиг.19E - еще один вид иллюстративного дерева разбиения колец по признаку близости, показанного на фиг.19A;
фиг.19F - дополнительный вид иллюстративного дерева разбиения колец по признаку близости, показанного на фиг.19A;
фиг.19G - более подробная схема части фиг.19F;
фиг.20 - иллюстративная логическая блок-схема способа поддержания множества коллатеральных колец для узла в дереве колец;
фиг.21 - иллюстративная логическая блок-схема способа осуществления межблизостной связи в дереве колец;
фиг.22 - иллюстративная логическая блок-схема еще одного способа осуществления межблизостной связи в дереве колец.
Подробное описание
Настоящее изобретение относится к способам, системам и компьютерным программным продуктам для облегчения межблизостной связи в федерации рандеву. В некоторых вариантах осуществления, поддерживается таблица вхождений множества коллатеральных колец для узла. Узел обращается к таблице вхождений множества коллатеральных колец, предназначенной для хранения вхождений множества коллатеральных колец для узла. Каждая запись множества коллатеральных колец способна указывать коллатеральное кольцо узла и, по меньшей мере, один соответствующий узел вхождения в коллатеральное кольцо узла. Выявляется информация таблицы вхождений множества коллатеральных колец из доступных ресурсов, которые поддерживают информацию, относящуюся к конфигурации дерева колец. Таблица вхождений множества коллатеральных колец обновляется надлежащим состоянием записи множества коллатеральных колец на основании выявленной информации таблицы вхождений множества коллатеральных колец. Надлежащее состояние записи множества коллатеральных колец включает в себя коллатеральное кольцо узла и, по меньшей мере, один соответствующий узел вхождения в коллатеральное кольцо узла.
В других вариантах осуществления, межблизостная связь осуществляется в дереве колец. В одном варианте осуществления межблизостной связи, производится определение, что узел должен отправить сообщение в указанное коллатеральное кольцо узла. Узел обращается к таблице вхождений множества коллатеральных колец, предназначенной для хранения вхождений множества коллатеральных колец для узла. Каждая запись множества коллатеральных колец способна указывать коллатеральное кольцо узла и, по меньшей мере, один соответствующий узел вхождения в коллатеральное кольцо узла. По меньшей мере, одна запись множества коллатеральных колец для указанного коллатерального кольца идентифицируется из таблицы вхождений множества коллатеральных колец узла. Каждая из, по меньшей мере, одной из вхождений множества коллатеральных колец указывает, по меньшей мере, один узел вхождения указанного коллатерального кольца. Сообщение отправляется на, по меньшей мере, один указанный узел вхождения.
В другом варианте осуществления межблизостной связи, производится определение, что исходный узел намерен маршрутизировать сообщение на узел назначения, ближайший к данному ID узла в целевом кольце близости в дереве колец. Один или несколько узлов вхождения, про которые известно, что они принадлежат, по меньшей мере, одному из целевого кольца близости и кольца, предшествующего целевому кольцу близости, идентифицируются. Сообщение отправляется на идентифицированный узел вхождения. Сообщение указывает, что идентифицированный узел вхождения призван разрешать сообщение на узел, который имеет ID узла, ближайший к указанному узлу назначения в целевом кольце близости.
Варианты осуществления настоящего изобретения могут содержать компьютер специального назначения или общего назначения, включающий в себя компьютерное оборудование, более подробно рассмотренное ниже. Варианты осуществления в объеме настоящего изобретения также включают в себя компьютерно-считываемые носители для переноса или хранения компьютерно-выполняемых инструкций или структур данных. Такие компьютерно-считываемые носители могут представлять собой любые доступные носители, к которым может осуществлять доступ компьютер общего назначения или специального назначения. В порядке примера, но не ограничения, компьютерно-считываемые носители могут содержать компьютерно-считываемые носители данных, например ОЗУ, ПЗУ, ЭСППЗУ, CD-ROM или другие носители данных в виде оптического диска, носители данных в виде магнитного диска или другие магнитные запоминающие устройства, или любой другой носитель, который можно использовать для хранения нужного средства программного кода в форме компьютерно-выполняемых инструкций или структур данных и к которым может осуществлять доступ компьютер общего назначения или специального назначения.
В этом описании и в нижеследующей формуле изобретения, “сеть” определяется как одна или несколько линий передачи данных, которые обеспечивают транспортировку электронных данных между компьютерными системами и/или модулями. При переносе или предоставлении информации по сети или иному соединению (проводному, беспроводному или комбинированному) на компьютер, компьютер рассматривает соединение как компьютерно-считываемый носитель. Таким образом, в порядке примера, но не ограничения, компьютерно-считываемые носители могут содержать сеть или линии передачи данных, которую(ые) можно использовать для переноса или хранения нужного средства программного кода в форме компьютерно-выполняемых инструкций или структур данных и к которым может осуществлять доступ компьютер общего назначения или специального назначения.
Компьютерно-выполняемые инструкции содержат, например, инструкции и данные, которые предписывают компьютеру общего назначения, компьютеру специального назначения или устройству обработки специального назначения осуществлять определенную функцию или группу функций. Компьютерно-выполняемые инструкции могут представлять собой, например, инструкции в двоичном формате, промежуточном формате, например, на языке ассемблера, или даже в виде исходного кода. Хотя настоящее изобретение описано применительно к структурным признакам и/или этапам способа, следует понимать, что настоящее изобретение, заданное в прилагаемой формуле изобретения, не обязано ограничиваться вышеописанными признаками или этапами. Напротив, описанные признаки и этапы приведены в качестве иллюстративных форм реализации формулы изобретения.
В некоторых вариантах осуществления, аппаратные модули, например интегральные схемы или вентильные матрицы специального назначения, оптимизированы для реализации принципов настоящего изобретения.
В этом описании и в нижеследующей формуле изобретения, “узел” определяется как один или несколько программных модулей, один или несколько аппаратных модулей или их комбинация, которые действуют совместно для осуществления операций над электронными данными. Например, определение узла включает в себя аппаратные компоненты персонального компьютера, а также программные модули, например операционную систему персонального компьютера. Физическая конфигурация модулей не имеет значения. Узел может включать в себя один или несколько компьютеров, соединенных через сеть. Аналогично, узел может включать в себя одно физическое устройство (например, мобильный телефон или карманный персональный компьютер “КПК”), где внутренние модули (например, память и процессор) действуют совместно для осуществления операций над электронными данными. Кроме того, узел может включать в себя оборудование специального назначения, например маршрутизатор, который включает в себя интегральные схемы специального назначения.
Специалистам в данной области очевидно, что изобретение можно осуществлять на практике в сетевых вычислительных средах, где существует много типов конфигураций узлов, включающих в себя, персональные компьютеры, портативные компьютеры, карманные устройства, многопроцессорные системы, микропроцессорные или программируемые бытовые электронные приборы, сетевые ПК, миникомпьютеры, универсальные компьютеры, мобильные телефоны, КПК, пейджеры, маршрутизаторы, шлюзы, брокеры, прокси-серверы, брандмауэры, редиректоры, трансляторы сетевых адресов и пр. Изобретение также можно осуществлять на практике в условиях распределенной системы, где задачи осуществляют локальные и удаленные узлы, которые связаны (посредством проводных линий передачи данных, беспроводных линий передачи данных или комбинации проводных и беспроводных линий передачи данных) через сеть. В условиях распределенной системы, программные модули могут располагаться как в локальных, так и удаленных запоминающих устройствах.
Архитектура федерации
На фиг.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 и Simple Object Access Protocol (“SOAP”)) из одной конечной точки в другую (например, от узла 101 к узлу 103). Канальный уровень также отвечает за обработку входящих и исходящих заголовков надежного обмена сообщениями и поддержание состояния, связанного с сеансами надежного обмена сообщениями.
В целом, уровень маршрутизации отвечает за вычисление следующего перехода к пункту назначения. Уровень маршрутизации также отвечает за обработку входящих и исходящих заголовков адресации и маршрутизации сообщений и поддержание состояния маршрутизации. В целом, функциональный уровень отвечает за выдачу и обработку сообщений протокола рандеву, например запросов вступления и выбытия, пингов, обновлений и других сообщений, а также генерацию ответов на эти сообщения. Функциональный уровень обрабатывает сообщения запроса с уровня маршрутизации и посылает соответствующие сообщения ответа, если таковые предусмотрены, обратно на исходный узел с использованием уровня маршрутизации. Функциональный уровень также инициирует сообщения запроса и использует уровень маршрутизации для доставки сообщений запросов.
В целом, прикладной уровень обрабатывает данные, не связанные с протоколом рандеву, доставляемые с функционального уровня (т.е. сообщения приложения). Функциональный уровень может обращаться к данным приложения с прикладного уровня и извлекать и вводить данные приложения в сообщения протокола рандеву (например, пинги и обновления). Таким образом, функциональный уровень может обеспечивать вложение данных приложения в сообщения протокола рандеву и может обеспечивать передачу данных приложения обратно на прикладной уровень на принимающих узлах протокола рандеву. В некоторых вариантах осуществления, данные приложения используются для идентификации ресурсов и ценности ресурсов. Таким образом, прикладной уровень может включать в себя логику прикладного уровня и состояние, которое обрабатывает данные, принимаемые с и передаваемые на другие, более низкие уровни в целях идентификации ресурсов и ценности ресурсов.
Механизмы объединения в федерацию
Узлы могут объединяться в федерацию с использованием разнообразных механизмов. Первый механизм объединения в федерацию включает в себя равноправные узлы, пересылающие информацию на все остальные равноправные узлы. Когда узел собирается вступить в инфраструктуру федерации, узел использует протокол обнаружения широковещания/групповой адресации, например WS-Discovery, для объявления своего присутствия и выдает команду обнаружения широковещания/групповой адресации для обнаружения других узлов. Затем узел устанавливает простое партнерство по пересылке с другими узлами, уже присутствующими в сети, и принимает новые партнерства с вновь вступающими узлами. Затем узел просто пересылает все сообщения прикладного уровня на все свои узлы-партнеры.
Второй механизм объединения в федерацию включает в себя равноправные узлы, которые наиболее эффективно передают сообщения прикладного уровня на свои пункты назначения. Когда новый узел собирается вступить в инфраструктуру федерации, новый узел использует протокол обнаружения широковещания/групповой адресации, например WS-Discovery, для объявления своего присутствия и выдает команду обнаружения широковещания/групповой адресации для обнаружения других узлов, которые входят в состав инфраструктуры федерации. Обнаружив другой узел, новый узел устанавливает партнерство с другим узлом. На основании установленного партнерства, новый узел получает информацию о наличии других узлов, уже участвующих в инфраструктуре федерации. Затем он устанавливает партнерства с этими вновь обнаруженными узлами и принимает любые новые входящие запросы партнерства.
Прибытия/выбытия и регистрации узлов, представляющие интерес, в определенных сообщениях прикладного уровня распространяются по инфраструктуре федерации, благодаря чему каждый узел имеет глобальную информацию о других узлах-партнерах и регистрациях, представляющих интерес, в сообщениях прикладного уровня. Благодаря такой глобальной информации, любой узел может посылать сообщения прикладного уровня непосредственно на узлы, которые проявили интерес к сообщению прикладного уровня.
Третий механизм объединения в федерацию включает в себя равноправные узлы, опосредованно пересылающие все сообщения прикладного уровня на их пункты назначения. В этом третьем механизме, узлам присваиваются идентификаторы (ID), например 128-битовый или 160-битовый ID. Узел, отвечающий за поддержание регистрации, представляющей интерес, в данном сообщении прикладного уровня можно определить как тот, ID которого является ближайшим к тому, который получен путем отображения (например, хэширования) идентификатора пункта назначения (например, URI) сообщения прикладного уровня в это пространство 128-битовых или 160-битовых ID.
В этом третьем механизме, прибытия и выбытия узла распространяются по всей архитектуре. С другой стороны, регистрации, представляющие интерес, в определенных сообщениях прикладного уровня пересылаются на узлы, в отношении которых определено, что они отвечают за поддержание такой информации регистрации. Для масштабируемости, балансировки нагрузки и отказоустойчивости узел, принимающий регистрацию, представляющую интерес, в определенных сообщениях прикладного уровня может надежно распространять эту информацию регистрации в пределах своего множества соседей. Множество соседей для указанного узла можно определить как множество узлов, имеющих ID в заранее заданном диапазоне по обе стороны от ID указанного узла.
Аналогично второму механизму, вновь вступающий узел использует протокол обнаружения широковещания/групповой адресации, например WS-Discovery, для объявления своего присутствия и выдает локальную команду обнаружения широковещания/групповой адресации для обнаружения узла, который уже является частью инфраструктуры федерации. Новый узел устанавливает партнерство с выявленным узлом и использует это партнерство для получения информации о наличии других новых узлов, участвующих в инфраструктуре федерации. Затем новый узел устанавливает дополнительные партнерства с вновь обнаруженными узлами и принимает любые новые входящие запросы партнерства. Новый узел принимает входящие регистрации, представляющие интерес, в определенных ресурсах прикладного уровня от своих партнеров, за которые он отвечает, и может распространять их по своему множеству соседей. Таким образом, сообщения можно, в целом, пересылать в их конечные пункты назначения через промежуточные маршрутизирующие узлы (например, с которыми вновь вступающий узел установил партнерства или о которых осведомлен узел-партнер).
В ответ на прием входящего сообщения прикладного уровня, новый узел пересылает сообщение на узел-партнер, который может отвечать за поддержание информации регистрации для пункта назначения, указанного в сообщении. Таким образом, с использованием этого третьего механизма каждый узел в инфраструктуре федерации получает глобальную информацию обо всех остальных узлах, но информация регистрации эффективно делится между узлами. Сообщения прикладного уровня передаются в свои конечные пункты назначения только через узлы-партнеры, которые могут отвечать за поддержание информации регистраций, представляющих интерес, в этих сообщениях прикладного уровня. Таким образом, опосредованность осуществляется за счет пересылки только на узел-партнер, который имеет глобальную информацию о регистрациях, представляющих интерес, для обрабатываемого сообщения. В этом состоит отличие от механизма, где опосредованность осуществляется за счет пересылки на все узлы-партнеры.
Четвертый механизм объединения в федерацию включает в себя равноправные узлы, которые маршрутизируют сообщения на другие равноправные узлы. Этот четвертый механизм отличается от третьего механизма, по меньшей мере, тем, что все прибытия/выбытия и регистрации узлов, представляющие интерес, в определенных сообщениях прикладного уровня маршрутизируются, а не распространяются. Протоколы маршрутизации призваны гарантировать рандеву между сообщениями прикладного уровня и сообщениями регистрации, которые проявляют интерес к этим сообщениям прикладного уровня.
На фиг.2 показан пример компьютерной архитектуры 200, которая облегчает запрос маршрутизации опосредованно партнерам. Компьютерная архитектура 200 представляет различные типы компьютерных систем и устройств, потенциально распределенных по нескольким локальным диапазонам обнаружения, участвующим в инфраструктуре федерации.
Рабочая станция 233 может включать в себя зарегистрированный экземпляр провайдера PnP. Чтобы сообщить партнерам о наличии этого экземпляра провайдера PnP, рабочая станция 233 маршрутизирует запрос 201 регистрации по инфраструктуре федерации. Запрос 201 регистрации первоначально направляется на портативный компьютер 231, который, в свою очередь, пересылает запрос 201 регистрации брокеру 237 сообщений, который, в свою очередь, пересылает запрос 201 регистрации на шлюз 241 сообщений. Шлюз 241 сообщений сохраняет информацию регистрации запроса 201 регистрации в своей базе данных и возвращает сообщение об успехе 204 на рабочую станцию 233.
Затем, другой зарегистрированный экземпляр провайдера, на этот раз провайдера действующих услуг, активизируется на рабочей станции 233. На этот раз узел знает, что шлюз 241 сообщений отвечает за регистрации, и пересылает запрос 205 регистрации непосредственно на шлюз 241 сообщений. Шлюз 241 сообщений сохраняет информацию регистрации запроса 205 регистрации в своей базе данных и возвращает сообщение 206 об успехе на рабочую станцию 233.
Затем принтер 236 (например, принтер UPnP) включается и посылает объявление 207. Сервер 234 обнаруживает объявление 207 и маршрутизирует запрос 208 регистрации брокеру 237 сообщений. Брокер 237 сообщений пересылает запрос 208 регистрации на шлюз 241 сообщений. Шлюз 241 сообщений сохраняет информацию регистрации запроса 208 регистрации в своей базе данных и возвращает сообщение 210 об успехе на сервер 234.
Затем персональный компьютер 242 выдает запрос 211 поиска для обнаружения всех устройств. Поскольку персональный компьютер 242 не знает, куда пересылать запрос 211 поиска, он маршрутизирует запрос 211 поиска через рабочую станцию 243. Поскольку запросы регистрации и поиска маршрутизируются в один и тот же пункт назначения, протокол маршрутизации, по существу, гарантирует рандеву между двумя запросами, благодаря чему рабочая станция 243 пересылает запрос 211 поиска на шлюз 241 сообщений. Шлюз 241 сообщений ищет информацию регистрации, поддерживаемую им, и пересылает запрос 211 поиска на рабочую станцию 233 и сервер 234. Рабочая станция 233 и сервер 234 посылают сообщения 214 и 216, соответственно, ответа на персональный компьютер 242.
Этот четвертый механизм предусматривает маршрутизацию (вместо распространения) запроса на узел (шлюз 241 сообщений), который имеет глобальную информацию о регистрациях, указанных в запросе. Этот четвертый механизм, который будет более подробно описан ниже, по существу, гарантирует, что маршрутизацию можно осуществлять за O(log N) переходов, где N - количество узлов, участвующих в инфраструктуре федерации. Поскольку этот четвертый механизм эффективно разбивает как партнерства, так и информацию регистрации узлов, он масштабируется на очень крупные сети, даже на интернет.
Хотя было описано несколько механизмов объединения в федерацию, специалистам в данной области техники, по ознакомлении с этим описанием, будет ясно, что возможны и другие механизмы объединения в федерацию.
Отношение между узлами в федерации
Соответственно, федерация состоит из множества узлов, которые взаимодействуют между собой для формирования динамической и масштабируемой сети, в которой можно систематически и эффективно распределять и локализовывать информацию. Узлы организованы для участия в федерации в виде сортированного списка с использованием бинарного отношения, которое рефлексивно, антисимметрично, транзитивно, полно и задано на области идентификаторов узлов. Концы сортированного списка соединены между собой, образуя кольцо. Таким образом, каждый узел в списке может рассматривать себя как находящийся посередине сортированного списка (в результате использования модульной арифметики). Кроме того, список имеет двунаправленную связность, благодаря чему любой узел может обходить список в любом направлении.
Каждому узлу в федерации можно присваивать ID (например, с помощью генератора случайных чисел с обнаружением дублирования) из фиксированного множества ID между 0 и некоторой фиксированной верхней границей. Таким образом, прибавление 1 к ID, равному фиксированной верхней границе, дает ID, равный нулю (т.е. перемещение с конца связного списка обратно к началу связного списка). Кроме того, задана функция отображения 1:1 из области значений идентификаторов узла в сами узлы.
На фиг.3 показан пример связного списка 304 и соответствующего кольца 306. Для такого кольца можно определить следующие функции:
RouteNumerically(V, Msg): для заданных значения V из области значений идентификаторов узлов и сообщения “Msg” доставлять сообщение на узел X, идентификатор которого можно отобразить в V с использованием функции отображения;
Neighborhood(X, S): соседство - это множество узлов по обе стороны узла X с мощностью, равной S.
Когда каждый узел в федерации имеет глобальную информацию о кольце, RouteNumerically(V, Msg) реализуется путем непосредственной отправки Msg на узел X, идентификатор которого получается путем применения функции отображения к V. Альтернативно, когда узлы имеют ограниченную информацию о других узлах (например, только о непосредственно соседствующих узлах), RouteNumerically(V, Msg) реализуется путем пересылки сообщения на последовательные узлы вдоль кольца, пока оно не достигнет узла назначения X.
Альтернативно (и преимущественно), узлы могут хранить достаточно информации о кольце для осуществления распределенного двоичного поиска (без необходимости иметь глобальную информацию или реализовывать маршрутизацию между непосредственно смежными узлами). Объем информации о кольце можно настроить так, чтобы поддержание информации о кольце оказывало достаточно небольшое влияние на каждый узел, но позволяло повысить производительность маршрутизации за счет сокращения количества переходов маршрутизации.
Как описано выше, ID можно присваивать с использованием отношения “<” (меньше), заданного на достаточно большом, ограниченном множестве натуральных чисел, в том смысле, что оно охватывает конечное множество чисел от 0 до некоторого фиксированного значения включительно. Таким образом, каждому узлу, участвующему в федерации, присваивается натуральное число, лежащее между 0 и некоторой надлежащим образом выбранной верхней границей включительно. Диапазон не обязан быть сплошным, и могут быть зазоры между числами, присвоенными узлам. Число, присвоенное узлу, служит его идентификатором в кольце. Функция отображения учитывает зазоры в пространстве чисел путем отображения числа, оказавшегося между двумя идентификаторами узла, в узел, идентификатор которого является численно ближайшим к числу.
Этот подход имеет ряд преимуществ. Благодаря присвоению каждому узлу равномерно распределенного числа, возрастает вероятность того, что все сегменты кольца наполняются равномерно. Кроме того, можно эффективно производить вычисления последователя, предшественника и соседства с использованием модульной арифметики.
В некоторых вариантах осуществления, узлам в федерации присваиваются ID из пространства ID настолько большого, чтобы вероятность того, что двум узлам будет присвоен один и тот же ID, была как можно меньше (например, когда используется генерация случайных чисел). Например, узлу можно присваивать ID в пределах от 0 до bn - 1, где b равно, например, 8 или 16, и n равно, например, цифрам, эквивалентным 128-битным или 160 битным. Соответственно, узлу можно присваивать ID, например, из диапазона от 0 до 1640 - 1 (или приблизительно 1.461502E48). Диапазон от 0 до 1640 - 1 обеспечивает, например, достаточное количество ID для присвоения каждому узлу в интернете уникального ID.
Таким образом, каждый узел в федерации может иметь:
ID, который является численным значением, равномерно распределенным в пределах от 0 до bn-1; и
таблицу маршрутизации, содержащую (все арифметические действия осуществляются по модулю bn):
Последующий узел (s);
Предшествующий узел (p);
Соседние узлы (pk, ..., p1, p, s, s1, ..., sj), так что sj.s.id > (id + u/2), j ≥ v/2-1, и pk.p.id < (id - u/2), и k ≥ v/2-1; и
Маршрутизирующие узлы (r-(n-1), ..., r-1, r1, ..., rn-1), так что r±i = RouteNumerically(id ± bi, Msg),
где b - основание системы счисления, n - размер поля в количестве цифр, u - диапазон соседства, v - размер соседства, и арифметические действия осуществляются по модулю bn. Для повышения эффективности маршрутизации и отказоустойчивости значения u и v можно задать следующим образом: u=b и v≥max(log2(N), 4), где N - полное количество узлов, физически участвующих в федерации. N можно оценить на основании количества узлов, присутствующих на сегменте кольца, длина которого больше или равна b, например, при наличии равномерного распределения ID. Типичными значениями для b и n являются b = 8 или 16 и n = цифры, эквивалентные 128-битным или 160-битным.
Соответственно, маршрутизирующие узлы могут формировать логарифмический индекс, охватывающий кольцо. В зависимости от положений узлов на кольце, точный логарифмический индекс, например, возможен при наличии существующего узла на каждом числе в множестве id ± bi, где i = (1, 2, …, (n-1)). Однако может быть так, что существующие узлы находятся не на каждом числе в множестве. В таких случаях, в качестве маршрутизирующего узла можно выбирать узел, ближайший к id ± bi. В результате, логарифмический индекс не является точным, и для некоторых чисел в множестве может даже не хватать уникальных маршрутизирующих узлов.
На фиг.3 показан пример бинарного отношения между узлами в инфраструктуре федерации в форме сортированного списка 304 и соответствующего кольца 306. Пространство ID сортированного списка 304 находится в пределах от 0 до 28 - 1 (или 255). Таким образом, b=2 и n=8. Таким образом, узлам, обозначенным на фиг.3, присваиваются ID в пределах от 0 до 255. Сортированный список 304 использует бинарное отношение, которое рефлексивно, антисимметрично, транзитивно, полно и задано на области идентификаторов узлов. Концы сортированного списка 304 соединены между собой, образуя кольцо 306. Благодаря этому каждый узел, показанный на фиг.3, может рассматривать себя как находящийся посередине сортированного списка 304. Сортированный список 304 имеет двунаправленную связность, благодаря чему любой узел может обходить сортированный список 304 в любом направлении. Арифметика для обхода сортированного списка 304 (или кольца 306) осуществляется по модулю 28. Таким образом, 255 (или конец сортированного списка 304) + 1 = 0 (или начало сортированного списка 304).
Таблица маршрутизации указывает, что последователем ID 64 является ID 76 (ID, следующий сразу же за ID 64 по часовой стрелке). Последователь может меняться, например, когда новый узел (например, с ID, равным 71) вступает в, или существующий узел (например, ID 76) покидает инфраструктуру федерации. Аналогично, таблица маршрутизации указывает, что предшественником ID 64 является ID 50 (ID, непосредственно предшествующий ID 64 против часовой стрелки). Предшественник может меняться, например, когда новый узел (например, с ID, равным 59) вступает в, или существующий узел (например, ID 50) покидает инфраструктуру федерации.
Таблица маршрутизации дополнительно указывает, что множество узлов, соседних с 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 ± 2i, где i = (1, 2, 3, 4, 5, 6, 7). Таким образом, b=2 и n=8. Например, узел, имеющий ID 76, можно идентифицировать путем вычисления узла, ближайшего к 64 + 23, или 72.
Узел может маршрутизировать сообщения (например, запросы на доступ к ресурсам) непосредственно на предшествующий узел, последующий узел, любой узел в множестве соседних узлов или любой маршрутизирующий узел. В некоторых вариантах осуществления, узлы реализуют функцию численной маршрутизации для маршрутизации сообщений. Таким образом, RouteNumerically(V, Msg) может быть реализована на узле X для доставки Msg на узел Y в федерации, ID которого является численно ближайшим к V, и возвращать ID узла Y узлу X. Например, узел, имеющий 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 содержит узлы в Азии.
В числовом пространстве, содержащем 65,536 (216) ID, маршрутизация сообщения от североамериканского узла, имеющего ID 5,345, на азиатский узел, имеющий ID 23,345, может включать в себя маршрутизацию сообщения в кольце 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. Таким образом, возможен рекурсивный вызов функции RouteProximally, причем каждый вызов приводит к маршрутизации сообщения ближе к пункту назначения.
Таким образом, с учетом критерия близости, переходы маршрутизации на пути к конечному пункту назначения могут оставаться в пределах близости узла, который выдает запрос, в то же время, совершая значительное продвижение между исходным узлом и узлом назначения в числовом пространстве, пока не будет достигнут узел назначения или какое-либо дополнительное продвижение будет невозможно согласно выбранному критерию близости, в каковой момент он ослабляется ровно настолько, чтобы можно было осуществлять дальнейшее продвижение к пункту назначения. Например, критерий близости можно ослабить в достаточной степени, чтобы сообщение можно было маршрутизировать от кольца 531 до кольца 522, и т.д.
Используя вышеописанный подход к близости, можно ограничить опубликованную информацию данным кольцом. Например, для организаций может быть важно гарантировать, что конфиденциальная информация будет недоступна для сущностей вне их доверенных доменов либо (1) неявно, в форме дублирования соседства на узлы вне их доменов, либо (2) явно, в форме обслуживания запросов поиска для такой информации. Первый аспект удовлетворяется путем дублирования опубликованной информации только среди узлов, соседствующих с ID цели в указанном кольце. Поскольку все сообщения, отправляемые узлом, маршрутизируются путем последовательного восхождения по кольцам, которым он принадлежит, к корневому кольцу, велика вероятность того, что все запросы поиска, выдаваемые в организации, будут способны находить опубликованную информацию в своих пределах, тем самым неявно удовлетворяя второму аспекту.
Кроме того, организации предпочитают не пользоваться узлами, автоматически устанавливающими федеральные отношения с узлами вне их доверенного домена. Это может происходить, например, когда разъездной продавец подключает свой портативный компьютер к сети в апартаментах покупателя. В идеале, портативный компьютер, принадлежащий продавцу, желает найти информацию, опубликованную в своем базовом домене и/или установить федеральные отношения с узлами в своем базовом домене начиная со своего самого низкого предпочтительного кольца близости. Обычно не разрешается устанавливать федеральные отношения с узлами в домене покупателя. Поддержка этого сценария требует способности находить затравочные узлы в базовом домене. Такие затравочные узлы можно использовать для нахождения информации, опубликованной в базовом домене, для вхождения в базовую федерацию, и избирательно импортировать и экспортировать опубликованную информацию по доменам. Затравочные узлы также иногда называют шлюзами сообщений.
В других вариантах осуществления, сущность публикует ссылки на затравочные узлы в корневом кольце. Затравочные узлы могут быть опубликованы на уникальном числе (например, полученном хэшированием своей представительной строки), связанном с кольцом (в качестве ID цели). Информация затравочного узла может дополнительно кэшироваться по требованию узлами в различных кольцах, которые находятся на пути к соответствующим ID цели в корневом кольце. Такое кэширование по требованию обеспечивает повышение производительности и сокращение количества заторов, которые могут возникать при достаточно частом поиске полустатической информации. Информацию затравочного узла также можно получить другими средствами, например, с помощью DNS.
Для обеспечения отказоустойчивости для ограниченной опубликованной информации, каждый узел может поддерживать множество соседних узлов во всех кольцах, где он участвует. С учетом вышесказанного, состояние, поддерживаемое узлом, можно кратко выразить следующим образом:
где 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 включает в себя этап, на котором обращаются к сортированному связному списку, содержащему ID узла, которые были присвоены узлам в инфраструктуре федерации (этап 801). Например, можно обращаться к сортированному связному списку, представленному кольцом 501. ID узла из сортированного связанного списка (узлы, указанные на кольце 501) могут представлять узлы в инфраструктуре федерации (например, инфраструктуре 100 федерации).
Способ 800 включает в себя этап, на котором обращаются к категориям близости, которые представляют совокупность разных критериев близости для разбиения сортированного связного списка (этап 802). Например, можно обращаться к критерию близости, представляющему границы 561 домена, географические границы 562 и организационные границы 563. Однако в критерии близости, к которому обращаются, могут быть представлены и другие критерии близости, например границы доверенного домена. Категории близости могут включать в себя ранее созданные частично упорядоченные списки критериев близости. Кольцо может быть разбито на основании частично упорядоченных списков критериев близости.
Способ 800 включает в себя этап разбиения сортированного связного списка на один или несколько первых подсписков на основании первого критерия близости, причем каждый из одного или нескольких первых подсписков содержит, по меньшей мере, подмножество ID узла из сортированного связного списка (этап 803). Например, кольцо 501 может быть разбито на подкольца 511, 512, 513 и 514 на основании критерия 571. Каждое из подколец 511, 512, 513 и 514 может содержать то или иное подмножество ID узла из кольца 501.
Способ 800 включает в себя этап разбиения первого подсписка, выбранного из одного или нескольких первых подсписков, на один или несколько вторых подсписков на основании второго критерия близости, причем каждый из одного или нескольких вторых подсписков содержит, по меньшей мере, подмножество ID узла, содержащихся в первом подсписке (этап 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 узлы, имеющие ID 83 и 76, можно идентифицировать в направлении 321 по часовой стрелке и узлы, имеющие ID 50 и 46, можно идентифицировать в направлении против 322 часовой стрелки (от конца B сортированного связного списка 304 к концу A сортированного связного списка 304). Возможно, что в некоторых средах никакие надлежащие соседние узлы не идентифицируются. Введение соседнего узла может устанавливать симметричное партнерство между текущим узлом и соседним узлом, согласно которому текущий узел является партнером соседнего узла, и соседний узел является партнером текущего узла.
Способ 900 включает в себя этап введения надлежащих маршрутизирующих узлов в таблицу маршрутизации, причем маршрутизирующие узлы идентифицируются из сортированного связного списка в первом и втором направлениях на основании основания системы исчисления и размера поля пространства ID для инфраструктуры федерации, причем маршрутизирующие узлы представляют логарифмический индекс сортированного связного списка в первом и втором направлениях (этап 904). Например, узлы, имеющие ID 200, 2, 30, 46, 50, 64, 64, 64, 64, 64, 76, 83, 98, 135 и 200, можно вводить в таблицу маршрутизации в качестве маршрутизирующих узлов для узла, имеющего ID 64. На основании основания системы исчисления 2 и размера поля 8, узлы, имеющие ID 64, 64, 76, 83, 98, 135 и 200, можно идентифицировать в направлении 321, и узлы, имеющие ID 64, 64, 50, 46, 30, 2 и 200, можно идентифицировать в направлении 322. Как указано в кольце 306, маршрутизирующие узлы представляют логарифмический индекс сортированного связного списка 304 как в направлении 321 по часовой стрелке, так и в направлении 322 против часовой стрелки. Введение маршрутизирующего узла может устанавливать симметричное партнерство между текущим узлом и маршрутизирующим узлом, согласно которому текущий узел является партнером маршрутизирующего узла, и маршрутизирующий узел является партнером текущего узла.
На фиг.7 показана иллюстративная логическая блок-схема способа 700 наполнения таблицы маршрутизации узла с учетом критериев близости. Способ 700 будет описан применительно к кольцам, показанным на фиг.5. Способ 700 включает в себя этап введения предшествующего узла для каждого иерархически разбитого кольца маршрутизации, в котором участвует текущий узел, в таблицу маршрутизации (этап 701). Каждый предшествующий узел предшествует текущему узлу в первом направлении (например, по часовой стрелке) в каждом иерархически разбитом кольце маршрутизации, в котором участвует текущий узел. Иерархически разбитые кольца маршрутизации делятся в соответствии с соответствующими критериями близости и содержат, по меньшей мере, подмножества двунаправленного связного списка (и, возможно, всего двунаправленного связного списка). Например, возможен случай, когда указанный узел участвует в корневом кольце 501 и подкольцах 511, 522, 523, 531 и 542. Таким образом, предшествующий узел выбирается для указанного узла из каждого из колец 501 и подколец 511, 522, 523, 531 и 542.
Способ 700 включает в себя этап введения последующего узла для каждого иерархически разбитого кольца маршрутизации, в котором участвует текущий узел, в таблицу маршрутизации (этап 702). Каждый последующий узел следует за текущим узлом в первом направлении в каждом иерархически разбитом кольце маршрутизации, в котором участвует текущий узел. Например, последующий узел выбирается для указанного узла из каждого из колец 501 и подколец 511, 522, 523, 531 и 542.
Способ 700 включает в себя этап введения надлежащих соседних узлов для каждого иерархически разбитого кольца маршрутизации, в котором участвует текущий узел, в таблицу маршрутизации (этап 703). Соседние узлы можно идентифицировать как в первом направлении (например, по часовой стрелке), так и во втором противоположном направлении (например, против часовой стрелки) на основании диапазона соседства и размера соседства из иерархически разбитых колец маршрутизации, в которых участвует текущий узел. Например, соседние узлы можно идентифицировать для указанного узла из каждого из колец 501 и подколец 511, 522, 523, 531 и 542.
Способ 700 включает в себя этап введения надлежащих маршрутизирующих узлов для каждого иерархически разбитого кольца маршрутизации, в котором участвует текущий узел, в таблицу маршрутизации (этап 704). Например, маршрутизирующие узлы можно идентифицировать для указанного узла из каждого из колец 501 и подколец 511, 522, 523, 531 и 542.
В некоторых вариантах осуществления, надлежащие маршрутизирующие узлы вводятся для каждого кольца близости d за исключением краевого кольца (или краевых колец согласно вариантам осуществления, предусматривающим использование псевдонимов), в котором участвует узел Y. Надлежащие маршрутизирующие узлы можно вводить на основании следующего(их) выражения(й):
если Y.sd.id < Y.id + bi < Y.sd+1.id истинно, то использовать кольцо d; или
если Y.pd.id < Y.id - bi < Y.pd+1.id истинно, то использовать кольцо d.
Если кольцо не было идентифицировано на предыдущем этапе, использовать следующее (например, кольцо 501) кольцо в качестве кольца d. Теперь, кольцо 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.
Фазы узла
Узел, участвующий в инфраструктуре федерации, может работать в разных рабочих фазах. Правильные значения фазы для узла можно задавать как элементы упорядоченного множества. Например, {NodeId}.{InstanceIds}.{Phase Value [Значения фазового состояния: Inserting (введение), Syncing (синхронизация), Routing (маршрутизация), Operating (эксплуатация)]. [Указание phase.unknown: фаза известна во время передачи, фаза неизвестна во время передачи]} задает одно возможное упорядоченное множество, представляющее фазовое пространство данного узла в инфраструктуре федерации. Экземпляр узла может последовательно переходить (или продвигаться) по фазовым состояниям узла от Inserting к Syncing к Routing к Operating по порядку. Кроме того, в некоторых вариантах осуществления, экземпляр узла можно конфигурировать так, чтобы экземпляр узла не мог совершать обратные переходы к предыдущему фазовому состоянию узла. В некоторых вариантах осуществления, узел продвигает свой ID экземпляра каждый раз, когда узел поднимается.
Например, можно препятствовать экземпляру узла в переходе от Routing обратно к Syncing (или обратно к Inserting), и т.д. Соответственно, в некоторых вариантах осуществления, когда известно, что данный экземпляр узла (например, идентифицированный посредством (NodeId, InstanceId)) продвинулся в конкретное фазовое состояние узла (например, Operating), также известно, что данный экземпляр узла скорее всего (и, в некоторых вариантах осуществления, точно) не вернется к предыдущему фазовому состоянию узла (например, обратно к Routing, Syncing или Inserting). Таким образом, велика вероятность того, что экземпляр любого узла в фазе узла, предшествующей конкретному фазовому состоянию узла, является новым (и продвинутым) экземпляром узла.
В некоторых вариантах осуществления, информация фазы и соответствующие ID экземпляра (которые продвигаются по мере подъема узла) преобразуются совместно. Таким образом, можно определить, что меньшее фазовое состояние узла для одного и того же экземпляра старше. Кроме того, когда известен более новый экземпляр узла (при любых значениях фазового состояния), любая информация о более старых экземплярах считается устаревшей.
Время от времени, узлы могут перезагружаться или терять связь друг с другом, например, при первом запуске, при постепенном выбытии или в результате аварийного завершения (краха). Таким образом, для узла в любом фазовом состоянии узла существует возможность перезагрузки или потери связи с другими узлами. Например, крах может обуславливать перезагрузку узла в фазовом состоянии Routing. При перезагрузке или потере связи невозможно определить, в каком фазовом состоянии узла находится узел. Соответственно, когда узел перезагружается, или связь с узлом теряется, можно устанавливать [Указание phase.unknown] для указания, что фазовое состояние для узла в данный момент неизвестно. Однако любое ранее выраженное и/или обнаруженное фазовое состояние для узла может поддерживаться и не теряться.
[Указание phase.unknown] можно использовать для указания, известно ли фазовое состояние на момент передачи значения фазового состояния (например, значение фазы с неустановленным phase.unknown), или является ли фазовое состояние ранее выраженным фазовым состоянием и фазовое состояние не было известно на момент передачи фазового состояния (например, значение фазы с установленным phase.unknown). Таким образом, фаза узла (его значение фазы) можно представлять с использованием значения фазового состояния и указания phase.unknown.
Протокол присоединения
Время от времени узлы могут присоединяться к и выбывать из существующих федераций. Узлы могут реализовывать соответствующие протоколы для присоединения к и выбытия из федераций. Например, узел может реализовать функцию Join(), чтобы стать частью существующей федерации. Узел, реализующий функцию Join(), может совершать переходы через три упорядоченные фазовые состояния: фазовое состояние введения, фазовое состояние синхронизации и фазовое состояние маршрутизации, прежде чем достигнет конечного фазового состояния эксплуатации. В других вариантах осуществления, эти конкретные упорядоченные фазовые состояния могут не существовать, но могут быть заданы другие. На фиг.12A показан пример узла, устанавливающего принадлежность в инфраструктуре федерации. На фиг.12B показан пример узлов в инфраструктуре федерации, обменивающихся сообщениями.
Фаза введения: узел Y входит в это фазовое состояние, выдавая сообщение присоединения, включающее в себя, по меньшей мере, свой ID узла и указывающее действие присоединения к федерации. Сообщение присоединения может представлять собой маршрутизируемое сообщение, отправляемое вновь присоединяющимся узлом (узлом Y), где его свойство пункта назначения задано равным идентификатору вновь присоединяющегося узла. В этом фазовом состоянии, вновь присоединяющийся узел вводится между своими предшествующим и последующим узлами в федерации. Фазовое состояние введения можно реализовать согласно следующему алгоритму (все арифметические действия осуществляются по модулю bn):
IP1. Y идентифицирует существующий узел, который уже является частью самого низкого кольца, из которого присоединяющийся узел желает участвовать в федерации. Он может быть либо статически сконфигурирован, либо динамически обнаружен с использованием DHCP, и/или DNS, и/или WS-Discovery, или (потенциально общеизвестной) константы. Пусть этот существующий узел федерации будет E.
IP2. Y вызывает E.RouteNumerically(Y, joinMsg) для определения узла X, ID которого является численно ближайшим к Y.id в каждом кольце близости, в котором участвует узел Y. Это может включать в себя маршрутизацию сообщения присоединения нескольким узлам.
IP3. Определить численно последующий (s) и предшествующий (p) узлы. (Заметим, что данные, необходимые для осуществления следующего введения, можно переносить в сообщении присоединения и в ответе на него. Поэтому дополнительные полные обходы не требуются.)
Случай 1: X.id > Y.id
Y.s = X, Y.p = X.p, X.p.s = Y, и X.p = Y
Случай 2: X.id < Y.id
Y.p = X, Y.s = X.s, X.s.p = Y, и X.s = Y
В ответ на сообщение присоединения, узел X (узел, который обработал сообщение присоединения) может посылать ответ присоединения обратно на узел Y. Ответ присоединения может указывать предшествующий узел (Y.p) и последующий узел (Y.s) для узла Y. Узел Y может принимать ответ присоединения и обрабатывать ответ присоединения, чтобы получать информацию о своих предшествующем и последующем узлах. После обработки ответа присоединения узел Y может быть слабым участником маршрутизации в федерации. Например, узел Y может просто пересылать переданное ему сообщение на свои последующие или предшествующие узлы. Таким образом, узел Y вводится в инфраструктуру федерации, но таблицы маршрутизации и соседства не наполняются. До этого, узел Y будет запрашивать другие узлы, направляя им сообщения о перенаправлении отправляемых ему сообщений через другой узел, возвращая на посылающий узел сообщение статуса, указывающее, что фаза живучести узла Y находится в фазовом состоянии введения.
В целом, время от времени, узлы могут обмениваться сообщениями запроса и ответа синхронизации. Сообщения запроса синхронизации и ответа синхронизации могут включать в себя информацию живучести (например, заголовки) для других узлов с точки зрения отправителя. Состояние соседства также можно включать в сообщения запроса и ответа синхронизации, чтобы прикладные уровни в соседстве знали состояние друг друга. Обмен сообщениями запроса и ответа синхронизации осуществляется, например, в фазовом состоянии синхронизации присоединяющегося узла. Однако сообщениями запроса и ответа синхронизации также можно обмениваться в других рабочих фазовых состояниях (например, в фазовом состоянии эксплуатации).
На фиг.16 показан пример модели сообщения и соответствующей модели 1600 обработки. Согласно фиг.16, узел может посылать и принимать сообщения запроса синхронизации. Например, сообщение 1601 запроса синхронизации можно принимать на функциональном уровне 1651 от вновь введенного узла (например, узла, показанного на фиг.12B, имеющего ID 144). Данные приложения 1602 (например, подписки пространства имен) можно вкладывать в сообщение 1601 запроса синхронизации. Функциональный уровень 1651 может информировать прикладной уровень 1652 о любых данных приложения, включенных в сообщения запроса синхронизации. Например, функциональный уровень 1651 может вызывать событие 1603 синхронизации состояния соседства, включающее в себя данные 1602 приложения, на прикладной уровень 1652. Запрос 1631 синхронизации, включающий в себя данные 1607 приложения, также можно направлять на другой узел, который обрабатывает запрос 1631 синхронизации аналогично обработке запроса 1601 синхронизации в модели 1600 обработки.
В ответ на некоторое событие функционального уровня (например, сообщение запроса 1601 синхронизации, сообщение 1641 ответа синхронизации или пинговое сообщение 1612) функциональный уровень 1651 может вызывать функцию 1604 запроса состояния соседства на прикладном уровне 1652. Запрос 1604 состояния соседства - это запрос, обращенный к прикладному уровню, для получения состояния, которое необходимо распространять в соседстве. В ответ на запрос 1604 состояния соседства, прикладной уровень 1652 может сообщать состояние 1606 соседства, включающее в себя необязательные данные 1607 приложения, функциональному уровню 1651. Альтернативно, прикладной уровень 1652 может посылать состояние 1606 соседства, включающее в себя необязательные данные 1607 приложения, в порядке реакции на некоторое событие прикладного уровня. С использованием внутренних механизмов, аналогичных вышеописанным, функциональный уровень 1651 может посылать сообщение 1608 ответа синхронизации, включающее в себя необязательные данные 1607 приложения, для распространения состояния соседства прикладного уровня.
Фаза синхронизации: после обработки сообщения ответа присоединения, узел Y переходит из фазового состояния введения в фазовое состояние синхронизации (Syncing). В фазовом состоянии синхронизации, вновь введенный узел Y синхронизирует информацию с узлами в соседстве. В целом, узел Y может посылать сообщения синхронизации на, по меньшей мере, свои предшествующий и последующий узлы, идентифицированные в фазовом состоянии введения. Эти узлы, обрабатывающие сообщения синхронизации, могут возвращать ответы синхронизации, которые указывают соответствующие соседние и маршрутизирующие узлы-партнеры этих обрабатывающих узлов. В более частном примере, фазовое состояние синхронизации можно реализовать согласно следующему алгоритму (все арифметические действия осуществляются по модулю bn):
SP1. Вычислить Neighborhood(Y) из объединения узлов Neighborhood(Y.s) и Neighborhood(Y.p) в каждом проксимальном кольце, в котором участвует узел Y. Вычисление объединения можно производить следующим образом:
(sj, ..., s1, s, p, p1, ..., pk), так что sj.s.id > (Y.id + u/2), j ≥ v/2-1, pk.p.id < (Y.id - u/2), и k ≥ v/2-1
SP2. Согласно фиг.16, запросить локальный прикладной уровень узла Y (например, прикладной уровень 1652) через запрос 1604 состояния соседства (например, запрос состояния соседства), чтобы получить необязательные данные соседства прикладного уровня (например, характерные для приложений данные 1607).
SP3. Отправить сообщение синхронизации на, по меньшей мере, ближайшие последующий и предшествующий узлы, включающее в себя, по меньшей мере, информацию состояния живучести каждого проксимального соседнего и маршрутизирующего узла-партнера с точки зрения Y. Любые необязательные данные соседства прикладного уровня (например, данные 1607 приложения), доступные через SP2, включается в запрос 1631 синхронизации.
SP3. Y принимает сообщения ответа синхронизации обратно от этих узлов, обрабатывающих сообщения синхронизации, отправленные в SP2. Например, узел Y может обмениваться сообщениями синхронизации (запрос/ответ) с одним или несколькими узлами в своем вычисленном соседстве. После обмена сообщениями синхронизации с, по меньшей мере, одним и, потенциально, всеми соседними узлами узла Y, вычисленные соседние узлы могут обмениваться дополнительными сообщениями для распространения синхронизированных данных. Сообщение синхронизации (запрос или ответ) может представлять собой немаршрутизируемое сообщение, отправляемое узлом для упреждающей синхронизации своих данных с целевым узлом, т.е., например, в соседстве узлов.
SP4. После приема сообщения ответа синхронизации в SP3 (например, сообщения 1641 ответа синхронизации), любые необязательные данные соседства прикладного уровня, присутствующие в этих принятых сообщениях ответа синхронизации (например, данные 1622 приложения) можно сообщать прикладному уровню 1652 Y посредством события 1603 синхронизации состояния соседства.
В фазовом состоянии синхронизации, проксимальные последующий (например, Y.s) и предшествующий (Y.p) узлы обмениваются своими таблицами маршрутизации с вновь введенным узлом (например, Y). Узлы, которые принимают сообщения синхронизации, могут в ответ посылать ответы синхронизации. Ответы синхронизации несут данные, аналогичные сообщениям синхронизации, но с точки зрения отвечающего узла. Сообщения синхронизации и ответы синхронизации могут нести (или присоединять) данные приложения. Таким образом, данные приложения можно распространять между узлами в фазовом состоянии синхронизации. По завершении фазового состояния синхронизации, узел может обрабатывать адресованные ему сообщения, вместо того чтобы просто пересылать их последователю или предшественнику. Однако узел также можно рассматривать как слабый участник маршрутизации, поскольку его таблица маршрутизации не наполнена.
Фаза маршрутизации: по завершении фазового состояния синхронизации, узел переходит в фазовое состояние маршрутизации. В фазовом состоянии маршрутизации, вновь синхронизированный узел (например, узел Y) вычисляет свои маршрутизирующие узлы. Фазовое состояние маршрутизации можно реализовать согласно следующему алгоритму (все арифметические действия осуществляются по модулю bn):
RP1. Если фазовое состояние маршрутизации выполняется как часть процедуры балансировки (объяснена ниже), гарантировать, что последующий узел (Y.s) и предшествующий узел (Y.p) живы в каждом кольце близости, где участвует узел Y. Если ни один из них не жив, определить узел замещения для сбойного(ых) узла(ов) путем выбора следующего наилучшего последующего или предшествующего узла среди соседних узлов в рассматриваемом кольце.
RP2. Для 1 ≤ i ≤ n-1
RP2a. Вычислить z=Y.id ± bi
RP2b. Если кольцо d не является наиболее специфичным кольцом близости, найти кольцо близости d, в котором участвует узел Y, и удовлетворяющее условию Y.sd.id < Y.id + bi < Y.sd+1.id или Y.pd.id < Y.id - bi < Y.pd+1.id. Иначе сделать кольцо d наиболее специфичным кольцом близости. Кольцо d является кольцом близости, в котором узел Y должен искать партнера маршрутизации, ближайшего к z. Пусть Q это узел, численно ближайший к z между Y.sd.r±i и Y.pd.r±i. Если |Q.id-z| находится в пределах регулируемого процента от bi (обычно 20%), просто задать Y.r±i=Q. Если Q.id ближе к z, чем к (Y.sd.id ± bi) или (Y.pd.id ± bi), это значит, что узел Y является лучшим партнерским маршрутизирующим узлом для уза Q в кольце близости d, чем любой из Y.sd и Y.pd. Поэтому, отправить updateMsg на узел Q, если оно еще не отправлено, передавая i и узел Y в качестве параметров, чтобы узел Q мог установить узел Y в качестве своего партнерского маршрутизирующего узла на r-i.
RP2c. Если это фазовое состояние выполняется как часть процедуры балансировки, и если Y.sd.r±i.id==Y.pd.r±i.id, то существует только один узел в числовом диапазоне между (Y.sd.id ± bi) и (Y.pd.id ± bi). Это тот узел, на который указывает маршрутизирующий узел r±i последующего (или предшествующего) узла. Поэтому, просто задать Y.r±i=Y.sd.r±i.i.
RP2d. Иначе, вычислить партнер маршрутизации Y.r±i, вызвав RouteProximally на узле Q с критерием близости, заданным равным критерию близости кольца d. Отсюда Y.r±i=Q.RouteProximally(z, updateMsg, d).
RP3. В этот момент, узел Y может не только обрабатывать адресованные ему сообщения, но также может маршрутизировать сообщения.
RP4. Подписаться на события извещения о живучести, передаваемые с прикладного уровня для ID конечных точек партнерских маршрутизирующих узлов, если это еще не сделано. Кроме того, отменить все подписки на события живучести, ранее установленные с помощью прикладного уровня для узлов, которые больше не являются партнерскими маршрутизирующими узлами. Например, запросы подписки и/или отмены можно передавать на прикладной уровень (например, прикладной уровень 121), который реализует логику публикации/подписки для соответствующего приложения (например, приложения пространства имен). Когда последующие сообщения живучести прикладного уровня (например, обусловленные подписками пространства имен) принимаются на прикладном уровне, извещения (события) можно публиковать вниз на другие, более низкие уровни (например, другие, более низкие уровни 131) для обработки.
На фиг.17 показан пример ряда взаимодействий живучести, которые могут происходить между функциональным уровнем 1751 и прикладным уровнем 1752. Согласно фиг.17, конечными точками являются, например, темы публикации/подписки (например, представленные URL или URI), представляющие различные узлы, и могут являться, например, узлами инфраструктуры федерации. Subscribe To Liveness Event 1701 (Подписка на событие живучести) можно вызывать с функционального уровня 1751 на прикладной уровень 1752 для подписки на событие живучести (например, на тему публикации/подписки). Revoke Liveness Subscription 1702 (Отмена подписки на живучесть) можно вызывать с функционального уровня 1751 на прикладной уровень 1752 для отмены подписки на событие живучести. End Point Down 1703 (Конечная точка не функционирует) можно посылать с прикладного уровня 1752 на функциональный уровень 1751 для указания, что конечная точка может быть неработоспособна и для обеспечения функционального уровня 1751 необязательной замещающей конечной точкой. Событие End Point Down 1703 можно посылать асинхронно на основании предыдущей подписки (например, Subscribe To Liveness Event 1701).
Node Down 1704 (Узел не функционирует) можно вызывать с функционального уровня 1751 на прикладной уровень 1752 для указания, что функциональный уровень 1751 (или какой-либо другой, более низкий уровень) обнаружил сбойный узел, и, в необязательном порядке, обеспечения прикладного уровня 1752 замещающим узлом. Прикладной уровень 1752 может затем сообщать об обнаружении потенциально сбойного узла другим заинтересованным сторонам. Событие Node down 1704 можно посылать асинхронно всякий раз, когда функциональный уровень 1751 или какой-либо другой, более низкий уровень обнаруживает потенциально сбойный узел. Send Liveness 1706 (Послать живучесть) можно вызывать с прикладного уровня 1752 на функциональный уровень 1751, когда прикладной уровень 1752 обнаруживает отказ узла (например, из события Node down 1704 или какого-либо другого внеполосного механизма). Событие Send Liveness 1706 может предписывать функциональному уровню 1751 отправить сообщение живучести. Событие Send Liveness 1706 также можно вызывать асинхронно всякий раз, когда прикладной уровень 1752 обнаруживает отказ узла и не зависит ни от каких ранее установленных подписок (через подписку на живучесть).
Таким образом, в некоторых вариантах осуществления, функциональный уровень 1751 используется рекурсивно. Например, функциональный уровень 1751 может указывать заинтересованность в указанном узле (например, функционирует или нет конкретный узел) прикладному уровню 1752. Прикладной уровень 1752 может формировать подписку прикладного уровня на извещения, относящиеся к указанному узлу, и затем повторно использовать функциональный уровень 1751 для передачи сформированной подписки на надлежащие экземпляры соответствующего прикладного уровня 1752 в других узлах федерации. Например, если прикладные уровни 1752 в узлах федерации реализуют поведения публикации/подписки пространств имен, функциональный уровень 1751 может маршрутизировать подписку на менеджер публикации/подписки, который управляет извещениями для указанного узла - менеджер публикации/подписки реализован как, по меньшей мере, часть прикладного уровня 1752 в соответствующих узлах федерации. Соответственно, функциональный уровень 1751 используется для маршрутизации подписки, которую функциональному уровню 1751 предписано генерировать. Аналогичные рекурсивные механизмы также можно использовать для отписки или иного указания того, что указанный узел более не представляет интереса.
Фаза эксплуатации: По завершении фазового состояния маршрутизации, узел переходит в фазовое состояние эксплуатации. Узел может оставаться в фазовом состоянии эксплуатации, пока он не перестанет функционировать (например, перезагрузится). В фазовом состоянии эксплуатации, узел может время от времени посылать сообщения обновления на партнеры маршрутизации. Сообщения обновления (запросы обновления и ответы обновления) могут включать в себя информацию живучести соседних узлов для передающих узлов (например, для всех ближайших соседей, представляющих интерес). Эта отправленная информация живучести также может включать в себя информацию живучести отправителя. Сообщения обновления могут представлять собой маршрутизируемые сообщения, отправляемые узлами для периодического обновления своих маршрутизирующих узлов-партнеров. Данные приложения можно присоединять к сообщениям обновления, чтобы данные приложения можно было распространять в ходе обновления партнера маршрутизации. Пункт назначения сообщения задается равным идентификатору совершенного партнера маршрутизации на желаемом индексе маршрутизации. Свойству Message ID этого сообщения присваивается порядковый номер приложения, чтобы узел(ы), обрабатывающий(е) это сообщение, могли определить самое последнее сообщение, и это сообщение маршрутизируется проксимально.
Узел, который принимает сообщение обновления, может в ответ посылать ответ обновления. Ответ обновления переносит те же данные, что и сообщение обновления, но с точки зрения отвечающего узла. Посредством обмена сообщениями обновления и ответами обновления, узлы могут обмениваться информацией маршрутизации. Время от времени, действующие узлы могут обновлять партнеров маршрутизации.
Время от времени, действующие узлы также могут посылать пинговые сообщения (например, пинговые сообщения 1609 и 1611). Пинговое сообщение - это однонаправленное сообщение, передаваемое узлом, чтобы периодически объявлять о своем наличии и рассылать информацию в пределах своего соседства о своих соседних/маршрутизирующих узлах и реплицировать (например, присоединенные) данные приложения.
Исходный узел может посылать пинговое сообщение на один или несколько своих непосредственно предшествующих и последующих соседних узлов. Таким образом, в зависимости от шаблона распределения пингования (т.е. на какие узлы передаются пинговые сообщения) информация, относящаяся к исходному узлу, распространяется на другие узлы на кольце в пределах соседства исходного узла. Например, исходный узел может посылать пинговое сообщение только на свои непосредственно предшествующий и последующий узлы, и пинговое сообщение распространяется за пределы позиции (ID узла) исходного узла вдоль кольца в обоих направлениях до границы соседства исходного узла. Альтернативно, исходный узел может посылать пинговое сообщение на каждый n-й узел в своем соседстве в направлениях предшественника и последователя.
Каждый узел, принимающий пинговое сообщение, проверяет свой интерес в исходном узле с точки зрения диапазона соседства. Если он не заинтересован, он игнорирует пинговое сообщение. Если он заинтересован, он обрабатывает пинговое сообщение и пересылает пинговое сообщение согласно его указанного шаблона пингования, если такая пересылка ограничивается соседством исходного узла. Например, обработав пинговое сообщение, принимающий узел может пересылать пинговое сообщение на, по меньшей мере, свой последующий узел, если отправляющий и исходные узлы принадлежат его множеству предшествующих узлов, или на, по меньшей мере, свой предшествующий узел, если отправляющий и исходные узлы принадлежат его множеству последующих узлов.
Таким образом, внешнее распространение пинговых сообщений останавливается, когда сообщение достигает границы множества соседних узлов вокруг исходного узла. Свойству Message ID пингового сообщения присваивается порядковый номер приложения, чтобы узлы, обрабатывающие это сообщение, могли определить самое последнее сообщение от исходного узла и избежать обработки или иной ненужной пересылки.
Согласно фиг.16, пинговое сообщение 1609 можно принимать на функциональном уровне 1651 от соседнего узла. Данные приложения 1612 (например, подписки пространства имен) можно вкладывать в пинговое сообщение 1609. Функциональный уровень 1651 может информировать прикладной уровень 1652 о любых данных приложения, включенных в пинговые сообщения. Аналогично, функциональный уровень 1651 может информировать прикладной уровень 1652 о любых данных приложения, включенных в сообщения запроса синхронизации. Оба эти варианта передачи можно осуществлять путем отправки события синхронизации состояния соседства 1603, включающего в себя данные приложения 1612, на прикладной уровень 1652.
В ответ на некоторое событие функционального уровня (например, принятое пинговое сообщение 1609) функциональный уровень 1651 может посылать запрос 1604 состояния соседства на прикладной уровень 1652. Запрос 1604 состояния соседства вызывается на прикладном уровне 1652 для получения состояния, которое может потребоваться распространять в соседстве. В ответ на запрос 1604 состояния соседства, прикладной уровень 1652 может возвращать состояние 1606 соседства, включающее в себя необязательные данные 1607 приложения, на функциональный уровень 1651. Функциональный уровень 1651 может посылать пинговое сообщение 1611, включающее в себя необязательные данные 1607 приложения, для распространения информации живучести соседних и маршрутизирующих узлов-партнеров, а также необязательного состояния соседства прикладного уровня. Функциональный уровень 1651 также может посылать ответ 1608 синхронизации, включающий в себя необязательные данные 1607 приложения, для распространения состояния приложения.
Протокол выбытия
Когда узел желает покинуть федерацию, узел может реализовать функцию Depart для плавного выбытия из федерации. Узел выбывает из существующей федерации, посылая сообщение выбытия на один или несколько из своих непосредственно проксимальных предшествующих и последующих узлов и, возможно, другие узлы в том же проксимальном соседстве. Таким образом, в зависимости от шаблона распределения выбытия (т.е., на какие узлы передаются сообщения выбытия) информация, относящаяся к выбывающему узлу, распространяется на другие узлы на кольце в пределах соседства выбывающего узла. Сообщение выбытия представляет собой однонаправленное сообщение, передаваемое постепенно выбывающим узлом для информирования одного или нескольких других узлов в пределах, по меньшей мере, одного из своих диапазонов проксимального соседства о своем предстоящем выбытии. Выбывающий узел распространяет сообщение выбытия (например, в пределах своего соседства) аналогично распространению пинговых сообщений. Например, узел, имеющий ID 30, может посылать сообщения 1219 выбытия на узлы, имеющие ID 17 и 40. Узел, имеющий ID 30, затем может удалить себя из инфраструктуры федерации с точки зрения данного проксимального кольца. Заметим, что узел может удалить себя из одного диапазона проксимального соседства, но не других, которым он может принадлежать.
Поскольку узлы, имеющие ID 17 и 40 (т.е. предшествующий и последующий узлы) скорее всего, являются ближайшими узлами к ID 30 после удаления узла, имеющего ID 30, узлы, имеющие ID 17 и 40, узнают о выбытии узла, имеющего ID 30. Таким образом, будущие сообщения, подлежащие доставке на ID 30, будут надлежащим образом обрабатываться на узлах, имеющих ID 17 и 40. Узлы, имеющие ID 17 и 40, могут распространять выбытие узла, имеющего ID 30, на другие узлы на кольце 1206. В отсутствие узла, имеющего ID 30, узлы, имеющие ID 17 и 40, также могут повторно вычислять указатели на предшественник и последователь, потенциально указывающие друг на друга.
Свойству Message ID сообщения выбытия присваивается тот же ID последовательности приложения, что и для пинговых сообщений, чтобы узлы, обрабатывающие сообщение выбытия, могли определить самое последнее сообщение из последовательности сообщений пингования и выбытия, переданных исходным узлом. Постепенное выбытие из проксимального кольца федерации не обязательно, но желательно. Однако федерация имеет свойство самовосстановления в случае внезапного выбытия узлов.
Живучесть
В течение времени жизни федерации, узлы могут обмениваться информацией живучести для поддержания федерации. Информацию живучести можно включать в практически любое сообщение, участвующее в обмене между членами федерации, в форме заголовков сообщений живучести. Например, сообщения вступления, ответы вступления, сообщения синхронизации, ответы синхронизации, сообщения обновления, ответы обновления, сообщения прикладного уровня, сообщения живучести и пинговые сообщения могут включать в себя заголовки информации живучести. Когда узел федерации передает какое-либо сообщение или ответ, узел может включать в себя информацию живучести для обработки другими узлами. Информация живучести может быть включена в заголовок информации живучести сообщения живучести.
Информацию живучести, указывающую состояние живучести узла, можно представлять с использованием следующих свойств:
[Node]: Идентифицирует узел, состояние живучести которого представляется. Узел можно идентифицировать на основании [Reference Properties], которые дополнительно указывают [Instance ID].
[Reference Properties]: Элементы информации элемента, указанной в спецификации WS-адресации. WS-адресация задает опорное свойство [Instance ID] для включения в множество опорных свойств.
[Instance ID]: Число, которое идентифицирует конкретный экземпляр узла. В качестве ID экземпляра узла можно использовать возрастающий счетчик загрузок.
[Phase]: Переносит фазу идентифицированного узла.
[Phase-State Value] Переносит наивысшее фазовое состояние (введения, синхронизации, маршрутизации, эксплуатации), про которое известно, что указанный экземпляр узла достиг его.
[Phase.Unknown Indication] Указатель того, известна текущая фаза или нет.
[Freshness]: Переносит свежесть информации, и ее значение составляет от 0 до MaxFreshness. Чем выше значение, тем свежее информация, причем 0 означает отсутствие информации, и MaxFreshness - это константа, заданная протоколом.
[Color]: Идентифицирует класс эквивалентности по близости, которому принадлежит узел. Два узла с одинаковым значением цвета всегда считаются проксимально ближайшими, поскольку они оба принадлежат одному и тому же классу эквивалентности, идентифицированному значением цвета. Количество классов эквивалентности по близости может возрастать по мере того, как все больше узлов вступает в федерацию.
[Weight]: Обеспечивает метрику возможностей узла, и его значение составляет от 0 до MaxWeight. Он измеряет нужные характеристики узла федерации, например большую вычислительную мощность, высокую пропускную способность сети и продолжительное время безотказной работы. Чем выше значение, тем больше возможности узла, что делает его более желаемым с точки зрения партнерства.
В некоторых средах, свойства [Node] и [Freshness] узла явно или неявно переносятся в более крупном объеме, например заголовках [Origin] и [Sender] сообщений, поэтому повторное включение вышеупомянутых свойств в заголовки живучести приведет к дублированию. Например, отправителю сообщения нужно перенести только текущую информацию о его фазе, цвете и весе, когда его ID, Instance ID внедряются в заголовки адресации сообщения и его свежесть выводится.
Состояние живучести можно, по меньшей мере, частично упорядочить на основании бинарного отношения “<”, заданного следующим образом:
“L1 < L2” истинно, если
1. “L1.[Node].[Name] == L2.[Node].[Name]” истинно, и одно из следующих утверждений истинно при осуществлении и зацикливании испытаний в перечисленном порядке:
- L1.[Node].[Reference Properties].[Instance ID] < L2.[Node].[Reference Properties].[Instance ID]
- L1.[Phase.Unknown Indication] != true AND L2.[Phase.Unknown Indication] != true AND L1.[phase-state] < L2.[phase-state]
- L1.[Freshness] < L2.[Freshness]
2. Или “L1.[Цвет] == L2.[Цвет]” истинно, и одно из следующих утверждений истинно при осуществлении и зацикливании испытаний в перечисленном порядке:
- L1.[phase-state] < L2.[phase-state]
- L1.[Weight] < L2.[Weight]
Кроме того, сообщение живучести “down” (нефункционирования) можно посылать на указанный узел, когда обнаруживается или предполагается, что указанный узел стал недоступен (например, перестал функционировать). Например, когда прикладной уровень (например, прикладной уровень 121) обнаруживает, что другой прикладной уровень (например, прикладной уровень 123) или узел, размещающий этот другой прикладной уровень, не функционирует, обнаруживший прикладной уровень может извещать другие, более низкие уровни (например, другие, более низкие уровни 131), что узел может испорченнее функционировать, например, в соответствии с моделями сообщения и соответствующими моделями 1600 и/или 1700 обработки. Такое извещение может предписывать другим, более низким уровням, например, функциональному уровню 1651, посылать сообщение снижения живучести. Это только один пример инициирования генерации сообщений снижения живучести.
Поскольку сообщения живучести нефункционирования маршрутизируются и, таким образом, доставляются на узел, ближайший к потенциально сбойным узлам, если сообщение живучести нефункционирования для указанного узла доставляется обратно на указанный узел, то либо указанный узел никогда не испытывал сбоя, либо указанный узел является другим экземпляром (например, с другим ID экземпляра). С другой стороны, если сообщение живучести нефункционирования доставляется на другой узел, это указывает, что указанный узел, скорее всего, отказал. Соответственно, если узел, принимающий сообщение живучести нефункционирования, рассматривает себя как находящийся в проксимальном соседстве с указанным узлом, он может отправить в это проксимальное соседство вышеописанное сообщение выбытия для указанного узла, также указывающее его прикладному уровню (например, с использованием Node Down 1704), что указанный узел может быть сбойным, и что принимающий узел является его заменой. Сообщение живучести нефункционирования для указанного узла можно маршрутизировать проксимально, если задать его ID цели таким же, как у узла, который может быть сбойным.
Процедура балансировки
Варианты осуществления настоящего изобретения позволяют иметь дело с большим количеством узлов, вступающих в федерацию и выбывающих из нее за короткий период времени. Такие изменения в сети могут обуславливать задержки маршрутизации, если деревья логарифмического поиска, поддерживаемые на различных узлах, становятся несбалансированными. То есть, на одной стороне кольца больше узлов, чем на другой. Для облегчения оптимальной эффективности маршрутизации, узлы, участвующие в федерации, выполняют процедуру балансировки при выполнении определенных критериев.
Например, при выполнении любого из следующих условий, любой узел может выполнять процедуру балансировки, чтобы гарантировать сбалансированную таблицу маршрутизации для оптимальной эффективности маршрутизации:
- Принято определенное количество вышеописанных сообщений живучести.
- После приема последнего из вышеописанных сообщений живучести прошло определенное время.
- Соседство изменилось в том смысле, что прибыли некоторые новые узлы или выбыли некоторые существующие узлы.
Балансировка таблиц маршрутизации является простым процессом. Например, узлы с несбалансированной таблицей маршрутизации могут повторно выполнить фазовые состояния синхронизации и маршрутизации протокола вступления.
Этапы RP2b, RP2d и RP4 совместно с 1) нахождением ближайшего по номеру маршрутизирующего узла, 2) протоколом выбытия с последующим постепенным выбытием узлов из федерации, и 3) процедурой балансировки, после чего узлы принимают сообщения живучести, обеспечивает ускоренное восстановление системы, когда узлы федерации вступают в сеть и выбывают из нее достаточно быстро и в больших количествах.
Статусные сообщения
Статусное сообщение представляет собой немаршрутизируемое сообщение, направляемое принимающим узлом на передающий узел для информирования об успехе/неудаче маршрутизации коррелированного сообщения, которое передающий узел ранее переслал на принимающий узел. На фиг.18 показан пример сообщений, составляющих часть шаблона обмена сообщениями типа запрос-ответ, маршрутизирующихся между узлами на кольце. Статусное сообщение может включать в себя заголовки, которые идентифицируют исходное коррелированное сообщение, статус маршрутизации которого сообщается. Поэтому статусное сообщения можно использовать между узлами для указания, что сообщение успешно маршрутизировано с одного узла к следующему. Например, сообщение запроса 1811 маршрутизации от узла 1801 на узел 1806 включает в себя отправку запроса 1811 через узлы 1802, 1803, 1804 и 1805. Соответствующие последовательные статусные сообщения успеха (статус 1817, 1818, 1819, 1820 и 1821) можно посылать от узла 1806 на узел 1805, от узла 1805 на узел 1804, от узла 1804 на узел 1803, от узла 1803 на узел 1802, и от узла 1802 на узел 1801, соответственно. В ответ на запрос 1811, ответ 1816 можно посылать непосредственно от узла 1807 на узел 1801. Ответ 1816 является необязательным и может не существовать в однонаправленном шаблоне обмена сообщениями.
На фиг.13 показана иллюстративная логическая блок-схема способа 1300 присоединения узла к инфраструктуре федерации. Способ 1300 будет описан применительно к кольцу 1206, показанному на фиг.12A и 12B. Способ 1300 включает в себя этап выдачи сообщения присоединения к инфраструктуре федерации (этап 1301). Например, узел, имеющий ID 144, может выдавать сообщения 1201 присоединения к инфраструктуре федерации, включая кольцо 1206. Способ 1300 включает в себя этап приема сообщения присоединения от вступающего узла (этап 1308). Например, существующий узел в инфраструктуре федерации, включающей в себя кольцо 1206, может принимать сообщение 1201 присоединения.
Способ 1300 включает в себя этап маршрутизации сообщения присоединения на обрабатывающий узел (этап 1309). Обрабатывающий узел может быть узлом, ID которого численно ближе к ID присоединяющегося узла, чем у других активных узлов в инфраструктуре федерации на момент маршрутизации сообщения присоединения. Например, сообщение 1201 присоединения может быть первоначально принято на узле, имеющем ID 64, маршрутизировано на узел, имеющий ID 135, и маршрутизировано на узел, имеющий ID 151.
Способ 1300 включает в себя этап вычисления одного или нескольких предшествующих узлов и одного или нескольких последующих узлов для присоединяющегося узла (этап 1310). Например, узел, имеющий ID 151, может вычислять непосредственно предшествующий узел и непосредственно последующий узел для узла, имеющего ID 144. В кольце 1206, узел, имеющий ID 151, может вычислить, что узел, имеющий ID 135, является непосредственно предшествующим узлом, и что узел, имеющий ID 151, является непосредственно последующим узлом. Аналогичные вычисления можно производить для других проксимальных колец.
Способ 1300 включает в себя этап вычисления одного или нескольких маршрутизирующих узлов для присоединяющегося узла (этап 1311). Например, узел, имеющий ID 151, может вычислять маршрутизирующие узлы (с точки зрения узла, имеющего ID 151) для узла, имеющего ID 144. В кольце 1206, узел, имеющий ID 151, может вычислить, например, что узлы, имеющие ID 218 и 40, являются маршрутизирующими узлами для узла, имеющего ID 144. Аналогичные вычисления можно производить для других проксимальных колец.
Способ 1300 включает в себя этап отправки ответа присоединения на вступающий узел (этап 1312). Ответ присоединения может идентифицировать все предшествующие и последующие соседние и маршрутизирующие узлы-партнеры для присоединяющегося узла, вычисленные обрабатывающим узлом, при условии его текущего вида инфраструктуры федерации. Например, ответ 1202 присоединения может идентифицировать, по меньшей мере, узел, имеющий ID 135, как непосредственно предшествующий узлу, имеющему ID 144, может идентифицировать узел, имеющий ID 151, как непосредственно следующий за узлом, имеющим ID 144, и может идентифицировать любые маршрутизирующие узлы (для узла, имеющего ID 144) вычисленные на узле, имеющем ID 151, для ID узла 144 (вновь присоединяющегося узла).
Способ 1300 включает в себя этап приема ответа присоединения от узла федерации, который обработал сообщение присоединения (этап 1302). Например, узел, имеющий ID 144, может принимать ответ 1202 присоединения от узла, имеющего ID 151.
Способ 1300 включает в себя этап отправки запроса синхронизации на, по меньшей мере, каждый из непосредственно проксимальных предшествующих узлов и непосредственно проксимальных последующих узлов (этап 1303). Например, согласно фиг.12B, узел, имеющий ID 144, может посылать запросы 1203 синхронизации на узлы, имеющие ID 135 и 151. Запрос 1203 синхронизации может включать в себя идентификацию любых соседних узлов узла, имеющего ID 144, и/или идентификацию любых партнеров маршрутизации узла, имеющего ID 144.
Узлы, имеющие ID 135 и 151, могут принимать запросы синхронизации 1203. В ответ на прием запросов 1203 синхронизации, узлы, имеющие ID 135 и 151, могут идентифицировать свои соседние и маршрутизирующие узлы-партнеры из соответствующих таблиц маршрутизации. Узлы, имеющие ID 135 и 151, могут включать информацию живучести своих идентифицированных соседних и маршрутизирующих узлов-партнеров в ответ 1204 синхронизации и посылать отправленные ответы 1204 синхронизации на узел, имеющий ID 144.
Способ 1300 включает в себя этап приема ответа синхронизации от каждого из проксимальных предшествующего и последующего узлов (этап 1304). Например, узел, имеющий ID 144, может принимать ответы 1204 синхронизации от узлов, имеющих ID 135 и 151. Ответ 1204 синхронизации может включать в себя информацию живучести для одного или нескольких узлов на кольце 1206 или других кольцах в инфраструктуре федерации. Ответ 1204 синхронизации также может идентифицировать любые предполагаемые маршрутизирующие узлы-партнеры для узла, имеющего ID 144.
Способ 1300 включает в себя этап вычисления соседних узлов (этап 1305). Например, узел, имеющий ID 144, может вычислять соответствующие соседние узлы на основании объединения соседних узлов для узлов, имеющих ID 135 и 151. Соседние узлы можно вычислять на основании обобщенного вида сообщения ответа присоединения и любых сообщений ответа синхронизации.
Способ 1300 включает в себя этап вычисления маршрутизирующих узлов (этап 1306). Например, узел, имеющий ID 144, может вычислять маршрутизирующие узлы из узлов кольца 1206. Партнеры маршрутизации можно вычислять на основании обобщенного вида сообщения ответа присоединения и любых сообщений ответа синхронизации.
Способ 1300 включает в себя этап обмена, по меньшей мере, информацией соседних узлов с вычисленными партнерами маршрутизации (этап 1307). Например, узел, имеющий ID 144, и узел, имеющий ID 218 (вычисленный партнер маршрутизации), могут обмениваться информацией состояния (например, ID экземпляра, фазовым состоянием и т.д.) соответствующей их соответствующим соседним узлам. Эти обмены осуществляются вновь присоединяющимся узлом, отправляющим (маршрутизирующим) сообщение обновления на, по меньшей мере, каждый уникальный вычисленный партнер маршрутизации, как описано выше в отношении фазового состояния маршрутизации. Узлы, обрабатывающие сообщение обновления, посылают соответствующее сообщение ответа обновления в ответ на прием этих сообщений обновления от вновь присоединяющегося узла. Ответ обновления включает в себя, по меньшей мере, информацию живучести для самого себя и его соседних узлов.
Способ 1300 также может включать в себя этап инициирования начального распространения таблиц маршрутизации на, по меньшей мере, один соседний узел. Например, узел, имеющий ID 144, может включать вычисленные соседние и маршрутизирующие узлы-партнеры в пинговое сообщение и посылать пинговое сообщение на узел, имеющий ID 174 (например, один из вычисленных соседних узлов). Узел, имеющий ID 174, может принимать пинговое сообщение и обновлять соответствующую таблицу маршрутизации информацией живучести, выдаваемую узлом, имеющим ID 144. Узел, имеющий ID 174, также может включать свою соответствующую таблицу маршрутизации во второе пинговое сообщение и посылать второе пинговое сообщение в некоторый момент в будущем на узел, имеющий ID 144. Узел, имеющий ID 144, может принимать второе пинговое сообщение и может обновлять свою соответствующую таблицу маршрутизации узлами в информации живучести, включенной во второе пинговое сообщение (т.е. узлы в таблице маршрутизации узла, имеющего ID 174). Узел, имеющий ID 144, может повторно отправлять пинговые сообщения с помощью других соседних узлов в кольце 1206.
Следует понимать, что, когда вновь присоединяющийся узел вступает в федерацию, вновь присоединяющийся узел может не найти существующего члена федерации и, таким образом, становится одиночным членом. Таким образом, с вновь присоединяющимся узлом может быть не связано никаких предшествующих, последующих или соседних узлов. Соответственно, вновь присоединяющийся узел отображается как наилучший партнер маршрутизации во всех классах.
Кроме того, хотя способ 1300 был описан применительно к одному кольцу (кольцо 1206), следует понимать, что в некоторых вариантах осуществления узел, который присоединяется к одному кольцу, по существу, также присоединяется к одному или нескольким другим кольцам. Например, согласно фиг.5, узел, который присоединяется к кольцу 551, по существу, также присоединяется к кольцам 543, 531, 522, 511 и 501. Таким образом, способ 1300 можно реализовать для присоединения к совокупности колец. В других вариантах осуществления, некоторые или все этапы способа 1300 могут повторяться при присоединении к нескольким кольцам. Например, согласно фиг.5, один или несколько этапов 1300 могут повторяться, когда узел присоединяется к кольцу 551 и кольцу 514 (например, с использованием псевдонимов). В любом случае, к ID вступающего узла можно осуществлять доступ, и его можно использовать для идентификации присоединяющегося узла в сортированном связном списке, а также в соответствующих иерархически разбитых подсписках, в которых присоединяющийся узел должен участвовать. Принимающий узел идентифицируется из сортированного связного списка и каждого разбитого подсписка. Сообщение присоединения маршрутизируется на обрабатывающий узел (например, на основании ID) в сортированном связном списке и каждом разбитом подсписке. Ответ присоединения поступает от обрабатывающего узла в сортированном связном списке и каждом разбитом подсписке.
На фиг.14 показана иллюстративная логическая блок-схема способа 1400 поддержания узлом принадлежности в инфраструктуре федерации. Способ 1400 будет описан применительно к кольцу 1206. Способ 1400 включает в себя этап отправки первого пингового сообщения на соседний узел (этап 1401). Первое пинговое сообщение указывает, что текущий узел, отправляющий первое пинговое сообщение, является соседом соседнего узла. Первое пинговое сообщение также может включать в себя состояние текущего узла партнера маршрутизации и соседних узлов. Например, узел, имеющий ID 144, может посылать пинговое сообщение на узел, имеющий ID 151. Приняв первое пинговое сообщение, узел, имеющий ID 151, узнает, что узел, имеющий ID 144, является соседом узла, имеющего ID 151. Узел 151 также может выявлять более новую информацию живучести (для других узлов на кольце 1206) от узла 144 в качестве побочного эффекта этого этапа.
Пинговые сообщения можно периодически повторять с указанной частотой на основании, например, состояния конфигурации, ассоциированного с проксимальным кольцом, в которое нужно отправить пинговое сообщение. Частота может изменяться в зависимости от состояния конфигурации. Например, указанная частота пингов для WAN может отличаться от указанной частоты для LAN. Пинговые сообщения также можно посылать в соответствии с шаблоном распределения пингования. Шаблон распределения пингования для исходного узла может указывать, что пинговые сообщения подлежат отправке на соседние узлы в обоих направлениях на кольце. Например, узел, имеющий ID 144, может посылать пинги как в направлении узла, имеющего ID 135, так и в направлении узла, имеющего ID 151. Шаблоны распределения и частоты пингования могут изменяться. Например, в зависимости от кольца близости.
Способ 1400 включает в себя этап приема второго пингового сообщения от соседнего узла (этап 1402). Второе пинговое сообщение указывает текущему узлу, по меньшей мере, что соседний узел, выдающий второе пинговое сообщение, является соседом текущего узла. Второе пинговое сообщение также может включать в себя состояние партнера маршрутизации и соседних узлов передающего соседнего узла. Например, узел, имеющий ID 151, может посылать второе пинговое сообщение на узел, имеющий ID 144. Приняв второе пинговое сообщение, узел, имеющий ID 144, узнает, что узел, имеющий ID 151, является соседом узла, имеющего ID 144. Второе пинговое сообщение также может включать в себя информацию живучести для других узлов на кольце 1206. Таким образом, в целом, пинговыми сообщениями можно обмениваться в пределах диапазона соседства, и их можно использовать для поддержания отношения принадлежности к соседству (для каждого отношения проксимальной принадлежности) и приближенного общего вида соседства для наличия узла в федерации.
Принятое пинговое сообщение можно периодически транслировать/пересылать на другие узлы в проксимальном соседстве, в которое был отправлен пинг (передан исходным узлом). Переправленные пинговые сообщения также можно посылать в соответствии с шаблоном распределения пингования. Шаблон распределения пингования для пересылающего узла может указывать, что пинговые сообщения подлежат отправке на соседние узлы в направлении от исходного узла. Например, узел, имеющий ID 1151, может пересылать пинги, выдаваемые на узле, имеющем ID 144, в направлении узла, имеющего ID 174. Шаблоны распределения пересылки пингов могут изменяться, например, в зависимости от кольца близости.
Узлы можно конфигурировать для приема пинговых сообщений с соответствующими интервалами. Когда ожидаемые пинговые сообщения не принимаются, узел может расценить это как нарушение связи и задать указание phase.unknown для другого узла равным истине для узла, который должен был выдать ожидавшееся, но, по меньшей мере, опоздавшее пинговое сообщение.
Способ 1400 включает в себя этап проксимальной маршрутизации сообщения запроса обновления на совершенный маршрутизирующий узел (этап 1403). Сообщение запроса обновления указывает маршрутизирующему узлу, принимающему такой маршрутизированный запрос обновления, что текущий узел участвует как партнер маршрутизации принимающего маршрутизирующего узла. Сообщение запроса обновления также может включать в себя, по меньшей мере, идентификаторы соседних узлов текущего узла (например, в форме информации живучести). Например, узел, имеющий ID 144, может маршрутизировать сообщение 1216 обновления на узел, имеющий ID 208, (совершенный партнер маршрутизации, смещенный на 64 от 144). Поскольку узел 210 (ранее вычисленный маршрутизирующий узел) является ближайшим к 208, он будет принимать и обрабатывать маршрутизированный запрос обновления. Приняв сообщение 1216 обновления, узел, имеющий ID 210, узнает (или убеждается), что узел, имеющий ID 144, является партнером маршрутизации узла, имеющего ID 210.
Способ 1400 включает в себя этап приема сообщения ответа обновления от обрабатывающего (принимающего) маршрутизирующего узла (этап 1404). Ответ обновления указывает текущему узлу, что обрабатывающий маршрутизирующий узел участвует как партнер маршрутизации текущего узла. Сообщение ответа обновления также может включать в себя, по меньшей мере, идентификаторы соседних узлов обрабатывающих партнеров маршрутизации. Например, узел, имеющий ID 210, может посылать ответ 1207 обновления на узел, имеющий ID 144. Приняв ответ 1207 обновления, узел, имеющий ID 144, узнает, что узел, имеющий ID 210, является партнером маршрутизации узла, имеющего ID 144.
Способ 1400 также может включать в себя этап надлежащего обновления информации узла для указания, что текущий узел и соседний узел участвуют как соседи, и что текущий узел и соседний узел участвуют как партнеры маршрутизации. Например, узел, имеющий ID 144, может обновлять информацию узла, соответствующую узлу, имеющему ID 151, для указания, что узлы, имеющие ID 144 и 141, участвуют в (проксимальном) соседстве. Аналогично, узел, имеющий ID 144, может обновлять информацию узла, соответствующую узлу, имеющему ID 210, для указания, что узлы, имеющие ID 144 и 210, участвуют как партнеры маршрутизации.
В некоторых вариантах осуществления, состояние приложения, сохраненное на указанном узле X, дублируется среди его узлов Neighborhood(X) с использованием протокола надежного распространения. Каждому элементу в состоянии приложения назначен владелец, которым может быть конечная точка, создавшая элемент. Каждому элементу в состоянии приложения также назначается метка времени (также именуемая номером последовательности), задаваемая его владельцем. Метка времени имеет, по меньшей мере, три компонента:
- ID экземпляра (например, беззнаковое целое) владеющей сущности. Должен, по меньшей мере, монотонно (>1) возрастать.
- ID последовательности (например, URI), идентифицирующий конкретную последовательность, генерируемую владельцем. Этот компонент позволяет одному и тому же владельцу генерировать несколько независимых последовательностей.
- Порядковое число (например, беззнаковое целое), идентифицирующее смещение в идентифицированном ID последовательности приложения.
Метки времени элемента используются для обнаружения последней информации, ассоциированной с соответствующим элементом в ходе дублирования, поскольку метки времени элемента генерируют, по меньшей мере, частичный порядок с помощью триплетов <ID экземпляра, ID последовательности и смещение>. Метка времени, ассоциированная с дублируемым элементом, сравнивается с локальной, если таковая существует, для выявления самой поздней. Метки времени элемента также используются для поддержки идемпотентной семантики операций создания/обновления/удаления. Например, когда узел принимает запрос на обновление существующего элемента в состоянии приложения, обновление принимается, только если метка времени, ассоциированная с запросом обновления, выше той, которая ассоциирована с локальным элементом. Методы разрешения конфликтов на основании векторных меток времени можно использовать, когда элементы не могут назначаться одним владельцем. Дублирование состояния приложения обеспечивает отказоустойчивость и облегчает запросы балансировки нагрузки по соседним узлам.
В качестве необязательного поведения, узлы, не обнаруживающие (по истечении периода времени) ожидаемого сообщения обновления или пингового сообщения от (передающих) других партнерских (маршрутизирующих и/или партнерских) узлов, могут посчитать фазовое состояние неизвестным, задать указание phase.unknown равным истине и сообщить об этом другим узлам 3-ей стороны. Другими словами, может потребоваться периодическая генерация обновлений и пингов. Это требование и фактические значения тайм-аута могут быть атрибутом различных проксимальных колец. Например, кольцо может иметь более ограничительные требования к таймингам для некоторых подколец (например, в сегменте LAN), и обнаружение/сообщение отказа узла является относительно быстрым. С другой стороны, кольцо может иметь менее ограничительные требования к таймингам (или даже вообще не иметь требований к таймингам) для других подколец (например, в интернете), и упреждающее обнаружение/сообщение отказа узла является относительно долгим (или не существует).
На фиг.15 показана иллюстративная логическая блок-схема способа 1500 выявления информации живучести для другого узла. Способ 1500 будет описан применительно к кольцу 1206, показанному на фиг.12A и 12B. В целом, любое сообщение, например запрос 1203 синхронизации, ответ 1204 синхронизации, запрос 1216 обновления, ответ 1207 обновления и т.д., может включать в себя, по меньшей мере, один заголовок живучести. В некоторых вариантах осуществления, заголовок живучести включает в себя <ID узла, ID экземпляра, фазу [значение фазового состояния].[указание phase.unknown], значение свежести, значение цвета (близости) и значение веса> для узла. В других вариантах осуществления, заголовок живучести включает в себя <фазу [значение фазового состояния].[указание phase.unknown], значение свежести, значение цвета (близости) и значение веса>. В этих других вариантах осуществления, заголовки живучести можно использовать для расширения заголовков адресации, которые уже включают в себя ID узла и ID экземпляра для узла-отправителя и исходного узла. Поскольку заголовки адресации уже включают в себя ID узла и ID экземпляра, эту информацию можно исключить из заголовка живучести.
Способ 1500 включает в себя этап приема заголовка живучести, представляющего информацию состояния для узла, участвующего в инфраструктуре федерации (этап 1501). Заголовок живучести включает в себя, по меньшей мере, принятый ID участвующего узла, принятый ID экземпляра узла, принятое значение фазы и принятое значение свежести. Например, узел, имеющий ID 144, может принимать первый заголовок живучести в ответе 1204 синхронизации от узла, имеющего ID 151. Первый заголовок живучести может включать в себя < ID участвующего узла, ID экземпляра, значение фазы [значение фазового состояния].[указание phase.unknown], значение свежести, значение цвета (близости) и значение веса> для узла, имеющего ID 174. Значение фазового состояния (например, Inserting, Syncing, Routing, Operating) идентифицирует выраженную фазу узла, имеющего ID 174, на момент первого значения свежести. Значение фазы (например, фазовое состояние: [Inserting, Syncing, Routing, Operating], и phase.unknown) идентифицирует выраженную и/или обнаруженную информацию фазы узла, имеющего ID 174, в момент времени, указанный первым значением свежести.
Однако значение свежести может уменьшаться вследствие задержки передачи. Значение свежести также может уменьшаться с течением времени. Кривые снижения значения свежести могут быть разными (и могут не быть линейными или симметричными) для разных фазовых состояний (включая неизвестное). Таким образом, при переходе между фазами узла, снижение значения свежести может быть нелинейным и/или асимметричным.
Способ 1500 включает в себя этап, на котором обращаются к, по меньшей мере, текущему ID экземпляра, текущему значению фазы и текущему значению свежести для участвующего узла, поддерживаемым на текущем узле (этап 1502). Например, узел, имеющий ID 144, может обращаться к ранее принятым и сохраненным ID экземпляра, значению фазы [значение фазового состояния.][указание phase.unknown], и значению свежести для узла, имеющего ID 174.
Способ 1500 включает в себя этап сравнения, по меньшей мере, принятого ID экземпляра, принятого значения фазы и принятого значения свежести с текущим ID экземпляра, текущим значением фазы и текущим значением свежести, соответственно, на текущем узле (этап 1503). Например, узел, имеющий ID 144, может сравнивать ранее принятые и сохраненные ID экземпляра, значение фазы [значение фазового состояния.][указание phase.unknown] и значение свежести для узла, имеющего ID 174, с ID экземпляра, значением фазы [значение фазового состояния.][указание phase.unknown] и значением свежести, принятыми в заголовке живучести.
Узел, имеющий ID 144, может определить, что информация текущего состояния для узла, имеющего ID 174 (например, принятая от узла, имеющего ID 151), устарела, на основании (по порядку) того, что первый ID экземпляра больше, чем сохраненный на данный момент ID экземпляра для узла, имеющего ID 174, на основании того, что первое значение фазового состояния более продвинуто, чем сохраненное на данный момент значение фазового состояния для узла, имеющего ID 174, или на основании того, что первое значение свежести больше, чем значение свежести, сохраненное на данный момент для узла, имеющего ID 174. Узел, имеющий ID 144, также может определить, что, по меньшей мере, одно указание phase.unkown (сохраненное на данный момент или принятое в заголовке живучести) указывает, что фазовое состояние было известно на момент обнаружения/передачи фазового состояния.
Способ 1500 включает в себя этап определения, подлежит ли обновлению информация состояния для участвующего узла на текущем узле на основании сравнения (этап 1504). Например, на основании сравнения значений для узла, имеющего ID 174, узел, имеющий ID 144, может определить, что информация состояния для узла, имеющего ID 174, подлежит обновлению. Обновление устаревшей информации состояния для узла, имеющего ID 174, может включать в себя замену текущих сохраненных значений (например, ID экземпляра, значения фазового состояния, указания phase.unknown или значения свежести) значениями, включенными в заголовок живучести. Например, узел, имеющий ID 144, может обновлять информацию состояния для узла, имеющего ID 174, для указания, что узел, имеющий ID 174, перешел в более продвинутое фазовое состояние.
В некоторых вариантах осуществления, можно обнаруживать потерю связи с участвующим узлом. Например, узел, имеющий ID 144, может обнаруживать потерю связи с узлом, имеющим ID 151. Согласно фиг.17, в ответ на предыдущую подписку на события живучести 1701 (с конечной точкой узла, имеющего ID 151), прикладной уровень 1752 может посылать событие снижения конечной точки 1703 (с конечной точкой узла, имеющего ID 151) на функциональный уровень 1751. В этих вариантах осуществления, такие обнаруженные условия живучести можно включать в информацию живучести с указателем Phase.Unknown, заданным равным истине, совместно с последним известным значением фазового состояния.
Способ 1500 также может включать в себя этап приема сообщения, которое включает в себя второй заголовок живучести от второго другого узла в инфраструктуре федерации. Например, узел, имеющий ID 144, может принимать сообщение статуса (от узла, имеющего ID 103 или какого-либо другого узла кольца 1206), которое включает в себя второй заголовок живучести. Второй заголовок живучести может включать в себя <ID участвующего узла, второй ID экземпляра, второе значение фазы [значение фазового состояния].[указание phase.unknown], второе значение свежести, второе значение цвета (близости) и второе весовое значение> для узла, имеющего ID 174. Второе значение фазы (например, фазовое состояние: [Inserting, Syncing, Routing, Operating] и указание phase.unknown) идентифицирует выраженную/обнаруженную фазу узла, имеющего ID 174, на момент второго значения свежести.
Альтернативно, приняв первый заголовок живучести, узел, имеющий ID 144, может попытаться связаться непосредственно с узлом, имеющим ID 174. В случае успешного установления связи, узел, имеющий ID 174, может возвращать сообщение (например, ответ синхронизации), имеющее ID узла и второй ID экземпляра в заголовке адресации и имеющее заголовок живучести, включающий в себя < второе значение фазы, второе значение свежести, второе значение цвета (близости) и второе весовое значение>. При обнаружении неудачи, узел, имеющий ID 144 генерирует внутреннее изменение состояния живучести (например, свежесть = max, и указание phase.unknown = true) и обрабатывает изменение состояния, как если бы изменение состояния было принято от другого узла. Такое изменение состояния имеет наивысшее значение свежести.
Способ 1500 также может включать в себя этап сравнения второго ID экземпляра, второго значения фазы и второго значения свежести с текущим ID экземпляра, текущим значением фазы и текущим значением свежести, соответственно (этап 1506). Например, приняв статусное сообщение от узла, имеющего ID 103, узел, имеющий ID 144, может определить, что информация текущего состояния для узла, имеющего ID 151, устарела, на основании (по порядку) того, что второй ID экземпляра больше, чем первый ID экземпляра, того, что вторая фаза более продвинута, чем первое значение фазы, или того, что второе значение свежести больше, чем первое значение фазы.
Способ 1500 также может включать в себя этап определения, подлежит ли обновлению информация состояния для участвующего узла на основании сравнения. Например, на основании сравнения значений для узла, имеющего ID 174, узел, имеющий ID 144, может определить, что информация состояния для узла, имеющего ID 174, подлежит обновлению. Обновление устаревшей информации состояния для узла, имеющего ID 174, может включать в себя замену текущих сохраненных значений (например, ID экземпляра, значения фазового состояния, указания phase.unknown или значения свежести) значениями, включенными во второй заголовок живучести. Например, узел, имеющий ID 144, может обновлять информацию состояния для узла, имеющего ID 174, для указания, что узел, имеющий ID 174, перешел в более продвинутое фазовое состояние.
В некоторых вариантах осуществления, значения фазы сравниваются в контексте равных значений цвета. Как описано выше, узел может участвовать в нескольких кольцах близости. Участие в нескольких кольцах близости может происходить в результате участия в более частном кольце, что предполагает участие в более общем кольце (вдоль общей ветви). Например, согласно фиг.5, участие узла в кольце 532 также означает, что узел участвует в кольцах 522, 511 и 501. Таким образом, цвет более частного кольца также представляет все родительские проксимальные кольца. Также, как описано выше, участие в нескольких кольцах близости может происходить, когда узел в одном кольце зеркально отображается в одно или несколько других колец (потенциально, вдоль разных ветвей). Например, согласно фиг.5, узел, участвующий в кольце 532, может зеркально отображаться в кольцо 531 (или даже кольцо 541, что предусматривает участие в кольцах 531, 522, 511 и 501). Таким образом, цвет одного кольца (например, кольца 531) можно рассматривать как равноправный цвет (или близость) другого кольца (например, кольца 532).
Когда узел участвует в совокупности колец близости с использованием псевдонимов, существует возможность того, что значения фазы (например, значения фазового состояния и/или указания phase.unknown) для узла будут разными для разных колец близости. Таким образом, узел, который принимает информацию состояния для другого узла, идентифицирует соответствующее кольцо близости для информации состояния (цвета), прежде чем определить, подлежит ли информация текущего состояния обновлению для этого узла и цвета. Например, узел, имеющий ID 144, может идентифицировать соответствующее кольцо близости для принятой информации состояния, соответствующей узлу, имеющему ID 174, прежде чем сравнивать принятую информацию состояния с информацией текущего состояния.
Идентификация надлежащего кольца близости может включать в себя сравнение принятого значения цвета с одним или несколькими текущими значениями цвета. Когда принятое значение цвета и текущее значение цвета равны, другую информацию состояния, например текущий ID экземпляра, текущее значение фазы и текущее значение свежести, можно сравнивать с соответствующей принятой информацией состояния, например принятым ID экземпляра, принятым значением фазы и принятым значением свежести. С другой стороны, когда принятое значение цвета и текущее значение цвета различны, дополнительные сравнения не проводятся.
Равенство значений цвета может иметь место по разным причинам. Например, равенство значений цвета может иметь место, когда текущее значение цвета и принятое значение цвета указывают одно и то же кольцо близости (например, кольцо 532). Кроме того, равенство значений цвета может иметь место, когда более частное значение цвета сравнивается с соответствующим родительским значением цвета (например, другим кольцом вдоль той же ветви). Например, сравнение значения цвета кольца 532 со значением цвета кольца 511 (или кольца 522 или 501) может приводить к равенству. Таким образом, дочерняя близость - это родительская близость, но более частная.
Таким образом, в целом, действующие на данный момент узлы в инфраструктуре федерации могут обмениваться выраженной и обнаруженной информацией состояния живучести для других узлов, даже когда связь с этими другими узлами кажется потерянной.
Механизмы самонастройки
В целом, для того чтобы узел стал активным членом федерации (например, присоединился к ней), узел должен связаться с, по меньшей мере, одним другим узлом, который уже является активным членом краевого кольца, к которому он намеревается присоединиться. Чтобы помочь убедиться в том, что эта начальная форма связи доступна, федерации могут использовать механизм самонастройки. Механизм самонастройки можно использовать как последнее прибежище, когда другие типы связи не позволяют идентифицировать активного члена краевого кольца, или ограничения безопасности требуют, чтобы вновь присоединяющийся узел первоначально связывался с, по меньшей мере, одним из множества частных узлов, например затравочными узлами. Таким образом, когда другие типы связи не действуют или вследствие ограничений безопасности, механизм самонастройки можно использовать для идентификации узла, являющегося активным членом краевого кольца.
В некоторых вариантах осуществления, затравочные узлы используются для самонастройки связи с федерацией. Затравочные узлы обеспечивают общеизвестные точки вхождения для некоторых типов чрез(меж)близостной связи. Затравочные узлы помогают восстанавливать разбиения кольца в результате сбоя/восстановления инфраструктуры и общего динамизма. Каждое кольцо может иметь, по меньшей мере, один действующий затравочный узел для обеспечения основных свойств самонастройки для федерации.
Равноправные затравочные узлы могут сами осуществлять связь друг с другом для поддержания структуры кольца (например, двунаправленного связного списка) для близости, которая состоит из, по меньшей мере, всех активных затравочных узлов для этой близости. Специализированный протокол синхронизации затравочных узлов можно использовать для обеспечения каждого затравочного узла, по меньшей мере, полной информацией состояния наличия (активности) всех остальных затравочных узлов. Активный затравочный узел принадлежит краевому кольцу близости, которое является для него базовым кольцом, а также всем остальным кольцам-предкам краевого кольца. Таким образом, затравочный узел может представлять всю ветвь колец близости, например, от краевого кольца затравочного узла до корневого кольца. Соответственно, затравочные узлы могут функционировать как высокодоступные и общеизвестные узлы вхождения в каждом из этих колец близости. В результате, состояние наличия затравочных узлов может быть полезно для различных форм связи (например, межблизостной связи) с федерацией. Соответственно, затравочные узлы могут обеспечивать ряд особых свойств, например, действующих в качестве общеизвестных “точек присоединения” для присоединяющихся узлов, действующих в качестве защищенной службы кольца, помогающей восстанавливать разбиения инфраструктуры, и действующих в качестве стабильного “узла вхождения” для каждой из их близостей.
Для обеспечения данных наличия, акты прибытия и акты постепенного выбытия затравочного узла можно регистрировать в качестве стабильного узла вхождения в точке рандеву в каждой из их близостей. Например, сообщения регистрации можно маршрутизировать на фиксированный URI, ID пункта назначения которого является хэш SHA-1 строки “Proximity:/”. Хотя, в одном варианте осуществления, затравочные узлы, действующие как стабильные узлы вхождения, регистрируются таким образом, существуют другие варианты осуществления, где выбранные незатравочные узлы также могут регистрироваться таким же образом и в тех же или аналогичных протоколах, которые описаны здесь для затравочного узла. Когда стабильный узел вхождения (например, затравочный узел) регистрируется, стабильный узел вхождения может указывать каждое кольцо, которому он принадлежит. Таким образом, информация, поддерживаемая в точке рандеву, идентифицированной этим фиксированным URI, по существу, представляет собой список стабильных узлов вхождения и их соответствующих отношений принадлежности к кольцу. Соответственно, любой узел может ссылаться на точку рандеву, идентифицированную этим фиксированным URI для получения списка доступных стабильных узлов вхождения и их отношений принадлежности к кольцу.
В одном варианте осуществления, стабильный узел вхождения непосредственно регистрирует эти события прибытия и выбытия. В другом варианте осуществления, стабильный узел вхождения регистрирует эти события непосредственно в точке рандеву в его кольце непосредственной близости, и эта точка рандеву прозрачно облегчает (непосредственно или опосредованно) обновление всех остальных надлежащих точек рандеву в каждом из оставшихся колец близости, которым принадлежит регистрирующий/нерегистрирующий стабильный узел вхождения. Свойства упорядочения и распространения состояний приложения федерации можно использовать для поддержания и распространения этой информации регистрации стабильного узла вхождения. Например, протокол надежного распространения можно использовать для дублирования сохраненного состояния приложения среди соседних узлов узла.
Продвижение данных присутствия стабильного узла вхождения к корневому кольцу позволяет другим узлам в федерации искать, по меньшей мере, один узел вхождения в каждой близости. Поиск узлов вхождения можно облегчить за счет маршрутизации сообщения поиска узла к определенной выше точке рандеву в самом нижнем общем предшествующем кольце [Lowest Common Ancestor Ring] (“LCAR”) краевого кольца узла, осуществляющем поиск, и нужном кольце близости. Например, согласно фиг.5, узел в кольце 541 может желать установить связь с узлом в кольце 533. Однако узел в кольце 541 может не иметь непосредственно информации о каком-либо узле в кольце 533. Таким образом, узел в кольце 541 может посылать сообщение поиска узла в кольцо 522 (LCAR кольца 541 и кольца 533). Узел точки рандеву в кольце 522, который обрабатывает информацию присутствия узла вхождения (например, вынужденного существовать в системе вследствие выдачи сообщения регистрации этим узлом вхождения), может возвращать сообщение ответа поиска с контактной информацией для, по меньшей мере, зарегистрированного стабильного узла вхождения в кольце 533.
В некоторых вариантах осуществления, стабильные узлы вхождения являются затравочными узлами, специально настроенными как стабильные узлы вхождения для поддержания данных присутствия для различных близостей. В других вариантах осуществления, другие типы узлов также могут функционировать как стабильные узлы вхождения, поддерживающие данные присутствия для различных близостей и также могут быть способны осуществлять другие операции. Например, определенные другие типы узлов могут быть сконфигурированы (например, администратором) как высокодоступные и, таким образом, пригодные в качестве стабильных узлов вхождения (т.е. для регистрации вышеописанным образом). Однако другие типы узлов могут не включать в себя дополнительные функции затравочного узла (например, может не быть доверенным в качестве защищенной службы кольца). В некоторых вариантах осуществления, точки рандеву, которые поддерживают состояние наличия узла вхождения для своей непосредственной близости, могут регистрироваться как стабильные узлы вхождения в предшествующем(их) кольце или кольцах.
Межблизостная связь
Варианты осуществления настоящего изобретения также могут облегчать межблизостную связь, например, между узлами в разных проксимальных ветвях дерева колец. Межблизостную связь можно использовать для связи с и/или между одним или несколькими, и потенциально всеми, кольцами близости в проксимально разбитой инфраструктуре кольца. На фиг.5A показано иллюстративное дерево разбиения 500 по признаку близости с дополнительными уровнями детализации в участках дерева 500 разбиения. Межблизостная связь может происходить между различными узлами, показанными на фиг.5A.
Согласно фиг.5A, дерево 500 разбиения колец дополнительно включает в себя различные подкольца под кольцом 513. Каждое из дополнительных подколец представляет раздел сортированного связного списка. Как описано выше согласно фиг.5, в дереве 500 разбиения, корневое кольцо 501 может быть разбито на совокупность подколец, включая подкольца 511, 512, 513 и 514, на основании критерия 571 (критерия границы первого административного домена). Также, как описано выше согласно фиг.5, подкольцо 511 дополнительно может быть разбито на совокупность подколец, включя подкольца 521, 522 и 523, на основании критерия 581 (критерия границы второго административного домена). Другие подкольца под подкольцом 522 далее разделяются на основании другого критерия.
Как описано выше, в дереве 500 разбиения, каждый узел имеет единственный ID и участвует в кольцах вдоль соответствующего пути разбиения (ветви) от корня к листу. Например, каждый узел, участвующий в подкольце 552, также будет участвовать в подкольцах 543, 531, 522, 511 и в корне 501.
Согласно фиг.5A, подкольцо 513 также может дополнительно делиться на совокупность подколец, включающую в себя подкольца 561 и 562, на основании другого критерия, например юрисдикции государства. Подкольцо 562 также дополнительно может быть разбито на совокупность подколец, включающую в себя подкольца 571 и 572, на основании другого критерия, например юрисдикции города. Соответственно, согласно фиг.5A, межблизостную связь можно использовать для отправки сообщения с узла кольца 541 на узел кольца 572, без необходимости связи по ветви от кольца 541 на корневое кольцо 501 и затем обратно от корневого кольца 501 на кольцо 572.
Межблизостная связь может быть включена как часть шаблона связи, например широковещание, групповая адресация или произвольная адресация, реализованные в дереве колец. Широковещание может включать в себя отправку сообщения на все активные узлы в дереве колец. Групповая адресация может включать в себя отправку сообщения группе узлов в дереве колец. Произвольная адресация может включать в себя отправку сообщения на, по меньшей мере, один узел в дереве колец.
На фиг.19A показано иллюстративное дерево 1900 разбиения колец для по признаку близости, которое облегчает межблизостную связь. В дереве 1900 разбиения колец, корневое кольцо 1901 делится на совокупность подколец, включающую в себя подкольца 1, 2, 3 и 4, на основании выбранного критерия (например, критерия границы первого административного домена). Подкольцо 1 далее делится на подкольца 11, 21, 31 и 41. Подкольцо 11 далее делится на подкольца 111, 211 и 311. Подкольцо 21 далее делится на подкольца 121, 221, 321, 421 и 521. Хотя это явно не указано, другие подкольца, например подкольца 2, 3, 4, 31 и 41, также могут дополнительно делиться.
Соглашение о нумерации колец в дереве 1900 разбиения колец для по признаку близости устроено так, что любые цифры после первой цифры указывают родительское кольцо кольца. Например, “11” в кольце “311” указывает, что кольцо 11 является родительским кольцом кольца 311. Аналогично, “1” в кольце “41” указывает, что кольцо 1 является родительским кольцом кольца 41. Глобальное кольцо 1901 является родительским кольцом для любых колец, нумерованных одной цифрой, например колец 1, 2, 3 и 4. Аналогично дереву 500 разбиения колец по признаку близости, показанному на фиг.5A, дерево 1900 разбиения колец может быть разбито на основании различных критериев близости.
В описании и нижеследующей формуле изобретения обозначение R[“<номер>”] используется со ссылкой на номер кольца. Например, R[“11”] относится к кольцу 11. В описании и нижеследующей формуле изобретения обозначение N[<номер>] используется со ссылкой на номер узла. Например, N[1311] относится к узлу 1311.
Для облегчения связи в дереве колец, узлы могут поддерживать таблицу вхождений, которая сопоставляет кольца с соответствующими узлами вхождения в этих кольцах. Как описано выше, на основании конфигурации дерева 1900 разбиения колец, родительское кольцо содержит все узлы из каждого из его дочерних колец. Например, кольцо 11 содержит все узлы из R[“111”], R[“211”], R[“311”]. Таким образом, отправки сообщения на кольцо 11 достаточно для получения сообщения на любом узле в кольце R[“111”], R[“211”] и R[“311”]. Соответственно, в некоторых вариантах осуществления, таблицу вхождений узла можно сократить до вхождений для тех колец, которые относительно различны с точки зрения кольца, где находится узел. Например, N[1111] может просто поддерживать запись для R[“21”] - N[1121] - поскольку поддержка записей для нескольких дочерних колец или R[“21”] была бы избыточной.
Создание и поддержание множеств коллатеральных колец
В этом описании и в нижеследующей формуле изобретения любое кольцо одного уровня с указанным кольцом определяется как “коллатеральное кольцо” указанного кольца. В этом описании и в нижеследующей формуле изобретения любое кольцо одного уровня с предшествующими кольцами указанного кольца также определяется как “коллатеральное кольцо” указанного кольца. Любое коллатеральное кольцо указанного кольца также является коллатеральным кольцом всех узлов, включенных в указанном кольце.
Таким образом, например, согласно фиг.19A, R[“211”] является коллатеральным кольцом для R[“111”], поскольку R[“211”] равноправно R[“111”]. R[“211”] также является коллатеральным кольцом любого узла, включенного в R[“111”], например N[1311]. Кроме того, R[“21”] является коллатеральным кольцом для R[“111”], поскольку R[“21”] равноправно R[“11”] (т.е., предку R[“111”]). R[“21”] также является коллатеральным кольцом любого узла, включенного в R[“111”], например N[1111].
В этом описании и в нижеследующей формуле изобретения “множество коллатеральных колец” (“CRS”) определяется как множество из одного или нескольких коллатеральных колец с точки зрения указанного кольца или узлов в указанном кольце. Например, согласно фиг.19A, множество коллатеральных колец для R[“221”], а также любых узлов в R[“221”], например N[8221], включает в себя R[“11”], R[“121”], R[“31”], R[“41”], R[“2”], R[“3”] и R[“4”].
Таким образом, для облегчения межблизостной связи, узел может поддерживать таблицу вхождений CRS, которая включает в себя одно или несколько коллатеральных колец и один или несколько соответствующих узлов вхождения в одном или нескольких коллатеральных кольцах. Таблица вхождений CRS может представлять собой структуру данных, включающую в себя один или несколько элементов <коллатеральное кольцо, узлы вхождения от 1 до N>, где N - некоторое целое число. Например, структура данных может иметь формат <коллатеральное кольцо_01, узел вхождения_01, узел вхождения_02, …>, где многоточие представляет один или несколько дополнительных узлов вхождения в коллатеральном кольце_01.
Для создания таблицы вхождений CRS, узел может использовать локальную информацию, сообщения протокола рандеву (например, пинговые сообщения, сообщения обновления и ответы обновления), используемые для распространения состояния в дереве колец, сообщений приложения и сообщения, используемые для облегчения указанных шаблонов связи (например, широковещания, групповой адресации и произвольной адресации) в дереве колец.
Узел может использовать локальную информацию, например информацию таблицы маршрутизации, из всех уровней колец, в которых участвует узел. Например, согласно фиг.19, N[1121] может быть соседом N[1311] в R[“1”]. Одно коллатеральное кольцо для N[1311] с точки зрения N[1121] представляет собой R[“21”]. Соответственно, N[1311] может вставить пару (R[“21”], N[1121]) (в этом случае, элемент, имеющий единственный узел вхождения) в таблицу вхождений CRS для N[1311]. Используя этот тип локальной информации, узел может вводить вхождения в таблицу вхождений CRS.
Узлы могут, помимо специально предназначенных сообщений, распространять свою информацию таблицы вхождений CRS на другие узлы в сообщениях, которые иначе использовались бы в других целях, например для распространения информации состояний соседства и партнера маршрутизации. Например, узлы могут включать в себя состояние таблицы вхождений CRS в пинговых сообщениях, передаваемых на соседние узлы, и в сообщениях обновления и ответах обновления, которыми обмениваются маршрутизирующие узлы-партнеры. Узлы, которые принимают состояние таблицы вхождений CRS от другого узла, могут использовать принятое состояние таблицы вхождений CRS для пополнения и/или поддержания своей собственной таблицы вхождений CRS.
Например, когда узел обменивается сообщениями пингования/обновления рандеву со своими узлами-соседями/партнерами (например, на уровне протокола рандеву), узел также может обмениваться (по меньшей мере, частью и, потенциально, всей) своей таблицей вхождений CRS (и использовать состояние таблицы вхождений CRS, принятое от своих соседей/партнеров для обновления своей собственной таблицы. Предположим, например, что N[1311] не имеет предыдущей информации любого узла в R[“3”] (в контексте или кольце 1901). Однако N[1311] не имеет соседа N[8221] (в R[“1”]), и таблица вхождений CRS для N[8221] имеет вхождение (R[“3”], N[8223]). По меньшей мере, поскольку N[1311] и N[8221] являются событиями, N[1311] и N[8221] могут, время от времени, посылать друг другу пинговые сообщения. N[8221] может включать (по меньшей мере, часть и, потенциально, всю) свою таблица вхождений CRS в пинговые сообщения, направляемые на N[1311]. Таким образом, когда N[1311] принимает пинговое сообщение от N[8221], то пинговое сообщение может включать в себя таблицу вхождений CRS для N[8221]. Из таблицы вхождений CRS для N[8221], N[1311] может идентифицировать элемент <R[“3”], N[8223], …> и включать элемент <R[“3”], N[8223], …>) в свою собственную таблицу вхождений CRS. N[1311] также может идентифицировать другие элементы для других колец в своем CRS и включать эти другие элементы в свою собственную таблицу вхождений CRS.
Состоянием таблицы вхождений CRS можно аналогично обмениваться в сообщениях обновления и ответах обновления, которыми обмениваются партнеры маршрутизации в кольце. Кроме того, любой протокол маршрутизации сообщения можно использовать для изучения (например, информации живучести) узлов вхождения CRS. Кроме того, можно использовать конкретные сообщения, предназначенные для поддержания таблиц вхождений CRS.
Состояние таблицы вхождений CRS также можно выявлять в сообщениях, которые способствуют указанным шаблонам связи (например, широковещанию, групповой адресации и произвольной адресации) в дереве колец. Например, для широковещания сообщения на каждый узел в дереве колец, алгоритм широковещания может использовать различные типы сообщений, специфических для широковещания. Узлы, которые посылают эти сообщения, специфические для широковещания, могут включать состояние таблицы вхождений CRS в сообщения, специфические для широковещания. Аналогично, при групповой адресации сообщения на каждый узел в группе узлов, алгоритм групповой адресации может использовать различные типы сообщений, специфических для групповой адресации. Узлы, которые посылают эти сообщения, специфические для групповой адресации, могут включать состояние таблицы вхождений CRS в сообщения, специфические для групповой адресации. Аналогично, при произвольной адресации сообщения на, по меньшей мере, один узел, алгоритм произвольной адресации может использовать различные типы сообщений, специфических для произвольной адресации. Узлы, которые посылают эти сообщения, специфические для произвольной адресации, могут включать состояние таблицы вхождений CRS в сообщения, специфические для произвольной адресации. Узлы, которые принимают сообщения, зависящие от шаблона связи, могут идентифицировать соответствующие записи (например, элементы <коллатеральное кольцо, узлы вхождения>) и включать некоторые или все состояния из этих записей в свою собственную таблицу вхождений CRS.
Состояние CRS также можно выявлять в сообщениях компонентов приложений, которыми могут обмениваться приложения. Согласно фиг.1, прикладные уровни 121, 122 и/или 123 могут обмениваться сообщениями компонентов приложений, которые включают в себя состояние CRS. Приняв сообщение компонента приложения, включающее в себя состояние CRS, прикладной уровень может перенести состояние CRS на соответствующие другие, более низкие уровни, например на уровень протокола рандеву, для расширения существующего состояния CRS.
Состояние CRS может обеспечиваться приложением и/или оборудованием и может конфигурироваться узлами в дереве колец.
Согласно фиг.19A, если узел находит, что ему известна совокупность узлов вхождения одного и того же кольца, он может принять решение сохранить два или более узлов вхождения для кольца. В некоторых вариантах осуществления, узел произвольно выбирает узел вхождения из любых сохраненных узлов вхождения. В других вариантах осуществления, политика применяется для помощи в выборе указанного узла вхождения из любых сохраненных узлов вхождения. Политика может указывать, что выбранный узел вхождения должен быть каждый одним и тем же узлом вхождения. Альтернативно, политика может указывать, что выбранный узел вхождения должен изменяться среди любых сохраненных узлов вхождения. Например, в некоторых вариантах осуществления, узлы вхождения выбираются по круговой схеме, чтобы можно было равномерно распределять нагрузку среди любых сохраненных узлов вхождения.
Кроме того, когда сохраняются несколько узлов вхождения, узел может эффективно переходить к другому узлу вхождения, например, если первый выбранный узел вхождения неисправен, занят или недоступен по какой-либо другой причине.
Альтернативно, узел может сохранять единственный узел вхождения для кольца.
Время от времени узел может обнаруживать дополнительные узлы вхождения для кольца. В некоторых вариантах осуществления, когда узел сохраняет единственный узел вхождения или ему не хватает памяти для хранения дополнительных узлов вхождения, узел может определять, должен ли вновь принятый узел вхождения замещать существующий узел вхождения. В некоторых вариантах осуществления, узел может использовать функцию для вычисления ранга для каждого кандидата в узлы вхождения со следующими параметрами: расстояние узла вхождения, свежесть информации узла вхождения и вес узла вхождения (например, предпочтительную конфигурацию). Узел вхождения более высокого ранга сохраняется.
Таблица вхождений CRS может быть полной или неполной. Полная таблица вхождений CRS включает в себя, по меньшей мере, один узел вхождения для каждого кольца в CRS узла. Например, полная таблица вхождений CRS для узла 1311 включает в себя, по меньшей мере, один узел вхождения в каждом из колец 111, 211, 21, 31, 41, 2, 3 и 4.
С использованием вышеописанных механизмов может быть невозможно построить полные таблицы вхождений CRS с точки зрения одного или нескольких колец и/или узлов в иерархии проксимальных колец. В некоторых вариантах осуществления возможно, что лишь информация состояния таблицы маршрутизации формирует полную таблицу вхождений CRS для каждого узла в дереве колец. Например, информация, относящаяся к таблице маршрутизации, распространяемая (например, в пинговых сообщениях, сообщениях запроса обновления и сообщениях ответа обновления) в дереве колец 1900 может формировать полную таблицу вхождений CRS для каждого узла в каждом из указанных колец.
Однако в других распределенных сетевых средах динамический характер кольца и/или задержка в обмене состоянием, связанным с таблицей вхождений, может затруднять построение полной таблицы вхождений. Альтернативно, в этих других средах, может существовать одно или несколько колец из множества коллатеральных колец кольца или узла, о которых узел или кольцо не знает в любое данное время. Например, согласно фиг.19A, если предположить, что N[8004] только что вступил, и до этого не существовало ни одного узла, принадлежащего R[“4”], большинство узлов не будет иметь узел вхождения для R[“4”], пока трафик сообщений (например, сообщений пингования/обновления) или другие действия не приведут к распределению этой информацию по всей инфраструктуре кольца. Таким образом, поддержание полной таблицы вхождений CRS на узле не всегда возможно вследствие динамизма сети (например, отказов узла, отказов связи, задержек передачи, добавления узлов и т.д.). Соответственно, во многих средах узел поддерживает частичную таблицу вхождений CRS, включающую в себя узлы вхождения для не всех колец в CRS узла.
Межблизостная связь с использованием таблицы вхождений CRS
Узел может использовать информацию в таблице вхождений CRS для осуществления межблизостной связи (например, без необходимости маршрутизировать сообщения на LCAR кольца-отправителя и кольца назначения). Согласно фиг.19A, на основании соответствующих вхождений в таблице вхождений CRS, N[1311] (например, узел-издатель) может иметь возможность осуществлять межблизостную связь непосредственно на один или несколько из R[“111”], R[“211”], R[“21”], R[“31”], R[“41”], R[“2”], R[“3”] и R[“4”]. Например, в некоторый момент времени таблица вхождений CRS для N[1311] может включать в себя следующие вхождения:
R[“2”] : N[1112]
R[“3”] : N[8223]
R[“21”] : N[1121]
R[“31”] : N[1131]
R[“111”] : N[1111]
R[“211”] : N[1211].
Эти вхождения можно использовать для прямой связи с R[“111”], R[“211”], R[“21”], R[“31], R[“2”] и R[“3”]. Например, N[1311] может осуществить связь 52 на R[“111”], N[1311] может осуществить связь 51 на R[“211”], N[1311] может осуществить связь 53 на R[“21”] (N[1121] принадлежит R[“21”] и R[“221”]), N[1311] может осуществить связь 56 на R[“31”], N[1311] может осуществить связь 57 на R[“2”], и N[1311] может осуществить связь 58 на R[“3”]. Со временем, N[“1311”] может идентифицировать вхождения (например, элементы <коллатеральное кольцо, узел вхождения>) для R[“41”] и R[“4”]. Эти вхождения можно идентифицировать из обновленной локальной информации, из таблиц вхождений CRS, содержащихся в сообщениях протокола рандеву (например, пинговых сообщениях, сообщениях обновления и ответах обновления), через состояние таблицы вхождений CRS, содержащееся в сообщениях, зависящих от шаблона связи, и посредством других механизмов, например компонента приложения.
Алгоритм нисходящей маршрутизации
В федерации рандеву (с или без таблиц вхождений CRS), возможен случай, когда сообщение подлежит маршрутизации на узел, ближайший к данному ID узла в указанном кольце близости, которое не является предком по отношению к краевому кольцу (или в нем), откуда исходит сообщение (далее именуемой “нисходящей маршрутизацией”). Одним примером этого является облегчение межблизостной связи от узла в исходном кольце на коллатеральное кольцо, когда узел в исходном кольце не знает об узле вхождения для коллатерального кольца. На фиг.19B показан еще один вид иллюстративного дерева разбиения колец по признаку близости 1900. Например, согласно фиг.19B, может быть так, что N[1311] нужно осуществить связь, адресованную узлу в R[“4”] или R[“41”].
В данной федерации рандеву, можно задать следующую функцию:
RouteDown(M, P, ID): федерация должна доставлять сообщение M на узел, ближайший к ID в близости P. Близость P может представлять собой любое кольцо близости в федерации (краевое или промежуточное), которое не является предком по отношению к краевому кольцу (или в нем) исходного узла.
В некоторых вариантах осуществления, сообщение M никогда не маршрутизируется над узлами в LCAR краевого кольца исходного узла и целевого кольца близости P. Например, для реализации нисходящей маршрутизации от N[1311] к R[“41”] может не требоваться маршрутизировать сообщение над R[“1”] (LCAR для R[“311”] и R[“41”]). Однако, в других вариантах осуществления, при необходимости сообщение можно маршрутизировать над LCAR.
Функция RouteDown(M, P, ID) может включать в себя идентификацию узла вхождения, про который известно, что он принадлежит целевому кольцу близости P. Передающий узел может идентифицировать узел вхождения в целевом кольце близости с использованием разнообразных механизмов. Передающий узел может быть исходным узлом (первым передающим узлом). Передающий узел также может быть промежуточным узлом, который принимает сообщение от исходного узла или другого промежуточного узла и затем пересылает сообщение.
Передающий узел может использовать локальную информацию, например, информацию конфигурации или локально кэшированную информацию (например, помимо таблицы вхождений CRS), чтобы идентифицировать узел вхождения для целевого кольца близости. Например, N[1311] может иметь доступ к кэшу и конфигурации 1902, которая включает в себя информацию конфигурации или локально кэшированную информацию о кольцах в дереве колец 1900. В некоторых средах, локальная информация о федерации получается посредством механизмов связи вне федерации (т.е. внеполосных). Локальную информацию можно использовать для идентификации любых узлов в точном целевом кольце близости P. При обнаружении каких-либо узлов в точном целевом кольце близости, сообщение M можно пересылать на один из них. Например, N[1311] может быть способен использовать кэш и конфигурацию 1902 для идентификации N[8004] и пересылки сообщения 1903 на R[“4”].
Передающий узел может использовать таблицу вхождений CRS для нахождения любых узлов вхождения в целевом кольце близости P. При обнаружении каких-либо узлов вхождения в целевом кольце близости, сообщение M можно пересылать на узел вхождения в целевом кольце близости P. Например, когда N[7521] является пунктом назначения для сообщения 1903, N[1311] может идентифицировать N[6521] как узел вхождения для R[“521”]. Соответственно, сообщение 1903 можно маршрутизировать на N[6521] (или в R[“521”]). В R[“521”], N[6521] может затем попытаться маршрутизировать сообщение 1903 на N[7521] с использованием связи внутри кольца. Таким образом, если передающий узел способен идентифицировать узел вхождения для целевого кольца близости, он пересылает сообщение на точное целевое кольцо близости. Например, если N[“6521”] способен идентифицировать узел вхождения для R[“21”], он пересылает сообщение 1903 в R[“21”] (пунктирная линия).
С другой стороны, когда передающий узел не способен идентифицировать ни один из узлов вхождения целевой близости пункта назначения (например, из локальной информации или таблицы вхождений CRS), передающий узел может проверить свою таблицу вхождений CRS для размещения узлов вхождения для любых предшествующих колец в целевом кольце близости. Например, возможен случай, когда N[1311] пытается отправить сообщение на узел в R[“121”], однако N[1311] может быть не способен идентифицировать узел вхождения для R[“121”]. Соответственно, N[1311] может обращаться к таблице вхождений CRS 1904 для размещения N[6521] (узла вхождения в R[“21”]). N[1311] может пересылать сообщение на N[6521], который теперь становится передающим узлом для сообщения.
Логически, сообщение 1903 теперь можно рассматривать как «находящееся в» R[“21”], поскольку N[6521] также является узлом из R[21]. Затем N[6521] может попытаться идентифицировать узел вхождения в R[221] (целевой близости). Например, N[6521] может обращаться к локальной информации, таблице вхождений CRS, и/или может (рекурсивно) применять алгоритм RouteDown. Может быть так, что N[6521] идентифицирует N[3221] как узел вхождения в R[221]. Соответственно, N[6521] может посылать сообщение 1903 на N[3221]. Затем N[3321] может маршрутизировать сообщение 1903 на надлежащий узел в R[221] с использованием связи внутри кольца.
При необходимости (например, в более глубоких деревьях, чем показано на фиг.19B), сообщение можно передавать на предки, все более и более близкие к целевому кольцу близости, пока не будет идентифицирован узел вхождения в целевом кольце близости или пока не останется ни одного предшествующего кольца.
Передающий узел также может маршрутизировать запрос поиска узла вхождения, содержащий, по меньшей мере, целевую близость, к механизму директорий узлов вхождения, например, используемому для самонастройки федерации. Маршрутизация запроса поиска узла вхождения может ограничиваться LCAR передающего узла и целевого кольца. Например, N[1311] может маршрутизировать Look Up Request (запрос поиска) 1906 в точку 7651 рандеву для запрашивания узлов вхождения для R[“31”]. Механизм директорий узлов вхождения может возвращать список потенциальных узлов вхождения. Например, точка 7651 рандеву может возвращать список потенциальных узлов вхождения (включающий в себя N[8431]), и, по меньшей мере, затравочные узлы, зарегистрированные с этой точкой рандеву для целевой близости в ответе 1907 поиска.
Передающий узел учитывает любые вновь обнаруженные узлы, идентифицированные в сообщении ответа поиска (отправленного из точки рандеву), и пересылает сообщение M на один из этих узлов вхождения. Учет вновь обнаруженных узлов может обуславливать расширение и иную поддержку таблицы вхождений CRS, а также другой локально кэшированной информации наличия узла. Сообщения ответа поиска также может содержать другую информацию наличия узла. Например, конкретные узлы вхождения, про которые известно, что они важны передающему узлу для возможного включения в таблицу вхождений CRS передающего узла.
Таким образом, если один или несколько доступных механизмов обеспечивают, по меньшей мере, узел вхождения в целевом кольце близости, сообщение M отправляется (либо исходным передающим узлом, либо узлом вхождения в предшествующем кольце целевой близости, либо искомым узлом вхождения) на, по меньшей мере, один из этих узлов вхождения в целевом кольце. Сообщение M может включать в себя инструкции для узла вхождения в целевом кольце близости для маршрутизации сообщения M на ID. С другой стороны, ни один из доступных механизмов не обеспечивает узел вхождения в целевом кольце близости, запрос RouteDown может возвращаться на исходный передающий узел.
В некоторых вариантах осуществления, исходный узел присоединяет заголовок сквозного сообщения RouteDown к сообщению, в котором заголовок сообщения RouteDown задает URI целевой близости.
Если какие-либо из вышеописанных механизмов идентифицируют несколько узлов “следующего перехода”, можно выбрать один узел. При выборе одного узла (например, разрыве связи), можно выбирать узлы, которые ближе к целевой близости P, затем можно выбирать узлы с более высоким весом, затем можно выбирать узлы, которые ближе к ID пункта назначения для M. Если ни один механизм не приводит к выбору, узел можно выбрать произвольно. Если попытка переслать сообщение M завершается неудачей при наличии нескольких кандидатов, можно повторить попытку пересылки, пока существуют исправные узлы-кандидаты.
Можно установить обратный путь сообщения статуса/отказа, когда сообщение приложения проходит от отправителя через посредников на конечный узел назначения. После доставки сообщения в пункт назначения или обнаружения отказа, соответствующее сообщение отказа/статуса можно посылать обратно отправителю вдоль этого пути.
На фиг.19C показано представление разбиения части иллюстративного дерева 1900 разбиения колец по признаку близости. На фиг.19D показана более подробная схема кольца 11 из иллюстративного дерева 1900 разбиения колец по признаку близости. На фиг.20 показана иллюстративная логическая блок-схема способа 2000 поддержания множества коллатеральных колец для узла в дереве колец. Способ 2000 будет описан применительно к кольцам, узлам, сообщениям и данным, показанным на фиг.19C и 19D.
Способ 2000 включает в себя этап, на котором узел обращается к таблице вхождений множества коллатеральных колец, предназначенной для хранения вхождений множества коллатеральных колец для узла (этап 2001). Каждое вхождение множества коллатеральных колец способно указывать коллатеральное кольцо узла и, по меньшей мере, один соответствующий узел вхождения в коллатеральном кольце узла. Например, N[1311] может обращаться к таблице вхождений CRS 1904, которая предназначена для хранения вхождений множества коллатеральных колец, в формате <коллатеральное кольцо, узлы вхождения от 1 до N>, где N - некоторое целое число, для N[1311]. Таким образом, таблица вхождений CRS 1904 может включать в себя нуль или более элементов <коллатеральное кольцо, узел вхождения>, причем каждый включенный элемент указывает коллатеральное кольцо для N[1311], и один или несколько соответствующих узлов вхождения в этом коллатеральном кольце. Например, согласно фиг.19C, таблица вхождений CRS 1904 включает в себя вхождение CRS <R[“51”], N[8651], …>, указывающее, что N[8651] является одним из узлов вхождения от 1 до N в R[51] (коллатеральном кольце для N[1311] и R[“311”]).
Способ 2000 включает в себя этап, на котором обнаруживают информацию таблицы вхождений множества коллатеральных колец из доступных ресурсов, которые поддерживают информацию, относящуюся к конфигурации дерева колец (этап 2002). Например, N[1311] может выявлять информацию таблицы вхождений множества коллатеральных колец из источников, которые поддерживают информацию, относящуюся к конфигурации дерева колец 1900. Как описано выше, различные источники информации таблицы вхождений CRS могут быть доступны узлу. Например, узел может иметь доступ к локальной информации, например, локальной информации конфигурации и кэша, может обращаться к состоянию, связанному с CRS, включенному в сообщения протокола рандеву, например, пинговые сообщения, сообщения обновления и ответы обновления, используемые для распространения состояния в дереве колец, может обращаться к состоянию, связанному с CRS, включенному в сообщения приложения, и может обращаться к состоянию, связанному с CRS, из сообщений, используемых для облегчения указанных шаблонов связи, например широковещания, групповой адресации и произвольной адресации, в дереве колец.
Таким образом, согласно фиг.19C, возможен случай, когда N[1311] обращается к локальной конфигурации 1921. Из локальной конфигурации 1921, N[1311] может обнаруживать вхождение CRS <R[“111”], N[1111], …>, указывающую, что N[1111] является, по меньшей мере, одним из узлов вхождения в R[“111”] (коллатеральном кольце для N[1311] и R[“311”]). N[1311] также может принимать сообщение 1971 приложения. Из сообщения 1971 приложения N[1311] может обнаруживать информацию 1972 CRS. Информация 1972 CRS может содержать или не содержать состояние CRS для колец в CRS для N[1311]. N[1311] также может принимать сообщение 1973, характерное для шаблона связи. Из сообщения 1973, характерного для шаблона связи, N[1311] может выявлять состояние 1974 CRS. Состояние 1974 CRS может содержать или не содержать состояние CRS для колец в CRS для N[1311].
Согласно фиг.19D, N[1311] может выявлять состояние CRS в сообщениях протокола рандеву и обмениваться ими. Поскольку N[1111] принадлежит R[“111”], N[1211] принадлежит R[“211”], и N[1311] принадлежит R[“311”], каждый из узлов N[1111], N[1211], N[1311] также принадлежит R[“11”]. Как описано выше, узлы, которые принадлежат общему кольцу, могут обмениваться пинговыми сообщениями, сообщениями обновления и ответами обновления для поддержания информации таблицы маршрутизации. Таким образом, узлы в R[“11”] могут обмениваться пинговыми сообщениями, сообщениями обновления, и ответами обновления для поддержания информации таблицы маршрутизации для R[“11”]. Состояние CRS можно включать в пинговые сообщения, сообщения обновления и ответы обновления, участвующие в обмене между узлами, а также другие сообщения протокола рандеву и приложения.
Например, N[A11] (сосед N[1311] в R[“11”]) может посылать пинговое сообщение 1931, включающее в себя состояние 1932 CRS, на N[1311]. Из состояния 1932 CRS, N[1311] может обнаруживать вхождение CRS <R[“31”], N[1131]>, указывающее, что N[1131] является узлом вхождения в R[“31”] (коллатеральном кольце для N[1311] и R[“311”]). Вхождения 1932 CRS могут представлять собой полный или частичный список вхождений CRS в таблице вхождений CRS для N[A11]. N[1311] может также посылать пинговые сообщения, включающие в себя состояние CRS, своим соседям. Например, N[1311] может посылать пинговое сообщение 1945, включающее в себя состояние 1934 CRS, на N[E11] (сосед N[1311] в R[“11”]). Вхождения 1934 CRS могут включать в себя полный или частичный список вхождений CRS из таблицы 1904 вхождений CRS.
N[1311] также может отправлять и принимать сообщения обновления и ответы обновления, которые включают в себя информацию, связанную с CRS. Например, N[1311] может посылать сообщение 1933 обновления, включающее в себя вхождения 1934 CRS, на N[D11] (партнер маршрутизации для N[1311] в R[“11”]). N[D11] может в ответ посылать ответ 1937 обновления, включающий в себя вхождения 1938 CRS, на N[1331]. Вхождения 1938 CRS могут представлять собой полный или частичный список вхождений CRS в таблице вхождений CRS для N[D11]. Аналогично, N[1311] может принимать сообщение обновления 1941, включающий в себя вхождения 1942 CRS, от N[C11] (партнера маршрутизации для N[1311] в R[“11”]). Вхождения 1942 CRS могут представлять собой полный или частичный список вхождений CRS в таблице вхождений CRS для N[C11]. N[1331] может в ответ посылать ответ 1943 обновления, включающий в себя вхождения 1934 CRS, на N[“C11”].
Узел также может принимать информацию, связанную с таблицей вхождений множества коллатеральных колец, из доступных ресурсов, указывающую (непосредственно или опосредованно), что вхождение CRS уже не верно, например указание, что связь с узлом вхождения невозможна. Любой ресурс, используемый для отправки состояния, связанного с CRS, также можно использовать для отправки указания, которое можно интерпретировать в том смысле, что вхождение CRS может быть уже неверно. Таким образом, возможно, что, время от времени, узел принимает состояние, связанное с CRS, которое предписывает добавлять одно или несколько вхождений CRS в свою таблицу вхождений CRS, а также указания, которые могут предписывать удаление одного или нескольких вхождений CRS, которые могут быть уже непригодны.
Способ 2000 включает в себя этап, на котором обновляют таблицу вхождений множества коллатеральных колец надлежащим состоянием вхождения множества коллатеральных колец на основании выявленной информации таблицы вхождений множества коллатеральных колец (этап 2003). Каждое надлежащее состояние вхождения множества коллатеральных колец включает в себя коллатеральное кольцо узла и, по меньшей мере, один соответствующий узел вхождения в коллатеральном кольце узла. Например, N[1311] может включать любые вхождения CRS, принятые на фиг.19C и 19D, в таблицу вхождений CRS 1904. N[1311] также может удалять любые вхождения CRS из таблицы вхождений CRS 1904, которые указаны (например, в конфигурации, сообщениях протокола рандеву, сообщениях приложений или сообщениях, характерных для шаблона связи) как потенциально более непригодные. Соответственно, таблицу вхождений CRS узла можно обновлять для надлежащего отражения изменения структуры федерации рандеву.
На фиг.19E показан еще один вид иллюстративного дерева 1900 разбиения колец по признаку близости. На фиг.19E показана таблица вхождений CRS 1904, которая может быть наполнена на основании состояния CRS, обмен которым осуществляется согласно фиг.19C и 19D. На фиг.21 показана иллюстративная логическая блок-схема способа 2100 осуществления межблизостной связи в дереве колец. Способ 2100 будет описан применительно к узлам, кольцам, сообщениям и данным, показанным на фиг.19F.
Способ 2100 включает в себя этап определения, что узел должен отправить сообщение на коллатеральное кольцо узла (этап 2101). Например, N[1311] может принимать указание, что он должен отправить сообщение 1976 в R[“2”]. Указание, что сообщение подлежит отправке на коллатеральное кольцо, может быть принято от другого узла, может быть предусмотрено как функция логики маршрутизации, приложение на N[1311], служба группововй адресации, служба широковещания, служба произвольной адресации и т.д.
Способ 2100 включает в себя этап, на котором узел обращается к таблице вхождений множества коллатеральных колец, предназначенной для хранения вхождений множества коллатеральных колец для узла (этап 2102). Каждое вхождение множества коллатеральных колец способно указывать коллатеральное кольцо узла и, по меньшей мере, один соответствующий узел вхождения в коллатеральном кольце узла. Например, N[1311] может обращаться к таблице вхождений CRS 1904. Каждое вхождение CRS в таблице вхождений CRS 1904 может указывать коллатеральное кольцо для N[1311] и, по меньшей мере, один соответствующий узел вхождения в коллатеральном кольце для N[1311]. Например, вхождение <R[“111”], N[1111], …> указывает, что R[“111”] является коллатеральным кольцом для N[1311], и N[1111] является одним из, по меньшей мере, одного узла вхождения в R[“111”].
Способ 2100 включает в себя этап идентификации, по меньшей мере, одного вхождения множества коллатеральных колец для коллатерального кольца из таблицы вхождений множества коллатеральных колец узла (этап 2103). Каждое из, по меньшей мере, одного из вхождений множества коллатеральных колец указывает, по меньшей мере, один узел вхождения коллатерального кольца. Например, N[1311] может идентифицировать вхождение <R[“2”], N[1112], …> для R[“2”] из таблицы 1094 вхождений CRS. Вхождение <R[“2”], N[1112], …> указывает, что N[1112] (и, потенциально, другие узлы) является узлом вхождения для R[“2”].
На основании количества соответствующих узлов вхождения, включенных в идентифицированное вхождение множества коллатеральных колец (например, где существует два или более узлов вхождения), способ 2100 также может включать в себя этап разрешения из совокупности узлов вхождения для коллатерального кольца в подходящее подмножество узлов вхождения и, потенциально, в единственный подходящий узел вхождения. Например, подмножество подходящих узлов вхождения можно разрешать на основании близости между исходной и целевой близостью P, можно выбирать на основании веса узла, на основании близости к ID пункта назначения или можно выбирать произвольно.
Способ 2100 включает в себя этап отправки сообщения на, по меньшей мере, один указанный узел вхождения (этап 2104). Например, N[1311] может посылать сообщение 1976 на N[1112]. Отправка сообщения на, по меньшей мере, один узел может включать в себя отправку сообщения на все узлы вхождения в совокупности узлов, на каждый узел вхождения в разрешенном подходящем подмножестве узлов вхождения или на единственный подходящий узел вхождения. В некоторых вариантах осуществления, когда не удается доставить сообщение на один узел вхождения, можно попробовать один или несколько других узлов вхождения. Возможно, что, в результате неудачной доставки, передающий узел идентифицирует новые узлы.
На фиг.22 показана иллюстративная логическая блок-схема способа 2200 осуществления межблизостной связи в дереве колец. Способ 2200 будет описан применительно к узлам, кольцам, сообщениям и данным, показанным на фиг.19F и 19G.
Способ 2200 включает в себя этап определения, что исходный узел намерен маршрутизировать сообщение на узел назначения, ближайший к данному ID узла в целевом кольце близости в дереве колец (этап 2201). Целевое кольцо близости может быть коллатеральным кольцом исходного узла или подкольцом коллатерального кольца исходного узла. Например, N[1311] может принимать указание, что нужно маршрутизировать сообщение 1998 в R[“1221”] (целевое кольцо близости) на ID 30. Указание, что сообщение подлежит отправке на коллатеральное кольцо или подкольцо коллатерального кольца, может быть принято от другого узла, приложения, связанного с N[1311], службы групповой адресации, службы широковещания, службы произвольной адресации и т.д.
Способ 2200 включает в себя этап идентификации одного или нескольких узлов вхождения, про которые известно, что они принадлежат, по меньшей мере, одному из целевого кольца близости и кольца, предшествующего целевому кольцу близости (этап 2202). Например, N[1311] может идентифицировать N[41221], имеющий ID узла 56, как узел вхождения в R[“1221”]. Для идентификации N[41221] можно использовать различные механизмы. N[1311] может обращаться к локальной информации в попытке идентифицировать узел вхождения в целевом кольце близости. Например, N[1311] может обращаться к кэшу и конфигурации 1902 в попытке идентифицировать узел вхождения в R[“1221”].
N[1311] также может обращаться к таблице вхождений CRS для идентификации узлов вхождения в предшествующих кольцах целевого кольца близости (например, когда узел вхождения в целевом кольце близости не идентифицирован). Может быть так, что подкольцо R[“321”] обеспечивает узел N[4321] как узел вхождения в R[“21”]. Аналогично, может быть так, что R[“2221”] обеспечивает узел N[12221] как узел вхождения в R[“221”]. Когда узел вхождения в R[1221] не идентифицирован, N[1311] может попытаться идентифицировать узел вхождения в R[“221”], например N[12221]. N[1331] также может попытаться идентифицировать узел вхождения в R[“21”], например N[4321].
Возможен случай, когда узел пытается идентифицировать узлы вхождения в более близких предшествующих кольцах до попытки идентифицировать узлы вхождения в более дальних предках с точки зрения указанной целевой близости, когда узел вхождения в целевой близости не идентифицирован. Например, когда узел вхождения в R[“1221”] не идентифицирован, N[1311] может сначала попытаться идентифицировать узел вхождения в R[“221”]. Если узел вхождения в R[“221”] не идентифицирован, N[1311] может затем попытаться идентифицировать узел вхождения в R[“21”].
N[1311] также может использовать механизмы самонастройки, например затравочные узлы. Например, N[1311] может маршрутизировать запрос поиска узла вхождения в известную точку рандеву, например точку N[7651] рандеву, запрашивая известные (зарегистрированные) узлы вхождения (например, затравочные узлы). В ответ на запрос поиска, точка рандеву может возвращать (посылать) сообщение ответа поиска, включающее в себя любые известные узлы вхождения. Например, ответ 1997 поиска может возвращаться из точки N[7651] рандеву в N[1311]. Ответ 1997 поиска может включать в себя положения любых узлов вхождения, зарегистрированных с помощью точки N[7651] рандеву.
Один или несколько из этих механизмов может идентифицировать N[4221] как узел вхождения в R[“221”].
В некоторых вариантах осуществления, некоторые механизмы идентификации узлов вхождения используются прежде других механизмов идентификации узлов вхождения. Например, передающий узел может обращаться к локальной информации, прежде чем пытаться идентифицировать узлы вхождения в предшествующих кольцах целевого кольца или маршрутизировать запрос поиска узла вхождения. В тех же самых вариантах осуществления, передающий узел также может пытаться идентифицировать узлы вхождения в предшествующих кольцах целевого кольца, прежде чем маршрутизировать запрос поиска узла вхождения. Однако, в других вариантах осуществления, механизмы идентификации узлов вхождения можно использовать в другом порядке или опустить.
Способ 2200 включает в себя этап отправки сообщения на идентифицированный узел вхождения (этап 2203). Сообщение указывает, что узел вхождения призван разрешать сообщение на узел, который имеет ID узла, ближайший к указанному узлу назначения в целевом кольце близости. Например, как указано сплошной линией, N[1311] может посылать сообщение 1998 на N[41221] (узел вхождения в R[“1221”] и имеющий ID узла 56) с указанием, что сообщение должно быть разрешено в ID узла 30. N[41221] может обращаться к своей таблице маршрутизации и/или соседству для определения, что ID узла, ближайший к ID узла 30, про который известно, что это N[61221], имеющий ID узла 25. Аналогично, N [61221] может обращаться к своей таблице маршрутизации и/или соседству для определения, что ID узла, ближайший к ID узла 30, про который известно, что это N[71221], имеющий ID узла 28. N[71221] может обращаться к своей таблице и/или соседству для определения, что его ID узла, ID узла 28, является ближайшим известным ID узла к ID узла 30, и доставлять сообщение.
Вышеописанные алгоритмы маршрутизации также можно использовать для маршрутизации сообщения 1998 в R[“221”].
Когда сообщение отправляется на идентифицированный узел вхождения, который принадлежит предшествующему кольцу или целевому кольцу близости, способ 2200 можно рекурсивно применять на идентифицированном узле вхождения. Таким образом, идентифицированный узел вхождения в предшествующем кольце может, в свою очередь, пытаться идентифицировать узел вхождения в целевом кольце близости. Например, как указано пунктирными линиями, возможно, что применение способа 2200 обуславливает отправку сообщения 1998 на узел вхождения N[12221] (узел вхождения для R[“221”], который обеспечен подкольцом R[“2221”]). Затем N[12221] (с точки зрения R[“2221”]) может идентифицировать узел вхождения в R[“1221”]. Таким образом, рекурсивное применение способа 2200 на N[12221] может обуславливать отправку сообщения 1998 на N[41221].
Если идентифицированный узел вхождения в предшествующем кольце не знает об узле вхождения в целевом кольце близости, идентифицированный узел вхождения может попытаться идентифицировать узел вхождения в другом предшествующем кольце, которое ближе к целевой близости. Затем узел вхождения в предшествующем кольце может пересылать сообщение на узел вхождения более близкого предшествующего кольца целевого кольца близости.
Например, как указано штриховыми линиями, возможно, что применение способа 2200 обуславливает отправку сообщения 1998 на узел вхождения N[4321] (узел вхождения для R[“21”], который обеспечен подкольцом R[“321”]). Однако N[4321] (с точки зрения R[“321”]) может быть неспособен идентифицировать узел вхождения в R[“1221”]. Таким образом, N[4321] (с точки зрения R[“321”]) может идентифицировать узел вхождения в R[“221”]. Соответственно, первое рекурсивное применение способа 2200 на N[4321] может обуславливать отправку сообщения 1998 на N[12221]. Затем, второе рекурсивное применение способа 2200 на N[12221] может обуславливать отправку сообщения 1998 на N[41221].
Однако, если N[4321] идентифицировал узел вхождения в R[“1221”], он может послать сообщение 1998 непосредственно на узел вхождения. Таким образом, узел вхождения в предшествующем кольце может, при необходимости, пересылать сообщение на целевое кольцо близости или узел вхождения более близкого предшествующего кольца целевого кольца близости (которое обычно находится в CRS пересылающего узла вхождения). Как описано, узел вхождения в более близком предшествующем кольце затем может, при необходимости, пересылать сообщение в целевое кольцо близости или еще более близкое предшествующее кольцо целевого кольца близости (которое обычно находится в CRS пересылающего “еще более близкого” узла вхождения). Этот процесс может повторяться (например, путем рекурсивного применения способа 2200), пока не будет достигнут узел вхождения целевого кольца близости.
По достижении целевого кольца близости, вышеописанные алгоритмы маршрутизации можно использовать для маршрутизации сообщения в целевом кольце близости.
На фиг.6 и в нижеследующем описании приведено краткое общее описание подходящей вычислительной среды, в которой можно реализовать изобретение. Хотя это не требуется, изобретение будет описано в общем контексте компьютерно-выполняемых инструкций, например программных модулей, выполняемых компьютерными системами. В целом, программные модули включают в себя подпрограммы, программы, объекты, компоненты, структуры данных и т.д., которые осуществляют конкретные задачи или реализуют те или иные абстрактные типы данных. Компьютерно-выполняемые инструкции, ассоциированные с ними структуры данных и программные модули представляют примеры средства программного кода для выполнения этапов раскрытых здесь способов.
Согласно фиг.6, иллюстративная система для реализации изобретения включает в себя вычислительное устройство общего назначения в форме компьютерной системы 620, включающей в себя блок 621 обработки, системную память 622 и системную шину 623, которая соединяет различные компоненты системы, в том числе системную память 622, с блоком 621 обработки. Блок 621 обработки может выполнять компьютерно-выполняемые инструкции, предназначенные для реализации признаков компьютерной системы 620, включающих в себя признаки настоящего изобретения. Системная шина 623 может относиться к любому из типов шинных структур, включающих в себя шину памяти или контроллер памяти, периферийную шину и локальную шину, использующие разнообразные шинные архитектуры. Системная память включает в себя постоянную память (“ПЗУ”) 624 и оперативную память (“ОЗУ”) 625. Базовая система ввода/вывода (“BIOS”) 626, содержащая основные подпрограммы, которые помогают переносить информацию между элементами компьютерной системы 620, например, при запуске, может храниться в ПЗУ 624.
Компьютерная система 620 также может включать в себя накопитель 627 на магнитных жестких дисках для чтения с и записи на магнитный жесткий диск 639, накопитель 628 на магнитных дисках для чтения с или записи на съемный магнитный диск 629, и накопитель 630 на оптических дисках для чтения с или записи на съемный оптический диск 631, например CD-ROM или другой оптический носитель. накопитель 627 на магнитных жестких дисках, накопитель 628 на магнитных дисках и накопитель 630 на оптических дисках соединены с системной шиной 623 посредством интерфейса 632 накопителя на жестких дисках, интерфейса 633 накопителя на магнитных дисках и интерфейса 634 накопителя на оптических дисках, соответственно. Накопители и ассоциированные с ними компьютерно-считываемые носители обеспечивают энергонезависимое хранение компьютерно-выполняемых инструкций, структур данных, программных модулей и других данных для компьютерной системы 620. Хотя в описанной здесь иллюстративной среде используется магнитный жесткий диск 639, съемный магнитный диск 629 и съемный оптический диск 631, можно использовать другие типы компьютерно-считываемых носителей для хранения данных, включая магнитные кассеты, карты флэш-памяти, цифровые универсальные диски, картриджи Бернулли, ОЗУ, ПЗУ и пр.
Средство программного кода, содержащее один или несколько программных модулей, может храниться на жестком диске 639, магнитном диске 629, оптическом диске 631, в ПЗУ 624 или ОЗУ 625, и может включать в себя операционную систему 635, одну или несколько прикладных программ 636, другие программные модули 637 и программные данные 638. Пользователь может вводить команды и информацию в компьютерную систему 620 через клавиатуру 640, указательное устройство 642 или другие устройства ввода (не показаны), например микрофон, джойстик, игровую панель, сканер и пр. Эти и другие устройства ввода могут быть подключены к блоку 621 обработки через интерфейс 646 ввода/вывода, подключенный к системной шине 623. Интерфейс 646 ввода/вывода логически представляет любой из разнообразных интерфейсов, например интерфейс последовательного порта, интерфейс PS/2, интерфейс параллельного порта, интерфейс универсальной последовательной шины (“USB”) или интерфейс Института инженеров по электротехнике и радиоэлектронике (“IEEE”) 1394 (т.е. интерфейс FireWire), или может даже логически представлять комбинацию разных интерфейсов.
Монитор 647 или другое устройство отображения также соединен с системной шиной 623 через видеоинтерфейс 648. Громкоговорители 669 или другое устройство аудиовывода также соединены с системной шиной 623 через аудиоинтерфейс 649. Другие периферийные устройства вывода (не показаны), например принтеры, также могут быть соединены с компьютерной системой 620.
Компьютерная система 620 может соединяться с сетями, например компьютерной сетью учреждения или предприятия, домашней сетью, интрасетью и/или интернетом. Компьютерная система 620 может обмениваться данными с внешними источниками, например удаленными компьютерными системами, удаленными приложениями и/или удаленными базами данных по таким сетям.
Компьютерная система 620 включает в себя сетевой интерфейс 653, через который компьютерная система 620 принимает данные от внешних источников и/или передает данные на внешние источники. Согласно фиг.6, сетевой интерфейс 653 облегчает обмен данными с удаленной компьютерной системой 683 по линии 651 связи. Сетевой интерфейс 653 может логически представлять один или несколько программных и/или аппаратных модулей, например карту сетевого интерфейса и соответствующий стек спецификации интерфейса сетевых драйверов (“NDIS”). Линия 651 связи представляет часть сети (например, сегмент Ethernet), и удаленная компьютерная система 683 представляет узел сети.
Аналогично, компьютерная система 620 включает в себя интерфейс 646 ввода/вывода, через который компьютерная система 620 принимает данные от внешних источников и/или передает данные на внешние источники. Интерфейс 646 ввода/вывода подключен к модему 654 (например, стандартному модему, кабельному модему или модему цифровой абонентской линии (“DSL”)) по линии 659 связи, через которую компьютерная система 620 принимает данные от внешних источников и/или передает данные на них. Согласно фиг.6, интерфейс 646 ввода/вывода и модем 654 облегчают обмен данными с удаленной компьютерной системой 693 по линии 652 связи. Линия 652 связи представляет часть сети, и удаленная компьютерная система 693 представляет узел сети.
Хотя фиг.6 представляет подходящую операционную среду для настоящего изобретения, принципы настоящего изобретения можно применять в любой системе, которая способна, при необходимой модификации, реализовать принципы настоящего изобретения. Среда, представленная на фиг.6, носит исключительно иллюстративный характер и никоим образом не представляет даже малой части широкого круга сред, в которых можно реализовать принципы настоящего изобретения.
В соответствии с настоящим изобретением, узлы, прикладные уровни и другие, более низкие уровни, а также ассоциированные данные, включающие в себя таблицы маршрутизации и ID узла, можно сохранять на любых компьютерно-считываемых носителях, ассоциированных с компьютерной системой 620, и считывать с них. Например, фрагменты таких модулей и фрагменты ассоциированных программных данных могут входить в состав операционной системы 635, прикладных программ 636, программных модулей 637 и/или программных данных 638, хранящихся в системной памяти 622.
Когда запоминающее устройство большой емкости, например магнитный жесткий диск 639, подключено к компьютерной системе 620, такие модули и соответствующие программные данные также могут сохраняться в запоминающем устройстве большой емкости. В сетевой среде, программные модули, указанные применительно к компьютерной системе 620 или ее части, могут сохраняться в удаленных запоминающих устройствах, например в системной памяти и/или запоминающих устройствах большой емкости, ассоциированных с удаленной компьютерной системой 683 и/или удаленной компьютерной системой 693. Выполнение таких модулей может осуществляться в распределенной среде, как описано выше.
Настоящее изобретение можно реализовать в различных конкретных формах без отхода от его сущности и существенных характеристик. Описанные варианты осуществления следует считать во всех отношениях исключительно иллюстративными, но не ограничительными. Поэтому объем изобретения определяется прилагаемой формулой изобретения, а не вышеизложенным описанием. Все изменения, соответствующие сущности и диапазону эквивалентности формулы изобретения, подлежат включению в ее объем.
Изобретение относится к программно-аппаратным средствам для облегчения межблизостной связи в федерации рандеву. Техническим результатом является обеспечение переноса данных между узлами сети за счет симметричных отношений между узлами, маршрутизации сообщений в обоих направлениях, разделения связных списков узлов на основании совокупности метрик близости и маршрутизации сообщений на основании совокупности метрик близости. Узлы поддерживают таблицы вхождений множества коллатеральных колец, которые включают в себя коллатеральные кольца и соответствующие узлы вхождения в коллатеральные кольца. Узлы могут обмениваться состоянием вхождения множества коллатеральных колец для взаимного обновления конфигурации колец в дереве колец. Узлы могут осуществлять доступ к таблицам вхождений множества коллатеральных колец, а также к другим узлам, чтобы идентифицировать узлы вхождения в кольцах, которые являются коллатеральными кольцами узла. Сообщения можно посылать на узлы вхождения в коллатеральных кольцах. Сообщение может включать в себя указание, что узел вхождения в целевом кольце близости должен разрешать сообщение на узел в целевом кольце близости, который имеет ID узла, ближайший к указанному узлу назначения. 3 н. и 39 з.п. ф-лы, 30 ил.
1. Реализуемый в компьютерной системе способ поддержания таблицы вхождений множества коллатеральных колец для узла в дереве колец, содержащий:
этап, на котором узел осуществляет доступ к таблице вхождений множества коллатеральных колец, сконфигурированной для хранения вхождений множества коллатеральных колец для узла, причем каждое вхождение множества коллатеральных колец сконфигурировано для указания коллатерального кольца узла и по меньшей мере одного соответствующего узла вхождения в коллатеральное кольцо узла,
этап, на котором обнаруживают информацию таблицы вхождений множества коллатеральных колец в доступных ресурсах, которые поддерживают информацию, относящуюся к конфигурации дерева колец, и
этап, на котором обновляют таблицу вхождений множества коллатеральных колец надлежащим состоянием вхождения множества коллатеральных колец на основании обнаруженной информации таблицы вхождений множества коллатеральных колец, причем надлежащее состояние вхождения множества коллатеральных колец включает в себя коллатеральное кольцо узла и по меньшей мере один соответствующий узел вхождения в коллатеральном кольце узла.
2. Способ по п.1, в котором этап, на котором узел осуществляет доступ к таблице вхождений множества коллатеральных колец, содержит этап, на котором осуществляют доступ к таблице вхождений множества коллатеральных колец, которая поддерживает элементы коллатерального кольца/узла вхождения.
3. Способ по п.1, в котором этап, на котором узел осуществляет доступ к таблице вхождений множества коллатеральных колец, содержит этап, на котором создают таблицу вхождений множества коллатеральных колец для узла.
4. Способ по п.1, в котором этап обнаружения информации таблицы вхождений множества коллатеральных колец в доступных ресурсах содержит этап, на котором обнаруживают информацию таблицы вхождений множества коллатеральных колец из локальной информации, доступной узлу.
5. Способ по п.1, в котором этап обнаружения информации таблицы вхождений множества коллатеральных колец в доступных ресурсах содержит этап, на котором обнаруживают информацию таблицы вхождений множества коллатеральных колец, включенную в принятое сообщение.
6. Способ по п.5, в котором этап обнаружения информации таблицы вхождений множества коллатеральных колец, включенной в принятое сообщение, содержит этап, на котором обнаруживают информацию таблицы вхождений множества коллатеральных колец, включенную в сообщение, принятое от другого узла федерации.
7. Способ по п.6, в котором этап обнаружения информации таблицы вхождений множества коллатеральных колец, включенной в сообщение, принятое от другого узла федерации, содержит этап, на котором обнаруживают информацию таблицы вхождений множества коллатеральных колец в пинговом сообщении.
8. Способ по п.6, в котором этап обнаружения информации таблицы вхождений множества коллатеральных колец, включенной в сообщение, принятое от другого узла федерации, содержит этап, на котором обнаруживают информацию таблицы вхождений множества коллатеральных колец в сообщении обновления.
9. Способ по п.6, в котором этап обнаружения информации таблицы вхождений множества коллатеральных колец, включенной в сообщение, принятое от другого узла федерации, содержит этап, на котором обнаруживают информацию таблицы вхождений множества коллатеральных колец в ответе обновления.
10. Способ по п.5, в котором этап обнаружения информации таблицы вхождений множества коллатеральных колец, включенной в принятое сообщение, содержит этап, на котором обнаруживают информацию таблицы вхождений множества коллатеральных колец в сообщении приложения.
11. Способ по п.1, в котором этап обнаружения информации таблицы вхождений множества коллатеральных колец в доступных ресурсах содержит этап, на котором обнаруживают один или несколько элементов коллатерального кольца/узла вхождения в доступных ресурсах.
12. Способ по п.1, в котором этап обнаружения информации таблицы вхождений множества коллатеральных колец содержит этап, на котором обнаруживают информацию таблицы вхождений множества коллатеральных колец, которая указывает, что вхождение множества коллатеральных колец должно быть удалено из информации таблицы вхождений множества коллатеральных колец.
13. Способ по п.1, в котором этап обнаружения информации таблицы вхождений множества коллатеральных колец содержит этап, на котором обнаруживают информацию таблицы вхождений множества коллатеральных колец, которая указывает, что вхождение множества коллатеральных колец должно быть добавлено в информацию таблицы вхождений множества коллатеральных колец.
14. Способ по п.1, в котором этап обнаружения информации таблицы вхождений множества коллатеральных колец содержит этап, на котором обнаруживают информацию таблицы вхождений множества коллатеральных колец, которая указывает, что существующее вхождение множества коллатеральных колец в таблице вхождений множества коллатеральных колец узла должно быть изменено.
15. Способ по п.1, в котором этап обнаружения информации таблицы вхождений множества коллатеральных колец содержит этап, на котором осуществляют доступ к сообщению, которое включает в себя, по меньшей мере, часть таблицы вхождений множества коллатеральных колец другого узла.
16. Способ по п.1, в котором этап обнаружения информации таблицы вхождений множества коллатеральных колец содержит этап, на котором осуществляют доступ к информации таблицы маршрутизации для одного или нескольких колец близости, членом которых является узел.
17. Способ по п.1, в котором этап, на котором обновляют таблицу вхождений множества коллатеральных колец надлежащим состоянием вхождения множества коллатеральных колец на основании обнаруженной информации таблицы вхождений множества коллатеральных колец, содержит этап, на котором добавляют информацию таблицы вхождений множества коллатеральных колец в таблицу вхождений множества коллатеральных колец.
18. Способ по п.17, в котором этап, на котором добавляют информацию таблицы вхождений множества коллатеральных колец в таблицу вхождений множества коллатеральных колец содержит этап, на котором добавляют элемент коллатерального кольца/узла вхождения в таблицу вхождений множества коллатеральных колец.
19. Способ по п.1, в котором этап, на котором обновляют таблицу вхождений множества коллатеральных колец надлежащим состоянием вхождения множества коллатеральных колец на основании обнаруженной информации таблицы вхождений множества коллатеральных колец, содержит этап, на котором удаляют информацию таблицы вхождений множества коллатеральных колец из таблицы вхождений множества коллатеральных колец.
20. Способ по п.19, в котором этап, на котором удаляют информацию таблицы вхождений множества коллатеральных колец из таблицы вхождений множества коллатеральных колец, содержит этап, на котором удаляют элемент коллатерального кольца/узла вхождения из таблицы вхождений множества коллатеральных колец.
21. Способ по п.1, дополнительно содержащий этап, на котором узел посылает информацию множества коллатеральных колец одному или более другим узлам, чтобы содействовать одному или нескольким другим узлам в поддержании их соответствующих таблиц вхождений множества коллатеральных колец.
22. Способ по п.21, в котором этап, на котором узел посылает состояние вхождения множества коллатеральных колец, содержит этап, на котором узел отправляет всю свою таблицу вхождений множества коллатеральных колец.
23. Система для поддержания таблицы вхождений коллатеральных колец для узла в совокупности иерархически разбитых классов узлов, содержащая:
более высокое кольцо узлов, разбитое на кольца узлов более низкого уровня, включающие в себя, по меньшей мере, первое более низкое кольцо узлов и второе более низкое кольцо узлов, причем каждый узел в более высоком кольце узлов имеет идентификатор узла, указывающий позицию в сортированном связном списке узлов, причем первое более низкое кольцо узлов и второе более низкое кольцо узлов являются коллатеральными кольцами друг для друга,
причем каждый узел в первом более низком кольце узлов имеет идентификатор узла в первом подсписке узлов, причем первый подсписок узлов выделяется из сортированного связного списка в соответствии с критерием близости, указывающим, как нужно классифицировать кольца узлов, причем каждый узел в первом более низком кольце узлов поддерживает таблицу вхождений коллатерального кольца, которая включает в себя узлы вхождения в известные коллатеральные кольца первого более низкого кольца узлов, включая второе более низкое кольцо узлов, и
причем каждый узел во втором более низком кольце узлов имеет идентификатор узла во втором подсписке узлов, причем второй подсписок узлов выделяется из сортированного связного списка в соответствии с критерием близости, указывающим, как нужно классифицировать кольца узлов, причем каждый узел во втором более низком кольце узлов поддерживает таблицу вхождений коллатеральных колец, которая включает в себя узлы вхождения в известные коллатеральные кольца второго более низкого кольца узлов, включая первое кольцо узлов.
24. Система по п.23, в которой дополнительно
каждый узел в первом более низком кольце узлов поддерживает таблицу маршрутизации с, по меньшей мере, частичной информацией о других узлах, присутствующих в первом более низком кольце узлов, и
каждый узел в более высоком кольце узлов поддерживает таблицу маршрутизации с, по меньшей мере, частичной информацией о других узлах, присутствующих в более высоком кольце узлов.
25. Система по п.24, в которой по меньшей мере один узел является членом как первого более низкого кольца, так и членом более высокого кольца.
26. Система по п.24, в которой состояние таблицы маршрутизации, поддерживаемое каждым узлом коллективно в более высоком кольце, задает множество коллатеральных колец для каждого узла в более высоком кольце так, что полное множество коллатеральных колец относится к более высокому кольцу.
27. Система по п.23, в которой каждый узел в кольцах узлов более низкого уровня конфигурируется для передачи сообщения из одной близости в другую целевую близость.
28. Система по п.27, в которой конфигурирование каждого узла в более высоком кольце узлов для передачи сообщения из одной близости в другую целевую близость содержит конфигурирование каждого узла в более высоком кольце узлов для идентификации Id узла назначения в другой целевой близости так, что сообщение может быть маршрутизировано и доставлено на узел в целевой близости, который является ближайшим к идентифицированному Id узла назначения.
29. Система по п.23, в которой каждый узел в более высоком кольце узлов конфигурируется для обнаружения наличия и отсутствия других узлов в системе.
30. Система по п.29, в которой конфигурирование каждого узла в более высоком кольце узлов для обнаружения наличия и отсутствия других узлов в системе содержит конфигурирование каждого узла в более высоком кольце узлов для поддержания состояния множества коллатеральных колец для отражения обнаруженных изменений в наличии и отсутствии других узлов.
31. Система по п.29, в которой конфигурирование каждого узла в более высоком кольце узлов для обнаружения наличия и отсутствия других узлов в системе содержит конфигурирование каждого узла в более высоком кольце узлов для обнаружения наличия и отсутствия других узлов, по меньшей мере, частично из информации, включенной в сообщения, передаваемые в системе.
32. Система по п.29, в которой конфигурирование каждого узла в более высоком кольце узлов для обнаружения наличия и отсутствия других узлов в системе содержит конфигурирование каждого узла в более высоком кольце узлов для обнаружения наличия и отсутствия других узлов, по меньшей мере, частично из указаний, принятых от любых компонентов приложения, ассоциированных с системой.
33. Система по п.23, дополнительно содержащая один или несколько затравочных узлов, которые, по меньшей мере, обеспечивают средства самонастройки для системы.
34. Система по п.33, в которой затравочные узлы сконфигурированы обнаруживать разделы инфраструктуры и компенсировать обнаруженные разделы инфраструктуры.
35. Система по п.23, дополнительно содержащая средства директорий регистрации узла вхождения.
36. Система по п.35, в которой средства директорий регистрации узла вхождения содержат средства директорий регистрации узла вхождения, поддерживаемые точками рандеву, включенными в систему.
37. Система по п.36, в которой средства директорий регистрации узла вхождения, поддерживаемые точками рандеву, включенными в систему, содержат точки рандеву на каждом уровне в более низких кольцах узлов.
38. Система по п.36, в которой средства директорий регистрации узла вхождения, поддерживаемые точками рандеву, включенными в систему, содержат точки рандеву в более высоких кольцах узлов.
39. Система по п.35, в которой поддерживаемые средства директорий регистрации узла вхождения содержат затравочные узлы, регистрирующиеся как узлы вхождения.
40. Машиночитаемый носитель данных, на котором сохранены машиноисполняемые инструкции, которые при их исполнении процессором в компьютерной системе предписывают процессору выполнять способ поддержания таблицы вхождений множества коллатеральных колец для узла в дереве колец, содержащий этапы, на которых:
осуществляют доступ к таблице вхождений множества коллатеральных колец, сконфигурированной для хранения вхождений множества коллатеральных колец для узла, причем каждое вхождение множества коллатеральных колец сконфигурировано для указания коллатерального кольца узла и по меньшей мере одного соответствующего узла вхождения в коллатеральное кольцо узла,
обнаруживают информацию таблицы вхождений множества коллатеральных колец в доступных ресурсах, которые поддерживают информацию, относящуюся к конфигурации дерева колец, и
обновляют таблицу вхождений множества коллатеральных колец надлежащим состоянием вхождения множества коллатеральных колец на основании обнаруженной информации таблицы вхождений множества коллатеральных колец, причем надлежащее состояние вхождения множества коллатеральных колец включает в себя коллатеральное кольцо узла и по меньшей мере один соответствующий узел вхождения в коллатеральном кольце узла.
41. Машиночитаемый носитель данных по п.40, содержащий системную память.
42. Машиночитаемый носитель данных по п.40, содержащий магнитный диск.
| Переносная печь для варки пищи и отопления в окопах, походных помещениях и т.п. | 1921 |
|
SU3A1 |
| US 20040030668 A1, 12.02.2004 | |||
| US 005564037 А, 08.10.1996 | |||
| СИСТЕМА И СПОСОБ ПРЕДОСТАВЛЕНИЯ ДОСТУПА К ЗАЩИЩЕННЫМ УСЛУГАМ С ОДНОКРАТНЫМ ВВОДОМ ПАРОЛЯ | 2003 |
|
RU2308755C2 |
| ОБРАБОТКА ДАННЫХ В БЕСПРОВОДНОЙ СЕТИ | 2002 |
|
RU2297101C2 |
| US 20050068913 А1, 31.03.2005. | |||
