[rbridge] Pseudonode minimization thoughts...

[mike shand]

On 31/01/2008 mike shand wrote:
> I'm not even convinced it simplifies the SPF, but since an SPF for a 
> several hundred node network takes < 1mS, I don't see this as a big 
> issue either way. However for a 15 node LAN, WITH pseudonode you explore 
> 1 hop to the PN then 14 hops to the other nodes, then check on back link 
> from each of the 14 to the PN (i.e 29 links). In the non PN case you 
> explore 14 hops, then another 14 hops back from each of those 14 (i.e. 
> 210 links). It would need a better analysis to determine exactly what 
> the relative merits are, but at best I would say it is a wash, and it 
>
> might even be a pessimisation not to have a PN.
>   
I couldn't resist conducting the experiment:-) For what its worth, my 
simulation seems to indicate that the SPF is faster WITH the pseudonodes 
than without, at least for 4 node LANs and above.

I constructed a network consisting of 4 LANs each containing 4 routers. 
The groups of routers were randomly interconnected with point to point 
links.

The average time to run an SPF WITH pseudonodes was 52 uS, and without 
pseudonodes (i.e. each "LAN" of 4 routers was replaced by a fully meshed 
set of pt-pt links... each router connected to the 3 other routers on 
the "LAN", was 64uS.

The absolute values are irrelevant, but it does seem to indicate that, 
for 4 node LANs, the SPF is faster with pseudonodes.


As I said, I don't think this matters at all; it is lost in the noise, 
but it certainly can't be said that it is BETTER not to have the 
pseudonodes from the SPF point of view.

    Mike