Subject: BGP ECMP

From: Manav Bhatia <[email-masked]>
Date: Mon, 21 Apr 2003 16:05:57 +0530

Hello,
Some vendors seem to allow multiple BGP routes to be installed in the
Loc-RIB for doing load balancing.  I was not able to find any IETF/non IETF
draft/standard which talks about this and am interested in pursuing this.

There are a lot of open issues which need to be resolved.

- Till what stage should the decision process be run for selecting ECMP BGP
routes. Till their IGP costs? Till the point where we compare the router
IDs, etc. We need to come up with a deterministic behavior to decide how
and what BGP routes will be considered equal.
- What should the next hop for these ECMP BGP routes be kept as?
- How to advertise these multiple routes to other BGP peers, etc?
- We need to exercise some caution as the packets here (unlike as in IGPs)
can go outside the AS and therefore cause huge differences in delay/cost
over "n" available paths.
- We need to come out with an interoperable scheme between different
vendors.

This is just a tentative list of issues which we need to ponder into.

Will the IDR community be interested in working over this?

Thanks,
Manav
----
Senior Software Engineer
Samsung India Software Operations
Bangalore - 560 001
+91-80-5550555/6 (1120)

---

From: Robert Raszuk <[email-masked]>
Date: Mon, 21 Apr 2003 15:13:45 +0200

Hi Manav,

> draft/standard which talks about this and am interested in pursuing this.

Before I comment on some your questions posted I think it is worth to
keep in mind that until now most of those implementations you may be
refering to treat multipath as a local to the box feature. As far as
advertisements to i/eBGP peers only best path is advertised as usual.
Hence there is no obvious interoperability problems in mutlipath as
such. 

What may be possibly needed to achive multipath in a few BGP deployment
scenarios is a way to receive more then one path for a given net. In
ipv4 AF those usually will be lost on reflectors. One possible way to
address that issue is presented in: draft-walton-bgp-add-paths-01.txt,
but I think there indeed could be more work needed on this ground. 

> routes. Till their IGP costs? 

Notice that IGP cost is important for IBGP multipath, but for a change
can be With no risk ignored for networks running mpls or any other
flavour of bgp free core.

> - What should the next hop for these ECMP BGP routes be kept as?

As we advertise the best one anyway next hop is not changed. Even
advertising multiple paths (or just multiple next hops for multipaths)
those should remain unchanged. 

> over "n" available paths.

Sure. I am aware that some implementations allow ebgp multipath over any
paths with different AS-PATHs, some may offer ignoring AS_PATHs only by
non-transit providers. In any case this is again local decision.

> - We need to come out with an interoperable scheme between different

If you mean for passing mutliple paths via RRs - I agree. Just for
selection of mutlipath candidates on a given box - I am not sure.
 
R.

---

From: Manav Bhatia <[email-masked]>
Date: Mon, 21 Apr 2003 19:00:17 +0530

Hi Robert,
I have not yet gone through the walton draft and am thus not in a position
to comment on that (will go through it in some time). Meanwhile I have some
comments inlined.

> advertisements to i/eBGP peers only best path is advertised as usual.

What is taken as the *best* path?

Say both the routes have equal AS-path lengths, LPs, etc. So which one is
advertised to the downstream peers? Won't the second advertisement (if both
are sent) be taken as an implict withdraw by the other peers? I thus dont
think its an issue local to the box implementing multi-path.

> Hence there is no obvious interoperability problems in mutlipath as

I see an obvious interoperability issue because the routes which are used
and advertised by this particular router directly affects the other routers
(downstream). Moreover i need a mechanism to formally announce BGP ECMP
routes to the other peers.

OR am i missing something.

> scenarios is a way to receive more then one path for a given net. In

Exactly.

> but I think there indeed could be more work needed on this ground.

I have yet to go through this.

> flavour of bgp free core.

I couldnt get you.

> those should remain unchanged.

Right. But we need to formalize it.

