Done is generated. Otherwise, it should send a new Database
Description to the slave.
Slave
Sets the sequence number to the sequence number appearing in the
received packet. The slave must send a Database Description in
reply. If the received packet has the more bit (M) set to 0, and
the packet to be sent by the slave will have the M-bit set to 0
also, the neighbor event Exchange Done is generated. Note that the
slave always generates this event before the master.
10.7 Receiving Link State Request Packets
This section explains the detailed processing of received Link State
Request packets. Received Link State Request Packets specify a list of
link state advertisements that the neighbor wishes to receive. Link
state Request Packets should be accepted when the neighbor is in states
Exchange, Loading, or Full. In all other states Link State Request
Packets should be ignored.
Each link state advertisement specified in the Link State Request packet
should be located in the router's database, and copied into Link State
Update packets for transmission to the neighbor. These link state
advertisements should NOT be placed on the Link state retransmission
list for the neighbor. If a link state advertisement cannot be found in
the database, something has gone wrong with the synchronization
procedure, and neighbor event BadLSReq should be generated.
10.8 Sending Database Description Packets
This section describes how Database Description Packets are sent to a
neighbor. The router's optional OSPF capabilities (see Section 4.5) are
transmitted to the neighbor in the Options field of the Database
Description packet. The router should maintain the same set of optional
capabilities throughout the Database Exchange and flooding procedures.
If for some reason the router's optional capabilities change, the
Database Exchange procedure should be restarted by reverting to neighbor
state ExStart. There are currently two optional capabilities defined.
The T-bit should be set if and only if the router is capable of
calculating separate routes for each IP TOS. The E-bit should be set if
and only if the attached network belongs to a non-stub area. The rest
of the Options field should be set to zero.
The sending of Database Description packets depends on the neighbor's
state. In state ExStart the router sends empty Database Description
packets, with the initialize (I), more (M) and master (MS) bits set.
These packets are retransmitted every RxmtInterval seconds.
In state Exchange the Database Description Packets actually contain
summaries of the link state information contained in the router's
database. Each link state advertisement in the area's topological
database (at the time the neighbor transitions into Exchange state) is
listed in the neighbor Database summary list. When a new Database
Description Packet is to be sent, the packet's sequence number is
incremented, and the (new) top of the Database summary list is described
by the packet. Items are removed from the Database summary list when
the previous packet is acknowledged.
In state Exchange, the determination of when to send a packet depends on
whether the router is master or slave:
Master
Packets are sent when either a) the slave acknowledges the previous
packet by echoing the sequence number or b) RxmtInterval seconds
elapse without an acknowledgment, in which case the previous packet
is retransmitted.
Slave
Packets are sent only in response to packets received from the
master. If the packet received from the master is new, a new packet
is sent, otherwise the previous packet is resent.
In states Loading and Full the slave must resend its last packet in
response to duplicate packets received from the master. For this reason
the slave must wait RouterDeadInterval seconds before freeing the last
packet. Reception of a packet from the master after this interval will
generate a Seq Number Mismatch neighbor event.
10.9 Sending Link State Request Packets
In neighbor states Exchange or Loading, the Link state request list
contains a list of those link state advertisements that need to be
obtained from the neighbor. To request these advertisements, a router
sends the neighbor the beginning of the Link state request list,
packaged in a Link State Request packet.
When the neighbor responds to these requests with the proper Link State
Update packet(s), the Link state request list is truncated and a new
Link State Request packet is sent. This process continues until the
link state request list becomes empty. Unsatisfied Link State Requests
are retransmitted at intervals of RxmtInterval. There should be at most
one Link State Request packet outstanding at any one time.
When the Link state request list becomes empty, and the neighbor state
is Loading (i.e., a complete sequence of Database Description packets
has been received from the neighbor), the Loading Done neighbor event is
generated.
10.10 An Example
Figure 14 shows an example of an adjacency forming. Routers RT1 and RT2
are both connected to a broadcast network. It is assumed that RT2 is
the Designated Router for the network, and that RT2 has a higher Router
ID that router RT1.
The neighbor state changes realized by each router are listed on the
sides of the figure.
At the beginning of Figure 14, router RT1's interface to the network
becomes operational. It begins sending hellos, although it doesn't know
the identity of the Designated Router or of any other neighboring
routers. Router RT2 hears this hello (moving the neighbor to Init
state), and in its next hello indicates that it is itself the Designated
Router and that it has heard hellos from RT1. This in turn causes RT1
to go to state ExStart, as it starts to bring up the adjacency.
RT1 begins by asserting itself as the master. When it sees that RT2 is
indeed the master (because of RT2's higher Router ID), RT1 transitions
to slave state and adopts its neighbor's sequence number. Database
Description packets are then exchanged, with polls coming from the
master (RT2) and responses from the slave (RT1). This sequence of
Database Description Packets ends when both the poll and associated
response has the M-bit off.
In this example, it is assumed that RT2 has a completely up to date
database. In that case, RT2 goes immediately into Full state. RT1 will
go into Full state after updating the necessary parts of its database.
This is done by sending Link State Request Packets, and receiving Link
State Update Packets in response. Note that, while RT1 has waited until
a complete set of Database Description Packets has been received (from
RT2) before sending any Link State Request Packets, this need not be the
case. RT1 could have interleaved the sending of Link State Request
Packets with the reception of Database Description Packets.
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.
________________________________________
(Figure not included in text version.)
Figure 14: An adjacency bring-up example
________________________________________
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). 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
The destination can be one of three types. Only the first type,
Network, is actually used when forwarding IP data traffic. The
other destinations are used solely as intermediate steps in the
routing table build process.
Network
A range of IP addresses, to which IP data traffic may be
forwarded. This includes IP networks (class A, B, or C), IP
subnets, and single IP hosts. The default route also falls in
this category.
Area border router
Routers that are connected to multiple OSPF areas. Such routers
originate summary link advertisements. These routing table
entries are used when calculating the inter-area routes (see
Section 16.2). These routing table entries may also be
associated with configured virtual links.
AS boundary router
Routers that originate AS external link advertisements. These
routing table entries 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's type. For networks, the identifier is their
associated IP address. For all other types, 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 (either an area border router or an
AS boundary router) this field indicates the optional OSPF
capabilities supported by the destination router. The two optional
capabilities currently defined by this specification are the ability
to route based on IP TOS and the ability to process AS external
advertisements. 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 IP Type of
Service and 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 two fields.
Type of Service
There can be a separate set of routes for each IP Type of Service.
The encoding of TOS in OSPF link state advertisements is described
in Section 12.3.
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 "area border
router", there may be separate sets of paths (and therefore separate
routing table entries) associated with each of several areas. This
will happen when two area border routers share multiple areas in
common. For all other destination types, only the set of paths
associated with the best area (the one providing the shortest 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 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
link advertisements. AS external paths are paths to destinations
external to the AS. These are detected through the examination of
received AS external link advertisements.
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, an external
type 2 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 link state
advertisement (router links or network links) that directly
references the destination. For example, if the destination is a
transit network, this is the transit network's network links
advertisement. If the destination is a stub network, this is the
router links advertisement for the attached router. The
advertisement is discovered during the shortest-path tree
calculation (see Section 16.1). Multiple advertisements may
reference the destination, however a tie-breaking scheme always
reduces the choice to a single advertisement.
This field is for informational purposes only. The advertisement
could be used as a root for an SPF calculation when building a
reverse path forwarding tree. This is beyond the scope of this
specification.
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 multi-access networks, the next hop also includes
the IP address of the next router (if any) in the path towards the
destination. This next router will always be one of the adjacent
neighbors.
Advertising router
Valid only for inter-area and AS external paths. This field
indicates the Router ID of the router advertising the summary link
or AS external link 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. The process consists of a
number of steps, wherein the collection of routing table entries is
progressively pruned. In the end, the single routing table entry
remaining is the called best match.
Note that the steps described below may fail to produce a best match
routing table entry (i.e., all existing routing table entries are pruned
for some reason or another). In this case, the packet's IP destination
is considered unreachable. Instead of being forwarded, the packet should
be dropped and an ICMP destination unreachable message should be
returned to the packet's source.
(1) Select the complete set of "matching" routing table entries from the
routing table. Each routing table entry describes a (set of)
path(s) to a range of IP addresses. If the data packet's IP
destination falls into an entry's range of IP addresses, the routing
table entry is called a match. (It is quite likely that multiple
entries will match the data packet. For example, a default route
will match all packets.)
(2) Suppose that the packet's IP destination falls into one of the
router's configured area address ranges (see Section 3.5), and that
the particular area address range is active. This means that there
are one or more reachable (by intra-area paths) networks contained
in the area address range. The packet's IP destination is then
required to belong to one of these constituent networks. For this
reason, only matching routing table entries with path-type of
intra-area are considered (all others are pruned). If no such
matching entries exist, the destination is unreachable (see above).
Otherwise, skip to step 4.
(3) Reduce the set of matching entries to those having the most
preferential path-type (see Section 11). OSPF has a four level
hierarchy of paths. Intra-area paths are the most preferred,
followed in order by inter-area, Type 1 external and Type 2 external
paths.
(4) Select the remaining routing table entry that provides the longest
(most specific) match. Another way of saying this is to choose the
remaining entry that specifies the narrowest range of IP
addresses.[10] 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.
(5) At this point, there may still be multiple routing table entries
remaining. Each routing entry will specify the same range of IP
addresses, but a different IP Type of Service. Select the routing
table entry whose TOS value matches the TOS found in the packet
header. If there is no routing table entry for this TOS, select the
routing table entry for TOS 0. In other words, packets requesting
TOS X are routed along the TOS 0 path if a TOS X path does not
exist.
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,
indicating that routes will not vary based on TOS. The calculation
router RT6's routing table proceeds as described in Section 2.1. The
resulting routing table is shown in Table 12. Destination types are
abbreviated: Network as "N", area border router as "BR" and AS boundary
router as "ASBR".
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
advertisements 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 (in this case having identical paths) for router RT7, in
its dual capacities as an area border router and an AS boundary router.
Note also 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 (BR).
These are used when determining the inter-area routes. Note that all of
Type Dest Area Path Type Cost Next Hop(s) Adv. 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 *
ASBR RT5 0 intra-area 6 RT5 *
ASBR RT7 0 intra-area 8 RT10 *
__________________________________________________________________________
N N12 * type 1 external 10 RT10 RT7
N N13 * type 1 external 14 RT5 RT5
N N14 * type 1 external 14 RT5 RT5
N N15 * type 1 external 17 RT10 RT7
Table 12: The routing table for Router RT6 (no configured areas).
the inter-area routes are associated with the backbone; this is always
the case when the 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 are all condensed to a single route when advertised to the
backbone (by router RT11). Note that the cost of this route is the
minimum 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 in Table
14.
12. Link State Advertisements
Each router in the Autonomous System originates one or more link state
advertisements. There are five distinct types of link state
advertisements, which are described in Section 4.3. The collection of
link state advertisements forms the link state or topological database.
Each separate type of advertisement has a separate function. Router
links and network links advertisements describe how an area's routers
and networks are interconnected. Summary link advertisements provide a
way of condensing an area's routing information. AS external
advertisements provide a way of transparently advertising externally-
derived routing information throughout the Autonomous System.
Each link state advertisement begins with a standard 20-byte header.
This link state header is discussed below.
Type Dest Area Path Type Cost Next Hop(s) Adv. 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 *
BR RT3 1 intra-area 1 * *
_______________________________________________________________________________
N Ib 0 intra-area 22 RT5 *
N Ia 0 intra-area 27 RT5 *
BR RT3 0 intra-area 21 RT5 *
BR RT7 0 intra-area 14 RT5 *
BR RT10 0 intra-area 22 RT5 *
BR RT11 0 intra-area 25 RT5 *
ASBR RT5 0 intra-area 8 * *
ASBR RT7 0 intra-area 14 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 26 RT5 RT11
_______________________________________________________________________________
N N12 * type 1 external 16 RT5 RT5,RT7
N N13 * type 1 external 16 RT5 RT5
N N14 * type 1 external 16 RT5 RT5
N N15 * type 1 external 23 RT5 RT7
Table 13: Router RT4's routing table in the presence of areas.
Type Dest Area Path Type Cost Next Hop(s) Adv. Router(s)
__________________________________________________________________________
N Ib 0 intra-area 16 RT3 *
N Ia 0 intra-area 21 RT3 *
BR RT3 0 intra-area 1 * *
BR RT10 0 intra-area 16 RT3 *
BR RT11 0 intra-area 19 RT3 *
__________________________________________________________________________
N N9-N11,H1 0 inter-area 20 RT3 RT11
Table 14: Changes resulting from an additional virtual link.
12.1 The Link State Header
The link state header contains the LS type, Link State ID and
Advertising Router fields. The combination of these three fields
uniquely identifies the link state advertisement.
There may be several instances of an advertisement present in the
Autonomous System, all at the same time. It must then be determined
which instance is more recent. This determination is made be examining
the LS sequence, LS checksum and LS age fields. These fields are also
contained in the 20-byte link state header.
Several of the OSPF packet types list link state advertisements. When
the instance is not important, an advertisement 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 link state header
follows.
12.1.1 LS age
This field is the age of the link state advertisement in seconds. It
should be processed as an unsigned 16-bit integer. It is set to 0 when
the link state advertisement is originated. It must be incremented by
InfTransDelay on every hop of the flooding procedure. Link state
advertisements are also aged as they are held in each router's database.
The age of a link state advertisement is never incremented past MaxAge.
Advertisements having age MaxAge are not used in the routing table
calculation. When an advertisement's age first reaches MaxAge, it is
reflooded. A link state advertisement of age MaxAge is finally flushed
from the database when it is no longer contained on any neighbor Link
state retransmission lists. This indicates that it has been
acknowledged by all adjacent neighbors. For more information on the
aging of link state advertisements, consult Section 14.
Ages are examined when a router receives two instances of a link state
advertisement, both having identical sequence numbers and checksums. An
instance of age MaxAge is then always accepted as most recent; this
allows old advertisements 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.[11] See Section 13.1
for more details.
12.1.2 Options
The options field in the link state header indicates which optional
capabilities are associated with the advertisement. OSPF's optional
capabilities are described in Section 4.5. There are currently two
optional capabilities defined; they are represented by the T-bit and E-
bit found in the options field. The rest of the options field should be
set to zero.
The E-bit represents OSPF's external routing capability. This bit
should be set in all advertisements associated with the backbone, and
all advertisements associated with non-stub areas (see Section 3.6). It
should also be set in all AS external advertisements. It should be
reset in all router links, network links and summary link advertisements
associated with a stub area. For all link state advertisements, the
setting of the E-bit is for informational purposes only; it does not
affect the routing table calculation.
The T-bit represents OSPF's TOS routing capability. This bit should be
set in a router links advertisement if and only if the router is capable
of calculating separate routes for each IP TOS (see Section 2.4). The
T-bit should always be set in network links advertisements. It should
be set in summary link and AS external link advertisements if and only
if the advertisement describes paths for all TOS values, instead of just
the TOS 0 path. Note that, with the T-bit set, there may still be only
a single metric in the advertisement (the TOS 0 metric). This would
mean that paths for non-zero TOS exist, but are equivalent to the TOS 0
path. A link state advertisement's T-bit is examined when calculating
the routing table's non-zero TOS paths (see Section 16.9).
12.1.3 LS type
The LS type field dictates the format and function of the link state
advertisement. Advertisements of different types have different names
(e.g., router links or network links). All advertisement types, except
the AS external link advertisements (LS type = 5), are flooded
throughout a single area only. AS external link advertisements are
flooded throughout the entire Autonomous System, excluding stub areas
(see Section 3.6). Each separate advertisement type is briefly
described below in Table 15.
LS Type Advertisement description
__________________________________________________
1 These are the router links
advertisements. They describe the
LS Type Advertisement description
__________________________________________________
collected states of the router's
interfaces. For more information,
consult Section 12.4.1.
__________________________________________________
2 These are the network links
advertisements. 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 link
advertisements. They describe
inter-area routes, and enable the
condensation of routing information at
area borders. Originated by area border
routers, the Type 3 advertisements
describe routes to networks while the
Type 4 advertisements describe routes to
AS boundary routers.
__________________________________________________
5 These are the AS external link
advertisements. 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 link
advertisement.
Table 15: OSPF link state advertisements.
12.1.4 Link State ID
This field identifies the piece of the routing domain that is being
described by the advertisement. Depending on the advertisement's LS
type, the Link State ID takes on the values listed in Table 16.
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 advertisement's Link State ID.
When the link state advertisement is describing a network, the Link
State ID is either the network's IP address (as in type 3 summary link
advertisements and in AS external link advertisements) or the network's
IP address is easily derivable from the Link State ID (note that masking
a network links advertisement's Link State ID with the network's subnet
mask yields the network's IP address). When the link state
advertisement is describing a router, the Link State ID is always the
described router's OSPF Router ID.
When an AS external advertisement (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 advertisement's
originator. For router links advertisements, this field is identical to
the Link State ID field. Network link advertisements are originated by
the network's Designated Router. Summary link advertisements are
originated by area border routers. Finally, AS external link
advertisements 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 link state advertisements. The space of
sequence numbers is linearly ordered. The larger the sequence number
(when compared as signed 32-bit integers) the more recent the
advertisement. 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. A router uses this sequence number the first time it
originates any link state advertisement. Afterwards, the
advertisement's sequence number is incremented each time the router
originates a new instance of the advertisement. When an attempt is made
to increment the sequence number past the maximum value of of N - 1
(0x7fffffff), the current instance of the advertisement must first be
flushed from the routing domain. This is done by prematurely aging the
advertisement (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 -N + 1 (0x80000001).
The router may be forced to promote the sequence number of one of its
advertisements when a more recent instance of the advertisement is
unexpectedly received during the flooding process. This should be a
rare event. This may indicate that an out-of-date advertisement,
originated by the router itself before its last restart/reload, still
exists in the Autonomous System. For more information see Section 13.4.
,uh "12.1.7 LS checksum"
This field is the checksum of the complete contents of the
advertisement, excepting the age field. The age field is excepted so
that an advertisement'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 C of [RFC994]. The link state
header also contains the length of the advertisement in bytes;
subtracting the size of the age field (two bytes) yields the amount of
data to checksum.
The checksum is used to detect data corruption of an advertisement.
This corruption can occur while an advertisement 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 a link state advertisement 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
advertisement are the same, the LS checksum field is examined. If there
is a difference, the instance with the larger checksum is considered to
be most recent.[12] 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. The link state database has been referred to elsewhere in the
text as the topological database. All routers belonging to the same
area have identical topological 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 topological 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 links advertisements, network
links advertisements, and summary link advertisements (all listed in the
area data structure). In addition, external routes (AS external
advertisements) 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 advertisement's LS
type, Link State ID and Advertising Router.[13] There will be a single
instance (the most up-to-date) of each link state advertisement in the
database. The database lookup function is invoked during the link state
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 link state
advertisement, and if so, with what LS sequence number.
A link state advertisement 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). A link state
advertisement 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 advertisements (Section 12.4) or c) the advertisement
ages out and is flushed from the routing domain (Section 14). Whenever
a link state advertisement 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
All OSPF link state advertisements (with the exception of network links
advertisements) specify metrics. In router links advertisements, the
metrics indicate the costs of the described interfaces. In summary link
and AS external link advertisements, the metric indicates the cost of
the described path. In all of these advertisements, a separate metric
can be specified for each IP TOS. TOS is encoded in an OSPF link state
advertisement as the following mapping of the Delay (D), Throughput (T)
and Reliability (R) flags found in the IP packet header's TOS field (see
[RFC791]).
OSPF encoding D T R
_________________________
0 0 0 0
4 0 0 1
8 0 1 0
12 0 1 1
16 1 0 0
20 1 0 1
24 1 1 0
28 1 1 1
Table 17: Representing TOS in OSPF.
Each OSPF link state advertisement must specify the TOS 0 metric. Other
TOS metrics, if they appear, must appear in order of increasing TOS
encoding. For example, the TOS 8 (high throughput) metric must always
appear before the TOS 16 (low delay) metric when both are specified. If
a metric for some non-zero TOS is not specified, its cost defaults to
the cost for TOS 0, unless the T-bit is reset in the advertisement's
options field (see Section 12.1.2 for more details).
Note that if more TOS types are defined in a future IP architecture,
OSPF's TOS encoding can be extended in a straightforward manner.
12.4 Originating link state advertisements
A router may originate many types of link state advertisements. A
router originates a router links advertisement for each area to which it
belongs. If the router is also the Designated Router for any of its
attached networks, it will originate a network links advertisement for
that network.
Area border routers originate a single summary links advertisement for
each known inter-area destination. AS boundary routers originate a
single AS external links advertisement 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 link state
advertisements 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 link state advertisements into the backbone (one
router links, and one summary link for each of the networks N1-N4).
Router RT4 will also originate 8 distinct link state advertisements into
Area 1 (one router links and seven summary link advertisements as
pictured in Figure 7). If RT4 has been selected as Designated Router
for network N3, it will also originate a network links advertisement for
N3 into Area 1.
In this same figure, router RT5 will be originating 3 distinct AS
external link advertisements (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 external advertisements for networks
N12-N14 will not be flooded into area 3 (see Section 3.6). Instead,
router RT11 would originate a default summary link advertisement 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 a link state advertisement is originated, its
LS sequence number is incremented, its LS age is set to 0, its LS
checksum is calculated, and the advertisement is added to the link state
database and flooded out the appropriate interfaces. See Section 13.2
for details concerning the installation of the advertisement into the
link state database. See Section 13.3 for details concerning the
flooding of newly originated advertisements.
The eight events that cause a new instance of a link state advertisement
to be originated are:
(1) The LS refresh timer firing. There is a LS refresh timer for each
link state advertisement that the router has originated. The LS
refresh timer is an interval timer, with length LSRefreshTimer. The
LS refresh timer guarantees periodic originations regardless of any
other events that cause new instances. This periodic updating of
link state advertisements adds robustness to the link state
algorithm. Link state advertisements 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 a link state advertisement changes,
a new advertisement is originated. Two instances of the same link state
advertisement may not be originated within the time period
MinLSInterval. This may require that the generation of the next
instance to be delayed by up to MinLSInterval. The following changes
may cause a router to originate a new instance of an advertisement.
These changes should cause new originations only if the contents of the
new advertisement 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 links
advertisement.
(3) An attached network's Designated Router changes. A new router links
advertisement should be originated. Also, if the router itself is
now the Designated Router, a new network links advertisement should
be produced.
(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 links advertisement. Also, if the router is itself the
Designated Router for the attached network, a new network links
advertisement should be produced.
The next three 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 links
advertisement (for this route) to be originated in each attached
area (this includes 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 links
advertisement (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 link advertisements into the newly attached area
for all pertinent intra-area and inter-area routes in its routing
table. See Section 12.4.3 for more details.
The last event concerns AS boundary routers only.
(8) An external route gained through direct experience with an external
routing protocol (like EGP) changes. This will cause the AS
boundary router to originate a new instance of an external links
advertisement.
The construction of each type of the link state advertisement is
explained below. In general, these sections describe the contents of
the advertisement body (i.e., the part coming after the 20-byte
advertisement header). For information concerning the building of the
link state advertisement header, see Section 12.1.
12.4.1 Router links
A router originates a router links advertisement for each area that it
belongs to. Such an advertisement describes the collected states of the
router's links to the area. The advertisement is flooded throughout the
particular area, and no further.
The format of a router links advertisement is shown in Appendix A
(Section A.4.2). The first 20 bytes of the advertisement consist of the
generic link state header that was discussed in Section 12.1. Router
links advertisements have LS type = 1. The router indicates whether it
is willing to calculate separate routes for each IP TOS by setting (or
resetting) the T-bit of the link state advertisement's Options field.
A router also indicates whether it is an area border router, or an AS
boundary router, by setting the appropriate bits in its router links
advertisements. This enables paths to those types of routers to be
saved in the routing table, for later processing of summary link
advertisements and AS external link advertisements.
The router links advertisement then describes the router's working
connections (links) to the area. Each link is typed according to the
_________________________________________
(Figure not included in text version.)
Figure 15: Area 1 with IP addresses shown
Figure 16: Forwarding address example
_________________________________________
kind of attached network. Each link is also labelled with its Link ID.
This 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 link Neighbor Router ID
2 Link to transit network Interface address of Designated Router
3 Link to stub network IP network number
4 Virtual link Neighbor Router ID
Table 18: Link descriptions in the router links advertisement.
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 routers
and transit networks, this field specifies the IP interface address of
the associated router interface (this is needed by the routing table
calculation, see Section 16.3). For links to stub networks, this field
specifies the network's IP address mask.
Finally, the cost of using the link for output (possibly specifying a
different cost for each type of service) is specified. The output cost
of a link is configurable. It must always be non-zero.
To further describe the process of building the list of link records,
suppose a router wishes to build router links advertisement for an 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 advertisement, and the next interface should be
examined.
o Else, if the state of the interface is Down, no links are added.
o Else, if the state of the interface is Point-to-Point, then add
links according to the following:
- If the neighboring router is fully adjacent, add a Type 1 link
(point-to-point) if this is an interface to a point-to-point
network, or add a type 4 link (virtual link) if this is a
virtual link. The Link ID should be set to the Router ID of the
neighboring router, and the Link Data should specify the
interface IP address.
- If this is a numbered point-to-point network (i.e, not a virtual
link and not an unnumbered point-to-point network) and the
neighboring router's IP address is known, add a Type 3 link
(stub network) whose Link ID is the neighbor's IP address, whose
Link Data is the mask 0xffffffff indicating a host route, and
whose cost is the interface's configured output cost.
o Else 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
serial line. The Link ID should be set to the IP interface address,
the Link Data set to the mask 0xffffffff (indicating a host route),