[Docs] [txt|pdf|xml|html] [Tracker] [Email] [Nits]

Versions: 00

Network Working Group                                V. Van den Schrieck
Internet-Draft                                               P. Francois
Intended status: Informational          Universite catholique de Louvain
Expires: January 7, 2010                                    July 6, 2009

            Analysis of paths selection modes for Add-Paths

Status of this Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.  This document may contain material
   from IETF Documents or IETF Contributions published or made publicly
   available before November 10, 2008.  The person(s) controlling the
   copyright in some of this material may not have granted the IETF
   Trust the right to allow modifications of such material outside the
   IETF Standards Process.  Without obtaining an adequate license from
   the person(s) controlling the copyright in such materials, this
   document may not be modified outside the IETF Standards Process, and
   derivative works of it may not be created outside the IETF Standards
   Process, except to format it for publication as an RFC or to
   translate it into languages other than English.

   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-

   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

   The list of Internet-Draft Shadow Directories can be accessed at

   This Internet-Draft will expire on January 7, 2010.

Copyright Notice

   Copyright (c) 2009 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal

V. Van den Schrieck & P. Francois  Expires January 7, 2010      [Page 1]

Internet-Draft             Add-Paths Analysis                  July 2009

   Provisions Relating to IETF Documents in effect on the date of
   publication of this document (http://trustee.ietf.org/license-info).
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.


   This document is aimed at discussing the various alternatives for the
   selection of the paths that are to be advertised with add-paths.  The
   goal is to summarize the properties of those selection methods
   depending on which application they are used for.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . 3
   2.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3
   3.  Potential uses of Add-Paths . . . . . . . . . . . . . . . . . . 4
   4.  Evaluation criteria . . . . . . . . . . . . . . . . . . . . . . 4
   5.  Paths selection modes . . . . . . . . . . . . . . . . . . . . . 5
     5.1.  Advertise All Paths . . . . . . . . . . . . . . . . . . . . 5
     5.2.  Advertise N Paths . . . . . . . . . . . . . . . . . . . . . 6
     5.3.  Advertise All AS-Wide Best Paths  . . . . . . . . . . . . . 6
     5.4.  Advertise Neighbor-AS Group Best Path . . . . . . . . . . . 7
     5.5.  Best LocPref/Second Locpref . . . . . . . . . . . . . . . . 7
     5.6.  Advertise Paths at decisive step - 1  . . . . . . . . . . . 8
   6.  Forwarding Modes  . . . . . . . . . . . . . . . . . . . . . . . 8
   7.  IANA considerations . . . . . . . . . . . . . . . . . . . . . . 8
   8.  Security Considerations . . . . . . . . . . . . . . . . . . . . 9
   9.  Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . 9
   10. References  . . . . . . . . . . . . . . . . . . . . . . . . . . 9
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . . . 9

V. Van den Schrieck & P. Francois  Expires January 7, 2010      [Page 2]

Internet-Draft             Add-Paths Analysis                  July 2009

1.  Introduction

   For quite a long time, the IETF has been investigating solutions to
   let BGP speakers advertise multiple paths for a single prefix in iBGP
   instead of advertising their best path only [AddPath].

   The primary goal of add-paths is to increase the visibility of paths
   within an iBGP system, so as to improve various aspects of the
   behavior of (i)BGP.  Add-paths increases the robustness in case of
   failure and reduces the number of BGP messages during such an event.
   Through careful selection of the paths to be advertised, Add-paths
   can also prevent routing oscillations.

   [AddPath] specifies how to encode the advertisement of multiple path
   towards the same NLRI over an iBGP session, and leaves complete
   freedom about the decision of which paths should be advertised.  In
   this document, we explore various alternatives for the selection of
   the multiple paths to be advertised, and discuss their related

   The document is organized as follows.  First, we present the
   terminology used throughout this document.  Next, we discuss the
   potential applications of multiple paths advertisement, and list some
   criteria to evaluate the way multiple paths are selected.  We then
   describe different paths selection and, for each them, discuss its
   properties based on those criteria.

2.  Terminology

   Backup / alternate path : A path toward a prefix that is not selected
   as best by a router, but that can be used as a replacement upon
   failure of the primary path.

   Post-convergence path or optimal backup path : a path toward an
   affected prefix that will be selected as the best path by an affected
   router, when the link is shut down and the BGP convergence is

   Loss of Connectivity (LoC) : the state when a router has no path
   towards an affected prefix.

   AS-Wide preferred paths : Paths that are considered as best when
   applying rules of the BGP decision process up to the IGP tie-break.

   Path diversity : The property that a router has several paths with
   different nexthops for a given prefix.

V. Van den Schrieck & P. Francois  Expires January 7, 2010      [Page 3]

Internet-Draft             Add-Paths Analysis                  July 2009

   Path visibility : The property that paths are not hidden by some
   routers, and are thus available to all routers in the AS.

3.  Potential uses of Add-Paths

   [draft-mohapatra] presents the applications that would benefit from
   multiple paths advertisement in iBGP.  Those are :

   Fast Connectivity Restoration, thanks to the dissemination of backup
   paths.  If a router has a backup path, it can directly selects that
   path as best upon failure of the primary path.  This minimizes packet
   loss on dataplane.  Sending multiple paths in iBGP allows routers to
   receive backup paths when path visibility is not sufficient with
   classical BGP.  This is especially useful when Route Reflection is

   Load Balancing, across several BGP nexthops : Increased path
   diversity allows routers to install several paths in their Routing
   Table and to load balance traffic across those paths.

   Churn reduction : As failures can be recovered locally when backup
   paths are available, BGP path exploration is reduced in iBGP, which
   results in less updates disseminated in eBGP.  When the preferred
   backup path is the post-convergence path, churn is minimized.

4.  Evaluation criteria

   Advertising multiple paths in iBGP has several impacts on the routing
   system.  In this section, we list some criteria for the evaluation of
   each proposal.

   Control Plane Charge : As a router receives multiples paths for a
   prefix from an iBGP client, it has to store more paths in its Adj-

   Control Plane Stress : Coping with multiple iBGP paths has two
   implications on the computation that a router has to handle : First,
   it has to compute the paths to send to its peers, i.e. more than the
   best path.  Second, it also has to handle the potential churn related
   to the exchange of those multiple paths.

   MED/IGP oscillations : BGP sometimes suffers from routing
   oscillations when the physical topology differs from the logical
   topology, or when the MED attribute is used.  This is due to the
   limited path visibility when a single path is advertised and Route
   Reflection is used.  Increasing the path visibility by advertising

V. Van den Schrieck & P. Francois  Expires January 7, 2010      [Page 4]

Internet-Draft             Add-Paths Analysis                  July 2009

   multiple paths can help solving this issue.

   Path optimality : When a single path is advertised, border routers do
   not always receive the path with the closest exit point, because the
   Route Reflectors send a single path chosen based on their own IGP
   tie-break.  Increasing path visibility would also help routers to
   learn the path that is best suited for them w.r.t. the IGP tie-break.

   Backup path optimality : Multiple paths advertisement gives routers
   the opportunity to have a backup path.  However, some backup paths
   are better than others.  Indeed, when a link failure occurs, if a
   router already knows its post-convergence path, the BGP reconvergence
   is straightforward and traffic is less impacted by the transient use
   of non-best forwarding paths.

   Convergence time : Advertising multiple paths in iBGP has an impact
   on the convergence time of the BGP system.  More paths need to be
   exchanged, but on the other hand, the routing information is
   propagated faster : With an increased path visibility, there is less
   path exploration during the convergence.  Also, with the availability
   of backup paths, convergence time in case of failure is also reduced.

5.  Paths selection modes

5.1.  Advertise All Paths

   A simple rule for advertising multiple paths in iBGP is to simply
   advertise to iBGP peers all received paths, provided they pass export
   filters.  This solution is easy to implement, but the counter part is
   that all those paths need to be stored by all routers that receive
   them, which can be quite expensive.  If a path to a prefix P is
   advertised to N border routers, with a FullMesh of iBGP sessions, all
   routers have N paths in their Adjribins.  If Route Reflection is used
   and each client is connected to 2 Route Reflectors, it may learn up
   to 2*N paths.

   This solution gives a perfect path visibility to all routers, thus
   limiting churn and losses of connectivity in case of failure.
   Indeed, this allows routers to select their optimal primary path, and
   to switch on their optimal backup path in case of failure.

   However, as more paths are exchanged, the number of BGP messages
   disseminated during the initial iBGP convergence can be high, and
   convergence may be slower.

   Routing oscillations are prevented with this rule, because a router
   won't need to withdraw a previously advertised path when its best

V. Van den Schrieck & P. Francois  Expires January 7, 2010      [Page 5]

Internet-Draft             Add-Paths Analysis                  July 2009

   path changes.

5.2.  Advertise N Paths

   Another cheaper solution is for a router to advertise a maximum of N
   paths to iBGP peers, N being chosen by the operators depending on its
   needs.  Here, the computational cost is the selection of the N paths.
   Indeed, there must be a ranking of the paths in order to advertise
   the most interesting ones.  A way for a router to select N paths is
   to run N times its decision process.  The memory cost is bounded : A
   router receives a maximum of N paths for each prefix from each peer.

   With N equals to 2, all routers know at least two paths and can
   provide local recovery in case of failure.  If multipath routing is
   to be deployed in the AS, N can be increased to provide more
   alternate paths to the routers.

   Path optimality and backup path optimality are not guaranteed, but as
   path diversity is better, the nexthops of the chosen primary and
   backup path are more likely to be closer to the router than with
   classical BGP.

   This solution helps to reduce routing oscillations, but not in all
   cases.  Indeed, path visibility is still constrained by the maximum
   number of paths, and configurations with routing oscillations still

5.3.  Advertise All AS-Wide Best Paths

   Another choice is to advertise all paths with the same AS-wide
   preference [Basu-ibgp-osc], i.e. the paths that all routers would
   select based on the rules of the decision process that are not
   router-dependent (i.e.  Local-preference, ASPath length and MED
   rules).  Thus, for a given router, those paths only differ by the IGP
   cost to the nexthop or by the tie-breaking rules.

   The computational cost is reduced, as a router only has to send the
   paths remaining before applying the IGP tie-breaking rule.  However,
   it is difficult to predict how many paths will be stored, as it
   depends on the number of eBGP sessions on which this prefix is
   advertised with the best AS-wide preference.

   With this rule, the routing system is optimal : All routers can
   choose their best path (or best paths if multipath is used) based on
   their router-specific preferences, i.e. the IGP cost to the nexthop.
   Hot potato routing is respected.  Also, MED oscillations are
   prevented, because the path visibility among the AS-wide preferred
   paths is total.

V. Van den Schrieck & P. Francois  Expires January 7, 2010      [Page 6]

Internet-Draft             Add-Paths Analysis                  July 2009

   The existence of a backup path is not guaranteed : If only one path
   with the AS-wide best attributes exists, there is no backup path
   disseminated.  However, if such a path exists, it is optimal as it
   has the same AS-wide preference as the primary.

5.4.  Advertise Neighbor-AS Group Best Path

   [walton-osc] proposes that a router groups its paths based on the
   neighbor AS from which it was learned, and to advertise the best path
   in each of those groups.

   The control plane stress induced by this solution is the computation
   of the per-neighbor path group, and the application of the decision
   process to each of them.  The Control-Plane charge is bounded by the
   number of neighboring ASes advertising a prefix, which cannot be
   known a-priori.

   Path optimality and backup path optimality are not guaranteed, as the
   paths advertised are not all the AS-wide preferred paths.  Backup
   path availability is not guaranteed.  Indeed, if only one AS
   advertises this prefix, even on multiple eBGP sessions, only one of
   the paths may be selected and advertised.

5.5.  Best LocPref/Second Locpref

   This selection method consists in grouping the paths by Local
   Preference.  A router sends to its peers all paths with the highest
   Local Preference.  If there is only a single path with the highest
   Local Preference, it also sends all paths with the second best Local

   This method ensures that all routers know all paths with the best
   local preference.  As local preference are often related to the type
   of peering of the peer the path comes from, this ensures that in case
   of failure, routers have a backup path of equivalent quality.  This
   prevents for example that a router switches temporarily on a peer
   path while an alternate path from a customer is available but hidden
   at the border of the AS.  Such a situation could result in a
   temporary withdrawal of the prefix on some eBGP sessions when the
   router selects the path via the peer.

   The advertisement of the Second Local Preference occurs when there is
   no alternate path with the same quality as the best path.  This way,
   fast convergence is still ensured.  Backup path is optimal, as it has
   the second AS-Wide preference, which becomes the AS-wide best
   preference upon failure of the primary one.

   Sending all the paths with a given Local Preference also has a

V. Van den Schrieck & P. Francois  Expires January 7, 2010      [Page 7]

Internet-Draft             Add-Paths Analysis                  July 2009

   positive impact on routing optimality : Indeed, this allow border
   routers to have an increased path visibility and to choose their best
   path based on their own criteria.

   The computational cost of this solution is reduced when there are
   several paths with the best local preference.  In this case, it is
   sufficient to stop the decision process after the first rule to have
   the set of paths to be advertised.  When it is necessary to advertise
   the paths with second local-preference, the additional cost is to
   apply a second time the first rule of the decision process, which is
   still reasonable.  The memory cost depends on the number of paths
   with the best local preference.

5.6.  Advertise Paths at decisive step - 1

   When the goal is to provide fast recovery by advertising candidate
   post-reconvergence paths, one can choose to stop the decision process
   just before the step where only one path remains.  If the decision
   process comes to IGP tie-break, all remaining paths are advertised.
   This way, routers advertise as many paths as possible with a quality
   as similar as possible.

   This path selection is an intermediary solution between the two
   preceding ones.  Here, instead of stopping the decision process at
   the local preference step or the IGP step, we stop it before the rule
   that removes the best potential backup paths.  This way, we minimize
   the number of paths to advertise while guaranteeing the presence of a
   backup path.  Primary and backup path optimality is ensured, as all
   paths with the same AS-wide preference as the best paths are included
   in the set of paths advertised.

6.  Forwarding Modes

   Forwarding from the ingress ASBR to the egress ASBR can be impacted
   by the application of Add-Path when encapsulation is not used and
   intermediate routers perform a lookup in BGP-fed FIBs to forward the

   The analysis for this deployment scenario of add-paths is left for
   further version of the draft.

7.  IANA considerations

   This document includes no request to IANA.

V. Van den Schrieck & P. Francois  Expires January 7, 2010      [Page 8]

Internet-Draft             Add-Paths Analysis                  July 2009

8.  Security Considerations

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

9.  Acknowledgments

   We would like to thank Olivier Bonaventure for his suggestions and

10.  References

   [AddPath]  D. Walton, A. Retana, and E. Chen, "Advertisement of
              Multiple Paths in BGP", draft-walton-bgp-add-paths-06.txt
              (work in progress).

              Marques, P., Fernando, R., Chen, E., and P. Mohapatra,
              "Advertisement of the best-external route to IBGP",
               draft-marques-idr-best-external-00.txt, July 2008.

              Basu, A., Ong, C., Rasala, A., Sheperd, B., and G.
              Wilfong, "Route oscillations in iBGP with Route
              Reflection", Sigcomm 2002.

              Mohapatra, P., Fernando, R., Filsfils, C., and R. Raszuk,
              "Fast Connectivity Restoration Using BGP Add-path",
              draft-pmohapat-idr-fast-conn-restore-00.txt (work in
              progress), September 2008.

              Walton, D., Retana, A., and E. Chen, "BGP Persistent Route
              Oscillation Solution",
              draft-walton-bgp-route-oscillation-stop-01.txt (work in
              progress), July 2005.

V. Van den Schrieck & P. Francois  Expires January 7, 2010      [Page 9]

Internet-Draft             Add-Paths Analysis                  July 2009

Authors' Addresses

   Virginie Van den Schrieck
   Universite catholique de Louvain
   Place Ste Barbe, 2
   Louvain-la-Neuve  1348

   Email: virginie.vandenschrieck@uclouvain.be
   URI:   http://inl.info.ucl.ac.be/vvandens

   Pierre Francois
   Universite catholique de Louvain
   Place Ste Barbe, 2
   Louvain-la-Neuve  1348

   Email: pierre.francois@uclouvain.be
   URI:   http://inl.info.ucl.ac.be/pfr

V. Van den Schrieck & P. Francois  Expires January 7, 2010     [Page 10]

Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/