RFC 2178
OSPF Version 2
E. An algorithm for assigning Link State IDs The Link State ID in AS-external-LSAs and summary-LSAs is usually set to the described network's IP address. However, if necessary one or more of the network's host bits may be set in the Link State ID. This allows the router to originate separate LSAs for networks having the same address, yet different masks. Such networks can occur in the presence of supernetting and subnet 0s (see [Ref10]). This appendix gives one possible algorithm for setting the host bits in Link State IDs. The choice of such an algorithm is a local decision. Separate routers are free to use different algorithms, since the only LSAs affected are the ones that the router itself originates. The only requirement on the algorithms used is that the network's IP address should be used as the Link State ID whenever possible; this maximizes interoperability with OSPF implementations predating RFC 1583. The algorithm below is stated for AS-external-LSAs. This is only for clarity; the exact same algorithm can be used for summary-LSAs. Suppose that the router wishes to originate an AS-external-LSA for a network having address NA and mask NM1. The following steps are then used to determine the LSA's Link State ID: (1) Determine whether the router is already originating an AS- external-LSA with Link State ID equal to NA (in such an LSA the router itself will be listed as the LSA's Advertising Router). If not, the Link State ID is set equal to NA and the algorithm terminates. Otherwise, (2) Obtain the network mask from the body of the already existing AS-external-LSA. Call this mask NM2. There are then two cases: o NM1 is longer (i.e., more specific) than NM2. In this case, set the Link State ID in the new LSA to be the network [NA,NM1] with all the host bits set (i.e., equal to NA or'ed together with all the bits that are not set in NM1, which is network [NA,NM1]'s broadcast address). o NM2 is longer than NM1. In this case, change the existing LSA (having Link State ID of NA) to reference the new network [NA,NM1] by incrementing the sequence number, changing the mask in the body to NM1 and inserting the cost of the new network. Then originate a new LSA for the old network [NA,NM2], with Link State ID equal to NA or'ed together with the bits that are not set in NM2 (i.e., network [NA,NM2]'s broadcast address).
The above algorithm assumes that all masks are contiguous; this
ensures that when two networks have the same address, one mask is
more specific than the other. The algorithm also assumes that no
network exists having an address equal to another network's broadcast
address. Given these two assumptions, the above algorithm always
produces unique Link State IDs. The above algorithm can also be
reworded as follows: When originating an AS-external-LSA, try to use
the network number as the Link State ID. If that produces a
conflict, examine the two networks in conflict. One will be a subset
of the other. For the less specific network, use the network number
as the Link State ID and for the more specific use the network's
broadcast address instead (i.e., flip all the "host" bits to 1). If
the most specific network was originated first, this will cause you
to originate two LSAs at once.
As an example of the algorithm, consider its operation when the
following sequence of events occurs in a single router (Router A).
(1) Router A wants to originate an AS-external-LSA for
[10.0.0.0,255.255.255.0]:
(a) A Link State ID of 10.0.0.0 is used.
(2) Router A then wants to originate an AS-external-LSA for
[10.0.0.0,255.255.0.0]:
(a) The LSA for [10.0.0,0,255.255.255.0] is reoriginated using a
new Link State ID of 10.0.0.255.
(b) A Link State ID of 10.0.0.0 is used for
[10.0.0.0,255.255.0.0].
(3) Router A then wants to originate an AS-external-LSA for
[10.0.0.0,255.0.0.0]:
(a) The LSA for [10.0.0.0,255.255.0.0] is reoriginated using a
new Link State ID of 10.0.255.255.
(b) A Link State ID of 10.0.0.0 is used for
[10.0.0.0,255.0.0.0].
(c) The network [10.0.0.0,255.255.255.0] keeps its Link State ID
of 10.0.0.255.
F. Multiple interfaces to the same network/subnet There are at least two ways to support multiple physical interfaces to the same IP subnet. Both methods will interoperate with implementations of RFC 1583 (and of course this memo). The two methods are sketched briefly below. An assumption has been made that each interface has been assigned a separate IP address (otherwise, support for multiple interfaces is more of a link-level or ARP issue than an OSPF issue). Method 1: Run the entire OSPF functionality over both interfaces, sending and receiving hellos, flooding, supporting separate interface and neighbor FSMs for each interface, etc. When doing this all other routers on the subnet will treat the two interfaces as separate neighbors, since neighbors are identified (on broadcast and NBMA networks) by their IP address. Method 1 has the following disadvantages: (1) You increase the total number of neighbors and adjacencies. (2) You lose the bidirectionality test on both interfaces, since bidirectionality is based on Router ID. (3) You have to consider both interfaces together during the Designated Router election, since if you declare both to be DR simultaneously you can confuse the tie-breaker (which is Router ID). Method 2: Run OSPF over only one interface (call it the primary interface), but include both the primary and secondary interfaces in your Router-LSA. Method 2 has the following disadvantages: (1) You lose the bidirectionality test on the secondary interface. (2) When the primary interface fails, you need to promote the secondary interface to primary status.
G. Differences from RFC 1583 This section documents the differences between this memo and RFC 1583. All differences are backward-compatible. Implementations of this memo and of RFC 1583 will interoperate. G.1 Enhancements to OSPF authentication An additional OSPF authentication type has been added: the Cryptographic authentication type. This has been defined so that any arbitrary "Keyed Message Digest" algorithm can be used for packet authentication. Operation using the MD5 algorithm is completely specified (see Appendix D). A number of other changes were also made to OSPF packet authentication, affecting the following Sections: o The authentication type is now specified per-interface, rather than per-area (Sections 6, 9, C.2 and C.3). o The OSPF packet header checksum is now considered part of the authentication procedure, and so has been moved out of the packet send and receive logic (Sections 8.1 and 8.2) and into the description of authentication types (Appendix D). o In Appendix D, sections detailing message generation and message verification have been added. o For the OSPF Cryptographic authentication type, a discussion of key management, including the requirement for simultaneous support of multiple keys, key lifetimes and smooth key transition, has been added to Appendix D. G.2 Addition of Point-to-MultiPoint interface This memo adds an additional method for running OSPF over non- broadcast networks: the Point-to-Multipoint network. To implement this addition, the language of RFC 1583 has been altered slightly. References to "multi-access" networks have been deleted. The term "non-broadcast networks" is now used to describe networks which can connect many routers, but which do not natively support broadcast/multicast (such as a public Frame relay network). Over non-broadcast networks, there are two options for running OSPF: modelling them as "NBMA networks" or as "Point-to-MultiPoint networks". NBMA networks require full mesh connectivity between routers; when employing NBMA networks in the presence of partial mesh connectivity, multiple NBMA networks must be configured, as described in [Ref15]. In contrast, Point-to-Multipoint networks have been
designed to work simply and naturally when faced with partial mesh
connectivity.
The addition of Point-to-MultiPoint networks has impacted the text in
many places, which are briefly summarized below:
o Section 2 describing the OSPF link-state database has been
split into additional subsections, with one of the subsections
(Section 2.1.1) describing the differing map representations of
the two non-broadcast network options. This subsection also
contrasts the NBMA network and Point- to-MultiPoint network
options, and describes the situations when one is preferable to
the other.
o In contrast to NBMA networks, Point-to-MultiPoint networks
have the following properties. Adjacencies are established
between all neighboring routers (Sections 4, 7.1, 7.5, 9.5 and
10.4). There is no Designated Router or Backup Designated Router
for a Point-to-MultiPoint network (Sections 7.3 and 7.4). No
network-LSA is originated for Point-to-MultiPoint networks
(Sections 12.4.2 and A.4.3). Router Priority is not configured
for Point-to-MultiPoint interfaces, nor for neighbors on Point-
to-MultiPoint networks (Sections C.3 and C.6).
o The Interface FSM for a Point-to-MultiPoint interface is
identical to that used for point-to-point interfaces. Two states
are possible: "Down" and "Point-to-Point" (Section 9.3).
o When originating a router-LSA, and Point-to-MultiPoint
interface is reported as a collection of "point-to-point links"
to all of the interface's adjacent neighbors, together with a
single stub link advertising the interface's IP address with a
cost of 0 (Section 12.4.1.4).
o When flooding out a non-broadcast interface (when either in
NBMA or Point-to-MultiPoint mode) the Link State Update or Link
State Acknowledgment packet must be replicated in order to be
sent to each of the interface's neighbors (see Sections 13.3 and
13.5).
G.3 Support for overlapping area ranges
RFC 1583 requires that all networks falling into a given area range
actually belong to a single area. This memo relaxes that restriction.
This is useful in the following example. Suppose that [10.0.0.0,
255.0.0.0] is carved up into subnets. Most of these subnets are
assigned to a single OSPF area (call it Area X), while a few subnets
are assigned to other areas. In order to get this configuration to
work with RFC 1583, you must not summarize the subnets of Area X with the single range [10.0.0.0, 255.0.0.0], because then the subnets of 10.0.0.0 belonging to other areas would become unreachable. However, with this memo you can summarize the subnets in Area X, provided that the subnets belonging to other areas are not summarized. Implementation details for this change can be found in Sections 11.1 and 16.2. G.4 A modification to the flooding algorithm The OSPF flooding algorithm has been modified as follows. When a Link State Update Packet is received that contains an LSA instance which is actually less recent than the the router's current database copy, the router will now in most cases respond by flooding back its database copy. This is in contrast to the RFC 1583 behavior, which was to simply throw the received LSA away. Detailed description of the change can be found in Step 8 of Section 13. This change improves MaxAge processing. There are times when MaxAge LSAs stay in a router's database for extended intervals: 1) when they are stuck in a retransmission queue on a slow link or 2) when a router is not properly flushing them from its database, due to software bugs. The prolonged existence of these MaxAge LSAs can inhibit the flooding of new instances of the LSA. New instances typically start with LS sequence number equal to InitialSequenceNumber, and are treated as less recent (and hence were discarded according to RFC 1583) by routers still holding MaxAge instances. However, with the above change to flooding, a router holding a MaxAge instance will flood back the MaxAge instance. When this flood reaches the LSA's originator, it will then pick the next highest LS sequence number and reflood, overwriting the MaxAge instance. G.5 Introduction of the MinLSArrival constant OSPF limits the frequency that new instances of any particular LSA can be accepted during flooding. This is extra protection, just in case a neighboring router is violating the mandated limit on LSA (re)originations (namely, one per LSA in any MinLSInterval).
In RFC 1583, the frequency at which new LSA instances were accepted was also set equal to once every MinLSInterval seconds. However, in some circumstances this led to unwanted link state retransmissions, even when the LSA originator was obeying the MinLSInterval limit on originations. This was due to either 1) choice of clock granularity in some OSPF implementations or 2) differing clock speed in neighboring routers. To alleviate this problem, the frequency at which new LSA instances are accepted during flooding has now been increased to once every MinLSArrival seconds, whose value is set to 1. This change is reflected in Steps 5a and 5d of Section 13, and in Appendix B. G.6 Optionally advertising point-to-point links as subnets When describing a point-to-point interface in its router-LSA, a router may now advertise a stub link to the point-to-point network's subnet. This is specified as an alternative to the RFC 1583 behavior, which is to advertise a stub link to the neighbor's IP address. See Sections 12.4.1 and 12.4.1.1 for details. G.7 Advertising same external route from multiple areas This document fixes routing loops which can occur in RFC 1583 when the same external destination is advertised by AS boundary routers in separate areas. There are two manifestations of this problem. The first, discovered by Dennis Ferguson, occurs when an aggregated forwarding address is in use. In this case, the desirability of the forwarding address can change for the worse as a packet crosses an area aggregation boundary on the way to the forwarding address, which in turn can cause the preference of AS-external-LSAs to change, resulting in a routing loop. The second manifestation was discovered by Richard Woundy. It is caused by an incomplete application of OSPF's preference of intra- area routes over inter-area routes: paths to any given ASBR/forwarding address are selected first based on intra-area preference, while the comparison between separate ASBRs/forwarding addresses is driven only by cost, ignoring intra-area preference. His example is replicated in Figure 19. Both router A3 and router B3 are originating an AS-external-LSA for 10.0.0.0/8, with the same type 2 metric. Router A1 selects B1 as its next hop towards 10.0.0.0/8, based on shorter cost to ASBR B3 (via B1->B2->B3). However, the shorter route to B3 is not available to B1, due to B1's preference for the (higher cost) intra-area route to B3 through Area A. This leads B1 to select A1 as its next hop to 10.0.0.0/8, resulting in a routing loop.
The following two changes have been made to prevent these routing
loops:
o When originating a type 3 summary-LSA for a configured area
address range, the cost of the summary-LSA is now set to the
maximum cost of the range's component networks (instead of the
previous algorithm which set the cost to the minimum component
cost). This change affects Sections 3.5 and 12.4.3, Figures 7
and 8, and Tables 6 and 13.
o The preference rules for choosing among multiple AS-
external-LSAs have been changed. Where previously cost was the
only determining factor, now the preference is driven first by
type of path (intra-area or inter-area, through non-backbone area
or through backbone) to the ASBR/forwarding address, using cost
only to break ties. This change affects Sections 16.4 and 16.4.1.
After implementing this change, the example in Figure 19 is modified
as follows. Router A1 now chooses A3 as the next
10.0.0.0/8
----------
|
+----+
| XX |
+----+
RIP / \ RIP
--------------------- --------------------
! !
! !
+----+ +----+ 1 +----+......+----+....
| A3 |------| A1 |---------------| B1 |------| B3 | .
+----+ 6 +----+ +----+ 8 +----+ .
1| . / .
OSPF backbone | . / .
+----+ 2 / .
| B2 |------- Area A.
+----+................
Figure 19: Example routing loop when the
same external route is advertised from multiple
areas
hop to 10.0.0.0/8, while B1 chooses B3 as next hop. The reason for
both choices is that ASBRs/forwarding addresses are now chosen based
first on intra-area preference, and then by cost.
Unfortunately, this change is not backward compatible. While the change prevents routing loops when all routers run the new preference rules, it can actually create routing loops when some routers are running the new preference rules and other routers implement RFC 1583. For this reason, a new configuration parameter has been added: RFC1583Compatibility. Only when RFC1583Compatibility is set to "disabled" will the new preference rules take effect. See Appendix C for more details. G.8 Retransmission of initial Database Description packets This memo allows retransmission of initial Database Description packets, without resetting the state of the adjacency. In some environments, retransmission of the initial Database Description packet may be unavoidable. For example, the link delay incurred by a satellite link may exceed the value configured for an interface's RxmtInterval. In RFC 1583 such an environment prevents a full adjacency from ever forming. In this memo, changes have been made in the reception of Database Description packets so that retransmitted initial Database Description packets are treated identically to any other retransmitted Database Description packets. See Section 10.6 for details. G.9 Detecting interface MTU mismatches When two neighboring routers have a different interface MTU for their common network segment, serious problems can ensue: large packets are prevented from being successfully transferred from one router to the other, impairing OSPF's flooding algorithm and possibly creating "black holes" for user data traffic. This memo provides a fix for the interface MTU mismatch problem by advertising the interface MTU in Database Description packets. When a router receives a Database description packet advertising an MTU larger than the router can receive, the router drops the Database Description packet. This prevents an adjacency from forming, telling OSPF flooding and user data traffic to avoid the connection between the two routers. For more information, see Sections 10.6, 10.8, and A.3.3. G.10 Deleting the TOS routing option The TOS routing option has been deleted from OSPF. This action was required by the Internet standards process ([Ref24]), due to lack of implementation experience with OSPF's TOS routing. However, for backward compatibility the formats of OSPF's various LSAs remain
unchanged, maintaining the ability to specify TOS metrics in router- LSAs, summary-LSAs, ASBR-summary-LSAs, and AS-external-LSAs (see Sections 12.3, A.4.2, A.4.4, and A.4.5). To see OSPF's original TOS routing design, consult [Ref9]. Security Considerations All OSPF protocol exchanges are authenticated. OSPF supports multiple types of authentication; the type of authentication in use can be configured on a per network segment basis. One of OSPF's authentication types, namely the Cryptographic authentication option, is believed to be secure against passive attacks and provide significant protection against active attacks. When using the Cryptographic authentication option, each router appends a "message digest" to its transmitted OSPF packets. Receivers then use the shared secret key and received digest to verify that each received OSPF packet is authentic. The quality of the security provided by the Cryptographic authentication option depends completely on the strength of the message digest algorithm (MD5 is currently the only message digest algorithm specified), the strength of the key being used, and the correct implementation of the security mechanism in all communicating OSPF implementations. It also requires that all parties maintain the secrecy of the shared secret key. None of the OSPF authentication types provide confidentiality. Nor do they protect against traffic analysis. Key management is also not addressed by this memo. For more information, see Sections 8.1, 8.2, and Appendix D.
Author's Address John Moy Cascade Communications Corp. 5 Carlisle Road Westford, MA 01886 Phone: 508-952-1367 Fax: 508-692-9214 Email: jmoy@casc.com