tech-invite   World Map     

3GPP     Specs     Glossaries     Architecture     IMS     UICC       IETF     RFCs     Groups     SIP     ABNFs       Search

RFC 1583

 
 
 

OSPF Version 2

Part 6 of 9, p. 126 to 151
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 126 
13.  The Flooding Procedure

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

Top      Up      ToC       Page 127 
                                +
                                |
                      +---+.....|.EGP
                      |RTA|-----|.....+---+
                      +---+     |-----|RTX|
                                |     +---+
                      +---+     |
                      |RTB|-----|
                      +---+     |
                                |
                      +---+     |
                      |RTC|-----|
                      +---+     |
                                |
                                +


               Figure 16: Forwarding address example

    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 link state advertisements, other than AS external link
    advertisements, are associated with a specific area.  However, link
    state advertisements do not contain an area field.  A link state
    advertisement's area must be deduced from the Link State Update
    packet header.

    For each link state advertisement contained in the packet, the
    following steps are taken:


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

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

Top      Up      ToC       Page 128 
    (3) Else if this is a AS external link advertisement (LS type = 5),
        and the area has been configured as a stub area, discard the
        advertisement and get the next one from the Link State Update
        Packet.  AS external link advertisements are not flooded
        into/throughout stub areas (see Section 3.6).

    (4) Else if the advertisement's LS age is equal to MaxAge, and there
        is currently no instance of the advertisement in the router's
        link state database, then take the following actions:

        (a) Acknowledge the receipt of the advertisement by sending a
            Link State Acknowledgment packet back to the sending
            neighbor (see Section 13.5).

        (b) Purge all outstanding requests for equal or previous
            instances of the advertisement from the sending neighbor's
            Link State Request list (see Section 10).

        (c) If the sending neighbor is in state Exchange or in state
            Loading, then install the MaxAge advertisement in the link
            state database.  Otherwise, simply discard the
            advertisement.  In either case, examine the next
            advertisement (if any) listed in the Link State Update
            packet.

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

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

        (b) Otherwise immediately flood the new advertisement 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 advertisement was received from a router other than
            the Backup DR) the advertisement 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.

Top      Up      ToC       Page 129 
        (d) Install the new advertisement 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 advertisement with the current time (i.e.,
            the time it was received).  The flooding procedure cannot
            overwrite the newly installed advertisement until
            MinLSInterval seconds have elapsed.  The advertisement
            installation process is discussed further in Section 13.2.

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

        (f) If this new link state advertisement indicates that it was
            originated by the receiving router itself (i.e., is
            considered a self-originated advertisement), the router must
            take special action, either updating the advertisement or in
            some cases flushing it from the routing domain. For a
            description of how self-originated advertisements are
            detected and subsequently handled, see Section 13.4.

    (6) Else, if there is an instance of the advertisement 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 advertisement 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 advertisement is listed in the Link state
            retransmission list for the receiving adjacency, the router
            itself is expecting an acknowledgment for this
            advertisement.  The router should treat the received
            advertisement as an acknowledgment, by removing the
            advertisement 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 advertisement by
            sending a Link State Acknowledgment packet back out the
            receiving interface.  This is explained below in Section
            13.5.

Top      Up      ToC       Page 130 
    (8) Else, the database copy is more recent.  Note an unusual event
        to network management, discard the advertisement and process the
        next link state advertisement contained in the Link State Update
        packet.


    13.1.  Determining which link state is newer

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

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


        o   The advertisement 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.


    13.2.  Installing link state advertisements in the database

        Installing a new link state advertisement in the database,
        either as the result of flooding or a newly self-originated
        advertisement, may cause the OSPF routing table structure to be
        recalculated.  The contents of the new advertisement should be
        compared to the old instance, if present.  If there is no

Top      Up      ToC       Page 131 
        difference, there is no need to recalculate the routing table.
        (Note that even if the contents are the same, the LS checksum
        will probably be different, since the checksum covers the LS
        sequence number.)

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


        Router links and network links advertisements
            The entire routing table must be recalculated, starting with
            the shortest path calculations for each area (not just the
            area whose topological 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.[16]

        Summary link advertisements
            The best route to the destination described by the summary
            link advertisement 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 link
            advertisements.

        AS external link advertisements
            The best route to the destination described by the AS
            external link advertisement must be recalculated (see
            Section 16.6).


        Also, any old instance of the advertisement must be removed from
        the database when the new advertisement 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) advertisement 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
        advertisement to the appropriate neighbors' Link state

