LSA ID Collision help

[Jigar Mehta]

So I tried tracing down this problem and here is what I got :

(Note :
1. 10.1.1.0 is a static route on the box and exported by custom protocol to
ospf
2. All these events happen within the same second)

1. when bird just comes up (box is rebooted), it tries to form adjacency and
eventually exchanges DBDES packets. In this case, it inserts (example
route )10.1.1.0/24 with a hash of 0000000000692768 and LSA ID :
10.1.1.0.
In this case, we use lsrqh hash table (Link state request queue hash) to store
the hash.

2. Now, bird sends out LSREQ packets to the DR(50.1.1.2) and receives LSUPD
packet from the DR static the following :
 LSA      Type: 0005, Id: 10.1.1.0, Rt: 10.0.1.11, Seq: 80000002, Age: 730,
Sum: 52d8
Bird identifies that the Rt:10.0.1.11 is its own IP and so marks this as a self
originated LSA (RFC 2328 13.4)

3. Bird installs the LSA with MAX AGE since it does not have a local copy of
the route and tries to flood out this update(floods out with max age of 3600)
(RFC 2328 13.5(f)
The LSA is installed using graph tree hash table.
hash entry 0000000000691b58 LSA ID: 10.1.1.0
ospf_lsa_lsrq_down:LSA hash 0000000000692768 removed ID 10.1.1.0 rtr:10.0.1.11
ospf_lsa_lsrt_up:get new hash entry same as 0000000000691b58 10.1.1.0
get new hash e:000000000069dcb8 LSA ID 10.1.1.0
So now, the lsrqh hash table has LSA ID 10.1.1.0  with hash set as
000000000069dcb8

4. Due to flooding, we receive LSUPDATE packet from our DR and now since we
have a local copy, we delete the hash entry from lsrqh hash table as per RFC
2328 13.3
LSA hash 000000000069dcb8 removed ID 10.1.1.0

< So at this point, there is no hash entry for 10.1.1.0 in lsrqh but we still
have a hash entry in the top graph tree hash table (p->gr) since we call
ospf_disp (ospf hearbeat/ospf table calculations) every second and all of this
is happening within same second >

5. Now custom protocol tries to redistribute apn routes to ospf and
ospf tries to add it to the top graph hash table where the hash
already exists resulting in LSA
ID collision.
(Note this would happen even with BGP redistributing to OSPF)


Also, is there a good way to announce from the custom protocol every X
seconds to sync up route tables with other protocols (send its routes
to other protocols).

I wanted to add this to my protocol so inspite of the above
collisions, I can still add back the routes. Might try using
rte_announce() but the problem is my protocol stores multiple routes
to same network with different cost and in this case, I want to
announce ALL routes not just RA_OPTIMAL.


   -


On Fri, Mar 18, 2016 at 5:43 AM, Ondrej Zajicek <santiago at crfreenet.org>
wrote:

> On Thu, Mar 17, 2016 at 06:14:24PM -0400, Jigar Mehta wrote:
> > Hi ,
> >
> > I cannot recreate this scenario at will but had some success when
> > restarting protocols or rebooting the linux box or feeding 1000+ routes
> (to
> > BGP and redistribute to OSPF in router) to the setup mentioned above.
> > My IP address space was not overlapping either, so the LSA ID generated
> > would have been unique.
> >
> > Also, I noticed that if I insert overlapping addresses in my protocol and
> > redistribute to OSPF , I see LSA ID collisions (bug ?)
> > Eg:
> > 2016-03-17 16:29:21 <ERR> ospf_0: LSA ID collision for 10.0.192.127/32
> > 2016-03-17 16:30:31 <ERR> ospf_0: LSA ID collision for 10.0.192.0/25
>
> Hi
>
> I don't know about the first case, but the second case (with overlaps) is
> expected. For each prefix, the number of possible subprefixes is about
> about two times larger than the number or possible LSA IDs. BIRD uses
> static assignment of LSA IDs <-> prefixes, so there are collisions even
> if just some subprefixes are originated.
>
> There is a simple rule to avoid LSA ID collisions - when exporting a
> prefix, do not export /32 representing the first and the last IP address
> in that prefix. Other overlapping prefixes should be fine.
>
> --
> 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."
>



-- 
Jigar Mehta
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://trubka.network.cz/pipermail/bird-users/attachments/20160321/c3af1fb6/attachment.html>