Tech-invite3GPPspaceIETFspace
959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 2328

OSPF Version 2

Pages: 244
Internet Standard: 54
Errata
Obsoletes:  2178
Updated by:  57096549684568607474804293559454
Part 6 of 8 – Pages 135 to 168
First   Prev   Next

Top   ToC   RFC2328 - Page 135   prevText
        12.4.3.  Summary-LSAs

            The destination described by a summary-LSA is either an IP
            network, an AS boundary router or a range of IP addresses.
            Summary-LSAs are flooded throughout a single area only.  The
            destination described is one that is external to the area,
            yet still belongs to the Autonomous System.

            Summary-LSAs are originated by area border routers.  The
            precise summary routes to advertise into an area are
            determined by examining the routing table structure (see
            Section 11) in accordance with the algorithm described
            below. Note that only intra-area routes are advertised into
            the backbone, while both intra-area and inter-area routes
            are advertised into the other areas.

            To determine which routes to advertise into an attached Area
            A, each routing table entry is processed as follows.
            Remember that each routing table entry describes a set of
            equal-cost best paths to a particular destination:

            o   Only Destination Types of network and AS boundary router
                are advertised in summary-LSAs.  If the routing table
                entry's Destination Type is area border router, examine
                the next routing table entry.

            o   AS external routes are never advertised in summary-LSAs.
                If the routing table entry has Path-type of type 1
                external or type 2 external, examine the next routing
                table entry.
Top   ToC   RFC2328 - Page 136
            o   Else, if the area associated with this set of paths is
                the Area A itself, do not generate a summary-LSA for the
                route.[17]

            o   Else, if the next hops associated with this set of paths
                belong to Area A itself, do not generate a summary-LSA
                for the route.[18] This is the logical equivalent of a
                Distance Vector protocol's split horizon logic.

            o   Else, if the routing table cost equals or exceeds the
                value LSInfinity, a summary-LSA cannot be generated for
                this route.

            o   Else, if the destination of this route is an AS boundary
                router, a summary-LSA should be originated if and only
                if the routing table entry describes the preferred path
                to the AS boundary router (see Step 3 of Section 16.4).
                If so, a Type 4 summary-LSA is originated for the
                destination, with Link State ID equal to the AS boundary
                router's Router ID and metric equal to the routing table
                entry's cost. Note: these LSAs should not be generated
                if Area A has been configured as a stub area.

            o   Else, the Destination type is network. If this is an
                inter-area route, generate a Type 3 summary-LSA for the
                destination, with Link State ID equal to the network's
                address (if necessary, the Link State ID can also have
                one or more of the network's host bits set; see Appendix
                E for details) and metric equal to the routing table
                cost.

            o   The one remaining case is an intra-area route to a
                network.  This means that the network is contained in
                one of the router's directly attached areas.  In
                general, this information must be condensed before
                appearing in summary-LSAs.  Remember that an area has a
                configured list of address ranges, each range consisting
                of an [address,mask] pair and a status indication of
                either Advertise or DoNotAdvertise.  At most a single
                Type 3 summary-LSA is originated for each range. When
                the range's status indicates Advertise, a Type 3
                summary-LSA is generated with Link State ID equal to the
Top   ToC   RFC2328 - Page 137
                range's address (if necessary, the Link State ID can
                also have one or more of the range's "host" bits set;
                see Appendix E for details) and cost equal to the
                largest cost of any of the component networks. When the
                range's status indicates DoNotAdvertise, the Type 3
                summary-LSA is suppressed and the component networks
                remain hidden from other areas.

                By default, if a network is not contained in any
                explicitly configured address range, a Type 3 summary-
                LSA is generated with Link State ID equal to the
                network's address (if necessary, the Link State ID can
                also have one or more of the network's "host" bits set;
                see Appendix E for details) and metric equal to the
                network's routing table cost.

                If an area is capable of carrying transit traffic (i.e.,
                its TransitCapability is set to TRUE), routing
                information concerning backbone networks should not be
                condensed before being summarized into the area.  Nor
                should the advertisement of backbone networks into
                transit areas be suppressed.  In other words, the
                backbone's configured ranges should be ignored when
                originating summary-LSAs into transit areas.

            If a router advertises a summary-LSA for a destination which
            then becomes unreachable, the router must then flush the LSA
            from the routing domain by setting its age to MaxAge and
            reflooding (see Section 14.1).  Also, if the destination is
            still reachable, yet can no longer be advertised according
            to the above procedure (e.g., it is now an inter-area route,
            when it used to be an intra-area route associated with some
            non-backbone area; it would thus no longer be advertisable
            to the backbone), the LSA should also be flushed from the
            routing domain.


            12.4.3.1.  Originating summary-LSAs into stub areas

                The algorithm in Section 12.4.3 is optional when Area A
                is an OSPF stub area. Area border routers connecting to
                a stub area can originate summary-LSAs into the area
Top   ToC   RFC2328 - Page 138
                according to the Section 12.4.3's algorithm, or can
                choose to originate only a subset of the summary-LSAs,
                possibly under configuration control.  The fewer LSAs
                originated, the smaller the stub area's link state
                database, further reducing the demands on its routers'
                resources. However, omitting LSAs may also lead to sub-
                optimal inter-area routing, although routing will
                continue to function.

                As specified in Section 12.4.3, Type 4 summary-LSAs
                (ASBR-summary-LSAs) are never originated into stub
                areas.

                In a stub area, instead of importing external routes
                each area border router originates a "default summary-
                LSA" into the area. The Link State ID for the default
                summary-LSA is set to DefaultDestination, and the metric
                set to the (per-area) configurable parameter
                StubDefaultCost.  Note that StubDefaultCost need not be
                configured identically in all of the stub area's area
                border routers.


            12.4.3.2.  Examples of summary-LSAs

                Consider again the area configuration in Figure 6.
                Routers RT3, RT4, RT7, RT10 and RT11 are all area border
                routers, and therefore are originating summary-LSAs.
                Consider in particular Router RT4.  Its routing table
                was calculated as the example in Section 11.3.  RT4
                originates summary-LSAs into both the backbone and Area
                1.  Into the backbone, Router RT4 originates separate
                LSAs for each of the networks N1-N4.  Into Area 1,
                Router RT4 originates separate LSAs for networks N6-N8
                and the AS boundary routers RT5,RT7.  It also condenses
                host routes Ia and Ib into a single summary-LSA.
                Finally, the routes to networks N9,N10,N11 and Host H1
                are advertised by a single summary-LSA.  This
                condensation was originally performed by the router
                RT11.
