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

[Curtis Villamizar <[e-mail]>]

In message <v0300781dae4a5559835d@[36.141.0.30]>0]>, "John G. Scudder" writes:
> Curtis,
> 
> [regarding need for specification of a particular MED election algorithm]
> At 1:36 PM -0400 8/28/96, Curtis Villamizar wrote:
> >Yes it is absolutely neccesary.  The order in which routes are
> >compared impacts the outcome of the comparison.
> 
> How is the text already in RFC 1771 section 9.1 not sufficient to clearly
> specify the order?  To summarize, it says that when selecting a route you
> should consider, *in this order*:
> 
> - Local_Pref
> - MED (adding the note that you can only compare MED between like ASes)
> - IGP distance
> - EBGP better than IBGP
> - Router ID
> 
> As far as I can tell this specifies everything which is needed for
> loop-free operation (I do understand the issue and agree with you).  I
> think that this:
> 
> >   One route from the neighboring
> >   AS is selected as best.  The best routes from each of these
> >   neighboring AS are then compared.
> 
> goes from specifying the algorithm (necessary) to specifying implementation
> (unneccessary).  Perhaps 9.1.2.1 could be made even more explicit as to the
> order in which the tie-breaking criteria must be applied, and there could
> be a forward reference from 5.1.4 to make sure people don't miss this.
> 
> Regards,
> 
> --John


John,

We need to go back quite a few messages on another recent thread.

  Refer to the diagram below where R{1-5} are routers and the numbers on
  the lines are IGP link costs.

    R1  --6--  R4  --1--  R5  --4--  R3
    R2  --2-/

	...

            AS  MED     IGP             
        R3   x   1      4-5             R2 is better than R3 (lower IGP)
        R2   y   2      2-3             R1 is better than R2 (lower MED)
        R1   y   3      6-7             R3 is better than R1 (lower IGP)

        R4 learns R1, R2, R3.  It prefers R3.  (R3 announcement delayed)
        R5 learns R3, R1, R2.  It prefers R2.
        R4 and R5 point next hop at each other.

This loop occurs if the comparison algorithm is:

  take the recently learned route and compare it with the current best
  route.

Two astute vendors might decide to fix this by insuring a fixed order
of comparison so that a loop could never form in a network of only
their routers.

One might decide to compare all routes from the same AS first, then
compare the best from each AS.

Another might decide to run the comparison from lowest advertising
router IP address to highest so the comparison order was constant
regardless of the order they came in.

The would be no loops due to MED in single vendor networks.  In a
multivendor network there would be loops.

I just want to fix BGP4 so multivendor networks will not form routing
loops.

Curtis

ps- I think we're now converging on a loop free route to concensus.  ;-)
[I know - corny as it gets!]


> P.S.:  Please do re-read 9.1.2.1 if you haven't already.  A few comments on
> your full text below, just in case I haven't been clear enough above:
> 
> At 1:36 PM -0400 8/28/96, Curtis Villamizar wrote:
> >In message <v03007820ae49140b08b4@[36.141.0.30]>0]>, "John G. Scudder" writes:
> >>
> >> I don't know if folks think it is also necessary to specify an algorithm t
> o
> >> do this, e.g. the election Rich has written about.  I tend to think of thi
> s
> >> as an implementation detail, but if people are complaining that MED is too
> >> hard to implement, I guess an existence proof to the contrary might be
> >> useful.  Perhaps as an appendix?
> >
> >
> >Yes it is absolutely neccesary.  The order in which routes are
> >compared impacts the outcome of the comparison.
> >
> >Lets say we don't.
> >
> >Most readers will not notice that there is the possibility of a
> >routing loop.  Routing loops will form.
> >
> >The very astute reader will notice that there is the possibility of a
> >routing loop if the order of comparison is not constrained to be the
> >same on all routers.
> 
> But 9.1.2.1 does constrain the order.
> 
> >Said reader picks an algorithm.
> 
> Which is non-compliant if it doesn't match 9.1.2.1.
> 
> >The algorithm
> >chosen is to compare all routes in order of lowest advertising router
> >first.  These routers work fine in a network of like routers.
> 
> Which won't be talking BGP4 but some similar thing instead.
> 
> >Put in
> >a router using Rich's algorithm and a routing loop forms since those
> >routers evaluate in a different order and come to a different
> >conclusion about which route is best.
> >
> >This will form routing loops.  Its been proven in real networks.
> >
> >The text could be as simple as:
> >
> >> 5.1.4   MULTI_EXIT_DISC
> >>
> >>    The MULTI_EXIT_DISC attribute may be used on external (inter-AS)
> >>    links to discriminate among multiple exit or entry points to the same
> >>    neighboring AS.  The value of the MULTI_EXIT_DISC attribute is a four
> >>    octet unsigned number which is called a metric.  All other factors
> >>    being equal, the exit or entry point with lower metric should be
> >>    preferred.  If received over external links, the MULTI_EXIT_DISC
> >>    attribute may be propagated over internal links to other BGP speakers
> >>    within the same AS.  The MULTI_EXIT_DISC attribute is never
> >>    propagated to other BGP speakers in neighboring AS's.
> >
> >   Due to the MED rules, route comparisons among all of the available
> >   routes may not have the transitive property.  Under some circumstances
> >   routing loops can form if routes are not evaluated in the same or a
> >   similar order on all routers.  The following order of comparison must
> >   be implemented:
> >
> >   All routes from the same neighboring AS are compared.  The MED value
> >   and the presence or absence of MED must be considered when comparing
> >   routes from the same neighboring AS.  One route from the neighboring
> >   AS is selected as best.  The best routes from each of these
> >   neighboring AS are then compared.  The MED value or the presence or
> >   absence of MED must be ignored when comparing the best route from each
> >   neighboring AS.
> >
> >This text assures that all implementors that carefully read an follow
> >the BGP4 spec will end up with implementations that 1) are loop free,
> >2) interoperate in a loop free manner with other implementations, 3)
> >don't require that MED be completely disabled to remain loop free in
> >the presence of other implementations.
> 
> BTW my notes about being able to disable MED really relate to (1) needing
> to interoperate with current routers, and (2) making any (hypothetical)
> people happy who are afraid of the CPU overhead of electing the best route
> per AS.
> 
> >Curtis
> 
> 
> --
> John Scudder                        email:  [e-mail]
> Internet Engineering Group, LLC     phone:  [phone]
> 122 S. Main, Suite 280              fax:    [phone]
> Ann Arbor, MI  41804                www:    http://www.ieng.com
> 
>