Subject: [Idr] draft-chen-bgp-avoid-transition-01.txt

From: Enke Chen <[email-masked]>
Date: Wed, 28 Apr 2004 10:13:29 -0700

Hi, Yakov and Sue:

I would like to request that the draft <draft-chen-bgp-avoid-transition-01.txt>
be accepted as an IDR WG document. The draft was presented previosuly at an
IDR meeting. The algorithm described in the draft has been deployed for several
years.

Thanks. -- Enke

------- Forwarded Message

Message-Id: <[email-masked]>
To: IETF-Announce: ;
From: [email-masked]
Reply-To: [email-masked]
Subject: I-D ACTION:draft-chen-bgp-avoid-transition-01.txt
Date: Tue, 20 Jan 2004 10:04:35 -0500

- --NextPart

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

	Title		: Avoid BGP Best Path Transition from One External to Another
	Author(s)	: E. Chen, S. Sangli
	Filename	: draft-chen-bgp-avoid-transition-01.txt
	Pages		: 5
	Date		: 2004-1-19
	
In this document we propose an algorithm that would help improve the
overall network stability by avoiding BGP best path transition from
one external to another (under certain conditions)

A URL for this Internet-Draft is:
http://www.ietf.org/internet-drafts/draft-chen-bgp-avoid-transition-01.txt

------- End of Forwarded Message

_______________________________________________
Idr mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/idr

---

From: Pedro Roque Marques <[email-masked]>
Date: Wed, 28 Apr 2004 15:41:17 -0700 (PDT)

Enke Chen writes:

> Hi, Yakov and Sue: I would like to request that the draft
> <draft-chen-bgp-avoid-transition-01.txt> be accepted as an IDR WG
> document. The draft was presented previosuly at an IDR meeting. The
> algorithm described in the draft has been deployed for several
> years.

my turn to cheer: i believe this should be a wg document.

  Pedro.

---

From: Thomas Barron <[email-masked]>
Date: Wed, 28 Apr 2004 14:38:30 -0500

> ------- End of Forwarded Message

Hi Enke,

    Attached is an email I sent to IDR that discusses some issues around  
your draft.  I don't think I have seen a reply.

   I will add now that since that note I've discussed and thought a bit  
more about your argument in 5.2, and I think it is quite clear (and is  
indeed the received opinion nowadays) that the essential ingredient in  
these route-oscillation problems is the interaction of Route Reflectors  
and IGP costs.  Using sufficiently high IGP costs between clusters will  
suffice to stop the churn both in your scenario and in other scenarios  
that don't involve router-id.  Indeed, in your scenario if by chance  
the times of arrival correspond in the same order to that determined by  
the router-ids the churn is not avoided by your algorithm either (the  
proof is tedious, but intuitively: start the scenario with the same  
ranking of tie-breakers, just use time-of-arrival instead of router-id;  
then realize that this order gets preserved as the oscillation proceeds  
because the repeatedly advertised-and-withdrawn route will always be  
"newest" and correspond to the largest router id in the original  
scenario.)

   But as I say in the attached, my argument is really with section 5.2,  
not with your overall proposal.  There are implementations that provide  
a knob to do just what you are documenting and I agree that the BGP  
spec should provide for this option.

    Best regards,

   Tom Barron

---

From: Pedro Roque Marques <[email-masked]>
Date: Wed, 28 Apr 2004 15:41:17 -0700 (PDT)

Pedro.

---

From: Thomas Barron <[email-masked]>
Date: Wed, 28 Apr 2004 14:38:30 -0500

Hi Enke,

    Best regards,

   Tom Barron

---

From: Jeffrey Haas <[email-masked]>
Date: Thu, 29 Apr 2004 23:17:08 -0400

> IDR meeting. The algorithm described in the draft has been deployed for several

I would echo many of Tom's comments.  Specifically:

1. This doesn't solve med oscillation - or at least I don't think so.
2. Having this as a knob would be handy.  Whether this knob is turned
   on by default is an interesting question and the matter of some
   debate.
3. By having such a knob, those who prefer deterministic path selection
   in their network can have it while those who prefer path stability
   with the caveat that it is temporally deterministic could have their
   way too - perhaps on a border router basis.

Suggested changes:
Remove 5.2
Add something along the lines of item 3 above?
Be a bit more specific about where in the tie breaking algorithm this goes.

-- 
Jeff Haas 
NextHop Technologies

---

From: Jeffrey Haas <[email-masked]>
Date: Thu, 29 Apr 2004 23:17:08 -0400

Suggested changes:
Remove 5.2

-- 
Jeff Haas 
NextHop Technologies

---

From: Enke Chen <[email-masked]>
Date: Thu, 29 Apr 2004 21:49:24 -0700

Hi, Tom:

Thanks for your comments, and sorry that I forgot to reply to your original
message earlier. Please see my comments inline.

