[Xorp-hackers] Bug in route_table_decision::find_winner
Atanu Ghosh
atanu at ICSI.Berkeley.EDU
Mon Jun 18 16:31:33 PDT 2007
Hi,
Thanks for the fix, it is now checked in.
Atanu.
>>>>> "Euan" == Euan Harris <euan.harris at cl.cam.ac.uk> writes:
Euan> Hi, I think I've found a bug in the path attribute comparisons
Euan> in the route selection algorithm. In some circumstances the
Euan> loop that is supposed to select the routes with the best
Euan> values of a particular attribute will also select one or more
Euan> routes which have poorer values for that attribute.
Euan> Here is an example from the local preference stage; the same
Euan> loop is replicated for all the other attributes except MED:
Euan> route_table_decision::find_winner
>> int test_pref = local_pref(alternatives.front().route(),
>> alternatives.front().peer_handler()); i = alternatives.begin();
>> i++; while(i!=alternatives.end()) { int lp =
>> local_pref(i->route(), i->peer_handler()); XLOG_ASSERT(lp >= 0);
>> //prefer higher preference if (lp < test_pref) { i =
>> alternatives.erase(i); } else if (lp > test_pref) { test_pref =
>> lp; alternatives.pop_front(); i++; } else { i++; } }
Euan> The loop is supposed to select the routes with the highest
Euan> local preference values. If alternatives has three routes
Euan> with local preference values [100, 100, 200] at the start then
Euan> after the loop finishes it should only contain [200]. However
Euan> the actual result is [100, 200] - the loop does not delete the
Euan> second 100 preference route.
Euan> Another example: a starting list of [50, 50,
Euan> 50,100,100,100,100,200,100,200,200] should be [200, 200, 200]
Euan> after filtering but will instead be [50, 100, 100, 100, 100,
Euan> 200, 200, 200]. In this case the loop encountered new maximum
Euan> values twice and so popped off the top two 50 pref routes but
Euan> none of the 100s.
Euan> The problem is that when the loop finds a new maximum
Euan> preference value it only pops the first route from the list:
>> } else if (lp > test_pref) { test_pref = lp;
>> alternatives.pop_front(); i++; } else {
Euan> If more than one route with that preference value has been
Euan> seen all the others will be left on the list. To be correct
Euan> the loop should erase all routes from the beginning of the
Euan> list to the new maximum:
>> } else if (lp > test_pref) { test_pref = lp;
>> alternatives.erase(alternatives.begin(), i); i++; } else {
Euan> This bug would cause the wrong route to be selected if, for
Euan> instance, a route with lower local preference erroneously
Euan> passed through local preference filtering and then beat a
Euan> route with higher local preference on AS path length.
Euan> I've attached a patch against CVS HEAD which fixes the 7
Euan> filter loops like this in route_table_decision::find_winner
Euan> and adds a test demonstrating the bug to
Euan> test_decision{.cc,.reference}. Apply with patch -p0 in the
Euan> toplevel directory.
Euan> Thanks, Euan
Euan> _______________________________________________ Xorp-hackers
Euan> mailing list Xorp-hackers at icir.org
Euan> http://mailman.ICSI.Berkeley.EDU/mailman/listinfo/xorp-hackers
More information about the Xorp-hackers
mailing list