tech-invite   World Map     

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

RFC 1583

 
 
 

OSPF Version 2

Part 4 of 9, p. 75 to 100
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 75 
    10.2.  Events causing neighbor state changes

        State changes can be effected by a number of events.  These
        events are shown in the labels of the arcs in Figures 12 and 13.
        The label definitions are as follows:


        HelloReceived
            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-WayReceived
            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 DD
            sequence numbers have been exchanged.  This signals the
            start of the sending/receiving of Database Description
            packets.  For more information on the generation of this
            event, consult Section 10.8.

        ExchangeDone
            Both routers have successfully transmitted a full sequence
            of Database Description packets.  Each router now knows what
            parts of its link state database are out of date.  For more
            information on the generation of this event, consult Section

Top      Up      ToC       Page 76 
            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 Database Exchange process.

        Loading Done
            Link State Updates have been received for all out-of-date
            portions of the database.  This is indicated by the Link
            state request list becoming empty after the Database
            Exchange process has completed.

        AdjOK?
            A decision must be made (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.


        SeqNumberMismatch
            A Database Description packet has been received that either
            a) has an unexpected DD sequence number, b) unexpectedly has
            the Init bit set or c) has an Options field differing from
            the last Options field received in a Database Description
            packet.  Any of these conditions indicate that some error
            has occurred during adjacency establishment.

        1-Way
            An Hello packet has been received from the neighbor, in
            which 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.

        InactivityTimer
            The inactivity Timer has fired.  This means that no Hello
            packets have been seen recently from the neighbor.  The
            neighbor reverts to Down state.

Top      Up      ToC       Page 77 
        LLDown
            This is an indication from the lower level protocols that
            the neighbor is now unreachable.  For example, on an X.25
            network this could be indicated by an X.25 clear indication
            with appropriate cause and diagnostic fields.  This event
            forces the neighbor into Down state.


    10.3.  The Neighbor state machine

        A detailed description of the neighbor state changes follows.
        Each state change is invoked by an event (Section 10.2).  This
        event may produce different effects, depending on the current
        state of the neighbor.  For this reason, the state machine below
        is organized by current neighbor state and received event.  Each
        entry in the state machine describes the resulting new neighbor
        state and the required set of additional actions.

        When a neighbor's state changes, it may be necessary to rerun
        the Designated Router election algorithm.  This is determined by
        whether the interface NeighborChange event is generated (see
        Section 9.2).  Also, if the Interface is in DR state (the router
        is itself Designated Router), changes in neighbor state may
        cause a new network 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 Packet 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

Top      Up      ToC       Page 78 
            Event:  HelloReceived

        New state:  Init

           Action:  Restart the Inactivity Timer for the neighbor, since
                    the neighbor has now been heard from.


         State(s):  Down

            Event:  HelloReceived

        New state:  Init

           Action:  Start the Inactivity Timer for the neighbor.  The
                    timer's later firing would indicate that the
                    neighbor is dead.


         State(s):  Init or greater

            Event:  HelloReceived

        New state:  No state change.

           Action:  Restart the Inactivity Timer for the neighbor, since
                    the neighbor has again been heard from.


         State(s):  Init

            Event:  2-WayReceived

        New state:  Depends upon action routine.

           Action:  Determine whether an adjacency should be established
                    with the neighbor (see Section 10.4).  If not, the
                    new neighbor state is 2-Way.

                    Otherwise (an adjacency should be established) the
                    neighbor state transitions to ExStart.  Upon
                    entering this state, the router increments the DD
                    sequence number for this neighbor.  If this is the
                    first time that an adjacency has been attempted, the
                    DD sequence number should be assigned some unique
                    value (like the time of day clock).  It then
                    declares itself master (sets the master/slave bit to
                    master), and starts sending Database Description

Top      Up      ToC       Page 79 
                    Packets, with the initialize (I), more (M) and
                    master (MS) bits set.  This Database Description
                    Packet should be otherwise empty.  This Database
                    Description Packet should be retransmitted at
                    intervals of RxmtInterval until the next state is
                    entered (see Section 10.8).


         State(s):  ExStart

            Event:  NegotiationDone

        New state:  Exchange

           Action:  The router must list the contents of its entire area
                    link state database in the neighbor Database summary
                    list.  The area link state database consists of the
                    router 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 DD sequence number, and is
                    explicitly acknowledged.  Only one Database
                    Description Packet is allowed outstanding at any one
                    time.  For more detail on the sending and receiving
                    of Database Description packets, see Sections 10.8
                    and 10.6.


         State(s):  Exchange

            Event:  ExchangeDone

        New state:  Depends upon action routine.

           Action:  If the neighbor Link state request list is empty,
                    the new neighbor state is Full.  No other action is
                    required.  This is an adjacency's final state.

