Subject: draft-chen-route-oscillation-avoid-00.txt

From: Enke Chen <[email-masked]>
Date: Mon, 17 Jun 2002 21:39:20 -0700

Hi, folks:
I have submitted <draft-chen-route-oscillation-avoid-00.txt>.
As I will be away (in a couple of days) from email for a while, I
thought that I would post the draft to the mailing list directly so
that your comments or questions on the draft can be taken care of
in the next couple of days.

Regards,  -- Enke
--------------------------------------------------------------------

Network Working Group                                         Enke Chen
Internet Draft                                         Redback Networks
Expiration Date: December 2002

 BGP Route Oscillation Avoidance for Route Reflection and Confederation

               draft-chen-route-oscillation-avoid-00.txt

1. Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as ``work in progress.''

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

2. Abstract

   In this document we propose a mechanism and routing setup that would
   avoid persistent route oscillations and yield consistent route
   selection in a network using one-level Route Reflection, or using
   Confederation where routers that participate in inter-member-AS
   peering are fully meshed.

Chen                                                            [Page 1]

Internet Draft  draft-chen-route-oscillation-avoid-00.txt      June 2002

3. Introduction

   As documented in [1], the routing information reduction by BGP Route
   Reflection [2], or BGP Confederation [3] can result in persistent
   route oscillations with certain network topologies and routing setup.

   In this document we propose a mechanism and routing setup that would
   avoid persistent route oscillations and yield consistent route
   selection in a network using one-level Route Reflection, or using
   Confederation where routers that participate in inter-member-AS
   peering are fully meshed.

   The proposed mechanism makes use of the mechanisms presented in [4,
   5], and works within the current BGP protocol [6, 7] that limits
   route advertisement to only one path per prefix.

4. Observations on IBGP Updates

   Currently a BGP speaker follows the basic BGP principle that only the
   best path is advertised to a BGP peer. Since the best path of a
   prefix for a BGP speaker is impacted by routes received from internal
   peers, the route advertised by the speaker is also impacted by routes
   received from internal peers. This dependency can lead to circular
   (and possibly excessive) IBGP routing updates, slow convergence, and
   persistent route oscillation in the worst case.

   The earlier version of BGP [6] specifies that a BGP speaker should
   advertise to IBGP its best external route [6, Sect. 9.2.1]. With this
   approach the route advertisement toward IBGP peers is independent of
   route advertisement received from IBGP peers. In addition, this
   approach has the benefit of faster routing convergence compared to
   the current practice of advertising the best path.

   If clients of a Route Reflector (RR) adopts this approach, and the RR
   advertises to other clusters the best path from its clients and
   external peers (as proposed in [4]), then the advertisement by the RR
   to other clusters would become independent of routes received from
   other clusters.

   It is based on this observation that we formulate a mechanism and
   routing setup that would avoid route oscillations for one-level route
   reflection, and for a confederation where routers that participate in
   inter-member-AS peering are fully meshed.

Chen                                                            [Page 2]

Internet Draft  draft-chen-route-oscillation-avoid-00.txt      June 2002

5. Mechanism for One-level Route Reflection

   This mechanism consists of the following procedures and routing
   setup:

     a) One-level Route Reflection (all RRs are fully meshed).

     b) BGP full mesh among clients of a RR.

     c) Apply the mechanism in [4] for a RR.

     d) A client advertises its best external route to IBGP peers.

   Due to c) and d), we claim that with this mechanism and setup the
   network is free of route oscillation.

   It is noted that due to d) the best external path advertised by a BGP
   speaker to an IBGP peer may be different from the overall best path
   installed in RIB/FIB. Clearly the difference will not cause any
   forwarding loop when the overall best path is also an external path.

   When the overall best path for a BGP speaker is from an internal
   peer, we claim that the best external path for the speaker will not
   be selected as the best path by any other speakers. The proof for
   this claim is included in the Appendix.

   Therefore we conclude that the route selection consistency is
   maintained with the proposed mechanism.

6. Mechanism for Confederation

   The mechanism for Confederation consists of the following procedures
   and routing setup:

     a) BGP full mesh among routers that participate in inter-member-AS
        peering.

     b) BGP full mesh within a member-AS.

     c) Apply the mechanism in [5] for a router that peers with a
        neighobring AS in the confederation.

     d) For a router that does not participate in inter-member-AS
        peering, it should advertises its best external route to peers
        within a confederation.

   We claim that with the mechanism and routing setup a network would

