Network Working Group Danny McPherson
INTERNET DRAFT Amber Networks, Inc.
Vijay Gill
Metromedia Fiber Network, Inc.
Daniel Walton
Alvaro Retana
December 2000 Cisco Systems, Inc.
BGP Persistent Route Oscillation Condition
<draft-mcpherson-bgp-route-oscillation-00.txt>
1. Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC 2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet- Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
2. Abstract
The Border Gateway Protocol (BGP) [1] 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 recently been discovered that in particular configurations,
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
McPherson, Gill, Walton, Retana [Page 1]
INTERNET DRAFT December 2000
avoid introducing such occurrences.
3. Specification of Requirements
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 [5].
4. Introduction
It has been known for some time that in particular configurations,
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.
The persistent route oscillation behavior is deterministic and can be
avoided by employing some rudimentary BGP network design principles
until protocol enhancements resolve the problem.
In the following sections a taxonomy of the types of oscillations is
presented and a description of the set of conditions that will
trigger route oscillations is given. We continue by providing
several network design alternatives that remove the potential for
this to occur.
It is the intent of the authors that this document serve to increase
operator awareness of the problem, as well as to trigger discussion
and subsequent proposals for potential protocol enhancements that
remove the possibly for this to occur.
The oscillations are classified into Type I and Type II depending
upon criteria documented below.
5. Type I Discussion
In the following two subsections we provide configurations under
which Type I Churn will occur. We begin with a discussion of the
problem when using Route Reflection, and then discuss the problem as
it relates to AS Confederations.
In general, Type I Churn occurs only when BOTH of the following
conditions are met:
1) a single-level Route Reflection or AS Confederations
design is used in the network AND
2) the network accepts the BGP MULTI_EXIT_DISC (MED)
McPherson, Gill, Walton, Retana [Page 2]
INTERNET DRAFT December 2000
attribute from two or more ASs for a single prefix
and the MED values are unique.
It is also possible for the non-deterministic ordering of paths to
cause the route oscillation problem. [1] does not specify that paths
should be ordered based on MEDs but it has been proven that non-
deterministic ordering can lead to loops and inconsistent routing
decisions. Most vendors have either implemented deterministic
ordering as default behavior, or provide a knob that permits the
operator to configure the router to order paths in a deterministic
manner based on MEDs.
5.1. Route Reflection and Type I Churn
We now discuss Type I oscillation as it relates to Route Reflection.
To begin, consider the topology depicted in Figure 1:
McPherson, Gill, Walton, Retana [Page 3]
INTERNET DRAFT December 2000
---------------------------------------------------------------
/ -------------------- -------------------- \
| / \ / \ |
| | Cluster 1 | | Cluster 2 | |
| | | | | |
| | | *1 | | |
| | Ra(RR) . . . . . . . . . . . . . . Rd(RR) | |
| | . . | | . | |
| | .*5 .*4 | | .*12 | |
| | . . | | . | |
| | Rb(C) Rc(C) | | Re(C) | |
| | . . | | . | |
| \ . . / \ . / |
| ---.------------.--- ---------.---------- |
\ .(10) .(1) AS1 .(0) /
-------.------------.---------------------------.--------------
. . .
------ . ------------ .
/ \ . / \ .
| AS10 | | AS6 |
\ / \ /
------ ------------
. .
. .
. --------------
. / \
| AS100 |- 10.0.0.0/8
\ /
--------------
Figure 1: Example Route Reflection Topology
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,
respectively). An associated 'RR' in parentheses represents each RR.
Cluster 1 contains two RR Clients (Rb and Rc), and Cluster 2 contains
one RR Client (Re). An associated 'C' in parentheses indicates RR
Client status. The dotted lines are used to represent BGP 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
the 10.0.0.0/8 network reachability advertisement.
The number proceeding each '*' on the IBGP peering sessions
McPherson, Gill, Walton, Retana [Page 4]
INTERNET DRAFT December 2000
represents the additive IGP metrics that are to be associated with
the BGP 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; while the metric value associated with the NEXT_HOP learned via
Re would be 13.
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
are only of concern when advertising the route to an IBGP peer.
Router MED AS_PATH
--------------------
Rb 10 10 100
Rc 1 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
a '*'.
1) Ra has the following installed in its BGP table with
the path learned via AS2 marked best:
NEXT_HOP
AS_PATH MED IGP Cost
-----------------------
6 100 1 4
* 10 100 10 5
The '10 100' route should not be marked as best, though
this is 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.
2) Rd receives the UPDATE from Ra, which leaves Rd with the
following installed in its BGP table:
NEXT_HOP
AS_PATH MED IGP Cost
-----------------------
* 6 100 0 12
6 100 1 5
McPherson, Gill, Walton, Retana [Page 5]
INTERNET DRAFT December 2000
Rd then marks the '6 100, 0, 12' route as best because it has
a lower MED. Rd sends an UPDATE message to its neighbors to
let them know that this is the best route.
3) Ra receives the UPDATE message from Rd and now has the
following in its BGP table:
NEXT_HOP
AS_PATH MED IGP Cost
-----------------------
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,
1, 4) because of 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 to let them
know its new best route.
4) Rd receives the UPDATE message from Rc, which leaves Rd with the
following BGP table:
NEXT_HOP
AS_PATH MED IGP Cost
-----------------------
6 100 0 12
* 10 100 10 6
Rd selects the '10 100, 10, 6' path as best because of the IGP
metric. Rd sends an UPDATE/withdraw to its peers to let them
know this is its best route.
5) Ra receives the UPDATE message from Rd, which leaves Ra with the
following BGP table:
NEXT_HOP
AS_PATH MED IGP Cost
-----------------------
6 100 1 4
* 10 100 10 5
Ra received a withdraw for '6 100, 0, 13', which changes what is
considered the best route for Ra.
This is why Ra has the '10 100, 10, 5' route selected as best in
McPherson, Gill, Walton, Retana [Page 6]
INTERNET DRAFT December 2000
Step 1, even though '6 100, 1, 4' is actually better.
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 the cycle
repeats. This is an example of Type I Churn when using Route Reflec-
tion.
5.2. AS Confederations and Type I Churn
We'll now provide an example of Type I Churn occurring with AS Con-
federations. To begin, consider the topology depicted in Figure 2:
McPherson, Gill, Walton, Retana [Page 7]
INTERNET DRAFT December 2000
---------------------------------------------------------------
/ -------------------- -------------------- \
| / \ / \ |
| | 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
The number proceeding each '*' on the BGP peering sessions represents
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
represents the MED value advertised by the peer to be associated with
the 10.0.0.0/8 network reachability advertisement.
The number proceeding each '*' on the IBGP peering sessions repre-
sents the additive IGP metrics that are to be associated with the BGP
NEXT_HOP attribute for the concerned route.
McPherson, Gill, Walton, Retana [Page 8]
INTERNET DRAFT December 2000
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
NEXT_HOP learned via Re would be 13.
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
are only of concern when advertising the route to an IBGP peer.
Router MED AS_PATH
--------------------
Rb 10 10 100
Rc 1 6 100
Re 0 6 100
Table 2: Route Attribute Table
For the following steps 1 through 6 the best route will be marked
with an '*'.
1) Ra has the following BGP table:
NEXT_HOP
AS_PATH MED IGP Cost
-------------------------------
* 10 100 10 3
(65001) 6 100 0 7
6 100 1 2
The '10 100' route is selected as best and advertised to
Rd, though this is not the cause of the persistent route
oscillation.
2) Rd has the following in its BGP table:
NEXT_HOP
AS_PATH MED IGP Cost
-------------------------------
6 100 0 6
* (65000) 10 100 10 4
The "(65000) 10 100' route is selected as best because it has
the lowest IGP metric. As a result, Rd sends an 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
McPherson, Gill, Walton, Retana [Page 9]
INTERNET DRAFT December 2000
its BGP table:
NEXT_HOP
AS_PATH MED IGP Cost
-------------------------------
* 10 100 10 3
6 100 1 2
Ra received a withdrawal for '(65001) 6 100', which changes what
is considered the best route for Ra. Ra does not compute the
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,
even though the '6 100, 1, 2' route is better.
4) Ra realizes that the '6 100' route is better because of the
lower IGP metric. Ra sends an UPDATE/withdraw to Rd for the '10
100' route since Ra is now using the '6 100' path as its best
route.
Ra's BGP table looks like this:
NEXT_HOP
AS_PATH MED IGP Cost
-------------------------------
10 100 10 3
* 6 100 1 2
5) Rd receives the UPDATE from Ra and now has the following in
its BGP table:
NEXT_HOP
AS_PATH MED IGP Cost
-------------------------------
(65000) 6 100 1 4
* 6 100 0 5
Rd selects the '6 100, 0, 5' route as best because of the lower
MED value. Rd sends an UPDATE message to Ra, reporting that
'6 100, 0 5' is now its best route.
6) Ra receives the UPDATE from Rd. Ra now has the following in its
BGP table:
NEXT_HOP
AS_PATH MED IGP Cost
-------------------------------
* 10 100 10 3
(65001) 6 100 0 7
McPherson, Gill, Walton, Retana [Page 10]
INTERNET DRAFT December 2000
6 100 1 2
At this point we have made a full cycle and are back to step 1.
This is an example of Type I Churn with AS Confederations.
5.3. Potential Workarounds for Type I Churn
There are a number of alternatives that can be employed to provide
workarounds to this problem:
1) When using Route Reflection make sure that the inter-Cluster
links have a higher IGP metric than the intra-Cluster links.
This is the preferred choice when using Route Reflection. Had
the inter-Cluster IGP metrics been much larger than the intra-
Cluster IGP metrics, the above would not have occurred.
2) When using AS Confederations ensure that the inter-Sub-AS
links have a higher IGP metric than the intra-Sub-AS links.
This is the preferred option when using AS Confederations.
Had the inter-Sub-AS IGP metrics been much larger than the
intra-Sub-AS IGP metrics, the above would not have occurred.
3) Do not accept MEDs from peers (this may not be a feasible
alternative).
4) Utilize other BGP attributes higher in the decision process
so that the BGP decision algorithm never reaches the MED
step. As using this completely overrides MEDs, Option 3 may make
more sense.
5) 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. As such, comparing
MED values for a single prefix learned from multiple ASs is
ill-advised. Of course, this mostly defeats the purpose of 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
ASs with a large number of BGP speakers.
McPherson, Gill, Walton, Retana [Page 11]
INTERNET DRAFT December 2000
6. Type II Discussion
In the following subsection we provide configurations under which
Type II Churn will occur when using AS Confederations. For sake of
brevity, we avoid similar discussion of the occurrence when using
Route Reflection.
In general, Type II churn occurs only when BOTH of the following con-
ditions are met:
1) More than one tier of Route Reflection or Sub-ASs
is used in the network AND
2) the network accepts the BGP MULTI_EXIT_DISC (MED)
attribute from two or more ASs for a single prefix
and the MED values are unique.
6.1. AS Confederations and Type II Churn
Let's now examine the occurrence of Type II Churn as it relates to AS
Confederations. Figure 3 provides our sample topology:
McPherson, Gill, Walton, Retana [Page 12]
INTERNET DRAFT December 2000
---------------------------------------------------------------
/ -------------------- \
| AS N / Sub-AS 65500 \ |
| | | |
| | Rc . . . . Rd | |
| | . *2 . | |
| \ . . / |
| -.---------------.-- |
| .*40 .*40 |
| --------------.----- .------------------- |
| / . \ / . \ |
| | Sub-AS . | | . Sub-AS | |
| | 65502 . | | . 65502 | |
| | Rb | | Re | |
| | . | | . . | |
| | .*10 | | *3. .*2 | |
| | . | | . . | |
| | Ra . | | . Rf . . . Rg | |
| \ . / . . / |
| -----------------.--- . -----------.--------- |
\ (0) . .() .(1) /
---------------------------.----.---------------.--------------
. .
------ . . ------------
|AS X| | AS Y |
------ ------------
Figure 3: Example AS Confederations Topology
In Figure 3 AS N contains three Sub-ASs, 65500, 65501 and
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
65501. Rc and Rd are members of Sub-AS 65500. Ra and Rg are EBGP
peering with AS Y, router Rf has an EBGP peering with AS X. The
dotted lines are used to represent BGP peering sessions.
The number proceeding each '*' on the BGP peering sessions
represents the additive IGP metrics that are to be associated with
the BGP NEXT_HOP. The number contained in parentheses on each AS N
EBGP peering session represents the MED value advertised by the peer
to be associated with the network reachability advertisement(s).
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.
For the following steps 1 through 8 each routers best route will be
McPherson, Gill, Walton, Retana [Page 13]
INTERNET DRAFT December 2000
marked with a '*'.
1) Re receives the 'X' and 'Y1' paths. E selects 'Y1' because of
IGP metric.
NEXT_HOP
Router AS_PATH MED IGP Cost
------------------------------
Re X 3
* Y 1 2
Re will advertise his new best path to Rd.
2) The 'Y0' path was passed from Ra to Rb, and then from Rb
to Rc. Rd learns the 'Y1' path from Re. Rc selects 'Y0',
Rd selects 'Y1'.
NEXT_HOP
Router AS_PATH MED IGP Cost
-------------------------------
Rc * Y 0 50
Rd * Y 1 42
Re X 3
* Y 1 2
3) Rc and Rd advertise their best paths to each other;
Rd selects 'Y0' because of MED.
NEXT_HOP
Router AS_PATH MED IGP Cost
------------------------------
Rc * Y 0 50
Y 1 44
Rd * Y 0 52
Y 1 42
Re X 3
* Y 1 2
Rd has a new best path so he will send an advertisement
to Re and send a withdraw for 'Y1' to Rc.
4) Re selects 'X' per 'Y0' beats 'Y1' because of the MED.
'X' beats 'Y0' because of IGP metric.
McPherson, Gill, Walton, Retana [Page 14]
INTERNET DRAFT December 2000
NEXT_HOP
Router AS_PATH MED IGP Cost
------------------------------
Rc * Y 0 50
Rd * Y 0 52
Y 1 42
Re * X 3
Y 0 92
5) Rd selects 'X' because of IGP metric.
NEXT_HOP
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
and an UPDATE/withdraw to Re for 'Y0'.
6) Rc selects 'X' because of IGP metric. Re selects 'Y1'
because of IGP metric.
NEXT_HOP
Router AS_PATH MED IGP Cost
------------------------------
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 Y 0 50
* X 45
Rd * Y 1 42
Re X 3
* Y 1 2
McPherson, Gill, Walton, Retana [Page 15]
INTERNET DRAFT December 2000
8) Rc selects 'Y0'.
NEXT_HOP
Router AS_PATH MED IGP Cost
------------------------------
Rc * Y 0 50
Y 1 44
Rd * Y 1 42
Re X 3
* Y 1 2
At this point we are back to Step 2 and are in a loop.
6.2. Potential Workarounds for Type II Churn
1) Do not accept MEDs from peers (this may not be a feasible
alternative).
2) Utilize other BGP attributes higher in the decision process
so that the BGP decision algorithm never reaches the MED
step. As this completely overrides MEDs, Option 1 may make
more sense.
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.
4) Future drafts will propose other solutions for Type II Churn
7. Future Works
It should be stated that protocol enhancements regarding this problem
must be pursued. Imposing network design requirements such as those
outlined above are clearly an unreasonable long-term solution. Prob-
lems such as this should not occur under 'default' configurations.
McPherson, Gill, Walton, Retana [Page 16]
INTERNET DRAFT December 2000
8. Security Considerations
This discussion introduces no new security concerns to BGP or other
specifications referenced in this document.
9. Acknowledgments
To be supplied.
10. References
[1] Rekhter, Y., and T. Li, "A Border Gateway Protocol 4 (BGP-4)",
RFC 1771, March 1995.
[2] Bates, T., Chandra, R., Chen, E., "BGP Route Reflection - An
Alternative to Full Mesh IBGP", RFC 2796, April 2000.
[3] Traina, P., McPherson, D., Scudder, J.. "Autonomous System
Confederations for BGP", RFC 1965bis, "Work In Progress",
October 2000.
[4] Cisco Systems, Inc., "Endless BGP Convergence Problem in Cisco
IOS Software Releases" , FN, October 10, 2000.
[5] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", RFC 2119, March 1997.
11. Authors' Addresses
Danny McPherson
Amber Networks, Inc.
48664 Milmont Drive
Fremont, CA 94538
Email: danny@ambernetworks.com
Vijay Gill
Metromedia Fiber Network, Inc.
8075 Leesburg Pike, STE 3
Vienna, VA, 22182
Email: vijay@umbc.edu
Daniel Walton
Cisco Systems, Inc.
7025 Kit Creek Rd.
Research Triangle Park, NC 27709
Email: dwalton@cisco.com
McPherson, Gill, Walton, Retana [Page 17]
INTERNET DRAFT December 2000
Alvaro Retana
Cisco Systems, Inc.
Email: aretana@cisco.com
McPherson, Gill, Walton, Retana [Page 18]