Subject: draft-chen-rr-oscillation-reduce-00.txt

From: Enke Chen <[email-masked]>
Date: Wed, 05 Jun 2002 07:28:17 -0700

Hi, folks:
Two drafts are posted:

   o draft-chen-rr-oscillation-reduce-00.txt
   o draft-chen-confed-oscillation-reduce-00.txt

A simple proposal for Route Reflection and one for Confederration
are presented for presistent route oscillation reduction. Based
on our computation, they resolve all the persisitent route oscillation
cases documented.

If you have a persistent route oscillatin case that can not be resolved
by these proposals, we will appreciate greatly if you let us know.

Comments?

Regards,   -- Enke

------- Forwarded Message

To: IETF-Announce: ;
From: [email-masked]
Reply-To: [email-masked]
Subject: I-D ACTION:draft-chen-rr-oscillation-reduce-00.txt
Date: Wed, 05 Jun 2002 07:33:23 -0400
Sender: [email-masked]

--NextPart

A New Internet-Draft is available from the on-line Internet-Drafts directories.

	Title		: BGP Route Oscillation Reduction with Route Reflection
	Author(s)	: E. Chen
	Filename	: draft-chen-rr-oscillation-reduce-00.txt
	Pages		: 4
	Date		: 04-Jun-02
	
This document proposes a simple revision to Route Reflection that
allows a Route Reflector to advertise the best path from its clients
to other clusters when the overall best path for the RR differs. The
availability of the routing information to other clusters helps
achieve stable route selection, and moves route reflection closer to
IBGP full-mesh equivalence in terms of routing information. It has
been shown that the proposed mechanism eliminates a number of
persistent route oscillation cases involving Route Reflection.

A URL for this Internet-Draft is:
http://www.ietf.org/internet-drafts/draft-chen-rr-oscillation-reduce-00.txt

------- End of Forwarded Message

---

From: Gordon Wilfong <[email-masked]>
Date: Wed, 05 Jun 2002 16:13:40 -0400

Unfortunately, this method can fail to 
prevent persistent oscillations.

Consider the example below that appears in a work
in progress by Tim Griffin and Gordon Wilfong.
There is a single cluster with one route reflector [RR1] and two
client routers [C1] and [C2].  The client routers
get routes from outside their AS from [AS1] and
[AS2].  The numbers in parentheses represent the
MED values.  The unadorned numbers on the links between
[RR1] and its clients are the IGP metric values.
The unadorned numbers on the links from the client [C1]
to the two outside ASes represent [C1]'s preference
according to BGP tie breaking (with lower number representing
the more preferred route).
The example has the property that it suffers from persistent
route oscillations.  However the method discussed in
draft-chen-rr-oscillation-reduce-00.txt will not prevent this
oscillation since the route reflector's best route is always
a client's route and so the method's behavior will be unchanged
from unmodified I-BGP.

                       4
            [RR1] *************
              *               *
           1  *               *
              *               *
              *               *
              *               *
            [C1]            [C2]
              ***             *
            2 *   *  1        *
              *     *         *
          (2) *   (1) *       * (0)
              *         *     *
           [AS1]          **[AS2]

- Gordon

---

From: Enke Chen <[email-masked]>
Date: Wed, 05 Jun 2002 14:42:13 -0700

Hi, Gordon:
As you correctly pointed out:

> However the method discussed in draft-chen-rr-oscillation-reduce-00.txt
> will not prevent this oscillation since the route reflector's best route
> is always a client's route and so the method's behavior will be unchanged
> from unmodified I-BGP.
> 
The proposal presented in draft-chen-rr-oscillation-reduce-00.txt does
not impact this case.

However, a couple comments on this case:

  o In general a route oscillation within a cluster can be resolved
    easily by full-mesh the clients within the cluster, which does not
    have a scalability issue, and is a better operational model. This
    is one way to resolve this case.

  o The code has been deployment for almost 3 years that (by default)
    avoid the switch between two EBGP paths when the route selection
    goes to the "random" steps (e.g., router-id comparison). As a result,
    C1 would converge to AS1 as the best. This is another way to resolve
    this case.

    Now you know the real reason why that step was introduced in the
    route selection :-)

