Addr: Re: BGP-4 - revised I-D

[[e-mail]]

>Date: Tue, 20 Aug 1996 21:24:02 -0400
>From: Curtis Villamizar <[e-mail]>

>Yakov,

>BGP4 is great stuff but for it to advance, we really should clean up
>the document to make it harder to come up with implementations that
>are compatible with the BGP4 RFC but don't interoperate well enough
>with other implementations to insure loop free operation.

>We gained a lot of experience with gated, Cisco, and Bay
>implementations of BGP4.  Subtle differences in the route selection
>rules of each can cause route loops, in some cases in single vendor
>environments, but mostly when mixing implementations.

Curtis,

I agree with this 100%, but I disagree with the details below.

>First, here are conditions that can cause routing loops.  These all
>involves differences in route selection criteria or route selection
>criteria that can cause routing loops if routes are evaluated in
>different orders on different routers in a network.

>   a. We haven't seen anyone lose the significance of local-preference
>      as the primary selection criteria.  I'd like to see the spec
>      absolutely clear about this.

>   b. We have seen routing loops form as a result of some routers
>      using AS-path length in the decision criteria.  If this is not
>      standard behavior, then the spec needs to say that.  If this is
>      useful (it is) but not standard behavior, the spec needs to
>      allow it as an option.

I think Paul Traina had the best idea here: incorporate the AS path
length and origin code selection criteria into the local pref value
(therefore, leave the main BGP spec as is).

I think I now understand how the local pref computation *could* work;
maybe I can send a note about it to the mailing list today.

>   c. Differences in interpretation of a missing MED and poor choice
>      of behavior covering a missing MED.  Without going into details
>      (see below) preferring a route with no MED over one with a
>      MED can cause route loops.  Not considering MED at all in
>      comparing routes with MED to routes without can cause route
>      loops.  This is addresses by the changes you've made.

I think at least one more change is needed in the new draft: removing
the clause "if the local system is configured to take into account MEDs"
I thought we agreed in Montreal that this configuration option does
not exist in today's routers, does not provide value-add to providers,
and can result in routing loops when internal peers are misconfigured
with respect to each other.  The reason why it does not provide value
add is that providers can change MEDs in BGP updates (ala "route-map")
to a uniform value (say 0), which effectively makes the path selection
step of comparing MEDs into a perpetual tie.

Should this be revisited (i.e. did I see consensus where none existed)?

Also, I thought we agreed that a missing MED on a route would be equal
to, not worse than, a MED of -1 on a route. The reason was to avoid a
separate check of whether the MED existed, with the (trivial) penalty
of losing one out of 2**32 MED values.

>   d. Without going into details (see below) not considering MED
>      when comparing routes from different AS can cause routing loops.
>      This is not addressed by the changes you've made.  BGP4 needs to
>      explicitly require considering MED when comparing routes from
>      different AS.

You do not have to require comparison of MED values from different ASes
(I speak from implementation and network deployment experience here).
You need to change the path selection comparisons somewhat from the
simple binary comparisons that often exist in BGP implementations.

For example, here are three paths to the same destination prefix, where
simple sequential comparison fails:
 path 1 from neighbor AS X, MED 10, IGP distance 20
 path 2 from neighbor AS Y, MED 15, IGP distance 15
 path 3 from neighbor AS X, MED 20, IGP distance 10
Using binary comparisons (all other factors being equal), path 2 is
better than path 1, path 3 is better than path 2, and path 1 is better
than path 3.

What I implemented in gated (not necessarily the best way, but it works)
is what I have called "MED election".  When receiving a BGP update
from neighbor AS Z, I compare and mark all of the routes for the same
prefix from neighbor AS Z that have the best MED value (note that it
is easy to get ties). Then, I use binary comparisons to sort the list
of routes. At the path selection stage where MEDs are considered, I
compare "best-MED-from-its-neighbor-AS" marks instead of MED values.

In the example above, paths 1 and 2 would have the best-MED marks,
and path 3 would not (because of the existance of path 1).
I do not directly compare MEDs *values* from different neighbor ASes,
but I compare best-MED *marks* from different neighbors ASes instead.

I've heard Cisco has fixed their version of this problem recently, but I
don't know what their implementation looks like.

If we (as a working group) agree that we should not compare MED values
from different neighbor ASes, then we should at least document a MED
election algorithm somewhere.

My biggest concern about MED election is the extra effort required
(read: CPU load on non-default routers).

-- Richard Woundy, IBM, [e-mail]

P.S. The expiration date of the latest spec needs to be fixed, too.