single area. The area leading to the routing table entry is
selected as follows: The area providing the shortest path is
always chosen; if more than one area provides paths with the
same minimum cost, the area with the largest OSPF Area ID
(when considered as an unsigned 32-bit integer) is chosen.
Note that whenever an AS boundary router's routing table
entry is added/modified, the Options found in the associated
router links advertisement is copied into the routing table
entry's Optional capabilities field.
If the newly added vertex is a transit network, the routing
table entry for the network is located. The entry's
Destination ID is the IP network number, which can be
obtained by masking the Vertex ID (Link State ID) with its
associated subnet mask (found in the body of the associated
network links advertisement). If the routing table entry
already exists (i.e., there is already an intra-area route
to the destination installed in the routing table), multiple
vertices have mapped to the same IP network. For example,
this can occur when a new Designated Router is being
established. In this case, the current routing table entry
should be overwritten if and only if the newly found path is
just as short and the current routing table entry's Link
State Origin has a smaller Link State ID than the newly
added vertex' link state advertisement.
If there is no routing table entry for the network (the
usual case), a routing table entry for the IP network should
be added. The routing table entry's Link State Origin
should be set to the newly added vertex' link state
advertisement.
(5) Iterate the algorithm by returning to Step 2.
The stub networks are added to the tree in the procedure's
second stage. In this stage, all router vertices are again
examined. Those that have been determined to be unreachable in
the above first phase are discarded. For each reachable router
vertex (call it V), the associated router links advertisement is
found in the link state database. Each stub network link
appearing in the advertisement is then examined, and the
following steps are executed:
(1) Calculate the distance D of stub network from the root. D
is equal to the distance from the root to the router vertex
(calculated in stage 1), plus the stub network link's
advertised cost. Compare this distance to the current best
cost to the stub network. This is done by looking up the
stub network's current routing table entry. If the
calculated distance D is larger, go on to examine the next
stub network link in the advertisement.
(2) If this step is reached, the stub network's routing table
entry must be updated. Calculate the set of next hops that
would result from using the stub network link. This
calculation is shown in Section 16.1.1; input to this
calculation is the destination (the stub network) and the
parent vertex (the router vertex). If the distance D is the
same as the current routing table cost, simply add this set
of next hops to the routing table entry's list of next hops.
In this case, the routing table already has a Link State
Origin. If this Link State Origin is a router links
advertisement whose Link State ID is smaller than V's Router
ID, reset the Link State Origin to V's router links
advertisement.
Otherwise D is smaller than the routing table cost.
Overwrite the current routing table entry by setting the
routing table entry's cost to D, and by setting the entry's
list of next hops to the newly calculated set. Set the
routing table entry's Link State Origin to V's router links
advertisement. Then go on to examine the next stub network
link.
For all routing table entries added/modified in the second
stage, the associated area will be set to Area A and the path
type will be set to intra-area. When the list of reachable
router links is exhausted, the second stage is completed. At
this time, all intra-area routes associated with Area A have
been determined.
The specification does not require that the above two stage
method be used to calculate the shortest path tree. However, if
another algorithm is used, an identical tree must be produced.
For this reason, it is important to note that links between
transit vertices must be bidirectional in ordered to be included
in the above tree. It should also be mentioned that more
efficient algorithms exist for calculating the tree; for
example, the incremental SPF algorithm described in [BBN].
16.1.1. The next hop calculation
This section explains how to calculate the current set of
next hops to use for a destination. Each next hop consists
of the outgoing interface to use in forwarding packets to
the destination together with the next hop router (if any).
The next hop calculation is invoked each time a shorter path
to the destination is discovered. This can happen in either
stage of the shortest-path tree calculation (see Section
16.1). In stage 1 of the shortest-path tree calculation a
shorter path is found as the destination is added to the
candidate list, or when the destination's entry on the
candidate list is modified (Step 2d of Stage 1). In stage 2
a shorter path is discovered each time the destination's
routing table entry is modified (Step 2 of Stage 2).
The set of next hops to use for the destination may be
recalculated several times during the shortest-path tree
calculation, as shorter and shorter paths are discovered.
In the end, the destination's routing table entry will
always reflect the next hops resulting from the absolute
shortest path(s).
Input to the next hop calculation is a) the destination and
b) its parent in the current shortest path between the root
(the calculating router) and the destination. The parent is
always a transit vertex (i.e., always a router or a transit
network).
If there is at least one intervening router in the current
shortest path between the destination and the root, the
destination simply inherits the set of next hops from the
parent. Otherwise, there are two cases. In the first case,
the parent vertex is the root (the calculating router
itself). This means that the destination is either a
directly connected network or directly connected router.
The next hop in this case is simply the OSPF interface
connecting to the network/router; no next hop router is
required. If the connecting OSPF interface in this case is a
virtual link, the setting of the next hop should be deferred
until the calculation in Section 16.3.
In the second case, the parent vertex is a network that
directly connects the calculating router to the destination
router. The list of next hops is then determined by
examining the destination's router links advertisement. For
each link in the advertisement that points back to the
parent network, the link's Link Data field provides the IP
address of a next hop router. The outgoing interface to use
can then be derived from the next hop IP address (or it can
be inherited from the parent network).
16.2. Calculating the inter-area routes
The inter-area routes are calculated by examining summary link
advertisements. If the router has active attachments to
multiple areas, only backbone summary link advertisements are
examined. Routers attached to a single area examine that area's
summary links. In either case, the summary links examined below
are all part of a single area's link state database (call it
Area A).
Summary link advertisements are originated by the area border
routers. Each summary link advertisement in Area A is
considered in turn. Remember that the destination described by
a summary link advertisement is either a network (Type 3 summary
link advertisements) or an AS boundary router (Type 4 summary
link advertisements). For each summary link advertisement:
(1) If the cost specified by the advertisement is LSInfinity, or
if the advertisement's LS age is equal to MaxAge, then
examine the the next advertisement.
(2) If the advertisement was originated by the calculating
router itself, examine the next advertisement.
(3) If the collection of destinations described by the summary
link advertisement falls into one of the router's configured
area address ranges (see Section 3.5) and the particular
area address range is active, the summary link advertisement
should be ignored. Active means that there are one or more
reachable (by intra-area paths) networks contained in the
area range. In this case, all addresses in the area range
are assumed to be either reachable via intra-area paths, or
else to be unreachable by any other means.
(4) Else, call the destination described by the advertisement N
(for Type 3 summary links, N's address is obtained by
masking the advertisement's Link State ID with the
network/subnet mask contained in the body of the
advertisement), and the area border originating the
advertisement BR. Look up the routing table entry for BR
having Area A as its associated area. If no such entry
exists for router BR (i.e., BR is unreachable in Area A), do
nothing with this advertisement and consider the next in the
list. Else, this advertisement describes an inter-area path
to destination N, whose cost is the distance to BR plus the
cost specified in the advertisement. Call the cost of this
inter-area path IAC.
(5) Next, look up the routing table entry for the destination N.
(The entry's Destination Type is either Network or AS
boundary router.) If no entry exists for N or if the
entry's path type is "type 1 external" or "type 2 external",
then install the inter-area path to N, with associated area
Area A, cost IAC, next hop equal to the list of next hops to
router BR, and Advertising router equal to BR.
(6) Else, if the paths present in the table are intra-area
paths, do nothing with the advertisement (intra-area paths
are always preferred).
(7) Else, the paths present in the routing table are also
inter-area paths. Install the new path through BR if it is
cheaper, overriding the paths in the routing table.
Otherwise, if the new path is the same cost, add it to the
list of paths that appear in the routing table entry.
16.3. Examining transit areas' summary links
This step is only performed by area border routers attached to
one or more transit areas. Transit areas are those areas
supporting one or more virtual links; their TransitCapability
parameter has been set to TRUE in Step 2 of the Dijkstra
algorithm (see Section 16.1). They are the only non-backbone
areas that can carry data traffic that neither originates nor
terminates in the area itself.
The purpose of the calculation below is to examine the transit
areas to see whether they provide any better (shorter) paths
than the paths previously calculated in Sections 16.1 and 16.2.
Any paths found that are better than or equal to previously
discovered paths are installed in the routing table.
The calculation proceeds as follows. All the transit areas'
summary link advertisements are examined in turn. Each such
summary link advertisement describes a route through a transit
area Area A to a Network N (N's address is obtained by masking
the advertisement's Link State ID with the network/subnet mask
contained in the body of the advertisement) or in the case of a
Type 4 summary link advertisement, to an AS boundary router N.
Suppose also that the summary link advertisement was originated
by an area border router BR.
(1) If the cost advertised by the summary link advertisement is
LSInfinity, or if the advertisement's LS age is equal to
MaxAge, then examine the next advertisement.
(2) If the summary link advertisement was originated by the
calculating router itself, examine the next advertisement.
(3) Look up the routing table entry for N. If it does not exist,
or if the route type is other than intra-area or inter-area,
or if the area associated with the routing table entry is
not the backbone area, then examine the next advertisement.
In other words, this calculation only updates backbone
intra-area routes found in Section 16.1 and inter-area
routes found in Section 16.2.
(4) Look up the routing table entry for the advertising router
BR associated with the Area A. If it is unreachable, examine
the next advertisement. Otherwise, the cost to destination N
is the sum of the cost in BR's Area A routing table entry
and the cost advertised in the advertisement. Call this cost
IAC.
(5) If this cost is less than the cost occurring in N's routing
table entry, overwrite N's list of next hops with those used
for BR, and set N's routing table cost to IAC. Else, if IAC
is the same as N's current cost, add BR's list of next hops
to N's list of next hops. In any case, the area associated
with N's routing table entry must remain the backbone area,
and the path type (either intra-area or inter-area) must
also remain the same.
It is important to note that the above calculation never makes
unreachable destinations reachable, but instead just potentially
finds better paths to already reachable destinations. Also,
unlike Section 16.3 of [RFC1247], the above calculation
installs any better cost found into the routing table entry,
from which it may be readvertised in summary link advertisements
to other areas.
As an example of the calculation, consider the Autonomous System
pictured in Figure 17. There is a single non-backbone area
(Area 1) that physically divides the backbone into two separate
pieces. To maintain connectivity of the backbone, a virtual link
has been configured between routers RT1 and RT4. On the right
side of the figure, Network N1 belongs to the backbone. The
dotted lines indicate that there is a much shorter intra-area
........................
. Area 1 (transit) . +
. . |
. +---+1 1+---+100 |
. |RT2|----------|RT4|=========|
. 1/+---+********* +---+ |
. /******* . |
. 1/*Virtual . |
1+---+/* Link . Net|work
=======|RT1|* . | N1
+---+\ . |
. \ . |
. \ . |
. 1\+---+1 1+---+20 |
. |RT3|----------|RT5|=========|
. +---+ +---+ |
. . |
........................ +
Figure 17: Routing through transit areas
backbone path between router RT5 and Network N1 (cost 20) than
there is between Router RT4 and Network N1 (cost 100). Both
Router RT4 and Router RT5 will inject summary link
advertisements for Network N1 into Area 1.
After the shortest-path tree has been calculated for the
backbone in Section 16.1, Router RT1 (left end of the virtual
link) will have calculated a path through Router RT4 for all
data traffic destined for Network N1. However, since Router RT5
is so much closer to Network N1, all routers internal to Area 1
(e.g., Routers RT2 and RT3) will forward their Network N1
traffic towards Router RT5, instead of RT4. And indeed, after
examining Area 1's summary link advertisements by the above
calculation, Router RT1 will also forward Network N1 traffic
towards RT5. Note that in this example the virtual link enables
Network N1 traffic to be forwarded through the transit area Area
1, but the actual path the data traffic takes does not follow
the virtual link. In other words, virtual links allow transit
traffic to be forwarded through an area, but do not dictate the
precise path that the traffic will take.
16.4. Calculating AS external routes
AS external routes are calculated by examining AS external link
advertisements. Each of the AS external link advertisements is
considered in turn. Most AS external link advertisements
describe routes to specific IP destinations. An AS external
link advertisement can also describe a default route for the
Autonomous System (Destination ID = DefaultDestination,
network/subnet mask = 0x00000000). For each AS external link
advertisement:
(1) If the cost specified by the advertisement is LSInfinity, or
if the advertisement's LS age is equal to MaxAge, then
examine the next advertisement.
(2) If the advertisement was originated by the calculating
router itself, examine the next advertisement.
(3) Call the destination described by the advertisement N. N's
address is obtained by masking the advertisement's Link
State ID with the network/subnet mask contained in the body
of the advertisement. Look up the routing table entry for
the AS boundary router (ASBR) that originated the
advertisement. If no entry exists for router ASBR (i.e.,
ASBR is unreachable), do nothing with this advertisement and
consider the next in the list.
Else, this advertisement describes an AS external path to
destination N. Examine the forwarding address specified in
the AS external link advertisement. This indicates the IP
address to which packets for the destination should be
forwarded. If the forwarding address is set to 0.0.0.0,
packets should be sent to the ASBR itself. Otherwise, look
up the forwarding address in the routing table.[23] An
intra-area or inter-area path must exist to the forwarding
address. If no such path exists, do nothing with the
advertisement and consider the next in the list.
Call the routing table distance to the forwarding address X
(when the forwarding address is set to 0.0.0.0, this is the
distance to the ASBR itself), and the cost specified in the
advertisement Y. X is in terms of the link state metric,
and Y is a type 1 or 2 external metric.
(4) Next, look up the routing table entry for the destination N.
If no entry exists for N, install the AS external path to N,
with next hop equal to the list of next hops to the
forwarding address, and advertising router equal to ASBR.
If the external metric type is 1, then the path-type is set
to type 1 external and the cost is equal to X+Y. If the
external metric type is 2, the path-type is set to type 2
external, the link state component of the route's cost is X,
and the type 2 cost is Y.
(5) Else, if the paths present in the table are not type 1 or
type 2 external paths, do nothing (AS external paths have
the lowest priority).
(6) Otherwise, compare the cost of this new AS external path to
the ones present in the table. Type 1 external paths are
always shorter than type 2 external paths. Type 1 external
paths are compared by looking at the sum of the distance to
the forwarding address and the advertised type 1 metric
(X+Y). Type 2 external paths are compared by looking at the
advertised type 2 metrics, and then if necessary, the
distance to the forwarding addresses.
If the new path is shorter, it replaces the present paths in
the routing table entry. If the new path is the same cost,
it is added to the routing table entry's list of paths.
16.5. Incremental updates -- summary link advertisements
When a new summary link advertisement is received, it is not
necessary to recalculate the entire routing table. Call the
destination described by the summary link advertisement N (N's
address is obtained by masking the advertisement's Link State ID
with the network/subnet mask contained in the body of the
advertisement), and let Area A be the area to which the
advertisement belongs. There are then two separate cases:
Case 1: Area A is the backbone and/or the router is not an area
border router.
In this case, the following calculations must be performed.
First, if there is presently an inter-area route to the
destination N, N's routing table entry is invalidated,
saving the entry's values for later comparisons. Then the
calculation in Section 16.2 is run again for the single
destination N. In this calculation, all of Area A's summary
link advertisements that describe a route to N are examined.
In addition, if the router is an area border router attached
to one or more transit areas, the calculation in Section
16.3 must be run again for the single destination. If the
results of these calculations have changed the cost/path to
an AS boundary router (as would be the case for a Type 4
summary link advertisement) or to any forwarding addresses,
all AS external link advertisements will have to be
reexamined by rerunning the calculation in Section 16.4.
Otherwise, if N is now newly unreachable, the calculation in
Section 16.4 must be rerun for the single destination N, in
case an alternate external route to N exists.
Case 2: Area A is a transit area and the router is an area
border router.
In this case, the following calculations must be performed.
First, if N's routing table entry presently contains one or
more inter-area paths that utilize the transit area Area A,
these paths should be removed. If this removes all paths
from the routing table entry, the entry should be
invalidated. The entry's old values should be saved for
later comparisons. Next the calculation in Section 16.3 must
be run again for the single destination N. If the results of
this calculation have caused the cost to N to increase, the
complete routing table calculation must be rerun starting
with the Dijkstra algorithm specified in Section 16.1.
Otherwise, if the cost/path to an AS boundary router (as
would be the case for a Type 4 summary link advertisement)
or to any forwarding addresses has changed, all AS external
link advertisements will have to be reexamined by rerunning
the calculation in Section 16.4. Otherwise, if N is now
newly unreachable, the calculation in Section 16.4 must be
rerun for the single destination N, in case an alternate
external route to N exists.
16.6. Incremental updates -- AS external link advertisements
When a new AS external link advertisement is received, it is not
necessary to recalculate the entire routing table. Call the
destination described by the AS external link advertisement N.
N's address is obtained by masking the advertisement's Link
State ID with the network/subnet mask contained in the body of
the advertisement. If there is already an intra-area or inter-
area route to the destination, no recalculation is necessary
(internal routes take precedence).
Otherwise, the procedure in Section 16.4 will have to be
performed, but only for those AS external link advertisements
whose destination is N. Before this procedure is performed, the
present routing table entry for N should be invalidated.
16.7. Events generated as a result of routing table changes
Changes to routing table entries sometimes cause the OSPF area
border routers to take additional actions. These routers need
to act on the following routing table changes:
o The cost or path type of a routing table entry has changed.
If the destination described by this entry is a Network or
AS boundary router, and this is not simply a change of AS
external routes, new summary link advertisements may have to
be generated (potentially one for each attached area,
including the backbone). See Section 12.4.3 for more
information. If a previously advertised entry has been
deleted, or is no longer advertisable to a particular area,
the advertisement must be flushed from the routing domain by
setting its LS age to MaxAge and reflooding (see Section
14.1).
o A routing table entry associated with a configured virtual
link has changed. The destination of such a routing table
entry is an area border router. The change indicates a
modification to the virtual link's cost or viability.
If the entry indicates that the area border router is newly
reachable (via TOS 0), the corresponding virtual link is now
operational. An InterfaceUp event should be generated for
the virtual link, which will cause a virtual adjacency to
begin to form (see Section 10.3). At this time the virtual
link's IP interface address and the virtual neighbor's
Neighbor IP address are also calculated.
If the entry indicates that the area border router is no
longer reachable (via TOS 0), the virtual link and its
associated adjacency should be destroyed. This means an
InterfaceDown event should be generated for the associated
virtual link.
If the cost of the entry has changed, and there is a fully
established virtual adjacency, a new router links
advertisement for the backbone must be originated. This in
turn may cause further routing table changes.
16.8. Equal-cost multipath
The OSPF protocol maintains multiple equal-cost routes to all
destinations. This can be seen in the steps used above to
calculate the routing table, and in the definition of the
routing table structure.
Each one of the multiple routes will be of the same type
(intra-area, inter-area, type 1 external or type 2 external),
cost, and will have the same associated area. However, each
route specifies a separate next hop and Advertising router.
There is no requirement that a router running OSPF keep track of
all possible equal-cost routes to a destination. An
implementation may choose to keep only a fixed number of routes
to any given destination. This does not affect any of the
algorithms presented in this specification.
16.9. Building the non-zero-TOS portion of the routing table
The OSPF protocol can calculate a different set of routes for
each IP TOS (see Section 2.4). Support for TOS-based routing is
optional. TOS-capable and non-TOS-capable routers can be mixed
in an OSPF routing domain. Routers not supporting TOS calculate
only the TOS 0 route to each destination. These routes are then
used to forward all data traffic, regardless of the TOS
indications in the data packet's IP header. A router that does
not support TOS indicates this fact to the other OSPF routers by
clearing the T-bit in the Options field of its router links
advertisement.
The above sections detailing the routing table calculations
handle the TOS 0 case only. In general, for routers supporting
TOS-based routing, each piece of the routing table calculation
must be rerun separately for the non-zero TOS values. When
calculating routes for TOS X, only TOS X metrics can be used.
Any link state advertisement may specify a separate cost for
each TOS (a cost for TOS 0 must always be specified). The
encoding of TOS in OSPF link state advertisements is described
in Section 12.3.
An advertisement can specify that it is restricted to TOS 0
(i.e., non-zero TOS is not handled) by clearing the T-bit in the
link state advertisement's Option field. Such advertisements
are not used when calculating routes for non-zero TOS. For this
reason, it is possible that a destination is unreachable for
some non-zero TOS. In this case, the TOS 0 path is used when
forwarding packets (see Section 11.1).
The following lists the modifications needed when running the
routing table calculation for a non-zero TOS value (called TOS
X). In general, routers and advertisements that do not support
TOS are omitted from the calculation.
Calculating the shortest-path tree (Section 16.1).
Routers that do not support TOS-based routing should be
omitted from the shortest-path tree calculation. These
routers are identified as those having the T-bit reset in
the Options field of their router links advertisements.
Such routers should never be added to the Dijktra
algorithm's candidate list, nor should their router links
advertisements be examined when adding the stub networks to
the tree. In particular, if the T-bit is reset in the
calculating router's own router links advertisement, it does
not run the shortest-path tree calculation for non-zero TOS
values.
Calculating the inter-area routes (Section 16.2).
Inter-area paths are the concatenation of a path to an area
border router with a summary link. When calculating TOS X
routes, both path components must also specify TOS X. In
other words, only TOS X paths to the area border router are
examined, and the area border router must be advertising a
TOS X route to the destination. Note that this means that
summary link advertisements having the T-bit reset in their
Options field are not considered.
Examining transit areas' summary links (Section 16.3).
This calculation again considers the concatenation of a path
to an area border router with a summary link. As with
inter-area routes, only TOS X paths to the area border
router are examined, and the area border router must be
advertising a TOS X route to the destination.
Calculating AS external routes (Section 16.4).
This calculation considers the concatenation of a path to a
forwarding address with an AS external link. Only TOS X
paths to the forwarding address are examined, and the AS
boundary router must be advertising a TOS X route to the
destination. Note that this means that AS external link
advertisements having the T-bit reset in their Options field
are not considered.
In addition, the advertising AS boundary router must also be
reachable for its advertisements to be considered (see
Section 16.4). However, if the advertising router and the
forwarding address are not one in the same, the advertising
router need only be reachable via TOS 0.
Footnotes
[1]The graph's vertices represent either routers, transit networks,
or stub networks. Since routers may belong to multiple areas, it is
not possible to color the graph's vertices.
[2]It is possible for all of a router's interfaces to be unnumbered
point-to-point links. In this case, an IP address must be assigned
to the router. This address will then be advertised in the router's
router links advertisement as a host route.
[3]Note that in these cases both interfaces, the non-virtual and the
virtual, would have the same IP address.
[4]Note that no host route is generated for, and no IP packets can
be addressed to, interfaces to unnumbered point-to-point networks.
This is regardless of such an interface's state.
[5]It is instructive to see what happens when the Designated Router
for the network crashes. Call the Designated Router for the network
RT1, and the Backup Designated Router RT2. If Router RT1 crashes
(or maybe its interface to the network dies), the other routers on
the network will detect RT1's absence within RouterDeadInterval
seconds. All routers may not detect this at precisely the same
time; the routers that detect RT1's absence before RT2 does will,
for a time, select RT2 to be both Designated Router and Backup
Designated Router. When RT2 detects that RT1 is gone it will move
itself to Designated Router. At this time, the remaining router
having highest Router Priority will be selected as Backup Designated
Router.
[6]On point-to-point networks, the lower level protocols indicate
whether the neighbor is up and running. Likewise, existence of the
neighbor on virtual links is indicated by the routing table
calculation. However, in both these cases, the Hello Protocol is
still used. This ensures that communication between the neighbors
is bidirectional, and that each of the neighbors has a functioning
routing protocol layer.
[7]When the identity of the Designated Router is changing, it may be
quite common for a neighbor in this state to send the router a
Database Description packet; this means that there is some momentary
disagreement on the Designated Router's identity.
[8]Note that it is possible for a router to resynchronize any of its
fully established adjacencies by setting the adjacency's state back
to ExStart. This will cause the other end of the adjacency to
process a SeqNumberMismatch event, and therefore to also go back to
ExStart state.
[9]The address space of IP networks and the address space of OSPF
Router IDs may overlap. That is, a network may have an IP address
which is identical (when considered as a 32-bit number) to some
router's Router ID.
[10]It is assumed that, for two different address ranges matching
the destination, one range is more specific than the other. Non-
contiguous subnet masks can be configured to violate this
assumption. Such subnet mask configurations cannot be handled by the
OSPF protocol.
[11]MaxAgeDiff is an architectural constant. It indicates the
maximum dispersion of ages, in seconds, that can occur for a single
link state instance as it is flooded throughout the routing domain.
If two advertisements differ by more than this, they are assumed to
be different instances of the same advertisement. This can occur
when a router restarts and loses track of the advertisement's
previous LS sequence number. See Section 13.4 for more details.
[12]When two advertisements have different LS checksums, they are
assumed to be separate instances. This can occur when a router
restarts, and loses track of the advertisement's previous LS
sequence number. In the case where the two advertisements have the
same LS sequence number, it is not possible to determine which link
state is actually newer. If the wrong advertisement is accepted as
newer, the originating router will originate another instance. See
Section 13.4 for further details.
[13]There is one instance where a lookup must be done based on
partial information. This is during the routing table calculation,
when a network links advertisement must be found based solely on its
Link State ID. The lookup in this case is still well defined, since
no two network links advertisements can have the same Link State ID.
[14]This clause covers the case: Inter-area routes are not
summarized to the backbone. This is because inter-area routes are
always associated with the backbone area.
[15]This clause is only invoked when Area A is a Transit area
supporting one or more virtual links. For example, in the area
configuration of Figure 6, Router RT11 need only originate a single
summary link having the (collapsed) destination N9-N11,H1 into its
connected Transit area Area 2, since all of its other eligible
routes have next hops belonging to Area 2 (and as such only need be
advertised by other area border routers; in this case, Routers RT10
and RT7).
[16]By keeping more information in the routing table, it is possible
for an implementation to recalculate the shortest path tree only for
a single area. In fact, there are incremental algorithms that allow
an implementation to recalculate only a portion of a single area's
shortest path tree [BBN]. However, these algorithms are beyond the
scope of this specification.
[17]This is how the Link state request list is emptied, which
eventually causes the neighbor state to transition to Full. See
Section 10.9 for more details.
[18]It should be a relatively rare occurrence for an advertisement's
LS age to reach MaxAge in this fashion. Usually, the advertisement
will be replaced by a more recent instance before it ages out.
[19]Only the TOS 0 routes are important here because all OSPF
protocol packets are sent with TOS = 0. See Appendix A.
[20]It may be the case that paths to certain destinations do not
vary based on TOS. For these destinations, the routing calculation
need not be repeated for each TOS value. In addition, there need
only be a single routing table entry for these destinations (instead
of a separate entry for each TOS value).
[21]Strictly speaking, because of equal-cost multipath, the
algorithm does not create a tree. We continue to use the "tree"
terminology because that is what occurs most often in the existing
literature.
[22]Note that the presence of any link back to V is sufficient; it
need not be the matching half of the link under consideration from V
to W. This is enough to ensure that, before data traffic flows
between a pair of neighboring routers, their link state databases
will be synchronized.
[23]When the forwarding address is non-zero, it should point to a
router belonging to another Autonomous System. See Section 12.4.5
for more details.
References
[BBN] McQuillan, J., I. Richer and E. Rosen, "ARPANET
Routing Algorithm Improvements", BBN Technical
Report 3803, April 1978.
[DEC] Digital Equipment Corporation, "Information
processing systems -- Data communications --
Intermediate System to Intermediate System Intra-
Domain Routing Protocol", October 1987.
[McQuillan] McQuillan, J. et.al., "The New Routing Algorithm for
the Arpanet", IEEE Transactions on Communications,
May 1980.
[Perlman] Perlman, R., "Fault-Tolerant Broadcast of Routing
Information", Computer Networks, December 1983.
[RFC791] Postel, J., "Internet Protocol", STD 5, RFC791,
USC/Information Sciences Institute, September 1981.
[RFC905] McKenzie, A., "ISO Transport Protocol specification
ISO DP 8073", RFC905, ISO, April 1984.
[RFC1112] Deering, S., "Host extensions for IP multicasting",
STD 5, RFC1112, Stanford University, May 1988.
[RFC1213] McCloghrie, K., and M. Rose, "Management Information
Base for network management of TCP/IP-based
internets: MIB-II", STD 17, RFC1213, Hughes LAN
Systems, Performance Systems International, March
1991.
[RFC1247] Moy, J., "OSPF Version 2", RFC1247, Proteon, Inc.,
July 1991.
[RFC1519] Fuller, V., T. Li, J. Yu, and K. Varadhan,
"Classless Inter-Domain Routing (CIDR): an Address
Assignment and Aggregation Strategy", RFC1519,
BARRNet, cisco, MERIT, OARnet, September 1993.
[RFC1340] Reynolds, J., and J. Postel, "Assigned Numbers", STD
2, RFC1340, USC/Information Sciences Institute,
July 1992.
[RFC1349] Almquist, P., "Type of Service in the Internet
Protocol Suite", RFC1349, July 1992.
[RS-85-153] Leiner, B., et.al., "The DARPA Internet Protocol
Suite", DDN Protocol Handbook, April 1985.
A. OSPF data formats
This appendix describes the format of OSPF protocol packets and OSPF
link state advertisements. The OSPF protocol runs directly over the
IP network layer. Before any data formats are described, the
details of the OSPF encapsulation are explained.
Next the OSPF Options field is described. This field describes
various capabilities that may or may not be supported by pieces of
the OSPF routing domain. The OSPF Options field is contained in OSPF
Hello packets, Database Description packets and in OSPF link state
advertisements.
OSPF packet formats are detailed in Section A.3. A description of
OSPF link state advertisements appears in Section A.4.
A.1 Encapsulation of OSPF packets
OSPF runs directly over the Internet Protocol's network layer. OSPF
packets are therefore encapsulated solely by IP and local data-link
headers.
OSPF does not define a way to fragment its protocol packets, and
depends on IP fragmentation when transmitting packets larger than
the network MTU. The OSPF packet types that are likely to be large
(Database Description Packets, Link State Request, Link State
Update, and Link State Acknowledgment packets) can usually be split
into several separate protocol packets, without loss of
functionality. This is recommended; IP fragmentation should be
avoided whenever possible. Using this reasoning, an attempt should
be made to limit the sizes of packets sent over virtual links to 576
bytes. However, if necessary, the length of OSPF packets can be up
to 65,535 bytes (including the IP header).
The other important features of OSPF's IP encapsulation are:
o Use of IP multicast. Some OSPF messages are multicast, when
sent over multi-access networks. Two distinct IP multicast
addresses are used. Packets sent to these multicast addresses
should never be forwarded; they are meant to travel a single hop
only. To ensure that these packets will not travel multiple
hops, their IP TTL must be set to 1.
AllSPFRouters
This multicast address has been assigned the value
224.0.0.5. All routers running OSPF should be prepared to
receive packets sent to this address. Hello packets are
always sent to this destination. Also, certain OSPF
protocol packets are sent to this address during the
flooding procedure.
AllDRouters
This multicast address has been assigned the value
224.0.0.6. Both the Designated Router and Backup Designated
Router must be prepared to receive packets destined to this
address. Certain OSPF protocol packets are sent to this
address during the flooding procedure.
o OSPF is IP protocol number 89. This number has been registered
with the Network Information Center. IP protocol number
assignments are documented in [RFC1340].
o Routing protocol packets are sent with IP TOS of 0. The OSPF
protocol supports TOS-based routing. Routes to any particular
destination may vary based on TOS. However, all OSPF routing
protocol packets are sent using the normal service TOS value of
binary 0000 defined in [RFC1349].
o Routing protocol packets are sent with IP precedence set to
Internetwork Control. OSPF protocol packets should be given
precedence over regular IP data traffic, in both sending and
receiving. Setting the IP precedence field in the IP header to
Internetwork Control [RFC791] may help implement this
objective.
A.2 The Options field
The OSPF Options field is present in OSPF Hello packets, Database
Description packets and all link state advertisements. The Options
field enables OSPF routers to support (or not support) optional
capabilities, and to communicate their capability level to other
OSPF routers. Through this mechanism routers of differing
capabilities can be mixed within an OSPF routing domain.
When used in Hello packets, the Options field allows a router to
reject a neighbor because of a capability mismatch. Alternatively,
when capabilities are exchanged in Database Description packets a
router can choose not to forward certain link state advertisements
to a neighbor because of its reduced functionality. Lastly, listing
capabilities in link state advertisements allows routers to route
traffic around reduced functionality routers, by excluding them from
parts of the routing table calculation.
Two capabilities are currently defined. For each capability, the
effect of the capability's appearance (or lack of appearance) in
Hello packets, Database Description packets and link state
advertisements is specified below. For example, the
ExternalRoutingCapability (below called the E-bit) has meaning only
in OSPF Hello Packets. Routers should reset (i.e. clear) the
unassigned part of the capability field when sending Hello packets
or Database Description packets and when originating link state
advertisements.
Additional capabilities may be assigned in the future. Routers
encountering unrecognized capabilities in received Hello Packets,
Database Description packets or link state advertisements should
ignore the capability and process the packet/advertisement normally.
+-+-+-+-+-+-+-+-+
| | | | | | |E|T|
+-+-+-+-+-+-+-+-+
The Options field
T-bit
This describes the router's TOS capability. If the T-bit is
reset, then the router supports only a single TOS (TOS 0). Such
a router is also said to be incapable of TOS-routing, and
elsewhere in this document referred to as a TOS-0-only router.
The absence of the T-bit in a router links advertisement causes
the router to be skipped when building a non-zero TOS shortest-
path tree (see Section 16.9). In other words, routers incapable
of TOS routing will be avoided as much as possible when
forwarding data traffic requesting a non-zero TOS. The absence
of the T-bit in a summary link advertisement or an AS external
link advertisement indicates that the advertisement is
describing a TOS 0 route only (and not routes for non-zero TOS).
E-bit
This bit reflects the associated area's
ExternalRoutingCapability. AS external link advertisements are
not flooded into/through OSPF stub areas (see Section 3.6). The
E-bit ensures that all members of a stub area agree on that
area's configuration. The E-bit is meaningful only in OSPF
Hello packets. When the E-bit is reset in the Hello packet sent
out a particular interface, it means that the router will
neither send nor receive AS external link state advertisements
on that interface (in other words, the interface connects to a
stub area). Two routers will not become neighbors unless they
agree on the state of the E-bit.
A.3 OSPF Packet Formats
There are five distinct OSPF packet types. All OSPF packet types
begin with a standard 24 byte header. This header is described
first. Each packet type is then described in a succeeding section.
In these sections each packet's division into fields is displayed,
and then the field definitions are enumerated.
All OSPF packet types (other than the OSPF Hello packets) deal with
lists of link state advertisements. For example, Link State Update
packets implement the flooding of advertisements throughout the OSPF
routing domain. Because of this, OSPF protocol packets cannot be
parsed unless the format of link state advertisements is also
understood. The format of Link state advertisements is described in
Section A.4.
The receive processing of OSPF packets is detailed in Section 8.2.
The sending of OSPF packets is explained in Section 8.1.
A.3.1 The OSPF packet header
Every OSPF packet starts with a common 24 byte header. This header
contains all the necessary information to determine whether the
packet should be accepted for further processing. This
determination is described in Section 8.2 of the specification.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # | Type | Packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Area ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Checksum | AuType |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Version #
The OSPF version number. This specification documents version 2
of the protocol.
Type
The OSPF packet types are as follows. The format of each of
these packet types is described in a succeeding section.
Type Description
________________________________
1 Hello
2 Database Description
3 Link State Request
4 Link State Update
5 Link State Acknowledgment
Packet length
The length of the protocol packet in bytes. This length
includes the standard OSPF header.
Router ID
The Router ID of the packet's source. In OSPF, the source and
destination of a routing protocol packet are the two ends of an
(potential) adjacency.
Area ID
A 32 bit number identifying the area that this packet belongs