Chen                                                            [Page 3]

Internet Draft  draft-chen-route-oscillation-avoid-00.txt      June 2002

   avoid persistent route oscillations and yield consistent route
   selection. This claim can be proved similarly.

7. Appendix: Proof of Route Selection Consistency

   To simplify presentation, let us describe a general route reflection
   setup as follows:

                   RR1  ---------- RR2 ---------- RR3 --- ... RRn
                  /  |               |              |          |
                 /   |               |              |          |
                /    |               |              |          |
               /     |               |              |          |
             C11    C12             C2             C3         ...
              |      |               |              |          |
              |      |               |              |          |
            (E11)  (E12)           (E2)            (E3)       ...

   In this figure, there are multiple clusters with RR1, RR2, RR3 as the
   route reflectors. C11 and C12 are clients of RR1.  C2 is client of
   RR2, and C3 is a client of RR3. E11, E12, E2, and E3 are the external
   paths. Other than for the purpose of illustration, no restrictions
   are imposed on the route reflection topology including the number of
   clusters, number of clients, and where and how many external paths
   are connected.

   Assume that E2 is the best path among all paths received by RR1 from
   other clusters, and assume that the EBGP path E11 is not the overall
   best path for C11. we try to prove that E11 will not be selected as
   the best path by any other routers.

   Based on route selection procedures described in [7], E11 can only
   lose (on C11) to an IBGP path (either E12 or E2) by either LOCAL-
   PREF, or Origin, or AS-PATH Length, or MED. Due to the natural of
   these parameters, as long as the overall best path (either E12 or E2)
   is present on a router, E11 will continue to lose on the router
   irrespective of any other paths.

   Due to full IBGP mesh within a cluster, both E12 and E2 are present
   on all routers within the cluster. So E11 will not be selected as the
   best path by any router within the cluster.

   To prove that E11 will not be selected as the best path by a router
   in another cluster, we need to consider two cases:

Chen                                                            [Page 4]

Internet Draft  draft-chen-route-oscillation-avoid-00.txt      June 2002

   (1) Assume E11 is lost to E12 on C11. Then E11 will not selected as
   the best path from its clients on RR1, and will not be advertised by
   RR1 to other clusters.

   (2) Assume E11 is lost to E2 on C11. As RRs are fully meshed, E2 will
   be present on all RRs. Thus E11 will not be selected as the best path
   by any of the RRs.

   Within the cluster served by RR2, E11 will not be selected by its
   clients (even if E11 is better than E3 on RR2) as E2 is present.

   As E2 is present on RR3, E11 will not be advertised to its clients,
   thus will not be selected as the best path by its clients.

8. Security Considerations

   This document introduces no new security concerns to BGP or other
   specifications referenced in this document.

9. Acknowledgments

   The author would like to thank Jenny Yuan for her review and
   comments.

10. References

   [1]  McPherson, D., Gill, V., Walton, D., Retana, A., "BGP Persistent
        Route Oscillation Condition", Work in Progress (draft-ietf-idr-
        route-oscillation-01), February 2002.

   [2]  Bates, T., Chandra, R., Chen, E., "BGP Route Reflection - An
        Alternative to Full Mesh IBGP", RFC 2796, April 2000.

   [3]  Traina, P., McPherson, D., Scudder, J.. "Autonomous System Con-
        federations for BGP", RFC 3065, February 2001.

   [4]  Chen, E., "BGP Route Oscillation Reduction with Route
        Reflection", Work in Progress
        (draft-chen-rr-oscillation-reduce-01.txt), June 2002.

   [5]  Chen, E., "BGP Route Oscillation Reduction with Confederation",
        Work in Progress (draft-chen-confed-oscillation-reduce-01.txt),
        June 2002.

   [6]  Rekhter, Y., and T. Li, "A Border Gateway Protocol 4 (BGP-4)",

Chen                                                            [Page 5]

Internet Draft  draft-chen-route-oscillation-avoid-00.txt      June 2002

        RFC 1771, March 1995.

   [7]  Rekhter, Y., and T. Li, "A Border Gateway Protocol 4 (BGP-4)",
        Work in Progress (draft-ietf-idr-bgp4-17), January 2002

11. Author Information

   Enke Chen
   Redback Networks, Inc.
   350 Holger Way
   San Jose, CA 95134
   Email: [email-masked]

Chen                                                            [Page 6]