Re: BGP-4 changes

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

I think this is good.  It basically trades terseness for clarity.  Clarity
is good.

However, if we're going to do this, why not go whole hog and write a little
pseudo-code?  For example, when considering routes to destination D:

    for m = all Adj-RIB-In routes for destination D
        mark route m as MED-Superior
        for n = all Adj-RIB-In routes for destination D
            if (neighborAS(m) == neighborAS(n)) and (MED(n) < MED(m))
                mark route m as MED-Inferior

This is inefficient and I hope no one would actually implement this way,
but I believe it specifies the same thing and is rather unambiguous IMO.
There would probably be a disclaimer somewhere that emphasizes that any
implementation of route selection which has the same outputs is acceptable.

This would allow 9.1.2.1.a to be written as:

    a) Remove from consideration any routes marked as MED-Inferior
    following the procedure given in 5.1.4.

Below the copy of Rich's message, I'll append a 9.1.2.1 that incorporates
the above in a somewhat more compact form, and treats route selection as a
process of deleting non-preferred routes rather than a process of looking
for the preferred route.

Regards,

--John

---
At 4:03 PM -0400 8/29/96, Rich Woundy wrote:
> (Hi folks, I'm finally back)
>
> Yakov,
> I have some comments about your proposed text.
>
> >To: [e-mail]
> >Subject: BGP-4 changes
> >Date: Thu, 29 Aug 96 08:03:22 PDT
> >From: Yakov Rekhter <[e-mail]>
>
> >Folks,
>
> >Let me propose that we'll make the following changes to the
> >spec:
>
> >1. Add to 5.1.4 the following:
>
> >  MULTI_EXIT_DISC shall not be considered when comparing routes received
>from
> >  different neighboring ASs.
>
> I agree with your intent, but this is too easy to misinterpret.  For
> example, suppose a router has three routes for a prefix, with the same
> local preference: one from AS X w/MED 5, one from AS X w/MED 10, and one
> from AS Y w/MED 15.  I think the consensus is that the router should not
> compare the MED values 5 and 10 from AS X with the MED value 15 from
> AS Y.  On the other hand, we should also make it clear that as part of
> MED comparison, the route from AS Y w/MED 15 should be preferred over
> the route from AS X w/MED 10 -- otherwise, you can get routing loops.
>
> How about the following text?
>
>  MULTI_EXIT_DISC values of routes received from different neighboring
>  ASs shall not be directly compared.  However, to ensure consistent
>  route selection, the ranking of MULTI_EXIT_DISC values of routes
>  must be compared, where the MULTI_EXIT_DISC ranking is computed over
>  all routes for the same IP prefix from the same neighbor AS.
>
>  In particular, a route with the best MULTI_EXIT_DISC value from its
>  neighbor AS must be preferred over a route with an inferior
>  MULTI_EXIT_DISC value from its (possibly different) neighbor AS.
>  If two routes have the best MULTI_EXIT_DISC values from their
>  respective neighboring ASs, they must be considered equivalent with
>  respect to MULTI_EXIT_DISC comparisons.
>
>  In the ranking computation, the lower MULTI_EXIT_DISC values are
>  preferred, and a route without the MULTI_EXIT_DISC attribute
>  shall be treated as equivalent to a route with the highest
>  possible MULTI_EXIT_DISC value.
>
> >  When a route with the MULTI_EXIT_DISC attribute is received over an
> >  external link it must be possible (based on local configuration) to
> >  remove or override the value of the attribute. This shall be done
> >  prior to determining the degree of preference of the route.
>
> I agree totally with this text.
>
> >2. Replace 9.1.2.1 clause (a) with the following:
>
> >     a) If the local system is configured to take into account
> >      MULTI_EXIT_DISC, and the candidate routes differ in their
> >      MULTI_EXIT_DISC attribute but were received from the same
> >      neighboring AS, select the route that has the lowest
> >      value of the MULTI_EXIT_DISC attribute.  A route with
> >      MULTI_EXIT_DISC shall be preferred to a route without
> >      MULTI_EXIT_DISC.
>
> Can we assume that the local system must take into account MEDs?
> I think the answer is yes.  The new text you propose back in 5.1.4
> explicitly permits the removal or override of MEDs.  If an
> ISP wants to ignore MEDs in the route selection process, it is
> safer to remove MEDs from all routes at the borders (as is
> commonly done today), than to set a configuration option on all
> routers in the AS to change the route selection algorithm.
>
> How about the following text (which also refers to ranking)?
>
>  a) If the candidate routes differ in their MULTI_EXIT_DISC
>  attribute, select the route(s) that have the best MULTI_EXIT_DISC
>  values from their respective neighboring ASs.  The ranking of
>  MULTI_EXIT_DISC values per neighboring AS is described in 5.1.4.
>
> >Comments ?
>
> Yes, one more comment.  Notice how I put the missing MED case
> in the ranking discussion, not in the tie-breaking discussion.
> To see the subtle point I am making here, consider two routes
> from AS X w/MED 10 and from AS Y w/no MED.  I don't think we
> should penalize the route from AS Y; after all, does any provider have
> a problem with a peer provider that *encourages* shortest exit???
> (There may be other legitimate reasons why MEDs are not sent.)
> If we compare routes from AS X w/MED 10 and from AS X w/no MED,
> *then* we should discourage use of the missing MED route.
> The first comparison is a tie-breaking consideration, and the
> second comparison is a ranking consideration.
>
> >Yakov.
>
> -- Richard Woundy, IBM

