Subject: I-BGP Oscillations

From: Anindya Basu <[email-masked]>
Date: Thu, 06 Jun 2002 15:13:17 -0400

I have been following the responses to various proposals for eliminating
I-BGP oscillations with some interest and it appears that there are
roughly two main approaches.

1. Try to solve the problem using a solution that fixes the current
manifestation of the problem, without changing the protocol too much.
draft-walton and draft-chen fall in this category. The main advantage to
both these solutions is that they do not involve major changes to the
protocol and they have reasonably good scaling properties. On the other
hand, such solutions may not address all possible manifestations of the
oscillation problem, as evidenced by some of the counter examples that
Gordon has suggested. One way to resolve this is to restrict the kind of
router configurations that are permitted (as suggested by Chen, as well
as Scudder, under the class of real configurations). 

This approach has two drawbacks: 
(1) It may make the configuration process too restrictive, i.e.,
disallow
many configurations that may be safe.
(2) Fixing the current manifestation of the problem with a solution
that appears to make it go away may be risky. It could produce other
problems that did not manifest themselves before, as well as not address
the entire existing class of problems. Obviously, as newer problems
manifest themselves, further and further revisions to the protocol need
to be made.

2. The second approach is to actually analyze the protocol and figure
out which feature(s) that are inherent in the protocol are causing
oscillations. Then redesign the protocol in a manner that is provably
correct under all circumstances. This approach obviously addresses the
two drawbacks outlined above. draft-wilfong and Pedro have been arguing
for such an approach (in my opinion). 

However, this approach has one distinct disadvantage --- as pointed
out by many of you (notably, John Scudder and Ben Abarbanel), there 
are some scalability issues that need to be addressed. The proposal 
in draft-wilfong (as well as in draft-walton) advocate sending some 
extra information to suppress oscillations. However, it is not clear 
how much extra information may need to get sent out (especially in 
the case of draft-wilfong). Given the memory constraints for today's 
routers, it may be hard to store all these extra routes in memory.

One way to address this issue would be to *only* send out extra routes
when necessary. In other words, if an oscillation involving I-BGP routes
is detected, extra information for only that route could be sent out.
This way, routers behave normally as usual, and when a particular route
(or set of routes) begin to flap, the extra information corresponding to
those routes could be computed and sent out. Thus, extra storage is
*only* required when something bad happens.

Hopefully, this provides a reasonable solution to the scalability
problem. 

Thanks,
-Anindya

---

From: f b shepherd <[email-masked]>
Date: Thu, 06 Jun 2002 14:24:38 -0400

Content-Length: 1650

Anindya:
The solution in draft-wilfong-ibgp-oscillations-00.txt is to merely dump all

the routes that were not resolved by BGP Route Selection Criteria (BRSC) to
all 
its peers, is a major disaster to the network. We are already pushing the
limits 
of capacities in routers with 200,000 routes, now to solve a potential route
oscillations problem, you dump all unresolved routes to all the peers. What
will that do to the routing tables for routers not able to handle such a
massive increase of routes?

==> Correct, as you put it, we dump a lot of extra routes.
    This was the only  approach we could see at that time to
    a) allow MED to maintain some semblance of its intended meaning
    and b) eliminate any route oscillations (and nondeterminism in the
     adopted routing).

    In general, we have not peformed any analysis on the actual
    number of routes which would be passed. Presumably, quite
    often it  could still only be the best route passed on by a RR.

What if some routers are situated in the topology such that they will never
get 
into route oscillations, why should they see a ton of useless routes coming
at 
them from routers that are potentially prone to form or pass oscillating
routes?

==> Good point. 

I also thought, one fundamental rule of BGP is to "Only propagate BGP routes
that  the router actually uses in its forwarding plain, meaning the route
made it to
its local-RIB".  Are you saying we should pass BRSC unresolved routes to the
Local-RIB with your proposal since you are propagating them to the peers? 

==> It seems to me impossible to adhere to only propogating best-path and yet
    to eliminate all oscillations which were considering (or maybe even to 
    only eleiminate types I and II churn). 
    At least not without some other radical change to the protocol.

    As you mentioned above, the impact on router capacities may
    make the extra route dumping infeasible. As John also said, scalability
    is a key issue. As I had previously said - take our work then as
    hinting that 
    a "total solution" to oscillations may actually require 
    such a larger collection
    of passed messages.

    Regards - and apologies for my indentations.
    Bruce

Ben

---

From: Pedro Roque Marques <[email-masked]>
Date: Thu, 6 Jun 2002 12:27:46 -0700 (PDT)

Anindya Basu writes:

> One way to address this issue would be to *only* send out extra
> routes when necessary. In other words, if an oscillation involving
> I-BGP routes is detected, extra information for only that route
> could be sent out.

If we come up with a decent detection mechanism it would be so much
simpler just to reduce the rate of oscilation.

Regardless a decent detection mechanism needs to be proposed...

'Decency' criteria includes state that one needs to hold, etc...

In other words, the ammount of state required to detect such events
shouldn't be greater than the state necessary to advertise the best
external MED winner paths from all mesh participants.

Note that the answer 'ibgp dampening' that is certain to pop up in
peoples minds by association is a bit misleading. When you start
thinking about it is quite a different beast... it is not suficient to
say that you just apply the procedures applied to ebgp dampening since
the problem is quite different.

  Pedro.

---

From: Jeffrey Haas <[email-masked]>
Date: Thu, 6 Jun 2002 16:14:12 -0400