Top      Up      ToC       Page 80 
                    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-WayReceived.


         State(s):  ExStart or greater

            Event:  AdjOK?

        New state:  Depends upon action routine.

           Action:  Determine whether the neighboring router should
                    still be adjacent.  If yes, there is no state change
                    and no further action is necessary.

                    Otherwise, the (possibly partially formed) adjacency
                    must be destroyed.  The neighbor state transitions
                    to 2-Way.  The Link state retransmission list,
                    Database summary list and Link state request list
                    are cleared of link state advertisements.

Top      Up      ToC       Page 81 
         State(s):  Exchange or greater

            Event:  SeqNumberMismatch

        New state:  ExStart

           Action:  The (possibly partially formed) adjacency is torn
                    down, and then an attempt is made at
                    reestablishment.  The neighbor state first
                    transitions to ExStart.  The Link state
                    retransmission list, Database summary list and Link
                    state request list are cleared of link state
                    advertisements.  Then the router increments the DD
                    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.

Top      Up      ToC       Page 82 
         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:  InactivityTimer

        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-WayReceived

        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-WayReceived

        New state:  No state change.

           Action:  No action required.


         State(s):  Init

            Event:  1-WayReceived

Top      Up      ToC       Page 83 
        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, HelloInterval,
        and RouterDeadInterval fields in the received Hello packet must
        be checked against the values configured for the receiving
        interface.  Any mismatch causes processing to stop and the

Top      Up      ToC       Page 84 
        packet to be dropped.  In other words, the above fields are
        really describing the attached network's configuration. However,
        there is one exception to the above rule: on point-to-point
        networks and on virtual links, the Network Mask in the received
        Hello Packet should be ignored.

        The receiving interface attaches to a single OSPF area (this
        could be the backbone).  The setting of the E-bit found in the
        Hello Packet's Options field must match this area's
        ExternalRoutingCapability.  If AS external advertisements are
        not flooded into/throughout the area (i.e, the area is a "stub")
        the E-bit must be clear in received Hello Packets, otherwise the
        E-bit must be set.  A mismatch causes processing to stop and the
        packet to be dropped.  The setting of the rest of the bits in
        the Hello Packet's Options field should be ignored.

        At this point, an attempt is made to match the source of the
        Hello Packet to one of the receiving interface's neighbors.  If
        the receiving interface 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 HelloReceived.

Top      Up      ToC       Page 85 
        o   Then the list of neighbors contained in the Hello Packet is
            examined.  If the router itself appears in this list, the
            neighbor state machine should be executed with the event 2-
            WayReceived.  Otherwise, the neighbor state machine should
            be executed with the event 1-WayReceived, and the processing
            of the packet stops.

        o   Next, the Hello Packet's Router Priority field is examined.
            If this field is different than the one previously received
            from the neighbor, the receiving interface's state machine
            is scheduled with the event NeighborChange.  In any case,
            the Router Priority field in the neighbor data structure
            should be updated accordingly.

        o   Next the Designated Router field in the Hello Packet is
            examined.  If the neighbor is both declaring itself to be
            Designated Router (Designated Router field = Neighbor IP
            address) and the Backup Designated Router field in the
            packet is equal to 0.0.0.0 and the receiving interface is in
            state Waiting, the receiving interface's state machine is
            scheduled with the event BackupSeen.  Otherwise, if the
            neighbor is declaring itself to be Designated Router and it
            had not previously, or the neighbor is not declaring itself
            Designated Router where it had previously, the receiving
            interface's state machine is scheduled with the event
            NeighborChange.  In any case, the Neighbors' Designated
            Router item in the neighbor structure is updated
            accordingly.

        o   Finally, the Backup Designated Router field in the Hello
            Packet is examined.  If the neighbor is declaring itself to
            be Backup Designated Router (Backup Designated Router field
            = Neighbor IP address) and the receiving interface is in
            state Waiting, the receiving interface's state machine is
            scheduled with the event BackupSeen.  Otherwise, if the
            neighbor is declaring itself to be Backup Designated Router
            and it had not previously, or the neighbor is not declaring
            itself Backup Designated Router where it had previously, the
            receiving interface's state machine is scheduled with the
            event NeighborChange.  In any case, the Neighbor's Backup
            Designated Router item in the neighbor structure is updated
            accordingly.

        On non-broadcast multi-access networks, receipt of an Hello
        Packet may also cause an Hello Packet to be sent back to the
        neighbor in response. See Section 9.5.1 for more details.