> Message-Id: <[email-masked]>
> Cc: [email-masked], [email-masked]
> From: Thomas Barron <[email-masked]>
> Subject: Re: [Idr] draft-chen-bgp-avoid-transition-01.txt
> To: Enke Chen <[email-masked]>, [email-masked]
> 
> Hi Enke,
> 
> and IGP costs.

MED plays a major role as well.

> Using sufficiently high IGP costs between clusters will suffice to stop
> the churn both in your scenario and in other scenarios that don't involve
> router-id.

Very true, and that is also discussed in Sect. 9 of RFC 2796 (RR).

Re-configuring the IGP metric is certainly an option. However, changing the
IGP metric typically has much larger impact on the network traffic matrix,
and may not be desirable or feasible.

> Indeed, in your scenario if by chance  

Do you have a specific example?  I would like to understand better whether
the algorithm is applicable to the example.

Unlike the ADD-PATH approach (which is a complete solution), the proposed
algorithm is effective only for a subset of route oscillations.

> >From [email-masked] Mon Nov 10 11:51:50 2003
> From: Tom Barron <[email-masked]>
> To: [email-masked]
> Cc: Thomas P Barron <[email-masked]>
> Message-ID: <[email-masked]>
> 
> Enke, Srihari, et. al:
> 
> I have some questions about draft-chen-bgp-avoid-transition-00.txt.
> I'm glad to see this draft since there are implementations out there
> using the route-selection algorithm this draft proposes, and since the
> proposed algorith is not what is documented in RFC1771 or in
> draft-ietf-idr-bgr4-22.txt section 9.1.2.2.
> 
> First, is it the intent of this draft that the proposed algorithm 
> should *replace* the algorithm currently documented, or just that
> it be added as an option?

It is a backward-compatible extension to the base BGP spec.. Whether
it is ON or OFF, that is an implementation decision. (If that is the
intent of your question.)

> 
> Second, while I think the claim in 5.1 that the proposed algorithm
> avoids an unnecessary best path transition is quite straightforward,
> there ought to be some discussion of concerns that have been expressed
> about the consequent lack of determinism in route selection.  See
> for example section 7.1.4 of draft-ietf-idr-bgp4-experience-protocol-03.txt
> and appendix A of "Guidelines for Interdomain Traffic Engineering" by
> Feamster, Borkenhagen, and Rexford.  I'm not personally convinced
> that this local indeterminism is a real big deal, but I do think it
> needs some discussion in your draft.

As I recall, the only practical concern raised so far is the impact on
BGP testing script by the proposed algorithm, and the subject (impact
on the testing script) seems to be outside the scope of the document.
Please let me know if I have missed any other practical concerns.

> 
> Third, I found the argument at 5.2 to the effect that the proposed
> algorithm reduces route oscillation a bit unclear.  Maybe just a bit
> more text is needed, but it seems to me that the really essential
> ingredient in your setup in figure 1 and figure 2 is not the router
> ID, but the high intracluster IGP metric.  Indeed, though you cite
> RFC3345, that work focuses on IGP metrics, not router ID, as a
> critical factor for "type 1" oscillation scenarios (yours appears to
> be a type 1 variant.)  If adjusting IGP metrics is sufficient to fix
> both your oscillation scenario and other type 1 scenarios, but
> shifting from Router ID selection to the proposed time-of-arrival
> algorithm is not sufficient for type 1 scenarios in general, then the
> contribution of the proposed algorithm to the route oscillation
> problem does not seem very decisive.  On the other hand, if using the
> proposed time-of-arrival algorithm yields a general solution to
> oscillation problems, then this reader at least did not get that from
> the draft as currently written.
> 

We will work on adding more text to clarify.

> I'm glad you folks wrote this draft.  I hope it's clear that I'm
> not against your proposal, but rather want to address some gaps
> in my own understanding of the issues that surround it.
> 

Some of the gaps are with the text in the document :-)
We will work on improving it in the next version.

Regards,

-- Enke

---

From: Enke Chen <[email-masked]>
Date: Thu, 29 Apr 2004 21:49:24 -0700

Hi, Tom:

Regards,

-- Enke

---

From: Thomas Barron <[email-masked]>
Date: Fri, 30 Apr 2004 14:46:43 -0500

Hi Enke,

    Please see inline.

> MED plays a major role as well.

Sure.

> Very true, and that is also discussed in Sect. 9 of RFC 2796 (RR).

I rather like the way the point is put there.

> and may not be desirable or feasible.

Hmmm.  Maybe my thinking is just too pedestrian, but I don't myself see 
the design drivers for setting up RRs and RCs such that clusters don't 
"cluster" in terms of IGP metrics as well.

> algorithm is effective only for a subset of route oscillations.