----
This version of section 9.1.2.1 treats route selection as a process of
deleting non-preferred routes rather than a process of looking for the
preferred route.  I like some things about it (like the fact that I think
it's pretty clear) and dislike others (I'm not sure I like this use of
pseudo-code in the spec).  Note that the way I've written (a) allows 5.1.4
to mostly be left as it is currently.  We would NOT need this in 5.1.4:

  MULTI_EXIT_DISC shall not be considered when comparing routes received
  from different neighboring ASs.

I like getting rid of this, since it's better for all text relating to
route selection to go in the route selection section.

I would still like to have this, though:

  When a route with the MULTI_EXIT_DISC attribute is received over an
  external link it must be possible (based on local configuration) to
  remove or override the value of the attribute. This shall be done
  prior to determining the degree of preference of the route.


9.1.2.1 Breaking Ties (Phase 2)


   In its Adj-RIBs-In a BGP speaker may have several routes to the same
   destination that have the same degree of preference. The local
   speaker can select only one of these routes for inclusion in the
   associated Loc-RIB. The local speaker considers all equally
   preferable routes, both those received from BGP speakers located in
   neighboring autonomous systems, and those received from other BGP
   speakers located in the local speaker's autonomous system.

   The following tie-breaking procedure assumes that for each candidate
   route all the BGP speakers within an autonomous system can ascertain
   the cost of a path (interior distance) to the address depicted by the
   NEXT_HOP attribute of the route.

   The tie-breaking algorithm begins by considering all equally
   preferable routes and then selects routes to be removed from
   consideration.  The algorithm terminates as soon as only one
   route  remains in consideration.  The criteria must be applied
   in the order specified.

      a) Remove from consideration routes with less-preferred
      MULTI_EXIT_DISC attributes, according to the following
      procedure:

      for m = all routes still under consideration
          for n = all routes still under consideration
              if (neighborAS(m) == neighborAS(n)) and (MED(n) < MED(m))
                  remove route m from consideration

      In the pseudo-code above, MED(n) is a function which returns
      the value of route n's MULTI_EXIT_DISC attribute.  If route n
      has no MULTI_EXIT_DISC attribute, the function returns the
      highest possible MULTI_EXIT_DISC value, i.e. 2^32-1.

      Similarly, neighborAS(n) is a function which returns the
      neighbor AS from which the route was received.

      b) Remove from consideration any routes with less-preferred
      interior cost, according to the following procedure.  If the
      BGP speaker has no notion of the cost of a path, skip this
      step (equivalently, consider all routes to have equal costs).

      for m = all routes still under consideration
          for n = all routes in still under consideration
              if (cost(n) is better than cost(m))
                  remove m from consideration

      In the pseudo-code above, cost(n) is a function which returns
      the cost of the path (interior distance) to the address
      depicted by the NEXT_HOP attribute of the route.

      c) If at least one of the candidate routes was advertised by a
      BGP speaker in a neighboring autonomous system, remove from
      consideration all routes which were not advertised by a BGP
      speaker in a neighboring autonomous system.

      d) Remove from consideration all routes other than the route
      that was advertised by the BGP speaker whose BGP Identifier
      has the lowest value.

      [Alternately, this could be written as follows.  I guess I wrote
      the above out of some mania to preserve the purity of the
      "always delete from the set" idea.  The inverse formulation is
      less wordy:]

      d) Select the route which was advertised by the BGP speaker whose
      BGP Identifier has the lowest value.

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