[quagga-dev 9598] Re: [PATCH] ospfd: avoid exhausting memory with OSPF vertices (BZ#476)

Scott Feldman sfeldma at cumulusnetworks.com
Wed Aug 1 22:03:33 BST 2012


On Aug 1, 2012, at 1:57 PM, Joakim Tjernlund wrote:

> Scott Feldman <sfeldma at cumulusnetworks.com> wrote on 2012/08/01 20:06:29:
>> 
>> 
>> On Aug 1, 2012, at 2:41 AM, Joakim Tjernlund wrote:
>> 
>>> Scott Feldman <sfeldma at cumulusnetworks.com> wrote on 2012/08/01 00:15:24:
>>>> 
>>>> On Jul 31, 2012, at 2:31 PM, Joakim Tjernlund wrote:
>>>> 
>>>>>> The topology used in testing was an NxN grid of routers.  For example, a 4x4 grid:
>>>>>> 
>>>>>>                      r1
>>>>>>                      /\
>>>>>>                     /  \
>>>>>>                    r2  r3
>>>>>>                    /\  /\
>>>>>>                   /  \/  \
>>>>>>                  r4  r5  r6
>>>>>>                  /\  /\  /\
>>>>>>                 /  \/  \/  \
>>>>>>                r7  r8  r9 r10
>>>>>>                 \  /\  /\  /
>>>>>>                  \/  \/  \/
>>>>>>                  r11 r12 r13
>>>>>>                   \  /\  /
>>>>>>                    \/  \/
>>>>>>                    r14 r15
>>>>>>                     \  /
>>>>>>                      \/
>>>>>>                      r16
>>>>>> 
>>>>>> So from root r1, r4 gets nh thru r2, r5 gets nhs thru r2/3, and r8 inherits nhs from r4 and r5, so it get 3 nhs, two of which are duplicates.  The further you get from root, the more duplication.  For this small grid, the duplicates aren't a big deal.  However, the duplicate nhs grow
>>>>>> combinatorially, so for a larger N, say 13, you have a very large number indeed.  Enough to exhaust memory in our testing.  The patch removes the duplicates as SPF works thru the graph, so r16 above would have just the 2 nhs, not the 20 nhs without the patch.
>>>>>> 
>>>>> It would be interesting to rerun this test with latest Quagga as the SPF code got some changes.
>>>> 
>>>> I re-tested 13x13 with the above fix on top of your 4 SPF patches, and test PASSES.
>>> 
>>> Nice! If you got the time, could you back out the
>>> ospfd: Do not fall back to intervening router
>>> and see if that makes the error come back?
>> 
>> I'm not quite sure what you're asking, but I did try same 13x13 test without the above fix and with your 4 SPF patches, and the test FAILS, as before.
> 
> hmm, there seems to be a misunderstanding here. Lets start over.
> Start with current quagga tree + your own get_next_link() in nexthop_calculation.
> 
> Then remove the patch
>  ospfd: avoid exhausting memory with OSPF vertices (BZ#476)

The test fails with that setup.

> Run test and if that passes, remove the patch
>  ospfd: Do not fall back to intervening router
> and tell if that passes or fails.





More information about the Quagga-dev mailing list