ОСНОВАННАЯ НА ПРИГОДНОСТИ МАРШРУТИЗАЦИЯ Российский патент 2012 года по МПК H04L12/28 

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

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

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

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

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

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

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

Существуют также другие проблемы, связанные с наложенными сетями. Например, используя наложенную сеть, часто полезно выполнять связь между двумя произвольными узлами наложения. Чтобы это сделать, узлу источника необходим адрес конечной точки (адрес протокола Интернета (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 управления таблицей маршрутизации может блокировать таблицу 102 маршрутизации. Блокирование таблицы 102 маршрутизации предотвращает другой доступ к таблице 102 маршрутизации (например, определения маршрутизации). Таким образом, блокирование уменьшает возможность ошибок маршрутизации из-за осуществления доступа к таблице 102 маршрутизации, когда изменяется таблица 102 маршрутизации.

Для каждого из множества дополнительных узлов способ 300 включает в себя этап вычисления значения метрики пригодности для дополнительного узла, причем значение метрики пригодности представляет способность дополнительного узла пересылать и обрабатывать сообщения в наложенной сети, при этом значение метрики пригодности основывается, по меньшей мере частично, на информации о пригодности для дополнительного узла (этап 303). Например, модуль 103 вычисления пригодности может вычислять значения 40, 200, 2000 и 500 метрики пригодности для ID 46, 144, 242 и 460 узла соответственно. Значения метрики пригодности могут вычисляться на основе размеров таблицы маршрутизации и/или других характеристик, указанных в сообщении 111.

Для каждого из множества дополнительных узлов способ 300 включает в себя этап вставления дополнительного узла в таблицу маршрутизации компьютерной системы (этап 304). Например, модуль 104 управления таблицей маршрутизации может вставлять ID 46, 144, 242 и 460 узла в таблицу 102 маршрутизации.

Способ 300 включает в себя этап определения, что количество узлов в таблице маршрутизации компьютерной системы превышает заданное количество (этап 305). Например, модуль 104 управления таблицей маршрутизации может ссылаться на политику 161 таблицы маршрутизации для осуществления доступа к максимальному числу узлов маршрутизации для таблиц 102 маршрутизации. Модуль 104 управления таблицей маршрутизации может определить, что вставление ID 46, 144, 242 и 460 узла вызвало то, что количество узлов в таблице 102 маршрутизации превысило максимальное число узлов маршрутизации.

Способ 300 включает в себя этап деления таблицы маршрутизации на множество диапазонов, причем каждый диапазон соответствует части наложенной сети (этап 306). Например, модуль 104 управления узлами маршрутизации может делить таблицу 102 маршрутизации на диапазоны 191-198. Способ 300 включает в себя этап назначения каждого узла в таблице маршрутизации одному из множества диапазонов, основываясь на расположении узла в наложенной сети (этап 307). Например, каждый узел в таблице 102 маршрутизации может быть назначен одному из диапазонов 191-198, основываясь на его расположении на кольце 151. ID 46 узла может быть назначен диапазону 193, ID 144 и 242 узла могут быть назначены диапазону 195, и ID 460 узла может быть назначен диапазону 197.

Способ 300 включает в себя этап идентификации диапазона с наибольшим количеством узлов (этап 308). Например, модуль управления таблицей маршрутизации может идентифицировать диапазон 194 как включающий в себя наибольшее количество (шесть) узлов маршрутизации. Способ 300 включает в себя удаление узла, который является наименее пригодным для пересылки и обработки сообщений, из числа узлов в идентифицированном диапазоне, из таблицы маршрутизации, основываясь на значениях метрики пригодности (этап 309). Например, модуль 102 управления таблицей маршрутизации может удалить ID 135 узла из таблицы 102 маршрутизации. Модуль 104 управления таблицей маршрутизации может идентифицировать ID 135 узла как имеющий наименьшее значение метрики пригодности в диапазоне 193. Следовательно, модуль 104 управления таблицей маршрутизации определяет, что ID 135 узла представляет собой узел маршрутизации, наименее способный пересылать и обрабатывать сообщения в кольце 151. (Однако, как ранее описано, в зависимости от конфигурации, более высокое значение метрики пригодности, или некоторый другой механизм для определения способностей обрабатывать и пересылать сообщения из значений метрики пригодности, может использоваться для указания меньшей способности пересылать и обрабатывать сообщения).

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

Например, после удаления ID 135 узла модуль 104 управления таблицей маршрутизации может определить, что диапазон 192 включает в себя пять узлов. Модуль 104 управления таблицей маршрутизации может идентифицировать ID 37 узла как узел маршрутизации, наименее способный пересылать и обрабатывать сообщения в кольце 151, основываясь на значениях метрики пригодности. Следовательно, модуль 104 управления таблицей маршрутизации удаляет ID 37 узла из таблицы 102 маршрутизации. Последующие подобные проверки могут выполняться, приводя к удалению ID 144 узла (в диапазоне 193) и ID 463 узла (в диапазоне 197). Таким образом, таблица 102 маршрутизации в итоге возвращается к размеру перед тем, как было принято сообщение 111. Фиг.1D изображает результирующее содержимое таблицы 102 маршрутизации после обработки сообщения 111.

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

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

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

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

1. Способ поддержания таблицы маршрутизации в компьютерной системе, причем компьютерная система включена в виде узла (101) в наложенную сеть (100), при этом наложенная сеть (100) также включает в себя множество других узлов (121), при этом способ содержит этапы, на которых:
принимают информацию (107) об узле для другого узла (121), который находится в заданном расположении в наложенной сети (100), причем информация (107) об узле включает в себя информацию о пригодности для другого узла (121);
осуществляют доступ к таблице (102) маршрутизации, которая включает в себя один или несколько узлов, причем каждый узел в таблице (102) маршрутизации представляет собой узел, которому компьютерная система может послать сообщение для доставки сообщения на узел назначения в наложенной сети (100), причем каждый узел в таблице (102) маршрутизации имеет значение метрики пригодности, представляющее способность узла пересылать и обрабатывать сообщения в наложенной сети (100);
вычисляют значение (107) метрики пригодности для другого узла, причем значение (107) метрики пригодности представляет способность другого узла пересылать и обрабатывать сообщения в наложенной сети (100), причем значение (107) метрики пригодности основано, по меньшей мере частично, на информации (107) о пригодности для другого узла;
вставляют другой узел (121) в таблицу (102) маршрутизации; делят таблицу маршрутизации на множество диапазонов (191, 192, 193), причем каждый диапазон соответствует части наложенной сети (100);
назначают каждый узел в таблице маршрутизации заданному диапазону, основываясь на расположении узла в наложенной сети;
идентифицируют диапазон (194), который включает в себя наибольшее количество узлов;
идентифицируют узел в идентифицированном диапазоне, который является наименее способным пересылать и обрабатывать сообщения в наложенной сети, основываясь на значениях метрики пригодности узлов в идентифицированном диапазоне; и удаляют идентифицированный узел из таблицы (102) маршрутизации.

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

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

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

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

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

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

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

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

10. Способ поддержания таблицы (102) маршрутизации в компьютерной системе, причем компьютерная система включена в виде узла (101) в наложенную сеть, при этом наложенная сеть также включает в себя множество других узлов, при этом способ содержит этапы, на которых:
принимают сообщение (111) от другого узла в наложенной сети, причем сообщение (111) включает в себя информацию об узле для множества дополнительных узлов в наложенной сети (100), при этом информация об узле включает в себя информацию о пригодности для каждого из множества дополнительных узлов;
осуществляют доступ к таблице маршрутизации компьютерной системы, причем таблица (102) маршрутизации компьютерной системы включает в себя множество узлов, с которыми компьютерная система может осуществлять связь для маршрутизации сообщений на узлы назначения в наложенной сети (100), причем каждый из множества узлов в таблице (102) маршрутизации компьютерной системы имеет значение метрики пригодности, представляющее способность пересылать и обрабатывать сообщения в наложенной сети;
для каждого из множества дополнительных узлов:
вычисляют значение метрики пригодности для дополнительного узла, причем значение метрики пригодности представляет способность дополнительного узла пересылать и обрабатывать сообщения в наложенной сети (100), значение метрики пригодности основано, по меньшей мере частично, на информации о пригодности для дополнительного узла; и
вставляют дополнительный узел в таблицу (102) маршрутизации компьютерной системы;
определяют, что количество узлов в таблице маршрутизации компьютерной системы превышает заданное количество (161);
делят таблицу маршрутизации на множество диапазонов (191, 192, 193), причем каждый диапазон соответствует части наложенной сети (100);
назначают каждый узел в таблице маршрутизации одному из множества диапазонов, основываясь на расположении узла в наложенной сети (100);
идентифицируют диапазон, который включает в себя наибольшее количество узлов (194); и
удаляют узел, который является наименее пригодным для пересылки и обработки сообщений, из числа узлов в идентифицированном диапазоне, из таблицы (102) маршрутизации, основываясь на значениях метрики пригодности.

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

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

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

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

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

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

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

18. Способ по п.10, в котором наложенная сеть представляет собой кольцевую топологию.

19. Способ по п.10, в котором наложенная сеть представляет собой одноранговую сеть, наложенную на Интернет.

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