Ondrej Zajicek <santiago@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.