Network Working Group A. D. Zinin Internet Draft AMT Group Expiration Date: August 1999 February 1999 File name: draft-ietf-ospf-abr-behavior-00.txt OSPF ABR Behavior Alternative Implementation and Deployment Considerations draft-ietf-ospf-abr-behavior-00.txt Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a "working draft" or "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. Abstract OSPF [Ref1] is a link-state intra-domain routing protocol used for routing in IP networks. Though the definition of the ABR in the current OSPF specification does not require a router with multiple attached areas to have a backbone connection, it is actually necessary to provide successful routing to the inter-area and external destinations. If this requirement is not met all traffic, destined for the areas not connected to such ab ABR or out of the OSPF domain, is dropped. The rules of originating and processing Summary-LSAs given in the current OSPF standard [Ref1] can also result in suboptimal inter-area routing. Though all these problems Zinin [Page 1] Internet Draft OSPF ABR Behavior January 1999 can be fixed using virtual links, this memo describes an alternative implementation of the OSPF ABR behavior, which allows the administrator to avoid it or, if virtual links are still used, to decrease the number of configured virtual links. This memo also describes possible situations where the proposed implementation can be used. Acknowledgements The author would like to acknowledge Christian Hopps for his help in finding weak points in early versions of this document and Thomas M. Thomas II for technical and grammar review. This document is a result of the discussion between the author, Christian Hopps, and Acee Lindem about Cisco Systems OSPF implementation. 1 Overview 1.1 Introduction An OSPF routing domain can be split into several subdomains, called areas, which limit the scope of LSA flooding. A router having attachments to multiple areas is called an "area border router" (ABR). The primary function of an ABR is to provide its attached areas with Type-3 and Type-4 LSAs (which are used for describing routes and ASBRs in other areas) as well as to perform actual inter- area routing. 1.2 Motivation In OSPF domains the area topology is restricted so that there must be a backbone area (area 0) and all other areas must have either physical or virtual connections to the backbone. The reason for this star-like topology is that OSPF inter-area routing uses the distance-vector approach and a strict area hierarchy permits avoidance of the "counting to infinity" technique. OSPF prevents inter-area routing loops by implementing a split-horizon mechanism, permitting ABRs to inject into the backbone only Summary-LSAs derived from the intra-area routes, and limiting ABRs' SPF calculation to consider only Summary-LSAs in the backbone area's link-state database. The last restriction leads to a problem when an ABR has no backbone Zinin [Page 2] Internet Draft OSPF ABR Behavior January 1999 connection (in OSPF an ABR does not need to be attached to the backbone). Consider a sample OSPF domain depicted in the Figure 1. . . . Area 0 . +--+ +--+ ..|R1|.. ..|R2|.. . +--+ .. +--+ . . .. . . +--+ . . Area1 |R3| Area2 . . +--+ +--+ . . .. |R4| . . . . +--+ . ....... ....... Figure 1. ABR dropping transit traffic In this example R1, R2, and R3 are ABRs. R1 and R2 have backbone connections, while R3 doesn't. Following the section 12.4.1 of [Ref1], R3 will identify itself as an ABR by setting the bit B in its router-LSA. Being an ABR, R3 can only consider summary-LSAs from the backbone when building the routing table (according to section 16.2 of [Ref1]), so it will not have any inter-area routes in its routing table, but only intra-area routes from both Area 1 and Area 2. Consequently, according to the section 12.4.3 of [Ref1], R3 will originate for Areas 1 and 2 only summary- LSAs covering destinations in the directly attached areas, i.e., in Area 2---the summary-LSAs for Area 1, and in Area 1---the summary- LSAs for Area 2. At the same time, router R2, as an ABR connected to the backbone, will inject into Area 2 summary-LSAs describing the destinations in Area 0 (the backbone), Area 1 and other areas reachable through the backbone. This results in a situation, where internal router R4 calculates its routes to destinations in the backbone and areas other than Area 1 via R2. The topology of Area 2 itself can be such that the best path from R4 to R2 is via the R3, so all traffic destined for the backbone and backbone-attached areas goes through R3. Router R3 in turn, having only intra-area routes for areas 1 and 2, will effectively drop all traffic not destined for the areas directly attached to it. The same problem can be seen when a backbone-connected ABR loses all of its adjacencies in the backbone---even if there are other normally functioning ABRs in the attached areas, all traffic going to the Zinin [Page 3] Internet Draft OSPF ABR Behavior January 1999 backbone (destined for it or for other areas) will be dropped. In a standard OSPF implementation this situation can be remedied by use of the Virtual Links (see section 15 of [Ref1] for more details). In this case, router R3 will have a virtual backbone connection, will form an adjacency over it, will receive all summary-LSAs directly from a backbone-attached router (R1 or R2, or both in our example) and will install inter-area routes. While being an unavoidable technique for repairing a partitioned backbone area, the use of virtual links in the described situation adds extra configuration headaches and system traffic overhead. Consider another example, illustrated by the Figure 2: . Area 2 . . . . +--+ . ......|R5|....... . +--+ . . / \ . . / \ . . BB /10Mb \ 2Mb . . / \ . . | \ . . +--+ +--+ . ..|R1|......|R2|.. . +--+ +--+ . . | 10Mb |\ . . ------------ | . . | . . +--+ . . |R4| . . Area 1 +--+ . .................. Figure 2. Suboptimal inter-area routing In this example router R2 has a 2Mb link to R5. At the same time R1 has a better link (10 Mbps), but R2 cannot route traffic going to area 2 through R1. This is because according to [Ref1] R2 is not allowed to consider summary-LSAs from non-backbone areas and, consequently, does not have routes covering destinations in area 2 via R1. The situation looks even more interesting if R4's routing table is considered. Since R2 floods summary-LSAs from R1 to R4, router R4 will have routes to the area 2 via R1 (the best path), expecting traffic to go via 10Mbps links. In reality R2 will not Zinin [Page 4] Internet Draft OSPF ABR Behavior January 1999 direct traffic to R1, but will forward it via 2Mbps link attached to itself. The last example shows how the main principle of the OSPF---prefer the shortest path---is broken due to distance vector approach used for inter-area routing. Again, the problem can be fixed using the virtual links between R1 and R2 in standard OSPF, but the solution proposed in this document appears to be more elegant and involving no administrative and traffic overhead. 2 Proposed Changes to ABR Behavior This section describes two alternative implementations of ABR behavior. The two solutions vary in details of Type 1 and Type 3/4 LSA origination, as well as routing table calculation. These details are described below. Any other parts of standard OSPF are not changed. The first solution, named "short-cut ABR", is an improvement on standard ABR behavior, based on relaxation of the restrictions applied to the calculation of the inter-area routes. ABRs are allowed to consider summary-LSAs from all attached areas (no matter if it is connected to the backbone or not). The routing loop prevention is done by restricting origination of summary-LSAs---inter-area routes are readvertised only if there is a valid summary-LSA for the destination learned from the backbone. Origination of summary-LSAs for intra-area routes is done as in standard OSPF, described in [Ref1]. The relaxation of the routing table calculation allows router R3 in the first example (Figure 1) to route traffic between the attached areas, as well as to route traffic destined for the backbone and other areas using the routes derived from the summary-LSAs in each attached area. This approach also enables router R2 in the second example to route inter-area traffic via R1. The second solution, named "transit router", is targeted to the situation when an ABR has no backbone connection. It implies that a router connected to multiple areas without a backbone connection is not an ABR and must function as a router internal to every attached area. This solution emulates a situation where separate OSPF processes are run for each area and supply routes to the routing table. It only remedies the situation described in the first example and only in the meaning of not dropping transit traffic. This approach is not ideal, though, as a router following it does not function as a real border router---it doesn't originates summary- LSAs. Nevertheless such a behavior may be desirable in certain Zinin [Page 5] Internet Draft OSPF ABR Behavior January 1999 situations. Note that the proposed solutions do not obviate the need of virtual link configuration in case an area has no physical backbone connection at all (except for a stub area, as described in section 5). The methods described here improve the behavior of a router connecting two or more backbone-attached areas. Note also, that in the following two subsections, an "active backbone attachment" means existence of at least one fully adjacent neighbor in the area 0. Though this document is initially oriented to processing Type-3 LSAs and, consequently, is targeted to improving OSPF inter-area routing, it's acceptable to apply described methods to Type-4 LSAs, which will lead to improvement of external routing in an OSPF domain. 2.1 Solution 1 ("short-cut ABR") The following changes are made to the base OSPF described in [Ref1]: 1. The algorithm of Type 1 LSA (router-LSA) origination is not changed, the router still identifies itself as an ABR by setting the bit B in its router-LSA when it has more than one attached area. 2. The algorithm of the routing table calculation is changed to allow the router to consider the summary-LSAs from all attached areas. Note that if the router has no physical (from OSPF's standpoint) interface in the backbone, it does not need to consider summary-LSAs from the backbone, as in this case they are received via the virtual links and the ABRs at the other ends of the VLs already injected summary-LSAs into the transit areas. Also, an ABR doesn't need to perform the calculations described in the section 16.3 of [Ref1], as summaries from other ABRs in the transit area are considered by the main algorithm. So, the paragraph 1 of section 16.2 of [Ref1] should be read as follows: "The inter-area routes are calculated by examining summary-LSAs. If the router has active attachments to multiple areas, summary- LSAs from all active areas must be considered, i.e., the router must perform the inter-area route computation algorithm given below for each attached area (one at a time). If all of the router's links to the backbone are virtual, the router must run the algorithm only for non-backbone areas. Routers attached to a single area examine that area's summary-LSAs..." 3. The algorithm of the summary-LSAs origination is changed to Zinin [Page 6] Internet Draft OSPF ABR Behavior January 1999 include an explicit restriction not to originate summary-LSAs for inter-area routes if the router doesn't have a summary-LSA for the destination from the backbone[1]. If the ABR in question has no backbone connection, it will not originate summary-LSA for any inter-area route in any area. The ABR will also not readvertise an inter-area route from non-backbone area if its backbone link state database does not contain a summary-LSA for the destination. In order to implement described policy, the paragraph 2 in section 12.4.3 of [Ref1] should be read as follows: "... Note that only intra-area routes are advertised into the backbone, while both intra-area and inter-area routes are advertised into the other areas. Also, summary-LSAs for inter- area routes are originated if and only if the backbone area's link-state database contains a valid summary-LSA for the destination (to prevent loops of summary-LSAs)." The 7th step of the algorithm given in sections 12.4.3 of [Ref1] must be read as shown below: "Else, the Destination type is network. If this is an inter-area route then do a lookup in the backbone area's link state database to find a summary-LSA for this destination. If there is no such LSA---examine the next routing table entry. If the LSA was found and the routing table contains an entry associated with the backbone for the originating ABR, generate a Type 3 summary-LSA for the destination..." Described changes in the ABR behavior allow a multi-area connected router to function as normal area border router, forwarding traffic between attached areas and still not dropping the traffic destined for the backbone and backbone-attached areas, not connected to the router itself. In case this behavior is used when an ABR loses all its backbone connections, the administrator doesn't need to configure virtual links to other ABRs in the attached areas. This solution also allows an ABR to consider inter-area routes provided by another ABRs in the same area, thus fixing the situation described in the second example in section 1. 2.2 Solution 2 ("transit router") The following changes are made to the base OSPF, described in [Ref1]: 1. The algorithm of Type 1 LSA (router-LSA) origination is changed to prevent a multi-area connected router from identifying itself as an ABR by the bit B until it has at least one active backbone Zinin [Page 7] Internet Draft OSPF ABR Behavior January 1999 attachment. The paragraph 3 in section 12.4.1 of [Ref1] must be read is given below: "...Bit B should be set when the router is actively attached to two or more areas and if the router has at least one active backbone attachment..." Note, that as soon as the router finds itself actively connected to the backbone, it must revert to standard OSPF ABR behavior, including setting the bit B in its router-LSA and flooding it through all attached areas (see section 2.3 for more details). The router can also revert to the short-cut ABR behavior. 2. The algorithm of the routing table calculation is changed to allow the router to consider the summary-LSAs from all attached areas, as described in section 2.1 of this document. The router is allowed to do this only if it doesn't have a backbone connection. If it does, standard rules must be applied. 3. The algorithm of the summary-LSAs origination is changed to prevent from originating summary-LSAs, i.e., to prevent a router with multiple attached areas from acting as a real ABR until it has an active backbone connection. In order to implement described policy, the following sentence must be added to the paragraph 2 in section 12.4.3 of [Ref1]: "...Also, if none of the actively attached areas is the backbone, then the router must refrain from summary-LSA origination until it has at least one active backbone connection. " The changes in the ABR behavior described in this solution allow a multi-area connected router to successfully route traffic destined for the backbone and other areas. The difference from the first solution is that the router does not actively attract inter-area traffic, because it does not originate summary-LSAs. It still can forward traffic from one attached area to another along intra-area routes in case other routers in corresponding areas have the best inter-area paths over it, as described in section 1.2. Note, that when a router, following this strategy, finds an active backbone connection, it can start acting as either standard or short-cut ABR. 2.3 Handling Transitions While the "short-cut ABR" solution does not imply changes of LSA origination and routing table computation depending upon the backbone Zinin [Page 8] Internet Draft OSPF ABR Behavior January 1999 connection state, the "transit router" approach requires special processing when the router finds a connection to the backbone or loses the last one. 2.3.1 First backbone adjacency found The actions given below must be performed after an adjacency on an interface that belongs to the OSPF backbone has reached the state Full and this is the first full adjacency in the backbone. 1. If the current behavior strategy is the "transit router", then do the following: a) reconstruct the router-LSAs for all area databases, setting the bit B to 1. b) flood the new router-LSA to all neighbors according to [Ref1]. c) if the router must revert to the standard ABR behavior--- schedule the routing table recalculation for all areas to get rid of the inter-area routes through non-backbone areas. 2. Else, the behavior strategy is the "short-cut ABR" and nothing must be done. 2.3.2 Last backbone adjacency lost The actions given below must be performed when the router loses the last adjacency in the OSPF backbone and all of the adjacencies in the backbone area are in the state lesser than ExStart. 1. If the target behavior strategy is the "transit router", then do the following: a) reconstruct the router-LSAs for all areas, setting the bit B to 0. b) flood the new router-LSA to all neighbors according to [Ref1]. c) schedule the routing table recalculation to install the inter-area routes via non-backbone areas. d) flush all locally originated summary-LSAs from all non- backbone areas. 2. Else, the target behavior strategy is the "short-cut ABR" and Zinin [Page 9] Internet Draft OSPF ABR Behavior January 1999 nothing must be done. 3 Implementation Details If the current implementation of OSPF uses the standard described in [Ref1], then support of the proposed ABR behavior strategies must be implemented as a configurable option, allowing to specify two types of the strategies---the first one (standard, short-cut or transit) to instruct the router how to behave without a backbone connection, and the second one (standard or short-cut) to instruct the router how to behave when it has a backbone connection. The default value of the second behavior strategy (with a backbone connection) must be standard, while the default for the first strategy can be either of the values. If the implementation originally follows one of the alternative behaviors, there must also be an option to revert to the standard one. 4 Compatibility The changes of the OSPF ABR operations do not influence any aspects of the router-to-router cooperation and do not create routing loops, and hence are fully compatible with standard OSPF. Proof of compatibility is outside the scope of this document. 5 Deployment Considerations This section discusses the deployments details of the ABR behaviors described in this document. Note that both approaches are fully compatible with standard ABR behavior, so ABRs acting as described in [Ref1] and in this document can coexist in an OSPF domain and will function without problems. Considerations of short-cut ABR and transit router deployment are given in separate subsections below. 5.1 Short-cut ABR 5.1.1 Necessity of virtual links First of all it should be repeated that short-cut ABR behavior does not obviate the need for virtual links in case an area has no physical backbone connection except for a stub area (see section 5.1.4). The difference with standard OSPF is that the administrator does not need to configure virtual links through all areas he or she wants the inter-area traffic to go through. A short-cut ABR needs a single backbone connection (physical or virtual) to achieve optimal routing, since it considers summary-LSAs from all attached areas. Zinin [Page 10] Internet Draft OSPF ABR Behavior January 1999 5.1.2 Change of traffic patterns Use of short-cut ABR can lead to changes in the paths inter-area traffic flows take comparing to those experienced with standard OSPF. This happens because the short-cut ABR approach allows a router to find paths better than it is possible with the standard OSPF. While standard OSPF tries to forward all inter-area traffic through the backbone area (though it does not guarantee it), the short-cut ABR finds best routes in the domain even across non-backbone areas. With short-cut ABR the backbone area is used as a dedicated place of inter-area routing information exchange and inter-area traffic is allowed to cross non-backbone area borders if such a path is really the best. 5.1.3 Optimized inter-area routing Use of short-cut ABR improves inter-area routing in OSPF domains by allowing ABRs to consider summary-LSAs from all attached area and consequently readvertise them into non-backbone areas. Consider an example show in the Figure 3: ....................... . Backbone . ......... . . . . . +--+ +--+ . . |R1| |R5|--| . . +--+ +--+ 1| . . 8/ 8\ 1/ . | . . / \ -------- . | . . 8/ 8\ /1 1\ . | Net N . .+--+ +--+ +--+ 1| . ......|R2|.....|R3|.......|R4|--| . . +--+ +--+ +--+ . . .|1 1/ \1 1/ . . Area 3 . . .-------- -------- . .......... . . . . . . .Area 1 . Area 2 . ....... ................... Figure 3. Optimized inter-area routing In case all ABRs use standard OSPF approach, routing to the net N would be as follows: - R4 and R5 inject summary-LSAs into the backbone Zinin [Page 11] Internet Draft OSPF ABR Behavior January 1999 - R4 also inject a summary-LSA into area 2 - R3 is limited to consider summary-LSAs from the backbone only, so it doesn't see the alternative path through area 2 and always routes through the backbone (though parallel paths are available) - R3 injects summary-LSA for the inter-area routes derived from the backbone summary-LSAs and received from R4 and R5 into Area 2 - R2 is not allowed to consider non-backbone summary-LSAs and routes via serial links to R2, though more optimal paths do exist If at least R2 and R3 use short-cut ABR approach inter-area routing is improved as shown below: - R4 and R5 inject summary-LSAs into the backbone - R4 also inject a summary-LSA into area 2 - R3 considers summary-LSAs from both attached areas and installs the route through area 2 (it has three routes in the routing table---via R5, via R4 through the backbone, and via R4 through area 2) and performs traffic sharing between the two ethernet links. - R3 injects summary-LSA for the inter-area routes to N (it will be the same as in the previous case, actually) - R2 considers summary-LSAs from all attached areas and prefers the route through area 2 rather than the backbone. 5.1.4 Connecting a stub area with a short-cut ABR Short-cut ABRs can be used to connect a stub area to another non- backbone area without a virtual link configured on the ABR. One restriction that is applied to such a scheme is that the stub area must use default routing for both external and inter-area destinations. Consider Figure 4. Zinin [Page 12] Internet Draft OSPF ABR Behavior January 1999 . Backbone . . +--+ . .......|R1|....... . +--+ . . . . Area 1 . . . . +--+ . .......|R2|....... . +--+ . . . . Stub Area 2 . . . .................. Figure 4. Connecting a stub area with short-cut ABR With standard OSPF router R2 would need to have a virtual link with R1, because otherwise R2 would have no inter-area routes (OSPF standard would limit R2 to consider only backbone summary-LSA while calculating its routing table) and would drop all traffic going out of the stub area 2. If short-cut ABR approach is used, R2 is allowed to consider summary-LSAs injected into area 1 by R1, so R2 is not required to have a virtual link to the backbone. Without it R2 is not allowed to readvertise inter-area routes into the stub area, but the default summary injected by each ABR connected to a stub area can do the job in most cases. 5.2 Transit router Deployment of ABRs using the transit router behavior is limited to the situations where the ABR does not need to perform actual inter- area routing, though in certain circumstances inter-area traffic will be routed from one attached area to another. This can lead to unexpected routing asymmetry, as described below. 5.2.1 Possible asymmetry in inter-area routing Consider an OSPF domain depicted in Figure 5. Zinin [Page 13] Internet Draft OSPF ABR Behavior January 1999 ....................... . Backbone . . . . --------------------- . . |1 1| . ..+--+.............+--+.. ..|R1|..... ....|R4|.. . +--+ . . +--+ . . 1| . . /4 . . | 8 +--+ 4 / . . | +-|R3|---+ . . 1| / +--+\4 . . +--+ / . . \ 4 +--+ . . |R2|/8 . . +--|R5| . . +--+ . . +--+ . . | . . | . . --------- . . -------- . . net N . . net M . . . . . . Area 1 . . Area 2 . ........... .......... Figure 5. Inter-area routing asymmetry Assume that R3 uses the transit router approach. In this case R2 will have inter-area routes to network M via ABR R1 only. R5 in turn will have its inter-area route to network N via R4, but as far as R4 is only reachable via R3, all traffic destined to network N will get into R3. R3 will have an intra-area route to network N via R2 and will, of course, route it directly to it (because intra-area routes are always preferred over inter-area ones). Traffic going back from network N to network M will get into R2 and will be routed to R1, as R2 will not have any inter-area routes via R3. So, traffic from N to M will always go through the backbone while traffic from M to N will cross the areas directly via R3 and, in this example, will not use a more optimal path through the backbone. Note that this problem is not caused by the fact that R3 uses the transit router approach, in fact it would remain even in case of short-cut ABR. The reason for attracting the attention to it is that R3 is not really functioning as an ABR in case the transit router behavior is used, i.e., it does not inject summary-LSAs into the attached areas, but inter-area traffic can still go through it. 6 Footnotes [1] In standard OSPF, it is implicitly prohibited for an ABR to originate summary-LSAs for inter-area routes via non-backbone area by limiting an ABR consider only backbone summary-LSAs when Zinin [Page 14] Internet Draft OSPF ABR Behavior January 1999 calculating the routing table. As far as we relaxed the restriction of the routing table calculation, we need to introduce a similar one for summary-LSA origination. 7 References [Ref1] J. Moy. OSPF version 2. Technical Report RFC 2328, Internet Engineering Task Force, 1998. ftp://ftp.isi.edu/in- notes/rfc2328.txt. 8 Author's Address Alex D. Zinin AMT Group 8 Maly Znamensky per., bld. 1 Office 3b 121019 Moscow, Russia Phone : (7-095) 725-76-60 Fax : (7-095) 725-76-63 E-mail: zinin@amt.ru Zinin [Page 15]