allowed outstanding at any one time. In this state, Link State
Request Packets may also be sent asking for the neighbor's more
recent LSAs. All adjacencies in Exchange state or greater are
used by the flooding procedure. In fact, these adjacencies are
fully capable of transmitting and receiving all types of OSPF
routing protocol packets.
Loading
In this state, Link State Request packets are sent to the neighbor
asking for the more recent LSAs that have been discovered (but not
yet received) in the Exchange state.
Full
In this state, the neighboring routers are fully adjacent. These
adjacencies will now appear in router-LSAs and network-LSAs.
10.2. Events causing neighbor state changes
State changes can be effected by a number of events. These events
are shown in the labels of the arcs in Figures 12 and 13. The label
definitions are as follows:
HelloReceived
An Hello packet has been received from the neighbor.
Start
This is an indication that Hello Packets should now be sent to the
neighbor at intervals of HelloInterval seconds. This event is
generated only for neighbors associated with NBMA networks.
2-WayReceived
Bidirectional communication has been realized between the two
neighboring routers. This is indicated by the router seeing
itself in the neighbor's Hello packet.
NegotiationDone
The Master/Slave relationship has been negotiated, and DD sequence
numbers have been exchanged. This signals the start of the
sending/receiving of Database Description packets. For more
information on the generation of this event, consult Section 10.8.
ExchangeDone
Both routers have successfully transmitted a full sequence of
Database Description packets. Each router now knows what parts of
its link state database are out of date. For more information on
the generation of this event, consult Section 10.8.
BadLSReq
A Link State Request has been received for an LSA not contained in
the database. This indicates an error in the Database Exchange
process.
Loading Done
Link State Updates have been received for all out-of-date portions
of the database. This is indicated by the Link state request list
becoming empty after the Database Exchange process has completed.
AdjOK?
A decision must be made as to whether an adjacency should be
established/maintained with the neighbor. This event will start
some adjacencies forming, and destroy others.
The following events cause well developed neighbors to revert to
lesser states. Unlike the above events, these events may occur when
the neighbor conversation is in any of a number of states.
SeqNumberMismatch
A Database Description packet has been received that either a) has
an unexpected DD sequence number, b) unexpectedly has the Init bit
set or c) has an Options field differing from the last Options
field received in a Database Description packet. Any of these
conditions indicate that some error has occurred during adjacency
establishment.
1-Way
An Hello packet has been received from the neighbor, in which the
router is not mentioned. This indicates that communication with
the neighbor is not bidirectional.
KillNbr
This is an indication that all communication with the neighbor is
now impossible, forcing the neighbor to revert to Down state.
InactivityTimer
The inactivity Timer has fired. This means that no Hello packets
have been seen recently from the neighbor. The neighbor reverts to
Down state.
LLDown
This is an indication from the lower level protocols that the
neighbor is now unreachable. For example, on an X.25 network this
could be indicated by an X.25 clear indication with appropriate
cause and diagnostic fields. This event forces the neighbor into
Down state.
10.3. The Neighbor state machine
A detailed description of the neighbor state changes follows. Each
state change is invoked by an event (Section 10.2). This event may
produce different effects, depending on the current state of the
neighbor. For this reason, the state machine below is organized by
current neighbor state and received event. Each entry in the state
machine describes the resulting new neighbor state and the required
set of additional actions.
When a neighbor's state changes, it may be necessary to rerun the
Designated Router election algorithm. This is determined by whether
the interface NeighborChange event is generated (see Section 9.2).
Also, if the Interface is in DR state (the router is itself
Designated Router), changes in neighbor state may cause a new
network-LSA to be originated (see Section 12.4).
When the neighbor state machine needs to invoke the interface state
machine, it should be done as a scheduled task (see Section 4.4).
This simplifies things, by ensuring that neither state machine will
be executed recursively.
State(s): Down
Event: Start
New state: Attempt
Action: Send an Hello Packet to the neighbor (this neighbor
is always associated with an NBMA network) and start
the Inactivity Timer for the neighbor. The timer's
later firing would indicate that communication with
the neighbor was not attained.
State(s): Attempt
Event: HelloReceived
New state: Init
Action: Restart the Inactivity Timer for the neighbor, since
the neighbor has now been heard from.
State(s): Down
Event: HelloReceived
New state: Init
Action: Start the Inactivity Timer for the neighbor. The
timer's later firing would indicate that the neighbor
is dead.
State(s): Init or greater
Event: HelloReceived
New state: No state change.
Action: Restart the Inactivity Timer for the neighbor, since
the neighbor has again been heard from.
State(s): Init
Event: 2-WayReceived
New state: Depends upon action routine.
Action: Determine whether an adjacency should be established
with the neighbor (see Section 10.4). If not, the
new neighbor state is 2-Way.
Otherwise (an adjacency should be established) the
neighbor state transitions to ExStart. Upon
entering this state, the router increments the DD
sequence number in the neighbor data structure. If
this is the first time that an adjacency has been
attempted, the DD sequence number should be assigned
some unique value (like the time of day clock). It
then declares itself master (sets the master/slave
bit to master), and starts sending Database
Description Packets, with the initialize (I), more
(M) and master (MS) bits set. This Database
Description Packet should be otherwise empty. This
Database Description Packet should be retransmitted
at intervals of RxmtInterval until the next state is
entered (see Section 10.8).
State(s): ExStart
Event: NegotiationDone
New state: Exchange
Action: The router must list the contents of its entire area
link state database in the neighbor Database summary
list. The area link state database consists of the
router-LSAs, network-LSAs and summary-LSAs contained
in the area structure, along with the AS-external-
LSAs contained in the global structure. AS-
external-LSAs are omitted from a virtual neighbor's
Database summary list. AS-external-LSAs are omitted
from the Database summary list if the area has been
configured as a stub (see Section 3.6). LSAs whose
age is equal to MaxAge are instead added to the
neighbor's Link state retransmission list. A
summary of the Database summary list will be sent to
the neighbor in Database Description packets. Each
Database Description Packet has a DD sequence
number, and is explicitly acknowledged. Only one
Database Description Packet is allowed outstanding
at any one time. For more detail on the sending and
receiving of Database Description packets, see
Sections 10.8 and 10.6.
State(s): Exchange
Event: ExchangeDone
New state: Depends upon action routine.
Action: If the neighbor Link state request list is empty,
the new neighbor state is Full. No other action is
required. This is an adjacency's final state.
Otherwise, the new neighbor state is Loading. Start
(or continue) sending Link State Request packets to
the neighbor (see Section 10.9). These are requests
for the neighbor's more recent LSAs (which were
discovered but not yet received in the Exchange
state). These LSAs are listed in the Link state
request list associated with the neighbor.
State(s): Loading
Event: Loading Done
New state: Full
Action: No action required. This is an adjacency's final
state.
State(s): 2-Way
Event: AdjOK?
New state: Depends upon action routine.
Action: Determine whether an adjacency should be formed with
the neighboring router (see Section 10.4). If not,
the neighbor state remains at 2-Way. Otherwise,
transition the neighbor state to ExStart and perform
the actions associated with the above state machine
entry for state Init and event 2-WayReceived.
State(s): ExStart or greater
Event: AdjOK?
New state: Depends upon action routine.
Action: Determine whether the neighboring router should
still be adjacent. If yes, there is no state change
and no further action is necessary.
Otherwise, the (possibly partially formed) adjacency
must be destroyed. The neighbor state transitions
to 2-Way. The Link state retransmission list,
Database summary list and Link state request list
are cleared of LSAs.
State(s): Exchange or greater
Event: SeqNumberMismatch
New state: ExStart
Action: The (possibly partially formed) adjacency is torn
down, and then an attempt is made at
reestablishment. The neighbor state first
transitions to ExStart. The Link state
retransmission list, Database summary list and Link
state request list are cleared of LSAs. Then the
router increments the DD sequence number in the
neighbor data structure, declares itself master
(sets the master/slave bit to master), and starts
sending Database Description Packets, with the
initialize (I), more (M) and master (MS) bits set.
This Database Description Packet should be otherwise
empty (see Section 10.8).
State(s): Exchange or greater
Event: BadLSReq
New state: ExStart
Action: The action for event BadLSReq is exactly the same as
for the neighbor event SeqNumberMismatch. The
(possibly partially formed) adjacency is torn down,
and then an attempt is made at reestablishment. For
more information, see the neighbor state machine
entry that is invoked when event SeqNumberMismatch
is generated in state Exchange or greater.
State(s): Any state
Event: KillNbr
New state: Down
Action: The Link state retransmission list, Database summary
list and Link state request list are cleared of
LSAs. Also, the Inactivity Timer is disabled.
State(s): Any state
Event: LLDown
New state: Down
Action: The Link state retransmission list, Database summary
list and Link state request list are cleared of
LSAs. Also, the Inactivity Timer is disabled.
State(s): Any state
Event: InactivityTimer
New state: Down
Action: The Link state retransmission list, Database summary
list and Link state request list are cleared of
LSAs.
State(s): 2-Way or greater
Event: 1-WayReceived
New state: Init
Action: The Link state retransmission list, Database summary
list and Link state request list are cleared of
LSAs.
State(s): 2-Way or greater
Event: 2-WayReceived
New state: No state change.
Action: No action required.
State(s): Init
Event: 1-WayReceived
New state: No state change.
Action: No action required.
10.4. Whether to become adjacent
Adjacencies are established with some subset of the router's
neighbors. Routers connected by point-to-point networks, Point-to-
MultiPoint networks and virtual links always become adjacent. On
broadcast and NBMA networks, all routers become adjacent to both the
Designated Router and the Backup Designated Router.
The adjacency-forming decision occurs in two places in the neighbor
state machine. First, when bidirectional communication is initially
established with the neighbor, and secondly, when the identity of the
attached network's (Backup) Designated Router changes. If the
decision is made to not attempt an adjacency, the state of the
neighbor communication stops at 2-Way.
An adjacency should be established with a bidirectional neighbor when
at least one of the following conditions holds:
o The underlying network type is point-to-point
o The underlying network type is Point-to-MultiPoint
o The underlying network type is virtual link
o The router itself is the Designated Router
o The router itself is the Backup Designated Router
o The neighboring router is the Designated Router
o The neighboring router is the Backup Designated Router
10.5. Receiving Hello Packets
This section explains the detailed processing of a received Hello
Packet. (See Section A.3.2 for the format of Hello packets.) The
generic input processing of OSPF packets will have checked the
validity of the IP header and the OSPF packet header. Next, the
values of the Network Mask, HelloInterval, and RouterDeadInterval
fields in the received Hello packet must be checked against the
values configured for the receiving interface. Any mismatch causes
processing to stop and the packet to be dropped. In other words, the
above fields are really describing the attached network's
configuration. However, there is one exception to the above rule: on
point-to-point networks and on virtual links, the Network Mask in the
received Hello Packet should be ignored.
The receiving interface attaches to a single OSPF area (this could be
the backbone). The setting of the E-bit found in the Hello Packet's
Options field must match this area's ExternalRoutingCapability. If
AS-external-LSAs are not flooded into/throughout the area (i.e, the
area is a "stub") the E-bit must be clear in received Hello Packets,
otherwise the E-bit must be set. A mismatch causes processing to
stop and the packet to be dropped. The setting of the rest of the
bits in the Hello Packet's Options field should be ignored.
At this point, an attempt is made to match the source of the Hello
Packet to one of the receiving interface's neighbors. If the
receiving interface connects to a broadcast, Point-to-MultiPoint or
NBMA network the source is identified by the IP source address found
in the Hello's IP header. If the receiving interface connects to a
point-to-point link or a virtual link, the source is identified by
the Router ID found in the Hello's OSPF packet header. The
interface's current list of neighbors is contained in the interface's
data structure. If a matching neighbor structure cannot be found,
(i.e., this is the first time the neighbor has been detected), one is
created. The initial state of a newly created neighbor is set to
Down.
When receiving an Hello Packet from a neighbor on a broadcast,
Point-to-MultiPoint or NBMA network, set the neighbor structure's
Neighbor ID equal to the Router ID found in the packet's OSPF header.
When receiving an Hello on a point-to-point network (but not on a
virtual link) set the neighbor structure's Neighbor IP address to the
packet's IP source address.
Now the rest of the Hello Packet is examined, generating events to be
given to the neighbor and interface state machines. These state
machines are specified either to be executed or scheduled (see
Section 4.4). For example, by specifying below that the neighbor
state machine be executed in line, several neighbor state transitions
may be effected by a single received Hello:
o Each Hello Packet causes the neighbor state machine to be
executed with the event HelloReceived.
o Then the list of neighbors contained in the Hello Packet is
examined. If the router itself appears in this list, the
neighbor state machine should be executed with the event 2-
WayReceived. Otherwise, the neighbor state machine should
be executed with the event 1-WayReceived, and the processing
of the packet stops.
o Next, the Hello Packet's Router Priority field is examined.
If this field is different than the one previously received
from the neighbor, the receiving interface's state machine
is scheduled with the event NeighborChange. In any case,
the Router Priority field in the neighbor data structure
should be updated accordingly.
o Next the Designated Router field in the Hello Packet is
examined. If the neighbor is both declaring itself to be
Designated Router (Designated Router field = Neighbor IP
address) and the Backup Designated Router field in the
packet is equal to 0.0.0.0 and the receiving interface is in
state Waiting, the receiving interface's state machine is
scheduled with the event BackupSeen. Otherwise, if the
neighbor is declaring itself to be Designated Router and it
had not previously, or the neighbor is not declaring itself
Designated Router where it had previously, the receiving
interface's state machine is scheduled with the event
NeighborChange. In any case, the Neighbors' Designated
Router item in the neighbor structure is updated
accordingly.
o Finally, the Backup Designated Router field in the Hello
Packet is examined. If the neighbor is declaring itself to
be Backup Designated Router (Backup Designated Router field
= Neighbor IP address) and the receiving interface is in
state Waiting, the receiving interface's state machine is
scheduled with the event BackupSeen. Otherwise, if the
neighbor is declaring itself to be Backup Designated Router
and it had not previously, or the neighbor is not declaring
itself Backup Designated Router where it had previously, the
receiving interface's state machine is scheduled with the
event NeighborChange. In any case, the Neighbor's Backup
Designated Router item in the neighbor structure is updated
accordingly.
On NBMA networks, receipt of an Hello Packet may also cause an Hello
Packet to be sent back to the neighbor in response. See Section 9.5.1
for more details.
10.6. Receiving Database Description Packets
This section explains the detailed processing of a received Database
Description Packet. The incoming Database Description Packet has
already been associated with a neighbor and receiving interface by
the generic input packet processing (Section 8.2). Whether the
Database Description packet should be accepted, and if so, how it
should be further processed depends upon the neighbor state.
If a Database Description packet is accepted, the following packet
fields should be saved in the corresponding neighbor data structure
under "last received Database Description packet": the packet's
initialize(I), more (M) and master(MS) bits, Options field, and DD
sequence number. If these fields are set identically in two
consecutive Database Description packets received from the neighbor,
the second Database Description packet is considered to be a
"duplicate" in the processing described below.
If the Interface MTU field in the Database Description packet
indicates an IP datagram size that is larger than the router can
accept on the receiving interface without fragmentation, the Database
Description packet is rejected. Otherwise, if the neighbor state is:
Down
The packet should be rejected.
Attempt
The packet should be rejected.
Init
The neighbor state machine should be executed with the event 2-
WayReceived. This causes an immediate state change to either
state 2-Way or state ExStart. If the new state is ExStart, the
processing of the current packet should then continue in this new
state by falling through to case ExStart below.
2-Way
The packet should be ignored. Database Description Packets are
used only for the purpose of bringing up adjacencies.[7]
ExStart
If the received packet matches one of the following cases, then
the neighbor state machine should be executed with the event
NegotiationDone (causing the state to transition to Exchange), the
packet's Options field should be recorded in the neighbor
structure's Neighbor Options field and the packet should be
accepted as next in sequence and processed further (see below).
Otherwise, the packet should be ignored.
o The initialize(I), more (M) and master(MS) bits are set,
the contents of the packet are empty, and the neighbor's
Router ID is larger than the router's own. In this case
the router is now Slave. Set the master/slave bit to
slave, and set the neighbor data structure's DD sequence
number to that specified by the master.
o The initialize(I) and master(MS) bits are off, the
packet's DD sequence number equals the neighbor data
structure's DD sequence number (indicating
acknowledgment) and the neighbor's Router ID is smaller
than the router's own. In this case the router is
Master.
Exchange
Duplicate Database Description packets are discarded by the
master, and cause the slave to retransmit the last Database
Description packet that it had sent. Otherwise (the packet is not
a duplicate):
o If the state of the MS-bit is inconsistent with the
master/slave state of the connection, generate the
neighbor event SeqNumberMismatch and stop processing the
packet.
o If the initialize(I) bit is set, generate the neighbor
event SeqNumberMismatch and stop processing the packet.
o If the packet's Options field indicates a different set
of optional OSPF capabilities than were previously
received from the neighbor (recorded in the Neighbor
Options field of the neighbor structure), generate the
neighbor event SeqNumberMismatch and stop processing the
packet.
o Database Description packets must be processed in
sequence, as indicated by the packets' DD sequence
numbers. If the router is master, the next packet
received should have DD sequence number equal to the DD
sequence number in the neighbor data structure. If the
router is slave, the next packet received should have DD
sequence number equal to one more than the DD sequence
number stored in the neighbor data structure. In either
case, if the packet is the next in sequence it should be
accepted and its contents processed as specified below.
o Else, generate the neighbor event SeqNumberMismatch and
stop processing the packet.
Loading or Full
In this state, the router has sent and received an entire sequence
of Database Description Packets. The only packets received should
be duplicates (see above). In particular, the packet's Options
field should match the set of optional OSPF capabilities
previously indicated by the neighbor (stored in the neighbor
structure's Neighbor Options field). Any other packets received,
including the reception of a packet with the Initialize(I) bit
set, should generate the neighbor event SeqNumberMismatch.[8]
Duplicates should be discarded by the master. The slave must
respond to duplicates by repeating the last Database Description
packet that it had sent.
When the router accepts a received Database Description Packet as the
next in sequence the packet contents are processed as follows. For
each LSA listed, the LSA's LS type is checked for validity. If the
LS type is unknown (e.g., not one of the LS types 1-5 defined by this
specification), or if this is an AS-external-LSA (LS type = 5) and
the neighbor is associated with a stub area, generate the neighbor
event SeqNumberMismatch and stop processing the packet. Otherwise,
the router looks up the LSA in its database to see whether it also
has an instance of the LSA. If it does not, or if the database copy
is less recent (see Section 13.1), the LSA is put on the Link state
request list so that it can be requested (immediately or at some
later time) in Link State Request Packets.
When the router accepts a received Database Description Packet as the
next in sequence, it also performs the following actions, depending
on whether it is master or slave:
Master
Increments the DD sequence number in the neighbor data structure.
If the router has already sent its entire sequence of Database
Description Packets, and the just accepted packet has the more bit
(M) set to 0, the neighbor event ExchangeDone is generated.
Otherwise, it should send a new Database Description to the slave.
Slave
Sets the DD sequence number in the neighbor data structure to the
DD sequence number appearing in the received packet. The slave
must send a Database Description Packet in reply. If the received
packet has the more bit (M) set to 0, and the packet to be sent by
the slave will also have the M-bit set to 0, the neighbor event
ExchangeDone is generated. Note that the slave always generates
this event before the master.
10.7. Receiving Link State Request Packets
This section explains the detailed processing of received Link State
Request packets. Received Link State Request Packets specify a list
of LSAs that the neighbor wishes to receive. Link State Request
Packets should be accepted when the neighbor is in states Exchange,
Loading, or Full. In all other states Link State Request Packets
should be ignored.
Each LSA specified in the Link State Request packet should be located
in the router's database, and copied into Link State Update packets
for transmission to the neighbor. These LSAs should NOT be placed on
the Link state retransmission list for the neighbor. If an LSA
cannot be found in the database, something has gone wrong with the
Database Exchange process, and neighbor event BadLSReq should be
generated.
10.8. Sending Database Description Packets
This section describes how Database Description Packets are sent to a
neighbor. The Database Description packet's Interface MTU field is
set to the size of the largest IP datagram that can be sent out the
sending interface, without fragmentation. Common MTUs in use in the
Internet can be found in Table 7-1 of [Ref22]. Interface MTU should
be set to 0 in Database Description packets sent over virtual links.
The router's optional OSPF capabilities (see Section 4.5) are
transmitted to the neighbor in the Options field of the Database
Description packet. The router should maintain the same set of
optional capabilities throughout the Database Exchange and flooding
procedures. If for some reason the router's optional capabilities
change, the Database Exchange procedure should be restarted by
reverting to neighbor state ExStart. One optional capability is
defined in this specification (see Sections 4.5 and A.2). The E-bit
should be set if and only if the attached network belongs to a non-
stub area. Unrecognized bits in the Options field should be set to
zero. The sending of Database Description packets depends on the
neighbor's state. In state ExStart the router sends empty Database
Description packets, with the initialize (I), more (M) and master
(MS) bits set. These packets are retransmitted every RxmtInterval
seconds.
In state Exchange the Database Description Packets actually contain
summaries of the link state information contained in the router's
database. Each LSA in the area's link-state database (at the time
the neighbor transitions into Exchange state) is listed in the
neighbor Database summary list. Each new Database Description Packet
copies its DD sequence number from the neighbor data structure and
then describes the current top of the Database summary list. Items
are removed from the Database summary list when the previous packet
is acknowledged.
In state Exchange, the determination of when to send a Database
Description packet depends on whether the router is master or slave:
Master
Database Description packets are sent when either a) the slave
acknowledges the previous Database Description packet by echoing
the DD sequence number or b) RxmtInterval seconds elapse without
an acknowledgment, in which case the previous Database Description
packet is retransmitted.
Slave
Database Description packets are sent only in response to Database
Description packets received from the master. If the Database
Description packet received from the master is new, a new Database
Description packet is sent, otherwise the previous Database
Description packet is resent.
In states Loading and Full the slave must resend its last Database
Description packet in response to duplicate Database Description
packets received from the master. For this reason the slave must
wait RouterDeadInterval seconds before freeing the last Database
Description packet. Reception of a Database Description packet from
the master after this interval will generate a SeqNumberMismatch
neighbor event.
10.9. Sending Link State Request Packets
In neighbor states Exchange or Loading, the Link state request list
contains a list of those LSAs that need to be obtained from the
neighbor. To request these LSAs, a router sends the neighbor the
beginning of the Link state request list, packaged in a Link State
Request packet.
When the neighbor responds to these requests with the proper Link
State Update packet(s), the Link state request list is truncated and
a new Link State Request packet is sent. This process continues
until the Link state request list becomes empty. Unsatisfied Link
State Request packets are retransmitted at intervals of RxmtInterval.
There should be at most one Link State Request packet outstanding at
any one time.
When the Link state request list becomes empty, and the neighbor
state is Loading (i.e., a complete sequence of Database Description
packets has been sent to and received from the neighbor), the Loading
Done neighbor event is generated.
10.10. An Example
Figure 14 shows an example of an adjacency forming. Routers RT1 and
RT2 are both connected to a broadcast network. It is assumed that
RT2 is the Designated Router for the network, and that RT2 has a
higher Router ID than Router RT1.
The neighbor state changes realized by each router are listed on the
sides of the figure.
At the beginning of Figure 14, Router RT1's interface to the network
becomes operational. It begins sending Hello Packets, although it
doesn't know the identity of the Designated Router or of any other
neighboring routers. Router RT2 hears this hello (moving the
neighbor to Init state), and in its next Hello Packet indicates that
it is itself the Designated Router and that it has heard Hello
Packets from RT1. This in turn causes RT1 to go to state ExStart, as
it starts to bring up the adjacency.
RT1 begins by asserting itself as the master. When it sees that RT2
is indeed the master (because of RT2's higher Router ID), RT1
transitions to slave state and adopts its neighbor's DD sequence
number. Database Description packets are then exchanged, with polls
coming from the master (RT2) and responses from the slave (RT1).
This sequence of Database Description Packets ends when both the poll
and associated response has the M-bit off.
In this example, it is assumed that RT2 has a completely up to date
database. In that case, RT2 goes immediately into Full state. RT1
will go into Full state after updating the necessary parts of its
database. This is done by sending Link State Request Packets, and
receiving Link State Update Packets in response. Note that, while
RT1 has waited until a complete set of Database Description Packets
has been received (from RT2) before sending any Link State Request
Packets, this need not be the case. RT1 could have interleaved the
sending of Link State Request Packets with the reception of Database
Description Packets.
+---+ +---+
|RT1| |RT2|
+---+ +---+
Down Down
Hello(DR=0,seen=0)
------------------------------>
Hello (DR=RT2,seen=RT1,...) Init
<------------------------------
ExStart D-D (Seq=x,I,M,Master)
------------------------------>
D-D (Seq=y,I,M,Master) ExStart
<------------------------------
Exchange D-D (Seq=y,M,Slave)
------------------------------>
D-D (Seq=y+1,M,Master) Exchange
<------------------------------
D-D (Seq=y+1,M,Slave)
------------------------------>
...
...
...
D-D (Seq=y+n, Master)
<------------------------------
D-D (Seq=y+n, Slave)
Loading ------------------------------>
LS Request Full
------------------------------>
LS Update
<------------------------------
LS Request
------------------------------>
LS Update
<------------------------------
Full
Figure 14: An adjacency bring-up example
11. The Routing Table Structure
The routing table data structure contains all the information
necessary to forward an IP data packet toward its destination. Each
routing table entry describes the collection of best paths to a
particular destination. When forwarding an IP data packet, the
routing table entry providing the best match for the packet's IP
destination is located. The matching routing table entry then
provides the next hop towards the packet's destination. OSPF also
provides for the existence of a default route (Destination ID =
DefaultDestination, Address Mask = 0x00000000). When the default
route exists, it matches all IP destinations (although any other
matching entry is a better match). Finding the routing table entry
that best matches an IP destination is further described in Section
11.1.
There is a single routing table in each router. Two sample routing
tables are described in Sections 11.2 and 11.3. The building of the
routing table is discussed in Section 16.
The rest of this section defines the fields found in a routing table
entry. The first set of fields describes the routing table entry's
destination.
Destination Type
Destination type is either "network" or "router". Only network entries
are actually used when forwarding IP data traffic. Router routing
table entries are used solely as intermediate steps in the routing
table build process.
A network is a range of IP addresses, to which IP data traffic may be
forwarded. This includes IP networks (class A, B, or C), IP subnets,
IP supernets and single IP hosts. The default route also falls into
this category.
Router entries are kept for area border routers and AS boundary
routers. Routing table entries for area border routers are used when
calculating the inter-area routes (see Section 16.2), and when
maintaining configured virtual links (see Section 15). Routing table
entries for AS boundary routers are used when calculating the AS
external routes (see Section 16.4).
Destination ID
The destination's identifier or name. This depends on the
Destination Type. For networks, the identifier is their associated IP
address. For routers, the identifier is the OSPF Router ID.[9]
Address Mask
Only defined for networks. The network's IP address together with its
address mask defines a range of IP addresses. For IP subnets, the
address mask is referred to as the subnet mask. For host routes, the
mask is "all ones" (0xffffffff).
Optional Capabilities
When the destination is a router this field indicates the optional
OSPF capabilities supported by the destination router. The only
optional capability defined by this specification is the ability to
process AS-external-LSAs. For a further discussion of OSPF's optional
capabilities, see Section 4.5.
The set of paths to use for a destination may vary based on the OSPF
area to which the paths belong. This means that there may be
multiple routing table entries for the same destination, depending on
the values of the next field.
Area
This field indicates the area whose link state information has led
to the routing table entry's collection of paths. This is called
the entry's associated area. For sets of AS external paths, this
field is not defined. For destinations of type "router", there
may be separate sets of paths (and therefore separate routing
table entries) associated with each of several areas. For example,
this will happen when two area border routers share multiple areas
in common. For destinations of type "network", only the set of
paths associated with the best area (the one providing the
preferred route) is kept.
The rest of the routing table entry describes the set of paths to the
destination. The following fields pertain to the set of paths as a
whole. In other words, each one of the paths contained in a routing
table entry is of the same path-type and cost (see below).
Path-type
There are four possible types of paths used to route traffic to
the destination, listed here in order of preference: intra-area,
inter-area, type 1 external or type 2 external. Intra-area paths
indicate destinations belonging to one of the router's attached
areas. Inter-area paths are paths to destinations in other OSPF
areas. These are discovered through the examination of received
summary-LSAs. AS external paths are paths to destinations
external to the AS. These are detected through the examination of
received AS-external-LSAs.
Cost
The link state cost of the path to the destination. For all paths
except type 2 external paths this describes the entire path's
cost. For Type 2 external paths, this field describes the cost of
the portion of the path internal to the AS. This cost is
calculated as the sum of the costs of the path's constituent
links.
Type 2 cost
Only valid for type 2 external paths. For these paths, this field
indicates the cost of the path's external portion. This cost has
been advertised by an AS boundary router, and is the most
significant part of the total path cost. For example, a type 2
external path with type 2 cost of 5 is always preferred over a
path with type 2 cost of 10, regardless of the cost of the two
paths' internal components.
Link State Origin
Valid only for intra-area paths, this field indicates the LSA
(router-LSA or network-LSA) that directly references the
destination. For example, if the destination is a transit
network, this is the transit network's network-LSA. If the
destination is a stub network, this is the router-LSA for the
attached router. The LSA is discovered during the shortest-path
tree calculation (see Section 16.1). Multiple LSAs may reference
the destination, however a tie-breaking scheme always reduces the
choice to a single LSA. The Link State Origin field is not used by
the OSPF protocol, but it is used by the routing table calculation
in OSPF's Multicast routing extensions (MOSPF).
When multiple paths of equal path-type and cost exist to a
destination (called elsewhere "equal-cost" paths), they are stored in
a single routing table entry. Each one of the "equal-cost" paths is
distinguished by the following fields:
Next hop
The outgoing router interface to use when forwarding traffic to
the destination. On broadcast, Point-to-MultiPoint and NBMA
networks, the next hop also includes the IP address of the next
router (if any) in the path towards the destination.
Advertising router
Valid only for inter-area and AS external paths. This field
indicates the Router ID of the router advertising the summary-LSA
or AS-external-LSA that led to this path.
11.1. Routing table lookup
When an IP data packet is received, an OSPF router finds the routing
table entry that best matches the packet's destination. This routing
table entry then provides the outgoing interface and next hop router
to use in forwarding the packet. This section describes the process
of finding the best matching routing table entry. The process
consists of a number of steps, wherein the collection of routing
table entries is progressively pruned. In the end, the single
routing table entry remaining is called the "best match".
Before the lookup begins, "discard" routing table entries should be
inserted into the routing table for each of the router's active area
address ranges (see Section 3.5). (An area range is considered
"active" if the range contains one or more networks reachable by
intra-area paths.) The destination of a "discard" entry is the set of
addresses described by its associated active area address range, and
the path type of each "discard" entry is set to "inter-area".[10]
Note that the steps described below may fail to produce a best match
routing table entry (i.e., all existing routing table entries are
pruned for some reason or another), or the best match routing table
entry may be one of the above "discard" routing table entries. In
these cases, the packet's IP destination is considered unreachable.
Instead of being forwarded, the packet should be discarded and an
ICMP destination unreachable message should be returned to the
packet's source.
(1) Select the complete set of "matching" routing table entries
from the routing table. Each routing table entry describes
a (set of) path(s) to a range of IP addresses. If the data
packet's IP destination falls into an entry's range of IP
addresses, the routing table entry is called a match. (It is
quite likely that multiple entries will match the data
packet. For example, a default route will match all
packets.)
(2) Reduce the set of matching entries to those having the most
preferential path-type (see Section 11). OSPF has a four
level hierarchy of paths. Intra-area paths are the most
preferred, followed in order by inter-area, type 1 external
and type 2 external paths.
(3) Select the remaining routing table entry that provides the
most specific (longest) match. Another way of saying this is
to choose the remaining entry that specifies the narrowest
range of IP addresses.[11] For example, the entry for the
address/mask pair of (128.185.1.0, 0xffffff00) is more
specific than an entry for the pair (128.185.0.0,
0xffff0000). The default route is the least specific match,
since it matches all destinations.
11.2. Sample routing table, without areas
Consider the Autonomous System pictured in Figure 2. No OSPF areas
have been configured. A single metric is shown per outbound
interface. The calculation of Router RT6's routing table proceeds as
described in Section 2.2. The resulting routing table is shown in
Table 12. Destination types are abbreviated: Network as "N", Router
as "R".
There are no instances of multiple equal-cost shortest paths in this
example. Also, since there are no areas, there are no inter-area
paths.
Routers RT5 and RT7 are AS boundary routers. Intra-area routes have
been calculated to Routers RT5 and RT7. This allows external routes
to be calculated to the destinations advertised by RT5 and RT7 (i.e.,
Networks N12, N13, N14 and N15). It is assumed all AS-external-LSAs
originated by RT5 and RT7 are advertising type 1 external metrics.
This results in type 1 external paths being calculated to
destinations N12-N15.
11.3. Sample routing table, with areas
Consider the previous example, this time split into OSPF areas. An
OSPF area configuration is pictured in Figure 6. Router RT4's
routing table will be described for this area configuration. Router
RT4 has a connection to Area 1 and a backbone connection. This
causes Router RT4 to view the AS as the concatenation of the two
graphs shown in Figures 7 and 8. The resulting routing table is
displayed in Table 13.
Type Dest Area Path Type Cost Next Adv.
Hop(s) Router(s)
____________________________________________________________
N N1 0 intra-area 10 RT3 *
N N2 0 intra-area 10 RT3 *
N N3 0 intra-area 7 RT3 *
N N4 0 intra-area 8 RT3 *
N Ib 0 intra-area 7 * *
N Ia 0 intra-area 12 RT10 *
N N6 0 intra-area 8 RT10 *
N N7 0 intra-area 12 RT10 *
N N8 0 intra-area 10 RT10 *
N N9 0 intra-area 11 RT10 *
N N10 0 intra-area 13 RT10 *
N N11 0 intra-area 14 RT10 *
N H1 0 intra-area 21 RT10 *
R RT5 0 intra-area 6 RT5 *
R RT7 0 intra-area 8 RT10 *
____________________________________________________________
N N12 * type 1 ext. 10 RT10 RT7
N N13 * type 1 ext. 14 RT5 RT5
N N14 * type 1 ext. 14 RT5 RT5
N N15 * type 1 ext. 17 RT10 RT7
Table 12: The routing table for Router RT6
(no configured areas).
Again, Routers RT5 and RT7 are AS boundary routers. Routers RT3,
RT4, RT7, RT10 and RT11 are area border routers. Note that there are
two routing entries for the area border router RT3, since it has two
areas in common with RT4 (Area 1 and the backbone).
Backbone paths have been calculated to all area border routers.
These are used when determining the inter-area routes. Note that all
of the inter-area routes are associated with the backbone; this is
always the case when the calculating router is itself an area border
router. Routing information is condensed at area boundaries. In
this example, we assume that Area 3 has been defined so that networks
N9-N11 and the host route to H1 are all condensed to a single route
when advertised into the backbone (by Router RT11). Note that the
cost of this route is the maximum of the set of costs to its
individual components.
There is a virtual link configured between Routers RT10 and RT11.
Without this configured virtual link, RT11 would be unable to
advertise a route for networks N9-N11 and Host H1 into the backbone,
and there would not be an entry for these networks in Router RT4's
routing table.
In this example there are two equal-cost paths to Network N12.
However, they both use the same next hop (Router RT5).
Type Dest Area Path Type Cost Next Adv.
Hops(s) Router(s)
__________________________________________________________________
N N1 1 intra-area 4 RT1 *
N N2 1 intra-area 4 RT2 *
N N3 1 intra-area 1 * *
N N4 1 intra-area 3 RT3 *
R RT3 1 intra-area 1 * *
__________________________________________________________________
N Ib 0 intra-area 22 RT5 *
N Ia 0 intra-area 27 RT5 *
R RT3 0 intra-area 21 RT5 *
R RT5 0 intra-area 8 * *
R RT7 0 intra-area 14 RT5 *
R RT10 0 intra-area 22 RT5 *
R RT11 0 intra-area 25 RT5 *
__________________________________________________________________
N N6 0 inter-area 15 RT5 RT7
N N7 0 inter-area 19 RT5 RT7
N N8 0 inter-area 18 RT5 RT7
N N9-N11,H1 0 inter-area 36 RT5 RT11
__________________________________________________________________
N N12 * type 1 ext. 16 RT5 RT5,RT7
N N13 * type 1 ext. 16 RT5 RT5
N N14 * type 1 ext. 16 RT5 RT5
N N15 * type 1 ext. 23 RT5 RT7
Table 13: Router RT4's routing table
in the presence of areas.
Router RT4's routing table would improve (i.e., some of the paths in
the routing table would become shorter) if an additional virtual link
were configured between Router RT4 and Router RT3. The new virtual
link would itself be associated with the first entry for area border
router RT3 in Table 13 (an intra-area path through Area 1). This
would yield a cost of 1 for the virtual link. The routing table
entries changes that would be caused by the addition of this virtual
link are shown in Table 14.
12. Link State Advertisements (LSAs)
Each router in the Autonomous System originates one or more link
state advertisements (LSAs). This memo defines five distinct types
of LSAs, which are described in Section 4.3. The collection of LSAs
forms the link-state database. Each separate type of LSA has a
separate function. Router-LSAs and network-LSAs describe how an
area's routers and networks are interconnected. Summary-LSAs provide
a way of condensing an area's routing information. AS-external-LSAs
provide a way of transparently advertising externally-derived routing
information throughout the Autonomous System.
Each LSA begins with a standard 20-byte header. This LSA header is
discussed below.
Type Dest Area Path Type Cost Next Adv.
Hop(s) Router(s)
________________________________________________________________
N Ib 0 intra-area 16 RT3 *
N Ia 0 intra-area 21 RT3 *
R RT3 0 intra-area 1 * *
R RT10 0 intra-area 16 RT3 *
R RT11 0 intra-area 19 RT3 *
________________________________________________________________
N N9-N11,H1 0 inter-area 30 RT3 RT11