Network Working Group J. Uttaro
Internet Draft AT&T
Intended status: Informational R. Fragassi
Feb 25, 2010 A. Simpson
Expires: August 2010 Alcatel-Lucent
P. Mohapatra
Cisco Systems
Best Practices for Advertisement of Multiple Paths in BGP
draft-uttaro-idr-add-paths-guidelines-00.txt
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
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 August 26, 2010.
Copyright Notice
Copyright (c) 2010 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
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
Uttaro, et al Expires August 26, 2010 [Page 1]
Internet-Draft draft-uttaro-idr-add-paths-guidelines Feb 2010
the Trust Legal Provisions and are provided without warranty as
described in the BSD License.
Abstract
ADD-PATH is a BGP enhancement that allows a BGP router to advertise
multiple distinct paths for the same prefix/NLRI. This provides a
number of potential benefits, including reduced routing churn, faster
convergence, better loadsharing and a mechanism for graceful
maintenance. This document describes implementation and operational
best practices for ADD-PATH in order to facilitate the introduction
of ADD-PATH to existing networks and to ensure interoperability.
Table of Contents
1. Introduction...................................................3
1.1. Add-Paths Overview........................................3
2. Conventions used in this document..............................6
3. Implementation Guidelines......................................6
3.1. Capability Negotiation....................................6
3.2. Receiving Multiple Paths..................................7
3.3. BGP Decision Process......................................8
3.4. Sending Multiple Paths....................................8
3.5. Using Multiple Paths for Forwarding.......................9
4. Deployment Guidelines..........................................9
4.1. Routing Consistency.......................................9
4.2. ADD-PATH Applications....................................10
5. Security Considerations.......................................10
6. IANA Considerations...........................................10
7. Conclusions...................................................10
8. References....................................................10
8.1. Normative References.....................................10
8.2. Informative References...................................10
9. Acknowledgments...............................................10
Uttaro, et al. Expires August 26, 2010 [Page 2]
Internet-Draft draft-uttaro-idr-add-paths-guidelines Feb 2010
1. Introduction
This best practices guide is intended to supplement [ADD-PATH] by
providing operators and implementers of BGP ADD-PATH with best
practice recommendations. It also aims to ensure that while
introducing ADD-PATH in existing networks, operators have the
controls needed to manage the additional resources it imposes.
1.1. Add-Paths Overview
The BGP ADD-PATH capability enhances current BGP implementations by
allowing a BGP router to exchange with its BGP peers more than one
path for the same destination/NLRI. The base BGP standard [RFC 4271]
does not provide for such a capability. If a BGP router learns
multiple paths for the same NLRI (from multiple peers), it selects
only one as its best path and advertises the best path to its peers.
The ADD-PATH extension [ADD-PATH] has a number of benefits, including
reduced routing churn, faster convergence, better loadsharing and a
mechanism for graceful maintenance.
Consider a network such as the one depicted in Figure 1 and suppose
that none of the routers support ADD-PATH. From AS1 there are 3 paths
(A, B and C) to a particular destination XYZ: two of the paths are
via AS3 and one of the paths is via AS2. In this example, Path A is
preferred over Path B due to Path A having a lower MED (multi-exit
discriminator) (MED for Path A is lower than MED for path B).
AS1 uses a route reflector RR1 to reduce the scale of its IBGP mesh.
During steady state, RR1 knows about (has in its RIB-IN) only 2 of
the 3 paths. Router B suppresses the advertisement of its best
external path (B) to RR, an IBGP peer, because its best overall path
is A, learnt from router A (via the RR). RR1 chooses path A as the
overall best since its IGP cost to router A is the lowest among path
A and C. During normal conditions, router D has even less knowledge
of the available paths to destination XYZ; it knows only about path
(A), the best path from RR1's perspective.
Uttaro, et al. Expires August 26, 2010 [Page 3]
Internet-Draft draft-uttaro-idr-add-paths-guidelines Feb 2010
======== =====================
= +---+ +---+ +---+
= |RTR|________|RTR| |RTR|
= | E | | A | | C |\ <-Path C
= +---+Path A->+---+ AS1 +---+ \
= = = \ / = \ =======
= = = \ / = +---+ =
= = = \ / = |RTR| =
= = = \ / = | G | =
= AS3 = = +---+ = +---+ =
= = = |RR | = = =
= = = | 1 | = = AS2 =
= = = +---+ = =======
= = = / \ =
= = = / \ =
= = = / \ =
= = = / \ =
= +---+Path B->+---+ +---+
= |RTR| ______|RTR| |RTR|
= | F | | B | | D |
= +---+ +---+ +---+
========== =====================
Figure 1: Example Topology
Consider now the steps required to restore traffic from router D to
destination XYZ when the link between Router A and Router E fails.
1. Router A sends a BGP UPDATE message withdrawing its advertisement
of path (A).
2. RR receives the withdrawal, and propagates it to its other client
peers, routers B, C and D.
3. When router B receives the withdrawal of path (A) it reruns its
decision process and selects path (B) as its new best path. Router
B advertises path (B) to RR.
4. RR reruns its decision process and selects path (B) as its new
best path. RR advertises path (B) to client peers A, C and D.
5. Router D reruns its decisions process, determines path (B) to be
the best path, and updates its forwarding table. After this step
traffic from router D to destination XYZ is restored (the traffic
path has changed from A to B).
Uttaro, et al. Expires August 26, 2010 [Page 4]
Internet-Draft draft-uttaro-idr-add-paths-guidelines Feb 2010
With the use of ADD-PATH, the convergence time for the above path
failure example can be reduced considerably. The main reason for the
improvement is that ADD-PATH allows router D to be aware of more than
one path to destination XYZ prior to the failure of the best path
(A). In steady-state (with no failures) router B decides, as before,
that path (A) is its best path but it also advertises path (B) -
which happens to be its next-best overall path and its best
"external" path - to RR. With ADD-PATH RR1 now has knowledge of all 3
paths to destination XYZ and it can advertise more than just the best
path (A) to its peers. Suppose RR1 is allowed to advertise up to 3
paths for destination XYZ. In this case it will advertise paths (A),
(B) and (C) to router D because (A) is the best path, (B) is the
second best path (if A is excluded from the decision process) and (C)
is the third best path (if A and B are excluded from the decision
process). Now consider again the scenario where the link between
Router A and Router E fails. In this case, with ADD-PATH, fewer steps
are required to achieve re-convergence:
1. Router A sends a BGP UPDATE message withdrawing its advertisement
of path (A).
2. RR1 receives the withdrawal, and propagates it to its other client
peers, routers B, C and D.
3. Router D receives the withdrawal, reruns the decision process and
updates the forwarding entry for destination XYZ.
This one example illustrates the benefit of ADD-PATH in terms of
faster convergence, and it also suggests how other benefits are
realizable as well. As an example, router D can use the knowledge of
multiple paths to perform [un]equal cost load balancing if required.
As with any technology, there are costs to ADD-PATH that must be
considered in relation to the benefits before introducing it into a
network. Specifically -
o Computing multiple best paths per prefix (best, second best, etc.)
is CPU-intensive and can potentially affect the convergence times.
Uttaro, et al. Expires August 26, 2010 [Page 5]
Internet-Draft draft-uttaro-idr-add-paths-guidelines Feb 2010
o Advertising multiple paths per prefix requires more memory and
state than an implementation that advertises only the best path
per prefix. More specifically, with the current behavior of
advertising best path only, each BGP speaker maintains send state
information in its prefix data structure per neighbor as a way to
determine that the prefix has been advertised to the neighbor.
With ADD-PATH, this information has to be replicated on a per path
basis that needs to be advertised. Mathematically, if "send state"
size per prefix is 's' bytes, number of neighbors is 'n', and
number of paths being advertised is 'p', then the current memory
requirement for BGP "send state" = n * s bytes; with ADD-PATH, it
becomes n * s * p bytes.
o Receiving multiple paths per prefix also requires more memory and
state since the number of paths per prefix effectively increases.
o In any BGP deployment it is important that the BGP routers within
an AS make a consistent routing decision about how to reach a
particular destination, otherwise route oscillations may occur.
When using ADD-PATH the opportunity for inconsistent routing
decisions increases and therefore routing policies must be applied
carefully.
2. Conventions used in this document
In this document ADD-PATH peer refers a peer with which the local
system has agreed to receive and/or send NLRI with path identifiers.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC-2119].
3. Implementation Guidelines
3.1. Capability Negotiation
+---+ +---+
|RTR|___________|RTR|
| A | <-BGP-> | B |
+---+ +---+
Figure 2: BGP Peering Example
In Figure 2, in order for a router A to receive multiple paths per
NLRI from peer B, for a particular address family (AFI=x, SAFI=y),
Uttaro, et al. Expires August 26, 2010 [Page 6]
Internet-Draft draft-uttaro-idr-add-paths-guidelines Feb 2010
the BGP capabilities advertisements during session setup must
indicate that peer B wants to send multiple paths for AFI=x, SAFI=y
and that router A is willing to receive multiple paths for AFI=x,
SAFI=y. Similarly, in order for router A to send multiple paths per
NLRI to peer B, for a particular address family (AFI=x, SAFI=y), the
BGP capabilities advertisements must indicate that router A wants to
send multiple paths for AFI=x, SAFI=y and peer B is willing to
receive multiple paths for AFI=x, SAFI=y. Refer to [ADD-PATH] for
details of the ADD-PATH capabilities advertisement.
The capabilities of the local router shall be configurable per peer
and per address family, with the ability to configure send-only
operation or receive-only operation. The default mode of operation
shall be to both send and receive.
3.2. Receiving Multiple Paths
Currently, per standard BGP behavior, if a BGP router receives an
advertisement of an NLRI and path from a specific peer and that peer
subsequently advertises the same NLRI with different path information
(e.g. a different NEXT_HOP and/or different path attributes) the new
path effectively overwrites the existing path.
When ADD-PATH has been negotiated with the peer, the newly advertised
path should be stored in the RIB-IN along with all of the paths
previously advertised (and not withdrawn) by the peer.
When the ADD-PATH receive capability for (AFIx, SAFIy) has been
negotiated with a peer all advertisements and withdrawals of NLRI
within that address family by that peer shall include a path
identifier, as described in [ADD-PATH]. The path identifiers have no
significance to the receiving peer. If the combination of NLRI and
path identifier in an advertisement from a peer is unique (does not
match an existing route in the RIB-IN from that peer) then the route
is added to the RIB-IN. If the combination of NLRI and path
identifier in a received advertisement is the same as an existing
route in the RIB-IN from the peer then the new route replaces the
existing one. If the combination of NLRI and path identifier in a
received withdrawal matches an existing route in the RIB-IN from the
peer then that route shall be removed from the RIB-IN.
A BGP UPDATE message from a peer sending NLRI with the path
identifier may advertise and withdraw more than one NLRI belonging to
one or more address families. In this case ADD-PATH may be supported
for some of the address families and not others. In this situation
the receiving BGP router should not expect that all of the path
identifiers in the UPDATE message will be the same.
Uttaro, et al. Expires August 26, 2010 [Page 7]
Internet-Draft draft-uttaro-idr-add-paths-guidelines Feb 2010
3.3. BGP Decision Process
In order to use multiple paths per NLRI for forwarding and to
advertise multiple paths per NLRI to ADD-PATH peers, a router
implementing ADD-PATH must run a modified version of the BGP decision
process. The existing BGP decision algorithm selects the one best
path (or set of paths tied for best if multipath is enabled) for any
particular NLRI. Paths that are second-best or third-best remain in
the RIB-IN but are not installed in the LOC-RIB and not advertised to
peers.
ADD-PATH modifies the BGP decision process to select up to n paths
for an NLRI, where n should be configurable per BGP instance and per
address family. n is the maximum number of paths per NLRI that can be
installed in the LOC-RIB. If multipath is not enabled then the
decision process finds the single best path, the single second-best
path, the single third-best path, etc. up to n paths. At each
iteration of the process only those paths not selected during a
previous iteration and not having a NEXT_HOP or BGP Identifier (or
Originator ID) in common with the previously-selected paths are
eligible for consideration.
If multipath is enabled (the number of multipaths is configured to be
m, m>1) then the decision process finds up to m best paths, up to m
second-best paths, etc. up to a total of n paths. For example, if n
is configured to be 3 and m (the number of multipaths) is configured
to be 2 then all of the following results are possible:
o 1 best path, 1 second-best-path, 1 third-best path
o 1 best path, 2 second-best paths
o 2 best paths, 1 second-best path
ADD-PATH shall not change the tie-breaking criteria used to determine
whether two paths are equal multipaths.
3.4. Sending Multiple Paths
By default, and unless changed through routing policies, all paths
for a particular NLRI in the LOC-RIB shall be advertised to all ADD-
PATH peers with which the send capability has been negotiated. To all
other peers (non Add-Path peers and ADD-PATH peers that have
indicated they do not want to receive multiple paths) only the single
best path is advertised. A non-best path need not be used for
forwarding in the local system in order for it to be advertised. All
advertisements to ADD-PATH peers (and any subsequent withdrawals)
Uttaro, et al. Expires August 26, 2010 [Page 8]
Internet-Draft draft-uttaro-idr-add-paths-guidelines Feb 2010
shall include a path identifier, as described in [ADD-PATH]. Each
advertised path for a given NLRI must have a unique path identifier.
When a path is reflected or propagated from one peer to another, the
path identifier is expected to change, even if there has been no
change in the NEXT_HOP. A BGP UPDATE message sent to an ADD-PATH peer
may advertise and withdraw more than one NLRI belonging to one or
more address families. In this case ADD-PATH may be supported for
some of the address families and not others and the path identifiers
associated with different NLRI in the UPDATE message SHOULD be the
same.
3.5. Using Multiple Paths for Forwarding
A path must be in the LOC-RIB in order to be used for local
forwarding. ADD-PATH implementations should provide the flexibility
to use all paths in the LOC-RIB for forwarding or a subset. If a
subset is chosen, then the paths in the subset should be equal or
better than the excluded paths as determined by the BGP decision
process. Implementations should provide the flexibility to load-
balance traffic across paths that are determined to be equally-
preferred by the BGP decision process. It should also be possible to
designate some paths as standby paths that are used only after
failure of a more-preferred path.
4. Deployment Guidelines
4.1. Routing Consistency
As stated earlier, inside an IBGP network, it is critical that all
the routers have the correct routing view and there is no
inconsistency in the decision process. It is envisioned that the ADD-
PATH send capability will be enabled on the route reflectors in most
of the networks and that the edge router clients will be enabled with
the ADD-PATH receive capability. In this scenario the route
reflectors will typically announce the exact same paths to each ADD-
PATH capable IBGP peer but if not the following guideline must be
adhered to: if the advertising router (the RR) advertises n paths to
peer_n and m paths to peer_m, and n < m, then all the paths
advertised to peer_n must be included in the paths advertised to
peer_m. If these rules are not followed routing inconsistencies
could occur. Note that it is valid to have a mix of ADD-PATH capable
and non ADD-PATH capable peers and in that case, the non ADD-PATH
capable peers will receive only the best path.
Uttaro, et al. Expires August 26, 2010 [Page 9]
Internet-Draft draft-uttaro-idr-add-paths-guidelines Feb 2010
4.2. ADD-PATH Applications
There are multiple applications of ADD-PATH support in BGP, the main
ones being fast connectivity restoration, load balancing, and
eliminating route oscillation. Depending on the application type, the
number of paths to advertise for a prefix will vary. For example, for
fast connectivity restoration, only one additional path (in addition
to the best path) will suffice to cater to all single point failures.
For load balancing purposes, the number of paths will depend on the
operator requirements and service level agreements (one to all). For
route oscillation elimination, it is required to advertise all group-
best paths for a prefix. Thus it is important to make a distinction
on the application type per prefix or group of prefixes and apply the
route policy on the ADD-PATH advertiser accordingly. This is to make
sure it does not degenerate to advertising all paths for all prefixes
that would create unnecessary burden on the routers.
5. Security Considerations
TBD
6. IANA Considerations
TBD
7. Conclusions
TBD
8. References
8.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
8.2. Informative References
[ADD-PATH] Walton, D., Retana, A., Chen E., Scudder J.,
"Advertisement of Multiple Paths in BGP", February 6,
2010.
9. Acknowledgments
This document was prepared using 2-Word-v2.0.template.dot.
Uttaro, et al. Expires August 26, 2010 [Page 10]
Internet-Draft draft-uttaro-idr-add-paths-guidelines Feb 2010
Authors' Addresses
Jim Uttaro
AT&T
200 S. Laurel Avenue
Middletown, NJ 07748 USA
Email: uttaro@att.com
Roberto Fragassi
Alcatel-Lucent
600 Mountain Avenue
Murray Hill, New Jersey
Email: roberto.fragassi@alcatel-lucent.com
Adam Simpson
Alcatel-Lucent
600 March Road
Ottawa, Ontario K2K 2E6
Canada
Email: adam.simpson@alcatel-lucent.com
Pradosh Mohapatra
Cisco Systems
170 W. Tasman Drive
San Jose, CA 95134 USA
Email: pmohapat@cisco.com
Uttaro, et al. Expires August 26, 2010 [Page 11]