Analysis of paths selection modes for Add-Paths
draft-vvds-add-paths-analysis-00

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-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.

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 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.

Abstract

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

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] (D. Walton, A. Retana, and E. Chen, “Advertisement of Multiple Paths in BGP,” .).

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] (D. Walton, A. Retana, and E. Chen, “Advertisement of Multiple Paths in BGP,” .) 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 properties.

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 completed.

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.

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] (Mohapatra, P., Fernando, R., Filsfils, C., and R. Raszuk, “Fast Connectivity Restoration Using BGP Add-path,” September 2008.) 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 used.

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-Rib-Ins.

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 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 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 exist.

5.3.  Advertise All AS-Wide Best Paths

Another choice is to advertise all paths with the same AS-wide preference [Basu‑ibgp‑osc] (Basu, A., Ong, C., Rasala, A., Sheperd, B., and G. Wilfong, “Route oscillations in iBGP with Route Reflection,” .), 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.

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] (Walton, D., Retana, A., and E. Chen, “BGP Persistent Route Oscillation Solution,” July 2005.) 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 Preference.

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 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 packet.

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.

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 comments.

10. References

Authors' Addresses