Top   ToC   RFC2328 - Page 139
                These LSAs are illustrated graphically in Figures 7 and
                8.  Two of the summary-LSAs originated by Router RT4
                follow.  The actual IP addresses for the networks and
                routers in question have been assigned in Figure 15.

        ; Summary-LSA for Network N1,
        ; originated by Router RT4 into the backbone

        LS age = 0                  ;always true on origination
        Options = (E-bit)           ;
        LS type = 3                 ;Type 3 summary-LSA
        Link State ID = 192.1.2.0   ;N1's IP network number
        Advertising Router = 192.1.1.4       ;RT4's ID
        metric = 4

        ; Summary-LSA for AS boundary router RT7
        ; originated by Router RT4 into Area 1

        LS age = 0                  ;always true on origination
        Options = (E-bit)           ;
        LS type = 4                 ;Type 4 summary-LSA
        Link State ID = Router RT7's ID
        Advertising Router = 192.1.1.4       ;RT4's ID
        metric = 14

        12.4.4.  AS-external-LSAs

            AS-external-LSAs describe routes to destinations external to
            the Autonomous System.  Most AS-external-LSAs describe
            routes to specific external destinations; in these cases the
            LSA's Link State ID is set to the destination network's IP
            address (if necessary, the Link State ID can also have one
            or more of the network's "host" bits set; see Appendix E for
            details).  However, a default route for the Autonomous
            System can be described in an AS-external-LSA by setting the
            LSA's Link State ID to DefaultDestination (0.0.0.0).  AS-
            external-LSAs are originated by AS boundary routers.  An AS
            boundary router originates a single AS-external-LSA for each
            external route that it has learned, either through another
            routing protocol (such as BGP), or through configuration
            information.
Top   ToC   RFC2328 - Page 140
            AS-external-LSAs are the only type of LSAs that are flooded
            throughout the entire Autonomous System; all other types of
            LSAs are specific to a single area.  However, AS-external-
            LSAs are not flooded into/throughout stub areas (see Section
            3.6).  This enables a reduction in link state database size
            for routers internal to stub areas.

            The metric that is advertised for an external route can be
            one of two types.  Type 1 metrics are comparable to the link
            state metric.  Type 2 metrics are assumed to be larger than
            the cost of any intra-AS path.

            If a router advertises an AS-external-LSA for a destination
            which then becomes unreachable, the router must then flush
            the LSA from the routing domain by setting its age to MaxAge
            and reflooding (see Section 14.1).


            12.4.4.1.  Examples of AS-external-LSAs

                Consider once again the AS pictured in Figure 6.  There
                are two AS boundary routers: RT5 and RT7.  Router RT5
                originates three AS-external-LSAs, for networks N12-N14.
                Router RT7 originates two AS-external-LSAs, for networks
                N12 and N15.  Assume that RT7 has learned its route to
                N12 via BGP, and that it wishes to advertise a Type 2
                metric to the AS.  RT7 would then originate the
                following LSA for N12:

        ; AS-external-LSA for Network N12,
        ; originated by Router RT7

        LS age = 0                  ;always true on origination
        Options = (E-bit)           ;
        LS type = 5                 ;AS-external-LSA
        Link State ID = N12's IP network number
        Advertising Router = Router RT7's ID
        bit E = 1                   ;Type 2 metric
        metric = 2
        Forwarding address = 0.0.0.0
Top   ToC   RFC2328 - Page 141
                    In the above example, the forwarding address field
                    has been set to 0.0.0.0, indicating that packets for
                    the external destination should be forwarded to the
                    advertising OSPF router (RT7).  This is not always
                    desirable.  Consider the example pictured in Figure
                    16.  There are three OSPF routers (RTA, RTB and RTC)
                    connected to a common network.  Only one of these
                    routers, RTA, is exchanging BGP information with the
                    non-OSPF router RTX.  RTA must then originate AS-
                    external-LSAs for those destinations it has learned
                    from RTX.  By using the AS-external-LSA's forwarding
                    address field, RTA can specify that packets for
                    these destinations be forwarded directly to RTX.
                    Without this feature, Routers RTB and RTC would take
                    an extra hop to get to these destinations.

                    Note that when the forwarding address field is non-
                    zero, it should point to a router belonging to
                    another Autonomous System.

                    A forwarding address can also be specified for the
                    default route.  For example, in figure 16 RTA may
                    want to specify that all externally-destined packets
                    should by default be forwarded to its BGP peer RTX.
                    The resulting AS-external-LSA is pictured below.
                    Note that the Link State ID is set to
                    DefaultDestination.

        ; Default route, originated by Router RTA
        ; Packets forwarded through RTX

        LS age = 0                  ;always true on origination
        Options = (E-bit)           ;
        LS type = 5                 ;AS-external-LSA
        Link State ID = DefaultDestination  ; default route
        Advertising Router = Router RTA's ID
        bit E = 1                   ;Type 2 metric
        metric = 1
        Forwarding address = RTX's IP address

                    In figure 16, suppose instead that both RTA and RTB
                    exchange BGP information with RTX.  In this case,
Top   ToC   RFC2328 - Page 142
                    RTA and RTB would originate the same set of AS-
                    external-LSAs.  These LSAs, if they specify the same
                    metric, would be functionally equivalent since they
                    would specify the same destination and forwarding
                    address (RTX).  This leads to a clear duplication of
                    effort.  If only one of RTA or RTB originated the
                    set of AS-external-LSAs, the routing would remain
                    the same, and the size of the link state database
                    would decrease.  However, it must be unambiguously
                    defined as to which router originates the LSAs
                    (otherwise neither may, or the identity of the
                    originator may oscillate).  The following rule is
                    thereby established: if two routers, both reachable
                    from one another, originate functionally equivalent
                    AS-external-LSAs (i.e., same destination, cost and
                    non-zero forwarding address), then the LSA
                    originated by the router having the highest OSPF
                    Router ID is used.  The router having the lower OSPF
                    Router ID can then flush its LSA.  Flushing an LSA
                    is discussed in Section 14.1.


                                +
                                |
                      +---+.....|.BGP
                      |RTA|-----|.....+---+
                      +---+     |-----|RTX|
                                |     +---+
                      +---+     |
                      |RTB|-----|
                      +---+     |
                                |
                      +---+     |
                      |RTC|-----|
                      +---+     |
                                |
                                +


               Figure 16: Forwarding address example
Top   ToC   RFC2328 - Page 143
13.  The Flooding Procedure

    Link State Update packets provide the mechanism for flooding LSAs.
    A Link State Update packet may contain several distinct LSAs, and
    floods each LSA one hop further from its point of origination.  To
    make the flooding procedure reliable, each LSA must be acknowledged
    separately.  Acknowledgments are transmitted in Link State
    Acknowledgment packets.  Many separate acknowledgments can also be
    grouped together into a single packet.

    The flooding procedure starts when a Link State Update packet has
    been received.  Many consistency checks have been made on the
    received packet before being handed to the flooding procedure (see
    Section 8.2).  In particular, the Link State Update packet has been
    associated with a particular neighbor, and a particular area.  If
    the neighbor is in a lesser state than Exchange, the packet should
    be dropped without further processing.

    All types of LSAs, other than AS-external-LSAs, are associated with
    a specific area.  However, LSAs do not contain an area field.  An
    LSA's area must be deduced from the Link State Update packet header.

    For each LSA contained in a Link State Update packet, the following
    steps are taken:


    (1) Validate the LSA's LS checksum.  If the checksum turns out to be
        invalid, discard the LSA and get the next one from the Link
        State Update packet.

    (2) Examine the LSA's LS type.  If the LS type is unknown, discard
        the LSA and get the next one from the Link State Update Packet.
        This specification defines LS types 1-5 (see Section 4.3).

    (3) Else if this is an AS-external-LSA (LS type = 5), and the area
        has been configured as a stub area, discard the LSA and get the
        next one from the Link State Update Packet.  AS-external-LSAs
        are not flooded into/throughout stub areas (see Section 3.6).

    (4) Else if the LSA's LS age is equal to MaxAge, and there is
        currently no instance of the LSA in the router's link state
        database, and none of router's neighbors are in states Exchange