Top      Up      ToC       Page 132 
        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
        advertisement that the router itself has just originated (see
        Section 12.4).  For these advertisements, this section provides
        the entirety of the flooding procedure (i.e., the processing of
        Section 13 is not performed, since, for example, the
        advertisement has not been received from a neighbor and
        therefore does not need to be acknowledged).

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


        AS external link advertisements (LS Type = 5)
            AS external link advertisements 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
            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 a link state advertisement out a particular
        interface, if there is a high probability that the attached
        neighbors have already received the advertisement.  However, in
        these cases the flooding procedure must be absolutely sure that
        the neighbors eventually do receive the advertisement, so the
        advertisement 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
            advertisement.  The following steps are executed for each
            neighbor:

Top      Up      ToC       Page 133 
            (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 advertisement on the list, it
                indicates that the neighboring router has an instance of
                the advertisement already.  Compare the new
                advertisement to the neighbor's copy:

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

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

                o   Else, the new advertisement is more recent.  Delete
                    the advertisement from the Link state request list.

            (c) If the new advertisement 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 advertisement.  Add
                the new advertisement to the Link state retransmission
                list for the adjacency.  This ensures that the flooding
                procedure is reliable; the advertisement will be
                retransmitted at intervals until an acknowledgment is
                seen from the neighbor.

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

        (3) If the new advertisement 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 advertisement already.  Therefore, examine
            the next interface.

        (4) If the new advertisement was received on this interface, and
            the interface state is Backup (i.e., the router itself is

Top      Up      ToC       Page 134 
            the Backup Designated Router), examine the next interface.
            The Designated Router will do the flooding on this
            interface.  If the Designated Router fails, this router will
            end up retransmitting the updates.

        (5) If this step is reached, the advertisement must be flooded
            out the interface.  Send a Link State Update packet (with
            the new advertisement as contents) out the interface.  The
            advertisement's LS age must be incremented by InfTransDelay
            (which must be > 0) when copied into the outgoing Link State
            Update packet (until the LS age field reaches its 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
            address AllSPFRouters should be used.  Otherwise, the
            address AllDRouters should be used.

            On non-broadcast, multi-access 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 link state

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

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

        It may be the case the router no longer wishes to originate the

Top      Up      ToC       Page 135 
        received advertisement. Possible examples include: 1) the
        advertisement is a summary link or AS external link and the
        router no longer has an (advertisable) route to the destination,
        2) the advertisement is a network links advertisement but the
        router is no longer Designated Router for the network or 3) the
        advertisement is a network links advertisement 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
        advertisement).  In all these cases, instead of updating the
        advertisement, the advertisement should be flushed from the
        routing domain by incrementing the received advertisement's LS
        age to MaxAge and reflooding (see Section 14.1).


    13.5.  Sending Link State Acknowledgment packets

        Each newly received link state advertisement 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 that has received the advertisements.  The packet can
        be sent in one of two ways: delayed and sent on an interval
        timer, or sent directly (as a unicast) to a particular neighbor.
        The particular acknowledgment strategy used depends on the
        circumstances surrounding the receipt of the advertisement.

        Sending delayed acknowledgments accomplishes several things: it
        facilitates the packaging of multiple acknowledgments in a
        single Link State Acknowledgment packet; it enables a single
        Link State Acknowledgment packet to indicate acknowledgments to
        several neighbors at once (through multicasting); and it
        randomizes the Link State Acknowledgment packets sent by the
        various routers attached to a multi-access 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 to a particular neighbor in
        response to the receipt of duplicate link state advertisements.
        These acknowledgments are sent as unicasts, and are sent
        immediately when the duplicate is received.

        The precise procedure for sending Link State Acknowledgment

