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

["John G. Scudder" <[e-mail]>]

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

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 to
>> do this, e.g. the election Rich has written about.  I tend to think of this
>> 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