ОСНОВАННАЯ НА ПРИГОДНОСТИ МАРШРУТИЗАЦИЯ

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