Top      Up      ToC       Page 86 
    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-WayReceived.  This causes an immediate state change to
            either state 2-Way or state ExStart. If the new state is
            ExStart, the processing of the current packet should then
            continue in this new state by falling through to case
            ExStart below.

        2-Way
            The packet should be ignored.  Database Description Packets
            are used only for the purpose of bringing up adjacencies.[7]

        ExStart
            If the received packet matches one of the following cases,
            then the neighbor state machine should be executed with the
            event NegotiationDone (causing the state to transition to
            Exchange), the packet's Options field should be recorded in
            the neighbor structure's Neighbor Options field and the
            packet should be accepted as next in sequence and processed
            further (see below).  Otherwise, the packet should be
            ignored.

            o   The initialize(I), more (M) and master(MS) bits are set,
                the contents of the packet are empty, and the neighbor's
                Router ID is larger than the router's own.  In this case
                the router is now Slave.  Set the master/slave bit to
                slave, and set the DD sequence number to that specified
                by the master.

            o   The initialize(I) and master(MS) bits are off, the
                packet's DD sequence number equals the router's own DD
                sequence number (indicating acknowledgment) and the
                neighbor's Router ID is smaller than the router's own.
                In this case the router is Master.

Top      Up      ToC       Page 87 
        Exchange
            If the state of the MS-bit is inconsistent with the
            master/slave state of the connection, generate the neighbor
            event SeqNumberMismatch and stop processing the packet.
            Otherwise:

            o   If the initialize(I) bit is set, generate the neighbor
                event SeqNumberMismatch and stop processing the packet.

            o   If the packet's Options field indicates a different set
                of optional OSPF capabilities than were previously
                received from the neighbor (recorded in the Neighbor
                Options field of the neighbor structure), generate the
                neighbor event SeqNumberMismatch and stop processing the
                packet.

            o   If the router is master, and the packet's DD sequence
                number equals the router's own DD 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 DD sequence
                number is one less than the router's DD sequence number,
                the packet is a duplicate.  Duplicates should be
                discarded by the master.

            o   If the router is slave, and the packet's DD sequence
                number is one more than the router's own DD 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 DD sequence
                number is equal to the router's DD sequence number, the
                packet is a duplicate.  The slave must respond to
                duplicates by repeating the last Database Description
                packet that it had sent.

            o   Else, generate the neighbor event SeqNumberMismatch and
                stop processing the packet.

        Loading or Full
            In this state, the router has sent and received an entire
            sequence of Database Description Packets.  The only packets
            received should be duplicates (see above).  In particular,
            the packet's Options field should match the set of optional
            OSPF capabilities previously indicated by the neighbor
            (stored in the neighbor structure's Neighbor Options field).
            Any other packets received, including the reception of a

Top      Up      ToC       Page 88 
            packet with the Initialize(I) bit set, should generate the
            neighbor event SeqNumberMismatch.[8] Duplicates should be
            discarded by the master.  The slave must respond to
            duplicates by repeating the last Database Description packet
            that it had sent.


        When the router accepts a received Database Description Packet
        as the next in sequence the packet contents are processed as
        follows.  For each 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 SeqNumberMismatch 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 DD sequence number.  If the router has
            already sent its entire sequence of Database Description
            Packets, and the just accepted packet has the more bit (M)
            set to 0, the neighbor event ExchangeDone is generated.
            Otherwise, it should send a new Database Description to the
            slave.

        Slave
            Sets the DD sequence number to the DD sequence number
            appearing in the received packet.  The slave must send a
            Database Description Packet in reply.  If the received
            packet has the more bit (M) set to 0, and the packet to be
            sent by the slave will also have the M-bit set to 0, the
            neighbor event ExchangeDone is generated.  Note that the
            slave always generates this event before the master.

Top      Up      ToC       Page 89 
    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 Database Exchange process, and
        neighbor event BadLSReq should be generated.


    10.8.  Sending Database Description Packets

        This section describes how Database Description Packets are sent
        to a neighbor.  The 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

Top      Up      ToC       Page 90 
        packet's DD 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 Database
        Description packet depends on whether the router is master or
        slave:


        Master
            Database Description packets are sent when either a) the
            slave acknowledges the previous Database Description packet
            by echoing the DD sequence number or b) RxmtInterval seconds
            elapse without an acknowledgment, in which case the previous
            Database Description packet is retransmitted.

        Slave
            Database Description packets are sent only in response to
            Database Description packets received from the master.  If
            the Database Description packet received from the master is
            new, a new Database Description packet is sent, otherwise
            the previous Database Description packet is resent.


        In states Loading and Full the slave must resend its last
        Database Description packet in response to duplicate Database
        Description packets received from the master.  For this reason
        the slave must wait RouterDeadInterval seconds before freeing
        the last Database Description packet.  Reception of a Database
        Description packet from the master after this interval will
        generate a SeqNumberMismatch neighbor event.


    10.9.  Sending Link State Request Packets

        In neighbor states Exchange or Loading, the Link state request
        list contains a list of those 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 Request packets are retransmitted

