[Moscow.pm] Взрыв мозга или занимательная топология

[Kaltashkin Eugene]

Александр Букреев пишет:
>> Предлагаю некоторую разминку для мозга.
>>     
>
> Хорошая задачка. Я над такой месяца три голову ломал.
> За счет того, что мне не были изначально известны все исходные
> технические данные видимости коммутаторов. :-)
> Т.е. придумывал алгоритм, мне говорили: ДА, но есть еще условие. :-)
>   
Идея Андрея была хороша. проверил её на деле, результаты уже есть.
Но с оговорками.
> Я бы на вашем месте для упрощения сделал некоторые вещи:
> 1. Взял бы для расчета только коммутаторы и концентраторы (вы же
> знаете мак-адреса своих устройств?).
> 2. Выделил бы корневое устройство (максимально равноудаленное от оконечек).
> Ну есть же узел связи для такой топологии, вот там устройство и
> берите. На схеме - устройство №2.
>   
проблема в том, что корневым устройством может быть любое :)
> Я делал по вычислению однозначных связей.
> А потом уже по вычисленным связям строил дерево.
> Однозначные связи можно построить только имея корневое устройство,
> т.к. связи вообще тут можно построить только от оконечных устройств к
> корневому. В обратную сторону ничего не построите.
>
> Как строить - уже подсказали: откидывать оконечные и вычеркивать их
> везде из видимости...
всё бы здорово, но есть проблемы. в таблице 2529 записей.
пришлось сделать
delete from mactable where macaddr not in (select macaddr from mactable 
where status='private');
получил 634 убитые записи, т.е. убрал все записи которые не 
классифицированы и не привязаны к какому-либо свичу.
Есть подозрение, что можно случайно потерять данные об устройствах.
потом вроде cработало
select switch,port,count(*) from mactable where status is null group by 
switch,port;
даёт полный список количества устройств на портах up/downлинков.
запрос
select switch,port,count(*) from mactable where status is null and 
macaddr not in (select macaddr from mactable where switch='10.6.204.21' 
and status = 'private') group by switch,port;
убирает из этого списка порт с downlinkом.

продолжаю исследования.