Tech-invite3GPPspaceIETFspace
959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 2178

OSPF Version 2

Pages: 211
Obsoletes:  1583
Obsoleted by:  2328
Part 3 of 8 – Pages 49 to 76
First   Prev   Next

ToP   noToC   RFC2178 - Page 49   prevText
8.  Protocol Packet Processing

   This section discusses the general processing of OSPF routing
   protocol packets.  It is very important that the router link-state
   databases remain synchronized.  For this reason, routing protocol
   packets should get preferential treatment over ordinary data packets,
   both in sending and receiving.

   Routing protocol packets are sent along adjacencies only (with the
   exception of Hello packets, which are used to discover the
   adjacencies).  This means that all routing protocol packets travel a
   single IP hop, except those sent over virtual links.

   All routing protocol packets begin with a standard header. The
   sections below provide details on how to fill in and verify this
   standard header.  Then, for each packet type, the section giving more
   details on that particular packet type's processing is listed.

8.1.  Sending protocol packets

   When a router sends a routing protocol packet, it fills in the fields
   of the standard OSPF packet header as follows.  For more details on
   the header format consult Section A.3.1:
ToP   noToC   RFC2178 - Page 50
   Version #
      Set to 2, the version number of the protocol as documented in this
      specification.

   Packet type
      The type of OSPF packet, such as Link state Update or Hello
      Packet.

   Packet length
      The length of the entire OSPF packet in bytes, including the
      standard OSPF packet header.

   Router ID
      The identity of the router itself (who is originating the packet).

   Area ID
      The OSPF area that the packet is being sent into.

   Checksum
      The standard IP 16-bit one's complement checksum of the entire
      OSPF packet, excluding the 64-bit authentication field.  This
      checksum is calculated as part of the appropriate authentication
      procedure; for some OSPF authentication types, the checksum
      calculation is omitted.  See Section D.4 for details.

   AuType and Authentication
      Each OSPF packet exchange is authenticated.  Authentication types
      are assigned by the protocol and are documented in Appendix D.  A
      different authentication procedure can be used for each IP
      network/subnet.  Autype indicates the type of authentication
      procedure in use.  The 64-bit authentication field is then for use
      by the chosen authentication procedure.  This procedure should be
      the last called when forming the packet to be sent.  See Section
      D.4 for details.
ToP   noToC   RFC2178 - Page 51
   The IP destination address for the packet is selected as follows.  On
   physical point-to-point networks, the IP destination is always set to
   the address AllSPFRouters.  On all other network types (including
   virtual links), the majority of OSPF packets are sent as unicasts,
   i.e., sent directly to the other end of the adjacency.  In this case,
   the IP destination is just the Neighbor IP address associated with
   the other end of the adjacency (see Section 10).  The only packets
   not sent as unicasts are on broadcast networks; on these networks
   Hello packets are sent to the multicast destination AllSPFRouters,
   the Designated Router and its Backup send both Link State Update
   Packets and Link State Acknowledgment Packets to the multicast
   address AllSPFRouters, while all other routers send both their Link
   State Update and Link State Acknowledgment Packets to the multicast
   address AllDRouters.

   Retransmissions of Link State Update packets are ALWAYS sent as
   unicasts.

   The IP source address should be set to the IP address of the sending
   interface.  Interfaces to unnumbered point-to-point networks have no
   associated IP address.  On these interfaces, the IP source should be
   set to any of the other IP addresses belonging to the router.  For
   this reason, there must be at least one IP address assigned to the
   router.[2] Note that, for most purposes, virtual links act precisely
   the same as unnumbered point-to-point networks.  However, each
   virtual link does have an IP interface address (discovered during the
   routing table build process) which is used as the IP source when
   sending packets over the virtual link.

   For more information on the format of specific OSPF packet types,
   consult the sections listed in Table 10.


             Type   Packet name            detailed section (transmit)
             _________________________________________________________
             1      Hello                  Section  9.5
             2      Database description   Section 10.8
             3      Link state request     Section 10.9
             4      Link state update      Section 13.3
             5      Link state ack         Section 13.5

    Table 10: Sections describing OSPF protocol packet transmission.

8.2.  Receiving protocol packets

   Whenever a protocol packet is received by the router it is marked
   with the interface it was received on.  For routers that have virtual
   links configured, it may not be immediately obvious which interface
