Interface Up
Lower-level protocols have indicated that the network interface is
operational. This enables the interface to transition out of Down
state. On virtual links, the interface operational indication is
actually a result of the shortest path calculation (see Section
16.7).
Wait Timer
The Wait timer has fired, indicating the end of the waiting period
that is required before electing a (Backup) Designated Router.
Backup seen
The router has detected the existence or non-existence of a Backup
Designated Router for the network. This is done in one of two ways.
First, a Hello Packet may be received from a neighbor claiming to be
itself the Backup Designated Router. Alternatively, a Hello Packet
may be received from a neighbor claiming to be itself the Designated
Router, and indicating that there is no Backup. In either case
there must be bidirectional communication with the neighbor, i.e.,
the router must also appear in the neighbor's Hello Packet. This
event signals an end to the Waiting state.
Neighbor Change
There has been a change in the set of bidirectional neighbors
associated with the interface. The (Backup) Designated Router needs
to be recalculated. The following neighbor changes lead to the
Neighbor Change event. For an explanation of neighbor states, see
Section 10.1.
o Bidirectional communication has been established to a neighbor.
In other words, the state of the neighbor has transitioned to
2-Way or higher.
o There is no longer bidirectional communication with a neighbor.
In other words, the state of the neighbor has transitioned to
Init or lower.
o One of the bidirectional neighbors is newly declaring itself as
either Designated Router or Backup Designated Router. This is
detected through examination of that neighbor's Hello Packets.
o One of the bidirectional neighbors is no longer declaring itself
as Designated Router, or is no longer declaring itself as Backup
Designated Router. This is again detected through examination
of that neighbor's Hello Packets.
o The advertised Router Priority for a bidirectional neighbor has
changed. This is again detected through examination of that
neighbor's Hello Packets.
Loop Ind
An indication has been received that the interface is now looped
back to itself. This indication can be received either from network
management or from the lower level protocols.
Unloop Ind
An indication has been received that the interface is no longer
looped back. As with the Loop Ind event, this indication can be
received either from network management or from the lower level
protocols.
Interface Down
Lower-level protocols indicate that this interface is no longer
functional. No matter what the current interface state is, the new
interface state will be Down.
9.3 The Interface state machine
A detailed description of the interface state changes follows. Each
state change is invoked by an event (Section 9.2). This event may
produce different effects, depending on the current state of the
interface. For this reason, the state machine below is organized by
current interface state and received event. Each entry in the state
machine describes the resulting new interface state and the required set
of additional actions.
When an interface's state changes, it may be necessary to originate a
new router links advertisement. See Section 12.4 for more details.
Some of the required actions below involve generating events for the
neighbor state machine. For example, when an interface becomes
inoperative, all neighbor connections associated with the interface must
be destroyed. For more information on the neighbor state machine, see
Section 10.3.
State(s): Down
Event: Interface Up
New state: Depends on action routine
Action: Start the interval Hello Timer, enabling the periodic
sending of Hello packets out the interface. If the attached
network is a physical point-to-point network or virtual
link, the interface state transitions to Point-to-Point.
Else, if the router is not eligible to become Designated
Router the interface state transitions to DR other.
Otherwise, the attached network is multi-access and the
router is eligible to become Designated Router. In this
case, in an attempt to discover the attached network's
Designated Router the interface state is set to Waiting and
the single shot Wait Timer is started. If in addition the
attached network is non-broadcast, examine the configured
list of neighbors for this interface and generate the
neighbor event Start for each neighbor that is also eligible
to become Designated Router.
State(s): Waiting
Event: Backup Seen
New state: Depends upon action routine.
Action: Calculate the attached network's Backup Designated Router
and Designated Router, as shown in Section 9.4. As a result
of this calculation, the new state of the interface will be
either DR other, Backup or DR.
State(s): Waiting
Event: Wait Timer
New state: Depends upon action routine.
Action: Calculate the attached network's Backup Designated Router
and Designated Router, as shown in Section 9.4. As a result
of this calculation, the new state of the interface will be
either DR other, Backup or DR.
State(s): DR Other, Backup or DR
Event: Neighbor Change
New state: Depends upon action routine.
Action: Recalculate the attached network's Backup Designated Router
and Designated Router, as shown in Section 9.4. As a result
of this calculation, the new state of the interface will be
either DR other, Backup or DR.
State(s): Any State
Event: Interface Down
New state: Down
Action: All interface variables are reset, and interface timers
disabled. Also, all neighbor connections associated with
the interface are destroyed. This is done by generating the
event KillNbr on all associated neighbors (see Section
10.2).
State(s): Any State
Event: Loop Ind
New state: Loopback
Action: Since this interface is no longer connected to the attached
network the actions associated with the above Interface Down
event are executed.
State(s): Loopback
Event: Unloop Ind
New state: Down
Action: No actions are necessary. For example, the interface
variables have already been reset upon entering the Loopback
state. Note that reception of an Interface Up event is
necessary before the interface again becomes fully
functional.
9.4 Electing the Designated Router
This section describes the algorithm used for calculating a network's
Designated Router and Backup Designated Router. This algorithm is
invoked by the Interface state machine. The initial time a router runs
the election algorithm for a network, the network's Designated Router
and Backup Designated Router are initialized to 0.0.0.0. This indicates
the lack of both a Designated Router and a Backup Designated Router.
The Designated Router election algorithm proceeds as follows: Call the
router doing the calculation Router X. The list of neighbors attached
to the network and having established bidirectional communication with
Router X is examined. This list is precisely the collection of Router
X's neighbors (on this network) whose state is greater than or equal to
2-Way (see Section 10.1). Router X itself is also considered to be on
the list. Discard all routers from the list that are ineligible to
become Designated Router. (Routers having Router Priority of 0 are
ineligible to become Designated Router.) The following steps are then
executed, considering only those routers that remain on the list:
(1) Note the current values for the network's Designated Router and
Backup Designated Router. This is used later for comparison
purposes.
(2) Calculate the new Backup Designated Router for the network as
follows. Only those routers on the list that have not declared
themselves to be Designated Router are eligible to become Backup
Designated Router. If one or more of these routers have declared
themselves Backup Designated Router (i.e., they are currently
listing themselves as Backup Designated Router, but not as
Designated Router, in their Hello Packets) the one having highest
Router Priority is declared to be Backup Designated Router. In case
of a tie, the one having the highest Router ID is chosen. If no
routers have declared themselves Backup Designated Router, choose
the router having highest Router Priority, (again excluding those
routers who have declared themselves Designated Router), and again
use the Router ID to break ties.
(3) Calculate the new Designated Router for the network as follows. If
one or more of the routers have declared themselves Designated
Router (i.e., they are currently listing themselves as Designated
Router in their Hello Packets) the one having highest Router
Priority is declared to be Designated Router. In case of a tie, the
one having the highest Router ID is chosen. If no routers have
declared themselves Designated Router, promote the new Backup
Designated Router to Designated Router.
(4) If Router X is now newly the Designated Router or newly the Backup
Designated Router, or is now no longer the Designated Router or no
longer the Backup Designated Router, repeat steps 2 and 3, and then
proceed to step 5. For example, if Router X is now the Designated
Router, when step 2 is repeated X will no longer be eligible for
Backup Designated Router election. Among other things, this will
ensure that no router will declare itself both Backup Designated
Router and Designated Router.[5]
(5) As a result of these calculations, the router itself may now be
Designated Router or Backup Designated Router. See Sections 7.3 and
7.4 for the additional duties this would entail. The router's
interface state should be set accordingly. If the router itself is
now Designated Router, the new interface state is DR. If the router
itself is now Backup Designated Router, the new interface state is
Backup. Otherwise, the new interface state is DR Other.
(6) If the attached network is non-broadcast, and the router itself has
just become either Designated Router or Backup Designated Router, it
must start sending hellos to those neighbors that are not eligible
to become Designated Router (see Section 9.5.1). This is done by
invoking the neighbor event Start for each neighbor having a Router
Priority of 0.
(7) If the above calculations have caused the identity of either the
Designated Router or Backup Designated Router to change, the set of
adjacencies associated with this interface will need to be modified.
Some adjacencies may need to be formed, and others may need to be
broken. To accomplish this, invoke the event AdjOK? on all
neighbors whose state is at least 2-Way. This will cause their
eligibility for adjacency to be reexamined (see Sections 10.3 and
10.4).
The reason behind the election algorithm's complexity is the desire for
an orderly transition from Backup Designated Router to Designated
Router, when the current Designated Router fails. This orderly
transition is ensured through the introduction of hysteresis: no new
Backup router can be chosen until the old Backup accepts its new
Designated Router responsibilities.
If Router X is not itself eligible to become Designated Router, it is
possible that neither a Backup Designated Router nor a Designated Router
will be selected in the above procedure. Note also that if Router X is
the only attached router that is eligible to become Designated Router,
it will select itself as Designated Router and there will be no Backup
Designated Router for the network.
9.5 Sending Hello packets
Hello packets are sent out each functioning router interface. They are
used to discover and maintain neighbor relationships.[6] On multi-access
networks, hellos are also used to elect the Designated Router and Backup
Designated Router, and in that way determine what adjacencies should be
formed.
The format of a Hello packet is detailed in Section A.3.2. The Hello
Packet contains the router's Router Priority (used in choosing the
Designated Router), and the interval between Hello broadcasts
(HelloInterval). The Hello Packet also indicates how often a neighbor
must be heard from to remain active (RouterDeadInterval). Both
HelloInterval and RouterDeadInterval must be the same for all routers
attached to a common network. The Hello packet also contains the IP
address mask of the attached network (Network Mask). On unnumbered
point-to-point networks and on virtual links this field should be set to
0.
The Hello packet's Options field describes the router's optional OSPF
capabilities. There are currently two optional capabilities defined
(see Sections 4.5 and A.2). The T-bit of the Options field should be
set if the router is capable of calculating separate routes for each IP
TOS. The E-bit should be set if and only if the attached area is
capable of processing AS external advertisements (i.e., it is not a stub
area). If the E-bit is set incorrectly the neighboring routers will
refuse to accept the Hello Packet (see Section 10.5). The rest of the
Hello Packet's Options field should be set to zero.
In order to ensure two-way communication between adjacent routers, the
Hello packet contains the list of all routers from which hellos have
been seen recently. The Hello packet also contains the router's current
choice for Designated Router and Backup Designated Router. A value of 0
in these fields means that one has not yet been selected.
On broadcast networks and physical point-to-point networks, Hello
packets are sent every HelloInterval seconds to the IP multicast address
AllSPFRouters. On virtual links, Hello packets are sent as unicasts
(addressed directly to the other end of the virtual link) every
HelloInterval seconds. On non-broadcast networks, the sending of Hello
packets is more complicated. This will be covered in the next section.
9.5.1 Sending Hello packets on non-broadcast networks
Static configuration information is necessary in order for the Hello
Protocol to function on non-broadcast networks (see Section C.5). Every
attached router which is eligible to become Designated Router has a
configured list of all of its neighbors on the network. Each listed
neighbor is labelled with its Designated Router eligibility.
The interface state must be at least Waiting for any hellos to be sent.
Hellos are then sent directly (as unicasts) to some subset of a router's
neighbors. Sometimes an hello is sent periodically on a timer; at other
times it is sent as a response to a received hello. A router's hello-
sending behavior varies depending on whether the router itself is
eligible to become Designated Router.
If the router is eligible to become Designated Router, it must
periodically send hellos to all neighbors that are also eligible. In
addition, if the router is itself the Designated Router or Backup
Designated Router, it must also send periodic hellos to all other
neighbors. This means that any two eligible routers are always
exchanging hellos, which is necessary for the correct operation of the
Designated Router election algorithm. To minimize the number of hellos
sent, the number of eligible routers on a non-broadcast network should
be kept small.
If the router is not eligible to become Designated Router, it must
periodically send hellos to both the Designated Router and the Backup
Designated Router (if they exist). It must also send an hello in reply
to an hello received from any eligible neighbor (other than the current
Designated Router and Backup Designated Router). This is needed to
establish an initial bidirectional relationship with any potential
Designated Router.
When sending Hello packets periodically to any neighbor, the interval
between hellos is determined by the neighbor's state. If the neighbor
is in state Down, hellos are sent every PollInterval seconds.
Otherwise, hellos are sent every HelloInterval seconds.
10. The Neighbor Data Structure
An OSPF router converses with its neighboring routers. Each separate
conversation is described by a "neighbor data structure". Each
conversation is bound to a particular OSPF router interface, and is
identified either by the neighboring router's OSPF router ID or by its
Neighbor IP address (see below). Thus if the OSPF router and another
router have multiple attached networks in common, multiple conversations
ensue, each described by a unique neighbor data structure. Each
separate conversation is loosely referred to in the text as being a
separate "neighbor".
The neighbor data structure contains all information pertinent to the
forming or formed adjacency between the two neighbors. (However,
remember that not all neighbors become adjacent.) An adjacency can be
viewed as a highly developed conversation between two routers.
State
The functional level of the neighbor conversation. This is
described in more detail in Section 10.1.
Inactivity Timer
A single shot timer whose firing indicates that no Hello Packet has
been seen from this neighbor recently. The length of the timer is
RouterDeadInterval seconds.
Master/Slave
When the two neighbors are exchanging databases, they form a Master
Slave relationship. The Master sends the first Database Description
Packet, and is the only part that is allowed to retransmit. The
slave can only respond to the master's Database Description Packets.
The master/slave relationship is negotiated in state ExStart.
Sequence Number
A 32-bit number identifying individual Database Description packets.
When the neighbor state ExStart is entered, the sequence number
should be set to a value not previously seen by the neighboring
router. One possible scheme is to use the machine's time of day
counter. The sequence number is then incremented by the master with
each new Database Description packet sent. The slave's sequence
number indicates the last packet received from the master. Only one
packet is allowed outstanding at a time.
Neighbor ID
The OSPF Router ID of the neighboring router. The neighbor ID is
learned when Hello packets are received from the neighbor, or is
configured if this is a virtual adjacency (see Section C.4).
Neighbor priority
The Router Priority of the neighboring router. Contained in the
neighbor's Hello packets, this item is used when selecting the
Designated Router for the attached network.
Neighbor IP address
The IP address of the neighboring router's interface to the attached
network. Used as the Destination IP address when protocol packets
are sent as unicasts along this adjacency. Also used in router
links advertisements as the Link ID for the attached network if the
neighboring router is selected to be Designated Router (see Section
12.4.1). The neighbor IP address is learned when Hello packets are
received from the neighbor. For virtual links, the neighbor IP
address is learned during the routing table build process (see
Section 15).
Neighbor Options
The optional OSPF capabilities supported by the neighbor. Learned
during the Database Exchange process (see Section 10.6). The
neighbor's optional OSPF capabilities are also listed in its Hello
packets. This enables received Hellos to be rejected (i.e.,
neighbor relationships will not even start to form) if there is a
mismatch in certain crucial OSPF capabilities (see Section 10.5).
The optional OSPF capabilities are documented in Section 4.5.
Neighbor's Designated Router
The neighbor's idea of the Designated Router. If this is the
neighbor itself, this is important in the local calculation of the
Designated Router. Defined only on multi-access networks.
Neighbor's Backup Designated Router
The neighbor's idea of the Backup Designated Router. If this is the
neighbor itself, this is important in the local calculation of the
Backup Designated Router. Defined only on multi-access networks.
The next set of variables are lists of link state advertisements. These
lists describe subsets of the area topological database. There can be
five distinct types of link state advertisements in an area topological
database: router links, network links, and type 3 and 4 summary links
(all stored in the area data structure), and AS external links (stored
in the global data structure).
Link state retransmission list
The list of link state advertisements that have been flooded but not
acknowledged on this adjacency. These will be retransmitted at
intervals until they are acknowledged, or until the adjacency is
destroyed.
Database summary list
The complete list of link state advertisements that make up the area
topological database, at the moment the neighbor goes into Database
Exchange state. This list is sent to the neighbor in Database
Description packets.
Link state request list
The list of link state advertisements that need to be received from
this neighbor in order to synchronize the two neighbors' topological
databases. This list is created as Database Description packets are
received, and is then sent to the neighbor in Link State Request
packets. The list is depleted as appropriate Link State Update
packets are received.
10.1 Neighbor states
The state of a neighbor (really, the state of a conversation being held
with a neighboring router) is documented in the following sections. The
states are listed in order of progressing functionality. For example,
the inoperative state is listed first, followed by a list of
intermediate states before the final, fully functional state is
achieved. The specification makes use of this ordering by sometimes
making references such as "those neighbors/adjacencies in state greater
than X". Figures 12 and 13 show the graph of neighbor state changes.
The arcs of the graphs are labelled with the event causing the state
change. The neighbor events are documented in Section 10.2.
The graph in Figure 12 show the state changes effected by the Hello
Protocol. The Hello Protocol is responsible for neighbor acquisition
and maintenance, and for ensuring two way communication between
neighbors.
The graph in Figure 13 shows the forming of an adjacency. Not every two
neighboring routers become adjacent (see Section 10.4). The adjacency
starts to form when the neighbor is in state ExStart. After the two
routers discover their master/slave status, the state transitions to
Exchange. At this point the neighbor starts to be used in the flooding
procedure, and the two neighboring routers begin synchronizing their
databases. When this synchronization is finished, the neighbor is in
state Full and we say that the two routers are fully adjacent. At this
point the adjacency is listed in link state advertisements.
For a more detailed description of neighbor state changes, together with
the additional actions involved in each change, see Section 10.3.
_____________________________________________________
(Figures not included in text version.)
Figure 12: Neighbor state changes (Hello Protocol)
Figure 13: Neighbor state changes (Database Exchange)
_____________________________________________________
Down
This is the initial state of a neighbor conversation. It indicates
that there has been no recent information received from the
neighbor. On non-broadcast networks, Hello packets may still be
sent to "Down" neighbors, although at a reduced frequency (see
Section 9.5.1).
Attempt
This state is only valid for neighbors attached to non-broadcast
networks. It indicates that no recent information has been received
from the neighbor, but that a more concerted effort should be made
to contact the neighbor. This is done by sending the neighbor Hello
packets at intervals of HelloInterval (see Section 9.5.1).
Init
In this state, an Hello packet has recently been seen from the
neighbor. However, bidirectional communication has not yet been
established with the neighbor (i.e., the router itself did not
appear in the neighbor's Hello packet). All neighbors in this state
(or higher) are listed in the Hello packets sent from the associated
interface.
2-Way
In this state, communication between the two routers is
bidirectional. This has been assured by the operation of the Hello
Protocol. This is the most advanced state short of beginning
adjacency establishment. The (Backup) Designated Router is selected
from the set of neighbors in state 2-Way or greater.
ExStart
This is the first step in creating an adjacency between the two
neighboring routers. The goal of this step is to decide which
router is the master, and to decide upon the initial sequence
number. Neighbor conversations in this state or greater are called
adjacencies.
Exchange
In this state the router is describing its entire link state
database by sending Database Description packets to the neighbor.
Each Database Description Packet has a sequence number, and is
explicitly acknowledged. Only one Database Description Packet is
allowed outstanding at any one time. In this state, Link State
Request Packets may also be sent asking for the neighbor's more
recent advertisements. 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 advertisements 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 links and network links
advertisements.
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:
Hello Received
A Hello packet has been received from a 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 non-broadcast networks.
2-Way Received
Bidirectional communication has been realized between the two
neighboring routers. This is indicated by this router seeing itself
in the other's Hello packet.
NegotiationDone
The Master/Slave relationship has been negotiated, and 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.
Exchange Done
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 a link state
advertisement not contained in the database. This indicates an
error in the synchronization 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 Description Process has completed.
AdjOK?
A decision must be made (again) 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.
Seq Number Mismatch
A Database Description packet has been received that either a) has
an unexpected 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 this
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.
Inactivity Timer
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 an neighbor's state changes, it may be necessary to rerun the
Designated Router election algorithm. This is determined by whether the
interface Neighbor Change 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 links
advertisement 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 to the neighbor (this neighbor is always
associated with a non-broadcast 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: Hello Received
New state: Init
Action: Restart the inactivity timer for the neighbor, since the
neighbor has now been heard from.
State(s): Down
Event: Hello Received
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: Hello Received
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-Way Received
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 sequence number for this neighbor. If
this is the first time that an adjacency has been attempted,
the 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: NegDone
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 links,
network links and summary links contained in the area
structure, along with the AS external links contained in the
global structure. AS external link advertisements are
omitted from a virtual neighbor's Database summary list. AS
external advertisements are omitted from the Database
summary list if the area has been configured as a stub (see
Section 3.6). Advertisements 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 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: Exchange Done
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 advertisements (which were discovered but not
yet received in the Exchange state). These advertisements
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-Way
Received.
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 link state
advertisements.
State(s): Exchange or greater
Event: Seq Number Mismatch
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 link state advertisements. Then
the router increments the sequence number for this neighbor,
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 link state
advertisements. 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 link state
advertisements. Also, the inactivity timer is disabled.
State(s): Any state
Event: Inactivity Timer
New state: Down
Action: The Link state retransmission list, Database summary list
and Link state request list are cleared of link state
advertisements.
State(s): 2-Way or greater
Event: 1-Way Received
New state: Init
Action: The Link state retransmission list, Database summary list
and Link state request list are cleared of link state
advertisements.
State(s): 2-Way or greater
Event: 2-Way received
New state: No state change.
Action: No action required.
State(s): Init
Event: 1-Way received
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 and virtual links always
become adjacent. On multi-access 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 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, HelloInt, and DeadInt 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. Note that the value of the Network
Mask field should not be checked in Hellos received on unnumbered serial
lines or on virtual links.
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
option field must match this area's external routing capability. If AS
external advertisements are not flooded into/throughout the area (i.e,
the area is a "stub") the E-bit must be clear in received hellos,
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 option 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 is a multi-access network (either broadcast or non-broadcast)
the source is identified by the IP source address found in the Hello's
IP header. If the receiving interface is 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 multi-access network
(broadcast or non-broadcast), 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 Hello Received.
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-Way Received.
Otherwise, the neighbor state machine should be executed with the
event 1-Way Received, 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 set 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 Designated Router item in the neighbor structure is set
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 Backup Designated
Router item in the neighbor structure is set accordingly.
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). The further processing
of the Database Description Packet depends on the neighbor state. If
the neighbor's state is Down or Attempt the packet should be ignored.
Otherwise, if the state is:
Init
The neighbor state machine should be executed with the event 2-Way
Received. This causes an immediate state change to either state 2-
Way or state Exstart. The processing of the current packet should
then continue in this new state.
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 sequence
number to that specified by the master.
o The initialize(I) and master(MS) bits are off, the packet's
sequence number equals the router's own 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
If the state of the MS-bit is inconsistent with the master/slave
state of the connection, generate the neighbor event Seq Number
Mismatch and stop processing the packet. Otherwise:
o If the initialize(I) bit is set, generate the neighbor event Seq
Number Mismatch 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 Seq Number
Mismatch and stop processing the packet.
o If the router is master, and the packet's sequence number equals
the router's own sequence number (this packet is the next in
sequence) the packet should be accepted and its contents
processed (below).
o If the router is master, and the packet's sequence number is one
less than the router's sequence number, the packet is a
duplicate. Duplicates should be discarded by the master.
o If the router is slave, and the packet's sequence number is one
more than the router's own sequence number (this packet is the
next in sequence) the packet should be accepted and its contents
processed (below).
o If the router is slave, and the packet's sequence number is
equal to the router's sequence number, the packet is a
duplicate. The slave must respond to duplicates by repeating
the last Database Description packet that it sent.
o Else, generate the neighbor event Seq Number Mismatch and stop
processing the packet.
Loading or Full
In this state, the router has sent and received an entire sequence
of Database Descriptions. 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 Seq Number Mismatch.[8] Duplicates
should be discarded by the master. The slave must respond to
duplicates by repeating the last Database Description packet that it
sent.
When the router accepts a received Database Description Packet as the
next in sequence the packet contents are processed as follows. For each
link state advertisement listed, the advertisement'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 a AS external
advertisement (LS type = 5) and the neighbor is associated with a stub
area, generate the neighbor event Seq Number Mismatch and stop
processing the packet. Otherwise, the router looks up the advertisement
in its database to see whether it also has an instance of the link state
advertisement. If it does not, or if the database copy is less recent
(see Section 13.1), the link state advertisement 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 sequence number. If the router has already sent its
entire sequence of Database Descriptions, and the just accepted
packet has the more bit (M) set to 0, the neighbor event Exchange