Subject: Re: issue 11

From: Curtis Villamizar <[email-masked]>
Date: Tue, 01 Oct 2002 19:36:25 -0400

In message <[email-masked]>, Alex Zinin writes:
> Yakov,
> 
> [...]
> >>    Multipath is
> >>   something that is normally in the heart of a routing protocol. There
> >>   should be a good reason to want something like this in a separate
> >>   document. Do we have one in this case?
> 
> > Time. If we are interested in getting the base spec completed within
> > the timeframe outlined in the current charter, we can't add
> > substantial new material to the spec. 
> 
> I share the concern about time. However, the issues related to best
> path calculation, multipath included, seem to me to be quite important
> from the perspective of interoperability and description of further
> extensions. Maybe if we the chairs could get the right people together
> and facilitate the process (ADs would definitely contribute to buying
> the libations), such a design team could come up with solid stuff
> within a month?
> 
> BTW, regarding the part of the spec describing the best path selection
> algo, I remember there was a concern that it didn't really describe
> what vendors actually did. Is it still the case?
> 
> Alex

Alex,

Two prior issues were use of "shortest AS path" and a detail of "MED
handling".  The former is in there, the latter is still a little
deficient.

The prior issue was inclusion of "shortest AS path" which wasn't in
earlier BGP-4 but Cisco has always done.  It is now in there.  It
reflects what Cisco does.  Everyone else seems to have a "Cisco BGP
compatibility" knob to enable it (typically enabled by default).

The other issue was MED handling.  In "5.1.4 MULTI_EXIT_DISC":

   A BGP speaker MUST IMPLEMENT a mechanism based on local configuration
   which allows the MULTI_EXIT_DISC attribute to be removed from a
   route. This MAY be done prior to determining the degree of preference
   of the route and performing route selection (decision process phases
   1 and 2).

   An implementation MAY also (based on local configuration) alter the
   value of the MULTI_EXIT_DISC attribute received over an external
   link.  If it does so, it shall do so prior to determining the degree
   of preference of the route and performing route selection (decision
   process phases 1 and 2).

This doesn't sufficiently address the issue.

The MED step in the decision process is (in 9.1.2.2):

      c) Remove from consideration routes with less-preferred
      MULTI_EXIT_DISC attributes. MULTI_EXIT_DISC is only comparable
      between routes learned from the same neighboring AS. Routes which
      do not have the MULTI_EXIT_DISC attribute are considered to have
      the lowest possible MULTI_EXIT_DISC value.

      This is also described in 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 lowest
      possible MULTI_EXIT_DISC value, i.e. 0.

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

The problem is that a route loop can be formed.

To avoid the route loop, two suggestions were made (2-3 years ago and
nothing was done).  One was to make MED(n) return infinity if there
was no MULTI_EXIT_DISC.  The other was to consider MULTI_EXIT_DISC in
the decision process only for the purpose of selecting among the EBGP
peers, then remove MULTI_EXIT_DISC, then use that best route in
comparisons to IBGP learned routes.

The statement in 5.1.4 "This MAY be done prior to determining the
degree of preference of the route and performing route selection
(decision process phases 1 and 2)" does not sufficiently address this.
This implies that you MAY also remove after route selection, in which
case field experience indicates you WILL get burned (unless you know
about the caveat above).  Initially this came up as an
interoperability issue but later it was proven (in the field) that a
Cisco and another Cisco could form a route loop until Cisco made this
change.

Additional wording is needed either in 5.1.4 or in 9.1.2.2.  I suggest
we put a forward reference in 5.1.4:

   [...]. This MAY be done prior to determining the degree of preference
   of the route and performing route selection (decision process phases
   1 and 2).  See section 9.1.2.2 for necessary restricts on this.

