parameter has been set to TRUE in Step 2 of the Dijkstra algorithm
(see Section 16.1).
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-
LSAs are examined in turn. Each such summary-LSA describes a route
through a transit area Area A to a Network N (N's address is obtained
by masking the LSA's Link State ID with the network/subnet mask
contained in the body of the LSA) or in the case of a Type 4
summary-LSA, to an AS boundary router N. Suppose also that the
summary-LSA was originated by an area border router BR.
(1) If the cost advertised by the summary-LSA is LSInfinity, or
if the LSA's LS age is equal to MaxAge, then examine the
next LSA.
(2) If the summary-LSA was originated by the calculating router
itself, examine the next LSA.
(3) Look up the routing table entry for N. (If N is an AS
boundary router, look up the "router" routing table entry
associated with the backbone area). 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 LSA. 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 LSA. 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 LSA. 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.
. 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
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. The
calculation installs any better cost found into the routing table
entry, from which it may be readvertised in summary-LSAs 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 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-LSAs 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-LSAs by
the above calculation, Router RT1 will also forward Network N1
traffic towards RT5. Note that in this example the virtual link
enables transit data traffic to be forwarded through Area 1, but the
actual path the transit 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-LSAs.
Each of the AS-external-LSAs is considered in turn. Most AS-
external-LSAs describe routes to specific IP destinations. An AS-
external-LSA can also describe a default route for the Autonomous
System (Destination ID = DefaultDestination, network/subnet mask =
0x00000000). For each AS-external-LSA:
(1) If the cost specified by the LSA is LSInfinity, or if the
LSA's LS age is equal to MaxAge, then examine the next LSA.
(2) If the LSA was originated by the calculating router itself,
examine the next LSA.
(3) Call the destination described by the LSA N. N's address is
obtained by masking the LSA's Link State ID with the
network/subnet mask contained in the body of the LSA. Look
up the routing table entries (potentially one per attached
area) for the AS boundary router (ASBR) that originated the
LSA. If no entries exist for router ASBR (i.e., ASBR is
unreachable), do nothing with this LSA and consider the next
in the list.
Else, this LSA describes an AS external path to destination
N. Examine the forwarding address specified in the AS-
external-LSA. 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. Among the multiple routing table
entries for the ASBR, select the preferred entry as follows.
If RFC1583Compatibility is set to "disabled", prune the set
of routing table entries for the ASBR as described in
Section 16.4.1. In any case, among the remaining routing
table entries, select the routing table entry with the least
cost; when there are multiple least cost routing table
entries the entry whose associated area has the largest OSPF
Area ID (when considered as an unsigned 32-bit integer) is
chosen.
If the forwarding address is non-zero, look up the
forwarding address in the routing table.[24] The matching
routing table entry must specify an intra-area or inter-area
path; if no such path exists, do nothing with the LSA and
consider the next in the list.
(4) Let X be the cost specified by the preferred routing table
entry for the ASBR/forwarding address, and Y the cost
specified in the LSA. X is in terms of the link state
metric, and Y is a type 1 or 2 external metric.
(5) 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.
(6) Compare the AS external path described by the LSA with the
existing paths in N's routing table entry, as follows. If
the new path is preferred, it replaces the present paths in
N's routing table entry. If the new path is of equal
preference, it is added to N's routing table entry's list of
paths.
(a) Intra-area and inter-area paths are always preferred
over AS external paths.
(b) Type 1 external paths are always preferred over type 2
external paths. When all paths are type 2 external
paths, the paths with the smallest advertised type 2
metric are always preferred.
(c) If the new AS external path is still indistinguishable
from the current paths in the N's routing table entry,
and RFC1583Compatibility is set to "disabled", select
the preferred paths based on the intra-AS paths to the
ASBR/forwarding addresses, as specified in Section
16.4.1.
(d) If the new AS external path is still indistinguishable
from the current paths in the N's routing table entry,
select the preferred path based on a least cost
comparison. 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 advertising equal type 2 metrics are
compared by looking at the distance to the forwarding
addresses.
16.4.1. External path preferences
When multiple intra-AS paths are available to ASBRs/forwarding
addresses, the following rules indicate which paths are preferred.
These rules apply when the same ASBR is reachable through multiple
areas, or when trying to decide which of several AS-external-LSAs
should be preferred. In the former case the paths all terminate at
the same ASBR, while in the latter the paths terminate at separate
ASBRs/forwarding addresses. In either case, each path is represented
by a separate routing table entry as defined in Section 11.
This section only applies when RFC1583Compatibility is set to
"disabled".
The path preference rules, stated from highest to lowest preference,
are as follows. Note that as a result of these rules, there may still
be multiple paths of the highest preference. In this case, the path
to use must be determined based on cost, as described in Section
16.4.
o Intra-area paths using non-backbone areas are always the
most preferred.
o Otherwise, intra-area backbone paths are preferred.
o Inter-area paths are the least preferred.
16.5. Incremental updates -- summary-LSAs
When a new summary-LSA is received, it is not necessary to
recalculate the entire routing table. Call the destination described
by the summary-LSA N (N's address is obtained by masking the LSA's
Link State ID with the network/subnet mask contained in the body of
the LSA), and let Area A be the area to which the LSA 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-LSAs 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-LSA) or
to any forwarding addresses, all AS- external-LSAs 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-LSA) or to any forwarding addresses
has changed, all AS-external-LSAs 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-LSAs
When a new AS-external-LSA is received, it is not necessary to
recalculate the entire routing table. Call the destination described
by the AS-external-LSA N. N's address is obtained by masking the
LSA's Link State ID with the network/subnet mask contained in the
body of the LSA. 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-LSAs 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-LSAs 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 LSA 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, 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, 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-LSA 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.
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-LSA 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]"Discard" entries are necessary to ensure that route
summarization at area boundaries will not cause packet looping.
[11]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.
[12]MaxAgeDiff is an architectural constant. It indicates the
maximum dispersion of ages, in seconds, that can occur for a single
LSA instance as it is flooded throughout the routing domain. If two
LSAs differ by more than this, they are assumed to be different
instances of the same LSA. This can occur when a router restarts and
loses track of the LSA's previous LS sequence number. See Section
13.4 for more details.
[13]When two LSAs have different LS checksums, they are assumed to be
separate instances. This can occur when a router restarts, and loses
track of the LSA's previous LS sequence number. In the case where
the two LSAs have the same LS sequence number, it is not possible to
determine which LSA is actually newer. However, if the wrong LSA is
accepted as newer, the originating router will simply originate
another instance. See Section 13.4 for further details.
[14]There is one instance where a lookup must be done based on
partial information. This is during the routing table calculation,
when a network-LSA must be found based solely on its Link State ID.
The lookup in this case is still well defined, since no two network-
LSAs can have the same Link State ID.
[15]This is the way RFC1583 specified point-to-point representation.
It has three advantages: a) it does not require allocating a subnet
to the point-to-point link, b) it tends to bias the routing so that
packets destined for the point-to-point interface will actually be
received over the interface (which is useful for diagnostic purposes)
and c) it allows network bootstrapping of a neighbor, without
requiring that the bootstrap program contain an OSPF implementation.
[16]This is the more traditional point-to-point representation used
by protocols such as RIP.
[17]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.
[18]This clause is only invoked when a non-backbone Area A supports
transit data traffic (i.e., has TransitCapability set to TRUE). For
example, in the area configuration of Figure 6, Area 2 can support
transit traffic due to the configured virtual link between Routers
RT10 and RT11. As a result, Router RT11 need only originate a single
summary-LSA into Area 2 (having the collapsed destination N9-N11,H1),
since all of Router RT11's other eligible routes have next hops
belonging to Area 2 itself (and as such only need be advertised by
other area border routers; in this case, Routers RT10 and RT7).
[19]By keeping more information in the routing table, it is possible
for an implementation to recalculate the shortest path tree for only
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 [Ref1]. However, these algorithms are beyond the
scope of this specification.
[20]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.
[21]It should be a relatively rare occurrence for an LSA's LS age to
reach MaxAge in this fashion. Usually, the LSA will be replaced by a
more recent instance before it ages out.
[22]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.
[23]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.
[24]When the forwarding address is non-zero, it should point to a
router belonging to another Autonomous System. See Section 12.4.4
for more details.
References
[Ref1] McQuillan, J., I. Richer and E. Rosen, "ARPANET Routing
Algorithm Improvements", BBN Technical Report 3803, April
1978.
[Ref2] Digital Equipment Corporation, "Information processing
systems -- Data communications -- Intermediate System to
Intermediate System Intra-Domain Routing Protocol", October
1987.
[Ref3] McQuillan, J. et.al., "The New Routing Algorithm for the
ARPANET", IEEE Transactions on Communications, May 1980.
[Ref4] Perlman, R., "Fault-Tolerant Broadcast of Routing
Information", Computer Networks, December 1983.
[Ref5] Postel, J., "Internet Protocol", STD 5, RFC791,
USC/Information Sciences Institute, September 1981.
[Ref6] McKenzie, A., "ISO Transport Protocol specification ISO DP
8073", RFC905, ISO, April 1984.
[Ref7] Deering, S., "Host extensions for IP multicasting", STD 5,
RFC1112, Stanford University, May 1988.
[Ref8] 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.
[Ref9] Moy, J., "OSPF Version 2", RFC1583, Proteon, Inc., March
1994.
[Ref10] 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.
[Ref11] Reynolds, J., and J. Postel, "Assigned Numbers", STD 2, RFC
1700, USC/Information Sciences Institute, October 1994.
[Ref12] Almquist, P., "Type of Service in the Internet Protocol
Suite", RFC1349, July 1992.
[Ref13] Leiner, B., et.al., "The DARPA Internet Protocol Suite", DDN
Protocol Handbook, April 1985.
[Ref14] Bradley, T., and C. Brown, "Inverse Address Resolution
Protocol", RFC1293, January 1992.
[Ref15] deSouza, O., and M. Rodrigues, "Guidelines for Running OSPF
Over Frame Relay Networks", RFC1586, March 1994.
[Ref16] Bellovin, S., "Security Problems in the TCP/IP Protocol
Suite", ACM Computer Communications Review, Volume 19,
Number 2, pp. 32-38, April 1989.
[Ref17] Rivest, R., "The MD5 Message-Digest Algorithm", RFC1321,
April 1992.
[Ref18] Moy, J., "Multicast Extensions to OSPF", RFC1584, Proteon,
Inc., March 1994.
[Ref19] Coltun, R. and V. Fuller, "The OSPF NSSA Option", RFC1587,
RainbowBridge Communications, Stanford University, March
1994.
[Ref20] Ferguson, D., "The OSPF External Attributes LSA", work in
progress.
[Ref21] Moy, J., "Extending OSPF to Support Demand Circuits", RFC
1793, Cascade, April 1995.
[Ref22] Mogul, J. and S. Deering, "Path MTU Discovery", RFC1191,
DECWRL, Stanford University, November 1990.
[Ref23] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4 (BGP-
4)", RFC1771, T.J. Watson Research Center, IBM Corp., cisco
Systems, March 1995.
[Ref24] Hinden, R., "Internet Routing Protocol Standardization
Criteria", BBN, October 1991.
A. OSPF data formats
This appendix describes the format of OSPF protocol packets and OSPF
LSAs. 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 LSAs.
OSPF packet formats are detailed in Section A.3. A description of
OSPF LSAs 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. If necessary, the length of OSPF packets can be up to
65,535 bytes (including the IP header). 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 OSPF packets sent over virtual links to
576 bytes unless Path MTU Discovery is being performed (see [Ref22]).
The other important features of OSPF's IP encapsulation are:
o Use of IP multicast. Some OSPF messages are multicast, when
sent over broadcast 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 [Ref11].
o All OSPF routing protocol packets are sent using the normal
service TOS value of binary 0000 defined in [Ref12].
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 [Ref5] 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 LSAs. 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 LSAs to a neighbor because
of its reduced functionality. Lastly, listing capabilities in LSAs
allows routers to forward traffic around reduced functionality
routers, by excluding them from parts of the routing table
calculation.
Five bits of the OSPF Options field have been assigned, although only
one (the E-bit) is described completely by this memo. Each bit is
described briefly below. Routers should reset (i.e. clear)
unrecognized bits in the Options field when sending Hello packets or
Database Description packets and when originating LSAs. Conversely,
routers encountering unrecognized Option bits in received Hello
Packets, Database Description packets or LSAs should ignore the
capability and process the packet/LSA normally.
+------------------------------------+
| * | * | DC | EA | N/P | MC | E | * |
+------------------------------------+
The Options field
E-bit
This bit describes the way AS-external-LSAs are flooded, as
described in Sections 3.6, 9.5, 10.8 and 12.1.2 of this memo.
MC-bit
This bit describes whether IP multicast datagrams are forwarded
according to the specifications in [Ref18].
N/P-bit
This bit describes the handling of Type-7 LSAs, as specified in
[Ref19].
EA-bit
This bit describes the router's willingness to receive and
forward External-Attributes-LSAs, as specified in [Ref20].
DC-bit
This bit describes the router's handling of demand circuits, as
specified in [Ref21].
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 LSAs. For example, Link State Update packets implement the
flooding of LSAs throughout the OSPF routing domain. Because of
this, OSPF protocol packets cannot be parsed unless the format of
LSAs is also understood. The format of LSAs 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 standard 24 byte header. This header
contains all the information necessary 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. See Sections A.3.2 through
A.3.6 for details.
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 OSPF protocol packet in bytes. This length
includes the standard OSPF header.
Router ID
The Router ID of the packet's source.
Area ID
A 32 bit number identifying the area that this packet belongs
to. All OSPF packets are associated with a single area. Most
travel a single hop only. Packets travelling over a virtual
link are labelled with the backbone Area ID of 0.0.0.0.
Checksum
The standard IP checksum of the entire contents of the packet,
starting with the OSPF packet header but excluding the 64-bit
authentication field. This checksum is calculated as the 16-bit
one's complement of the one's complement sum of all the 16-bit
words in the packet, excepting the authentication field. If the
packet's length is not an integral number of 16-bit words, the
packet is padded with a byte of zero before checksumming. The
checksum is considered to be part of the packet authentication
procedure; for some authentication types the checksum
calculation is omitted.
AuType
Identifies the authentication procedure to be used for the
packet. Authentication is discussed in Appendix D of the
specification. Consult Appendix D for a list of the currently
defined authentication types.
Authentication
A 64-bit field for use by the authentication scheme. See
Appendix D for details.
A.3.2 The Hello packet
Hello packets are OSPF packet type 1. These packets are sent
periodically on all interfaces (including virtual links) in order to
establish and maintain neighbor relationships. In addition, Hello
Packets are multicast on those physical networks having a multicast
or broadcast capability, enabling dynamic discovery of neighboring
routers.
All routers connected to a common network must agree on certain
parameters (Network mask, HelloInterval and RouterDeadInterval).
These parameters are included in Hello packets, so that differences
can inhibit the forming of neighbor relationships. A detailed
explanation of the receive processing for Hello packets is presented
in Section 10.5. The sending of Hello packets is covered in Section
9.5.
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 # | 1 | Packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Area ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Checksum | AuType |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Network Mask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| HelloInterval | Options | Rtr Pri |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RouterDeadInterval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Designated Router |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Backup Designated Router |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
Network mask
The network mask associated with this interface. For example,
if the interface is to a class B network whose third byte is
used for subnetting, the network mask is 0xffffff00.
Options
The optional capabilities supported by the router, as documented
in Section A.2.
HelloInterval
The number of seconds between this router's Hello packets.
Rtr Pri
This router's Router Priority. Used in (Backup) Designated
Router election. If set to 0, the router will be ineligible to
become (Backup) Designated Router.
RouterDeadInterval
The number of seconds before declaring a silent router down.
Designated Router
The identity of the Designated Router for this network, in the
view of the sending router. The Designated Router is identified
here by its IP interface address on the network. Set to 0.0.0.0
if there is no Designated Router.
Backup Designated Router
The identity of the Backup Designated Router for this network,
in the view of the sending router. The Backup Designated Router
is identified here by its IP interface address on the network.
Set to 0.0.0.0 if there is no Backup Designated Router.
Neighbor
The Router IDs of each router from whom valid Hello packets have
been seen recently on the network. Recently means in the last
RouterDeadInterval seconds.
A.3.3 The Database Description packet
Database Description packets are OSPF packet type 2. These packets
are exchanged when an adjacency is being initialized. They describe
the contents of the link-state database. Multiple packets may be
used to describe the database. For this purpose a poll-response
procedure is used. One of the routers is designated to be the master,
the other the slave. The master sends Database Description packets
(polls) which are acknowledged by Database Description packets sent
by the slave (responses). The responses are linked to the polls via
the packets' DD sequence numbers.
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 # | 2 | Packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Area ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Checksum | AuType |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Interface MTU | Options |0|0|0|0|0|I|M|MS
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| DD sequence number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+- -+
| |
+- An LSA Header -+
| |
+- -+
| |
+- -+
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
The format of the Database Description packet is very similar to both
the Link State Request and Link State Acknowledgment packets. The
main part of all three is a list of items, each item describing a
piece of the link-state database. The sending of Database
Description Packets is documented in Section 10.8. The reception of
Database Description packets is documented in Section 10.6.
Interface MTU
The size in bytes of the largest IP datagram that can be sent out
the associated interface, without fragmentation. The MTUs of
common Internet link types can be found in Table 7-1 of [Ref22].
Interface MTU should be set to 0 in Database Description packets
sent over virtual links.
Options
The optional capabilities supported by the router, as documented
in Section A.2.
I-bit
The Init bit. When set to 1, this packet is the first in the
sequence of Database Description Packets.
M-bit
The More bit. When set to 1, it indicates that more Database
Description Packets are to follow.
MS-bit
The Master/Slave bit. When set to 1, it indicates that the router
is the master during the Database Exchange process. Otherwise,
the router is the slave.
DD sequence number
Used to sequence the collection of Database Description Packets.
The initial value (indicated by the Init bit being set) should be
unique. The DD sequence number then increments until the complete
database description has been sent.
The rest of the packet consists of a (possibly partial) list of the
link-state database's pieces. Each LSA in the database is described
by its LSA header. The LSA header is documented in Section A.4.1. It
contains all the information required to uniquely identify both the
LSA and the LSA's current instance.
A.3.4 The Link State Request packet
Link State Request packets are OSPF packet type 3. After exchanging
Database Description packets with a neighboring router, a router may
find that parts of its link-state database are out-of-date. The Link
State Request packet is used to request the pieces of the neighbor's
database that are more up-to-date. Multiple Link State Request
packets may need to be used.
A router that sends a Link State Request packet has in mind the
precise instance of the database pieces it is requesting. Each
instance is defined by its LS sequence number, LS checksum, and LS
age, although these fields are not specified in the Link State
Request Packet itself. The router may receive even more recent
instances in response.
The sending of Link State Request packets is documented in Section
10.9. The reception of Link State Request packets is documented in
Section 10.7.
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 # | 3 | Packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Area ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Checksum | AuType |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LS type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link State ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertising Router |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
Each LSA requested is specified by its LS type, Link State ID, and
Advertising Router. This uniquely identifies the LSA, but not its
instance. Link State Request packets are understood to be requests
for the most recent instance (whatever that might be).
A.3.5 The Link State Update packet
Link State Update packets are OSPF packet type 4. These packets
implement the flooding of LSAs. Each Link State Update packet
carries a collection of LSAs one hop further from their origin.
Several LSAs may be included in a single packet.
Link State Update packets are multicast on those physical networks
that support multicast/broadcast. In order to make the flooding
procedure reliable, flooded LSAs are acknowledged in Link State
Acknowledgment packets. If retransmission of certain LSAs is
necessary, the retransmitted LSAs are always carried by unicast Link
State Update packets. For more information on the reliable flooding
of LSAs, consult Section 13.
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 # | 4 | Packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Area ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Checksum | AuType |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| # LSAs |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+- +-+
| LSAs |
+- +-+
| ... |
# LSAs
The number of LSAs included in this update.
The body of the Link State Update packet consists of a list of LSAs.
Each LSA begins with a common 20 byte header, described in Section
A.4.1. Detailed formats of the different types of LSAs are described
in Section A.4.
A.3.6 The Link State Acknowledgment packet
Link State Acknowledgment Packets are OSPF packet type 5. To make
the flooding of LSAs reliable, flooded LSAs are explicitly
acknowledged. This acknowledgment is accomplished through the
sending and receiving of Link State Acknowledgment packets. Multiple
LSAs can be acknowledged in a single Link State Acknowledgment
packet.
Depending on the state of the sending interface and the sender of the
corresponding Link State Update packet, a Link State Acknowledgment
packet is sent either to the multicast address AllSPFRouters, to the
multicast address AllDRouters, or as a unicast. The sending of Link
State Acknowledgment packets is documented in Section 13.5. The
reception of Link State Acknowledgment packets is documented in
Section 13.7.
The format of this packet is similar to that of the Data Description
packet. The body of both packets is simply a list of LSA headers.
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 # | 5 | Packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Area ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Checksum | AuType |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+- -+
| |
+- An LSA Header -+