OSPF performance/SPF calculations

[Ondrej Zajicek]

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).

> 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).

> 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.

-- 
Elen sila lumenn' omentielvo

Ondrej 'SanTiago' Zajicek (email: santiago at crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
"To err is human -- to blame it on a computer is even more so."
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: Digital signature
URL: <http://trubka.network.cz/pipermail/bird-users/attachments/20100421/72de77e4/attachment-0001.asc>