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

[Curtis Villamizar <[e-mail]>]

Hi Rich,

Good to hear from you.

In message <19960821.143930.RWOUNDY@RHQVM21>, [e-mail] writes:
> >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.

We need administrative control over local-pref.  If some router vendor
wants to set local-pref according to some function based on a
configured value and the as-path length, that's OK.  If the choice is
either a configured value or based on as-path length, then for us
as-path length simply won't be considered.

I prefer keeping as-path length separate and explicitly mentioned in
BGP4.  I'd like to see both included in the decision with a given AS
given the option to consider as-path length or ignore it.

If there is consensus, then the consensus seems to be that as-path
length will never be considered by the protocol machinery but a
particular router vendor has a scheme to compute local-pref based at
least partially on as-path length.  Then you need an explicit
exclusion or a blanket exclusion of any other criteria as I had in the
last addition to the text.

> >   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.

The -1 thing is OK with me.  

I don't think a machine should ever be not "configured to take into
account MEDs".  I agree that the draft should be changed.  If some but
not all routers are configured to ignore MED route loops are almost
certain if MEDs are present.

What might need to be added is the option to pass MED into IBGP or not
pass MED into IBGP.  (I didn't look carefully - is it in there?).

> >   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.

This wouldwork too, but all routers in the AS must do the same thing.
If some other vendor does something else, different outcomes will
result and you'll get routing loops.

What you have described here is what I refer to as "insuring a fixed
order of comparison".  If we agree that we don't want to solve the
problem by comparing MEDs from different AS, then we might agree to
fix the problem by agreeing to use some fixed order of comparison.  We
can then agrue about what the order of comparison should be.

Either way something needs to go into BGP4 to address this or
different vendors will pick different solutions and multivendor
networks will still have route loops.

> 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.

There is a problem that needs to be solved and the current draft has
not addressed it.  I favor comparing MEDs across AS for simplicity,
but I'd go along with a fixed order of comparison if that was
preferred and we don't have vendors claiming it is too hard to do.

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

Not to mention getting the code right.

> -- Richard Woundy, IBM, [e-mail]
> 
> P.S. The expiration date of the latest spec needs to be fixed, too.

Regards,

Curtis