Network Working Group J. Moy Internet Draft Proteon, Inc. April 1992 Proposed modifications to RFC 1247 Status of this Memo This memo documents proposed modifications to the OSPF protocol. It is the intent that these modifications be folded into the OSPF specification, resulting in an update to RFC 1247. OSPF is a standards track protocol, and is presently at Draft Standard status. The modifications proposed herein are backward-compatible, and will not outdate any current OSPF implementations. Abstract The proposed modification to OSPF fall into three general categories, as listed below: o Bugfixes. There is a problem with certain anomalous virtual links configurations wherein permanent routing loops can form. This memo describes a modification to the OSPF routing table calculation that fixes the problem. Only area border routers attaching to non-backbone transit areas (which by definition contain virtual links) are affected. o Responses to changes in the IP architecture. Since the IP TOS field is being redefined to be one bit larger (the extra bit being assigned to monetary cost), the list of TOS encodings in Section 12.3 of RFC 1247 must be enhanced. The encoding for the previously defined TOS types will not change. o Incremental optimizations. Several small changes fall into this category. One example is for the OSPF specification to mention that, other than default, it is not necessary to summarize information into OSPF stub areas (although this may be at the expense of optimal inter-area routing). [Moy] [Page 1] Internet Draft OSPF modifications April 1992 1. A problem with virtual links OSPF allows an Autonomous System to be organized into separate pieces, called Areas. This might be done for several reasons: it can lessen the amount of resources consumed by the routing protocol itself (both in terms of network bandwidth, router CPU and memory), and it provides an additional level of routing protection. When splitting an AS into areas, there is always a special area called the backbone (which uses Area ID 0.0.0.0). It is the responsibility of the backbone area to distribute routing information to and from the other areas. When OSPF routing information, and in fact IP data traffic, flows from one non-backbone area to another, it must transit the backbone. In this way, the area configuration looks like a hub and spoke topology, with the backbone area being the hub. In order to support this functionality, the backbone must remain connected. However, so that arbitrary area configurations can be supported, OSPF introduces the idea of virtual links. By configuring virtual links through non-backbone areas, the backbone is extended and connectivity is maintained. The areas containing these virtual links are called "transit areas". They are the only areas in an OSPF, besides the backbone, that can forward data traffic which neither originates nor terminates in the area itself. Transit areas pose a special problem when forwarding data traffic. This is because as transit data traffic goes from a border router into the interior of the transit area, it goes from a router having global knowledge to one having only local knowledge (and one that has no knowledge of the virtual link's existence). In other words, there is an information disparity between the border routers and the transit area's interior. Realizing this, RFC 1247 attempted to deal with this by recalculating the first hop of a packet as it enters the transit area (see Section 16.3, "Resolving virtual next hops", of [1]). However, this ends up being inadequate for certain virtual link configurations, one of which is shown in Figure 1. Figure 1 shows the last configuration tested in the Interop pre- staging held in October 1992 in Boxborough, MA. The backbone area was configured as three physically separate pieces: networks 128.8.0.0, 12.0.0.0 and the serial line joining routers RT4 and RT5. The middle network, 6.0.0.0, was configured as Area 1. In order to reconnect the backbone, two virtual links were configured, one between Routers RT2 and RT6 and the other between routers RT6 and RT4, making Area 1 into a transit area. The problem then occurred when attempting to forward packets to router RT5. In the backbone Dijkstra, RT2 calculated the next hop as being Router RT6, and then uses the calculation in Section 16.3 of [Moy] [Page 2] Internet Draft OSPF modifications April 1992 +-----+ | RT1 | +-----+ | 128.8.0.0 -------------------------------------------------- | | +-----+ +-----+ |18.0.0.0 | RT2 | | RT3 |------------| +-----+ +-----+ +-----+ |------| RT4 | | 6.0.0.0 | | +-----+ --------------------------- | | | | +-----+ +-----+ +-----+ | RT6 | | RT7 | | RT5 | +-----+ +-----+ +-----+ | 12.0.0.0 --------------------------- | | +-----+ +-----+ | RT8 | | RT9 | +-----+ +-----+ Figure 1: A problem configuration [1] to adjust the next hop to the better choice RT3. Unfortunately, RT3's backbone Dijkstra calculated the next hop (correctly) as RT2 (!), and did not invoke the Section 16.3 calculation since it is not a virtual link endpoint. This led to a tight routing loop between RT2 and RT3. It is interesting to note that the problem could have been avoided by the configuration of an additional virtual link between RT3 and RT4. But in general what is needed is an additional routing table calculation in all of the transit area's border routers. This calculation, which will replace Section 16.3 of [1], is presented below. 1.1. A fix for the virtual link problem The general idea of the fix is as follows. First, an area's border routers dynamically determine whether the area is contains any active virtual links (i.e., whether it is a transit area). Then, after calculating the intra-area and inter-area paths in Sections 16.1 and 16.2 of [1], each border router examines the summary-LSAs associated with its connected transit areas to see whether more optimal paths using the transit area exist. If so, they override the previously discovered routes. [Moy] [Page 3] Internet Draft OSPF modifications April 1992 Relating this to figure 1, what would happen when calculating routes to RT5 is as follows. All of Area 1's border routers (RT2, RT3, RT4 and RT6) would dynamically discover that Area 1 is a transit area. Using the calculations in Sections 16.1 and 16.2 of [1], RT2 calculates the next hop to RT5 as RT6, and RT3 calculates it as RT2 (as before). Then, performing the new (additional) calculation which replaces 16.3 of [1], the summary-LSA originated into Area 1 by RT4 causes the next hops to be overridden by the next hops of RT3 and RT4, respectively. In more detail, this new mechanism consists of the following components: o There will be a new bit in the "router type" field of the router-LSA. This bit (call it the "V" bit) will be set in a router X's router-LSA for Area A if and only if router X is the endpoint of an active (i.e., configured and up) virtual link through Area A. Note that the other bits in the router type field indicate whether the router is an area border, AS boundary router and/or wild-card multicast receiver (see Section A.2 of [1] and Section A.1 of [4]). o Whether Area A is a transit area will be discovered dynamically in Area A's Dijkstra calculation (Section 16.1). Area A is a transit if and only if one or more router-LSAs having the "V" bit set are discovered in Step 2 on page 82 of [1], or if the calculating router itself is the endpoint of an active virtual link through Area A. Only area border routers need perform this calculation, since they are the only ones that perform the succeeding calculations. o The calculation in Section 16.3 is replaced by the calculation detailed below in "Replacement for Resolving virtual next hops". The new calculation, performed only in area border routers, examines all connected transit areas, installing any paths that are better than those discovered in Sections 16.1 and 16.2 of [1]. o The calculation in Section 16.5 of [1], "Incremental updates -- summary links" will be updated as follows. There are two cases: - If the summary-LSA is associated with the backbone, or if the router is attached to a single area, the calculation in 16.2 of [1] is run again for a single routing table entry (as before). Then, if the router is attached to one or more transit areas, the calculation in Section 16.3's replacement must be run again for the single destination. Finally, if the results of these calculations have changed the cost to [Moy] [Page 4] Internet Draft OSPF modifications April 1992 an AS boundary router (as would be the case for a type 4 summary-LSA) or to any forwarding addresses, the AS external links will have to be examined by rerunning the calculation in Section 16.5. - Otherwise, if the summary-LSA is associated with a transit area, the following calculations must be performed. If the new summary-LSA specifies a lower cost than the previous instance (or if there was no previous instance of the summary-LSA) the calculation in the replacement for Section 16.3 should be rerun for a single routing table entry, removing those next hops belonging to the transit area before the recalculation commences. As before, if the results of this calculation changes the cost to an AS boundary router or to any forwarding addresses, the AS external links will have to be examined by rerunning the calculation in Section 16.5. On the other hand, if the new summary-LSA specifies a larger cost than the previous instance, the complete routing table calculation must be rerun starting with the Dijkstra algorithm specified in Section 16.1. 1.2. Replacement for Resolving virtual next hops The following calculation will be substituted for section 16.3 of [1]. The calculation is extremely similar to the calculation in Section 16.2 of [1], and is performed in area border routers only: Examine in turn all the summary-LSAs associated with transit areas. Each such summary-LSA advertises a route to Network N (or in the case of a type 4 summary-LSA, router N). It is associated with transit area A, and was originated by an area border router BR. (1) If the cost advertised by the summary-LSA is LSInfinity, examine the next LSA. (2) If the summary-LSA was originated by the calculating router itself, examine the next LSA. (3) Look up the routing table entry for N. If it does not exist, or if the route type is other than intra-area or inter-area, or if the area associated with the routing table entry is not the backbone area, then examine the next LSA. In other words, this calculation only updates backbone Dijkstra routes found in Section 16.1 of [1] and inter-area routes found in Section 16.2 of [1]. [Moy] [Page 5] Internet Draft OSPF modifications April 1992 (4) Look up the routing table entry for the advertising router BR associated with the Area A. If it is unreachable, examine the next LSA. Otherwise, the cost to destination N is the sum of the cost in BR's routing table entry and the cost advertised in the LSA. Call this cost IAC. (5) If this cost is less than the cost occurring in N's routing table entry, overwrite N's list of next hops with those used for BR, and set N's routing table cost to IAC. Else, if IAC is the same as N's current cost, add BR's list of next hops to N's list of next hops. In any case, the area associated with N's routing table entry must remain the backbone area. And the path type (either intra-area or inter-area), must also remain the same. 1.3. Notes on the new Section 16.3 It is important to note that the new calculation never makes unreachable destinations reachable, but instead just potentially finds better paths to already reachable destinations. Also, unlike the old 16.3, the new calculation installs any better cost found into the routing table entry, from which it may be readvertised in summary-LSAs to other areas. 1.4. Obsoleting LSInfinity in router-LSAs As a related change, the metric of LSInfinity can no longer be used in router-LSAs to indicate unusable links. This is being done for several reasons: o It removes any possible confusion in an OSPF area as to just which routers/networks are reachable in the area. For example, the above virtual link fix automatically detects the existence of virtual links when running the Dijkstra. However, when one- directional links are possible, some routers may detect the existence of virtual links while others may not. This may defeat the proposed fix for the virtual link problem. For example, consider a modification to Figure 1 where RT3 is advertising its cost to Network 6 as LSInfinity, and where there is no virtual link between RT6 and RT4 but instead a connection through the physical backbone. In this case, RT3 would not know about the virtual link through Area 1, and a routing loop would again result. o It also helps the IP multicast extensions, because one-way reachability can lead to places that are reachable via unicast but not multicast, or vice versa. [Moy] [Page 6] Internet Draft OSPF modifications April 1992 It is believed that no current OSPF implementations are using LSInfinity in router-LSAs; its two prior justifications (a way to not support TOS before TOS was optional, and for strong TOS interpretations) are no longer valid. LSInfinity will continue to mean "unreachable" in summary-LSAs and AS-external-LSAs, as some implementations use this as an alternative to the premature aging procedure specified in Section 14.1 of [1]. 2. Other changes 2.1. TOS encoding Now that an additional IP TOS bit (monetary cost) has been defined (see [3]), additional TOS encodings will now be defined in Section 12.3 of [1]. Note that the encodings of the already existing TOS types will not change. The OSPF MIB ([2]) must also be modified in the same fashion. 2.2. Summarizing routes into transit areas Originating summary-LSAs (Section 12.4.3 of [1]). The OSPF specification mandates that routes associated with Area A are never summarized back into Area A. However, you can further reduce the number of summary-LSAs by refusing to summarize into Area A those routes having next hops in Area A (this only happens in the presence of virtual links). For example, in Figure 1 Router RT6 does not have to summarize a route for 128.8.0.0 into Area 1 (if it does, it will never be used). This is the logical equivalent of a Distance Vector protocol's split horizon logic. 2.3. Summarizing routes into stub areas While area border routers connected to OSPF stub areas must import default summary-LSAs into the stub area, they need not summarize other routes into the stub area. The amount of summarization done into stub areas can be put under configuration control. The user can then make a trade-off between optimal routing and database size. This is also a change to Section 12.4.3 of [1]. 3. References [1] Moy, J., "OSPF Version 2", RFC 1247, July 1991. [2] Baker, F. and Coltun, R., "OSPF Version 2 Management Information Base", RFC 1253, August 1991. [3] Almquist, Philip, "Type of Service in the Internet Protocol Suite", Internet Draft, January 1992. [Moy] [Page 7] Internet Draft OSPF modifications April 1992 [4] Moy, J., "Multicast extensions to OSPF", Internet Draft, November 1991. [Moy] [Page 8]