(a) The received digest is set aside.
(b) A new digest is calculated, as specified in Step 6
of Section D.4.3.
(c) The calculated and received digests are compared. If
they do not match, the OSPF packet is discarded. If
they do match, the OSPF protocol packet is accepted
as authentic, and the "cryptographic sequence
number" in the neighbor's data structure is set to
the sequence number found in the packet's OSPF
header.
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 RFC1583.
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 RFC1583 (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 RFC1583
This section documents the differences between this memo and RFC
1583. All differences are backward-compatible. Implementations of
this memo and of RFC1583 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 RFC1583 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
RFC1583 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 RFC1583, 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 RFC1583 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 RFC1583) 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 RFC1583, 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 RFC1583 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 RFC1583 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 RFC1583 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