Well, if I'm right, it isn't always effective for this subset either.

    Consider the example in Fig. 3 where

       o R1, R2, R3 and R4 belong to one AS
       o R1 is a route reflector with R3 as its client.
       o R2 is a route reflector with R4 as its client.
       o External paths (a), (b) and (c) are as described in Fig. 4.

                   +----+      10      +----+
                   | R1 |--------------| R2 |
                   +----+              +----+
                      |                   |
                      |                   |
                      | 5                 | 20
                      |                   |
                      |                   |
                   +----+              +----+
                   | R3 |              | R4 |
                   +----+              +----+
                  /      \                |
                 /        \               |
               (a)        (b)            (c)

                           Figure 3

                 Path    AS     MED   TimeofArrival
                  a        1        0         2
                  b        2       20        1
                  c        2       10        5

                           Figure 4

Here is the oscillation:

1. R3 likes (b) over (a) (ToA)
2. R3 advertises (b) to R1
3. R1 hears (b, c) and prefers (c) (MED)
4. R1 advertises (c) to R3
5. R3 prefers (a) among (a, b, c) (MED + ToA)
     *NOTE* the arrival time of (c) is no longer 5, but it is some 
quantity >5.
      ToA(c) > 5 > ToA(a), so  (a) wins after MED eliminates (b) in 
favor of (c).
6. R3 advertises (a) to R1
7. R1 hears (a, c) and prefers (a) (IGP)
8. R1 advertises (a) to R2
9. R2 prefers (a) over (c) (lower IGP cost)
10. R2 withdraws (c) from R1 and the withdrawal propagates through R1 
to R3
11.  R3 prefers (b) over (a) since (c) is no longer available to 
disqualify (b) and
       ToA(b) < ToA(a)

(Thanks to Nick Feamster, some time ago, for documenting these steps in 
a private email.)

So, what we've done is keep everything the same in your example except 
that we've put ToA where you have Router ID.  You make the point that 
"the BGP identifier of a route received from an external peer is just a 
random number" and that led me to think of the fact that the same can 
be said of the Time of Arrival.  The interesting thing about your 
scenario is that the Time of Arrival of route (c) will change because 
it is withdrawn and readvertised, but since it is the highest that 
doesn't affect the order of the Times of Arrival so the formal 
parallelism with your case using BGP identifiers is preserved.

> intent of your question.)

Good.   Yes, that is the intention of my question, and I suggest that 
you make this point explicitly in your draft.

>> for example section 7.1.4 of 
>> draft-ietf-idr-bgp4-experience-protocol-03.txt

Well, without getting into issues about whether Traffic Engineering is 
"practical" :-), I suggest that you might want to explicitly state that 
there may be circumstances in which an ISP is doing TE where this knob 
would be best left off.

I am not myself aware of any other circumstances where the 
indeterminism that this knob introduces has any bad effects.

> We will work on improving it in the next version.

Thanks,

- Tom

---

From: Thomas Barron <[email-masked]>
Date: Fri, 30 Apr 2004 14:46:43 -0500

Hi Enke,

    Please see inline.

Sure.

                   +----+      10      +----+

                           Figure 3

                           Figure 4

Here is the oscillation:

Thanks,

- Tom

---

From: Enke Chen <[email-masked]>
Date: Fri, 30 Apr 2004 15:17:21 -0700

Hi, Tom:

Please see inline.

> Message-Id: <[email-masked]>
> Content-Transfer-Encoding: 7bit
> Cc: [email-masked]
> Date: Fri, 30 Apr 2004 14:46:43 -0500
> To: Enke Chen <[email-masked]>
> 

[snip]

>        o External paths (a), (b) and (c) are as described in Fig. 4.

I see where your confusion was. The proposed algorithm in Sect. 4 of the
draft does not really care about ToA ("Time of Arrival"). It just says
that "Do not switch the best path from one EBGP path to another EBGP
path when the comparison comes down to the route-id.

So, in Step 11, if you follow the proposed algorithm, (a) will remain
as the best path on R3, and the churn will stop.

I will need to think about other comments of yours, and try to clarify
the text in the next version.

Thanks. -- Enke

---

From: Jeffrey Haas <[email-masked]>
Date: Fri, 30 Apr 2004 18:25:46 -0400

> indeterminism that this knob introduces has any bad effects.

Or existing implementations of this knob that already do this. :-)

Speaking as a former network operator of a tier-3 ISP, it took us a
while to understand why otherwise very stable paths would all of
a sudden take a sharp turn.  This was typically noticed when the
new stable path was poor for some reason.  

-- 
Jeff Haas 
NextHop Technologies

---

From: Enke Chen <[email-masked]>
Date: Fri, 30 Apr 2004 15:17:21 -0700

Hi, Tom:

Please see inline.

[snip]

Thanks. -- Enke

---

From: Jeffrey Haas <[email-masked]>
Date: Fri, 30 Apr 2004 18:25:46 -0400

-- 
Jeff Haas 
NextHop Technologies

---

From: Thomas Barron <[email-masked]>
Date: Fri, 30 Apr 2004 17:41:07 -0500

Hi Enke,

   Thanks for clarifying.  I'm cool with this :-)

- Tom

---

From: Thomas Barron <[email-masked]>
Date: Fri, 30 Apr 2004 17:41:07 -0500

Hi Enke,

- Tom