ToP   noToC   RFC2178 - Page 52
   to associate the packet with.  For example, consider the Router RT11
   depicted in Figure 6.  If RT11 receives an OSPF protocol packet on
   its interface to Network N8, it may want to associate the packet with
   the interface to Area 2, or with the virtual link to Router RT10
   (which is part of the backbone).  In the following, we assume that
   the packet is initially associated with the non-virtual  link.[3]

   In order for the packet to be accepted at the IP level, it must pass
   a number of tests, even before the packet is passed to OSPF for
   processing:

   o   The IP checksum must be correct.

   o   The packet's IP destination address must be the IP address
       of the receiving interface, or one of the IP multicast
       addresses AllSPFRouters or AllDRouters.

   o   The IP protocol specified must be OSPF (89).

   o   Locally originated packets should not be passed on to OSPF.
       That is, the source IP address should be examined to make
       sure this is not a multicast packet that the router itself
       generated.

   Next, the OSPF packet header is verified.  The fields specified
   in the header must match those configured for the receiving
   interface.  If they do not, the packet should be discarded:


   o   The version number field must specify protocol version 2.

   o   The Area ID found in the OSPF header must be verified.  If
       both of the following cases fail, the packet should be
       discarded.  The Area ID specified in the header must either:

       (1) Match the Area ID of the receiving interface.  In this
           case, the packet has been sent over a single hop.
           Therefore, the packet's IP source address is required to
           be on the same network as the receiving interface.  This
           can be verified by comparing the packet's IP source
           address to the interface's IP address, after masking
           both addresses with the interface mask.  This comparison
           should not be performed on point-to-point networks. On
           point-to-point networks, the interface addresses of each
           end of the link are assigned independently, if they are
           assigned at all.
ToP   noToC   RFC2178 - Page 53
       (2) Indicate the backbone.  In this case, the packet has
           been sent over a virtual link.  The receiving router
           must be an area border router, and the Router ID
           specified in the packet (the source router) must be the
           other end of a configured virtual link.  The receiving
           interface must also attach to the virtual link's
           configured Transit area.  If all of these checks
           succeed, the packet is accepted and is from now on
           associated with the virtual link (and the backbone
           area).

   o   Packets whose IP destination is AllDRouters should only be
       accepted if the state of the receiving interface is DR or
       Backup (see Section 9.1).

   o   The AuType specified in the packet must match the AuType
       specified for the associated area.

   o   The packet must be authenticated.  The authentication
       procedure is indicated by the setting of AuType (see
       Appendix D).  The authentication procedure may use one or
       more Authentication keys, which can be configured on a per-
       interface basis.  The authentication procedure may also
       verify the checksum field in the OSPF packet header (which,
       when used, is set to the standard IP 16-bit one's complement
       checksum of the OSPF packet's contents after excluding the
       64-bit authentication field).  If the authentication
       procedure fails, the packet should be discarded.

   If the packet type is Hello, it should then be further processed by
   the Hello Protocol (see Section 10.5).  All other packet types are
   sent/received only on adjacencies.  This means that the packet must
   have been sent by one of the router's active neighbors.  If the
   receiving interface connects to a broadcast network, Point-to-
   MultiPoint network or NBMA network the sender is identified by the IP
   source address found in the packet's IP header.  If the receiving
   interface connects to a point-to-point network or a virtual link, the
   sender is identified by the Router ID (source router) found in the
   packet's OSPF header.  The data structure associated with the
   receiving interface contains the list of active neighbors.  Packets
   not matching any active neighbor are discarded.

   At this point all received protocol packets are associated with an
   active neighbor.  For the further input processing of specific packet
   types, consult the sections listed in Table 11.
ToP   noToC   RFC2178 - Page 54
      Type   Packet name            detailed section (receive)
      ________________________________________________________
      1      Hello                  Section 10.5
      2      Database description   Section 10.6
      3      Link state request     Section 10.7
      4      Link state update      Section 13
      5      Link state ack         Section 13.7

     Table 11: Sections describing OSPF protocol packet reception.

9.  The Interface Data Structure

   An OSPF interface is the connection between a router and a network.
   We assume a single OSPF interface to each attached network/subnet,
   although supporting multiple interfaces on a single network is
   considered in Appendix F. Each interface structure has at most one IP
   interface address.

   An OSPF interface can be considered to belong to the area that
   contains the attached network.  All routing protocol packets
   originated by the router over this interface are labelled with the
   interface's Area ID.  One or more router adjacencies may develop over
   an interface. A router's LSAs reflect the state of its interfaces and
   their associated adjacencies.

   The following data items are associated with an interface. Note that
   a number of these items are actually configuration for the attached
   network; such items must be the same for all routers connected to the
   network.

   Type
      The OSPF interface type is either point-to-point, broadcast, NBMA,
      Point-to-MultiPoint or virtual link.

   State
      The functional level of an interface.  State determines whether or
      not full adjacencies are allowed to form over the interface.
      State is also reflected in the router's LSAs.

   IP interface address
      The IP address associated with the interface.  This appears as the
      IP source address in all routing protocol packets originated over
      this interface.  Interfaces to unnumbered point-to-point networks
      do not have an associated IP address.

   IP interface mask
      Also referred to as the subnet mask, this indicates the portion of
      the IP interface address that identifies the attached network.
