[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