Regards,  -- Enke    

> Message-ID: <[email-masked]>
> Date: Wed, 05 Jun 2002 16:13:40 -0400
> From: Gordon Wilfong <[email-masked]>
> To: Enke Chen <[email-masked]>
> Cc: [email-masked]
> Subject: Re: draft-chen-rr-oscillation-reduce-00.txt
> References: <[email-masked]>
>

---

From: Pedro Roque Marques <[email-masked]>
Date: Wed, 5 Jun 2002 15:59:20 -0700 (PDT)

Enke Chen writes:

> Hi, Gordon: As you correctly pointed out:

>   o The code has been deployment for almost 3 years that (by
> default) avoid the switch between two EBGP paths when the route
> selection goes to the "random" steps (e.g., router-id
> comparison). As a result, C1 would converge to AS1 as the best. This
> is another way to resolve this case.

>     Now you know the real reason why that step was introduced in the

Avoiding the switch between paths doesn't avoid 'random' steps. It is
itself a 'random' step in which the factor is arrival time of the
route making it random and non-deterministic.

If there are cases where this seems a good idea there is an equal
number of cases where it makes things worse.

I was under the impression that the "real reason" is much more related
to certain implementation choices a vendor we used to work for has in
their implementation that make it really hard for said implementation
to suppress duplicate updates ;-)

regards,
  Pedro.

---

From: Enke Chen <[email-masked]>
Date: Wed, 05 Jun 2002 16:14:54 -0700

> Date: Wed, 5 Jun 2002 15:59:20 -0700 (PDT)
> Message-Id: <[email-masked]>
> From: Pedro Roque Marques <[email-masked]>
> Cc: Gordon Wilfong <[email-masked]>, [email-masked]
> In-Reply-To: <[email-masked]>
> 
> Enke Chen writes:
> 

Let me clarify: I did not mean the step is "random" (sorry). I mean
the result of the step is random. For example, a BGP speaker does not
have any control over what router-id an EBGP peer will use (or change).
In that case, it really does not matter to the speaker which EBGP path
to choose when the route selection goes all the way to comparing
router-id.

> number of cases where it makes things worse.

Is there a specific example that avoid EBGP switch (based on router-id)
makes things worse?

> to suppress duplicate updates ;-)

No, it was not the duplicate update. It was a real churn (involving RR)
seen on one of the large ISP networks in the US three years ago. Srihari
was the one that logged into the routers and first identified the churn.

Regards,  -- Enke

---

From: Pedro Roque Marques <[email-masked]>
Date: Wed, 5 Jun 2002 16:30:59 -0700 (PDT)

Enke Chen writes:

>> Date: Wed, 5 Jun 2002 15:59:20 -0700 (PDT) Message-Id:
>> <[email-masked]> From: Pedro Roque
>> Marques <[email-masked]> To: Enke Chen <[email-masked]> Cc:
>> Gordon Wilfong <[email-masked]>, [email-masked] Subject:
>> Re: draft-chen-rr-oscillation-reduce-00.txt In-Reply-To:
>> <[email-masked]>
>> 
>> Enke Chen writes:
>> 
>> > o The code has been deployment for almost 3 years that (by >
>> default) avoid the switch between two EBGP paths when the route >
>> selection goes to the "random" steps (e.g., router-id >
>> comparison). As a result, C1 would converge to AS1 as the
>> best. This > is another way to resolve this case.
>> 
>> Avoiding the switch between paths doesn't avoid 'random' steps. It
>> is itself a 'random' step in which the factor is arrival time of
>> the route making it random and non-deterministic.

> the result of the step is random. For example, a BGP speaker does
> not have any control over what router-id an EBGP peer will use (or
> change).  In that case, it really does not matter to the speaker
> which EBGP path to choose when the route selection goes all the way
> to comparing router-id.

It matters that the router-id test is deterministic, i.e. predictable,
while arrival order isn't.

> Is there a specific example that avoid EBGP switch (based on
> router-id) makes things worse?