ToP   noToC   RFC2178 - Page 55
      Masking the IP interface address with the IP interface mask yields
      the IP network number of the attached network.  On point-to-point
      networks and virtual links, the IP interface mask is not defined.
      On these networks, the link itself is not assigned an IP network
      number, and so the addresses of each side of the link are assigned
      independently, if they are assigned at all.

   Area ID
      The Area ID of the area to which the attached network belongs.
      All routing protocol packets originating from the interface are
      labelled with this Area ID.

   HelloInterval
      The length of time, in seconds, between the Hello packets that the
      router sends on the interface.  Advertised in Hello packets sent
      out this interface.

   RouterDeadInterval
      The number of seconds before the router's neighbors will declare
      it down, when they stop hearing the router's Hello Packets.
      Advertised in Hello packets sent out this interface.

   InfTransDelay
      The estimated number of seconds it takes to transmit a Link State
      Update Packet over this interface.  LSAs contained in the Link
      State Update packet will have their age incremented by this amount
      before transmission.  This value should take into account
      transmission and propagation delays; it must be greater than zero.

   Router Priority
      An 8-bit unsigned integer.  When two routers attached to a network
      both attempt to become Designated Router, the one with the highest
      Router Priority takes precedence.  A router whose Router Priority
      is set to 0 is ineligible to become Designated Router on the
      attached network.  Advertised in Hello packets sent out this
      interface.

   Hello Timer
      An interval timer that causes the interface to send a Hello
      packet.  This timer fires every HelloInterval seconds.  Note that
      on non-broadcast networks a separate Hello packet is sent to each
      qualified neighbor.

   Wait Timer
      A single shot timer that causes the interface to exit the Waiting
      state, and as a consequence select a Designated Router on the
      network.  The length of the timer is RouterDeadInterval seconds.
ToP   noToC   RFC2178 - Page 56
   List of neighboring routers
      The other routers attached to this network.  This list is formed
      by the Hello Protocol.  Adjacencies will be formed to some of
      these neighbors.  The set of adjacent neighbors can be determined
      by an examination of all of the neighbors' states.

   Designated Router
      The Designated Router selected for the attached network.  The
      Designated Router is selected on all broadcast and NBMA networks
      by the Hello Protocol.  Two pieces of identification are kept for
      the Designated Router: its Router ID and its IP interface address
      on the network.  The Designated Router advertises link state for
      the network; this network-LSA is labelled with the Designated
      Router's IP address.  The Designated Router is initialized to
      0.0.0.0, which indicates the lack of a Designated Router.

   Backup Designated Router
      The Backup Designated Router is also selected on all broadcast and
      NBMA networks by the Hello Protocol.  All routers on the attached
      network become adjacent to both the Designated Router and the
      Backup Designated Router.  The Backup Designated Router becomes
      Designated Router when the current Designated Router fails. The
      Backup Designated Router is initialized to 0.0.0.0, indicating the
      lack of a Backup Designated Router.

   Interface output cost(s)
      The cost of sending a data packet on the interface, expressed in
      the link state metric.  This is advertised as the link cost for
      this interface in the router-LSA. The cost of an interface must be
      greater than zero.

   RxmtInterval
      The number of seconds between LSA retransmissions, for adjacencies
      belonging to this interface.  Also used when retransmitting
      Database Description and Link State Request Packets.

   AuType
      The type of authentication used on the attached network/subnet.
      Authentication types are defined in Appendix D.  All OSPF packet
      exchanges are authenticated.  Different authentication schemes may
      be used on different networks/subnets.
ToP   noToC   RFC2178 - Page 57
   Authentication key
      This configured data allows the authentication procedure to
      generate and/or verify OSPF protocol packets.  The Authentication
      key can be configured on a per-interface basis.  For example, if
      the AuType indicates simple password, the Authentication key would
      be a 64-bit clear password which is inserted into the OSPF packet
      header. If instead Autype indicates Cryptographic authentication,
      then the Authentication key is a shared secret which enables the
      generation/verification of message digests which are appended to
      the OSPF protocol packets. When Cryptographic authentication is
      used, multiple simultaneous keys are supported in order to achieve
      smooth key transition (see Section D.3).

9.1.  Interface states

   The various states that router interfaces may attain is documented in
   this section.  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 interfaces in
   state greater than X".  Figure 11 shows the graph of interface state
   changes.  The arcs of the graph are labelled with the event causing
   the state change.  These events are documented in Section 9.2.  The
   interface state machine is described in more detail in Section 9.3.

   Down
      This is the initial interface state.  In this state, the lower-
      level protocols have indicated that the interface is unusable.  No
      protocol traffic at all will be sent or received on such a
      interface.  In this state, interface parameters should be set to
      their initial values.
ToP   noToC   RFC2178 - Page 58
                                  +----+   UnloopInd   +--------+
                                  |Down|<--------------|Loopback|
                                  +----+               +--------+
                                     |
                                     |InterfaceUp
                          +-------+  |               +--------------+
                          |Waiting|<-+-------------->|Point-to-point|
                          +-------+                  +--------------+
                              |
                     WaitTimer|BackupSeen
                              |
                              |
                              |   NeighborChange
          +------+           +-+<---------------- +-------+
          |Backup|<----------|?|----------------->|DROther|
          +------+---------->+-+<-----+           +-------+
                    Neighbor  |       |
                    Change    |       |Neighbor
                              |       |Change
                              |     +--+
                              +---->|DR|
                                    +--+

                   Figure 11: Interface State changes

             In addition to the state transitions pictured,
           Event InterfaceDown always forces Down State, and
               Event LoopInd always forces Loopback State

      All interface timers should be disabled, and there should be no
      adjacencies associated with the interface.

   Loopback
      In this state, the router's interface to the network is looped
      back.  The interface may be looped back in hardware or software.
      The interface will be unavailable for regular data traffic.
      However, it may still be desirable to gain information on the
      quality of this interface, either through sending ICMP pings to
      the interface or through something like a bit error test.  For
      this reason, IP packets may still be addressed to an interface in
      Loopback state.  To facilitate this, such interfaces are
      advertised in router-LSAs as single host routes, whose destination
      is the IP interface address.[4]