On Thu, Jun 06, 2002 at 12:18:30PM -0700, Pedro Roque Marques wrote:
> Can you elaborate please... i don't quite get the scenario where
> different behaviour is introduced.

The simplest one I can think of is that when "always-compare-med" is
on, if you have some ISP that is injecting better MEDs than yours,
it removes your routes from being used even when they should be
used as the closest exit router.

Example:

  Ra     Rb
   *-----*

Routers a and b are AS-BR's and iBGP between each other.
ISPs 1 and 2 peer at Ra and Rb respectively.

Some destination, D is injected by both.  ISP-1 injects it with a MED of
2 and ISP-2 injects it with an MED of 1.

With always-compare-med, if the LocalPref, AS_Path length, and origin
are the same, then ISP-2's route will win in both routers because
ISP-1's route is suppressed.

Without always-compare-med, each ISP wins at the their respective BR.

If you add a Rc that peers with Ra, Rb (fully-meshed), then:
With always-compare-med:
   ISP-1's D is suppressed and never gets used.
Without always-compare-med:
   Rc has the choice of ISP-1's and ISP-2's D and will continue through
   route selection, choosing IGP distance or routerid.

Without taking this to the more complicated cases, the argument that
the operational community makes is that "always-compare-med" is a form
of denial of service.

Of course, I don't speak for the operational community - I haven't had
a login on a router that actually affects customer's routing for a few
years. :-)

> Only for prefixes that they both announce... i don't have access to
> meaningful data myself but a point made several times in this
> discussion is that the number of prefixes which end up with a decision
> with same length as-paths from different neighbor ASes where between
> the same AS you pick best MED and between different AS you pick best
> IGP, etc... is said to be quite small.

For particular topologies.

It is possible that many ISPs just don't implement topologies
that are affected by these issues.

-- 
Jeff Haas 
NextHop Technologies

---

From: Anindya Basu <[email-masked]>
Date: Thu, 06 Jun 2002 15:37:09 -0400

> the problem is quite different.

could you elucidate further and explain how detection of the problem is
different for i-bgp and e-bgp? also, i was not exactly suggesting a
dampening mechanism (as they are used today). i was arguing for a
mechanism which would be triggered whenever frequent announcements
followed by withdrawals of the same i-bgp route is observed. this
mechanism would then start sending out extra routes.

-anindya

---

From: Jeffrey Haas <[email-masked]>
Date: Thu, 6 Jun 2002 15:00:51 -0400

On Thu, Jun 06, 2002 at 11:55:39AM -0700, Pedro Roque Marques wrote:
> One possible solution is to mandate 'always-compare-med' behaviour
> which will make paths have a global ordering. I remember there was
> strong reaction against this from the operational folks but i'm not
> quite sure what the arguments where (would apreciate if somebody could
> refresh my memory).

With the current behavior, a given AS may inject backup paths to
their upstream and have the expected behavior happen so long as
it gets to the MED portion of tie-breaking: the routes with the 
worse meds are suppressed.

With always-compare-med, all AS peers must adhere to a common policy
of what MEDs they will use for a given prefix.  While theoretically
possible, making more than one ISP agree about anything is hard to 
scale. :-)

> Or we can attempt to specify a different attribute/mechanism that
> achieves the desired effects.

If I recall previous discussions, the amount of state that would need
to be flooded throughout the AS was only a little less than flooding
the relevant full routing instances.

-- 
Jeff Haas 
NextHop Technologies

---

From: Pedro Roque Marques <[email-masked]>
Date: Thu, 6 Jun 2002 11:55:39 -0700 (PDT)

f b shepherd writes:

> ==> It seems to me impossible to adhere to only propogating
> best-path and yet to eliminate all oscillations which were
> considering (or maybe even to only eleiminate types I and II churn).

There is a simple answer, which is to address the current MED
behaviour. MEDs as current specified make it so that there isn't
possible to establish a global ordering between BGP paths. The
protocol when originally designed implicit required such property.

Given a global ordering of paths within an ibgp mesh no persistent
osciallation will occur and the protocol as originally specified will
be stable.

In order to achieve this, of course, one needs to encounter an
solution to the problem that MEDs are supposed to solve.

  Pedro.

---

From: Pedro Roque Marques <[email-masked]>
Date: Thu, 6 Jun 2002 12:18:30 -0700 (PDT)

Jeffrey Haas writes:

>>...

> their upstream and have the expected behavior happen so long as it
> gets to the MED portion of tie-breaking: the routes with the worse
> meds are suppressed.

> of what MEDs they will use for a given prefix.

Still probably unpractical to coordinate, i admit.

>  While theoretically

Don't forget that the same thing is true for any proposal that changes
the number of paths present on their systems... or any behaviour
change. :-)

> If I recall previous discussions, the amount of state that would
> need to be flooded throughout the AS was only a little less than
> flooding the relevant full routing instances.

There are 2 different type of problems that i'm aware of...

1) The current behaviour of MEDs make it so that all the routers in an
ibgp choose one of the paths of a neighbor AS over another reducing
the number of paths in the system. If you discard MEDs at your borders
the number of paths injected in the iBGP greatly increases (to the
number of peering points) as all the mesh members start prefering
their own external path and advertising them into the mesh.

2) You need to convey the information itself of which of the exit
points is preferable from a point of view of your neighbor AS.

MHO is that it is possible to find solutions for this issues.

  Pedro.