Tech-invite3GPPspaceIETFspace
96959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 1247

OSPF Version 2

Pages: 189
Obsoletes:  1131
Obsoleted by:  1583
Updated by:  1349
Part 5 of 7 – Pages 103 to 134
First   Prev   Next

ToP   noToC   RFC1247 - Page 103   prevText
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 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 link state advertisements, other than AS external links,
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 link state 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).

(3) Else if this is a AS external 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
    advertisements are not flooded into/throughout stub areas (see
    Section 3.6).

(4) Else if the advertisement's 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:
ToP   noToC   RFC1247 - Page 104
    (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.

    (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
ToP   noToC   RFC1247 - Page 105
        interface.  This is explained below in Section 13.5.

    (f) If this new link state advertisement indicates that it was
        originated by this router itself, the router must advance the
        advertisement's link state sequence number, and issue a new
        instance of the advertisement (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 Description process.  In this case, restart the Database
    Description 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.

(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 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 the 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:
ToP   noToC   RFC1247 - Page 106
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 is of age MaxAge, the instance of
    age MaxAge is considered to be more recent.

o   Else, if the ages of the two instances differ by more than
    MaxAgeDiff, the instance having the smaller (younger) 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 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 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 LS type field:


Router links, network links
    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.[15]

Summary link
    The best route to the destination described by the summary link
    advertisement must be re-examined (see Section 16.5).  If this
    destination is an AS boundary router, it may also be necessary to
ToP   noToC   RFC1247 - Page 107
    re-examine all the AS external link advertisements.

AS external link
    The best route to the destination described by the AS external link
    advertisement must be re-examined (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 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 links (LS Type = 5)
    AS external links 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 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.
ToP   noToC   RFC1247 - Page 108
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:

    (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 try the next
            neighbor.

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

        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, try
        the next neighbor.

    (d) At this point we are not positive that the new 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.
ToP   noToC   RFC1247 - Page 109
(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
    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 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 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 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 to receive a self-originated link state
advertisement via the flooding procedure.  If the advertisement received
is a newer instance 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 this case, the router must
advance the sequence number for the advertisement one past the received
sequence number, and originate a new instance of the advertisement.
ToP   noToC   RFC1247 - Page 110
Note also that if the type of the advertisement is Summary link or AS
external link, the router may no longer have an (advertisable) route to
the destination.  In this case, the advertisement should be flushed from
the routing domain by incrementing the 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
packet; it enables a single packet to indicate acknowledgments to
several neighbors at once (through multicasting); and it randomizes the
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 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.


                                     Action taken in state
     Circumstances          Backup               All other states
     ______________________________________________________________
ToP   noToC   RFC1247 - Page 111
                                     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       ack-   Delayed       ack-
more  recent  than     nowledgment   sent   nowledgment sent.
database copy, but     if   advertisement
was   not  flooded     received  from DR,
back out receiving     otherwise do noth-
interface              ing
______________________________________________________________
Advertisement is a     Delayed       ack-   No  acknowledgment
duplicate, and was     nowledgment   sent   sent.
treated as an  im-     if   advertisement
plied  acknowledg-     received  from DR,
ment (see  Section     otherwise do noth-
13, step 7a).          ing
______________________________________________________________
Advertisement is a     Direct acknowledg-   Direct acknowledg-
duplicate, and was     ment sent.           ment sent.
not treated as  an
implied       ack-
nowledgment.
______________________________________________________________
Advertisement's age    Direct acknowledg-   Direct acknowledg-
is equal to MaxAge,    ment sent.           ment sent.
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.

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 acks must be unicast separately over
ToP   noToC   RFC1247 - Page 112
each adjacency (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 DR, and RT3 as Backup 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 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 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.
ToP   noToC   RFC1247 - Page 113
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 packet is discarded.

Otherwise, for each acknowledgment in the 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.


14. Aging The Link State Database

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

An advertisement's 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 age may reach MaxAge.[17] 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 a Database summary list for a newly adjacent neighbor is formed,
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 is removed entirely from the router's link state
database when 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.
ToP   noToC   RFC1247 - Page 114
When, in the process of aging the link state database, an
advertisement's age hits a multiple of CheckAge, its checksum should be
verified.  If the 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 age to MaxAge and reflooding the advertisement.  This
procedure follows the same course as flushing an advertisement whose 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
age to MaxAge premature aging.

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.

A router may only prematurely age its own (self-originated) link state
advertisements.  These are the link state advertisements having the
router's own OSPF Router ID in the Advertising Router field.


15. Virtual Links

The single backbone area (Area ID = 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
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-
ToP   noToC   RFC1247 - Page 115
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 adjacency.  Such an adjacency has been
referred to 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 Interface Up event occurs for a virtual link
when its corresponding TOS 0 routing table entry becomes reachable.
Conversely, the Interface Down event occurs when its TOS 0 routing table
entry becomes unreachable.[18] 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.  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 protocol packets over the virtual link.

o   In each endpoint's router links advertisement for the backbone, the
    virtual link is represented as a link having link type 4, Link ID
    set to the virtual neighbor's OSPF Router ID and Link Data set to
    the virtual interface's IP address.  See Section 12.4.1 for more
    information.  Also, it may be the case that there is a TOS 0 path,
ToP   noToC   RFC1247 - Page 116
    but no non-zero TOS paths to the other endpoint router.  In this
    case, non-zero TOS costs must be set to LSInfinity in the router
    links advertisement.

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

(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.
ToP   noToC   RFC1247 - Page 117
(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) For those routing entries whose next hop is over a virtual link, a
    real (physical) next hop is calculated.  The real next hop will be
    on one of the router's directly attached networks.  This step only
    concerns routers having configured virtual links.

(5) Routes to external destinations are calculated, through examination
    of AS external link advertisements.  The location of the AS boundary
    routers (which originate the AS external link advertisements) has
    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.[19]
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 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.[20] 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   noToC   RFC1247 - Page 118
Vertex (node) ID
    A 32-bit number uniquely identifying the vertex.  For router
    vertices this is the 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 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 shortest path(s) 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.


The first stage of the procedure can now be summarized as follows.  At
each iteration of the algorithm, there is a list of candidate vertices.
The shortest paths from the root to these vertices have not
(necessarily) been found.  The candidate vertex closest to the root 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 first stage 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).
ToP   noToC   RFC1247 - Page 119
(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 link state database based on the Vertex ID.  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 age is equal to MaxAge, or
        it does not have a link back to vertex V, examine the next link
        in V's advertisement.  Both ends of a link must advertise the
        link before it will be used for data traffic.[21]

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

    (d) If the cost of the link (from V to W) is LSInfinity, the link
        should not be used for data traffic.  In this case, examine the
        next link in the advertisement.

    (e) 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 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 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
ToP   noToC   RFC1247 - Page 120
            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 algorithm 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).

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

    If the newly added vertex is an area border router, 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 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: A set of intra-area paths having no
    virtual next hops is always preferred over a set of intra-area paths
    in which some virtual next hops appear[22] ; all other things being
    equal the set of paths having lower cost is preferred.  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
    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
    added vertex' link state advertisement.
ToP   noToC   RFC1247 - Page 121
    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) If the cost of the stub network link is LSInfinity, the link should
    not be used for data traffic.  In this case, go on to examine the
    next stub network link in the advertisement.

(2) Otherwise, 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 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.

(3) 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 routing table entry's Link State origin to
    V's router links advertisement.  Then go on to examine the next stub
    network link.
ToP   noToC   RFC1247 - Page 122
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 algorithms exist for incrementally updating the
shortest-path tree (see [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 2e of Stage
1).  In stage 2 a shorter path is discovered each time the destination's
routing table entry is modified (Step 3 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).

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.
ToP   noToC   RFC1247 - Page 123
In the second case, the destination is a router, and its parent vertex
is a network.  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, then
    examine the next advertisement.

(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
    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 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, and the
    area border originating the advertisement BR.  Look up the routing
    table entry for BR having 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
ToP   noToC   RFC1247 - Page 124
    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 "AS
    external", install the inter-area path to N, with associated 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.


16.3 Resolving virtual next hops

This step is only necessary in area-border routers having configured
virtual links.  In these routers, some of the routing table entries may
have virtual next hops.  That is, one or more of the next hops installed
in Sections 16.1 and 16.2 may be over a virtual link.  However, when
forwarding data traffic to a destination, the next hops must always be
on a directly attached network.

In this section, each virtual next hop is replaced by a real next hop.
In the process a new routing table distance is calculated that may be
smaller than the previously calculated distance.  In this case, the list
of next hops is pruned so that only those giving rise to the new
shortest distance are included, and the routing table entry's distance
is updated accordingly.




                 ______________________________________

                 (Figure not included in text version.)

                 Figure 17: Resolving virtual next hops
                 ______________________________________
ToP   noToC   RFC1247 - Page 125
This resolution of virtual next hops is done only for Destination types
Network or AS Boundary router.  Suppose that one of a routing table
entry's next hops is a virtual link.  This is determined by the
following combination: the routing table entry's path type is either
intra-area or inter-area, the area associated with the routing table
entry must be the backbone, yet the next hop belongs to a different area
(the virtual link's transit area).

Let N be the above entry's destination, and A the virtual link's transit
area.  The real next hop (and new distance) is calculated as follows.
Let D be a distance counter, and set the real next hop NH to null.
Then, look up all the summary link advertisements for N in area A's
database, performing the following steps for each advertisement:[23]


(1) Call the border router that originated the advertisement BR.  If
    there is no routing table entry for BR having A as associated area
    (i.e., BR is unreachable through Area A), examine the next
    advertisement.

(2) Else, let X be the distance to BR via Area A.  If the cost
    advertised by BR (call it Y) to the destination is LSInfinity,
    examine the next summary link advertisement.  Else, the cost to
    destination N through area border router BR is X+Y.

(3) If next hop NH is null or X+Y is smaller is smaller than D, set D to
    X+Y and set the next hop NH to the next hop specified in router BR's
    routing table entry.


At this point, the real next hop NH should be set, and the distance D
calculated should be less than or equal to the cost originally specified
in destination N's routing table entry.  This same calculation should be
done for all of N's virtual next hops, and then N's new cost set to the
minimum calculated distance, with the its new set of next hops that
combination of non-virtual and recalculated next hops that correspond to
this (possibly same as original) distance.

The resolving of virtual next hops may produce unexpected results.
After the virtual next hops are resolved, traffic that was originally
scheduled to go over the virtual link may instead take a different path
through the virtual link's transit area.  In other words, virtual links
allow transit traffic to be forwarded through an area, but do not
dictate the precise path that the traffic will take.

As an example, consider the Autonomous System pictured in Figure 17.
There is a single non-backbone area (Area 1) that physically divides the
backbone into two separate pieces.  To maintain connectivity of the
ToP   noToC   RFC1247 - Page 126
backbone, a virtual link has been configured between routers RT1 and
RT4.  On the right side of the figure, network N1 belongs to the
backbone.  The dotted lines indicate that there is a much shorter
intra-area backbone path between router RT5 and network N1 (cost 20)
than there is between router RT4 and network N1 (cost 100).  Both router
RT4 and router RT5 will inject summary link advertisements for network
N1 into Area 1.

After the shortest-path tree has been calculated for the backbone,
router RT1 (one end of the virtual link) will have selected router RT4
as the virtual next hop for all data traffic destined for network N1.
However, since router RT5 is so much closer to network N1, all routers
internal to Area 1 (e.g., routers RT2 and RT3) will forward their
network N1 traffic towards router RT5, instead of RT4.  And indeed,
after resolving the virtual next hop by the above calculation, router
RT1 will also forward network N1 traffic towards RT5.  So, in this
example the virtual link enables network N1 traffic to be forwarded
through the transit Area 1, but the actual path the data traffic takes
does not follow the virtual link.


16.4 Calculating AS external routes

AS external routes are calculated by examining AS external link
advertisements.  Each of the AS external link advertisements is
considered in turn.  Most AS external advertisements describe routes to
specific IP destinations.  An AS external advertisement can also
describe a default route for the Autonomous System (destination =
DefaultDestination).  For each AS external link advertisement:


(1) If the cost specified by the advertisement is LSInfinity, then
    examine the next advertisement.

(2) If the advertisement was originated by the calculating router
    itself, examine the next advertisement.

(3) Call the destination described by the advertisement N.  Look up the
    routing table entry for the AS boundary router (ASBR) that
    originated the advertisement.  If no entry exists for router ASBR
    (i.e., ASBR is unreachable), do nothing with this advertisement and
    consider the next in the list.

    Else, this advertisement describes an AS external path to
    destination N.  Examine the forwarding address specified in the
    external advertisement.  This indicates the IP address to which
    packets for the destination should be forwarded.  If forwarding
    address is set to 0.0.0.0, packets should be sent to the ASBR
ToP   noToC   RFC1247 - Page 127
    itself.  Otherwise, look up the forwarding address in the routing
    table.[24] An intra-area or inter-area path must exist to the
    forwarding address.  If no such path exists, do nothing with the
    advertisement and consider the next in the list.

    Call the routing table distance to the forwarding address X (when
    the forwarding address is set to 0.0.0.0, this is the distance to
    the ASBR itself), and the cost specified in the advertisement Y.  X
    is in terms of the link state metric, and Y is a Type 1 or 2
    external metric.

(4) Next, look up the routing table entry for the destination N.  If no
    entry exists for N, install the AS external path to N, with next hop
    equal to the list of next hops to the forwarding address, and
    advertising router equal to ASBR.  If the external metric type is 1,
    then the path-type is set to type 1 external and the cost is equal
    to X+Y.  If the external metric type is 2, the the path-type is set
    to type 2 external, the link state component of the route's cost is
    X, and the Type 2 cost is Y.

(5) Else, if the paths present in the table are not type 1 or type 2
    external paths, do nothing (AS external paths have the lowest
    priority).

(6) Otherwise, compare the cost of this new AS external path to the ones
    present in the table.  Type 1 external paths are always shorter than
    Type 2 external paths.  Type 1 external paths are compared by
    looking at the sum of the distance to the forwarding address and the
    advertised Type 1 metric (X+Y).  Type 2 external paths are compared
    by looking at the advertised Type 2 metrics, and then if necessary,
    the distance to the forwarding addresses.

    If the new path is shorter, it replaces the present paths in the
    routing table entry.  If the new path is the same cost, it is added
    to the routing table entry's list of paths.


16.5 Incremental updates --- summary links

When a new summary link advertisement is received, it is not necessary
to recalculate the entire routing table.  Call the destination described
by the summary link advertisement N, and let A be the area to which the
advertisement belongs.

Look up the routing table entry for N.  If the next hop to N is a
virtual link through Area A (this means that the entry's associated area
is the backbone, and the listed next hop does not belong to the
backbone, but instead belongs to Area A), the real next hop must again
ToP   noToC   RFC1247 - Page 128
be resolved.  This means running the algorithm in Section 16.3 for
destination N only.

Else, if there is an intra-area route to destination N nothing need be
done (intra-area routes always take precedence).  Otherwise, if Area A
is the router's sole attached area, or Area A is the backbone, the
procedure in Section 16.2 will have to be performed, but only for those
summary link advertisements whose destination is N.  Before this
procedure is performed, the present routing table entry for N should be
invalidated (but kept for comparison purposes).  If this procedure leads
to a virtual next hop, the algorithm in Section 16.3 will again have to
be performed in order to calculate the real next hop.

If N's routing table entry changes, and N is an AS boundary router, the
AS external links will have to be reexamined (Section 16.4).


16.6 Incremental updates --- AS external links

When a new AS external link advertisement is received, it is not
necessary to recalculate the entire routing table.  Call the destination
described by the AS external link advertisement N.  If there is already
an intra-area or inter-area route to the destination, no recalculation
is necessary (these routes take precedence).

Otherwise, the procedure in Section 16.4 will have to be performed, but
only for those AS external link advertisements whose destination is N.
Before this procedure is performed, the present routing table entry for
N should be invalidated.


16.7 Events generated as a result of routing table changes

Changes to routing table entries sometimes cause the OSPF area border
routers to take additional actions.  These routers need to act on the
following routing table changes:


o   The cost or path type of a routing table entry has changed.  If the
    destination described by this entry is a Network or AS boundary
    router, and this is not simply a change of AS external routes, new
    summary link advertisements may have to be generated (potentially
    one for each attached area, including the backbone).  See Section
    12.4.3 for more information.  If a previously advertised entry has
    been deleted, or is no longer advertisable to a particular area, the
    advertisement must be flushed from the routing domain by setting its
    age to MaxAge and reflooding (see Section 14.1).
ToP   noToC   RFC1247 - Page 129
o   A routing table entry associated with a configured virtual link has
    changed.  The destination of such a routing table entry is an area
    border router.  The change indicates a modification to the virtual
    link's cost or viability.

    If the entry indicates that the area border router is newly
    reachable (via TOS 0), the corresponding virtual link is now
    operational.  An Interface Up event should be generated for the
    virtual link, which will cause a virtual adjacency to begin to form
    (see Section 10.3).  At this time the virtual interface's IP address
    and the virtual neighbor's IP address are also calculated.

    If the entry indicates that the area border router is no longer
    reachable (via TOS 0), the virtual link and its associated adjacency
    should be destroyed.  This means an Interface Down event should be
    generated for the associated virtual link.

    If the cost of the entry has changed, and there is a fully
    established virtual adjacency, a new router links advertisement for
    the backbone must be originated.  This in turn may cause further
    routing table changes.


16.8 Equal-cost multipath

The OSPF protocol maintains multiple equal-cost routes to all
destinations.  This can be seen in the steps used above to calculate the
routing table, and in the definition of the routing table structure.

Each one of the multiple routes will be of the same type (intra-area,
inter-area, type 1 external or type 2 external), cost, and will have the
same associated area.  However, each route specifies a separate next hop
and advertising router.

There is no requirement that a router running OSPF keep track of all
possible equal-cost routes to a destination.  An implementation may
choose to keep only a fixed number of routes to any given destination.
This does not affect any of the algorithms presented in this
specification.


16.9 Building the non-zero-TOS portion of the routing table

The OSPF protocol can calculate a different set of routes for each IP
TOS (see Section 2.4).  Support for TOS-based routing is optional.
TOS-capable and non-TOS-capable routers can be mixed in an OSPF routing
domain.  Routers not supporting TOS calculate only the TOS 0 route to
each destination.  These routes are then used to forward all data
ToP   noToC   RFC1247 - Page 130
traffic, regardless of the TOS indications in the data packet's IP
header.  A router that does not support TOS indicates this fact to the
other OSPF routers by clearing the T-bit in the Options field of its
router links advertisement.

The above sections detailing the routing table calculations handle the
TOS 0 case only.  In general, for routers supporting TOS-based routing,
each piece of the routing table calculation must be rerun separately for
the non-zero TOS values.  When calculating routes for TOS X, only TOS X
metrics can be used.  Any link state advertisement may specify a
separate cost for each TOS (a cost for TOS 0 must always be specified).
The encoding of TOS in OSPF link state advertisements is described in
Section 12.3.

An advertisement can specify that it is restricted to TOS 0 (i.e., non-
zero TOS is not handled) by clearing the T-bit in the link state
advertisement's Option field.  Such advertisements are not used when
calculating routes for non-zero TOS.  For this reason, it is possible
that a destination is unreachable for some non-zero TOS.  In this case,
the TOS 0 path is used when forwarding packets (see Section 11.1).

The following lists the modifications needed when running the routing
table calculation for a non-zero TOS value (called TOS X).  In general,
routers and advertisements that do not support TOS are omitted from the
calculation.


Calculating the shortest-path tree (Section  16.1).
    Routers that do not support TOS-based routing should be omitted from
    the shortest-path tree calculation.  These routers are identified as
    those having the T-bit reset in their router links advertisements.
    Such routers should never be added to the Dijktra algorithm's
    candidate list, nor should their router links advertisements be
    examined when adding the stub networks to the tree.

Calculating the inter-area routes (Section  16.2).
    Inter-area paths are the concatenation of a path to an area border
    router with a summary link.  When calculating TOS X routes, both
    path components must also specify TOS X.  In other words, only TOS X
    paths to the area border router are examined, and the area border
    router must be advertising a TOS X route to the destination.  Note
    that this means that summary link advertisements having the T-bit
    reset in their Options field are not considered.

Resolving virtual next hops (Section 16.3).
    This calculation again considers the concatenation of a path to an
    area border router with a summary link.  As with inter-area routes,
    only TOS X paths to the area border router are examined, and the
ToP   noToC   RFC1247 - Page 131
    area border router must be advertising a TOS X route to the
    destination.

Calculating AS external routes (Section 16.4).
    This calculation considers the concatenation of a path to a
    forwarding address with an AS external link.  Only TOS X paths to
    the forwarding address are examined, and the AS boundary router must
    be advertising a TOS X route to the destination.  Note that this
    means that AS external link advertisements having the T-bit reset in
    their Options field are not considered.

    In addition, the advertising AS boundary router must also be
    reachable for its advertisements to be considered (see Section
    16.4).  However, if the advertising router and the forwarding
    address are not one in the same, the advertising router need only be
    reachable via TOS 0.
ToP   noToC   RFC1247 - Page 132
    [1]The graph's vertices represent either routers, transit networks,
    or stub networks.  Since routers may belong to multiple areas, it is
    not possible to color the graph's vertices.

    [2]It is possible for all of a router's interfaces to be unnumbered
    point-to-point links.  In this case, an IP address must be assigned
    to the router.  This address will then be advertised in the router's
    router links advertisement as a host route.

    [3]Note that in these cases both interfaces, the non-virtual and the
    virtual, would have the same IP address.

    [4]Note that no host route is generated for, and no IP packets can
    be addressed to, interfaces to unnumbered point-to-point networks.
    This is regardless of such an interface's state.

    [5]It is instructive to see what happens when the Designated Router
    for the network crashes.  Call the Designated Router for the network
    RT1, and the the Backup Designated Router RT2.  If router RT1
    crashes (or maybe its interface to the network dies), the other
    routers on the network will detect RT1's absence within
    RouterDeadInterval seconds.  All routers may not detect this at
    precisely the same time; the routers that detect RT1's absence
    before RT2 does will, for a time, select RT2 to be both Designated
    Router and Backup Designated Router.  When RT2 detects that RT1 is
    gone it will move itself to Designated Router.  At this time, the
    remaining router having highest Router Priority will be selected as
    Backup Designated Router.

    [6]On point-to-point networks, the lower level protocols indicate
    whether the neighbor is up and running.  Likewise, existence of the
    neighbor on virtual links is indicated by the routing table
    calculation.  However, in both these cases, the Hello Protocol is
    still used.  This ensures that communication between the neighbors
    is bidirectional, and that each of the neighbors has a functioning
    routing protocol layer.

    [7]When the identity of the Designated Router is changing, it may be
    quite common for a neighbor in this state to send the router a
    Database Description packet; this means that there is some momentary
    disagreement on the Designated Router's identity.

    [8]Note that it is possible for a router to resynchronize any of its
    fully established adjacencies by setting the adjacency's state back
    to ExStart.  This will cause the other end of the adjacency to
    process a Seq Number Mismatch event, and therefore to also go back
    to ExStart state.
ToP   noToC   RFC1247 - Page 133
    [9]The address space of IP networks and the address space of OSPF
    Router IDs may overlap.  That is, a network may have an IP address
    which is identical (when considered as a 32-bit number) to some
    router's Router ID.

    [10]It is assumed that, for two different address ranges matching
    the destination, one range is more specific than the other. Non-
    contiguous subnet masks can be configured to violate this
    assumption. Such subnet mask configurations cannot be handled by the
    OSPF protocol.

    [11]MaxAgeDiff is an architectural constant.  It indicates the
    maximum dispersion of ages, in seconds, that can occur for a single
    link state instance as it is flooded throughout the routing domain.
    If two advertisements differ by more than this, they are assumed to
    be different instances of the same advertisement.  This can occur
    when a router restarts and loses track of its previous sequence
    number.  See Section 13.4 for more details.

    [12]When two advertisements have different checksums, they are
    assumed to be separate instances.  This can occur when a router
    restarts, and loses track of its previous sequence number.  In this
    case, since the two advertisements have the same sequence number, it
    is not possible to determine which link state is actually newer.  If
    the wrong advertisement is accepted as newer, the originating router
    will originate another instance.  See Section 13.4 for further
    details.

    [13]There is one instance where a lookup must be done based on
    partial information.  This is during the routing table calculation,
    when a network links advertisement must be found based solely on its
    Link State ID.  The lookup in this case is still well defined, since
    no two network advertisements can have the same Link State ID.

    [14]This clause covers the case: Inter-area routes are not
    summarized to the backbone.  This is because inter-area routes are
    always associated with the backbone area.

    [15]By keeping more information in the routing table, it is possible
    for an implementation to recalculate the shortest path tree only for
    a single area.  In fact, there are incremental algorithms that allow
    an implementation to recalculate only a portion of the shortest path
    tree [BBN].  These algorithms are beyond the scope of this
    specification.

    [16]This is how the Link state request list is emptied, which
    eventually causes the neighbor state to transition to Full.  See
    Section 10.9 for more details.
ToP   noToC   RFC1247 - Page 134
    [17]It should be a relatively rare occurrence for an advertisement's
    age to reach MaxAge.  Usually, the advertisement will be replaced by
    a more recent instance before it ages out.

    [18]Only the TOS 0 routes are important here.  This is because all
    routing protocol packets are sent with TOS= 0.  See Appendix A.

    [19]It may be the case that paths to certain destinations do not
    vary based on TOS.  For these destinations, the routing calculation
    need not be repeated for each TOS value.  In addition, there need
    only be a single routing table entry for these destinations (instead
    of a separate entry for each TOS value).

    [20]Strictly speaking, because of equal-cost multipath, the
    algorithm does not create a tree.  We continue to use the "tree"
    terminology because that is what occurs most often in the existing
    literature.

    [21]This means that before data traffic will flow between a pair of
    neighboring routers, their link state databases must be
    synchronized.  Before synchronization (neighbor state < Full), a
    router will not include the connection to its neighbor in its link
    state advertisements.

    [22]As a result of this clause, when a virtual link exists between
    the calculating router and an AS boundary router, the intra-area
    path through the virtual link's transit area is always preferred
    over the virtual link itself.

    [23]Note the similarity between this procedure and the calculation
    of inter-area routes by a router internal to Area A.

    [24]When the forwarding address is non-zero, it should point to a
    router belonging to another Autonomous System.  See Section 12.4.4
    for more details.


(next page on part 6)

Next Section