ToP   noToC   RFC2178 - Page 59
   Waiting
      In this state, the router is trying to determine the identity of
      the (Backup) Designated Router for the network.  To do this, the
      router monitors the Hello Packets it receives.  The router is not
      allowed to elect a Backup Designated Router nor a Designated
      Router until it transitions out of Waiting state.  This prevents
      unnecessary changes of (Backup) Designated Router.

   Point-to-point
      In this state, the interface is operational, and connects either
      to a physical point-to-point network or to a virtual link.  Upon
      entering this state, the router attempts to form an adjacency with
      the neighboring router.  Hello Packets are sent to the neighbor
      every HelloInterval seconds.

   DR Other
      The interface is to a broadcast or NBMA network on which another
      router has been selected to be the Designated Router.  In this
      state, the router itself has not been selected Backup Designated
      Router either.  The router forms adjacencies to both the
      Designated Router and the Backup Designated Router (if they
      exist).

   Backup
      In this state, the router itself is the Backup Designated Router
      on the attached network.  It will be promoted to Designated Router
      when the present Designated Router fails.  The router establishes
      adjacencies to all other routers attached to the network.  The
      Backup Designated Router performs slightly different functions
      during the Flooding Procedure, as compared to the Designated
      Router (see Section 13.3).  See Section 7.4 for more details on
      the functions performed by the Backup Designated Router.

   DR  In this state, this router itself is the Designated Router
      on the attached network.  Adjacencies are established to all other
      routers attached to the network.  The router must also originate a
      network-LSA for the network node.  The network-LSA will contain
      links to all routers (including the Designated Router itself)
      attached to the network.  See Section 7.3 for more details on the
      functions performed by the Designated Router.

9.2.  Events causing interface state changes

   State changes can be effected by a number of events.  These events
   are pictured as the labelled arcs in Figure 11.  The label
   definitions are listed below.  For a detailed explanation of the
   effect of these events on OSPF protocol operation, consult Section
   9.3.
ToP   noToC   RFC2178 - Page 60
   InterfaceUp
      Lower-level protocols have indicated that the network interface is
      operational.  This enables the interface to transition out of Down
      state.  On virtual links, the interface operational indication is
      actually a result of the shortest path calculation (see Section
      16.7).

   WaitTimer
      The Wait Timer has fired, indicating the end of the waiting period
      that is required before electing a (Backup) Designated Router.

   BackupSeen
      The router has detected the existence or non-existence of a Backup
      Designated Router for the network.  This is done in one of two
      ways.  First, an Hello Packet may be received from a neighbor
      claiming to be itself the Backup Designated Router.
      Alternatively, an Hello Packet may be received from a neighbor
      claiming to be itself the Designated Router, and indicating that
      there is no Backup Designated Router.  In either case there must
      be bidirectional communication with the neighbor, i.e., the router
      must also appear in the neighbor's Hello Packet.  This event
      signals an end to the Waiting state.

   NeighborChange
      There has been a change in the set of bidirectional neighbors
      associated with the interface.  The (Backup) Designated Router
      needs to be recalculated.  The following neighbor changes lead to
      the NeighborChange event. For an explanation of neighbor states,
      see Section 10.1.

       o   Bidirectional communication has been established to a
           neighbor.  In other words, the state of the neighbor has
           transitioned to 2-Way or higher.

       o   There is no longer bidirectional communication with a
           neighbor.  In other words, the state of the neighbor has
           transitioned to Init or lower.

       o   One of the bidirectional neighbors is newly declaring
           itself as either Designated Router or Backup Designated
           Router.  This is detected through examination of that
           neighbor's Hello Packets.

       o   One of the bidirectional neighbors is no longer
           declaring itself as Designated Router, or is no longer
           declaring itself as Backup Designated Router.  This is
           again detected through examination of that neighbor's
           Hello Packets.
ToP   noToC   RFC2178 - Page 61
       o   The advertised Router Priority for a bidirectional
           neighbor has changed.  This is again detected through
           examination of that neighbor's Hello Packets.

   LoopInd
      An indication has been received that the interface is now looped
      back to itself.  This indication can be received either from
      network management or from the lower level protocols.

   UnloopInd
      An indication has been received that the interface is no longer
      looped back.  As with the LoopInd event, this indication can be
      received either from network management or from the lower level
      protocols.

   InterfaceDown
      Lower-level protocols indicate that this interface is no longer
      functional. No matter what the current interface state is, the new
      interface state will be Down.

