draft-ietf-idr-route-oscillation-00.txt   rfc3345.txt 
Network Working Group Danny McPherson
INTERNET DRAFT Amber Networks, Inc.
Vijay Gill
Metromedia Fiber Network, Inc.
Daniel Walton
Alvaro Retana
March 2001 Cisco Systems, Inc.
BGP Persistent Route Oscillation Condition Network Working Group D. McPherson
<draft-ietf-idr-route-oscillation-00.txt> Request for Comments: 3345 TCB
Category: Informational V. Gill
1. Status of this Memo AOL Time Warner, Inc.
D. Walton
A. Retana
Cisco Systems, Inc.
August 2002
This document is an Internet-Draft and is in full conformance with Border Gateway Protocol (BGP) Persistent Route Oscillation Condition
all provisions of Section 10 of RFC 2026.
Internet-Drafts are working documents of the Internet Engineering Status of this Memo
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 This memo provides information for the Internet community. It does
and may be updated, replaced, or obsoleted by other documents at any not specify an Internet standard of any kind. Distribution of this
time. It is inappropriate to use Internet- Drafts as reference memo is unlimited.
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at Copyright Notice
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at Copyright (C) The Internet Society (2002). All Rights Reserved.
http://www.ietf.org/shadow.html.
2. Abstract Abstract
The Border Gateway Protocol (BGP) [1] is an inter-Autonomous System In particular configurations, the BGP scaling mechanisms defined in
routing protocol. The primary function of a BGP speaking system is to "BGP Route Reflection - An Alternative to Full Mesh IBGP" and
exchange network reachability information with other BGP systems. "Autonomous System Confederations for BGP" will introduce persistent
BGP route oscillation. This document discusses the two types of
persistent route oscillation that have been identified, describes
when these conditions will occur, and provides some network design
guidelines to avoid introducing such occurrences.
It has recently been discovered that in particular configurations, 1. Introduction
the BGP scaling mechanisms defined in "BGP Route Reflection - An
Alternative to Full Mesh IBGP" [2] and "Autonomous System
Confederations for BGP" [3] will introduce persistent BGP route
oscillation[4]. This document discusses the two types of persistent
route oscillation that have been identified, describes when these
conditions will occur, and provides some network design guidelines to
avoid introducing such occurrences.
3. Introduction The Border Gateway Protocol (BGP) is an inter-Autonomous System
routing protocol. The primary function of a BGP speaking system is
to exchange network reachability information with other BGP systems.
It has been known for some time that in particular configurations, In particular configurations, the BGP [1] scaling mechanisms defined
the BGP scaling mechanisms defined in "BGP Route Reflection - An in "BGP Route Reflection - An Alternative to Full Mesh IBGP" [2] and
Alternative to Full Mesh IBGP" [2] and "Autonomous System "Autonomous System Confederations for BGP" [3] will introduce
Confederations for BGP" [3] will introduce persistent BGP route persistent BGP route oscillation.
oscillation.
The problem is inherent in the way BGP works: locally defined routing The problem is inherent in the way BGP works: locally defined routing
policies may conflict globally, and certain types of conflicts can policies may conflict globally, and certain types of conflicts can
cause persistent oscillation of the protocol. Given current cause persistent oscillation of the protocol. Given current
practices, we happen to see the problem manifest itself in the practices, we happen to see the problem manifest itself in the
context of MED + route reflectors or confederations. context of MED + route reflectors or confederations.
The current specification of BGP-4 [5] states that the The current specification of BGP-4 [4] states that the
MULTI_EXIT_DISC is only comparable between routes learned from the MULTI_EXIT_DISC is only comparable between routes learned from the
same neighboring AS. This limitation is consistent with the same neighboring AS. This limitation is consistent with the
description of the attribute: "The MULTI_EXIT_DISC attribute may be description of the attribute: "The MULTI_EXIT_DISC attribute may be
used on external (inter-AS) links to discriminate among multiple exit used on external (inter-AS) links to discriminate among multiple exit
or entry points to the same neighboring AS." [1,5] or entry points to the same neighboring AS." [1,4]
In a full mesh iBGP network, all the internal routers have complete In a full mesh iBGP network, all the internal routers have complete
visibility of the available exit points into a neighboring AS. The visibility of the available exit points into a neighboring AS. The
comparison of the MULTI_EXIT_DISC for only some paths is not a comparison of the MULTI_EXIT_DISC for only some paths is not a
problem. problem.
Because of the scalability implications of a full mesh iBGP network, Because of the scalability implications of a full mesh iBGP network,
two alternatives have been standardized: route reflectors [2] and AS two alternatives have been standardized: route reflectors [2] and AS
confederations [3]. Both alternatives describe methods by which confederations [3]. Both alternatives describe methods by which
route distribution may be achieved without a full iBGP mesh in an AS. route distribution may be achieved without a full iBGP mesh in an AS.
The route reflector alternative defines the ability to re-advertise The route reflector alternative defines the ability to re-advertise
(reflect) iBGP-learned routes to other iBGP peers once the best path (reflect) iBGP-learned routes to other iBGP peers once the best path
is selected [2]. AS Confederations specify the operation of a is selected [2]. AS Confederations specify the operation of a
collection of autonomous systems under a common administration as a collection of autonomous systems under a common administration as a
single entity (i.e. from the outside, the internal topology and the single entity (i.e. from the outside, the internal topology and the
existence of separate autonomous systems are not visible). In both existence of separate autonomous systems are not visible). In both
cases, the reduction of the iBGP full mesh results in the fact that cases, the reduction of the iBGP full mesh results in the fact that
not all the BGP speakers in the AS have complete visibility of the not all the BGP speakers in the AS have complete visibility of the
available exit points into a neighboring AS. In fact, the visibility available exit points into a neighboring AS. In fact, the visibility
may be partial and inconsistent depending on the location (and may be partial and inconsistent depending on the location (and
function) of the router in the AS. function) of the router in the AS.
In certain topologies involving either route reflectors or In certain topologies involving either route reflectors or
confederations (detailed description later in this document), the confederations (detailed description later in this document), the
partial visibility of the available exit points into a neighboring AS partial visibility of the available exit points into a neighboring AS
may result in an inconsistent best path selection decision as the may result in an inconsistent best path selection decision as the
routers don't have all the relevant information. If the routers don't have all the relevant information. If the
inconsistencis span more than one peering router, they may result in inconsistencies span more than one peering router, they may result in
a persistent route oscillation. The best path selection rules a persistent route oscillation. The best path selection rules
applied in this document are consistent with the current applied in this document are consistent with the current
specification [5]. specification [4].
The persistent route oscillation behavior is deterministic and can be The persistent route oscillation behavior is deterministic and can be
avoided by employing some rudimentary BGP network design principles avoided by employing some rudimentary BGP network design principles
until protocol enhancements resolve the problem. until protocol enhancements resolve the problem.
In the following sections a taxonomy of the types of oscillations is In the following sections a taxonomy of the types of oscillations is
presented and a description of the set of conditions that will presented and a description of the set of conditions that will
trigger route oscillations is given. We continue by providing trigger route oscillations is given. We continue by providing
several network design alternatives that remove the potential for several network design alternatives that remove the potential of this
this to occur. occurrence.
It is the intent of the authors that this document serve to increase It is the intent of the authors that this document serve to increase
operator awareness of the problem, as well as to trigger discussion operator awareness of the problem, as well as to trigger discussion
and subsequent proposals for potential protocol enhancements that and subsequent proposals for potential protocol enhancements that
remove the possibly for this to occur. remove the possibility of this to occur.
The oscillations are classified into Type I and Type II depending The oscillations are classified into Type I and Type II depending
upon criteria documented below. upon the criteria documented below.
4. Type I Discussion 2. Discussion of Type I Churn
In the following two subsections we provide configurations under In the following two subsections we provide configurations under
which Type I Churn will occur. We begin with a discussion of the which Type I Churn will occur. We begin with a discussion of the
problem when using Route Reflection, and then discuss the problem as problem when using Route Reflection, and then discuss the problem as
it relates to AS Confederations. it relates to AS Confederations.
In general, Type I Churn occurs only when BOTH of the following In general, Type I Churn occurs only when BOTH of the following
conditions are met: conditions are met:
1) a single-level Route Reflection or AS Confederations 1) a single-level Route Reflection or AS Confederations design is
design is used in the network AND used in the network AND
2) the network accepts the BGP MULTI_EXIT_DISC (MED) 2) the network accepts the BGP MULTI_EXIT_DISC (MED) attribute
attribute from two or more ASs for a single prefix from two or more ASs for a single prefix and the MED values are
and the MED values are unique. unique.
It is also possible for the non-deterministic ordering of paths to It is also possible for the non-deterministic ordering of paths to
cause the route oscillation problem. [1] does not specify that paths cause the route oscillation problem. [1] does not specify that paths
should be ordered based on MEDs but it has been proven that non- should be ordered based on MEDs but it has been proven that non-
deterministic ordering can lead to loops and inconsistent routing deterministic ordering can lead to loops and inconsistent routing
decisions. Most vendors have either implemented deterministic decisions. Most vendors have either implemented deterministic
ordering as default behavior, or provide a knob that permits the ordering as default behavior, or provide a knob that permits the
operator to configure the router to order paths in a deterministic operator to configure the router to order paths in a deterministic
manner based on MEDs. manner based on MEDs.
4.1. Route Reflection and Type I Churn 2.1. Route Reflection and Type I Churn
We now discuss Type I oscillation as it relates to Route Reflection. We now discuss Type I oscillation as it relates to Route Reflection.
To begin, consider the topology depicted in Figure 1: To begin, consider the topology depicted in Figure 1:
--------------------------------------------------------------- ---------------------------------------------------------------
/ -------------------- -------------------- \ / -------------------- -------------------- \
| / \ / \ | | / \ / \ |
| | Cluster 1 | | Cluster 2 | | | | Cluster 1 | | Cluster 2 | |
| | | | | | | | | | | |
| | | *1 | | | | | | *1 | | |
| | Ra(RR) . . . . . . . . . . . . . . Rd(RR) | | | | Ra(RR) . . . . . . . . . . . . . . Rd(RR) | |
| | . . | | . | | | | . . | | . | |
| | .*5 .*4 | | .*12 | | | | .*5 .*4 | | .*12 | |
| | . . | | . | | | | . . | | . | |
| | Rb(C) Rc(C) | | Re(C) | | | | Rb(C) Rc(C) | | Re(C) | |
| | . . | | . | | | | . . | | . | |
| \ . . / \ . / | | \ . . / \ . / |
| ---.------------.--- ---------.---------- | | ---.------------.--- ---------.---------- |
\ .(10) .(1) AS1 .(0) / \ .(10) .(1) AS1 .(0) /
-------.------------.---------------------------.-------------- -------.------------.---------------------------.--------------
. . . . . .
------ . ------------ . ------ . ------------ .
/ \ . / \ . / \ . / \ .
| AS10 | | AS6 | | AS10 | | AS6 |
\ / \ / \ / \ /
------ ------------ ------ ------------
. . . .
. . . .
. -------------- . --------------
. / \ . / \
| AS100 |- 10.0.0.0/8 | AS100 |- 10.0.0.0/8
\ / \ /
-------------- --------------
Figure 1: Example Route Reflection Topology Figure 1: Example Route Reflection Topology
In Figure 1 AS1 contains two Route Reflector Clusters, Clusters 1 and In Figure 1 AS1 contains two Route Reflector Clusters, Clusters 1 and
2. Each Cluster contains one Route Reflector (RR) (i.e., Ra and Rd, 2. Each Cluster contains one Route Reflector (RR) (i.e., Ra and Rd,
respectively). An associated 'RR' in parentheses represents each RR. respectively). An associated 'RR' in parentheses represents each RR.
Cluster 1 contains two RR Clients (Rb and Rc), and Cluster 2 contains Cluster 1 contains two RR Clients (Rb and Rc), and Cluster 2 contains
one RR Client (Re). An associated 'C' in parentheses indicates RR one RR Client (Re). An associated 'C' in parentheses indicates RR
Client status. The dotted lines are used to represent BGP peering Client status. The dotted lines are used to represent BGP peering
sessions. sessions.
The number contained in parentheses on the AS1 EBGP peering sessions The number contained in parentheses on the AS1 EBGP peering sessions
represents the MED value advertised by the peer to be associated with represents the MED value advertised by the peer to be associated with
the 10.0.0.0/8 network reachability advertisement. the 10.0.0.0/8 network reachability advertisement.
The number proceeding each '*' on the IBGP peering sessions repre- The number following each '*' on the IBGP peering sessions represents
sents the additive IGP metrics that are to be associated with the BGP the additive IGP metrics that are to be associated with the BGP
NEXT_HOP attribute for the concerned route. For example, the Ra IGP NEXT_HOP attribute for the concerned route. For example, the Ra IGP
metric value associated with a NEXT_HOP learned via Rb would be 5; metric value associated with a NEXT_HOP learned via Rb would be 5;
while the metric value associated with the NEXT_HOP learned via Re while the metric value associated with the NEXT_HOP learned via Re
would be 13. would be 13.
Table 1 depicts the 10.0.0.0/8 route attributes as seen by routers Table 1 depicts the 10.0.0.0/8 route attributes as seen by routers
Rb, Rc and Re, respectively. Note that the IGP metrics in Figure 1 Rb, Rc and Re, respectively. Note that the IGP metrics in Figure 1
are only of concern when advertising the route to an IBGP peer. are only of concern when advertising the route to an IBGP peer.
Router MED AS_PATH Router MED AS_PATH
-------------------- --------------------
Rb 10 10 100 Rb 10 10 100
Rc 1 6 100 Rc 1 6 100
Re 0 6 100 Re 0 6 100
Table 1: Route Attribute Table
For the following steps 1 through 5 the best path will be marked with Table 1: Route Attribute Table
a '*'.
1) Ra has the following installed in its BGP table with For the following steps 1 through 5, the best path will be marked
the path learned via AS2 marked best: with a '*'.
NEXT_HOP 1) Ra has the following installed in its BGP table, with the path
AS_PATH MED IGP Cost learned via AS2 marked best:
-----------------------
6 100 1 4
* 10 100 10 5
The '10 100' route should not be marked as best, though NEXT_HOP
this is not the cause of the persistent route oscillation. AS_PATH MED IGP Cost
Ra realizes it has the wrong route marked as best since the -----------------------
'6 100' path has a lower IGP metric. As such, Ra makes this 6 100 1 4
change and advertises an UPDATE message to its neighbors to * 10 100 10 5
let them know that it now considers the '6 100, 1, 4' route
as best.
2) Rd receives the UPDATE from Ra, which leaves Rd with the The '10 100' route should not be marked as best, though this is
following installed in its BGP table: not the cause of the persistent route oscillation. Ra realizes
it has the wrong route marked as best since the '6 100' path
has a lower IGP metric. As such, Ra makes this change and
advertises an UPDATE message to its neighbors to let them know
that it now considers the '6 100, 1, 4' route as best.
NEXT_HOP 2) Rd receives the UPDATE from Ra, which leaves Rd with the
AS_PATH MED IGP Cost following installed in its BGP table:
-----------------------
* 6 100 0 12
6 100 1 5
Rd then marks the '6 100, 0, 12' route as best because it has NEXT_HOP
a lower MED. Rd sends an UPDATE message to its neighbors to AS_PATH MED IGP Cost
let them know that this is the best route. -----------------------
* 6 100 0 12
6 100 1 5
3) Ra receives the UPDATE message from Rd and now has the Rd then marks the '6 100, 0, 12' route as best because it has a
following in its BGP table: lower MED. Rd sends an UPDATE message to its neighbors to let
them know that this is the best route.
NEXT_HOP 3) Ra receives the UPDATE message from Rd and now has the
AS_PATH MED IGP Cost following in its BGP table:
-----------------------
6 100 0 13
6 100 1 4
* 10 100 10 5
The first route (6 100, 0, 13) beats the second route (6 100, NEXT_HOP
1, 4) because of lower MED, then the third route (10 100, 10, AS_PATH MED IGP Cost
5) beats the first route because of lower IGP metric to -----------------------
NEXT_HOP. Ra sends an UPDATE message to its peers to let them 6 100 0 13
know its new best route. 6 100 1 4
* 10 100 10 5
4) Rd receives the UPDATE message from Ra, which leaves Rd with the The first route (6 100, 0, 13) beats the second route (6 100,
following BGP table: 1, 4) because of a lower MED. Then the third route (10 100,
10, 5) beats the first route because of lower IGP metric to
NEXT_HOP. Ra sends an UPDATE message to its peers informing
them of the new best route.
NEXT_HOP 4) Rd receives the UPDATE message from Ra, which leaves Rd with
AS_PATH MED IGP Cost the following BGP table:
-----------------------
6 100 0 12
* 10 100 10 6
Rd selects the '10 100, 10, 6' path as best because of the IGP NEXT_HOP
metric. Rd sends an UPDATE/withdraw to its peers to let them AS_PATH MED IGP Cost
know this is its best route. -----------------------
6 100 0 12
* 10 100 10 6
5) Ra receives the UPDATE message from Rd, which leaves Ra with the Rd selects the '10 100, 10, 6' path as best because of the IGP
following BGP table: metric. Rd sends an UPDATE/withdraw to its peers letting them
know this is the best route.
NEXT_HOP 5) Ra receives the UPDATE message from Rd, which leaves Ra with
AS_PATH MED IGP Cost the following BGP table:
-----------------------
6 100 1 4
* 10 100 10 5
Ra received a withdraw for '6 100, 0, 13', which changes what is NEXT_HOP
considered the best route for Ra. AS_PATH MED IGP Cost
This is why Ra has the '10 100, 10, 5' route selected as best in -----------------------
Step 1, even though '6 100, 1, 4' is actually better. 6 100 1 4
* 10 100 10 5
At this point, we've made a full loop and are back at Step 1. The Ra received an UPDATE/withdraw for '6 100, 0, 13', which
router realizes it is using the incorrect best path, and the cycle changes what is considered the best route for Ra. This is why
repeats. This is an example of Type I Churn when using Route Reflec- Ra has the '10 100, 10, 5' route selected as best in Step 1,
tion. even though '6 100, 1, 4' is actually better.
4.2. AS Confederations and Type I Churn At this point, we've made a full loop and are back at Step 1. The
router realizes it is using the incorrect best path, and repeats
the cycle. This is an example of Type I Churn when using Route
Reflection.
We'll now provide an example of Type I Churn occurring with AS Con- 2.2. AS Confederations and Type I Churn
federations. To begin, consider the topology depicted in Figure 2:
--------------------------------------------------------------- Now we provide an example of Type I Churn occurring with AS
/ -------------------- -------------------- \ Confederations. To begin, consider the topology depicted in Figure
| / \ / \ | 2:
| | Sub-AS 65000 | | Sub-AS 65001 | |
| | | | | |
| | | *1 | | |
| | Ra . . . . . . . . . . . . . . . . . Rd | |
| | . . | | . | |
| | .*3 .*2 | | .*6 | |
| | . . | | . | |
| | Rb . . . . . Rc | | Re | |
| | . *5 . | | . | |
| \ . . / \ . / |
| ---.------------.--- ---------.---------- |
\ .(10) .(1) AS1 .(0) /
-------.------------.---------------------------.--------------
. . .
------ . ------------ .
/ \ . / \ .
| AS10 | | AS6 |
\ / \ /
------ ------------
. .
. .
. --------------
. / \
| AS100 |- 10.0.0.0/8
\ /
--------------
Figure 2: Example AS Confederations Topology ---------------------------------------------------------------
/ -------------------- -------------------- \
| / \ / \ |
| | Sub-AS 65000 | | Sub-AS 65001 | |
| | | | | |
| | | *1 | | |
| | Ra . . . . . . . . . . . . . . . . . Rd | |
| | . . | | . | |
| | .*3 .*2 | | .*6 | |
| | . . | | . | |
| | Rb . . . . . Rc | | Re | |
| | . *5 . | | . | |
| \ . . / \ . / |
| ---.------------.--- ---------.---------- |
\ .(10) .(1) AS1 .(0) /
-------.------------.---------------------------.--------------
. . .
------ . ------------ .
/ \ . / \ .
| AS10 | | AS6 |
\ / \ /
------ ------------
. .
. .
. --------------
. / \
| AS100 |- 10.0.0.0/8
\ /
--------------
The number proceeding each '*' on the BGP peering sessions represents Figure 2: Example AS Confederations Topology
the additive IGP metrics that are to be associated with the BGP
NEXT_HOP. The number contained in parentheses on each AS1 EBGP peer-
ing sessions represents the MED value advertised by the peer to be
associated with the 10.0.0.0/8 network reachability advertisement.
The number contained in parentheses on each AS1 EBGP peering sessions The number contained in parentheses on each AS1 EBGP peering session
represents the MED value advertised by the peer to be associated with represents the MED value advertised by the peer to be associated with
the 10.0.0.0/8 network reachability advertisement. the 10.0.0.0/8 network reachability advertisement.
The number proceeding each '*' on the IBGP peering sessions repre- The number following each '*' on the IBGP peering sessions represents
sents the additive IGP metrics that are to be associated with the BGP the additive IGP metrics that are to be associated with the BGP
NEXT_HOP attribute for the concerned route. NEXT_HOP attribute for the concerned route.
For example, the Ra IGP metric value associated with a NEXT_HOP For example, the Ra IGP metric value associated with a NEXT_HOP
learned via Rb would be 5; while the metric value associated with the learned via Rb would be 3; while the metric value associated with the
NEXT_HOP learned via Re would be 13. NEXT_HOP learned via Re would be 6.
Table 2 depicts the 10.0.0.0/8 route attributes as seen by routers Table 2 depicts the 10.0.0.0/8 route attributes as seen by routers
Rb, Rc and Re, respectively. Note that the IGP metrics in Figure 2 Rb, Rc and Re, respectively. Note that the IGP metrics in Figure 2
are only of concern when advertising the route to an IBGP peer. are only of concern when advertising the route to an IBGP peer.
Router MED AS_PATH Router MED AS_PATH
-------------------- --------------------
Rb 10 10 100 Rb 10 10 100
Rc 1 6 100 Rc 1 6 100
Re 0 6 100 Re 0 6 100
Table 2: Route Attribute Table Table 2: Route Attribute Table
For the following steps 1 through 6 the best route will be marked For the following steps 1 through 6 the best route will be marked
with an '*'. with an '*'.
1) Ra has the following BGP table: 1) Ra has the following BGP table:
NEXT_HOP NEXT_HOP
AS_PATH MED IGP Cost AS_PATH MED IGP Cost
------------------------------- -------------------------------
* 10 100 10 3 * 10 100 10 3
(65001) 6 100 0 7 (65001) 6 100 0 7
6 100 1 2 6 100 1 2
The '10 100' route is selected as best and advertised to The '10 100' route is selected as best and is advertised to Rd,
Rd, though this is not the cause of the persistent route though this is not the cause of the persistent route
oscillation. oscillation.
2) Rd has the following in its BGP table: 2) Rd has the following in its BGP table:
NEXT_HOP NEXT_HOP
AS_PATH MED IGP Cost AS_PATH MED IGP Cost
------------------------------- -------------------------------
6 100 0 6 6 100 0 6
* (65000) 10 100 10 4 * (65000) 10 100 10 4
The "(65000) 10 100' route is selected as best because it has The '(65000) 10 100' route is selected as best because it has
the lowest IGP metric. As a result, Rd sends an UPDATE/withdraw the lowest IGP metric. As a result, Rd sends an
to Ra for the '6 100' route that it had previously advertised. UPDATE/withdraw to Ra for the '6 100' route that it had
previously advertised.
3) Ra receives the withdraw from Rd. Ra now has the following in 3) Ra receives the withdraw from Rd. Ra now has the following in
its BGP table: its BGP table:
NEXT_HOP NEXT_HOP
AS_PATH MED IGP Cost AS_PATH MED IGP Cost
------------------------------- -------------------------------
* 10 100 10 3 * 10 100 10 3
6 100 1 2 6 100 1 2
Ra received a withdrawal for '(65001) 6 100', which changes what Ra received a withdraw for '(65001) 6 100', which changes what
is considered the best route for Ra. Ra does not compute the is considered the best route for Ra. Ra does not compute the
best path for a prefix unless its best route was withdrawn. best path for a prefix unless its best route was withdrawn.
This is why Ra has the '10 100, 10, 3' route selected as best, This is why Ra has the '10 100, 10, 3' route selected as best,
even though the '6 100, 1, 2' route is better. even though the '6 100, 1, 2' route is better.
4) Ra realizes that the '6 100' route is better because of the 4) Ra's periodic BGP scanner runs and realizes that the '6 100'
lower IGP metric. Ra sends an UPDATE/withdraw to Rd for the '10 route is better because of the lower IGP metric. Ra sends an
100' route since Ra is now using the '6 100' path as its best UPDATE/withdraw to Rd for the '10 100' route since Ra is now
route. using the '6 100' path as its best route.
Ra's BGP table looks like this: Ra's BGP table looks like this:
NEXT_HOP NEXT_HOP
AS_PATH MED IGP Cost AS_PATH MED IGP Cost
------------------------------- -------------------------------
10 100 10 3 10 100 10 3
* 6 100 1 2 * 6 100 1 2
5) Rd receives the UPDATE from Ra and now has the following in 5) Rd receives the UPDATE from Ra and now has the following in its
its BGP table: BGP table:
NEXT_HOP NEXT_HOP
AS_PATH MED IGP Cost AS_PATH MED IGP Cost
------------------------------- -------------------------------
(65000) 6 100 1 3 (65000) 6 100 1 3
* 6 100 0 6 * 6 100 0 6
Rd selects the '6 100, 0, 5' route as best because of the lower Rd selects the '6 100, 0, 6' route as best because of the lower
MED value. Rd sends an UPDATE message to Ra, reporting that MED value. Rd sends an UPDATE message to Ra, reporting that '6
'6 100, 0 5' is now its best route. 100, 0, 6' is now the best route.
6) Ra receives the UPDATE from Rd. Ra now has the following in its 6) Ra receives the UPDATE from Rd. Ra now has the following in
BGP table: its BGP table:
NEXT_HOP NEXT_HOP
AS_PATH MED IGP Cost AS_PATH MED IGP Cost
------------------------------- -------------------------------
* 10 100 10 3 * 10 100 10 3
(65001) 6 100 0 7 (65001) 6 100 0 7
6 100 1 2 6 100 1 2
At this point we have made a full cycle and are back to step 1. This At this point we have made a full cycle and are back to step 1.
is an example of Type I Churn with AS Confederations. This is an example of Type I Churn with AS Confederations.
4.3. Potential Workarounds for Type I Churn 2.3. Potential Workarounds for Type I Churn
There are a number of alternatives that can be employed to provide There are a number of alternatives that can be employed to avoid this
workarounds to this problem: problem:
1) When using Route Reflection make sure that the inter-Cluster 1) When using Route Reflection make sure that the inter-Cluster
links have a higher IGP metric than the intra-Cluster links. links have a higher IGP metric than the intra-Cluster links.
This is the preferred choice when using Route Reflection. Had This is the preferred choice when using Route Reflection. Had
the inter-Cluster IGP metrics been much larger than the intra- the inter-Cluster IGP metrics been much larger than the intra-
Cluster IGP metrics, the above would not have occurred. Cluster IGP metrics, the above would not have occurred.
2) When using AS Confederations ensure that the inter-Sub-AS 2) When using AS Confederations ensure that the inter-Sub-AS links
links have a higher IGP metric than the intra-Sub-AS links. have a higher IGP metric than the intra-Sub-AS links. This is
This is the preferred option when using AS Confederations. the preferred option when using AS Confederations. Had the
Had the inter-Sub-AS IGP metrics been much larger than the inter-Sub-AS IGP metrics been much larger than the intra-Sub-AS
intra-Sub-AS IGP metrics, the above would not have occurred. IGP metrics, the above would not have occurred.
3) Do not accept MEDs from peers (this may not be a feasible 3) Do not accept MEDs from peers (this may not be a feasible
alternative). alternative).
4) Utilize other BGP attributes higher in the decision process 4) Utilize other BGP attributes higher in the decision process so
so that the BGP decision algorithm never reaches the MED that the BGP decision algorithm never reaches the MED step. As
step. As using this completely overrides MEDs, Option 3 may make using this completely overrides MEDs, Option 3 may make more
more sense. sense.
5) Always compare BGP MEDs, regardless of whether or not they were 5) Always compare BGP MEDs, regardless of whether or not they were
obtained from a single AS. This is probably a bad idea since obtained from a single AS. This is probably a bad idea since
MEDs may be derived in a number of ways, and are typically done MEDs may be derived in a number of ways, and are typically done
so as a matter of operator-specific policy. As such, comparing so as a matter of operator-specific policy. As such, comparing
MED values for a single prefix learned from multiple ASs is MED values for a single prefix learned from multiple ASs is
ill-advised. Of course, this mostly defeats the purpose of MEDs, ill-advised. Of course, this mostly defeats the purpose of
and as such, Option 3 may be a more viable alternative. MEDs, and as such, Option 3 may be a more viable alternative.
6) Use a full IBGP mesh. This is not a feasible solution for 6) Use a full IBGP mesh. This is not a feasible solution for ASs
ASs with a large number of BGP speakers. with a large number of BGP speakers.
5. Type II Discussion 3. Discussion of Type II Churn
In the following subsection we provide configurations under which In the following subsection we provide configurations under which
Type II Churn will occur when using AS Confederations. For sake of Type II Churn will occur when using AS Confederations. For the sake
brevity, we avoid similar discussion of the occurrence when using of brevity, we avoid similar discussion of the occurrence when using
Route Reflection. Route Reflection.
In general, Type II churn occurs only when BOTH of the following con- In general, Type II churn occurs only when BOTH of the following
ditions are met: conditions are met:
1) More than one tier of Route Reflection or Sub-ASs 1) More than one tier of Route Reflection or Sub-ASs is used in
is used in the network AND the network AND
2) the network accepts the BGP MULTI_EXIT_DISC (MED) 2) the network accepts the BGP MULTI_EXIT_DISC (MED) attribute
attribute from two or more ASs for a single prefix from two or more ASs for a single prefix and the MED values are
and the MED values are unique. unique.
5.1. AS Confederations and Type II Churn 3.1. AS Confederations and Type II Churn
Let's now examine the occurrence of Type II Churn as it relates to AS Let's now examine the occurrence of Type II Churn as it relates to AS
Confederations. Figure 3 provides our sample topology: Confederations. Figure 3 provides our sample topology:
--------------------------------------------------------------- ---------------------------------------------------------------
/ -------------------- \ / ------------------- \
| AS N / Sub-AS 65500 \ | | AS 1 / Sub-AS 65500 \ |
| | | | | | | |
| | Rc . . . . Rd | | | | Rc . . . . Rd | |
| | . *2 . | | | | . *2 . | |
| \ . . / | | \ . . / |
| -.---------------.-- | | .-----------------. |
| .*40 .*40 | | .*40 .*40 |
| --------------.----- .------------------- | | --------------.----- --.----------------- |
| / . \ / . \ | | / . \ / . \ |
| | Sub-AS . | | . Sub-AS | | | | Sub-AS . | | . Sub-AS | |
| | 65501 . | | . 65502 | | | | 65501 . | | . 65502 | |
| | Rb | | Re | | | | Rb | | Re | |
| | . | | . . | | | | . | | . . | |
| | .*10 | | *3. .*2 | | | | .*10 | | *2. .*3 | |
| | . | | . . | | | | . | | . . | |
| | Ra . | | . Rf . . . Rg | | | | Ra | | . Rg . . . Rf | |
| \ . / . . / | | \ . / . . / |
| -----------------.--- . -----------.--------- | | ----------.---------- . -------------.------- |
\ (0) . .() .(1) / \ .(0) .(1) .() /
---------------------------.----.---------------.-------------- ----------------.---------------.-------------------.----------
. .
------ . . ------------
|AS X| | AS Y |
------ ------------
Figure 3: Example AS Confederations Topology . . .
--------- . ---------
|AS 200 | |AS 300 |
--------- ---------
. .
. .
-------------------
| AS 400 | - 10.0.0.0/8
-------------------
In Figure 3 AS N contains three Sub-ASs, 65500, 65501 and Figure 3: Example AS Confederations Topology
65502. No RR is used within the Sub-AS, and as such, all routers
within each Sub-AS are fully meshed. Ra and Rb are members of Sub-AS In Figure 3 AS 1 contains three Sub-ASs, 65500, 65501 and 65502. No
65501. Rc and Rd are members of Sub-AS 65500. Ra and Rg are EBGP RR is used within the Sub-AS, and as such, all routers within each
peering with AS Y, router Rf has an EBGP peering with AS X. The Sub-AS are fully meshed. Ra and Rb are members of Sub-AS 65501. Rc
and Rd are members of Sub-AS 65500. Ra and Rg are EBGP peering with
AS 200, router Rf has an EBGP peering with AS 300. AS 200 and AS 300
provide transit for AS 400, and in particular, the 10/8 network. The
dotted lines are used to represent BGP peering sessions. dotted lines are used to represent BGP peering sessions.
The number proceeding each '*' on the BGP peering sessions The number following each '*' on the BGP peering sessions represents
represents the additive IGP metrics that are to be associated with the additive IGP metrics that are to be associated with the BGP
the BGP NEXT_HOP. The number contained in parentheses on each AS N NEXT_HOP. The number contained in parentheses on each AS 1 EBGP
EBGP peering session represents the MED value advertised by the peer peering session represents the MED value advertised by the peer to be
to be associated with the network reachability advertisement(s). associated with the network reachability advertisement (10.0.0.0/8).
Rc, Rd and Re are the primary routers involved in the churn, and as Rc, Rd and Re are the primary routers involved in the churn, and as
such, will be the only BGP tables that we will monitor step by step. such, will be the only BGP tables that we will monitor step by step.
For the following steps 1 through 8 each routers best route will be For the following steps 1 through 8 each router's best route will be
marked with a '*'. marked with a '*'.
1) Re receives the 'X' and 'Y1' paths. Re selects 'Y1' because of 1) Re receives the AS 400 10.0.0.0/8 route advertisement via AS
IGP metric. 200 from Rg and AS 300 from Rf. Re selects the path via Rg and
AS 200 because of IGP metric (Re didn't consider MED because
the advertisements were received from different ASs).
NEXT_HOP NEXT_HOP
Router AS_PATH MED IGP Cost Router AS_PATH MED IGP Cost
------------------------------ ------------------------------
Re X 3 Re * 200 400 1 2
* Y 1 2 300 400 3
Re will advertise its new best path to Rd. Re sends an UPDATE message to Rd advertising its new best path
'200 400, 1'.
2) The 'Y0' path was passed from Ra to Rb, and then from Rb 2) The '200 400, 0' path was advertised from Ra to Rb, and then
to Rc. Rd learns the 'Y1' path from Re. Rc selects 'Y0', from Rb to Rc. Rd learns the '200 400, 1' path from Re.
Rd selects 'Y1'.
NEXT_HOP NEXT_HOP
Router AS_PATH MED IGP Cost Router AS_PATH MED IGP Cost
------------------------------- -------------------------------
Rc * Y 0 50 Rc * 200 400 0 50
Rd * Y 1 42 Rd * 200 400 1 42
Re X 3 Re 300 400 3
* Y 1 2 * 200 400 1 2
3) Rc and Rd advertise their best paths to each other; 3) Rc and Rd advertise their best paths to each other; Rd selects
Rd selects 'Y0' because of MED. '200 400, 0' because of the MED.
NEXT_HOP NEXT_HOP
Router AS_PATH MED IGP Cost Router AS_PATH MED IGP Cost
------------------------------ ------------------------------
Rc * Y 0 50 Rc * 200 400 0 50
Y 1 44 200 400 1 44
Rd * Y 0 52 Rd * 200 400 0 52
Y 1 42 200 400 1 42
Re X 3 Re 300 400 3
* Y 1 2 * 200 400 1 2
Rd has a new best path so he will send an advertisement Rd has a new best path so it sends an UPDATE to to Re,
to Re and send a withdraw for 'Y1' to Rc. announcing the new path and an UPDATE/withdraw for '200 400, 1'
to Rc.
4) Re selects 'X' per 'Y0' beats 'Y1' because of the MED. 4) Re now selects '300 400' (with no MED) because '200 400, 0'
'X' beats 'Y0' because of IGP metric. beats '200 400, 1' based on MED and '300 400' beats '200 400,
0' because of IGP metric.
NEXT_HOP NEXT_HOP
Router AS_PATH MED IGP Cost Router AS_PATH MED IGP Cost
------------------------------ ------------------------------
Rc * Y 0 50 Rc * 200 400 0 50
Rd * Y 0 52 Rd * 200 400 0 52
Y 1 42 200 400 1 42
Re * X 3 Re * 300 400 3
Y 0 92 200 400 0 92
5) Rd selects 'X' because of IGP metric. Re has a new best path and sends an UPDATE to Rd for '300 400'.
NEXT_HOP 5) Rd selects the '300 400' path because of IGP metric.
Router AS_PATH MED IGP Cost
------------------------------
Rc * Y 0 50
Rd Y 0 52
* X 43
Re * X 3
Y 0 92
Y 1 2
Rd has a new best path so he will send an UPDATE to Rc NEXT_HOP
and an UPDATE/withdraw to Re for 'Y0'. Router AS_PATH MED IGP Cost
------------------------------
Rc * 200 400 0 50
Rd 200 400 0 52
* 300 400 43
Re * 300 400 3
200 400 0 92
200 400 1 2
6) Rc selects 'X' because of IGP metric. Re selects 'Y1' Rd has a new best path so it sends an UPDATE to Rc and a
because of IGP metric. UPDATE/withdraw to Re for '200 400, 0'.
NEXT_HOP 6) Rc selects '300 400' because of the IGP metric. Re selects
Router AS_PATH MED IGP Cost '200 400, 1' because of the IGP metric.
------------------------------
Rc Y 0 50
* X 45
Rd Y 0 52
* X 43
Re X 3
* Y 1 2
7) Rd selects 'Y1'. NEXT_HOP
Router AS_PATH MED IGP Cost
------------------------------
Rc 200 400 0 50
* 300 400 45
Rd 200 400 0 52
* 300 400 43
Re 300 400 3
* 200 400 1 2
NEXT_HOP Rc sends an UPDATE/withdraw for '200 400, 0' to Rd. Re sends
Router AS_PATH MED IGP Cost an UPDATE for '200 400, 1' to Rd.
------------------------------
Rc Y 0 50
* X 45
Rd * Y 1 42
Re X 3
* Y 1 2
8) Rc selects 'Y0'. 7) Rd selects '200 400, 1' as its new best path based on the IGP
metric.
NEXT_HOP NEXT_HOP
Router AS_PATH MED IGP Cost Router AS_PATH MED IGP Cost
------------------------------ ------------------------------
Rc * Y 0 50 Rc 200 400 0 50
Y 1 44 * 300 400 45
Rd * Y 1 42 Rd * 200 400 1 42
Re X 3 Re 300 400 3
* Y 1 2 * 200 400 1 2
At this point we are back to Step 2 and are in a loop. Rd sends an UPDATE to Rc, announcing '200 400, 1' and
implicitly withdraws '300 400'.
5.2. Potential Workarounds for Type II Churn 8) Rc selects '200 400, 0'.
1) Do not accept MEDs from peers (this may not be a feasible NEXT_HOP
alternative). Router AS_PATH MED IGP Cost
------------------------------
Rc * 200 400 0 50
200 400 1 44
Rd * 200 400 1 42
Re 300 400 3
* 200 400 1 2
2) Utilize other BGP attributes higher in the decision process so At this point we are back to Step 2 and are in a loop.
that the BGP decision algorithm selects a single AS before it
reaches the MED step. For example, if local-pref were set based
on the advertising AS, then you first eliminated all routes
except those in a single AS. In the example, router Re
would pick either X or Y based on local-pref and never change
that selection.
This leaves two simple workarounds for the two types of problems. 3.2. Potential Workarounds for Type II Churn
Type I: Make inter-cluster or inter-sub-AS link metrics higher 1) Do not accept MEDs from peers (this may not be a feasible
than intra-cluster or intra-sub-AS metrics. alternative).
Type II: Make route selections based on local pref assigned to 2) Utilize other BGP attributes higher in the decision process so
advertising AS first and then used IGP cost and MED that the BGP decision algorithm selects a single AS before it
to make selection among routes from the same AS. reaches the MED step. For example, if local-pref were set based
on the advertising AS, then you first eliminate all routes except
those in a single AS. In the example, router Re would pick either
X or Y based on your local-pref and never change selections.
Note that this requires per-prefix policies, as well as near This leaves two simple workarounds for the two types of problems.
intimate knowledge of other networks by the network operator.
The authors are not aware of ANY [large] provider today that
performs per-prefix policies on routes learned from peers.
Implicitly removing this dynamic portion of route selection
does not appear to be a viable option in today's networks.
The main point is that an available workaround using
local_pref so no two AS advertise a given prefix at the same
local_pref solves type II churn.
3) Always compare BGP MEDs, regardless of whether or not they were Type I: Make inter-cluster or inter-sub-AS link metrics higher
obtained from a single AS. This is probably a bad idea since than intra-cluster or intra-sub-AS metrics.
MEDs may be derived in a number of ways, and are typically done
so as a matter of operator-specific policy and largely a function
of available metric space provided by the employed IGP. As such,
comparing MED values for a single prefix learned from multiple
ASs is ill-advised. This mostly defeats the purpose of MEDs;
Option 1 may be a more viable alternative.
4) Do not use more than one tier of Route Reflection or Sub-ASs Type II: Make route selections based on local-pref assigned to the
in the network. The risk of route oscillation should be advertising AS first and then use IGP cost and MED to make
considered when desiging networks that might use a multi-tiered selection among routes from the same AS.
routing isolation architecture.
5) In a RR topology, mesh the clients. For confederations, mesh Note that this requires per-prefix policies, as well as near
the border routers at each level in the hierarchy. In intimate knowledge of other networks by the network operator. The
Figure 3, for example, if Rb and Re are peers, then there's authors are not aware of ANY [large] provider today that performs
no churn. per-prefix policies on routes learned from peers. Implicitly
removing this dynamic portion of route selection does not appear
to be a viable option in today's networks. The main point is that
an available workaround using local-pref so that no two AS's
advertise a given prefix at the same local-pref solves type II
churn.
Future drafts will propose other solutions for Type II Churn 3) Always compare BGP MEDs, regardless of whether or not they were
obtained from a single AS. This is probably a bad idea since MEDs
may be derived in a number of ways, and are typically done so as a
matter of operator-specific policy and largely a function of
available metric space provided by the employed IGP. As such,
comparing MED values for a single prefix learned from multiple ASs
is ill-advised. This mostly defeats the purpose of MEDs; Option 1
may be a more viable alternative.
6. Future Works 4) Do not use more than one tier of Route Reflection or Sub-ASs in
the network. The risk of route oscillation should be considered
when designing networks that might use a multi-tiered routing
isolation architecture.
5) In a RR topology, mesh the clients. For confederations, mesh the
border routers at each level in the hierarchy. In Figure 3, for
example, if Rb and Re are peers, then there's no churn.
4. Future Work
It should be stated that protocol enhancements regarding this problem It should be stated that protocol enhancements regarding this problem
must be pursued. Imposing network design requirements such as those must be pursued. Imposing network design requirements, such as those
outlined above are clearly an unreasonable long-term solution. Prob- outlined above, are clearly an unreasonable long-term solution.
lems such as this should not occur under 'default' configurations. Problems such as this should not occur under 'default' protocol
configurations.
7. Security Considerations 5. Security Considerations
This discussion introduces no new security concerns to BGP or other This discussion introduces no new security concerns to BGP or other
specifications referenced in this document. specifications referenced in this document.
8. Acknowledgments 6. Acknowledgments
The authors would like to thank: Curtis Villamizar, Tim Griffin, John
Scudder and Ron Da Silva.
9. References The authors would like to thank Curtis Villamizar, Tim Griffin, John
Scudder, Ron Da Silva, Jeffrey Haas and Bill Fenner.
[1] Rekhter, Y., and T. Li, "A Border Gateway Protocol 4 (BGP-4)", 7. References
RFC 1771, March 1995.
[2] Bates, T., Chandra, R., Chen, E., "BGP Route Reflection - An [1] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4 (BGP-4)", RFC
Alternative to Full Mesh IBGP", RFC 2796, April 2000. 1771, March 1995.
[3] Traina, P., McPherson, D., Scudder, J.. "Autonomous System [2] Bates, T., Chandra, R. and E. Chen, "BGP Route Reflection - An
Confederations for BGP", RFC 1965bis, "Work In Progress", Alternative to Full Mesh IBGP", RFC 2796, April 2000.
October 2000.
[4] Cisco Systems, Inc., "Endless BGP Convergence Problem in Cisco [3] Traina, P., McPherson, D. and J. Scudder, J., "Autonomous System
IOS Software Releases" , FN, October 10, 2000. Confederations for BGP", RFC 3065, February 2001.
[5] Rekhter, Y., and T. Li, "A Border Gateway Protocol 4 (BGP-4)", [4] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4 (BGP-4)",
Work in Progress (draft-ietf-idr-bgp4-12.txt), March 2001. Work in Progress.
10. Authors' Addresses 8. Authors' Addresses
Danny McPherson Danny McPherson
Amber Networks, Inc. TCB
48664 Milmont Drive EMail: danny@tcb.net
Fremont, CA 94538
Email: danny@ambernetworks.com
Vijay Gill Vijay Gill
Metromedia Fiber Network, Inc. AOL Time Warner, Inc.
8075 Leesburg Pike, STE 3 12100 Sunrise Valley Drive
Vienna, VA, 22182 Reston, VA 20191
Email: vijay@umbc.edu EMail: vijay@umbc.edu
Daniel Walton Daniel Walton
Cisco Systems, Inc. Cisco Systems, Inc.
7025 Kit Creek Rd. 7025 Kit Creek Rd.
Research Triangle Park, NC 27709 Research Triangle Park, NC 27709
Email: dwalton@cisco.com EMail: dwalton@cisco.com
Alvaro Retana Alvaro Retana
Cisco Systems, Inc. Cisco Systems, Inc.
7025 Kit Creek Rd. 7025 Kit Creek Rd.
Research Triangle Park, NC 27709 Research Triangle Park, NC 27709
Email: aretana@cisco.com EMail: aretana@cisco.com
9. Full Copyright Statement
Copyright (C) The Internet Society (2002). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
 End of changes. 138 change blocks. 
505 lines changed or deleted 499 lines changed or added

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/