RFC 1247
OSPF Version 2
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
Done is generated. Otherwise, it should send a new Database
Description to the slave.
Slave
Sets the sequence number to the sequence number appearing in the
received packet. The slave must send a Database Description in
reply. If the received packet has the more bit (M) set to 0, and
the packet to be sent by the slave will have the M-bit set to 0
also, the neighbor event Exchange Done 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
link state advertisements 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 link state advertisement 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 link state advertisements should NOT be placed on the Link state retransmission list for the neighbor. If a link state advertisement cannot be found in the database, something has gone wrong with the synchronization procedure, 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 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. There are currently two optional capabilities defined. The T-bit should be set if and only 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 network belongs to a non-stub area. The rest of 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 link state advertisement in the area's topological database (at the time the neighbor transitions into Exchange state) is listed in the neighbor Database summary list. When a new Database Description Packet is to be sent, the packet's sequence number is incremented, and the (new) top of the Database summary list is described by the packet. Items are removed from the Database summary list when the previous packet is acknowledged. In state Exchange, the determination of when to send a packet depends on whether the router is master or slave:
Master
Packets are sent when either a) the slave acknowledges the previous
packet by echoing the sequence number or b) RxmtInterval seconds
elapse without an acknowledgment, in which case the previous packet
is retransmitted.
Slave
Packets are sent only in response to packets received from the
master. If the packet received from the master is new, a new packet
is sent, otherwise the previous packet is resent.
In states Loading and Full the slave must resend its last packet in
response to duplicate packets received from the master. For this reason
the slave must wait RouterDeadInterval seconds before freeing the last
packet. Reception of a packet from the master after this interval will
generate a Seq Number Mismatch 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 link state advertisements that need to be
obtained from the neighbor. To request these advertisements, 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 Requests
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 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 that 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 hellos, 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 indicates that it is itself the Designated Router and that it has heard hellos 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 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. 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. ________________________________________ (Figure not included in text version.) Figure 14: An adjacency bring-up example ________________________________________
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). 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
The destination can be one of three types. Only the first type,
Network, is actually used when forwarding IP data traffic. The
other destinations are used solely as intermediate steps in the
routing table build process.
Network
A range of IP addresses, to which IP data traffic may be
forwarded. This includes IP networks (class A, B, or C), IP
subnets, and single IP hosts. The default route also falls in
this category.
Area border router
Routers that are connected to multiple OSPF areas. Such routers
originate summary link advertisements. These routing table
entries are used when calculating the inter-area routes (see
Section 16.2). These routing table entries may also be
associated with configured virtual links.
AS boundary router
Routers that originate AS external link advertisements. These
routing table entries 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's type. For networks, the identifier is their
associated IP address. For all other types, 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 (either an area border router or an
AS boundary router) this field indicates the optional OSPF
capabilities supported by the destination router. The two optional
capabilities currently defined by this specification are the ability
to route based on IP TOS and the ability to process AS external
advertisements. 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 IP Type of
Service and 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 two fields.
Type of Service
There can be a separate set of routes for each IP Type of Service.
The encoding of TOS in OSPF link state advertisements is described
in Section 12.3.
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 "area border
router", there may be separate sets of paths (and therefore separate
routing table entries) associated with each of several areas. This
will happen when two area border routers share multiple areas in
common. For all other destination types, only the set of paths
associated with the best area (the one providing the shortest 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
link advertisements. AS external paths are paths to destinations
external to the AS. These are detected through the examination of
received AS external link advertisements.
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, an external
type 2 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 link state
advertisement (router links or network links) that directly
references the destination. For example, if the destination is a
transit network, this is the transit network's network links
advertisement. If the destination is a stub network, this is the
router links advertisement for the attached router. The
advertisement is discovered during the shortest-path tree
calculation (see Section 16.1). Multiple advertisements may
reference the destination, however a tie-breaking scheme always
reduces the choice to a single advertisement.
This field is for informational purposes only. The advertisement
could be used as a root for an SPF calculation when building a
reverse path forwarding tree. This is beyond the scope of this
specification.
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 multi-access networks, the next hop also includes
the IP address of the next router (if any) in the path towards the
destination. This next router will always be one of the adjacent
neighbors.
Advertising router
Valid only for inter-area and AS external paths. This field
indicates the Router ID of the router advertising the summary link
or AS external link 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 the called best match.
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). In this case, the packet's IP destination
is considered unreachable. Instead of being forwarded, the packet should
be dropped 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) Suppose that the packet's IP destination falls into one of the
router's configured area address ranges (see Section 3.5), and that
the particular area address range is active. This means that there
are one or more reachable (by intra-area paths) networks contained
in the area address range. The packet's IP destination is then
required to belong to one of these constituent networks. For this
reason, only matching routing table entries with path-type of
intra-area are considered (all others are pruned). If no such
matching entries exist, the destination is unreachable (see above).
Otherwise, skip to step 4.
(3) 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.
(4) Select the remaining routing table entry that provides the longest
(most specific) match. Another way of saying this is to choose the
remaining entry that specifies the narrowest range of IP
addresses.[10] 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.
(5) At this point, there may still be multiple routing table entries
remaining. Each routing entry will specify the same range of IP
addresses, but a different IP Type of Service. Select the routing
table entry whose TOS value matches the TOS found in the packet
header. If there is no routing table entry for this TOS, select the
routing table entry for TOS 0. In other words, packets requesting
TOS X are routed along the TOS 0 path if a TOS X path does not
exist.
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,
indicating that routes will not vary based on TOS. The calculation
router RT6's routing table proceeds as described in Section 2.1. The
resulting routing table is shown in Table 12. Destination types are
abbreviated: Network as "N", area border router as "BR" and AS boundary
router as "ASBR".
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
advertisements 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. 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 (in this case having identical paths) for router RT7, in its dual capacities as an area border router and an AS boundary router. Note also 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 (BR). These are used when determining the inter-area routes. Note that all of Type Dest Area Path Type Cost Next Hop(s) Adv. 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 * ASBR RT5 0 intra-area 6 RT5 * ASBR RT7 0 intra-area 8 RT10 * __________________________________________________________________________ N N12 * type 1 external 10 RT10 RT7 N N13 * type 1 external 14 RT5 RT5 N N14 * type 1 external 14 RT5 RT5 N N15 * type 1 external 17 RT10 RT7 Table 12: The routing table for Router RT6 (no configured areas).
the inter-area routes are associated with the backbone; this is always the case when the 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 to the backbone (by router RT11). Note that the cost of this route is the minimum 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). 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.
(page 81 continued on part 4)
