Как построить топологию сетей (данные в FDB таблице) когда связи замкнуты в кольцо?

Question

[redabyq]

Есть условная гипотетическая подсеть
Вот её исходная топология:
УСТР200 подключен к кольцу из УСТР201-202-203 через свой порт 8.
Кольцо состоит из:
УСТР201 (порт 4) ↔ УСТР202 (порт 7)
УСТР202 (порт 6) ↔ УСТР203 (порт 2)
УСТР203 (порт 1) ↔ УСТР201 (порт 5)
В чем прикол - вот данные которые мы найдем в FDB таблице по этим связям

По УСТР200:
Порт 8: все остальные устройства (201, 202, 203).
По УСТР201:
Порт 3: УСТР200.
По портам 4 и 5: видим все устройства в кольце (201, 202, 203).
По УСТР202:
По портам 7 и 6: видим все устройства в кольце (201, 202, 203).
По УСТР203:
По портам 1 и 2: видим все устройства в кольце (201, 202, 203).

Каким образом можно получить реальные связи с реальными портами из таких данных?
Разрывать связи возможности естественно нет. Перебор подключений по всем возможным портам тоже не вариант поскольку в реальных условиях устройств может быть значительно больше

Comments

[CityCat4]

Это задание, а не вопрос.

[Jammeren2]

CityCat4, Это не задание, а реальная проблема построения топологии по FDB в кольцевых сетях, где стандартные методы не работают — если есть решение, подскажите!

[Everything_is_bad]

Jammeren2, ой, не заливай, видно же что это какие-то учебные задачи, еще и несколько вопросов у тебя с ними

Answer 1

[Wataru]

Вообще говоря, однозначно вы восстановить все не сможете. Допустим у кольцо из 6 узлов:
100-101-102-103-104-105-100

При этом можно добавить связи 100-103 и 101-104. А можно добавить 100-104 и 101-103. В обоих случаях вы по всем портам видите одно и то же - все узлы. FDB таблица будет идентична.

Вы можете только определять компоненты двусвязности в графе - этакие кольца с всеми хордами внутри, но конкретные их формы - вы знать не можете.

Если допустить, что в графе нет парных ребер (2 узла не соеденины несколькими связями), то можно компоненты находить так: Если у узла по двум портам видны одни и те же узлы, эти 3 вершины надо объединить в одну компоненту. Потом эти компоненты надо "сжать". В любой записи все узлы из этой компоненты будут идти вместе - замените их все на один номер компоненты. Получится граф без колец, в нем решите задачу, как умеете. Все входящие ребра в компоненту надо назначить тому узлу, у которого по какому-то порту виден другой конец этого ребра. Потом как угодно объежинить все узлы в компоненте оставшимеся портами. Их там у каждого узла будет хотя бы 2, так что объедините их в произвольное кольцо и потом оставшиеся порты надо объединять парочками, начиная с двух самых больших узлов (по количеству не занятых портов).