9.3.  The Interface state machine

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

   When an interface's state changes, it may be necessary to originate a
   new router-LSA.  See Section 12.4 for more details.

   Some of the required actions below involve generating events for the
   neighbor state machine.  For example, when an interface becomes
   inoperative, all neighbor connections associated with the interface
   must be destroyed.  For more information on the neighbor state
   machine, see Section 10.3.
ToP   noToC   RFC2178 - Page 62
    State(s):  Down

       Event:  InterfaceUp

   New state:  Depends upon action routine

      Action:  Start the interval Hello Timer, enabling the
               periodic sending of Hello packets out the interface.
               If the attached network is a physical point-to-point
               network, Point-to-MultiPoint network or virtual
               link, the interface state transitions to Point-to-
               Point.  Else, if the router is not eligible to
               become Designated Router the interface state
               transitions to DR Other.

               Otherwise, the attached network is a broadcast or
               NBMA network and the router is eligible to become
               Designated Router.  In this case, in an attempt to
               discover the attached network's Designated Router
               the interface state is set to Waiting and the single
               shot Wait Timer is started.  Additionally, if the
               network is an NBMA network examine the configured
               list of neighbors for this interface and generate
               the neighbor event Start for each neighbor that is
               also eligible to become Designated Router.

    State(s):  Waiting

       Event:  BackupSeen

   New state:  Depends upon action routine.

      Action:  Calculate the attached network's Backup Designated
               Router and Designated Router, as shown in Section
               9.4.  As a result of this calculation, the new state
               of the interface will be either DR Other, Backup or
               DR.


    State(s):  Waiting

       Event:  WaitTimer

   New state:  Depends upon action routine.
ToP   noToC   RFC2178 - Page 63
      Action:  Calculate the attached network's Backup Designated
               Router and Designated Router, as shown in Section
               9.4.  As a result of this calculation, the new state
               of the interface will be either DR Other, Backup or
               DR.


    State(s):  DR Other, Backup or DR

       Event:  NeighborChange

   New state:  Depends upon action routine.

      Action:  Recalculate the attached network's Backup Designated
               Router and Designated Router, as shown in Section
               9.4.  As a result of this calculation, the new state
               of the interface will be either DR Other, Backup or
               DR.


    State(s):  Any State

       Event:  InterfaceDown

   New state:  Down

      Action:  All interface variables are reset, and interface
               timers disabled.  Also, all neighbor connections
               associated with the interface are destroyed.  This
               is done by generating the event KillNbr on all
               associated neighbors (see Section 10.2).


    State(s):  Any State

       Event:  LoopInd

   New state:  Loopback

      Action:  Since this interface is no longer connected to the
               attached network the actions associated with the
               above InterfaceDown event are executed.


    State(s):  Loopback

       Event:  UnloopInd
ToP   noToC   RFC2178 - Page 64
   New state:  Down

      Action:  No actions are necessary.  For example, the
               interface variables have already been reset upon
               entering the Loopback state.  Note that reception of
               an InterfaceUp event is necessary before the
               interface again becomes fully functional.

9.4.  Electing the Designated Router

   This section describes the algorithm used for calculating a network's
   Designated Router and Backup Designated Router.  This algorithm is
   invoked by the Interface state machine.  The initial time a router
   runs the election algorithm for a network, the network's Designated
   Router and Backup Designated Router are initialized to 0.0.0.0.  This
   indicates the lack of both a Designated Router and a Backup
   Designated Router.

   The Designated Router election algorithm proceeds as follows: Call
   the router doing the calculation Router X.  The list of neighbors
   attached to the network and having established bidirectional
   communication with Router X is examined.  This list is precisely the
   collection of Router X's neighbors (on this network) whose state is
   greater than or equal to 2-Way (see Section 10.1).  Router X itself
   is also considered to be on the list.  Discard all routers from the
   list that are ineligible to become Designated Router.  (Routers
   having Router Priority of 0 are ineligible to become Designated
   Router.)  The following steps are then executed, considering only
   those routers that remain on the list:

   (1) Note the current values for the network's Designated Router
       and Backup Designated Router.  This is used later for
       comparison purposes.

   (2) Calculate the new Backup Designated Router for the network
       as follows.  Only those routers on the list that have not
       declared themselves to be Designated Router are eligible to
       become Backup Designated Router.  If one or more of these
       routers have declared themselves Backup Designated Router
       (i.e., they are currently listing themselves as Backup
       Designated Router, but not as Designated Router, in their
       Hello Packets) the one having highest Router Priority is
       declared to be Backup Designated Router.  In case of a tie,
       the one having the highest Router ID is chosen.  If no
       routers have declared themselves Backup Designated Router,
