RFC 2328
OSPF Version 2
Pages: 244
Internet Standard: 54
→ Errata
Obsoletes: 2178
Updated by: 5709 6549 6845 6860 7474 8042 9355 9454
Internet Standard: 54
→ Errata
Obsoletes: 2178
Updated by: 5709 6549 6845 6860 7474 8042 9355 9454
Part 5 of 8 – Pages 107 to 135
11. The Routing Table Structure The routing table data structure contains all the information necessary to forward an IP data packet toward its destination. Each routing table entry describes the collection of best paths to a particular destination. When forwarding an IP data packet, the routing table entry providing the best match for the packet's IP destination is located. The matching routing table entry then provides the next hop towards the packet's destination. OSPF also provides for the existence of a default route (Destination ID = DefaultDestination, Address Mask = 0x00000000). When the default route exists, it matches all IP destinations (although any other matching entry is a better match). Finding the routing table entry that best matches an IP destination is further described in Section 11.1. There is a single routing table in each router. Two sample routing tables are described in Sections 11.2 and 11.3. The building of the routing table is discussed in Section 16.
The rest of this section defines the fields found in a routing table
entry. The first set of fields describes the routing table entry's
destination.
Destination Type
Destination type is either "network" or "router". Only network
entries are actually used when forwarding IP data traffic.
Router routing table entries are used solely as intermediate
steps in the routing table build process.
A network is a range of IP addresses, to which IP data traffic
may be forwarded. This includes IP networks (class A, B, or C),
IP subnets, IP supernets and single IP hosts. The default route
also falls into this category.
Router entries are kept for area border routers and AS boundary
routers. Routing table entries for area border routers are used
when calculating the inter-area routes (see Section 16.2), and
when maintaining configured virtual links (see Section 15).
Routing table entries for AS boundary routers are used when
calculating the AS external routes (see Section 16.4).
Destination ID
The destination's identifier or name. This depends on the
Destination Type. For networks, the identifier is their
associated IP address. For routers, the identifier is the OSPF
Router ID.[9]
Address Mask
Only defined for networks. The network's IP address together
with its address mask defines a range of IP addresses. For IP
subnets, the address mask is referred to as the subnet mask.
For host routes, the mask is "all ones" (0xffffffff).
Optional Capabilities
When the destination is a router this field indicates the
optional OSPF capabilities supported by the destination router.
The only optional capability defined by this specification is
the ability to process AS-external-LSAs. For a further
discussion of OSPF's optional capabilities, see Section 4.5.
The set of paths to use for a destination may vary based on the OSPF
area to which the paths belong. This means that there may be
multiple routing table entries for the same destination, depending
on the values of the next field.
Area
This field indicates the area whose link state information has
led to the routing table entry's collection of paths. This is
called the entry's associated area. For sets of AS external
paths, this field is not defined. For destinations of type
"router", there may be separate sets of paths (and therefore
separate routing table entries) associated with each of several
areas. For example, this will happen when two area border
routers share multiple areas in common. For destinations of
type "network", only the set of paths associated with the best
area (the one providing the preferred route) is kept.
The rest of the routing table entry describes the set of paths to
the destination. The following fields pertain to the set of paths
as a whole. In other words, each one of the paths contained in a
routing table entry is of the same path-type and cost (see below).
Path-type
There are four possible types of paths used to route traffic to
the destination, listed here in decreasing order of preference:
intra-area, inter-area, type 1 external or type 2 external.
Intra-area paths indicate destinations belonging to one of the
router's attached areas. Inter-area paths are paths to
destinations in other OSPF areas. These are discovered through
the examination of received summary-LSAs. AS external paths are
paths to destinations external to the AS. These are detected
through the examination of received AS-external-LSAs.
Cost
The link state cost of the path to the destination. For all
paths except type 2 external paths this describes the entire
path's cost. For Type 2 external paths, this field describes
the cost of the portion of the path internal to the AS. This
cost is calculated as the sum of the costs of the path's
constituent links.
Type 2 cost
Only valid for type 2 external paths. For these paths, this
field indicates the cost of the path's external portion. This
cost has been advertised by an AS boundary router, and is the
most significant part of the total path cost. For example, a
type 2 external path with type 2 cost of 5 is always preferred
over a path with type 2 cost of 10, regardless of the cost of
the two paths' internal components.
Link State Origin
Valid only for intra-area paths, this field indicates the LSA
(router-LSA or network-LSA) that directly references the
destination. For example, if the destination is a transit
network, this is the transit network's network-LSA. If the
destination is a stub network, this is the router-LSA for the
attached router. The LSA is discovered during the shortest-path
tree calculation (see Section 16.1). Multiple LSAs may
reference the destination, however a tie-breaking scheme always
reduces the choice to a single LSA. The Link State Origin field
is not used by the OSPF protocol, but it is used by the routing
table calculation in OSPF's Multicast routing extensions
(MOSPF).
When multiple paths of equal path-type and cost exist to a
destination (called elsewhere "equal-cost" paths), they are stored
in a single routing table entry. Each one of the "equal-cost" paths
is distinguished by the following fields:
Next hop
The outgoing router interface to use when forwarding traffic to
the destination. On broadcast, Point-to-MultiPoint and NBMA
networks, the next hop also includes the IP address of the next
router (if any) in the path towards the destination.
Advertising router
Valid only for inter-area and AS external paths. This field
indicates the Router ID of the router advertising the summary-
LSA or AS-external-LSA that led to this path.
11.1. Routing table lookup When an IP data packet is received, an OSPF router finds the routing table entry that best matches the packet's destination. This routing table entry then provides the outgoing interface and next hop router to use in forwarding the packet. This section describes the process of finding the best matching routing table entry. Before the lookup begins, "discard" routing table entries should be inserted into the routing table for each of the router's active area address ranges (see Section 3.5). (An area range is considered "active" if the range contains one or more networks reachable by intra-area paths.) The destination of a "discard" entry is the set of addresses described by its associated active area address range, and the path type of each "discard" entry is set to "inter-area".[10] Several routing table entries may match the destination address. In this case, the "best match" is the routing table entry that provides the most specific (longest) match. Another way of saying this is to choose the entry that specifies the narrowest range of IP addresses.[11] For example, the entry for the address/mask pair of (128.185.1.0, 0xffffff00) is more specific than an entry for the pair (128.185.0.0, 0xffff0000). The default route is the least specific match, since it matches all destinations. (Note that for any single routing table entry, multiple paths may be possible. In these cases, the calculations in Sections 16.1, 16.2, and 16.4 always yield the paths having the most preferential path-type, as described in Section 11). If there is no matching routing table entry, or the best match routing table entry is one of the above "discard" routing table entries, then the packet's IP destination is considered unreachable. Instead of being forwarded, the packet should then be discarded and an ICMP destination unreachable message should be returned to the packet's source. 11.2. Sample routing table, without areas Consider the Autonomous System pictured in Figure 2. No OSPF areas have been configured. A single metric is shown per
outbound interface. The calculation of Router RT6's routing
table proceeds as described in Section 2.2. The resulting
routing table is shown in Table 12. Destination types are
abbreviated: Network as "N", Router as "R".
There are no instances of multiple equal-cost shortest paths in
this example. Also, since there are no areas, there are no
inter-area paths.
Routers RT5 and RT7 are AS boundary routers. Intra-area routes
have been calculated to Routers RT5 and RT7. This allows
external routes to be calculated to the destinations advertised
by RT5 and RT7 (i.e., Networks N12, N13, N14 and N15). It is
assumed all AS-external-LSAs originated by RT5 and RT7 are
advertising type 1 external metrics. This results in type 1
external paths being calculated to destinations N12-N15.
11.3. Sample routing table, with areas
Consider the previous example, this time split into OSPF areas.
An OSPF area configuration is pictured in Figure 6. Router
RT4's routing table will be described for this area
configuration. Router RT4 has a connection to Area 1 and a
backbone connection. This causes Router RT4 to view the AS as
the concatenation of the two graphs shown in Figures 7 and 8.
The resulting routing table is displayed in Table 13.
Again, Routers RT5 and RT7 are AS boundary routers. Routers
RT3, RT4, RT7, RT10 and RT11 are area border routers. Note that
there are two routing entries for the area border router RT3,
since it has two areas in common with RT4 (Area 1 and the
backbone).
Backbone paths have been calculated to all area border routers.
These are used when determining the inter-area routes. Note
that all of the inter-area routes are associated with the
backbone; this is always the case when the calculating router is
itself an area border router. Routing information is condensed
at area boundaries. In this example, we assume that Area 3 has
been defined so that networks N9-N11 and the host route to H1
Type Dest Area Path Type Cost Next Adv.
Hop(s) Router(s)
____________________________________________________________
N N1 0 intra-area 10 RT3 *
N N2 0 intra-area 10 RT3 *
N N3 0 intra-area 7 RT3 *
N N4 0 intra-area 8 RT3 *
N Ib 0 intra-area 7 * *
N Ia 0 intra-area 12 RT10 *
N N6 0 intra-area 8 RT10 *
N N7 0 intra-area 12 RT10 *
N N8 0 intra-area 10 RT10 *
N N9 0 intra-area 11 RT10 *
N N10 0 intra-area 13 RT10 *
N N11 0 intra-area 14 RT10 *
N H1 0 intra-area 21 RT10 *
R RT5 0 intra-area 6 RT5 *
R RT7 0 intra-area 8 RT10 *
____________________________________________________________
N N12 * type 1 ext. 10 RT10 RT7
N N13 * type 1 ext. 14 RT5 RT5
N N14 * type 1 ext. 14 RT5 RT5
N N15 * type 1 ext. 17 RT10 RT7
Table 12: The routing table for Router RT6
(no configured areas).
are all condensed to a single route when advertised into the
backbone (by Router RT11). Note that the cost of this route is
the maximum of the set of costs to its individual components.
There is a virtual link configured between Routers RT10 and
RT11. Without this configured virtual link, RT11 would be
unable to advertise a route for networks N9-N11 and Host H1 into
the backbone, and there would not be an entry for these networks
in Router RT4's routing table.
In this example there are two equal-cost paths to Network N12.
However, they both use the same next hop (Router RT5).
Router RT4's routing table would improve (i.e., some of the
paths in the routing table would become shorter) if an
additional virtual link were configured between Router RT4 and
Router RT3. The new virtual link would itself be associated
with the first entry for area border router RT3 in Table 13 (an
intra-area path through Area 1). This would yield a cost of 1
for the virtual link. The routing table entries changes that
would be caused by the addition of this virtual link are shown
Type Dest Area Path Type Cost Next Adv.
Hops(s) Router(s)
__________________________________________________________________
N N1 1 intra-area 4 RT1 *
N N2 1 intra-area 4 RT2 *
N N3 1 intra-area 1 * *
N N4 1 intra-area 3 RT3 *
R RT3 1 intra-area 1 * *
__________________________________________________________________
N Ib 0 intra-area 22 RT5 *
N Ia 0 intra-area 27 RT5 *
R RT3 0 intra-area 21 RT5 *
R RT5 0 intra-area 8 * *
R RT7 0 intra-area 14 RT5 *
R RT10 0 intra-area 22 RT5 *
R RT11 0 intra-area 25 RT5 *
__________________________________________________________________
N N6 0 inter-area 15 RT5 RT7
N N7 0 inter-area 19 RT5 RT7
N N8 0 inter-area 18 RT5 RT7
N N9-N11,H1 0 inter-area 36 RT5 RT11
__________________________________________________________________
N N12 * type 1 ext. 16 RT5 RT5,RT7
N N13 * type 1 ext. 16 RT5 RT5
N N14 * type 1 ext. 16 RT5 RT5
N N15 * type 1 ext. 23 RT5 RT7
Table 13: Router RT4's routing table
in the presence of areas.
in Table 14.
12. Link State Advertisements (LSAs)
Each router in the Autonomous System originates one or more link
state advertisements (LSAs). This memo defines five distinct types
of LSAs, which are described in Section 4.3. The collection of LSAs
forms the link-state database. Each separate type of LSA has a
separate function. Router-LSAs and network-LSAs describe how an
area's routers and networks are interconnected. Summary-LSAs
provide a way of condensing an area's routing information. AS-
external-LSAs provide a way of transparently advertising
externally-derived routing information throughout the Autonomous
System.
Each LSA begins with a standard 20-byte header. This LSA header is
discussed below.
Type Dest Area Path Type Cost Next Adv.
Hop(s) Router(s)
________________________________________________________________
N Ib 0 intra-area 16 RT3 *
N Ia 0 intra-area 21 RT3 *
R RT3 0 intra-area 1 * *
R RT10 0 intra-area 16 RT3 *
R RT11 0 intra-area 19 RT3 *
________________________________________________________________
N N9-N11,H1 0 inter-area 30 RT3 RT11
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
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).
16.
Actually, for Type 3 summary-LSAs (LS type = 3) and AS-
external-LSAs (LS type = 5), the Link State ID may
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.
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.
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 RFC 1349 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.
.................................... . 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 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 (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
(page 135 continued on part 6)