Top      Up      ToC       Page 136 
        packets is described in Table 19.  The circumstances surrounding
        the receipt of the advertisement 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
        on the state of the interface.  If the state is DR or Backup,
        the destination AllSPFRouters is used.  In 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
        advertisement to Network N3, it is received by routers RT1, RT2,
        and RT3.  These routers will not flood the advertisement back
        onto net N3, but they still must ensure that their topological
        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 link state advertisements (see Section 13.3,
        step 4).



    13.6.  Retransmitting link state advertisements

        Advertisements flooded out an adjacency are placed on the
        adjacency's Link state retransmission list.  In order to ensure
        that flooding is reliable, these advertisements are
        retransmitted until they are acknowledged.  The length of time
        between retransmissions is a configurable per-interface value,
        RxmtInterval.  If this is set 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

Top      Up      ToC       Page 137 
                                    Action taken in state
    Circumstances          Backup                All other states
    _______________________________________________________________
    Advertisement  has     No  acknowledgment    No  acknowledgment
    been  flooded back     sent.                 sent.
    out receiving  in-
    terface  (see Sec-
    tion 13, step 5b).
    _______________________________________________________________
    Advertisement   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
    _______________________________________________________________
    Advertisement 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
    _______________________________________________________________
    Advertisement is a     Direct acknowledg-    Direct acknowledg-
    duplicate, and was     ment sent.            ment sent.
    not treated as  an
    implied       ack-
    nowledgment.
    _______________________________________________________________
    Advertisement's LS     Direct acknowledg-    Direct acknowledg-
    age is equal to        ment sent.            ment sent.
    MaxAge, and there is
    no current instance
    of the advertisement
    in the link state
    database (see
    Section 13, step 4).


             Table 19: Sending link state acknowledgements.

Top      Up      ToC       Page 138 
        affected.

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

        Link State Update Packets carrying retransmissions are always
        sent as unicasts (directly to the physical address of the
        neighbor).  They are never sent as multicasts.  Each
        advertisement's LS age must be incremented by InfTransDelay
        (which must be > 0) when copied into the outgoing Link State
        Update packet (until the LS age field reaches its maximum value
        of MaxAge).

        If the 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 advertisement acknowledged have an instance on the
            Link state retransmission list for the neighbor?  If not,
            examine the next acknowledgment.  Otherwise:

        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.

Top      Up      ToC       Page 139 
14.  Aging The Link State Database

    Each link state advertisement has an LS age field.  The LS age is
    expressed in seconds.  An advertisement'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 advertisement's LS age is incremented by
    InfTransDelay.

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

    When creating a Database summary list for a newly forming adjacency,
    any MaxAge advertisements 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 advertisement 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
    advertisement'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.


    14.1.  Premature aging of advertisements

        A link state advertisement can be flushed from the routing
        domain by setting its LS age to MaxAge and reflooding the
        advertisement.  This procedure follows the same course as
        flushing an advertisement whose LS age has naturally reached the
        value MaxAge (see Section 14).  In particular, the MaxAge
        advertisement 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
        advertisement's LS age to MaxAge premature aging.

Top      Up      ToC       Page 140 
        Premature aging is used when it is time for a self-originated
        advertisement's sequence number field to wrap.  At this point,
        the current advertisement instance (having LS sequence number of
        0x7fffffff) must be prematurely aged and flushed from the
        routing domain before a new instance with sequence number
        0x80000001 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
        external advertisement from the routing domain via premature
        aging. This procedure is preferable to the alternative, which is
        to originate a new advertisement for the destination specifying
        a metric of LSInfinity.  Premature aging is also be used when
        unexpectedly receiving self-originated advertisements during the
        flooding procedure (see Section 13.4).

        A router may only prematurely age its own self-originated link
        state advertisements. The router may not prematurely age
        advertisements that have been originated by other routers. An
        advertisement is considered self-originated when either 1) the
        advertisement's Advertising Router is equal to the router's own
        Router ID or 2) the advertisement is a network links
        advertisement and its Link State ID is equal to one of the
        router's own IP interface addresses.


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) 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 links advertisements, and
    OSPF packets pertaining to the backbone area will flow over the