Then there can be some issues when RRs are deployed.

Thanks,
Manav

---

From: Russ White <[email-masked]>
Date: Tue, 22 Apr 2003 13:52:49 -0400 (Eastern Daylight Time)

> advertised to the downstream peers? Won't the second advertisement (if
> both are sent) be taken as an implict withdraw by the other peers? I thus
> dont think its an issue local to the box implementing multi-path.

It's based on the local bestpath decision--the older route, or the better
router id, if you're straight by the spec. What you normally do is to
exclude some portion of the bestpath algorithm, usually just the router id,
to determine "equal cost" paths.

> and advertised by this particular router directly affects the other
> routers (downstream).

A downstream router will have no idea an upstream router is doing
multipath. The advertisements it receives will be the same either way.

:-)

Russ

--
[email-masked] CCIE <>< Grace Alone

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 22 Apr 2003 15:44:50 -0400

> to determine "equal cost" paths.

The last step in the route selection being either router-id based or
first come based is called deterministic or non-deterministic.  The
spec calls for deterministic selection.  If you have a route flap and
the stable route is the least preferred, then deterministic selection
causes a lot of route change.  The obvious answer is to damp the route
flap.  Some providers insist on using the non-deterministic route
selection (first route to arrive is preferred) then wonder why they
occasionally get a few persistant route loops.

The deterministic selection is free of persistant route loops.
Non-deterministic selection is not free of persistant route loops and
that is why it is a MUST in the spec.  Some providers ask for it,
therefore non-deterministic selection is an option on most routers.

> multipath. The advertisements it receives will be the same either way.

Right.

> Russ

Curtis

---

From: Daniel Walton <[email-masked]>
Date: Tue, 22 Apr 2003 16:43:43 -0400 (EDT)

On Tue, 22 Apr 2003, Curtis Villamizar wrote:

> flap.

Changing bestpath based on router-id can cause MED churn in some topologies.

> Some providers insist on using the non-deterministic route selection (first
> route to arrive is preferred) then wonder why they occasionally get a few
> persistant route loops.

Do you have an example of when this will loop?

Daniel

---

From: Pedro Roque Marques <[email-masked]>
Date: Tue, 22 Apr 2003 16:20:12 -0700 (PDT)

Daniel Walton writes:

>> The last step in the route selection being either router-id based
>> or first come based is called deterministic or non-deterministic.
>> The spec calls for deterministic selection.  If you have a route
>> flap and the stable route is the least preferred, then
>> deterministic selection causes a lot of route change.  The obvious
>> answer is to damp the route flap.

>> Some providers insist on using the non-deterministic route

> Do you have an example of when this will loop?

It is not clear to me if you folks are talking about the same thing...

There are two non deterministic steps in cisco's path selection as
publicly documented(1):
a) non-"bgp deterministic med"
b) Step 10 (of the public algorithm) "When both paths are external,
prefer the path that was received first".

The first can only be described as a bug and can indeed lead to
routing loops as it has been found in the field. The latter cannot
cause routing loops as far as i can see. Selection between external
paths can be considered a local matter.

What i'm not clear about is how this rule, as documented, avoids MED
oscillation. Would you mind giving an example ?

(1) http://www.cisco.com/warp/public/459/25.shtml

  Pedro.

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 22 Apr 2003 22:33:46 -0400

In message <[email-masked]>, Dan
> Do you have an example of when this will loop?

You are right.  It is the non-deterministic-med that can loop.

The deterministic next hop only affects where traffic goes in the
normal everything up situation.

Curtis

---

From: Manav Bhatia <[email-masked]>
Date: Wed, 23 Apr 2003 08:37:07 +0530

Russ,

Right.

But the point is that you're still advertising only one best route to your
other peers (based on the age of the route/router ID/etc) while you may
yourself be injecting multiple entries in your FIB. It is possible
(especially in IBGP) to think of a scenario where if you advertise multiple
routes to your peer then it may be in a position to use them for its own
forwarding.

