Internet DRAFT - draft-klockar-ibgp-oscillation
draft-klockar-ibgp-oscillation
Network Working Group T. Klockar
Internet-Draft July 8, 2005
Expires: January 9, 2006
Oscillation Prevention in I-BGP
draft-klockar-ibgp-oscillation-00
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 January 9, 2006.
Copyright Notice
Copyright (C) The Internet Society (2005).
Abstract
This memo presents a technique for preventing oscillations in I-BGP.
The idea is to utilize already known data in routers to stop
oscillation. This builds on the fact that routers can send implicit
and explicit withdrawals. Implicit withdrawals are redefined to mean
that the route still exist and explicit withdrawal to mean that the
route has disappeared. The router can detect and avoid oscillation
by storing the implicit withdrawn routes and using them to rule out
other routes. The cost is more cheap memory for the RIB-In but no
extra expensive memory is needed in the forwarding table.
Klockar Expires January 9, 2006 [Page 1]
Internet-Draft Osc. Prevention I-BGP July 2005
1. Introduction
The de-facto inter-domain routing protocol Border Gateway Protocol
version 4(BGP4) as described by RFC1771 [1], had a scaling problem
with Autonomous Systems(AS). Two solutions were suggested to this
problem, Route reflectors (RFC1966 [3], RFC2796 [4]) and AS-
Confederations (RFC1965 [2], RFC3065 [5]), but these solutions
introduced the possibility of route oscillations. The I-BGP route
oscillation problem has been described in RFC3345 [6], and it appears
when there is an unlucky combination of Route Reflectors or AS-
confederations, MED and multihoming.
Klockar Expires January 9, 2006 [Page 2]
Internet-Draft Osc. Prevention I-BGP July 2005
2. Algorithm
The algorithm is based on the implicit and explicit withdrawals. The
implicit withdrawal is when a new route update is received, for a
destination from a peer, which replaces a previous update for the
same destination. An explicit withdrawal is when a route removal is
received. Here, the meaning of implicit and explicit withdrawal are
slightly redefined. Implicit withdrawal means that the previous
route still exists but there is a better route, while the explicit
withdrawal means that the route does NOT exist any more.
o Every time BGP receive a new route from a peer for a destination
it MUST mark the previous routes from that peer for that
destination as inactive, and the new route as active.
o The decision process, i.e. the best route selection algorithm,
MUST consider both active and passive routes in its selection.
Passive routes are only used to avoid selecting certain active
routes.
E.g.
Oscillating circuit as described in RFC3345.
Ra - - - Rb
/\ |
/4 \3 |6
Rc..Rd Re
\ \(2)/(1)
\ \ /
AS2 AS3
\ /
AS4
Numbers in brackets are MED values and numbers by links are link
costs. Unnumbered links have a unit cost of one.
The oscillation condition here is that Rb [Re,AS3,AS4] and Ra select
[Rd,AS3,AS4], and announce the selected path. Then Ra needs to
select [Rc,AS2,AS4] and announce that path. Rb then selects
[Ra,Rc,AS2,AS3] and announce that path. Now Ras condition, i.e.
higher MED value, for selecting the longer Rc path has been removed
so Ra select [Rd,AS3,AS4], and we are back in the first state. This
oscillation will continue until any of the involved routes changes.
The suggested solution allows routers to remember more routes, so
router Ra will have stored all three routes.
Klockar Expires January 9, 2006 [Page 3]
Internet-Draft Osc. Prevention I-BGP July 2005
All RIB-Ins for Ra in one table
Best | State | Peer | MED | AS-Path
=============================================
* | Active | Rc | | [Rc,AS2,AS4]
| Active | Rd | 2 | [Rd,AS3,AS4]
| Active | Rb | | [Rb,Ra,Rc,AS2,AS4]
| Passive | Rb | 1 | [Rb,Re,AS3,AS4]
All RIB-Ins for Rb in one table
Best | State | Peer | MED | AS-Path
=============================================
| Active | Re | a | [Rc,AS2,AS4]
* | Active | Ra | 2 | [Ra,Rc,AS2,AS4]
| Passive | Ra | | [Ra,Rd,AS3,AS4]
Router Rb does not have to implement the suggested algorithm. It is
enough that router Ra implements the algorithm to prevent
oscillation. Full proofs and examples can be found in [7], [8].
Klockar Expires January 9, 2006 [Page 4]
Internet-Draft Osc. Prevention I-BGP July 2005
3. Impact BGP and routers
This algorithm affects the finite state machine in BGP and changes
its behavior slightly. In this way, other routers without the
modification will still be able to communicate with it. Compared to
the normal BGP4, the modification needs more storage for routes in
the RIB-In, but not in the forwarding table. This is very important
because forwarding table memory is very expensive while normal slow
processing memory used for the RIBs is cheap. Measurements at Lulea
University of Technology have shown that the total amount of route
data received at startup there takes up 2.5 MB. The data contains
160000 prefixes according to zebra bgpd. Transferring those updates
over the network takes more time than storing the date in memory.
During a normal day between 30000 and 200000 updates are received,
that is less than 2.4 updates per second. This means that storing
the RIB database in expensive forwarding memory would be a waste of
resources. As proven [7] and shown [8] in tests the algorithm only
needs to be implemented in certain routers.
Klockar Expires January 9, 2006 [Page 5]
Internet-Draft Osc. Prevention I-BGP July 2005
4. Conclusions
The algorithm presented here solves the problem with MED induced
I-BGP oscillations for Route Reflectors and AS-confederations, by
giving the router an overview of which routes that exist within the
AS. Compared to other algorithms for solving the same problem this
algorithm does not change the BGP messaging or types of messages.
This means that the algorithm is ready to be deployed in any router,
and can work in cooperation with unmodified routers. However to be
sure that oscillation is prevented all routers within the AS that
have more than two peers should implement it.
5. References
[1] Rehkter, Y. and T. Li, "A Border Gateway Protocol (BGP version
4)", RFC 1771, STD 1, June 1995.
[2] Traina, P., "Autonomous System Confederations for BGP",
RFC 1965, STD 1, June 1996.
[3] Bates, T. and R. Chandra, "BGP Route Reflection An alternative
to full mesh IBGP", RFC 1966, STD 1, June 1996.
[4] Bates, T., Chandra, R., and E. Chen, "BGP Route Reflection - An
alternative to full mesh IBGP", RFC 2796, STD 1, April 2000.
[5] Traina, P., McPherson, D., and P. Traina, "Autonomous System
Confederations for BGP", RFC 3065, STD 1, February 2001.
[6] McPherson, D., Gill, V., Walton, D., and A. Retina, "Border
Gateway Protocol (BGP) Persistent Route Oscillation Condition",
RFC 3345, STD 1, August 2002.
[7] Klockar, T. and L. Carr-Motyckova, "Preventing Oscillation in
Route Reflector-Based I-BGP", ICCCN 2004, October 2004.
[8] Klockar, T., "Preventing Oscillation in I-BGP", SNCNW 2004,
November 2004.
Klockar Expires January 9, 2006 [Page 6]
Internet-Draft Osc. Prevention I-BGP July 2005
Author's Address
Tomas Klockar
Sandviksgatan 76b
Lulea 97 234
Sweden
Phone: +46 (0)920-231335
Email: tomas@klockar.se
URI: http://www.klockar.se/
Klockar Expires January 9, 2006 [Page 7]
Internet-Draft Osc. Prevention I-BGP July 2005
Intellectual Property Statement
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.
Disclaimer of Validity
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 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.
Copyright Statement
Copyright (C) The Internet Society (2005). 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.
Acknowledgment
Funding for the RFC Editor function is currently provided by the
Internet Society.
Klockar Expires January 9, 2006 [Page 8]
