I had always thought the BGP path selection algorithm whittles down the alternative paths by elimination until only one candidate remains. But according to Wendell Odom's CCIE Certification Guide, page 445, that is not so. It appears that each of the 12 steps (or however many there are) is considered seperately. If any step fails to produce a unique clear winner, then all the paths are carried forward to the next step. That is, unless there is a clear winner, the ânon-bestâ paths are not eliminated.
This has some strange consequences that I am I having a hard time getting my head around. One example is in my blog:
Can anyone with BGP experience comment?
"No matter how it is implemented exactly, I believe the result should be equivalent to the bubblesort logic. "
This is correct.... There is no "carrying forward" of routes in the algorithm in any implementation, unless the routes are identical for the specific attribute being compared. No implementation that I'm aware of (having looked at gated, cisco, juniper, old procket, and several others) have ever implemented it in any other way. The results of each step are completely deterministic, all the time.
The only steps which vary from implementation to implementation are:
1. Cost community, which not all implementations support. Cisco only supports this with some insertion points. This doesn't make the result any less of a bubble sort, but it does mean that you may have different results on different implementations.
2. The final tie breaker is, on cisco implementations, the oldest route, rather than being based on the router id (though there is a knob for this). Some other implementations don't do this.