Основанная на пригодности маршрутизация

Основанная на пригодности маршрутизация

Иллюстрации

Показать все

Реферат

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

Уровень техники и относящаяся к изобретению область техники

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

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

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

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

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

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

Сущность изобретения

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

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

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

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

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

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

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

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

Краткое описание чертежей

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

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

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

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

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

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

Подробное описание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг.1А иллюстрирует вид сетевой архитектуры 100, которая способствует основанной на пригодности маршрутизации. Как показано на фиг.1А, сетевая архитектура 100 включает в себя кольцо 151. Кольцо 151 представляет собой двунаправленный список с двойной связью 2⁹, или 512, расположений, которые могут быть заняты узлом, обеспечивающим кольцевую топологию с двойной связью (т.е. наложенную сеть). Кольцо 151 включает в себя множество узлов, включая узел 101 и другие узлы, перечисленные по номеру идентификатора (ID) в таблице 102 маршрутизатора. В основном, кольцо 151 представляет возможность логического соединения между узлами, которые могут быть физически соединены по различным и разным лежащим в основе сетям и соединениям. Например, каждый из узлов может быть физически соединен с одним другим по системной шине и/или по (или является частью) одной или нескольким лежащим в основе сетям, таких как, например, локальная сеть (LAN), глобальная сеть (WAN) или даже Интернет.

Узлы на кольце 151 могут использовать различные протоколы наложения для связи друг с другом. Протоколы наложения могут составлять и/или быть основаны на протоколах, лежащих в основе физических сетей. Таким образом, каждый из описанных узлов, а также любые другие подсоединенные узлы, может создавать относящиеся к сообщениям данные и обмениваться относящимися к сообщению данными (например, дейтаграммы протокола Интернета (IP) и другие протоколы более высоких уровней, которые используют IP-дейтаграммы, такие как протокол управлений передачей («TCP»), протокол передачи гипертекста («HTTP»), простой протокол электронной почты («SMTP») и т.п.) по лежащим в основе сетям.

Узел 101 поддерживает таблицу 102 маршрутизации, которая хранит множество узлов (ниже в данном документе упоминаемых как «узлы маршрутизации»). Узел 101 может выполнять связь непосредственно с каждым узлом маршрутизации в таблице 102 маршрутизации. Узел 101 может посылать сообщение на узел маршрутизации для доставки сообщения узлу, который находится ближе к узлу маршрутизации, чем узел 101. Например, чтобы доставить сообщение узлу, имеющему ID=403, узел 101 может послать сообщение узлу маршрутизации, имеющему ID=401.

Узел 101 может поддерживать таблицу 102 маршрутизации в соответствии с политикой 161 таблицы маршрутизации. Политика 161 таблицы маршрутизации может определять максимальное количество узлов маршрутизации, которые должны быть включены в таблицу 102 маршрутизации. Политика 161 таблицы маршрутизации также может указывать то, как поделить узлы в таблице 102 маршрутизации на количество диапазонов и определить максимальное количество узлов маршрутизации на диапазон. Например, политика 161 таблицы маршрутизации может предписывать, что таблица 102 маршрутизации может быть разделена на диапазоны 191, 192, 193, 194, 195, 196, 197 и 198.

Диапазон, в котором ID включены в диапазон, может изменяться, так что диапазоны, которые находятся ближе к узлу 101, заполнены более плотно узлами маршрутизации, и диапазоны, которые находятся дальше от узла 101, заполнены менее плотно узлами маршрутизации. Например, диапазон 192 включает в себя четыре узла маршрутизации в диапазоне от +32 ID до +64 ID от узла 101. Диапазон 194 включает в себя четыре узла маршрутизации в диапазоне от +128 до +246. Таким образом, оба диапазона 192 и 194 включают в себя четыре узла маршрутизации. Однако диапазон 192 более плотно заполнен, так как четыре узла маршрутизации в диапазоне 192 распределены по меньшему расстоянию на кольце 151. С другой стороны, диапазон 194 менее плотно заполнен, так как четыре узла маршрутизации в диапазоне 192 распределены по большему расстоянию на кольце 151.

Политика 161 таблицы маршрутизации также может определять диапазон для узлов близлежащей окрестности. Например, узлы в пределах от +16 до -16 ID узлов от узла 101 автоматически могут включаться в таблицу 102 маршрутизации в качестве узлов окрестности. Узлы окрестности могут быть разбиты на окрестности предшествующих узлов и последующих узлов. Например, таблица 102 маршрутизации включает в себя окрестность 181 последующих узлов и окрестность 182 предшествующих узлов, причем каждая имеет три узла относительно близко к (в пределах 16 ID узла) узлу 101.

Фиг.1В иллюстрирует вид узла 101, поддерживающего таблицу 102 маршрутизации. Как показано на фиг.1В, узел 101 включает в себя модуль 103 вычисления пригодности и модуль 104 управления таблицей маршрутизации. Модуль 103 вычисления пригодности выполнен с возможностью вычисления значений пригодности для узлов маршрутизации. Модуль 103 вычисления пригодности может реализовывать алгоритм вычисления пригодности для вычисления значений пригодности для узлов маршрутизации. В основном, значение пригодности указывает способность узла маршрутизации обрабатывать и маршрутизировать сообщения.

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

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

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

