Table 14: Changes resulting from an
additional virtual link.
12.1. The LSA Header
The LSA header contains the LS type, Link State ID and Advertising
Router fields. The combination of these three fields uniquely
identifies the LSA.
There may be several instances of an LSA present in the Autonomous
System, all at the same time. It must then be determined which
instance is more recent. This determination is made by examining the
LS sequence, LS checksum and LS age fields. These fields are also
contained in the 20-byte LSA header.
Several of the OSPF packet types list LSAs. When the instance is not
important, an LSA is referred to by its LS type, Link State ID and
Advertising Router (see Link State Request Packets). Otherwise, the
LS sequence number, LS age and LS checksum fields must also be
referenced.
A detailed explanation of the fields contained in the LSA header
follows.
12.1.1. LS age
This field is the age of the LSA in seconds. It should be processed
as an unsigned 16-bit integer. It is set to 0 when the LSA is
originated. It must be incremented by InfTransDelay on every hop of
the flooding procedure. LSAs are also aged as they are held in each
router's database.
The age of an LSA is never incremented past MaxAge. LSAs having age
MaxAge are not used in the routing table calculation. When an LSA's
age first reaches MaxAge, it is reflooded. An LSA of age MaxAge is
finally flushed from the database when it is no longer needed to
ensure database synchronization. For more information on the aging
of LSAs, consult Section 14.
The LS age field is examined when a router receives two instances of
an LSA, both having identical LS sequence numbers and LS checksums.
An instance of age MaxAge is then always accepted as most recent;
this allows old LSAs to be flushed quickly from the routing domain.
Otherwise, if the ages differ by more than MaxAgeDiff, the instance
having the smaller age is accepted as most recent.[12] See Section
13.1 for more details.
12.1.2. Options
The Options field in the LSA header indicates which optional
capabilities are associated with the LSA. OSPF's optional
capabilities are described in Section 4.5. One optional capability is
defined by this specification, represented by the E-bit found in the
Options field. The unrecognized bits in the Options field should be
set to zero. The E-bit represents OSPF's ExternalRoutingCapability.
This bit should be set in all LSAs associated with the backbone, and
all LSAs associated with non-stub areas (see Section 3.6). It should
also be set in all AS-external-LSAs. It should be reset in all
router-LSAs, network-LSAs and summary-LSAs associated with a stub
area. For all LSAs, the setting of the E-bit is for informational
purposes only; it does not affect the routing table calculation.
12.1.3. LS type
The LS type field dictates the format and function of the LSA. LSAs
of different types have different names (e.g., router-LSAs or
network-LSAs). All LSA types defined by this memo, except the AS-
external-LSAs (LS type = 5), are flooded throughout a single area
only. AS-external-LSAs are flooded throughout the entire Autonomous
System, excepting stub areas (see Section 3.6). Each separate LSA
type is briefly described below in Table 15.
12.1.4. Link State ID
This field identifies the piece of the routing domain that is being
described by the LSA. Depending on the LSA's LS type, the Link State
ID takes on the values listed in Table 16.
Actually, for Type 3 summary-LSAs (LS type = 3) and AS-external-LSAs
(LS type = 5), the Link State ID may additionally have one or more of
the destination network's "host" bits set. For example, when
originating an AS-external-LSA for the network 10.0.0.0 with mask of
255.0.0.0, the Link State ID can be set to anything in the range
10.0.0.0 through 10.255.255.255 inclusive (although 10.0.0.0 should
be used whenever possible). The freedom to set certain host bits
allows a router to originate separate LSAs for two networks having
the same address but different masks. See Appendix E for details.
LS Type LSA description
________________________________________________
1 These are the router-LSAs.
They describe the collected
states of the router's
interfaces. For more information,
consult Section 12.4.1.
________________________________________________
2 These are the network-LSAs.
They describe the set of routers
attached to the network. For
more information, consult
Section 12.4.2.
________________________________________________
3 or 4 These are the summary-LSAs.
They describe inter-area routes,
and enable the condensation of
routing information at area
borders. Originated by area border
routers, the Type 3 summary-LSAs
describe routes to networks while the
Type 4 summary-LSAs describe routes to
AS boundary routers.
________________________________________________
5 These are the AS-external-LSAs.
Originated by AS boundary routers,
they describe routes
to destinations external to the
Autonomous System. A default route for
the Autonomous System can also be
described by an AS-external-LSA.
Table 15: OSPF link state advertisements (LSAs).
LS Type Link State ID
_______________________________________________
1 The originating router's Router ID.
2 The IP interface address of the
network's Designated Router.
3 The destination network's IP address.
4 The Router ID of the described AS
boundary router.
5 The destination network's IP address.
Table 16: The LSA's Link State ID.
When the LSA is describing a network (LS type = 2, 3 or 5), the
network's IP address is easily derived by masking the Link State ID
with the network/subnet mask contained in the body of the LSA. When
the LSA is describing a router (LS type = 1 or 4), the Link State ID
is always the described router's OSPF Router ID.
When an AS-external-LSA (LS Type = 5) is describing a default route,
its Link State ID is set to DefaultDestination (0.0.0.0).
12.1.5. Advertising Router
This field specifies the OSPF Router ID of the LSA's originator. For
router-LSAs, this field is identical to the Link State ID field.
Network-LSAs are originated by the network's Designated Router.
Summary-LSAs originated by area border routers. AS-external-LSAs are
originated by AS boundary routers.
12.1.6. LS sequence number
The sequence number field is a signed 32-bit integer. It is used to
detect old and duplicate LSAs. The space of sequence numbers is
linearly ordered. The larger the sequence number (when compared as
signed 32-bit integers) the more recent the LSA. To describe to
sequence number space more precisely, let N refer in the discussion
below to the constant 2**31.
The sequence number -N (0x80000000) is reserved (and unused). This
leaves -N + 1 (0x80000001) as the smallest (and therefore oldest)
sequence number; this sequence number is referred to as the constant
InitialSequenceNumber. A router uses InitialSequenceNumber the first
time it originates any LSA. Afterwards, the LSA's sequence number is
incremented each time the router originates a new instance of the
LSA. When an attempt is made to increment the sequence number past
the maximum value of N - 1 (0x7fffffff; also referred to as
MaxSequenceNumber), the current instance of the LSA must first be
flushed from the routing domain. This is done by prematurely aging
the LSA (see Section 14.1) and reflooding it. As soon as this flood
has been acknowledged by all adjacent neighbors, a new instance can
be originated with sequence number of InitialSequenceNumber.
The router may be forced to promote the sequence number of one of its
LSAs when a more recent instance of the LSA is unexpectedly received
during the flooding process. This should be a rare event. This may
indicate that an out-of-date LSA, originated by the router itself
before its last restart/reload, still exists in the Autonomous
System. For more information see Section 13.4.
12.1.7. LS checksum
This field is the checksum of the complete contents of the LSA,
excepting the LS age field. The LS age field is excepted so that an
LSA's age can be incremented without updating the checksum. The
checksum used is the same that is used for ISO connectionless
datagrams; it is commonly referred to as the Fletcher checksum. It
is documented in Annex B of [Ref6]. The LSA header also contains the
length of the LSA in bytes; subtracting the size of the LS age field
(two bytes) yields the amount of data to checksum.
The checksum is used to detect data corruption of an LSA. This
corruption can occur while an LSA is being flooded, or while it is
being held in a router's memory. The LS checksum field cannot take
on the value of zero; the occurrence of such a value should be
considered a checksum failure. In other words, calculation of the
checksum is not optional.
The checksum of an LSA is verified in two cases: a) when it is
received in a Link State Update Packet and b) at times during the
aging of the link state database. The detection of a checksum
failure leads to separate actions in each case. See Sections 13 and
14 for more details.
Whenever the LS sequence number field indicates that two instances of
an LSA are the same, the LS checksum field is examined. If there is
a difference, the instance with the larger LS checksum is considered
to be most recent.[13] See Section 13.1 for more details.
12.2. The link state database
A router has a separate link state database for every area to which
it belongs. All routers belonging to the same area have identical
link state databases for the area.
The databases for each individual area are always dealt with
separately. The shortest path calculation is performed separately
for each area (see Section 16). Components of the area link-state
database are flooded throughout the area only. Finally, when an
adjacency (belonging to Area A) is being brought up, only the
database for Area A is synchronized between the two routers.
The area database is composed of router-LSAs, network-LSAs and
summary-LSAs (all listed in the area data structure). In addition,
external routes (AS-external-LSAs) are included in all non-stub area
databases (see Section 3.6).
An implementation of OSPF must be able to access individual pieces of
an area database. This lookup function is based on an LSA's LS type,
Link State ID and Advertising Router.[14] There will be a single
instance (the most up-to-date) of each LSA in the database. The
database lookup function is invoked during the LSA flooding procedure
(Section 13) and the routing table calculation (Section 16). In
addition, using this lookup function the router can determine whether
it has itself ever originated a particular LSA, and if so, with what
LS sequence number.
An LSA is added to a router's database when either a) it is received
during the flooding process (Section 13) or b) it is originated by
the router itself (Section 12.4). An LSA is deleted from a router's
database when either a) it has been overwritten by a newer instance
during the flooding process (Section 13) or b) the router originates
a newer instance of one of its self-originated LSAs (Section 12.4) or
c) the LSA ages out and is flushed from the routing domain (Section
14).
Whenever an LSA is deleted from the database it must also be removed
from all neighbors' Link state retransmission lists (see Section 10).
12.3. Representation of TOS
For backward compatibility with previous versions of the OSPF
specification ([Ref9]), TOS-specific information can be included in
router-LSAs, summary-LSAs and AS-external-LSAs. The encoding of TOS
in OSPF LSAs is specified in Table 17. That table relates the OSPF
encoding to the IP packet header's TOS field (defined in [Ref12]).
The OSPF encoding is expressed as a decimal integer, and the IP
packet header's TOS field is expressed in the binary TOS values used
in [Ref12].
OSPF encoding RFC1349 TOS values
___________________________________________
0 0000 normal service
2 0001 minimize monetary cost
4 0010 maximize reliability
6 0011
8 0100 maximize throughput
10 0101
12 0110
14 0111
16 1000 minimize delay
18 1001
20 1010
22 1011
24 1100
26 1101
28 1110
30 1111
Table 17: Representing TOS in OSPF.
12.4. Originating LSAs
Into any given OSPF area, a router will originate several LSAs. Each
router originates a router-LSA. If the router is also the Designated
Router for any of the area's networks, it will originate network-LSAs
for those networks.
Area border routers originate a single summary-LSA for each known
inter-area destination. AS boundary routers originate a single AS-
external-LSA for each known AS external destination. Destinations
are advertised one at a time so that the change in any single route
can be flooded without reflooding the entire collection of routes.
During the flooding procedure, many LSAs can be carried by a single
Link State Update packet.
As an example, consider Router RT4 in Figure 6. It is an area border
router, having a connection to Area 1 and the backbone. Router RT4
originates 5 distinct LSAs into the backbone (one router-LSA, and one
summary-LSA for each of the networks N1-N4). Router RT4 will also
originate 8 distinct LSAs into Area 1 (one router-LSA and seven
summary-LSAs as pictured in Figure 7). If RT4 has been selected as
Designated Router for Network N3, it will also originate a network-
LSA for N3 into Area 1.
In this same figure, Router RT5 will be originating 3 distinct AS-
external-LSAs (one for each of the networks N12-N14). These will be
flooded throughout the entire AS, assuming that none of the areas
have been configured as stubs. However, if area 3 has been
configured as a stub area, the AS-external-LSAs for networks N12-N14
will not be flooded into area 3 (see Section 3.6). Instead, Router
RT11 would originate a default summary- LSA that would be flooded
throughout area 3 (see Section 12.4.3). This instructs all of area
3's internal routers to send their AS external traffic to RT11.
Whenever a new instance of an LSA is originated, its LS sequence
number is incremented, its LS age is set to 0, its LS checksum is
calculated, and the LSA is added to the link state database and
flooded out the appropriate interfaces. See Section 13.2 for details
concerning the installation of the LSA into the link state database.
See Section 13.3 for details concerning the flooding of newly
originated LSAs.
The ten events that can cause a new instance of an LSA to be
originated are:
(1) The LS age field of one of the router's self-originated LSAs
reaches the value LSRefreshTime. In this case, a new
instance of the LSA is originated, even though the contents
of the LSA (apart from the LSA header) will be the same.
This guarantees periodic originations of all LSAs. This
periodic updating of LSAs adds robustness to the link state
algorithm. LSAs that solely describe unreachable
destinations should not be refreshed, but should instead be
flushed from the routing domain (see Section 14.1).
When whatever is being described by an LSA changes, a new LSA is
originated. However, two instances of the same LSA may not be
originated within the time period MinLSInterval. This may require
that the generation of the next instance be delayed by up to
MinLSInterval. The following events may cause the contents of an LSA
to change. These events should cause new originations if and only if
the contents of the new LSA would be different:
(2) An interface's state changes (see Section 9.1). This may
mean that it is necessary to produce a new instance of the
router-LSA.
(3) An attached network's Designated Router changes. A new
router-LSA should be originated. Also, if the router itself
is now the Designated Router, a new network-LSA should be
produced. If the router itself is no longer the Designated
Router, any network-LSA that it might have originated for
the network should be flushed from the routing domain (see
Section 14.1).
(4) One of the neighboring routers changes to/from the FULL
state. This may mean that it is necessary to produce a new
instance of the router-LSA. Also, if the router is itself
the Designated Router for the attached network, a new
network-LSA should be produced.
The next four events concern area border routers only:
(5) An intra-area route has been added/deleted/modified in the
routing table. This may cause a new instance of a summary-
LSA (for this route) to be originated in each attached area
(possibly including the backbone).
(6) An inter-area route has been added/deleted/modified in the
routing table. This may cause a new instance of a summary-
LSA (for this route) to be originated in each attached area
(but NEVER for the backbone).
(7) The router becomes newly attached to an area. The router
must then originate summary-LSAs into the newly attached
area for all pertinent intra-area and inter-area routes in
the router's routing table. See Section 12.4.3 for more
details.
(8) When the state of one of the router's configured virtual
links changes, it may be necessary to originate a new
router-LSA into the virtual link's Transit area (see the
discussion of the router-LSA's bit V in Section 12.4.1), as
well as originating a new router-LSA into the backbone.
The last two events concern AS boundary routers (and former AS
boundary routers) only:
(9) An external route gained through direct experience with an
external routing protocol (like BGP) changes. This will
cause an AS boundary router to originate a new instance of
an AS-external-LSA.
(10)
A router ceases to be an AS boundary router, perhaps after
restarting. In this situation the router should flush all
AS-external-LSAs that it had previously originated. These
LSAs can be flushed via the premature aging procedure
specified in Section 14.1.
The construction of each type of LSA is explained in detail below. In
general, these sections describe the contents of the LSA body (i.e.,
the part coming after the 20-byte LSA header). For information
concerning the building of the LSA header, see Section 12.1.
12.4.1. Router-LSAs
A router originates a router-LSA for each area that it belongs to.
Such an LSA describes the collected states of the router's links to
the area. The LSA is flooded throughout the particular area, and no
further. The format of a router-LSA is shown in Appendix A (Section
A.4.2). The first 20 bytes of the LSA consist of the generic LSA
header that was discussed in Section 12.1. router-LSAs have LS type
= 1.
A router also indicates whether it is an area border router, or an AS
boundary router, by setting the appropriate bits
....................................
. 192.1.2 Area 1 .
. + .
. | .
. | 3+---+1 .
. N1 |--|RT1|-----+ .
. | +---+ \ .
. | \ _______N3 .
. + \/ \ . 1+---+
. * 192.1.1 *------|RT4|
. + /\_______/ . +---+
. | / | .
. | 3+---+1 / | .
. N2 |--|RT2|-----+ 1| .
. | +---+ +---+8 . 6+---+
. | |RT3|----------------|RT6|
. + +---+ . +---+
. 192.1.3 |2 . 18.10.0.6|7
. | . |
. +------------+ .
. 192.1.4 (N4) .
....................................
Figure 15: Area 1 with IP addresses shown
(bit B and bit E, respectively) in its router-LSAs. This enables
paths to those types of routers to be saved in the routing table, for
later processing of summary-LSAs and AS-external-LSAs. Bit B should
be set whenever the router is actively attached to two or more areas,
even if the router is not currently attached to the OSPF backbone
area. Bit E should never be set in a router-LSA for a stub area
(stub areas cannot contain AS boundary routers).
In addition, the router sets bit V in its router-LSA for Area A if
and only if the router is the endpoint of one or more fully adjacent
virtual links having Area A as their Transit area. The setting of bit
V enables other routers in Area A to discover whether the area
supports transit traffic (see TransitCapability in Section 6).
The router-LSA then describes the router's working connections (i.e.,
interfaces or links) to the area. Each link is typed according to
the kind of attached network. Each link is also labelled with its
Link ID. This Link ID gives a name to the entity that is on the
other end of the link. Table 18 summarizes the values used for the
Type and Link ID fields.
Link type Description Link ID
__________________________________________________
1 Point-to-point Neighbor Router ID
link
2 Link to transit Interface address of
network Designated Router
3 Link to stub IP network number
network
4 Virtual link Neighbor Router ID
Table 18: Link descriptions in the
router-LSA.
In addition, the Link Data field is specified for each link. This
field gives 32 bits of extra information for the link. For links to
transit networks, numbered point-to-point links and virtual links,
this field specifies the IP interface address of the associated
router interface (this is needed by the routing table calculation,
see Section 16.1.1). For links to stub networks, this field
specifies the stub network's IP address mask. For unnumbered point-
to-point links, the Link Data field should be set to the unnumbered
interface's MIB-II [Ref8] ifIndex value.
Finally, the cost of using the link for output is specified. The
output cost of a link is configurable. With the exception of links to
stub networks, the output cost must always be non-zero.
To further describe the process of building the list of link
descriptions, suppose a router wishes to build a router-LSA for Area
A. The router examines its collection of interface data structures.
For each interface, the following steps are taken:
o If the attached network does not belong to Area A, no
links are added to the LSA, and the next interface should be
examined.
o If the state of the interface is Down, no links are added.
o If the state of the interface is Loopback, add a Type 3
link (stub network) as long as this is not an interface to an
unnumbered point-to-point network. The Link ID should be set to
the IP interface address, the Link Data set to the
mask 0xffffffff (indicating a host route), and the cost set to 0.
o Otherwise, the link descriptions added to the router-LSA
depend on the OSPF interface type. Link descriptions used for
point-to-point interfaces are specified in Section 12.4.1.1, for
virtual links in Section 12.4.1.2, for broadcast and NBMA
interfaces in 12.4.1.3, and for Point-to-MultiPoint interfaces in
12.4.1.4.
After consideration of all the router interfaces, host links are
added to the router-LSA by examining the list of attached hosts
belonging to Area A. A host route is represented as a Type 3 link
(stub network) whose Link ID is the host's IP address, Link Data is
the mask of all ones (0xffffffff), and cost the host's configured
cost (see Section C.7).
12.4.1.1. Describing point-to-point interfaces
For point-to-point interfaces, one or more link descriptions are
added to the router-LSA as follows:
o If the neighboring router is fully adjacent, add a
Type 1 link (point-to-point). The Link ID should be set to the
Router ID of the neighboring router. For numbered point-to-point
networks, the Link Data should specify the IP interface address.
For unnumbered point-to-point networks, the Link Data field
should specify the interface's MIB-II [Ref8] ifIndex value. The
cost should be set to the output cost of the point-to-point
interface.
o In addition, as long as the state of the interface
is "Point-to-Point" (and regardless of the neighboring router
state), a Type 3 link (stub network) should be added. There are
two forms that this stub link can take:
Option 1
Assuming that the neighboring router's IP address is known, set
the Link ID of the Type 3 link to the neighbor's IP address, the
Link Data to the mask 0xffffffff (indicating a host route), and
the cost to the interface's configured output cost.[15]
Option 2
If a subnet has been assigned to the point-to-point link, set the
Link ID of the Type 3 link to the subnet's IP address, the Link
Data to the subnet's mask, and the cost to the interface's
configured output cost.[16]
12.4.1.2. Describing broadcast and NBMA interfaces
For operational broadcast and NBMA interfaces, a single link
description is added to the router-LSA as follows:
o If the state of the interface is Waiting, add a Type
3 link (stub network) with Link ID set to the IP network number
of the attached network, Link Data set to the attached network's
address mask, and cost equal to the interface's configured output
cost.
o Else, there has been a Designated Router elected 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) with Link ID set to the IP
interface address of the attached network's Designated Router
(which may be the router itself), Link Data set to the router's
own IP interface address, and cost equal to the interface's
configured output cost. Otherwise, add a link as if the
interface state were Waiting (see above).
12.4.1.3. Describing virtual links
For virtual links, a link description is added to the router-LSA only
when the virtual neighbor is fully adjacent. In this case, add a Type
4 link (virtual link) with Link ID set to the Router ID of the
virtual neighbor, Link Data set to the IP interface address
associated with the virtual link and cost set to the cost calculated
for the virtual link during the routing table calculation (see
Section 15).
12.4.1.4. Describing Point-to-MultiPoint interfaces
For operational Point-to-MultiPoint interfaces, one or more link
descriptions are added to the router-LSA as follows:
o A single Type 3 link (stub network) is added with
Link ID set to the router's own IP interface address, Link Data
set to the mask 0xffffffff (indicating a host route), and cost
set to 0.
o For each fully adjacent neighbor associated with the
interface, add an additional Type 1 link (point-to-point) with
Link ID set to the Router ID of the neighboring router, Link Data
set to the IP interface address and cost equal to the interface's
configured output cost.
12.4.1.5. Examples of router-LSAs
Consider the router-LSAs 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-LSAs, 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-LSA 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 an area
border router.
; RT3's router-LSA for Area 1
LS age = 0 ;always true on origination
Options = (E-bit) ;
LS type = 1 ;indicates router-LSA
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 ;area border router
#links = 2
Link ID = 192.1.1.4 ;IP address of Desig. Rtr.
Link Data = 192.1.1.3 ;RT3's IP interface to net
Type = 2 ;connects to transit network
# TOS metrics = 0
metric = 1
Link ID = 192.1.4.0 ;IP Network number
Link Data = 0xffffff00 ;Network mask
Type = 3 ;connects to stub network
# TOS metrics = 0
metric = 2
Next RT3's router-LSA 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 an area border router.
; RT3's router-LSA for the backbone
LS age = 0 ;always true on origination
Options = (E-bit) ;
LS type = 1 ;indicates router-LSA
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 ;area border router
#links = 1
Link ID = 18.10.0.6 ;Neighbor's Router ID
Link Data = 0.0.0.3 ;MIB-II ifIndex of P-P link
Type = 1 ;connects to router
# TOS metrics = 0
metric = 8
12.4.2. Network-LSAs
A network-LSA is generated for every transit broadcast or NBMA
network. (A transit network is a network having two or more attached
routers). The network-LSA describes all the routers that are
attached to the network.
The Designated Router for the network originates the LSA. The
Designated Router originates the LSA only if it is fully adjacent to
at least one other router on the network. The network-LSA is flooded
throughout the area that contains the transit network, and no
further. The network-LSA 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-LSA 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-LSA) 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-LSA that it had previously
originated. This LSA is no longer used in the routing table
calculation. It is flushed by prematurely incrementing the LSA's age
to MaxAge and reflooding (see Section 14.1). In addition, in those
rare cases where a router's Router ID has changed, any network-LSAs
that were originated with the router's previous Router ID must be
flushed. Since the router may have no idea what it's previous Router
ID might have been, these network-LSAs are indicated by having their
Link State ID equal to one of the router's IP interface addresses and
their Advertising Router equal to some value other than the router's
current Router ID (see Section 13.4 for more details).
12.4.2.1. Examples of network-LSAs
Again consider the area configuration in Figure 6. Network-LSAs 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-LSA is
generated by RT4 on behalf of Network N3 (see Figure 15 for the
address assignments):
; Network-LSA for Network N3
LS age = 0 ;always true on origination
Options = (E-bit) ;
LS type = 2 ;indicates network-LSA
Link State ID = 192.1.1.4 ;IP address of Desig. Rtr.
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-LSAs
The destination described by a summary-LSA is either an IP network,
an AS boundary router or a range of IP addresses. Summary-LSAs are
flooded throughout a single area only. The destination described is
one that is external to the area, yet still belongs to the Autonomous
System.
Summary-LSAs are originated by area border routers. The precise
summary routes to advertise into an area are determined by examining
the routing table structure (see Section 11) in accordance with the
algorithm described below. Note that only intra-area routes are
advertised into the backbone, while both intra-area and inter-area
routes are advertised into the other areas.
To determine which routes to advertise into an attached Area A, each
routing table entry is processed as follows. Remember that each
routing table entry describes a set of equal-cost best paths to a
particular destination:
o Only Destination Types of network and AS boundary router
are advertised in summary-LSAs. If the routing table entry's
Destination Type is area border router, examine the next routing
table entry.
o AS external routes are never advertised in summary-LSAs.
If the routing table entry has Path-type of type 1 external or
type 2 external, examine the next routing table entry.
o Else, if the area associated with this set of paths is
the Area A itself, do not generate a summary-LSA for the
route.[17]
o Else, if the next hops associated with this set of paths
belong to Area A itself, do not generate a summary-LSA for the
route.[18] This is the logical equivalent of a Distance Vector
protocol's split horizon logic.
o Else, if the routing table cost equals or exceeds the
value LSInfinity, a summary-LSA cannot be generated for this
route.
o Else, if the destination of this route is an AS boundary
router, a summary-LSA should be originated if and only if the
routing table entry describes the preferred path to the AS
boundary router (see Step 3 of Section 16.4). If so, a Type 4
summary-LSA is originated for the destination, with Link State ID
equal to the AS boundary router's Router ID and metric equal to
the routing table entry's cost. Note: these LSAs should not be
generated if Area A has been configured as a stub area.
o Else, the Destination type is network. If this is an
inter-area route, generate a Type 3 summary-LSA for the
destination, with Link State ID equal to the network's address (if
necessary, the Link State ID can also have one or more of the
network's host bits set; see Appendix E for details) and metric
equal to the routing table cost.
o The one remaining case is an intra-area route to a network. This
means that the network is contained in one of the router's
directly attached areas. In general, this information must be
condensed before appearing in summary-LSAs. Remember that an area
has a configured list of address ranges, each range consisting of
an [address,mask] pair and a status indication of either Advertise
or DoNotAdvertise. At most a single Type 3 summary-LSA is
originated for each range. When the range's status indicates
Advertise, a Type 3 summary-LSA is generated with Link State ID
equal to the range's address (if necessary, the Link State ID can
also have one or more of the range's "host" bits set; see Appendix
E for details) and cost equal to the largest cost of any of the
component networks. When the range's status indicates
DoNotAdvertise, the Type 3 summary-LSA is suppressed and the
component networks remain hidden from other areas.
By default, if a network is not contained in any explicitly
configured address range, a Type 3 summary-LSA is generated with Link
State ID equal to the network's address (if necessary, the Link State
ID can also have one or more of the network's "host" bits set; see
Appendix E for details) and metric equal to the network's routing
table cost.
If an area is capable of carrying transit traffic (i.e., its
TransitCapability is set to TRUE), routing information concerning
backbone networks should not be condensed before being summarized
into the area. Nor should the advertisement of backbone networks
into transit areas be suppressed. In other words, the backbone's
configured ranges should be ignored when originating summary-LSAs
into transit areas.
If a router advertises a summary-LSA for a destination which then
becomes unreachable, the router must then flush the LSA from the
routing domain by setting its age to MaxAge and reflooding (see
Section 14.1). Also, if the destination is still reachable, yet can
no longer be advertised according to the above procedure (e.g., it is
now an inter-area route, when it used to be an intra-area route
associated with some non-backbone area; it would thus no longer be
advertisable to the backbone), the LSA should also be flushed from
the routing domain.
12.4.3.1. Originating summary-LSAs into stub areas
The algorithm in Section 12.4.3 is optional when Area A is an OSPF
stub area. Area border routers connecting to a stub area can
originate summary-LSAs into the area according to the Section
12.4.3's algorithm, or can choose to originate only a subset of the
summary-LSAs, possibly under configuration control. The fewer LSAs
originated, the smaller the stub area's link state database, further
reducing the demands on its routers' resources. However, omitting
LSAs may also lead to sub-optimal inter-area routing, although
routing will continue to function.
As specified in Section 12.4.3, Type 4 summary-LSAs (ASBR-summary-
LSAs) are never originated into stub areas.
In a stub area, instead of importing external routes each area border
router originates a "default summary-LSA" into the area. The Link
State ID for the default summary-LSA is set to DefaultDestination,
and the metric set to the (per-area) configurable parameter
StubDefaultCost. Note that StubDefaultCost need not be configured
identically in all of the stub area's area border routers.
12.4.3.2. Examples of summary-LSAs
Consider again the area configuration in Figure 6. Routers RT3, RT4,
RT7, RT10 and RT11 are all area border routers, and therefore are
originating summary-LSAs. Consider in particular Router RT4. Its
routing table was calculated as the example in Section 11.3. RT4
originates summary-LSAs into both the backbone and Area 1. Into the
backbone, Router RT4 originates separate LSAs for each of the
networks N1-N4. Into Area 1, Router RT4 originates separate LSAs for
networks N6-N8 and the AS boundary routers RT5,RT7. It also
condenses host routes Ia and Ib into a single summary-LSA. Finally,
the routes to networks N9,N10,N11 and Host H1 are advertised by a
single summary-LSA. This condensation was originally performed by
the router RT11.
These LSAs are illustrated graphically in Figures 7 and 8. Two of
the summary-LSAs originated by Router RT4 follow. The actual IP
addresses for the networks and routers in question have been assigned
in Figure 15.
; Summary-LSA for Network N1,
; originated by Router RT4 into the backbone
LS age = 0 ;always true on origination
Options = (E-bit) ;
LS type = 3 ;Type 3 summary-LSA
Link State ID = 192.1.2.0 ;N1's IP network number
Advertising Router = 192.1.1.4 ;RT4's ID
metric = 4
; Summary-LSA for AS boundary router RT7
; originated by Router RT4 into Area 1
LS age = 0 ;always true on origination
Options = (E-bit) ;
LS type = 4 ;Type 4 summary-LSA
Link State ID = Router RT7's ID
Advertising Router = 192.1.1.4 ;RT4's ID
metric = 14
12.4.4. AS-external-LSAs
AS-external-LSAs describe routes to destinations external to the
Autonomous System. Most AS-external-LSAs describe routes to specific
external destinations; in these cases the LSA's Link State ID is set
to the destination network's IP address (if necessary, the Link State
ID can also have one or more of the network's "host" bits set; see
Appendix E for details). However, a default route for the Autonomous
System can be described in an AS-external-LSA by setting the LSA's
Link State ID to DefaultDestination (0.0.0.0). AS-external-LSAs are
originated by AS boundary routers. An AS boundary router originates
a single AS-external-LSA for each external route that it has learned,
either through another routing protocol (such as BGP), or through
configuration information.
AS-external-LSAs are the only type of LSAs that are flooded
throughout the entire Autonomous System; all other types of LSAs are
specific to a single area. However, AS-external-LSAs are not flooded
into/throughout stub areas (see Section 3.6). This enables a
reduction in link state database size for routers internal to stub
areas.
The metric that is advertised for an external route can be one of two
types. Type 1 metrics are comparable to the link state metric. Type
2 metrics are assumed to be larger than the cost of any intra-AS
path.
If a router advertises an AS-external-LSA for a destination which
then becomes unreachable, the router must then flush the LSA from the
routing domain by setting its age to MaxAge and reflooding (see
Section 14.1).
12.4.4.1. Examples of AS-external-LSAs
Consider once again the AS pictured in Figure 6. There are two AS
boundary routers: RT5 and RT7. Router RT5 originates three AS-
external-LSAs, for networks N12-N14. Router RT7 originates two AS-
external-LSAs, for networks N12 and N15. Assume that RT7 has learned
its route to N12 via BGP, and that it wishes to advertise a Type 2
metric to the AS. RT7 would then originate the following LSA for
N12:
; AS-external-LSA for Network N12,
; originated by Router RT7
LS age = 0 ;always true on origination
Options = (E-bit) ;
LS type = 5 ;AS-external-LSA
Link State ID = N12's IP network number
Advertising Router = Router RT7's ID
bit E = 1 ;Type 2 metric
metric = 2
Forwarding address = 0.0.0.0
In the above example, the forwarding address field has been set to
0.0.0.0, indicating that packets for the external destination should
be forwarded to the advertising OSPF router (RT7). This is not always
desirable. Consider the example pictured in Figure 16. There are
three OSPF routers (RTA, RTB and RTC) connected to a common network.
Only one of these routers, RTA, is exchanging BGP information with
the non-OSPF router RTX. RTA must then originate AS- external-LSAs
for those destinations it has learned from RTX. By using the AS-
external-LSA's forwarding address field, RTA can specify that packets
for these destinations be forwarded directly to RTX. Without this
feature, Routers RTB and RTC would take an extra hop to get to these
destinations.
Note that when the forwarding address field is non-zero, it should
point to a router belonging to another Autonomous System.
A forwarding address can also be specified for the default route. For
example, in figure 16 RTA may want to specify that all externally-
destined packets should by default be forwarded to its BGP peer RTX.
The resulting AS-external-LSA is pictured below. Note that the Link
State ID is set to DefaultDestination.
; Default route, originated by Router RTA
; Packets forwarded through RTX
LS age = 0 ;always true on origination
Options = (E-bit) ;
LS type = 5 ;AS-external-LSA
Link State ID = DefaultDestination ; default route
Advertising Router = Router RTA's ID
bit E = 1 ;Type 2 metric
metric = 1
Forwarding address = RTX's IP address
In figure 16, suppose instead that both RTA and RTB exchange BGP
information with RTX. In this case, RTA and RTB would originate the
same set of AS-external-LSAs. These LSAs, if they specify the same
metric, would be functionally equivalent since they would specify the
same destination and forwarding address (RTX). This leads to a clear
duplication of effort. If only one of RTA or RTB originated the set
of AS-external-LSAs, the routing would remain the same, and the size
of the link state database would decrease. However, it must be
unambiguously defined as to which router originates the LSAs
(otherwise neither may, or the identity of the originator may
oscillate). The following rule is thereby established: if two
routers, both reachable from one another, originate functionally
equivalent AS-external-LSAs (i.e., same destination, cost and non-
zero forwarding address), then the LSA originated by the router
having the highest OSPF Router ID is used. The router having the
lower OSPF Router ID can then flush its LSA. Flushing an LSA is
discussed in Section 14.1.
13. The Flooding Procedure
Link State Update packets provide the mechanism for flooding LSAs. A
Link State Update packet may contain several distinct LSAs, and
floods each LSA one hop further from its point of origination. To
make the flooding procedure reliable, each LSA must be acknowledged
separately. Acknowledgments are transmitted in Link State
Acknowledgment packets. Many separate acknowledgments can also be
grouped together into a single packet.
The flooding procedure starts when a Link State Update packet has
been received. Many consistency checks have been made on the
received packet before being handed to the flooding procedure (see
Section 8.2). In particular, the Link State Update packet has been
associated with a particular neighbor, and a particular area. If the
neighbor is in a lesser state than Exchange, the packet should be
dropped without further processing.
+
|
+---+.....|.BGP
|RTA|-----|.....+---+
+---+ |-----|RTX|
| +---+
+---+ |
|RTB|-----|
+---+ |
|
+---+ |
|RTC|-----|
+---+ |
|
+
Figure 16: Forwarding address example
All types of LSAs, other than AS-external-LSAs, are associated with a
specific area. However, LSAs do not contain an area field. An LSA's
area must be deduced from the Link State Update packet header.
For each LSA contained in a Link State Update packet, the following
steps are taken:
(1) Validate the LSA's LS checksum. If the checksum turns out to be
invalid, discard the LSA and get the next one from the Link
State Update packet.
(2) Examine the LSA's LS type. If the LS type is unknown, discard
the LSA and get the next one from the Link State Update Packet.
This specification defines LS types 1-5 (see Section 4.3).
(3) Else if this is an AS-external-LSA (LS type = 5), and the area
has been configured as a stub area, discard the LSA and get the
next one from the Link State Update Packet. AS-external-LSAs
are not flooded into/throughout stub areas (see Section 3.6).
(4) Else if the LSA's LS age is equal to MaxAge, and there is
currently no instance of the LSA in the router's link state
database, then take the following actions:
(a) Acknowledge the receipt of the LSA by sending a Link State
Acknowledgment packet back to the sending neighbor (see
Section 13.5).
(b) Purge all outstanding requests for equal or previous
instances of the LSA 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 LSA in the link state
database. Otherwise, simply discard the LSA. In either
case, examine the next LSA (if any) listed in the Link State
Update packet.
(5) Otherwise, find the instance of this LSA that is currently
contained in the router's link state database. If there is no
database copy, or the received LSA is more recent than the
database copy (see Section 13.1 below for the determination of
which LSA is more recent) the following steps must be performed:
(a) If there is already a database copy, and if the database
copy was installed less than MinLSArrival seconds ago,
discard the new LSA (without acknowledging it) and examine
the next LSA (if any) listed in the Link State Update
packet.
(b) Otherwise immediately flood the new LSA out some subset of
the router's interfaces (see Section 13.3). In some cases
(e.g., the state of the receiving interface is DR and the
LSA was received from a router other than the Backup DR) the
LSA will be flooded back out the receiving interface. This
occurrence should be noted for later use by the
acknowledgment process (Section 13.5).
(c) Remove the current database copy from all neighbors' Link