OSPF performance/SPF calculations

[Joakim Tjernlund]

>
> Ondrej Zajicek <santiago at crfreenet.org> wrote on 2010/04/21 20:15:07:
> > On Wed, Apr 21, 2010 at 09:41:47AM +0200, Joakim Tjernlund wrote:
> > > I am using Quagga ATM but I had a quick look at BIRD and I got a few
> > > observations.
> >
> > Hello. Thank you for your tips and notes.
> >
> > > The LSA/checksum code seem very inefficient.
> > > LSAs are built allocating/reallocing bits
> > > of memory. This is slow and will case memory fragmentation.
> >
> > You mean lsab_alloc() in originate_rt_lsa_body()?
> > This allocation is just a sequential allocation in a persistent memory buffer,
> > therefore it is very efficient (in most cases just increase of lsab_used counter)
> > and there si no memory fragmentation (all is done inside a persistent memory buffer).
>
> Yes, you do realloc on small amounts of memory. Also, receives LSAs
> seems to be impl. differently so you need handle these somewhat
> differently.
> >
> > > The fletcher checksum is very slow as it has extra tests in the hot path and also
> > > flips endian in the LSA back and forth.
> >
> > Do you have some suggestions for a better algorithm, or just a better
> > implementation? Yes, the problem with flipping endianity is known.
> > I do not studied this part of the code yet (the checksum algorithm).
>
> Yes, but not at the moment. The endian problem should be addressed when you
> build the lsa.
>
> >
> > > I can't work out how the SPF next hop works(calc_next_hop). I tried to
> compare it with
> > > Quagga's ospf_nexthop_calculation() but the structure is too different. The reason
> > > for me looking into this was to see how much work it would be to add
> > unnumbered ppp links
> > > but as I can't work out how nexthop is working I didn't get very far.
> >
> > The current code is different from what RFC says. For direct neighbors
> > (on both ptp and non-ptp networks), we just use IP address taken from
> > the source address of the HELLO packet of the neighbor (stored in
> > neighbor structure returned by find_neigh_noifa()).
> >
> > This works well [*] for both broadcast and ptp links (numbered or
> > unnumbered), but is broken on NBMA networks. I have some not-yet-commited
> > changes to calc_next_hop() that on broadcast and NBMA networks uses the
> > standard way (taking IP address from the router LSA) and the source address
> > from HELLO packet as a nexthop is used just for PTP links.
> > Such behavior is also suggested by RFC 5340 (for OSFPv3).
> >
> > [*] Regardless of how the other side is implemented.
> >
> > > I have impl. unnumbered ppp link for Quagga that works really well but this work
> > > hasn't been accepted into Quagga yet since Quagga development has stalled.
> > > I could show you how I did it Quagga though.
> >
> > The development state of Quagga is sad. Do you implement it in a different
> > way than in BIRD? I wonder whether there is any other possible way to get
> > next hop address for unnumbered ptp links than from source address
> > of HELLO packet.

> Yep, now it gets tricky. It took me quite some time to figure out what to
> do. The secret is that you never use search for the interface using IP addresses
> in the LSA's. Instead you record what interface created what entry in in your
> own Router LSA. Based on the position of on entry in your own router
> LSA you can lookup the interface that created that entry. Once
> you know the interface, the reset is easy.
>
> One way to impl. this is to build an array of interface pointers when
> you construct the Router LSA:
> RLSA     Array
> Item 0   ptr to ppp0
> Item 1   ptr to ppp0
> Item 2   ptr to eth0
> ...
> Item n   ptr to if n
>
> Now you can easily find the interface if you pass on the position of the
> the entry in the RLSA you are processing to the nexthop calculation.
>
> I have a few patches to Quagga that does this somewhere, they are all
> on the Quagga mailing list and a few of them are also in my personal
> git repo at the Quagga site.
>
>  Jocke

Found two different impl. I did for Quagga. Figured you could use
them to get an idea.