СПОСОБ ОПРЕДЕЛЕНИЯ ТОПОЛОГИИ КОМПЬЮТЕРНОЙ СЕТИ Российский патент 2003 года по МПК H04L12/24 H04L12/56 

Таблицыг

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

1. Способ определения топологии сети данных, состоящей из сетевых устройств, включающих устройства передачи данных, содержащий (a) получение адреса источника для данных отображения порта из устройств передачи данных, (b) составление для каждого порта каждого устройства передачи данных множества адресов источников, принимаемых каждым портом в течение определенного периода времени, (c) определение в качестве подключенных портов тех из указанных портов, которые передали через сетевые устройства данные отображения, причем эти устройства имеют другие порты, кроме рассматриваемого порта, и определение остальных портов, не являющихся подключенными портами, в качестве отключенных портов, (d) определение соединений с отключенными портами от устройств, видимых из отключенного порта, (е) определение соединений между подключенными портами и между подключенными и отключенными портами на основании множеств адресов источников.2. Способ по п.1, отличающийся тем, что множество адресов источников получают путем образования множества из набора подмножеств, каждое из которых представляет части указанного периода времени.3. Способ по п.1, отличающийся тем, что этап (d) включает определение соединения между устройством и отключенным портом в случае, когда устройство является видимым из отключенного порта.4. Способ по п.3, отличающийся тем, что этап (е) включает сравнение множеств объектов с подключенными портами и объектов, соединенных с отключенным портом, видимых подключенным портом, и определения соединения пар подключенных портов, для которых пересечения этих множеств являются минимальными.5. Способ по п.4, отличающийся тем, что дополнительно включает ограничения сравнения подключенного порта устройства с подключенными портами каждого другого устройства так, что множество объектов, видимых прямо и опосредованно через этот подключенный порт имеет ненулевое пересечение с множествами объектов, видимыми на множестве портов других устройств или так, что множество объектов, видимых через упомянутый порт первого устройства включает множество объектов, видимых на множестве портов других устройств, причем это ограничение применяют к обоим подключенным портам в каждом таком сравнении.6. Способ по п.5, отличающийся тем, что включает определение наличия объекта, не сообщающего таблицу адресов, соединенного с одним из подключенных портов, через который проходит соединение с другими портами, в случае наличия ненулевых или множества нулевых пересечений указанного подключенного порта.7. Способ по п.1, отличающийся тем, что адрес источника для данных отображения порта представляет собой данные таблицы мостов, данные таблицы протокола разрешения адресов, данные тестирования соединений, данные записи адреса источника и другие табличные данные.8. Способ по п.1, отличающийся тем, что этап составления (в) выполняют путем запуска программы обнаружения для определения списка устройств в сети, последующего запуска программы упорядоченного опроса для получения адреса источника для информации отображения порта от устройств передачи данных, и записи для каждого порта множества адресов источников, принимаемых указанным портом в течение определенного периода времени.9. Способ по п.6, отличающийся тем, что этап составления (в) выполняют путем запуска программы обнаружения для определения списка устройств в сети, последующего запуска программы упорядоченного опроса для получения адреса источника для информации отображения порта от устройств передачи данных, и записи для каждого порта множества адресов источника, принимаемых указанным портом в течение определенного периода времени.10. Способ по п.9, отличающийся тем, что адрес источника для данных отображения порта представляет собой одни из данных таблицы мостов, данных таблицы протокола разрешения адресов, данных тестирования соединения, данных записи адреса источника и другие табличные данные.11. Способ определения топологии сети передачи данных, состоящей из устройств передачи данных и узловых устройств, причем каждое устройство передачи данных имеет один или большее количество портов, содержащий (a) составление таблицы адреса источника для каждого порта каждого устройства передачи данных, (b) классификацию в качестве подключенных тех портов, которые соединяются прямо или опосредованно с другими устройствами передачи данных, которые сообщают таблицы адреса источника, (c) классификацию портов, которые соединяются прямо или опосредованно с другими устройствами передачи данных, которые не сообщают таблицы адреса источника, в качестве отключенных портов, (d) замену каждого адреса источника в каждой таблице подключенного порта на адрес источника устройства передачи данных, содержащего отключенный порт, таблица которого содержит этот адрес источника, благодаря чему таблицы подключенного порта, таким образом, содержат только адреса устройств, передающих данные и адреса устройств, не сообщающих таблицы, опосредованно соединенных с подключенными портами, (e) сравнение таблиц пары портов путем пересечения, (f) определение наиболее вероятного соединения для каждого подключенного порта путем определения минимального пересечения.12. Способ по п.11, отличающийся тем, что этапы (a)-(f) непрерывно повторяют и суммируют вероятности соединения между портами до тех пор, пока не будет получена заранее определенная достоверность указанного соединения.13. Способ по п.12, отличающийся тем, что этап составления (в) выполняют путем запуска программы обнаружения для определения списка устройств в сети, последующего запуска программы упорядоченного опроса для получения адреса источника для информации отображения порта от устройств передачи данных, и записи для каждого порта множества адресов источников, принимаемых указанным портом в течение определенного периода времени.14. Способ по п.11, отличающийся тем, что этап (f) включает определение наличия ненулевых пересечений или множества нулевых пересечений для конкретного порта и, таким образом, определение наличия объекта, не сообщающего таблицы, соединенного с конкретным портом и, таким образом, что соединения из конкретного порта с другими портами проходят через объект, не сообщающий таблицы.15. Способ по п.1, отличающийся тем, что этап (с) содержит, по меньшей мере, одно из следующих действий: (i) определение A_i в качестве подключенного порта, если NS(A_i, B_j)>0 и NS(A_i, B_k)>0 и А<>В и k<>j, где NS(A_i, B_j) представляет собой количество элементов множества, сформированных пересечением S(A_i) и S(B_j) где S(A_i) представляет собой множество адресов источников, записанных из порта i в устройстве А, (ii) определение A_i в качестве подключенного порта, если пересечение S(A_i) и Т не равно нулю, где Т представляет собой множество всех сетевых устройств, которые имеют таблицы адреса источника, (iii) определение A_i в качестве подключенного порта, если B_j представляет собой отключенный порт и В_j<>А_i, причем NS(A_i, B_j)>=1.16. Способ по п.15, отличающийся тем, что этапы (а), (b) и (с) выполняют с использованием какого-либо или обоих этапов (i) и (ii) и повторно выполняют этапы (а), (b) и (с) время от времени с использованием этапа (iii).17. Способ по п.15, отличающийся тем, что порт определяют в качестве отключенного порта в случае, если он не был определен как подключенный порт в течение нескольких повторений этапов (а), (b) и (с).18. Способ по п.15, отличающийся тем, что дополнительно включает этап сравнения множеств объектов, соединенных с отключенным портом, видимых подключенным портом, и определения соединения пары подключенных портов, для которой эти множества являются минимальными.19. Способ по п.18, отличающийся тем, что включает сортировку всех портов во множестве всех устройств в сети, видимых отключенными портами, по размеру множеств, и сравнение наименьших множеств портов перед сравнением больших множеств.20. Способ по п.17, отличающийся тем, что дополнительно включает выполнение требования того, что NS(A_iY<>A_i)>=k, k>1, Y представляет собой множество всех устройств в сети, видимых отключенными портами.21. Способ по п.4, отличающийся тем, что этап сравнения включает этапы: (i) определения множества V для каждого подключенного порта, (ii) определения NV(A_i, B_j) для пар портов, которые могут сравниваться, (iii) определения минимума NV(A_i, B_j) для всех портов, при этом множество V(A_i) описывает все устройства с подключенными портами, которые подключенный порт A_i определенно видит, включая устройство А, множество V(A_i) содержит все устройства В, для которых, по меньшей мере, одно из следующих условий является справедливым:

(I) В=А,

(II) NS(A_i, B_j)>0 и NS(A_i, B_k<>j)>0,

(III) S(A_i) включает В,

(IV) S(B_j) включает А,

сравнение пары портов выполняют только, если V(A_i) включает В и V(B_j) включает А.