The main problem, imho, is that given a set of offered paths you
cannot predict the behaviour, i.e. which path will be selected since
it is not possible to predict the arrival order of the paths in a
system. Personally i think that is a significant operational problem
by itself.

In this discussion, for instance, people attempt to given a set of
paths predict the behaviour to check if it is stable or not and assume
a deterministic behaviour in order to do so. In certain
implementations that assumption is actually not correct.

Although the IDR WG typically attempts to have a 'pratical'
prespective on things, "theoretical" models are important in that they
allow you to understand pratical behaviour.

Let me put things in another way... even if i can't from the top of my
head present you an example of what problems it causes, it doesn't
mean that one can assert that it doesn't introduce new
issues. i.e. lack of negative proof doesn't prove something.

  Pedro.

---

From: Gordon Wilfong <[email-masked]>
Date: Thu, 06 Jun 2002 08:03:17 -0400

Hi Pedro,

I completely agree with your statement that theoretical models
are essential in permitting a thorough understanding of
the behavior of systems.

I also agree with you when you say that nondeterministic behavior
is a significant operational problem in that it makes reasoning
about your network, and hence debugging your network, difficult.

One aspect of nondeterministic behavior is something we called
"transient oscillations" in our sigcomm 2002 paper.  These
are instances where extreme timing coincidences could cause
route oscillations but such coincidences are
very unlikely.  The more
significant aspect is that they indicate that there are more
than one stable routing states that the system could fall into.
That is, the behavior, while convergent, is nondeterministic.

So for instance, the following example has two solutions.  Given
very unlikely timing coincidences it could exhibit route oscillations.

.................................                             
            .          AS0                  .                          
            .                              
.                             
            .                               .                            
            .   [R1]***************[R2]    
.                             
            .    * *              *  *     
.                             
            .  2 *  *1       1  *    *2    
.                             
            .....*....*  .....*
.....*.......                             
                 *       *  *       
*                                    
                 *        * *       
*                                    
             (0) *      *    *      
*                                    
                 *    *(1)  (1) *    *
(0)                                
                 *  *             * 
*                                    
                [AS1]              [AS2] 
 
This example comes from a paper Tim Griffin and I are working
on.  The numbers in parens are the MED values and the unadorned
numbers indicate BGP tie breaking rules (the lower the number
the more preferred the route).  R1 and R2 are just
two (fully-meshed) routers, not necessarily route reflectors
in AS0.  So one solution is where
R1 chooses to go through AS1 and R2 chooses to go through AS2.
Another solution is where R1 goes through AS2 and R2 goes through
AS1.  It all depends on timing which routing gets established.
And the 2nd solution actually has the property that it violates
the semantics of MEDs in that both routers end up with routes
with higher MED values than other available routes through
the same neighboring AS. 

Since the modification to IBGP that we describe in                
draft-wilfong-IBGP-oscillations-00.txt is guaranteed
to eliminate such transient oscillations (as well as
persistent oscillations), it guarantees not only will
any system converge, but it will converge deterministically
to the same solution irrespective of timing issues.
(The solution our method would result in would be the
first one with each Ri choosing the route through ASi.)

- Gordon

---

From: Enke Chen <[email-masked]>
Date: Thu, 06 Jun 2002 09:24:14 -0700

Hi, Gordon:

As I posted in the previous message, the local speaker does not have
any control over the router-id allocation of the remote speaker. In
addition, the router-id of the remote speaker can change without the
prior knowledge of the local speaker. In that sense, the two external
paths are equally good for the local speaker when the router-id has to
be compared in route selection. We obvious are of different opinions on
how big an issue the "non-deterministic behavior" (which one to select)
is for a customer. Our opinions may not matter that much as compared
to customers'.

As we seem to be getting philosophical in the discussion thread, let me
add some of my own. A "zero-cost" optimization is the the best thing,
however, most of the time that is not possible. The next best thing
is the "near-zero-cost" optimization, which IMO the approach of
avoiding EBGP path switch (base on router-id) achieves.

-- Enke

