[Xorp-hackers] Bug in route_table_decision::find_winner

[Euan Harris]

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: decision-bug.patch.gz
Type: application/x-gzip
Size: 1447 bytes
Desc: not available
Url : http://mailman.ICSI.Berkeley.EDU/pipermail/xorp-hackers/attachments/20070614/a590fd5b/attachment.gz