tech-invite   World Map     

3GPP     Specs     Glossaries     Architecture     IMS     UICC       IETF     RFCs     Groups     SIP     ABNFs       Search

RFC 1247

 
 
 

OSPF Version 2

Part 3 of 7, p. 54 to 81
Prev RFC Part       Next RFC Part

 


prevText      Top       Page 54 
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,

Top       Page 55 
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

Top       Page 56 
    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

Top       Page 57 
    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)
         _____________________________________________________

Top       Page 58 
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.

Top       Page 59 
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.

Top       Page 60 
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.

Top       Page 61 
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

Top       Page 62 
    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

Top       Page 63 
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

Top       Page 64 
   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,

Top       Page 65 
            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

Top       Page 66 
   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.

Top       Page 67 
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

Top       Page 68 
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.

Top       Page 69 
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.

Top       Page 70 
    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

Top       Page 71 
    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

Top       Page 72 
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:

Top       Page 73 
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

Top       Page 74 
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
                ________________________________________

Top       Page 75 
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

Top       Page 76 
    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

Top       Page 77 
    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:

Top       Page 78 
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

Top       Page 79 
    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.

Top       Page 80 
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).

Top       Page 81 
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)

Next RFC Part