> Message-ID: <[email-masked]>
> Date: Thu, 06 Jun 2002 08:03:17 -0400
> To: Pedro Roque Marques <[email-masked]>
> Cc: Enke Chen <[email-masked]>, [email-masked]
> References: <[email-masked]>
> 		<[email-masked]>
> 		<[email-masked]> <[email-masked]>
> 
> Hi Pedro,
>

---

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

Enke,
A few questions/comments on your proposal...

The gist of it is to advertise 'the best external' (i.e. route from
rr-clients) to the rest of the mesh when the best path is internal
(i.e. received from a ibgp mesh router).

1) Why do you limit this procedure to RRs/Confeds... ?

2) Advertising the 'best external' route as always had the issue of
traffic loops (i believe the reason it hasn't been implemented as
specified in 1771 originally). You don't seem to address this in your
draft... do you believe it is not relevant... or is there some other
solution to this problem...

To be more specific, if you have rtrs A, B, such that B has the best
path at t0, and A a valid external path, when at t1 B's external path
gets withrawn, traffic is almost guaranteed to loop until B's
advertisement reaches A. This can be potentially exacerbated by
mechanisms such as min advertisement interval.

Whereas today such traffic would be blackholed by B... while it is
true that current routers are not as susceptible to rollover and die
when presented with looping traffic as opposed to software forwarding
based boxes of 5+ years ago it is likely that the resulting link
congestion is still a relevant factor.... comments ?

  Pedro.

---

From: Enke Chen <[email-masked]>
Date: Fri, 07 Jun 2002 16:11:42 -0700

Hi, Pedro:
Thanks for your comments on the proposal.

> Date: Thu, 6 Jun 2002 11:44:16 -0700 (PDT)
> Message-Id: <[email-masked]>
> To: [email-masked]
> Subject: rr-oscillation-reduce
> 
> Enke,

Always advertising "the external best" by all border routers can cause
significant increase in the number of paths (and memory usage) in a
network. The proposal in draft-chen-rr-oscillation-reduce is trying to
reduce/eliminate most the route oscillations by advertising the minimal
set of additional routing information (that is, at most one path).
By "at most one path" I mean that a RR may not advertise a path to other
clusters even when clients have external paths. For example, after the RR
advertises the overall best (from another cluster) to a client, the client
would withdraw its advertisement to the RR if the client does not select
its external path as the best. If we allowed the client to always advertise
"the best external" path, the client would not withdraw. Then the RR and
the rest of the network would be stuck with the additional path that are
not useful in route selection. Please note that the additional path would
not be present in the netowrk even in the case of full IBGP mesh (with
advertising only the best).

> solution to this problem...

I do not know that part of the implementation history. I can only
speculate that the concern of additional memory and implementation
simplicity/complexity may have played a larger role in the decision.

> congestion is still a relevant factor.... comments ?

Your comparison makes a lot of sense. With the proposal a RR advertises
the cleints' best that survives through the route selection (see comment
on 1)). It follows the current practice/spirit of advertising the best
path. So I do not expect the convergence time to deviate much from
today's.

-- Enke

---

From: Pedro Roque Marques <[email-masked]>
Date: Fri, 7 Jun 2002 17:01:45 -0700 (PDT)

Enke Chen writes:

> Hi, Pedro: Thanks for your comments on the proposal.

>> Date: Thu, 6 Jun 2002 11:44:16 -0700 (PDT) Message-Id:
>> <[email-masked]> From: Pedro Roque
>> Marques <[email-masked]> To: [email-masked] Cc: [email-masked]
>> Enke, A few questions/comments on your proposal...
>> 

> Always advertising "the external best" by all border routers can
> cause significant increase in the number of paths (and memory usage)
> in a network. The proposal in draft-chen-rr-oscillation-reduce is
> trying to reduce/eliminate most the route oscillations by
> advertising the minimal set of additional routing information (that
> is, at most one path).  By "at most one path" I mean that a RR may
> not advertise a path to other clusters even when clients have
> external paths. For example, after the RR advertises the overall
> best (from another cluster) to a client, the client would withdraw
> its advertisement to the RR if the client does not select its
> external path as the best. If we allowed the client to always
> advertise "the best external" path, the client would not
> withdraw. Then the RR and the rest of the network would be stuck
> with the additional path that are not useful in route
> selection. Please note that the additional path would not be present
> in the netowrk even in the case of full IBGP mesh (with advertising
> only the best).

