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