Top   ToC   RFC2328 - Page 144
        or Loading, then take the following actions: a) Acknowledge the
        receipt of the LSA by sending a Link State Acknowledgment packet
        back to the sending neighbor (see Section 13.5), and b) Discard
        the LSA and examine the next LSA (if any) listed in the Link
        State Update packet.

    (5) Otherwise, find the instance of this LSA that is currently
        contained in the router's link state database.  If there is no
        database copy, or the received LSA is more recent than the
        database copy (see Section 13.1 below for the determination of
        which LSA is more recent) the following steps must be performed:

        (a) If there is already a database copy, and if the database
            copy was received via flooding and installed less than
            MinLSArrival seconds ago, discard the new LSA (without
            acknowledging it) and examine the next LSA (if any) listed
            in the Link State Update packet.

        (b) Otherwise immediately flood the new LSA out some subset of
            the router's interfaces (see Section 13.3).  In some cases
            (e.g., the state of the receiving interface is DR and the
            LSA was received from a router other than the Backup DR) the
            LSA will be flooded back out the receiving interface.  This
            occurrence should be noted for later use by the
            acknowledgment process (Section 13.5).

        (c) Remove the current database copy from all neighbors' Link
            state retransmission lists.

        (d) Install the new LSA in the link state database (replacing
            the current database copy).  This may cause the routing
            table calculation to be scheduled.  In addition, timestamp
            the new LSA with the current time (i.e., the time it was
            received).  The flooding procedure cannot overwrite the
            newly installed LSA until MinLSArrival seconds have elapsed.
            The LSA installation process is discussed further in Section
            13.2.

        (e) Possibly acknowledge the receipt of the LSA by sending a
            Link State Acknowledgment packet back out the receiving
            interface.  This is explained below in Section 13.5.
Top   ToC   RFC2328 - Page 145
        (f) If this new LSA indicates that it was originated by the
            receiving router itself (i.e., is considered a self-
            originated LSA), the router must take special action, either
            updating the LSA or in some cases flushing it from the
            routing domain. For a description of how self-originated
            LSAs are detected and subsequently handled, see Section
            13.4.

    (6) Else, if there is an instance of the LSA on the sending
        neighbor's Link state request list, an error has occurred in the
        Database Exchange process.  In this case, restart the Database
        Exchange process by generating the neighbor event BadLSReq for
        the sending neighbor and stop processing the Link State Update
        packet.

    (7) Else, if the received LSA is the same instance as the database
        copy (i.e., neither one is more recent) the following two steps
        should be performed:

        (a) If the LSA is listed in the Link state retransmission list
            for the receiving adjacency, the router itself is expecting
            an acknowledgment for this LSA.  The router should treat the
            received LSA as an acknowledgment by removing the LSA from
            the Link state retransmission list.  This is termed an
            "implied acknowledgment".  Its occurrence should be noted
            for later use by the acknowledgment process (Section 13.5).

        (b) Possibly acknowledge the receipt of the LSA by sending a
            Link State Acknowledgment packet back out the receiving
            interface.  This is explained below in Section 13.5.

    (8) Else, the database copy is more recent.  If the database copy
        has LS age equal to MaxAge and LS sequence number equal to
        MaxSequenceNumber, simply discard the received LSA without
        acknowledging it. (In this case, the LSA's LS sequence number is
        wrapping, and the MaxSequenceNumber LSA must be completely
        flushed before any new LSA instance can be introduced).
        Otherwise, as long as the database copy has not been sent in a
        Link State Update within the last MinLSArrival seconds, send the
        database copy back to the sending neighbor, encapsulated within
        a Link State Update Packet. The Link State Update Packet should
        be sent directly to the neighbor. In so doing, do not put the
Top   ToC   RFC2328 - Page 146
        database copy of the LSA on the neighbor's link state
        retransmission list, and do not acknowledge the received (less
        recent) LSA instance.


    13.1.  Determining which LSA is newer

        When a router encounters two instances of an LSA, it must
        determine which is more recent.  This occurred above when
        comparing a received LSA to its database copy.  This comparison
        must also be done during the Database Exchange procedure which
        occurs during adjacency bring-up.

        An LSA is identified by its LS type, Link State ID and
        Advertising Router.  For two instances of the same LSA, the LS
        sequence number, LS age, and LS checksum fields are used to
        determine which instance is more recent:


        o   The LSA having the newer LS sequence number is more recent.
            See Section 12.1.6 for an explanation of the LS sequence
            number space.  If both instances have the same LS sequence
            number, then:

        o   If the two instances have different LS checksums, then the
            instance having the larger LS checksum (when considered as a
            16-bit unsigned integer) is considered more recent.

        o   Else, if only one of the instances has its LS age field set
            to MaxAge, the instance of age MaxAge is considered to be
            more recent.

        o   Else, if the LS age fields of the two instances differ by
            more than MaxAgeDiff, the instance having the smaller
            (younger) LS age is considered to be more recent.

        o   Else, the two instances are considered to be identical.
Top   ToC   RFC2328 - Page 147
    13.2.  Installing LSAs in the database

        Installing a new LSA in the database, either as the result of
        flooding or a newly self-originated LSA, may cause the OSPF
        routing table structure to be recalculated.  The contents of the
        new LSA should be compared to the old instance, if present.  If
        there is no difference, there is no need to recalculate the
        routing table. When comparing an LSA to its previous instance,
        the following are all considered to be differences in contents:

            o   The LSA's Options field has changed.

            o   One of the LSA instances has LS age set to MaxAge, and
                the other does not.

            o   The length field in the LSA header has changed.

            o   The body of the LSA (i.e., anything outside the 20-byte
                LSA header) has changed. Note that this excludes changes
                in LS Sequence Number and LS Checksum.

        If the contents are different, the following pieces of the
        routing table must be recalculated, depending on the new LSA's
        LS type field:


        Router-LSAs and network-LSAs
            The entire routing table must be recalculated, starting with
            the shortest path calculations for each area (not just the
            area whose link-state database has changed).  The reason
            that the shortest path calculation cannot be restricted to
            the single changed area has to do with the fact that AS
            boundary routers may belong to multiple areas.  A change in
            the area currently providing the best route may force the
            router to use an intra-area route provided by a different
            area.[19]

        Summary-LSAs
            The best route to the destination described by the summary-
            LSA must be recalculated (see Section 16.5).  If this
            destination is an AS boundary router, it may also be
            necessary to re-examine all the AS-external-LSAs.