Некоторые из узлов могут сохраняться в таблице 102 маршрутизации вместе с их соответствующими значениями пригодности. Например, в диапазоне 193: ID 76 узла имеет пригодность=100, ID 90 узла имеет пригодность=1000, ID 99 узла имеет пригодность=50, и ID 112 узла имеет пригодность=5000. Модуль 104 управления таблицей маршрутизации может разрешить заполнение таблицы 102 маршрутизации и ее различных диапазонов узлами маршрутизации до заданных максимальных значений. После достижения заданных максимальных значений модуль 104 управления таблицей маршрутизации может взаимодействовать с модулем 103 вычисления пригодности для поддержания размера таблицы 102 маршрутизации и ее различных диапазонов на заданных максимальных значениях.

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

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

Способ 200 включает в себя этап осуществления доступа к таблице маршрутизации, которая включает в себя один или несколько узлов, причем каждый узел в таблице маршрутизации представляет собой узел, на который компьютерная система может послать сообщение для доставки сообщения на узел назначения в наложенной сети, при этом каждый узел в таблице маршрутизации имеет значение метрики пригодности, представляющее способность узла пересылать и обрабатывать сообщения в наложенной сети (этап 202). Например, модуль 104 управления таблицей маршрутизации может осуществлять доступ к таблице 102 маршрутизации. Каждый узел в таблице 102 маршрутизации представляет собой узел маршрутизации, которому узел 101 может послать сообщение для доставки сообщения на узел назначения (на кольце 151). Каждый узел маршрутизации в таблице 102 маршрутизации также имеет значение пригодности. Например, в диапазоне 193: ID 76 узла имеет пригодность=100, ID 90 узла имеет пригодность=1000, ID 99 узла имеет пригодность=50, и ID 112 узла имеет пригодность=5000.

Перед осуществлением доступа к таблице 102 маршрутизации модуль 104 управления таблицей маршрутизации может заблокировать таблицу 102 маршрутизации. Блокирование таблицы 102 маршрутизации предотвращает другой доступ к таблице 102 маршрутизации (например, определения маршрутизации). Таким образом, блокирование уменьшает возможность ошибок маршрутизации вследствие осуществления доступа к таблице 102 маршрутизации, когда таблица 102 маршрутизации изменяется.

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

Способ 200 включает в себя этап вставления другого узла в таблицу маршрутизации (этап 204). Например, модуль 104 управления таблицей маршрутизации может вставить ID 97 узла в таблицу 102 маршрутизации. Способ 200 включает в себя этап деления таблицы маршрутизации на множество диапазонов, причем каждый диапазон соответствует части наложенной сети (этап 205). Например, модуль 104 управления таблицей маршрутизации может разделить таблицу 102 маршрутизации на диапазоны 191-198.

Способ 200 включает в себя этап назначения каждого узла в таблице маршрутизации заданному диапазону, основываясь на расположении узла в наложенной сети (этап 206). Например, модуль управления таблицей маршрутизации может назначать каждый узел маршрутизации таблицы 102 маршрутизации заданному диапазону, выбранному из числа диапазонов 191-198, основываясь на расположении узла маршрутизации в кольце 151. Таблица 102 маршрутизации может быть разделена и узлы маршрутизации назначены диапазонам так, как показано на фиг.1. Кроме того, узел 121 может быть назначен диапазону 193, как показано на фиг.1В.

Способ 200 включает в себя этап идентификации диапазона, который включает в себя наибольшее количество узлов (этап 207). Например, модуль 104 управления таблицей маршрутизации может идентифицировать, что диапазон 193 включает в себя наибольшее количество узлов. Диапазон 193 включает в себя пять узлов, тогда как диапазоны 192 и 194-197 включают в себя четыре узла (узлы окрестности могут быть исключены из идентификации).

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

Способ 200 включает в себя этап удаления идентифицированного узла из таблицы маршрутизации (этап 209). Например, модуль 104 управления таблицей маршрутизации может удалить ID 99 узла из таблицы 102 маршрутизации. Впоследствии, после удаления ID 99 узла модуль 104 управления таблицей маршрутизации может разблокировать таблицу 102 маршрутизации. Разблокирование таблицы 102 маршрутизации позволяет другой доступ к таблице 102 маршрутизации. Таким образом, узел 101 может использовать таблицу 102 маршрутизации для идентификации узлов маршрутизации после того, как будет завершено любое изменение.

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

Способ 300 включает в себя этап приема сообщения от другого узла в наложенной системе, причем сообщение включает в себя информацию об узле для множества дополнительных узлов в наложенной сети, при этом информация об узле включает в себя информацию о пригодности для каждого из множества дополнительных узлов (этап 301). Например, узел 101 может принимать сообщение 111 от другого узла на кольце 151. Сообщение 111 включает в себя информацию об узле для множества других узлов на кольце 151, включающую информацию о пригодности для каждого из множества узлов. Например, сообщение 111 включает в себя размер таблицы маршрутизации и другие характеристики (например, количество посланных сообщений, количество принятых сообщений и т.д.) для ID 46, 144, 242 и 460 узла. Содержимое сообщения 111 может представлять таблицу маршрутизации другого узла или ее часть.

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

Перед осуществлением доступа к таблице 102 маршрутизации модуль 104 управления таблицей маршрутизации может блокировать таб