This becomes more of an issue when deploying RRs as they will be connected
to a lot of IBGP peers and it might be recieving multiple "equal cost" BGP
routes (which it might insert in its FIB) while it would be advertising
only the *best* one out and thus depriving the other peers to use those
multiple routes for load balancing.

Regards,
Manav

---

From: Daniel Walton <[email-masked]>
Date: Wed, 23 Apr 2003 11:40:28 -0400 (EDT)

> (1) http://www.cisco.com/warp/public/459/25.shtml

This is from several years ago, before we knew what MED oscillation was:

                       ________________      iBGP       ______________
                       |     RR       |-----------------| non-Client |
                       |  4.0.4.43    |     (IGP : 235) | 4.0.0.106  |
                       |______________|                 |____________|
                              |                               \
                              | iBGP                           \
                              | (IGP : 60)                      \
                              |                               AS : 5646
                       _______|________                       MED: 1000
                       |    Client    |
                       |   4.0.0.10   |
                       |______________|
                         /         \
                  eBGP  /           \ eBGP
                       /             \
                      /               \
                eBGP-1                 eBGP-2
             AS  : 5696              AS  : 5646
             MED : 1000              MED : 10000
             Rid : 209.54.136.8      Rid : 207.112.244.49

1. Client selects eBGP-2 (MED 10000) due to router-id as the bestpath
initially. (MED is not comparable since neighboring-AS are different).

2. Client advertises this path to RR.

3. RR has 2 iBGP paths, one from non-client and another from client. It
selects the one from non-client (MED being lower).

4. RR reflects the bestpath (MED 1000) to client.

5. Client now has 3 paths, 2 eBGP and 1 iBGP. It selects eBGP-1 (MED 1000)
since iBGP path wins over eBGP-2 on MED, eBGP-1 wins over iBGP since we
prefer external over internal.

6. Client now advertises the current bestpath (MED 1000)  to RR.

7. RR which has 2 iBGP paths picks up the path from Client based on the IGP
distance as best. It poisons the route to client.

8. Client which receives the withdraw from RR silently discards it since
the iBGP path was not the current best. We calculate the bestpath only when
current bestpath is withdrawn.

9. The BGP scanner which runs once in a minute (which explains the
periodicity in maeeast router) validates the nexthop and calculates the
bestpath. At this stage, eBGP-2 is picked up as best due to lower
router-id.

10. Client advertises the new bestpath to RR and cycles again...

Daniel

---

From: Pedro Roque Marques <[email-masked]>
Date: Wed, 23 Apr 2003 10:51:38 -0700 (PDT)

Daniel Walton writes:

Daniel,

> periodicity in maeeast router) validates the nexthop and calculates
> the bestpath. At this stage, eBGP-2 is picked up as best due to
> lower router-id.

If i understand your text correctly, it is at this stage that the new
rule of using the "oldest" of the external routes comes into play.

But it would seem to me that you have 50-50 chance that the oldest
route is the same as the lowest router-id, thus causing a loop again.

It seems to me that introducing this non-deterministic step wouldn't
fix the MED oscillation problem... it just makes it non-deterministic
when the problem will occur. Which is not necessarly a feature...

regards,
  Pedro.

---

From: Daniel Walton <[email-masked]>
Date: Wed, 23 Apr 2003 16:24:54 -0400 (EDT)

> route is the same as the lowest router-id, thus causing a loop again.

MED oscillation happens in this topology when we change our bestpath based only
on a difference in router-id.  It is easy to stop the oscillation here by
preferring the 'oldest external' instead of making a bestpath change over a
router-id change which is fairly arbitrary.  If only the other variations of MED
churn where this easy to solve :)

There is a knob to enforce the router-id comparison step if the user desires.

Daniel

---

From: Pedro Roque Marques <[email-masked]>
Date: Wed, 23 Apr 2003 14:10:47 -0700 (PDT)