Top   ToC   RFC2328 - Page 148
        AS-external-LSAs
            The best route to the destination described by the AS-
            external-LSA must be recalculated (see Section 16.6).


        Also, any old instance of the LSA must be removed from the
        database when the new LSA is installed.  This old instance must
        also be removed from all neighbors' Link state retransmission
        lists (see Section 10).


    13.3.  Next step in the flooding procedure

        When a new (and more recent) LSA has been received, it must be
        flooded out some set of the router's interfaces.  This section
        describes the second part of flooding procedure (the first part
        being the processing that occurred in Section 13), namely,
        selecting the outgoing interfaces and adding the LSA to the
        appropriate neighbors' Link state retransmission lists.  Also
        included in this part of the flooding procedure is the
        maintenance of the neighbors' Link state request lists.

        This section is equally applicable to the flooding of an LSA
        that the router itself has just originated (see Section 12.4).
        For these LSAs, this section provides the entirety of the
        flooding procedure (i.e., the processing of Section 13 is not
        performed, since, for example, the LSA has not been received
        from a neighbor and therefore does not need to be acknowledged).

        Depending upon the LSA's LS type, the LSA can be flooded out
        only certain interfaces.  These interfaces, defined by the
        following, are called the eligible interfaces:


        AS-external-LSAs (LS Type = 5)
            AS-external-LSAs are flooded throughout the entire AS, with
            the exception of stub areas (see Section 3.6).  The eligible
            interfaces are all the router's interfaces, excluding
            virtual links and those interfaces attaching to stub areas.

        All other LS types
            All other types are specific to a single area (Area A).  The
Top   ToC   RFC2328 - Page 149
            eligible interfaces are all those interfaces attaching to
            the Area A.  If Area A is the backbone, this includes all
            the virtual links.


        Link state databases must remain synchronized over all
        adjacencies associated with the above eligible interfaces.  This
        is accomplished by executing the following steps on each
        eligible interface.  It should be noted that this procedure may
        decide not to flood an LSA out a particular interface, if there
        is a high probability that the attached neighbors have already
        received the LSA.  However, in these cases the flooding
        procedure must be absolutely sure that the neighbors eventually
        do receive the LSA, so the LSA is still added to each
        adjacency's Link state retransmission list.  For each eligible
        interface:


        (1) Each of the neighbors attached to this interface are
            examined, to determine whether they must receive the new
            LSA.  The following steps are executed for each neighbor:

            (a) If the neighbor is in a lesser state than Exchange, it
                does not participate in flooding, and the next neighbor
                should be examined.

            (b) Else, if the adjacency is not yet full (neighbor state
                is Exchange or Loading), examine the Link state request
                list associated with this adjacency.  If there is an
                instance of the new LSA on the list, it indicates that
                the neighboring router has an instance of the LSA
                already.  Compare the new LSA to the neighbor's copy:

                o   If the new LSA is less recent, then examine the next
                    neighbor.

                o   If the two copies are the same instance, then delete
                    the LSA from the Link state request list, and
                    examine the next neighbor.[20]

                o   Else, the new LSA is more recent.  Delete the LSA
                    from the Link state request list.
Top   ToC   RFC2328 - Page 150
            (c) If the new LSA was received from this neighbor, examine
                the next neighbor.

            (d) At this point we are not positive that the neighbor has
                an up-to-date instance of this new LSA.  Add the new LSA
                to the Link state retransmission list for the adjacency.
                This ensures that the flooding procedure is reliable;
                the LSA will be retransmitted at intervals until an
                acknowledgment is seen from the neighbor.

        (2) The router must now decide whether to flood the new LSA out
            this interface.  If in the previous step, the LSA was NOT
            added to any of the Link state retransmission lists, there
            is no need to flood the LSA out the interface and the next
            interface should be examined.

        (3) If the new LSA was received on this interface, and it was
            received from either the Designated Router or the Backup
            Designated Router, chances are that all the neighbors have
            received the LSA already.  Therefore, examine the next
            interface.

        (4) If the new LSA was received on this interface, and the
            interface state is Backup (i.e., the router itself is the
            Backup Designated Router), examine the next interface.  The
            Designated Router will do the flooding on this interface.
            However, if the Designated Router fails the router (i.e.,
            the Backup Designated Router) will end up retransmitting the
            updates.

        (5) If this step is reached, the LSA must be flooded out the
            interface.  Send a Link State Update packet (including the
            new LSA as contents) out the interface.  The LSA's LS age
            must be incremented by InfTransDelay (which must be > 0)
            when it is copied into the outgoing Link State Update packet
            (until the LS age field reaches the maximum value of
            MaxAge).

            On broadcast networks, the Link State Update packets are
            multicast.  The destination IP address specified for the
            Link State Update Packet depends on the state of the
            interface.  If the interface state is DR or Backup, the
Top   ToC   RFC2328 - Page 151
            address AllSPFRouters should be used.  Otherwise, the
            address AllDRouters should be used.

            On non-broadcast networks, separate Link State Update
            packets must be sent, as unicasts, to each adjacent neighbor
            (i.e., those in state Exchange or greater).  The destination
            IP addresses for these packets are the neighbors' IP
            addresses.


    13.4.  Receiving self-originated LSAs

        It is a common occurrence for a router to receive self-
        originated LSAs via the flooding procedure. A self-originated
        LSA is detected when either 1) the LSA's Advertising Router is
        equal to the router's own Router ID or 2) the LSA is a network-
        LSA and its Link State ID is equal to one of the router's own IP
        interface addresses.

        However, if the received self-originated LSA is newer than the
        last instance that the router actually originated, the router
        must take special action.  The reception of such an LSA
        indicates that there are LSAs in the routing domain that were
        originated by the router before the last time it was restarted.
        In most cases, the router must then advance the LSA's LS
        sequence number one past the received LS sequence number, and
        originate a new instance of the LSA.

        It may be the case the router no longer wishes to originate the
        received LSA. Possible examples include: 1) the LSA is a
        summary-LSA or AS-external-LSA and the router no longer has an
        (advertisable) route to the destination, 2) the LSA is a
        network-LSA but the router is no longer Designated Router for
        the network or 3) the LSA is a network-LSA whose Link State ID
        is one of the router's own IP interface addresses but whose
        Advertising Router is not equal to the router's own Router ID
        (this latter case should be rare, and it indicates that the
        router's Router ID has changed since originating the LSA).  In
        all these cases, instead of updating the LSA, the LSA should be
        flushed from the routing domain by incrementing the received
        LSA's LS age to MaxAge and reflooding (see Section 14.1).
Top   ToC   RFC2328 - Page 152
    13.5.  Sending Link State Acknowledgment packets

        Each newly received LSA must be acknowledged.  This is usually
        done by sending Link State Acknowledgment packets.  However,
        acknowledgments can also be accomplished implicitly by sending
        Link State Update packets (see step 7a of Section 13).

        Many acknowledgments may be grouped together into a single Link
        State Acknowledgment packet.  Such a packet is sent back out the
        interface which received the LSAs.  The packet can be sent in
        one of two ways: delayed and sent on an interval timer, or sent
        directly to a particular neighbor.  The particular
        acknowledgment strategy used depends on the circumstances
        surrounding the receipt of the LSA.

        Sending delayed acknowledgments accomplishes several things: 1)
        it facilitates the packaging of multiple acknowledgments in a
        single Link State Acknowledgment packet, 2) it enables a single
        Link State Acknowledgment packet to indicate acknowledgments to
        several neighbors at once (through multicasting) and 3) it
        randomizes the Link State Acknowledgment packets sent by the
        various routers attached to a common network.  The fixed
        interval between a router's delayed transmissions must be short
        (less than RxmtInterval) or needless retransmissions will ensue.

        Direct acknowledgments are sent directly to a particular
        neighbor in response to the receipt of duplicate LSAs. Direct
        acknowledgments are sent immediately when the duplicate is
        received. On multi-access networks, these acknowledgments are
        sent directly to the neighbor's IP address.

        The precise procedure for sending Link State Acknowledgment
        packets is described in Table 19.  The circumstances surrounding
        the receipt of the LSA are listed in the left column.  The
        acknowledgment action then taken is listed in one of the two
        right columns.  This action depends on the state of the
        concerned interface; interfaces in state Backup behave
        differently from interfaces in all other states.  Delayed
        acknowledgments must be delivered to all adjacent routers
        associated with the interface.  On broadcast networks, this is
        accomplished by sending the delayed Link State Acknowledgment
        packets as multicasts.  The Destination IP address used depends
