Network Working Group J. Moy Internet Draft Sycamore Networks, Inc. Expiration Date: July 2001 February 2001 File name: draft-ietf-ospf-subset-flood-00.txt Flooding Over a Subset Topology draft-ietf-ospf-subset-flood-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 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. Abstract This memo defines a method for limiting the flooding of OSPF LSAs to a configurable subset of the network topology. The following OSPF properties are maintained: (1) routers are omitted from the routing calculation until their link-state databases are synchronized and (2) links must be bidirectional before they can be used in the calculation. Backward-compatibility with unmodified OSPF routers is also provided. Moy [Page 1]
Internet Draft OSPF Subset Flooding February 2001 Table of Contents 1 Overview ............................................... 2 2 Mechanisms ............................................. 3 2.1 Deciding to become adjacent ............................ 3 2.2 LSA origination ........................................ 3 2.2.1 Advertising forwarding adjacencies ..................... 4 2.3 Modified routing calculation ........................... 4 2.4 MTU check .............................................. 5 4 Backward compatibility ................................. 5 5 Notes .................................................. 5 References ............................................. 6 A New LSA formats ........................................ 7 A.1 Router-LSA: rtype field ................................ 8 A.2 Router-additions-LSA .................................. 10 A.3 Network-additions-LSA ................................. 12 Security Considerations ............................... 13 Authors' Addresses .................................... 13 1. Overview Standard OSPF floods its LSAs over all links. This flooding logic is simple, robust, and auto-configuring. However, in highly meshed environments when many routers have a large number of neighbors, this flooding can be a burden on the router's processing power. For that reason, this memo suggests restricting flooding to a configured set of links. For backward-compatibility, and to enable the network operator to restore control connectivity from any location, a link is used for flooding if configured as such in *either* end. To prevent a link to be used for flooding, we use the technique from [Ref3], preventing its neighbor relationships from advancing past 2-way state. These neighbor relationships that were artificially stopped at 2-way state, but would have advanced to Full state if Section 10.4 of [Ref1] were followed, are termed "forwarding adjacencies". We do not change the building of router-LSAs and network-LSAs, and instead report these forwarding adjacencies in a new set of LSAs, called router-addition-LSAs and network-addition-LSAs. The standard OSPF routing calculation is then extended on an area- by-area basis to include the forwarding adjacencies, but only if both (a) all routers in the area support this memo and (b) both ends of the forwarding adjacency are reachable via the standard OSPF routing calculation. Moy [Page 2]
Internet Draft OSPF Subset Flooding February 2001 2. Mechanisms The descriptions of the required enhancements is split into the following sections. Section 2.1 describes how we prevent flooding on certain links by preventing their neighbor relationships from advancing past state 2-Way. These non-flooding relationships, called "forwarding adjacencies", are advertised in new LSAs as described in Section 2.2. Section 2.3 describes how these new LSAs are used in the routing calculation. The use of forwarding adjacencies requires that we perform the MTU check in the OSPF Hello protocol, as Section 2.4 explains. 2.1. Deciding to become adjacent OSPF floods only to neighbors is state Exchange or greater. So we prevent flooding on a link by preventing the neighbor relationships on the link from advancing past 2-way, exactly as was done in [Ref3]. In particular, if Section 10.4 of [Ref1] indicates that the router should form an adjacency with a neighbor (transitioning the neighbor from 2-Way to ExStart state), the router should execute additional steps as follows: (1) If the interface type is Virtual Link, start forming the adjacency (we don't allow you to disable flooding over virtual links). (2) If the neighbor is asking to form an adjacency (that is, we're running the logic in Section 10.4 of [Ref1] because we have received a Database Description packet from the neighbor), start forming the adjacency. This is necessary for backward compatibility. (3) Otherwise, we're running Section 10.4 of [Ref1] because either (i) we've just received a bidirectional Hello from the neighbor, (ii) there was an error in the previous Database Exchange over this link or (iii) an adjacency over an equivalent link has been lost (see Section 2.2). In this case, start forming the adjacency by transitioning the neighbor state to ExStart *only* if you have been configured to do so. 2.2. LSA origination A router implementing the enhancements in this memo sets the FA bit it its router-LSA's type field (Section A.1), and advertises its forwarding adjacencies in router-addition-LSAs and network- Moy [Page 3]
Internet Draft OSPF Subset Flooding February 2001 addition-LSAs. 2.2.1. Advertising forwarding adjacencies Forwarding adjacencies, those bidirectional neighbors (neighbor state 2-Way) that would have been advertised in router-LSAs and network-LSAs had the router been configured to flood over them, are advertised instead in router- addition-LSAs and network-addition-LSAs. The way a forwarding adjacency is advertised depends upon its associated interface type and the role that the router is playing on the associated segment. o Neighbors that have been stopped at 2-Way state on point-to-point and point-to-multipoint interfaces are added to router-addition-LSAs as Type 1 links (point-to- point connection to another router), formatted according to Sections 12.4.1.1 and 12.4.1.4 of [Ref1]. o If the router is attached to a broadcast or NBMA segment, is not the DR, and its conversation with the DR has been limited to state 2Way, a Type 2 link (connection to a transit network) is added to a router- addition-LSA. o If the router is the DR on an attached broadcast or NBMA segment, neighbor conversations that have been limited to state 2Way are added to network-addition-LSAs. 2.3. Modified routing calculation If all the router-LSAs in Area A's link-state database have the FA bit (Section A.1) set in their rtype field, then the OSPF routing calculation for Area A is modified as follows. (1) The intra-area calculation for Area A, Section 16.1 of [Ref1], is run to determine which routers are reachable in Area A. (2) The intra-area calculation is then rerun. However, this time when Section 16.1 of [Ref1] examines the router-LSA for router X, you must examine both the router-LSA originated by X *and* all the router-addition-LSAs that it has originated. Likewise, when 16.1 of [Ref1] examines network-LSAs for network N (defined by its Designated Router's address), you must examine the network-LSA and also all matching network-addition-LSAs. For the Moy [Page 4]
Internet Draft OSPF Subset Flooding February 2001 forwarding adjacencies listed in router-addition-LSAs and network-addition-LSAs, we substitute a different check for the bidirectional check in Step 2b of Section 16.1 of [Ref1]. In order to use a forwarding adjacency in the routing calculation, both router endpoints must have been found to be reachable. 2.4. MTU check Links that are not used by the OSPF Database Exchange process are now included in the routing calculation. However, we still want links with MTU mismatches to be excluded from the routing calculation. For this reason we implement the MTU mismatch detection in OSPF's Hello Protocol, exactly as was specified in Section 2.4 of [Ref3]. This logic prevents links with MTU mismatches from being declared bidirectional. See Section G.9 of [Ref3] for more details on MTU mismatches. 3. Backward compatibility If the router's neighbor requests to form a full adjacency, by sending a Database Description packet, the router must comply as long as a full adjacency is warranted according to Section 10.4 of [Ref1}, and is the same backward-compatibility mechanism used by [Ref3]. Also, all routers within an OSPF area need to be capable of including forwarding adjacencies (advertised in router-additions- LSAs and network-additions-LSAs) in their routing calculations before any router in the area is allowed to. This is determined by checking to see that all router-LSAs in the area's link-state database have the FA-bit set. 4. Notes Note the following concerning the enhancements proposed by this memo. o We do not recommend any particular configuration syntax. A vendor may decide to let you configure over which links to flood, or configure over which links not to flood. Or the vendor could combine with the functionality of [Ref3], and configure the Router IDs of the neighbors with which to flood (or not to flood). o In the future, the routers may themselves choose which links to use in flooding, For example, if a distributed, stable algorithm were developed which produced a 2-connected spanning graph, that Moy [Page 5]
Internet Draft OSPF Subset Flooding February 2001 might be used to autoconfigure the flooding links. o If insufficient links are configured from flooding, some routers may become isolated from the flooding algorithm, and hence from the routing calculation. However, since a link's flooding participation need only be configured in one endpoint, and operator would be able to reconfigure flooding and fix the problem remotely. o Two Dijkstra calculations are employed by the enhanced routing calculation of this memo, the first to determine router reachability, and the second to include the forwarding adjacencies. However, since the first only deals with reachability, one does not need to perform its sorting phase. References [Ref1] Moy, J., "OSPF Version 2", RFC 2328, April 1998. [Ref2] Coltun, R., "The OSPF Opaque LSA Option", RFC 2370, July 1998. [Ref3] Moy, J., "Flooding over parallel point-to-point links", Internet Draft, draft-ietf-ospf-ppp-flood-00.txt, November 2000. RFC 2154, June 1997. [Ref4] Moy, J., "OSPF Version 2", RFC 2178, July 1997. [Ref5] Coltun, R., D. Ferguson and J. Moy, "OSPF for IPv6", RFC 2740, December 1999. Moy [Page 6]
Internet Draft OSPF Subset Flooding February 2001 A. New LSA formats This memo requires that the router set an additional bit in it's router-LSA's rtype field (Section A.1) and that the router be capable of originating and processing two new LSAs, the router- additions-LSA (Section A.2) and the network-additions-LSA (Section A.2). Moy [Page 7]
Internet Draft OSPF Subset Flooding February 2001 A.1 Router-LSA: rtype field The format and building of the OSPF router-LSA remains unchanged, reflecting the router's full adjacencies (neighbor state Full) as specified in Section 12.4.1 of [Ref1]. However, a new flag, called bit FA, is added to the rtype field of the router-LSA. A router sets this bit if and only if it is capable of using the new router- additions-LSAs and network-additions-LSAs in its routing calculations. Equivalently, bit FA is set when the router is capable of using forwarding adjacencies in the routing calculation. Setting bit FA also implies that the router is capable of handling Opaque- LSAs, as specified in [Ref2]. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS age | Options | 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link State ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Advertising Router | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS checksum | length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | rtype | 0 | # links | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Link ID | P +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ E | Link Data | R +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | # TOS | TOS 0 metric | # + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ L # | TOS | 0 | metric | I T +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ N O | ... | K S +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ S | | TOS | 0 | metric | | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | ... | The router-LSA Moy [Page 8]
Internet Draft OSPF Subset Flooding February 2001 +---+---+---+---+---+---+---+---+ | * | FA| S | Nt| W | V | E | B | +---+---+---+---+---+---+---+-+-+ The rtype field Moy [Page 9]
Internet Draft OSPF Subset Flooding February 2001 A.2 Router-additions-LSA The router-additions-LSA is an area-scoped Opaque-LSA, having Opaque Type equal to TBD1. It is used to advertise forwarding adjacencies, and uses the same format as the router-LSA. The router's collection of forwarding adjacencies can be listed in one or more router- additions-LSAs, with the Opaque ID field used to distinguish the LSAs. Rules for building the router-additions-LSA are described in Section 2.2.1 above. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS age | Options | 10 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Opaque Type | Opaque ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Advertising Router | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS checksum | length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 | # links | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Link ID | P +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ E | Link Data | R +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | # TOS | TOS 0 metric | # + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ L # | TOS | 0 | metric | I T +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ N O | ... | K S +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ S | | TOS | 0 | metric | | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | ... | The router-additions-LSA The format of the router-additions-LSA is identical to the router- LSA, except for the following differences: o Multiple router-addition-LSAs can be originated, distinguished by Opaque ID. The value of Opaque ID can be arbitrary. Note the similarity to the OSPF for IPv6 router-LSA [Ref5]. Moy [Page 10]
Internet Draft OSPF Subset Flooding February 2001 o The router-additions-LSA has no rtype field. Moy [Page 11]
Internet Draft OSPF Subset Flooding February 2001 A.3 Network-additions-LSA The network-additions-LSA is an area-scoped Opaque-LSA, having Opaque Type equal to TBD2. It is used by the Designated Router on a broadcast or NBMA segment to advertise its forwarding adjacencies on the segment, and uses a similar format to the network-LSA. The router's collection of forwarding adjacencies can be listed in one or more network-additions-LSAs, with the Opaque ID field used to distinguish the LSAs. Rules for building the network-additions-LSA are described in Section 2.2.1 above. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS age | Options | 10 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Opaque Type | Opaque ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Advertising Router | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LS checksum | length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Network Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Network Mask | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Attached Router | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | The format of the network-additions-LSA is identical to the network- LSA, except for the following differences: o The IP address of the network segment is included in the body of the network-additions-LSA, in the "Network Address" field. As in standard OSPF, this is the IP address of the segment's Designated Router. o Multiple network-addition-LSAs can be originated, distinguished by Opaque ID. The value of Opaque ID can be arbitrary. Moy [Page 12]
Internet Draft OSPF Subset Flooding February 2001 Security Considerations This memo does not create any new security issues for the OSPF protocol. Security considerations for the base OSPF protocol are covered in [Ref1]. Authors' Addresses J. Moy Sycamore Networks, Inc. 150 Apollo Drive Chelmsford, MA 01824 Phone: (978) 367-2505 Fax: (978) 256-4203 email: jmoy@sycamorenet.com Moy [Page 13]