Top      Up      ToC       Page 141 
    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).  Actually, there may be a separate routing
    table entry for each Type of Service.  These are called the virtual
    link's corresponding routing table entries.  The InterfaceUp event
    occurs for a virtual link when its corresponding TOS 0 routing table
    entry becomes reachable.  Conversely, the InterfaceDown event occurs
    when its TOS 0 routing table entry becomes unreachable.[19] 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 links advertisement) 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 links are NEVER flooded over virtual adjacencies.
        This would be duplication of effort, since the same AS external
        links are already flooded throughout the virtual link's transit
        area.  For this same reason, AS external link advertisements 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 links advertisement 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.

Top      Up      ToC       Page 142 
    o   In each endpoint's router links advertisement 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. Note that it may be the case that
        there is a TOS 0 path, but no non-zero TOS paths, between the
        two endpoint routers.  In this case, both routers must revert to
        being non-TOS-capable, clearing the T-bit in the Options field
        of their backbone router links advertisements.

    o   When virtual links are configured for the backbone, information
        concerning backbone networks should not be condensed before
        being summarized for the transit areas.  In other words, each
        backbone network should be advertised into the transit areas in
        a separate summary link advertisement, regardless of the
        backbone's configured area address ranges.  See Section 12.4.3
        for more information.

    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
        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 links advertisement originated by a
    certain router).  This access is performed by the lookup function
    discussed in Section 12.2.  The lookup process may return a link
    state advertisement whose LS age is equal to MaxAge.  Such an
    advertisement 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.