ToP   noToC   RFC2178 - Page 65
       choose the router having highest Router Priority, (again
       excluding those routers who have declared themselves
       Designated Router), and again use the Router ID to break
       ties.

   (3) Calculate the new Designated Router for the network as
       follows.  If one or more of the routers have declared
       themselves Designated Router (i.e., they are currently
       listing themselves as Designated Router in their Hello
       Packets) the one having highest Router Priority is declared
       to be Designated Router.  In case of a tie, the one having
       the highest Router ID is chosen.  If no routers have
       declared themselves Designated Router, assign the Designated
       Router to be the same as the newly elected Backup Designated
       Router.

   (4) If Router X is now newly the Designated Router or newly the
       Backup Designated Router, or is now no longer the Designated
       Router or no longer the Backup Designated Router, repeat
       steps 2 and 3, and then proceed to step 5.  For example, if
       Router X is now the Designated Router, when step 2 is
       repeated X will no longer be eligible for Backup Designated
       Router election.  Among other things, this will ensure that
       no router will declare itself both Backup Designated Router
       and Designated Router.[5]

   (5) As a result of these calculations, the router itself may now
       be Designated Router or Backup Designated Router.  See
       Sections 7.3 and 7.4 for the additional duties this would
       entail.  The router's interface state should be set
       accordingly.  If the router itself is now Designated Router,
       the new interface state is DR.  If the router itself is now
       Backup Designated Router, the new interface state is Backup.
       Otherwise, the new interface state is DR Other.

   (6) If the attached network is an NBMA network, and the router
       itself has just become either Designated Router or Backup
       Designated Router, it must start sending Hello Packets to
       those neighbors that are not eligible to become Designated
       Router (see Section 9.5.1).  This is done by invoking the
       neighbor event Start for each neighbor having a Router
       Priority of 0.

   (7) If the above calculations have caused the identity of either
       the Designated Router or Backup Designated Router to change,
       the set of adjacencies associated with this interface will
       need to be modified.  Some adjacencies may need to be
       formed, and others may need to be broken.  To accomplish
ToP   noToC   RFC2178 - Page 66
       this, invoke the event AdjOK?  on all neighbors whose state
       is at least 2-Way.  This will cause their eligibility for
       adjacency to be reexamined (see Sections 10.3 and 10.4).


   The reason behind the election algorithm's complexity is the desire
   for an orderly transition from Backup Designated Router to Designated
   Router, when the current Designated Router fails.  This orderly
   transition is ensured through the introduction of hysteresis: no new
   Backup Designated Router can be chosen until the old Backup accepts
   its new Designated Router responsibilities.

   The above procedure may elect the same router to be both Designated
   Router and Backup Designated Router, although that router will never
   be the calculating router (Router X) itself.  The elected Designated
   Router may not be the router having the highest Router Priority, nor
   will the Backup Designated Router necessarily have the second highest
   Router Priority.  If Router X is not itself eligible to become
   Designated Router, it is possible that neither a Backup Designated
   Router nor a Designated Router will be selected in the above
   procedure.  Note also that if Router X is the only attached router
   that is eligible to become Designated Router, it will select itself
   as Designated Router and there will be no Backup Designated Router
   for the network.

9.5.  Sending Hello packets

   Hello packets are sent out each functioning router interface.  They
   are used to discover and maintain neighbor relationships.[6] On
   broadcast and NBMA networks, Hello Packets are also used to elect the
   Designated Router and Backup Designated Router.

   The format of an Hello packet is detailed in Section A.3.2.  The
   Hello Packet contains the router's Router Priority (used in choosing
   the Designated Router), and the interval between Hello Packets sent
   out the interface (HelloInterval).  The Hello Packet also indicates
   how often a neighbor must be heard from to remain active
   (RouterDeadInterval).  Both HelloInterval and RouterDeadInterval must
   be the same for all routers attached to a common network.  The Hello
   packet also contains the IP address mask of the attached network
   (Network Mask).  On unnumbered point-to-point networks and on virtual
   links this field should be set to 0.0.0.0.

   The Hello packet's Options field describes the router's optional OSPF
   capabilities.  One optional capability is defined in this
   specification (see Sections 4.5 and A.2).  The E-bit of the Options
   field should be set if and only if the attached area is capable of
   processing AS-external-LSAs (i.e., it is not a stub area). If the E-
ToP   noToC   RFC2178 - Page 67
   bit is set incorrectly the neighboring routers will refuse to accept
   the Hello Packet (see Section 10.5).  Unrecognized bits in the Hello
   Packet's Options field should be set to zero.

   In order to ensure two-way communication between adjacent routers,
   the Hello packet contains the list of all routers on the network from
   which Hello Packets have been seen recently.  The Hello packet also
   contains the router's current choice for Designated Router and Backup
   Designated Router.  A value of 0.0.0.0 in these fields means that one
   has not yet been selected.

   On broadcast networks and physical point-to-point networks, Hello
   packets are sent every HelloInterval seconds to the IP multicast
   address AllSPFRouters.  On virtual links, Hello packets are sent as
   unicasts (addressed directly to the other end of the virtual link)
   every HelloInterval seconds. On Point-to-MultiPoint networks,
   separate Hello packets are sent to each attached neighbor every
   HelloInterval seconds. Sending of Hello packets on NBMA networks is
   covered in the next section.