Then in 9.1.2.2 add a clarificatio to the neighborAS(n) function and
add to the existing text.

      Similarly, neighborAS(n) is a function which returns the
      neighbor AS from which the route was received.  If the route is
      learned via IBGP, it is the neighbor AS from which the other
      IBGP speaker learned the route, not the internal AS.

      If a MULTI_EXIT_DISC attribute is removed before redistributing
      a route into IBGP, the MULTI_EXIT_DISC attribute may only be
      considered in the comparison of EBGP learned routes, them
      removed, then the remaining EBGP learned route may be compared
      to the remaining IBGP learned routes, without considering the
      MULTI_EXIT_DISC attribute for those EBGP learned routes whose
      MULTI_EXIT_DISC will be dropped before advertising to IBGP.
      Including the MULTI_EXIT_DISC of an EBGP learned route in the
      comparison with an IBGP learned route, then dropping the
      MULTI_EXIT_DISC and advertising the route has been proven to
      cause route loops.

The loop is the classic I prefer your and you prefer mine problem.  It
occurs when the router is configured to remove MULTI_EXIT_DISC and
advertise out a route so other routers can use IGP cost to select the
best route.  If two routers do this, as soon as they hear the route
with no MULTI_EXIT_DISC from the other peer they start forwarding
toward that peer but they continue to advertise to it since others
IBPG peers are expected to select among the MULTI_EXIT_DISC free IBGP
learned routes using the next step in the decision process, IGP cost.

In this case, what you want is each router to prefer its own EBGP
route, even though it has a MULTI_EXIT_DISC and the IBGP learned route
from the same neighbor AS has had its MULTI_EXIT_DISC stripped off (or
didn't have one, you can't tell which it is).  You then want all of
the IBGP peers with a MULTI_EXIT_DISC free route from that AS, or that
have stripped the MULTI_EXIT_DISC to form one, to advertise them.
Others in the AS will then use IGP cost to further resolve which exit
point to use.  It make a difference when the route is the aggregate
route of another major provider.  IGP cost yields what ISPs call "hot
potatoe routing" and MED selects among multiple heavily loaded
provider interconnects.

[Aside: Having a missing MULTI_EXIT_DISC default to infinity would do
exactly what the ISPs want it to do in the first place and be a lot
easier to explain but we didn't fix that 2-3 years ago when the issue
came up even though we had WG consensus that it was the right thing to
do.  The authors didn't act on it at the time (because Cisco didn't do
it that way and the authors preferred to sit on the draft).  At this
point we might as well adequately document what we ended up with....
End of soapbox.  I don't take myself all that seriously so others
shouldn't either.  :-)]

Curtis

---

From: Alex Zinin <[email-masked]>
Date: Wed, 2 Oct 2002 15:57:54 -0700

Curtis,

  Sounds like we have another issue to fix. If so, Andrew,
  could you please put this on the list?

-- 
Alex

---

From: Jeffrey Haas <[email-masked]>
Date: Thu, 3 Oct 2002 11:05:30 -0400

> what vendors actually did. Is it still the case?

Cisco has cluster length as part of their tie-breaker.

I'm curious about the scenario that is trying to be addressed by this.

-- 
Jeff Haas 
NextHop Technologies

---

From: vrishab sikand <[email-masked]>
Date: Thu, 3 Oct 2002 11:17:55 -0700 (PDT)

> I'm curious about the scenario that is trying to be
hierarchical route reflector configurations. i.e.
levels of RR clusters.
Routes which have come through a no RR are prefferred
over routes which come over one level of RR, are
preffered over 2 two levels etc.
  At least one of the biggest ISP's uses RR's in this
way.
> > Alex

__________________________________________________
Do you Yahoo!?
New DSL Internet Access from SBC & Yahoo!
http://sbc.yahoo.com

---

From: Curtis Villamizar <[email-masked]>
Date: Thu, 03 Oct 2002 15:22:02 -0400

In message <[email-masked]>, vrishab sikand
>   At least one of the biggest ISP's uses RR's in this

It would be useful to add this to the RR RFC.

It could be mentioned in the base spec.  I defer to Yakov, Sue, Alex,
and Bill for that decision.

Curtis

---

From: Jeffrey Haas <[email-masked]>
Date: Thu, 3 Oct 2002 15:28:01 -0400

> It would be useful to add this to the RR RFC.

That would be my preferred action.

However, I would also prefer that the AS_PATH length calculation
for confederation segments (i.e. they have zero value) also be
moved into the confed update.

-- 
Jeff Haas 
NextHop Technologies