Top   ToC   RFC2328 - Page 153
                                     Action taken in state
   Circumstances            Backup                All other states
   _________________________________________________________________
   LSA  has                 No  acknowledgment    No  acknowledgment
   been  flooded back       sent.                 sent.
   out receiving  in-
   terface  (see Sec-
   tion 13, step 5b).
   _________________________________________________________________
   LSA   is                 Delayed acknowledg-   Delayed       ack-
   more  recent  than       ment sent if adver-   nowledgment sent.
   database copy, but       tisement   received
   was   not  flooded       from    Designated
   back out receiving       Router,  otherwise
   interface                do nothing
   _________________________________________________________________
   LSA is a                 Delayed acknowledg-   No  acknowledgment
   duplicate, and was       ment sent if adver-   sent.
   treated as an  im-       tisement   received
   plied  acknowledg-       from    Designated
   ment (see  Section       Router,  otherwise
   13, step 7a).            do nothing
   _________________________________________________________________
   LSA is a                 Direct acknowledg-    Direct acknowledg-
   duplicate, and was       ment sent.            ment sent.
   not treated as  an
   implied       ack-
   nowledgment.
   _________________________________________________________________
   LSA's LS                 Direct acknowledg-    Direct acknowledg-
   age is equal to          ment sent.            ment sent.
   MaxAge, and there is
   no current instance
   of the LSA
   in the link state
   database, and none
   of router's neighbors
   are in states Exchange
Top   ToC   RFC2328 - Page 154
   or Loading (see
   Section 13, step 4).


             Table 19: Sending link state acknowledgements.




        on the state of the interface.  If the interface state is DR or
        Backup, the destination AllSPFRouters is used.  In all other
        states, the destination AllDRouters is used.  On non-broadcast
        networks, delayed Link State Acknowledgment packets must be
        unicast separately over each adjacency (i.e., neighbor whose
        state is >= Exchange).

        The reasoning behind sending the above packets as multicasts is
        best explained by an example.  Consider the network
        configuration depicted in Figure 15.  Suppose RT4 has been
        elected as Designated Router, and RT3 as Backup Designated
        Router for the network N3.  When Router RT4 floods a new LSA to
        Network N3, it is received by routers RT1, RT2, and RT3.  These
        routers will not flood the LSA back onto net N3, but they still
        must ensure that their link-state databases remain synchronized
        with their adjacent neighbors.  So RT1, RT2, and RT4 are waiting
        to see an acknowledgment from RT3.  Likewise, RT4 and RT3 are
        both waiting to see acknowledgments from RT1 and RT2.  This is
        best achieved by sending the acknowledgments as multicasts.

        The reason that the acknowledgment logic for Backup DRs is
        slightly different is because they perform differently during
        the flooding of LSAs (see Section 13.3, step 4).



    13.6.  Retransmitting LSAs

        LSAs flooded out an adjacency are placed on the adjacency's Link
        state retransmission list.  In order to ensure that flooding is
        reliable, these LSAs are retransmitted until they are
        acknowledged.  The length of time between retransmissions is a
        configurable per-interface value, RxmtInterval.  If this is set
Top   ToC   RFC2328 - Page 155
        too low for an interface, needless retransmissions will ensue.
        If the value is set too high, the speed of the flooding, in the
        face of lost packets, may be affected.

        Several retransmitted LSAs may fit into a single Link State
        Update packet.  When LSAs are to be retransmitted, only the
        number fitting in a single Link State Update packet should be
        sent.  Another packet of retransmissions can be sent whenever
        some of the LSAs are acknowledged, or on the next firing of the
        retransmission timer.

        Link State Update Packets carrying retransmissions are always
        sent directly to the neighbor. On multi-access networks, this
        means that retransmissions are sent directly to the neighbor's
        IP address.  Each LSA's LS age must be incremented by
        InfTransDelay (which must be > 0) when it is copied into the
        outgoing Link State Update packet (until the LS age field
        reaches the maximum value of MaxAge).

        If an adjacent router goes down, retransmissions may occur until
        the adjacency is destroyed by OSPF's Hello Protocol.  When the
        adjacency is destroyed, the Link state retransmission list is
        cleared.


    13.7.  Receiving link state acknowledgments

        Many consistency checks have been made on a received Link State
        Acknowledgment packet before it is handed to the flooding
        procedure.  In particular, it has been associated with a
        particular neighbor.  If this neighbor is in a lesser state than
        Exchange, the Link State Acknowledgment packet is discarded.

        Otherwise, for each acknowledgment in the Link State
        Acknowledgment packet, the following steps are performed:


        o   Does the LSA acknowledged have an instance on the Link state
            retransmission list for the neighbor?  If not, examine the
            next acknowledgment.  Otherwise:
Top   ToC   RFC2328 - Page 156
        o   If the acknowledgment is for the same instance that is
            contained on the list, remove the item from the list and
            examine the next acknowledgment.  Otherwise:

        o   Log the questionable acknowledgment, and examine the next
            one.


