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]