I'm missing something here...

The draft says that the proposed modification is:

   "When the client best path for a RR exists, and the overall
      best path for the RR is from a non-client IBGP peer, the RR
      may advertise the client best path to all non-client IBGP
      peers."

It seems to me that by your own admission this is a no op, since as
you correctly point out the client will subsequently withrawn it's
best path.

>>  2) Advertising the 'best external' route as always had the issue
>> of traffic loops (i believe the reason it hasn't been implemented
>> as specified in 1771 originally). You don't seem to address this in
>> your draft... do you believe it is not relevant... or is there some
>> other solution to this problem...

>> true that current routers are not as susceptible to rollover and
>> die when presented with looping traffic as opposed to software
>> forwarding based boxes of 5+ years ago it is likely that the
>> resulting link congestion is still a relevant factor.... comments ?

> So I do not expect the
> convergence time to deviate much from today's.

Yes, i believe that the convergence time will be the same. However the
fundamental difference i'm point out is that during the convergence
time traffic will loop instead of being blackholed as it is today.

That would apear to be an implication that is necessary to consider.

  Pedro.

---

From: Enke Chen <[email-masked]>
Date: Fri, 07 Jun 2002 17:25:03 -0700

> Date: Fri, 7 Jun 2002 17:01:45 -0700 (PDT)
> Message-Id: <[email-masked]>
> Subject: Re: rr-oscillation-reduce 
> In-Reply-To: <[email-masked]>
> 	<[email-masked]>
> 	<[email-masked]>
> X-Mailer: VM 6.34 under 19.16 "Lille" XEmacs Lucid
> 
> Enke Chen writes:
> 

The text in the draft talks about a RR (toward other clusters), and
it does not suggest any change to a client. So a client will withdraw
its best path only if its external best does not survive through the
route selection. It will not withdraw if its external path remains
as the best.

> That would apear to be an implication that is necessary to consider.

Understood. However, it seems to me the implication on the traffic
behavior (during routing re-converging) should be no different from
doing closest-exit routing in which case multiple alternate paths are
present. As I understand, quite a few large providers have been doing
closest-exit routing for years.

-- Enke

---

From: Pedro Roque Marques <[email-masked]>
Date: Fri, 7 Jun 2002 17:40:03 -0700 (PDT)

Enke Chen writes:

> it does not suggest any change to a client. So a client will
> withdraw its best path only if its external best does not survive
> through the route selection. It will not withdraw if its external
> path remains as the best.

Ok... would you consider including a description of why this is
necessary and/or sufficient to avoid oscilation or certain types of
oscillation.

> doing closest-exit routing in which case multiple alternate paths
> are present. As I understand, quite a few large providers have been
> doing closest-exit routing for years.

I believe i disagree:

	If you have RRa and RRb, where RRa is advertising a route that
it is not installed in it's routing table, it is actually prefering
RRb route. When RRb (or the cluster) looses it's best external path it
may proceed to forward traffic to RRa which will then loop it back to
RRb.

This regardless if you are doing closest-exit or not... btw: if you
are doing pure closest-exit this entire discussion is irrelevant,
correct ?

  Pedro.

---

From: Enke Chen <[email-masked]>
Date: Fri, 07 Jun 2002 18:06:29 -0700

> Date: Fri, 7 Jun 2002 17:40:03 -0700 (PDT)
> Message-Id: <[email-masked]>
> In-Reply-To: <[email-masked]>
> 	<[email-masked]>
> 	<[email-masked]>
> 
> Enke Chen writes:
> 

Sure.

> may proceed to forward traffic to RRa which will then loop it back to

Ok.

> are doing pure closest-exit this entire discussion is irrelevant,

Right. As I remember, the providers typically only does closest-exit
routing toward other providers, and they typically honors MEDs from
their customers. So it was (and still is?) a mixed routing.

-- Enke