[Xorp-hackers] Bug in route_table_decision::find_winner

[Mark Handley]

Thanks Euan - from reading the code, I agree with your analysis - this
does indeed appear to be a problem.  Mea culpa.  Your fix looks good
to me too.

 - Mark

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