14.  Aging The Link State Database

    Each LSA has an LS age field.  The LS age is expressed in seconds.
    An LSA's LS age field is incremented while it is contained in a
    router's database.  Also, when copied into a Link State Update
    Packet for flooding out a particular interface, the LSA's LS age is
    incremented by InfTransDelay.

    An LSA's LS age is never incremented past the value MaxAge.  LSAs
    having age MaxAge are not used in the routing table calculation.  As
    a router ages its link state database, an LSA's LS age may reach
    MaxAge.[21] At this time, the router must attempt to flush the LSA
    from the routing domain.  This is done simply by reflooding the
    MaxAge LSA just as if it was a newly originated LSA (see Section
    13.3).

    When creating a Database summary list for a newly forming adjacency,
    any MaxAge LSAs present in the link state database are added to the
    neighbor's Link state retransmission list instead of the neighbor's
    Database summary list.  See Section 10.3 for more details.

    A MaxAge LSA must be removed immediately from the router's link
    state database as soon as both a) it is no longer contained on any
    neighbor Link state retransmission lists and b) none of the router's
    neighbors are in states Exchange or Loading.

    When, in the process of aging the link state database, an LSA's LS
    age hits a multiple of CheckAge, its LS checksum should be verified.
    If the LS checksum is incorrect, a program or memory error has been
    detected, and at the very least the router itself should be
    restarted.
Top   ToC   RFC2328 - Page 157
    14.1.  Premature aging of LSAs

        An LSA can be flushed from the routing domain by setting its LS
        age to MaxAge, while leaving its LS sequence number alone, and
        then reflooding the LSA.  This procedure follows the same course
        as flushing an LSA whose LS age has naturally reached the value
        MaxAge (see Section 14).  In particular, the MaxAge LSA is
        removed from the router's link state database as soon as a) it
        is no longer contained on any neighbor Link state retransmission
        lists and b) none of the router's neighbors are in states
        Exchange or Loading.  We call the setting of an LSA's LS age to
        MaxAge "premature aging".

        Premature aging is used when it is time for a self-originated
        LSA's sequence number field to wrap.  At this point, the current
        LSA instance (having LS sequence number MaxSequenceNumber) must
        be prematurely aged and flushed from the routing domain before a
        new instance with sequence number equal to InitialSequenceNumber
        can be originated.  See Section 12.1.6 for more information.

        Premature aging can also be used when, for example, one of the
        router's previously advertised external routes is no longer
        reachable.  In this circumstance, the router can flush its AS-
        external-LSA from the routing domain via premature aging. This
        procedure is preferable to the alternative, which is to
        originate a new LSA for the destination specifying a metric of
        LSInfinity.  Premature aging is also be used when unexpectedly
        receiving self-originated LSAs during the flooding procedure
        (see Section 13.4).

        A router may only prematurely age its own self-originated LSAs.
        The router may not prematurely age LSAs that have been
        originated by other routers. An LSA is considered self-
        originated when either 1) the LSA's Advertising Router is equal
        to the router's own Router ID or 2) the LSA is a network-LSA and
        its Link State ID is equal to one of the router's own IP
        interface addresses.
Top   ToC   RFC2328 - Page 158
15.  Virtual Links

    The single backbone area (Area ID = 0.0.0.0) cannot be disconnected,
    or some areas of the Autonomous System will become unreachable.  To
    establish/maintain connectivity of the backbone, virtual links can
    be configured through non-backbone areas.  Virtual links serve to
    connect physically separate components of the backbone.  The two
    endpoints of a virtual link are area border routers.  The virtual
    link must be configured in both routers.  The configuration
    information in each router consists of the other virtual endpoint
    (the other area border router), and the non-backbone area the two
    routers have in common (called the Transit area).  Virtual links
    cannot be configured through stub areas (see Section 3.6).

    The virtual link is treated as if it were an unnumbered point-to-
    point network belonging to the backbone and joining the two area
    border routers.  An attempt is made to establish an adjacency over
    the virtual link.  When this adjacency is established, the virtual
    link will be included in backbone router-LSAs, and OSPF packets
    pertaining to the backbone area will flow over the adjacency.  Such
    an adjacency has been referred to in this document as a "virtual
    adjacency".

    In each endpoint router, the cost and viability of the virtual link
    is discovered by examining the routing table entry for the other
    endpoint router.  (The entry's associated area must be the
    configured Transit area).  This is called the virtual link's
    corresponding routing table entry.  The InterfaceUp event occurs for
    a virtual link when its corresponding routing table entry becomes
    reachable.  Conversely, the InterfaceDown event occurs when its
    routing table entry becomes unreachable.  In other words, the
    virtual link's viability is determined by the existence of an
    intra-area path, through the Transit area, between the two
    endpoints.  Note that a virtual link whose underlying path has cost
    greater than hexadecimal 0xffff (the maximum size of an interface
    cost in a router-LSA) should be considered inoperational (i.e.,
    treated the same as if the path did not exist).

    The other details concerning virtual links are as follows:

    o   AS-external-LSAs are NEVER flooded over virtual adjacencies.
        This would be duplication of effort, since the same AS-
Top   ToC   RFC2328 - Page 159
        external-LSAs are already flooded throughout the virtual link's
        Transit area.  For this same reason, AS-external-LSAs are not
        summarized over virtual adjacencies during the Database Exchange
        process.

    o   The cost of a virtual link is NOT configured.  It is defined to
        be the cost of the intra-area path between the two defining area
        border routers.  This cost appears in the virtual link's
        corresponding routing table entry.  When the cost of a virtual
        link changes, a new router-LSA should be originated for the
        backbone area.

    o   Just as the virtual link's cost and viability are determined by
        the routing table build process (through construction of the
        routing table entry for the other endpoint), so are the IP
        interface address for the virtual interface and the virtual
        neighbor's IP address.  These are used when sending OSPF
        protocol packets over the virtual link. Note that when one (or
        both) of the virtual link endpoints connect to the Transit area
        via an unnumbered point-to-point link, it may be impossible to
        calculate either the virtual interface's IP address and/or the
        virtual neighbor's IP address, thereby causing the virtual link
        to fail.

    o   In each endpoint's router-LSA for the backbone, the virtual link
        is represented as a Type 4 link whose Link ID is set to the
        virtual neighbor's OSPF Router ID and whose Link Data is set to
        the virtual interface's IP address.  See Section 12.4.1 for more
        information.

    o   A non-backbone area can carry transit data traffic (i.e., is
        considered a "transit area") if and only if it serves as the
        Transit area for one or more fully adjacent virtual links (see
        TransitCapability in Sections 6 and 16.1). Such an area requires
        special treatment when summarizing backbone networks into it
        (see Section 12.4.3), and during the routing calculation (see
        Section 16.3).

    o   The time between link state retransmissions, RxmtInterval, is
        configured for a virtual link.  This should be well over the
        expected round-trip delay between the two routers.  This may be
Top   ToC   RFC2328 - Page 160
        hard to estimate for a virtual link; it is better to err on the
        side of making it too large.


