Tech-invite3GPPspaceIETF RFCsSIP
in Index   Prev   Next

RFC 2178

OSPF Version 2

Pages: 211
Obsoletes:  1583
Obsoleted by:  2328
Part 8 of 8 – Pages 201 to 211
First   Prev   None

ToP   noToC   RFC2178 - Page 201   prevText
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).
ToP   noToC   RFC2178 - Page 202
   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

        (a) A Link State ID of is used.

    (2) Router A then wants to originate an AS-external-LSA for

        (a) The LSA for [10.0.0,0,] is reoriginated using a
            new Link State ID of

        (b) A Link State ID of is used for

    (3) Router A then wants to originate an AS-external-LSA for

        (a) The LSA for [,] is reoriginated using a
            new Link State ID of

        (b) A Link State ID of is used for

        (c) The network [,] keeps its Link State ID
ToP   noToC   RFC2178 - Page 203
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

     Method 2 has the following disadvantages:

     (1) You lose the bidirectionality test on the secondary

     (2) When the primary interface fails, you need to promote the
         secondary interface to primary status.
ToP   noToC   RFC2178 - Page 204
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
ToP   noToC   RFC2178 - Page 205
   designed to work simply and naturally when faced with partial mesh

   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

   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

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 [,] 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
ToP   noToC   RFC2178 - Page 206
   work with RFC 1583, you must not summarize the subnets of Area X with
   the single range [,], because then the subnets of 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

   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

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).
ToP   noToC   RFC2178 - Page 207
   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 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, with the same type 2
   metric. Router A1 selects B1 as its next hop towards,
   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, resulting in a
   routing loop.
ToP   noToC   RFC2178 - Page 208
   The following two changes have been made to prevent these routing

   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

                                | 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

   hop to, 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.
ToP   noToC   RFC2178 - Page 209
   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

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

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
ToP   noToC   RFC2178 - Page 210
   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.
ToP   noToC   RFC2178 - Page 211
Author's Address

   John Moy
   Cascade Communications Corp.
   5 Carlisle Road
   Westford, MA 01886

   Phone: 508-952-1367
   Fax:   508-692-9214