Top      Up      ToC       Page 91 
        at intervals of RxmtInterval.  There should be at most one Link
        State Request packet outstanding at any one time.

        When the Link state request list becomes empty, and the neighbor
        state is Loading (i.e., a complete sequence of Database
        Description packets has been sent to and received from the
        neighbor), the Loading Done neighbor event is generated.


    10.10.  An Example

        Figure 14 shows an example of an adjacency forming.  Routers RT1
        and RT2 are both connected to a broadcast network.  It is
        assumed that RT2 is the Designated Router for the network, and
        that RT2 has a higher Router ID than Router RT1.

        The neighbor state changes realized by each router are listed on
        the sides of the figure.

        At the beginning of Figure 14, Router RT1's interface to the
        network becomes operational.  It begins sending Hello Packets,
        although it doesn't know the identity of the Designated Router
        or of any other neighboring routers.  Router RT2 hears this
        hello (moving the neighbor to Init state), and in its next Hello
        Packet indicates that it is itself the Designated Router and
        that it has heard Hello Packets from RT1.  This in turn causes
        RT1 to go to state ExStart, as it starts to bring up the
        adjacency.

        RT1 begins by asserting itself as the master.  When it sees that
        RT2 is indeed the master (because of RT2's higher Router ID),
        RT1 transitions to slave state and adopts its neighbor's DD
        sequence number.  Database Description packets are then
        exchanged, with polls coming from the master (RT2) and responses
        from the slave (RT1).  This sequence of Database Description
        Packets ends when both the poll and associated response has the
        M-bit off.

        In this example, it is assumed that RT2 has a completely up to
        date database.  In that case, RT2 goes immediately into Full
        state.  RT1 will go into Full state after updating the necessary
        parts of its database.  This is done by sending Link State
        Request Packets, and receiving Link State Update Packets in
        response.  Note that, while RT1 has waited until a complete set
        of Database Description Packets has been received (from RT2)
        before sending any Link State Request Packets, this need not be
        the case.  RT1 could have interleaved the sending of Link State
        Request Packets with the reception of Database Description

Top      Up      ToC       Page 92 
            +---+                                         +---+
            |RT1|                                         |RT2|
            +---+                                         +---+

            Down                                          Down
                            Hello(DR=0,seen=0)
                       ------------------------------>
                         Hello (DR=RT2,seen=RT1,...)      Init
                       <------------------------------
            ExStart        D-D (Seq=x,I,M,Master)
                       ------------------------------>
                           D-D (Seq=y,I,M,Master)         ExStart
                       <------------------------------
            Exchange       D-D (Seq=y,M,Slave)
                       ------------------------------>
                           D-D (Seq=y+1,M,Master)         Exchange
                       <------------------------------
                           D-D (Seq=y+1,M,Slave)
                       ------------------------------>
                                     ...
                                     ...
                                     ...
                           D-D (Seq=y+n, Master)
                       <------------------------------
                           D-D (Seq=y+n, Slave)
             Loading   ------------------------------>
                                 LS Request                Full
                       ------------------------------>
                                 LS Update
                       <------------------------------
                                 LS Request
                       ------------------------------>
                                 LS Update
                       <------------------------------
             Full


                   Figure 14: An adjacency bring-up example

Top      Up      ToC       Page 93 
        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.  The matching routing table entry then
    provides the next hop towards the packet's destination.  OSPF also
    provides for the existence of a default route (Destination ID =
    DefaultDestination, Address Mask =  0x00000000).  When the default
    route exists, it matches all IP destinations (although any other
    matching entry is a better match).  Finding the routing table entry
    that best matches an IP destination is further described in Section
    11.1.

    There is a single routing table in each router.  Two sample routing
    tables are described in Sections 11.2 and 11.3.  The building of the
    routing table is discussed in Section 16.

    The rest of this section defines the fields found in a routing table
    entry.  The first set of fields describes the routing table entry's
    destination.


    Destination Type
        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, IP supernets 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.

Top      Up      ToC       Page 94 
        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 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 link 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

Top      Up      ToC       Page 95 
        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, a
        type 2 external path with type 2 cost of 5 is always preferred
        over a path with type 2 cost of 10, regardless of the cost of
        the two paths' internal components.

    Link State Origin
        Valid only for intra-area paths, this field indicates the 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-

Top      Up      ToC       Page 96 
        breaking scheme always reduces the choice to a single
        advertisement. The Link State Origin field is not used by the
        OSPF protocol, but it is used by the routing table calculation
        in OSPF's Multicast routing extensions (MOSPF).

    When multiple paths of equal path-type and cost exist to a
    destination (called elsewhere "equal-cost" paths), they are stored
    in a single routing table entry.  Each one of the "equal-cost" paths
    is distinguished by the following fields:


    Next hop
        The outgoing router interface to use when forwarding traffic to
        the destination.  On 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

Top      Up      ToC       Page 97 
            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

Top      Up      ToC       Page 98 
        on TOS.  The calculation of 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 table 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 the inter-area routes are associated with the
        backbone; this is always the case when the calculating router is
        itself an area border router.  Routing information is condensed
        at area boundaries.  In this example, we assume that Area 3 has
        been defined so that networks N9-N11 and the host route to H1
        are all condensed to a single route when advertised into the
        backbone (by Router RT11).  Note that the cost of this route is

Top      Up      ToC       Page 99 
      Type   Dest   Area   Path  Type    Cost   Next     Adv.
                                                Hop(s)   Router(s)
      ____________________________________________________________
      N      N1     0      intra-area    10     RT3      *
      N      N2     0      intra-area    10     RT3      *
      N      N3     0      intra-area    7      RT3      *
      N      N4     0      intra-area    8      RT3      *
      N      Ib     0      intra-area    7      *        *
      N      Ia     0      intra-area    12     RT10     *
      N      N6     0      intra-area    8      RT10     *
      N      N7     0      intra-area    12     RT10     *
      N      N8     0      intra-area    10     RT10     *
      N      N9     0      intra-area    11     RT10     *
      N      N10    0      intra-area    13     RT10     *
      N      N11    0      intra-area    14     RT10     *
      N      H1     0      intra-area    21     RT10     *
      ASBR   RT5    0      intra-area    6      RT5      *
      ASBR   RT7    0      intra-area    8      RT10     *
      ____________________________________________________________
      N      N12    *      type 1 ext.   10     RT10     RT7
      N      N13    *      type 1 ext.   14     RT5      RT5
      N      N14    *      type 1 ext.   14     RT5      RT5
      N      N15    *      type 1 ext.   17     RT10     RT7


               Table 12: The routing table for Router RT6
                         (no configured areas).

        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

Top      Up      ToC       Page 100 
   Type   Dest        Area   Path  Type    Cost   Next      Adv.
                                                  Hops(s)   Router(s)
   __________________________________________________________________
   N      N1          1      intra-area    4      RT1       *
   N      N2          1      intra-area    4      RT2       *
   N      N3          1      intra-area    1      *         *
   N      N4          1      intra-area    3      RT3       *
   BR     RT3         1      intra-area    1      *         *
   __________________________________________________________________
   N      Ib          0      intra-area    22     RT5       *
   N      Ia          0      intra-area    27     RT5       *
   BR     RT3         0      intra-area    21     RT5       *
   BR     RT7         0      intra-area    14     RT5       *
   BR     RT10        0      intra-area    22     RT5       *
   BR     RT11        0      intra-area    25     RT5       *
   ASBR   RT5         0      intra-area    8      *         *
   ASBR   RT7         0      intra-area    14     RT5       *
   __________________________________________________________________
   N      N6          0      inter-area    15     RT5       RT7
   N      N7          0      inter-area    19     RT5       RT7
   N      N8          0      inter-area    18     RT5       RT7
   N      N9-N11,H1   0      inter-area    26     RT5       RT11
   __________________________________________________________________
   N      N12         *      type 1 ext.   16     RT5       RT5,RT7
   N      N13         *      type 1 ext.   16     RT5       RT5
   N      N14         *      type 1 ext.   16     RT5       RT5
   N      N15         *      type 1 ext.   23     RT5       RT7


                  Table 13: Router RT4's routing table
                       in the presence of areas.

        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 100 continued on part 5)

Next RFC Part