16.  Calculation of the routing table

    This section details the OSPF routing table calculation.  Using its
    attached areas' link state databases as input, a router runs the
    following algorithm, building its routing table step by step.  At
    each step, the router must access individual pieces of the link
    state databases (e.g., a router-LSA originated by a certain router).
    This access is performed by the lookup function discussed in Section
    12.2.  The lookup process may return an LSA whose LS age is equal to
    MaxAge.  Such an LSA should not be used in the routing table
    calculation, and is treated just as if the lookup process had
    failed.

    The OSPF routing table's organization is explained in Section 11.
    Two examples of the routing table build process are presented in
    Sections 11.2 and 11.3.  This process can be broken into the
    following steps:

    (1) The present routing table is invalidated.  The routing table is
        built again from scratch.  The old routing table is saved so
        that changes in routing table entries can be identified.

    (2) The intra-area routes are calculated by building the shortest-
        path tree for each attached area.  In particular, all routing
        table entries whose Destination Type is "area border router" are
        calculated in this step.  This step is described in two parts.
        At first the tree is constructed by only considering those links
        between routers and transit networks.  Then the stub networks
        are incorporated into the tree. During the area's shortest-path
        tree calculation, the area's TransitCapability is also
        calculated for later use in Step 4.

    (3) The inter-area routes are calculated, through examination of
        summary-LSAs.  If the router is attached to multiple areas
        (i.e., it is an area border router), only backbone summary-LSAs
        are examined.
Top   ToC   RFC2328 - Page 161
    (4) In area border routers connecting to one or more transit areas
        (i.e, non-backbone areas whose TransitCapability is found to be
        TRUE), the transit areas' summary-LSAs are examined to see
        whether better paths exist using the transit areas than were
        found in Steps 2-3 above.

    (5) Routes to external destinations are calculated, through
        examination of AS-external-LSAs.  The locations of the AS
        boundary routers (which originate the AS-external-LSAs) have
        been determined in steps 2-4.


    Steps 2-5 are explained in further detail below.

    Changes made to routing table entries as a result of these
    calculations can cause the OSPF protocol to take further actions.
    For example, a change to an intra-area route will cause an area
    border router to originate new summary-LSAs (see Section 12.4).  See
    Section 16.7 for a complete list of the OSPF protocol actions
    resulting from routing table changes.


    16.1.  Calculating the shortest-path tree for an area

        This calculation yields the set of intra-area routes associated
        with an area (called hereafter Area A).  A router calculates the
        shortest-path tree using itself as the root.[22] The formation
        of the shortest path tree is done here in two stages.  In the
        first stage, only links between routers and transit networks are
        considered.  Using the Dijkstra algorithm, a tree is formed from
        this subset of the link state database.  In the second stage,
        leaves are added to the tree by considering the links to stub
        networks.

        The procedure will be explained using the graph terminology that
        was introduced in Section 2.  The area's link state database is
        represented as a directed graph.  The graph's vertices are
        routers, transit networks and stub networks.  The first stage of
        the procedure concerns only the transit vertices (routers and
        transit networks) and their connecting links.  Throughout the
        shortest path calculation, the following data is also associated
        with each transit vertex:
Top   ToC   RFC2328 - Page 162
        Vertex (node) ID
            A 32-bit number which together with the vertex type (router
            or network) uniquely identifies the vertex.  For router
            vertices the Vertex ID is the router's OSPF Router ID.  For
            network vertices, it is the IP address of the network's
            Designated Router.

        An LSA
            Each transit vertex has an associated LSA.  For router
            vertices, this is a router-LSA.  For transit networks, this
            is a network-LSA (which is actually originated by the
            network's Designated Router).  In any case, the LSA's Link
            State ID is always equal to the above Vertex ID.

        List of next hops
            The list of next hops for the current set of shortest paths
            from the root to this vertex.  There can be multiple
            shortest paths due to the equal-cost multipath capability.
            Each next hop indicates the outgoing router interface to use
            when forwarding traffic to the destination.  On broadcast,
            Point-to-MultiPoint and NBMA networks, the next hop also
            includes the IP address of the next router (if any) in the
            path towards the destination.

        Distance from root
            The link state cost of the current set of shortest paths
            from the root to the vertex.  The link state cost of a path
            is calculated as the sum of the costs of the path's
            constituent links (as advertised in router-LSAs and
            network-LSAs).  One path is said to be "shorter" than
            another if it has a smaller link state cost.


        The first stage of the procedure (i.e., the Dijkstra algorithm)
        can now be summarized as follows. At each iteration of the
        algorithm, there is a list of candidate vertices.  Paths from
        the root to these vertices have been found, but not necessarily
        the shortest ones.  However, the paths to the candidate vertex
        that is closest to the root are guaranteed to be shortest; this
        vertex is added to the shortest-path tree, removed from the
        candidate list, and its adjacent vertices are examined for
        possible addition to/modification of the candidate list.  The
Top   ToC   RFC2328 - Page 163
        algorithm then iterates again.  It terminates when the candidate
        list becomes empty.

        The following steps describe the algorithm in detail.  Remember
        that we are computing the shortest path tree for Area A.  All
        references to link state database lookup below are from Area A's
        database.

        (1) Initialize the algorithm's data structures.  Clear the list
            of candidate vertices.  Initialize the shortest-path tree to
            only the root (which is the router doing the calculation).
            Set Area A's TransitCapability to FALSE.

        (2) Call the vertex just added to the tree vertex V.  Examine
            the LSA associated with vertex V.  This is a lookup in the
            Area A's link state database based on the Vertex ID.  If
            this is a router-LSA, and bit V of the router-LSA (see
            Section A.4.2) is set, set Area A's TransitCapability to
            TRUE.  In any case, each link described by the LSA gives the
            cost to an adjacent vertex.  For each described link, (say
            it joins vertex V to vertex W):

            (a) If this is a link to a stub network, examine the next
                link in V's LSA.  Links to stub networks will be
                considered in the second stage of the shortest path
                calculation.

            (b) Otherwise, W is a transit vertex (router or transit
                network).  Look up the vertex W's LSA (router-LSA or
                network-LSA) in Area A's link state database.  If the
                LSA does not exist, or its LS age is equal to MaxAge, or
                it does not have a link back to vertex V, examine the
                next link in V's LSA.[23]

            (c) If vertex W is already on the shortest-path tree,
                examine the next link in the LSA.

            (d) Calculate the link state cost D of the resulting path
                from the root to vertex W.  D is equal to the sum of the
                link state cost of the (already calculated) shortest
                path to vertex V and the advertised cost of the link
                between vertices V and W.  If D is:
Top   ToC   RFC2328 - Page 164
                o   Greater than the value that already appears for
                    vertex W on the candidate list, then examine the
                    next link.

                o   Equal to the value that appears for vertex W on the
                    candidate list, calculate the set of next hops that
                    result from using the advertised link.  Input to
                    this calculation is the destination (W), and its
                    parent (V).  This calculation is shown in Section
                    16.1.1.  This set of hops should be added to the
                    next hop values that appear for W on the candidate
                    list.

                o   Less than the value that appears for vertex W on the
                    candidate list, or if W does not yet appear on the
                    candidate list, then set the entry for W on the
                    candidate list to indicate a distance of D from the
                    root.  Also calculate the list of next hops that
                    result from using the advertised link, setting the
                    next hop values for W accordingly.  The next hop
                    calculation is described in Section 16.1.1; it takes
                    as input the destination (W) and its parent (V).

        (3) If at this step the candidate list is empty, the shortest-
            path tree (of transit vertices) has been completely built
            and this stage of the procedure terminates.  Otherwise,
            choose the vertex belonging to the candidate list that is
            closest to the root, and add it to the shortest-path tree
            (removing it from the candidate list in the process). Note
            that when there is a choice of vertices closest to the root,
            network vertices must be chosen before router vertices in
            order to necessarily find all equal-cost paths. This is
            consistent with the tie-breakers that were introduced in the
            modified Dijkstra algorithm used by OSPF's Multicast routing
            extensions (MOSPF).

        (4) Possibly modify the routing table.  For those routing table
            entries modified, the associated area will be set to Area A,
            the path type will be set to intra-area, and the cost will
            be set to the newly discovered shortest path's calculated
            distance.
