Internet Engineering Task Force V. Van den Schrieck
Internet-Draft O. Bonaventure
Intended status: Informational Universite catholique de Louvain
Expires: December 31, 2007 June 29, 2007
Routing oscillations using BGP multiple paths advertisement
draft-vandenschrieck-bgp-add-paths-oscillations-00.txt
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of 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 December 31, 2007.
Copyright Notice
Copyright (C) The IETF Trust (2007).
Abstract
The advertisement of multiple paths for the same prefix in the Border
Gateway Protocol is possible by using an extension to the attributes
developed for multiprotocol transfer. This allows better path
diversity in the adj-rib-ins, and can prevent some routing
inconsistencies with Route Reflection. However, if not carefully
used, this mechanism can also introduce routing oscillations and
inconsistencies in topologies with Route Reflection that were correct
without this extension.
Van den Schrieck & Bonaventure Expires December 31, 2007 [Page 1]
Internet-Draft Routing oscillations with add-paths June 2007
This document describes four types of routing inconsistencies that
occur in badly designed topologies when more than one path is
advertised by the routers.
1. Introduction
The Border Gateway Protocol (BGP) [1] is the interdomain routing
protocol currently used in the Internet. BGP-speaking routers
exchange network reachability information with each other by
advertising their best path to each destination prefix.
The ADD-PATH BGP capability allows multiple paths advertisement for
the same prefix [2]. Using multiple nexthops for a given prefix in
UPDATE messages, as explained in [4] serves similar purpose. The
advertisement of all available paths to a given prefix by Route
Reflectors [3] can prevent some routing oscillations, at the cost of
an increased memory consumption in the Adj-Rib-Ins. If a carefully
chosen subset of the paths is advertised by Route Reflectors in a
topology respecting some constraints on the IGP weights, MED
oscillations can also be prevented [5].
However, if the topology does not respect these constraints, routing
oscillations can appear while using multiple paths advertisement,
even if the system was stable with best path advertisement only.
This document presents several systems that have routing
inconsistencies when a subset of the available paths are advertised
by the routers when Route Reflection is used. They are inspired from
systems that have routing inconsistencies with standard BGP and Route
Reflection [6][7][8].
2. Topology with multiple solutions
The network described in Figure 1 represents two ASes. The edges in
the schema represens eBGP or iBGP sessions, depending on the routers
being in the same AS or not. AS 1 has two Route Reflectors, each of
them having two clients. AS2 advertises prefix P on four eBGP
sessions with AS1. We call PA the path to P via RA, PB the path via
RB, etc. The IGP links between the routers in AS 1, not shown in the
figure, are such that RR1's preferences on the paths to P are PC > PA
> PB > PD. Similarly RR2's preferences are PB > PD > PC > PA.
If only the best path is advertised, this system converges : RR1
chooses and advertises path PA, and RR2 path PD. If all paths are
advertised, they both know all the available paths, and RR1 can
choose C while RR2 selects PB.
Van den Schrieck & Bonaventure Expires December 31, 2007 [Page 2]
Internet-Draft Routing oscillations with add-paths June 2007
If BGP ADD-PATHS is used and the routers advertise all paths, both
Route Reflectors learn the four available paths and the system also
converges.
However, if only two paths are advertised, this topology has two
solutions. We suppose that the two paths advertised are always the
two that were ranked highest by the BGP decision process. Even if
one or both of those two paths were learned from some iBGP neighbor,
the next preferred paths are never advertised to that neighbor.
Depending on which route reflector advertises the paths from its
client first, two different states can be reached :
o If RR1 advertises paths PA and PB before RR2, RR2 selects PB as
its best path and advertises PB and PD. RR1 never learns path PC,
and keeps PA as its best route.
o If RR2 is the first to send its update, RR1 chooses PC as its best
path, and RR2 never learns PB.
If both Route Reflectors always send their paths to each other
together, the system never converges.
Van den Schrieck & Bonaventure Expires December 31, 2007 [Page 3]
Internet-Draft Routing oscillations with add-paths June 2007
System with two solutions
*****************************************
* AS1 *
* *
* +-----+ +-----+ *
* | RR1 |----------------| RR2 | *
* +-----+ +-----+ *
* /\ /\ *
* / \ / \ *
* / \ / \ *
* RA RB RC RD *
* | | | | *
*****************************************
| | | |
| | | |
*****************************************
* \ / \ / *
* RX---------------------RY *
* | *
* AS2 P *
*****************************************
Figure 1
3. Topology with MED oscillations on the second path
In Figure 2, AS1 has two Route Reflectors. RR1 has RA and RB as
clients, and RR2 has RC as client. AS 1 peers with ASX, ASY and AS0.
Router RX of ASX has an eBGP session with RA, router RZ of ASY
advertises the path to P to RB with a MED attribute of 1, and to RC
with MED 0. Router R0 of AS0 has an eBGP session with route
reflector RR1. ASX, ASZ and AS0 also peer with each other.
IGP costs in AS 1 are such that RB is the nearest router for both
RRs, then RA, then RC.
If router R0 of AS0 advertises prefix P, AS1 learns 4 paths towards P
: via RA, RB, RC and RR1. All routers of AS1 choose as best path the
one via RR1, as it has a shorter AS path. This system converges to a
unique solution if standard BGP is used.
If BGP ADD-PATHS is used and the routers advertise all paths, both
Route Reflectors learn the four available paths and the system also
converges.
Van den Schrieck & Bonaventure Expires December 31, 2007 [Page 4]
Internet-Draft Routing oscillations with add-paths June 2007
However, if the routers of AS1 advertise only the two paths that were
ranked highest by the BGP decision process, the system can oscillate
on the second path. The best path is still the one via RR1, but the
selection of the second path leads to the classical MED oscillation
problem [6][8].
The selection of the second path of RR1 depends upon RR2 advertising
PC or not. Indeed, if RR1 knows path PC, it selects PA as its second
path even if PB is better in terms of IGP distances, because PB has a
higher MED than PC. But if it does not know about PC, PB is selected
as its second best path. Similarly, the advertisement of PC by RR2
depends upon the second best path selected by RR1. PC is advertised
if RR1 selects PB, but not if it selects PA, because RR2 prefers PA
over PC but not over PB because of the MED attribute.
This system is clearly inconsistent : RR1 advertises PA if RR2
selects PC, but RR2 withdraws PC if it knows about PA, which is then
withdrawn by RR1, resulting in RR2 selecting PC again, and so on.
MED oscillations
*****************************************
* *AS1* *
* *
* +-----+ (1) +-----+ *
* | RR1 |-------------------| RR2 | *
* +-----+ +-----+ *
* /\ \ | *
* (2)/ \ \(1) (4)| *
* / \ \ | *
* RA \ RB RC *
* | \ \ | *
*****************************************
| \ \ |
| \ \MED=1 |MED=0
| \ \ |
********** ************ **********
* RX----*----* R0-------*-----* RZ *
* * * | * * *
* *ASX** * | *AS0** * *ASY**
********** ************ **********
|
P
Figure 2
Van den Schrieck & Bonaventure Expires December 31, 2007 [Page 5]
Internet-Draft Routing oscillations with add-paths June 2007
4. Topology with oscillations on the second path
In Figure 3, AS1 has three Route Reflectors, each of them having one
client. The IGP links and the corresponding costs, not shown in the
figure, are such that each Route Reflector prefers its left neighbor
path over its own client path, this one being preferred over the
right neighor path.
Prefix P is advertised by AS0 to AS1 and AS2. Routers of AS1 choose
the path advertised on the eBGP link with AS0 as their best path, as
it has the shortest AS-Path. This topology has thus coherent routing
if only one path is advertised. Similarly, if all paths are learned
by all Route Reflectors, they are able to choose their left neighbor
path as second best path.
However, if only two paths are advertised, there are routing
oscillations on the second best path chosen by each RRs. Each of
them constantly advertises then withdraws its client path, depending
on the right neighbor withdrawing or advertising its own client path.
The system being circular, it never converges.
Van den Schrieck & Bonaventure Expires December 31, 2007 [Page 6]
Internet-Draft Routing oscillations with add-paths June 2007
Oscillations on the second path
*****************************************
* *AS1* *
* *
* *
* +-----+ *
* /| RR1 |\ *
* / +-----+ \ *
* / | \ *
* +-----+ | +-----+ *
* | RR2 |----------------- | RR2 | *
* +-----+ | +-----+ *
* | | | \ *
* | | | \ *
* RA RB RC *
* | | | *\
***************************************** \
| | | \
| | | \
***************************************** \ ***********
* | | | * \* *AS0* *
* RX-----------RY-----------RZ---- *----- * R0 *
* * ***********
* * |
* *AS2* * P
*****************************************
Figure 3
5. Non deterministic topology becoming oscillating
In Figure 4, AS1 has three Route Reflectors, each of them having one
client. The IGP links and the corresponding costs, not shown in the
figure, are such that each Route Reflector prefers its left neighbor
path over its right neighbor path, this one being preferred over its
own client path.
If only the best route is advertised, the system is already instable
: Depending on the time on which each Route Reflector advertises the
path via its client, it can converge to a common path being chosen by
Van den Schrieck & Bonaventure Expires December 31, 2007 [Page 7]
Internet-Draft Routing oscillations with add-paths June 2007
all the RRs. For example, if RR1 advertises PA first, RR2 and RR3
select PA as their best path and don't advertise PB and PC. If they
all advertise their client path at the same time, the system diverges
: All RRs learn a better path than their own, and they thus
simultaneously withdraw then re-advertise their client paths.
If two paths are advertised, things get worse : the system always
diverges. Even if the initial path advertisements are not
synchronised, Route Reflectors are constantly advertising and
withdrawing their client path. For example, if PA is advertised
first, RR2 and RR3 choose it as their best path, but still advertise
respectively PB and PC as their second path. All Route Reflectors
having learned two paths better than their own, they withdraw their
client path then re-advertise it, and the system oscillates.
This topology is instable even with only the best path advertised,
but can still reach a stable state. If the configuration of the
Route Reflectors is modified so that they advertise two paths instead
of one, routing oscillations appear and the system becomes
inconsistent. The only way to have deterministic routing is to
advertise all available paths to P.
Van den Schrieck & Bonaventure Expires December 31, 2007 [Page 8]
Internet-Draft Routing oscillations with add-paths June 2007
Oscillations on the best and second paths
*****************************************
* *AS1* *
* *
* *
* +-----+ *
* /| RR2 |\ *
* / +-----+ \ *
* / | \ *
* +-----+ | +-----+ *
* | RR1 |----------------- | RR3 | *
* +-----+ | +-----+ *
* | | | *
* | | | *
* RA RB RC *
* | | | *
*****************************************
| | |
| | |
*****************************************
* | | | *
* RX-----------RY-----------RZ *
* | *
* P *
* *AS2* *
*****************************************
Figure 4
6. Conclusion
This document presents several situations where using the ADD-PATH
BGP capability with iBGP Route Reflection introduces routing
inconsistancies in systems that have coherent solutions otherwise.
It also presents a bad designed system that can sometimes converge to
a solution with normal BGP, but always oscillates on the best and the
second route when advertising two routes instead of one.
This document shows that the ADD-PATH extension to BGP should be
carefully used by operators, as routing loops can occur when
Van den Schrieck & Bonaventure Expires December 31, 2007 [Page 9]
Internet-Draft Routing oscillations with add-paths June 2007
advertising only a subset of the routes. One way to prevent such
routing inconsistancies is to advertise all available routes instead
of a subset, such that route diversity is identical as when using
Full Mesh iBGP. The drawback of this solution is the memory
consumption, which can cause scalability concerns. Another
possibility is to design the network such that the IGP distances
between Route Reflectors and their clients are smaller that the IGP
distances between Route Reflectors [5][7]. This prevents routing
inconsistancies to appear, because Route Reflectors will never prefer
the paths advertised by other Route Reflectors over the paths
advertised by their clients. However, designing iBGP in order to
respect that constraint is not always possible. Furthermore, even if
the network topology respects that constraint under normal operation,
it could be violated as a consequence of links or nodes failure [7].
7. IANA Considerations
This memo includes no request to IANA.
8. Security Considerations
This discussion does not introduces security concerns to BGP or any
specifications referenced in this document.
9. References
9.1. Normative References
[1] Rekhter, Y., Li, T., and S. Hares, "A Border Gateway Protocol 4
(BGP-4)", RFC 4271, January 2006.
[2] Walton, D., "Advertisement of Multiple Paths in BGP",
draft-walton-bgp-add-paths-05 (work in progress), March 2006.
[3] Bates, T., Chen, E., and R. Chandra, "BGP Route Reflection: An
Alternative to Full Mesh Internal BGP (IBGP)", RFC 4456,
April 2006.
9.2. Informative References
[4] Bhatia, M., "Advertising Multiple NextHop Routes in BGP",
draft-bhatia-bgp-multiple-next-hops-01 (work in progress),
August 2006.
[5] Walton, D., "BGP Persistent Route Oscillation Solution",
Van den Schrieck & Bonaventure Expires December 31, 2007 [Page 10]
Internet-Draft Routing oscillations with add-paths June 2007
draft-walton-bgp-route-oscillation-stop-01 (work in progress),
July 2005.
[6] McPherson, D., Gill, V., Walton, D., and A. Retana, "Border
Gateway Protocol (BGP) Persistent Route Oscillation Condition",
RFC 3345, August 2002.
[7] Griffin, T. and G. Wilfong, "On the Correctness of iBGP
Configuration", In ACM SIGCOMM Computer Communication Review,
Proceedings of the 2002 SIGCOMM conference, p.17-29, 2002.
[8] Griffin, T. and G. Wilfong, "Analysis of the MED oscillation
problem in BGP", In Network Protocols, 2002. Proceedings. 10th
IEEE International Conference on Network Protocols, 2002.
Authors' Addresses
Virginie Van den Schrieck
Universite catholique de Louvain
Louvain-la-Neuve,
Belgium
Email: firstname.lastname@uclouvain.be
URI: http://inl.info.ucl.ac.be
Olivier Bonaventure
Universite catholique de Louvain
Louvain-la-Neuve,
Belgium
Email: firstname.uclouvain@be.lastname
URI: http://inl.info.ucl.ac.be
Van den Schrieck & Bonaventure Expires December 31, 2007 [Page 11]
Internet-Draft Routing oscillations with add-paths June 2007
Full Copyright Statement
Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
Van den Schrieck & Bonaventure Expires December 31, 2007 [Page 12]