9.5.1.  Sending Hello packets on NBMA networks

   Static configuration information may be necessary in order for the
   Hello Protocol to function on non-broadcast networks (see Sections
   C.5 and C.6).  On NBMA networks, every attached router which is
   eligible to become Designated Router becomes aware of all of its
   neighbors on the network (either through configuration or by some
   unspecified mechanism).  Each neighbor is labelled with the
   neighbor's Designated Router eligibility.

   The interface state must be at least Waiting for any Hello Packets to
   be sent out the NBMA interface. Hello Packets are then sent directly
   (as unicasts) to some subset of a router's neighbors.  Sometimes an
   Hello Packet is sent periodically on a timer; at other times it is
   sent as a response to a received Hello Packet.  A router's hello-
   sending behavior varies depending on whether the router itself is
   eligible to become Designated Router.

   If the router is eligible to become Designated Router, it must
   periodically send Hello Packets to all neighbors that are also
   eligible. In addition, if the router is itself the Designated Router
   or Backup Designated Router, it must also send periodic Hello Packets
   to all other neighbors.  This means that any two eligible routers are
   always exchanging Hello Packets, which is necessary for the correct
   operation of the Designated Router election algorithm.  To minimize
   the number of Hello Packets sent, the number of eligible routers on
   an NBMA network should be kept small.
ToP   noToC   RFC2178 - Page 68
   If the router is not eligible to become Designated Router, it must
   periodically send Hello Packets to both the Designated Router and the
   Backup Designated Router (if they exist).  It must also send an Hello
   Packet in reply to an Hello Packet received from any eligible
   neighbor (other than the current Designated Router and Backup
   Designated Router).  This is needed to establish an initial
   bidirectional relationship with any potential Designated Router.

   When sending Hello packets periodically to any neighbor, the interval
   between Hello Packets is determined by the neighbor's state.  If the
   neighbor is in state Down, Hello Packets are sent every PollInterval
   seconds.  Otherwise, Hello Packets are sent every HelloInterval
   seconds.

10.  The Neighbor Data Structure

   An OSPF router converses with its neighboring routers.  Each separate
   conversation is described by a "neighbor data structure".  Each
   conversation is bound to a particular OSPF router interface, and is
   identified either by the neighboring router's OSPF Router ID or by
   its Neighbor IP address (see below). Thus if the OSPF router and
   another router have multiple attached networks in common, multiple
   conversations ensue, each described by a unique neighbor data
   structure.  Each separate conversation is loosely referred to in the
   text as being a separate "neighbor".

   The neighbor data structure contains all information pertinent to the
   forming or formed adjacency between the two neighbors.  (However,
   remember that not all neighbors become adjacent.)  An adjacency can
   be viewed as a highly developed conversation between two routers.

   State
      The functional level of the neighbor conversation.  This is
      described in more detail in Section 10.1.

   Inactivity Timer
      A single shot timer whose firing indicates that no Hello Packet
      has been seen from this neighbor recently.  The length of the
      timer is RouterDeadInterval seconds.

   Master/Slave
      When the two neighbors are exchanging databases, they form a
      master/slave relationship.  The master sends the first Database
      Description Packet, and is the only part that is allowed to
      retransmit.  The slave can only respond to the master's Database
      Description Packets.  The master/slave relationship is negotiated
      in state ExStart.
ToP   noToC   RFC2178 - Page 69
   DD Sequence Number
      The DD Sequence number of the Database Description packet that is
      currently being sent to the neighbor.

   Last received Database Description packet
      The initialize(I), more (M) and master(MS) bits, Options field,
      and DD sequence number contained in the last Database Description
      packet received from the neighbor. Used to determine whether the
      next Database Description packet received from the neighbor is a
      duplicate.

   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-LSAs as the Link ID for the attached network if the
      neighboring router is selected to be Designated Router (see
      Section 12.4.1).  The Neighbor IP address is learned when Hello
      packets are received from the neighbor.  For virtual links, the
      Neighbor IP address is learned during the routing table build
      process (see Section 15).

   Neighbor Options
      The optional OSPF capabilities supported by the neighbor.  Learned
      during the Database Exchange process (see Section 10.6).  The
      neighbor's optional OSPF capabilities are also listed in its Hello
      packets. This enables received Hello Packets 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 broadcast and NBMA networks.
ToP   noToC   RFC2178 - Page 70
   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 broadcast and NBMA
      networks.

   The next set of variables are lists of LSAs.  These lists describe
   subsets of the area link-state database.  This memo defines five
   distinct types of LSAs, all of which may be present in an area link-
   state database: router-LSAs, network-LSAs, and Type 3 and 4 summary-
   LSAs (all stored in the area data structure), and AS- external-LSAs
   (stored in the global data structure).

   Link state retransmission list
      The list of LSAs 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 LSAs that make up the area link-state
      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 LSAs that need to be received from this neighbor in
      order to synchronize the two neighbors' link-state databases.
      This list is created as Database Description packets are received,
      and is then sent to the neighbor in Link State Request packets.
      The list is depleted as appropriate Link State Update packets are
      received.