Top   ToC   RFC2328 - Page 165
            If the newly added vertex is an area border router or AS
            boundary router, a routing table entry is added whose
            destination type is "router".  The Options field found in
            the associated router-LSA is copied into the routing table
            entry's Optional capabilities field. Call the newly added
            vertex Router X.  If Router X is the endpoint of one of the
            calculating router's virtual links, and the virtual link
            uses Area A as Transit area:  the virtual link is declared
            up, the IP address of the virtual interface is set to the IP
            address of the outgoing interface calculated above for
            Router X, and the virtual neighbor's IP address is set to
            Router X's interface address (contained in Router X's
            router-LSA) that points back to the root of the shortest-
            path tree; equivalently, this is the interface that points
            back to Router X's parent vertex on the shortest-path tree
            (similar to the calculation in Section 16.1.1).

            If the newly added vertex is a transit network, the routing
            table entry for the network is located.  The entry's
            Destination ID is the IP network number, which can be
            obtained by masking the Vertex ID (Link State ID) with its
            associated subnet mask (found in the body of the associated
            network-LSA).  If the routing table entry already exists
            (i.e., there is already an intra-area route to the
            destination installed in the routing table), multiple
            vertices have mapped to the same IP network.  For example,
            this can occur when a new Designated Router is being
            established.  In this case, the current routing table entry
            should be overwritten if and only if the newly found path is
            just as short and the current routing table entry's Link
            State Origin has a smaller Link State ID than the newly
            added vertex' LSA.

            If there is no routing table entry for the network (the
            usual case), a routing table entry for the IP network should
            be added.  The routing table entry's Link State Origin
            should be set to the newly added vertex' LSA.

        (5) Iterate the algorithm by returning to Step 2.
Top   ToC   RFC2328 - Page 166
        The stub networks are added to the tree in the procedure's
        second stage.  In this stage, all router vertices are again
        examined.  Those that have been determined to be unreachable in
        the above first phase are discarded.  For each reachable router
        vertex (call it V), the associated router-LSA is found in the
        link state database.  Each stub network link appearing in the
        LSA is then examined, and the following steps are executed:

        (1) Calculate the distance D of stub network from the root.  D
            is equal to the distance from the root to the router vertex
            (calculated in stage 1), plus the stub network link's
            advertised cost.  Compare this distance to the current best
            cost to the stub network.  This is done by looking up the
            stub network's current routing table entry.  If the
            calculated distance D is larger, go on to examine the next
            stub network link in the LSA.

        (2) If this step is reached, the stub network's routing table
            entry must be updated.  Calculate the set of next hops that
            would result from using the stub network link.  This
            calculation is shown in Section 16.1.1; input to this
            calculation is the destination (the stub network) and the
            parent vertex (the router vertex).  If the distance D is the
            same as the current routing table cost, simply add this set
            of next hops to the routing table entry's list of next hops.
            In this case, the routing table already has a Link State
            Origin.  If this Link State Origin is a router-LSA whose
            Link State ID is smaller than V's Router ID, reset the Link
            State Origin to V's router-LSA.

            Otherwise D is smaller than the routing table cost.
            Overwrite the current routing table entry by setting the
            routing table entry's cost to D, and by setting the entry's
            list of next hops to the newly calculated set.  Set the
            routing table entry's Link State Origin to V's router-LSA.
            Then go on to examine the next stub network link.


        For all routing table entries added/modified in the second
        stage, the associated area will be set to Area A and the path
        type will be set to intra-area.  When the list of reachable
        router-LSAs is exhausted, the second stage is completed.  At
Top   ToC   RFC2328 - Page 167
        this time, all intra-area routes associated with Area A have
        been determined.

        The specification does not require that the above two stage
        method be used to calculate the shortest path tree.  However, if
        another algorithm is used, an identical tree must be produced.
        For this reason, it is important to note that links between
        transit vertices must be bidirectional in order to be included
        in the above tree.  It should also be mentioned that more
        efficient algorithms exist for calculating the tree; for
        example, the incremental SPF algorithm described in [Ref1].


        16.1.1.  The next hop calculation

            This section explains how to calculate the current set of
            next hops to use for a destination.  Each next hop consists
            of the outgoing interface to use in forwarding packets to
            the destination together with the IP address of the next hop
            router (if any).  The next hop calculation is invoked each
            time a shorter path to the destination is discovered.  This
            can happen in either stage of the shortest-path tree
            calculation (see Section 16.1).  In stage 1 of the
            shortest-path tree calculation a shorter path is found as
            the destination is added to the candidate list, or when the
            destination's entry on the candidate list is modified (Step
            2d of Stage 1).  In stage 2 a shorter path is discovered
            each time the destination's routing table entry is modified
            (Step 2 of Stage 2).

            The set of next hops to use for the destination may be
            recalculated several times during the shortest-path tree
            calculation, as shorter and shorter paths are discovered.
            In the end, the destination's routing table entry will
            always reflect the next hops resulting from the absolute
            shortest path(s).

            Input to the next hop calculation is a) the destination and
            b) its parent in the current shortest path between the root
            (the calculating router) and the destination.  The parent is
            always a transit vertex (i.e., always a router or a transit
            network).
Top   ToC   RFC2328 - Page 168
            If there is at least one intervening router in the current
            shortest path between the destination and the root, the
            destination simply inherits the set of next hops from the
            parent.  Otherwise, there are two cases.  In the first case,
            the parent vertex is the root (the calculating router
            itself).  This means that the destination is either a
            directly connected network or directly connected router.
            The outgoing interface in this case is simply the OSPF
            interface connecting to the destination network/router. If
            the destination is a router which connects to the
            calculating router via a Point-to-MultiPoint network, the
            destination's next hop IP address(es) can be determined by
            examining the destination's router-LSA: each link pointing
            back to the calculating router and having a Link Data field
            belonging to the Point-to-MultiPoint network provides an IP
            address of the next hop router. If the destination is a
            directly connected network, or a router which connects to
            the calculating router via a point-to-point interface, no
            next hop IP address is required. If the destination is a
            router connected to the calculating router via a virtual
            link, the setting of the next hop should be deferred until
            the calculation in Section 16.3.

            In the second case, the parent vertex is a network that
            directly connects the calculating router to the destination
            router.  The list of next hops is then determined by
            examining the destination's router-LSA.  For each link in
            the router-LSA that points back to the parent network, the
            link's Link Data field provides the IP address of a next hop
            router.  The outgoing interface to use can then be derived
            from the next hop IP address (or it can be inherited from
            the parent network).




(page 168 continued on part 7)

Next Section