Daniel Walton writes:

Daniel,
I don't think your message really addresses my question.

> MED oscillation happens in this topology when we change our bestpath
> based only on a difference in router-id.

That is not acurate... MED oscillation happens when you have a
circular dependency. The "oldest external" rule will, in 50% of the
cases, on the previous example yield the same result as if you would
select these paths based router-id. i.e. whenever the 'oldest
external' is the lowest router-id the result is the exact same.

Thus i don't think you can claim that this solves the problem that you
mention. Although you may claim to make it less likely... at the
expense of making it even less predictable.

>  It is easy to stop the
> oscillation here by preferring the 'oldest external' instead of
> making a bestpath change over a router-id change which is fairly
> arbitrary.  If only the other variations of MED churn where this
> easy to solve :)

I don't understand how the 'oldest external' rule as currently
documented by cisco stops oscillation.

It would be great if you could provide more details to substantiate
this claim.

> There is a knob to enforce the router-id comparison step if the user

We are discussing what the 'oldest external' rule buys you and
potential disadvantages. I'm trying to understand the
implications...

thanks,
  Pedro.

---

From: Daniel Walton <[email-masked]>
Date: Thu, 24 Apr 2003 09:52:53 -0400 (EDT)

Assumptions:
- * indicates the bestpath
- deterministic-med is configured

Step 1 - init state
                AS      MED     E/I     IGP     ID
                --      ---     ---     ---     --
Client          5696    1000    E       0       209.54.136.8
                *5646   10000   E       0       207.112.244.49
RR              -       -       -       -       -
non-Client      *5646   1000    E       0       -

Step 2 - Client and non-Client advertise bestpaths to RR
                AS      MED     E/I     IGP     ID
                --      ---     ---     ---     --
Client          5696    1000    E       0       209.54.136.8
                *5646   10000   E       0       207.112.244.49
RR              5646    10000   I       60      207.112.244.49
                *5646   1000    I       235     -
non-Client      *5646   1000    E       0       -

Step 3 - RR advertises bestpath to Client
       - Client selects eBGP-1 path as best
                AS      MED     E/I     IGP     ID
                --      ---     ---     ---     --
Client          5646    1000    I       295     -
                5646    10000   E       0       207.112.244.49
                *5696   1000    E       0       209.54.136.8
RR              5646    10000   I       60      207.112.244.49
                *5646   1000    I       235     -
non-Client      *5646   1000    E       0       -

Step 4 - RR selects eBGP-1 path as best
                AS      MED     E/I     IGP     ID
                --      ---     ---     ---     --
Client          5646    1000    I       295     -
                5646    10000   E       0       207.112.244.49
                *5696   1000    E       0       209.54.136.8
RR              *5696   1000    I       60      209.54.136.8
                5646    1000    I       235     -
non-Client      *5646   1000    E       0       -

Step 5 - RR withdraws his previous advertisement of 5646, MED 1000
       - Client is left with two external paths.  If he changes bestpath
         based on router-id then we will be back to step 2 (RR will know
         about eBGP-2 from Client and 5646, MED 1000 from non-client) and
         we are in MED oscillation.  If he prefers to keep his
         current bestpath then we do not oscillate.
                AS      MED     E/I     IGP     ID
                --      ---     ---     ---     --
Client          5646    10000   E       0       207.112.244.49
                5696    1000    E       0       209.54.136.8
RR              *5696   1000    I       60      209.54.136.8
                5646    1000    I       235     -
non-Client      *5646   1000    E       0       -

One point of confusion here is that the docs say we prefer the older external
path. A more accurate description is that we won't make the bestpath change if
we are comparing two external paths and make it to the router-id step in the
decision process.

Call it non-deterministic if you want but it solves MED churn in this scenario
and I have never heard a customer complain.  If they decide to start
complaining, we have a knob they can turn to enforce the router-id check.

Daniel