Top      Up      ToC       Page 143 
    (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 link advertisements.  If the router is attached to
        multiple areas (i.e., it is an area border router), only
        backbone summary link advertisements are examined.

    (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 link advertisements 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 link advertisements.  The locations
        of the AS boundary routers (which originate the AS external link
        advertisements) have been determined in steps 2-4.


    Steps 2-5 are explained in further detail below.  The explanations
    describe the calculations for TOS 0 only.  It may also be necessary
    to perform each step (separately) for each of the non-zero TOS
    values.[20] For more information concerning the building of non-zero
    TOS routes see Section 16.9.

    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 link advertisements (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.[21] 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

Top      Up      ToC       Page 144 
        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:


        Vertex (node) ID
            A 32-bit number uniquely identifying the vertex.  For router
            vertices this is the router's OSPF Router ID.  For network
            vertices, this is the IP address of the network's Designated
            Router.

        A link state advertisement
            Each transit vertex has an associated link state
            advertisement.  For router vertices, this is a router links
            advertisement.  For transit networks, this is a network
            links advertisement (which is actually originated by the
            network's Designated Router).  In any case, the
            advertisement'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 multi-access
            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 links and network
            links advertisements).  One path is said to be "shorter"
            than another if it has a smaller link state cost.

Top      Up      ToC       Page 145 
        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
        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 link state advertisement 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 links advertisement, and bit
            V of the router links advertisement (see Section A.4.2) is
            set, set Area A's TransitCapability to TRUE.  In any case,
            each link described by the advertisement 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 advertisement.  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 link state
                advertisement (router links or network links) in Area
                A's link state database.  If the advertisement 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 advertisement.[22]

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

Top      Up      ToC       Page 146 
            (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:

                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      Up      ToC       Page 147 
            If the newly added vertex is an area border router (call it
            ABR), a routing table entry is added whose destination type
            is "area border router". The Options field found in the
            associated router links advertisement is copied into the
            routing table entry's Optional capabilities field. If in
            addition ABR is the endpoint of one of the calculating
            router's configured virtual links that uses Area A as its
            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 ABR, and the
            virtual neighbor's IP address is set to the ABR interface
            address (contained in ABR's router links advertisement) that
            points back to the root of the shortest-path tree;
            equivalently, this is the interface that points back to
            ABR's parent vertex on the shortest-path tree (similar to
            the calculation in Section 16.1.1).

            If the newly added vertex is an AS boundary router, the
            routing table entry of type "AS boundary router" for the
            destination is located.  Since routers can belong to more
            than one area, it is possible that several sets of intra-
            area paths exist to the AS boundary router, each set using a
            different area.  However, the AS boundary router's routing
            table entry must indicate a set of paths which utilize a
            single area.  The area leading to the routing table entry is
            selected as follows: The area providing the shortest path is
            always chosen; if more than one area provides paths with the
            same minimum cost, the area with the largest OSPF Area ID
            (when considered as an unsigned 32-bit integer) is chosen.
            Note that whenever an AS boundary router's routing table
            entry is added/modified, the Options found in the associated
            router links advertisement is copied into the routing table
            entry's Optional capabilities field.

            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 links advertisement).  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

Top      Up      ToC       Page 148 
            added vertex' link state advertisement.

            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' link state
            advertisement.

        (5) Iterate the algorithm by returning to Step 2.


        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 links advertisement is
        found in the link state database.  Each stub network link
        appearing in the advertisement 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 advertisement.

        (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 links
            advertisement whose Link State ID is smaller than V's Router
            ID, reset the Link State Origin to V's router links
            advertisement.

            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

Top      Up      ToC       Page 149 
            routing table entry's Link State Origin to V's router links
            advertisement.  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 links is exhausted, the second stage is completed.  At
        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 ordered 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 [BBN].


        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 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

Top      Up      ToC       Page 150 
            always a transit vertex (i.e., always a router or a transit
            network).

            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 next hop in this case is simply the OSPF interface
            connecting to the network/router; no next hop router is
            required. If the connecting OSPF interface in this case is 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 links advertisement.  For
            each link in the advertisement 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).


    16.2.  Calculating the inter-area routes

        The inter-area routes are calculated by examining summary link
        advertisements.  If the router has active attachments to
        multiple areas, only backbone summary link advertisements are
        examined.  Routers attached to a single area examine that area's
        summary links.  In either case, the summary links examined below
        are all part of a single area's link state database (call it
        Area A).

        Summary link advertisements are originated by the area border
        routers.  Each summary link advertisement in Area A is
        considered in turn.  Remember that the destination described by
        a summary link advertisement is either a network (Type 3 summary
        link advertisements) or an AS boundary router (Type 4 summary
        link advertisements).  For each summary link advertisement:


        (1) If the cost specified by the advertisement is LSInfinity, or
            if the advertisement's LS age is equal to MaxAge, then
            examine the the next advertisement.

Top      Up      ToC       Page 151 
        (2) If the advertisement was originated by the calculating
            router itself, examine the next advertisement.

        (3) If the collection of destinations described by the summary
            link advertisement falls into one of the router's configured
            area address ranges (see Section 3.5) and the particular
            area address range is active, the summary link advertisement
            should be ignored.  Active means that there are one or more
            reachable (by intra-area paths) networks contained in the
            area range.  In this case, all addresses in the area range
            are assumed to be either reachable via intra-area paths, or
            else to be unreachable by any other means.

        (4) Else, call the destination described by the advertisement N
            (for Type 3 summary links, N's address is obtained by
            masking the advertisement's Link State ID with the
            network/subnet mask contained in the body of the
            advertisement), and the area border originating the
            advertisement BR.  Look up the routing table entry for BR
            having Area A as its associated area.  If no such entry
            exists for router BR (i.e., BR is unreachable in Area A), do
            nothing with this advertisement and consider the next in the
            list.  Else, this advertisement describes an inter-area path
            to destination N, whose cost is the distance to BR plus the
            cost specified in the advertisement. Call the cost of this
            inter-area path IAC.

        (5) Next, look up the routing table entry for the destination N.
            (The entry's Destination Type is either Network or AS
            boundary router.)  If no entry exists for N or if the
            entry's path type is "type 1 external" or "type 2 external",
            then install the inter-area path to N, with associated area
            Area A, cost IAC, next hop equal to the list of next hops to
            router BR, and Advertising router equal to BR.

        (6) Else, if the paths present in the table are intra-area
            paths, do nothing with the advertisement (intra-area paths
            are always preferred).

        (7) Else, the paths present in the routing table are also
            inter-area paths.  Install the new path through BR if it is
            cheaper, overriding the paths in the routing table.
            Otherwise, if the new path is the same cost, add it to the
            list of paths that appear in the routing table entry.


Next RFC Part