10.1.  Neighbor states

   The state of a neighbor (really, the state of a conversation being
   held with a neighboring router) is documented in the following
   sections.  The states are listed in order of progressing
   functionality.  For example, the inoperative state is listed first,
   followed by a list of intermediate states before the final, fully
   functional state is achieved.  The specification makes use of this
   ordering by sometimes making references such as "those
   neighbors/adjacencies in state greater than X".  Figures 12 and 13
   show the graph of neighbor state changes.  The arcs of the graphs are
   labelled with the event causing the state change.  The neighbor
   events are documented in Section 10.2.
ToP   noToC   RFC2178 - Page 71
   The graph in Figure 12 shows 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
   LSAs.

   For a more detailed description of neighbor state changes, together
   with the additional actions involved in each change, see Section
   10.3.

   Down
      This is the initial state of a neighbor conversation.  It
      indicates that there has been no recent information received from
      the neighbor. On NBMA networks, Hello packets may still be sent to
      "Down" neighbors, although at a reduced frequency (see Section
      9.5.1).
ToP   noToC   RFC2178 - Page 72
                                   +----+
                                   |Down|
                                   +----+
                                     |\
                                     | \Start
                                     |  \      +-------+
                             Hello   |   +---->|Attempt|
                            Received |         +-------+
                                     |             |
                             +----+<-+             |HelloReceived
                             |Init|<---------------+
                             +----+<--------+
                                |           |
                                |2-Way      |1-Way
                                |Received   |Received
                                |           |
              +-------+         |        +-----+
              |ExStart|<--------+------->|2-Way|
              +-------+                  +-----+

           Figure 12: Neighbor state changes (Hello Protocol)

             In addition to the state transitions pictured,
                Event KillNbr always forces Down State,
            Event Inactivity Timer always forces Down State,
                 Event LLDown always forces Down State
ToP   noToC   RFC2178 - Page 73
                                  +-------+
                                  |ExStart|
                                  +-------+
                                    |
                     NegotiationDone|
                                    +->+--------+
                                       |Exchange|
                                    +--+--------+
                                    |
                            Exchange|
                              Done  |
                    +----+          |      +-------+
                    |Full|<---------+----->|Loading|
                    +----+<-+              +-------+
                            |  LoadingDone     |
                            +------------------+

         Figure 13: Neighbor state changes (Database Exchange)

             In addition to the state transitions pictured,
             Event SeqNumberMismatch forces ExStart state,
                  Event BadLSReq forces ExStart state,
                     Event 1-Way forces Init state,
                Event KillNbr always forces Down State,
            Event InactivityTimer always forces Down State,
                 Event LLDown always forces Down State,
            Event AdjOK? leads to adjacency forming/breaking
ToP   noToC   RFC2178 - Page 74
   Attempt
      This state is only valid for neighbors attached to NBMA 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 DD 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 DD 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 LSAs.  All adjacencies in Exchange state or greater are
      used by the flooding procedure.  In fact, these adjacencies are
      fully capable of transmitting and receiving all types of OSPF
      routing protocol packets.

   Loading
      In this state, Link State Request packets are sent to the neighbor
      asking for the more recent LSAs that have been discovered (but not
      yet received) in the Exchange state.
ToP   noToC   RFC2178 - Page 75
   Full
      In this state, the neighboring routers are fully adjacent.  These
      adjacencies will now appear in router-LSAs and network-LSAs.

10.2.  Events causing neighbor state changes

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

   HelloReceived
      An Hello packet has been received from the neighbor.

   Start
      This is an indication that Hello Packets should now be sent to the
      neighbor at intervals of HelloInterval seconds.  This event is
      generated only for neighbors associated with NBMA networks.

   2-WayReceived
      Bidirectional communication has been realized between the two
      neighboring routers.  This is indicated by the router seeing
      itself in the neighbor's Hello packet.

   NegotiationDone
      The Master/Slave relationship has been negotiated, and DD sequence
      numbers have been exchanged.  This signals the start of the
      sending/receiving of Database Description packets.  For more
      information on the generation of this event, consult Section 10.8.

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

   BadLSReq
      A Link State Request has been received for an LSA not contained in
      the database. This indicates an error in the Database Exchange
      process.

   Loading Done
      Link State Updates have been received for all out-of-date portions
      of the database.  This is indicated by the Link state request list
      becoming empty after the Database Exchange process has completed.
ToP   noToC   RFC2178 - Page 76
   AdjOK?
      A decision must be made as to whether an adjacency should be
      established/maintained with the neighbor.  This event will start
      some adjacencies forming, and destroy others.

   The following events cause well developed neighbors to revert to
   lesser states.  Unlike the above events, these events may occur when
   the neighbor conversation is in any of a number of states.

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

   1-Way
      An Hello packet has been received from the neighbor, in which the
      router is not mentioned. This indicates that communication with
      the neighbor is not bidirectional.

   KillNbr
      This is an indication that all communication with the neighbor is
      now impossible, forcing the neighbor to revert to Down state.

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

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



(page 76 continued on part 4)

Next Section