and the cost set to 0.
o Else if the state of the interface is Waiting, add a Type 3 link
(stub network) whose Link ID is the IP network number of the
attached network and whose Link Data is the attached network's
address mask.
o Else, there has been a Designated Router selected for the attached
network. If the router is fully adjacent to the Designated Router,
or if the router itself is Designated Router and is fully adjacent
to at least one other router, add a single Type 2 link (transit
network) whose whose link ID is the IP interface address of the
attached network's Designated Router (which may be the router
itself) and whose Link Data is the interface IP address. Otherwise,
add a link as if the interface state were Waiting (see above).
Unless otherwise specified, the cost of each link generated by the above
procedure is equal to the output cost of the associated interface. Note
that in the case of serial lines, multiple links may be generated by a
single interface.
After consideration of all the router interfaces, host links are added
to the advertisement by examining the list of attached hosts. A host
route is represented as a Type 3 link (stub network) whose link ID is
the host's IP address and whose Link Data is the mask of all ones
(0xffffffff).
As an example, consider the router links advertisements generated by
router RT3, as pictured in Figure 6. The area containing router RT3
(Area 1) has been redrawn, with actual network addresses, in Figure 15.
Assume that the last byte of all of RT3's interface addresses is 3,
giving it the interface addresses 192.1.1.3 and 192.1.4.3, and that the
other routers have similar addressing schemes. In addition, assume that
all links are functional, and that Router IDs are assigned as the
smallest IP interface address.
RT3 originates two router links advertisements, one for Area 1 and one
for the backbone. Assume that router RT4 has been selected as the
Designated router for network 192.1.1.0. RT3's router links
advertisement for Area 1 is then shown below. It indicates that RT3 has
two connections to Area 1, the first a link to the transit network
192.1.1.0 and the second a link to the stub network 192.1.4.0. Note
that the transit network is identified by the IP interface of its
Designated Router (i.e., the Link ID = 192.1.1.4 which is the Designated
Router RT4's IP interface to 192.1.1.0). Note also that RT3 has
indicated that it is capable of calculating separate routes based on IP
TOS, through setting the T-bit in the Options field. It has also
indicated that it is an area border router.
; RT3's router links advertisement for Area 1
LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable
LS type = 1 ;indicates router links
Link State ID = 192.1.1.3 ;RT3's Router ID
Advertising Router = 192.1.1.3 ;RT3's Router ID
bit E = 0 ;not an AS boundary router
bit B = 1 ;RT3 is an area border router
#links = 2
Link ID = 192.1.1.4 ;IP address of Designated Router
Link Data = 192.1.1.3 ;RT3's IP interface to net
Type = 2 ;connects to transit network
# other metrics = 0
TOS 0 metric = 1
Link ID = 192.1.4.0 ;IP Network number
Link Data = 0xffffff00 ;Network mask
Type = 3 ;connects to stub network
# other metrics = 0
TOS 0 metric = 2
Next RT3's router links advertisement for the backbone is shown. It
indicates that RT3 has a single attachment to the backbone. This
attachment is via an unnumbered point-to-point link to router RT6. RT3
has again indicated that it is TOS-capable, and that it is an area
border router.
; RT3's router links advertisement for the backbone
LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable
LS type = 1 ;indicates router links
Link State ID = 192.1.1.3 ;RT3's router ID
Advertising Router = 192.1.1.3 ;RT3's router ID
bit E = 0 ;not an AS boundary router
bit B = 1 ;RT3 is an area border router
#links = 1
Link ID = 18.10.0.6 ;Neighbor's Router ID
Link Data = 0.0.0.0 ;Interface to unnumbered SL
Type = 1 ;connects to router
# other metrics = 0
TOS 0 metric = 8
Even though router RT3 has indicated that it is TOS-capable in the above
examples, only a single metric (the TOS 0 metric) has been specified for
each interface. Different metrics can be specified for each TOS. The
encoding of TOS in OSPF link state advertisements is described in
Section 12.3.
As an example, suppose the point-to-point link between routers RT3 and
RT6 in Figure 15 is a satellite link. The AS administrator may want to
encourage the use of the line for high bandwidth traffic. This would be
done by setting the metric artificially low for that TOS. Router RT3
would then originate the following router links advertisement for the
backbone (IP TOS 8 = high bandwidth):
; RT3's router links advertisement for the backbone
LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable
LS type = 1 ;indicates router links
Link State ID = 192.1.1.3 ;RT3's Router ID
Advertising Router = 192.1.1.3
bit E = 0 ;not an AS boundary router
bit B = 1 ;RT3 is an area border router
#links = 1
Link ID = 18.10.0.6 ; Neighbor's Router ID
Link Data = 0.0.0.0 ;Interface to unnumbered SL
Type = 1 ;connects to router
# other metrics = 1
TOS 0 metric = 8
TOS = 8 ;High bandwidth
metric = 1 ;traffic preferred
12.4.2 Network links
A network links advertisement is generated for every transit multi-
access network. (A transit network is a network having two or more
attached routers). The network links advertisement describes all the
routers that are attached to the network.
The Designated Router for the network originates the advertisement. The
Designated Router originates the advertisement only if it is fully
adjacent to at least one other router on the network. The network links
advertisement is flooded throughout the area that contains the transit
network, and no further. The networks links advertisement lists those
routers that are fully adjacent to the Designated Router; each fully
adjacent router is identified by its OSPF Router ID. The Designated
Router includes itself in this list.
The Link State ID for a network links advertisement is the IP interface
address of the Designated Router. This value, masked by the network's
address mask (which is also contained in the network links
advertisement) yields the network's IP address.
A router that has formerly been the Designated Router for a network, but
is no longer, should flush the network links advertisement that it had
previously originated. This advertisement is no longer used in the
routing table calculation. It is flushed by prematurely incrementing
the advertisement's age to MaxAge and reflooding (see Section 14.1).
As an example of a network links advertisement, again consider the area
configuration in Figure 6. Network links advertisements are originated
for network N3 in Area 1, networks N6 and N8 in Area 2, and network N9
in Area 3. Assuming that router RT4 has been selected as the Designated
Router for network N3, the following network links advertisement is
generated by RT4 on behalf of network N3 (see Figure 15 for the address
assignments):
; network links advertisement for network N3
LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable
LS type = 2 ;indicates network links
Link State ID = 192.1.1.4 ;IP address of Designated Router
Advertising Router = 192.1.1.4 ;RT4's Router ID
Network Mask = 0xffffff00
Attached Router = 192.1.1.4 ;Router ID
Attached Router = 192.1.1.1 ;Router ID
Attached Router = 192.1.1.2 ;Router ID
Attached Router = 192.1.1.3 ;Router ID
12.4.3 Summary links
Each summary link advertisement describes a route to a single
destination. Summary link advertisements are flooded throughout a
single area only. The destination described is one that is external to
the area, yet still belonging to the Autonomous System.
The DefaultDestination can also be specified in summary link
advertisements. This is used when implementing OSPF's stub area
functionality (see Section 3.6). In a stub area, instead of importing
external routes each area border router originates a "default summary
link" (Link State ID = DefaultDestination) into the area.
Summary link advertisements are originated by area border routers. The
precise summary routes to advertise into an area are determined by
examining the routing table structure (see Section 11). Only intra-area
routes are advertised into the backbone. Both intra-area and inter-area
routes are advertised into the other areas.
To determine which routes to advertise into an attached Area A, each
routing table entry is processed as follows:
o Only Destination types of network and AS boundary router are
advertised in summary link advertisements. If the routing table
entry's Destination type is area border router, examine the next
routing table entry.
o AS external routes are never advertised in summary link
advertisements. If the routing table entry has Path-type type 1
external or type 2 external, examine the next routing table entry.
o Else, if the area associated with this set of paths is the Area A
itself, do not generate a summary link advertisement for the
route.[14]
o Else, if the destination of this route is an AS boundary router,
generate a Type 4 link state advertisement for the destination, with
Link State ID equal to the AS boundary router's ID and metric equal
to the routing table entry's cost. These advertisements should not
be generated if area A has been configured as a stub area.
o Else, the Destination type is network. If this is an inter-area
route, generate a Type 3 advertisement for the destination, with
Link State ID equal to the network's address and metric equal to the
routing table cost.
o The one remaining case is an intra-area route to a network. This
means that the network is contained in one of the router's directly
attached areas. In general, this information must be condensed
before appearing in summary link advertisements. Remember that an
area has been defined as a list of address ranges, each range
consisting of an [address,mask] pair. A single Type 3 advertisement
must be made for each range, with Link State ID equal to the range's
address and cost equal to the smallest cost of any of the component
networks.
If virtual links are being used to provide/increase connectivity of
the backbone, routing information concerning the backbone networks
should not be condensed before being summarized into the virtual
links' transit areas. In other words, the backbone ranges should be
ignored when originating summary links into these areas. The
existence of virtual links can be determined during the shortest
path calculation for the backbone (see Section 16.1).
In addition, if area A has been configured as a stub area and the router
is an area border router, it should advertise a default summary link
into Area A. The Link State ID for the advertisement should be set to
DefaultDestination, and the metric set to the (per-area) configurable
parameter StubDefaultCost.
If a router advertises a summary advertisement for a destination which
then becomes unreachable, the router must then flush the advertisement
from the routing domain by setting its age to MaxAge and reflooding (see
Section 14.1). Also, if the destination is still reachable, yet can no
longer be advertised according to the above procedure (e.g., it is now
an inter-area route, when it used to be an intra-area route associated
with some non-backbone area; it would thus no longer be advertisable to
the backbone), the advertisement should also be flushed from the routing
domain.
For an example of summary link advertisements, consider again the area
configuration in Figure 6. Routers RT3, RT4, RT7, RT10 and RT11 are all
area border routers, and therefore are originating summary links
advertisements. Consider in particular router RT4. Its routing table
was calculated as the example in Section 11.3. RT4 originates summary
link advertisements into both the backbone and Area 1. Into the
backbone, router RT4 originates separate advertisements for each of the
networks N1-N4. Into Area 1, router RT4 originates separate
advertisements for networks N6-N8 and the AS boundary routers RT5,RT7.
It also condenses host routes Ia and Ib into a single summary
advertisement. Finally, the routes to networks N9,N10,N11 and host H9
are advertised by a single summary link. This condensation was
originally performed by the router RT11.
These advertisements are illustrated graphically in Figures 7 and 8.
Two of the summary link advertisements originated by router RT4 follow.
The actual IP addresses for the networks and routers in question have
been assigned in Figure 15.
; summary link advertisement for network N1,
; originated by router RT4 into the backbone
LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable
LS type = 3 ;indicates summary link to IP net
Link State ID = 192.1.2.0 ;N1's IP network number
Advertising Router = 192.1.1.4 ;RT4's ID
TOS = 0
metric = 4
; summary link advertisement for AS boundary router RT7
; originated by router RT4 into Area 1
LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable
LS type = 4 ;indicates summary link to ASBR
Link State ID = router RT7's ID
Advertising Router = 192.1.1.4 ;RT4's ID
TOS = 0
metric = 14
Summary link advertisements pertain to a single destination (IP network
or AS boundary router). However, for a single destination there may be
separate sets of paths, and therefore separate routing table entries,
for each Type of Service. All these entries must be considered when
building the summary link advertisement for the destination; a single
advertisement must specify the separate costs (if they exist) for each
TOS. The encoding of TOS in OSPF link state advertisements is described
in Section 12.3.
Clearing the T-bit in the Options field of a summary link advertisement
indicates that there is a TOS 0 path to the destination, but no paths
for non-zero TOS. This can happen when non-TOS capable routers exist in
the routing domain (see Section 2.4).
12.4.4 AS external links
AS external link advertisements describe routes to destinations external
to the Autonomous System. Most AS external link advertisements describe
routes to specific external destinations. However, a default route for
the Autonomous System can be described in an AS external advertisement
by setting the advertisement's Link State ID to DefaultDestination
(0.0.0.0). AS external link advertisements are originated by AS
boundary routers. An AS boundary router originates a single AS external
link advertisement for each external route that it has learned, either
through another routing protocol (such as EGP), or through configuration
information.
In general, AS external link advertisements are the only type of link
state advertisements that are flooded throughout the entire Autonomous
System; all other types of link state advertisements are specific to a
single area. However, AS external advertisements are not flooded
into/throughout stub areas (see Section 3.6). This enables a reduction
in link state database size for routers internal to stub areas.
The metric that is advertised for an external route can be one of two
types. Type 1 metrics are comparable to the link state metric. Type 2
metrics are assumed to be larger than the cost of any intra-AS path. As
with summary link advertisements, if separate paths exist based on TOS,
separate TOS costs can be included in the AS external link
advertisement. The encoding of TOS in OSPF link state advertisements is
described in Section 12.3. If the T-bit of the advertisement's Options
field is clear, no non-zero TOS paths to the destination exist.
If a router advertises an AS external link advertisement for a
destination which then becomes unreachable, the router must then flush
the advertisement from the routing domain by setting its age to MaxAge
and reflooding (see Section 14.1).
For an example of AS external link advertisements, consider once again
the AS pictured in Figure 6. There are two AS boundary routers: RT5 and
RT7. Router RT5 originates three external link advertisements, for
networks N12-N14. Router RT7 originates two external link
advertisements, for networks N12 and N15. Assume that RT7 has learned
its route to N12 via EGP, and that it wishes to advertise a Type 2
metric to the AS. RT7 would then originate the following advertisement
for N12:
; AS external link advertisement for network N12,
; originated by router RT7
LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable
LS type = 5 ;indicates AS external link
Link State ID = N12's IP network number
Advertising Router = Router RT7's ID
bit E = 1 ;Type 2 metric
TOS = 0
metric = 2
Forwarding address = 0.0.0.0
In the above example, the forwarding address field has been set to
0.0.0.0, indicating that packets for the external destination should be
forwarded to the advertising OSPF router (RT7). This is not always
desirable. Consider the example pictured in Figure 16. There are three
OSPF routers (RTA, RTB and RTC) connected to a common network. Only one
of these routers, RTA, is exchanging EGP information with the non-OSPF
router RTX. RTA must then originate AS external link state
advertisements for those destinations it has learned from RTX. By using
the AS external advertisement's forwarding address field, RTA can
specify that packets for these destinations be forwarded directly to
RTX. Without this feature, routers RTB and RTC would take an extra hop
to get to these destinations.
Note that when the forwarding address field is non-zero, it should point
to a router belonging to another Autonomous System.
A forwarding address can also be specified for the default route. For
example, in figure 16 RTA may want to specify that all externally-
destined packets should by default be forwarded to its EGP peer RTX.
The resulting AS external link advertisement is pictured below. Note
that the Link State ID is set to DefaultDestination.
; Default route, originated by router RTA
; Packets forwarded through RTX
LS age = 0 ;always true on origination
Options = (T-bit|E-bit) ;TOS-capable
LS type = 5 ;indicates AS external link
Link State ID = DefaultDestination ; default route
Advertising Router = Router RTA's ID
bit E = 1 ;Type 2 metric
TOS = 0
metric = 1
Forwarding address = RTX's IP address
In figure 16, suppose instead that both RTA and RTB exchange EGP
information with RTX. In this case, RTA and RTB would originate the
same set of external advertisements. These advertisements, if they
specify the same metric, would be functionally equivalent since they
would specify the same destination and forwarding address (RTX). This
leads to a clear duplication of effort. If only one of RTA or RTB
originated the set of external advertisements, the routing would remain
the same, and the size of the link state database would decrease.
However, it must be unambiguously defined as to which router originates
the advertisements (otherwise neither may, or the identity of the
originator may oscillate). The following rule is thereby established:
if two routers, both reachable from one another, originate functionally
equivalent AS external advertisements (i.e., same destination, cost and
non-zero forwarding address), then the advertisement originated by the
router having the highest OSPF Router ID is used. The router having the
lower OSPF Router ID can then flush its advertisement. Flushing a link
state advertisement is discussed in Section 14.1.
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:
(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
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:
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
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.
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.
(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.
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
______________________________________________________________
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
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.
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.
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-
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