RFC 1583
OSPF Version 2
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 [RFC 1247], 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. [RFC 791] Postel, J., "Internet Protocol", STD 5, RFC 791, USC/Information Sciences Institute, September 1981. [RFC 905] McKenzie, A., "ISO Transport Protocol specification ISO DP 8073", RFC 905, ISO, April 1984. [RFC 1112] Deering, S., "Host extensions for IP multicasting", STD 5, RFC 1112, Stanford University, May 1988. [RFC 1213] McCloghrie, K., and M. Rose, "Management Information Base for network management of TCP/IP-based internets: MIB-II", STD 17, RFC 1213, Hughes LAN Systems, Performance Systems International, March 1991. [RFC 1247] Moy, J., "OSPF Version 2", RFC 1247, Proteon, Inc., July 1991. [RFC 1519] 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. [RFC 1340] Reynolds, J., and J. Postel, "Assigned Numbers", STD 2, RFC 1340, USC/Information Sciences Institute, July 1992. [RFC 1349] Almquist, P., "Type of Service in the Internet Protocol Suite", RFC 1349, 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 [RFC 1340].
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 [RFC 1349].
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 [RFC 791] 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
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.
AuType
Identifies the authentication scheme 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.
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 advertising 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 advertising 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 topological 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 master, the other a 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 | 0 | Options |0|0|0|0|0|I|M|MS +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DD sequence number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | +- -+ | A | +- Link State Advertisement -+ | 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 topological 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.
0 These fields are reserved. They must be 0.
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
topological database's pieces. Each link state advertisement in the
database is described by its link state advertisement header. The
link state advertisement header is documented in Section A.4.1. It
contains all the information required to uniquely identify both the
advertisement and the advertisement's current instance.
(next page on part 8)
