Tech-invite3GPPspaceIETFspace
96959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 2328

OSPF Version 2

Pages: 244
Internet Standard: 54
Errata
Obsoletes:  2178
Updated by:  57096549684568607474804293559454
Part 3 of 8 – Pages 52 to 80
First   Prev   Next

Top   ToC   RFC2328 - Page 52   prevText
7.  Bringing Up Adjacencies

    OSPF creates adjacencies between neighboring routers for the purpose
    of exchanging routing information.  Not every two neighboring
    routers will become adjacent.  This section covers the generalities
    involved in creating adjacencies.  For further details consult
    Section 10.


    7.1.  The Hello Protocol

        The Hello Protocol is responsible for establishing and
        maintaining neighbor relationships.  It also ensures that
        communication between neighbors is bidirectional.  Hello packets
        are sent periodically out all router interfaces.  Bidirectional
        communication is indicated when the router sees itself listed in
        the neighbor's Hello Packet.  On broadcast and NBMA networks,
        the Hello Protocol elects a Designated Router for the network.

        The Hello Protocol works differently on broadcast networks, NBMA
        networks and Point-to-MultiPoint networks.  On broadcast
        networks, each router advertises itself by periodically
        multicasting Hello Packets.  This allows neighbors to be
        discovered dynamically.  These Hello Packets contain the
        router's view of the Designated Router's identity, and the list
        of routers whose Hello Packets have been seen recently.

        On NBMA networks some configuration information may be necessary
        for the operation of the Hello Protocol.  Each router that may
        potentially become Designated Router has a list of all other
Top   ToC   RFC2328 - Page 53
        routers attached to the network.  A router, having Designated
        Router potential, sends Hello Packets to all other potential
        Designated Routers when its interface to the NBMA network first
        becomes operational.  This is an attempt to find the Designated
        Router for the network.  If the router itself is elected
        Designated Router, it begins sending Hello Packets to all other
        routers attached to the network.

        On Point-to-MultiPoint networks, a router sends Hello Packets to
        all neighbors with which it can communicate directly. These
        neighbors may be discovered dynamically through a protocol such
        as Inverse ARP (see [Ref14]), or they may be configured.

        After a neighbor has been discovered, bidirectional
        communication ensured, and (if on a broadcast or NBMA network) a
        Designated Router elected, a decision is made regarding whether
        or not an adjacency should be formed with the neighbor (see
        Section 10.4). If an adjacency is to be formed, the first step
        is to synchronize the neighbors' link-state databases.  This is
        covered in the next section.


    7.2.  The Synchronization of Databases

        In a link-state routing algorithm, it is very important for all
        routers' link-state databases to stay synchronized.  OSPF
        simplifies this by requiring only adjacent routers to remain
        synchronized.  The synchronization process begins as soon as the
        routers attempt to bring up the adjacency.  Each router
        describes its database by sending a sequence of Database
        Description packets to its neighbor.  Each Database Description
        Packet describes a set of LSAs belonging to the router's
        database.  When the neighbor sees an LSA that is more recent
        than its own database copy, it makes a note that this newer LSA
        should be requested.

        This sending and receiving of Database Description packets is
        called the "Database Exchange Process".  During this process,
        the two routers form a master/slave relationship.  Each Database
        Description Packet has a sequence number.  Database Description
        Packets sent by the master (polls) are acknowledged by the slave
        through echoing of the sequence number.  Both polls and their
Top   ToC   RFC2328 - Page 54
        responses contain summaries of link state data.  The master is
        the only one allowed to retransmit Database Description Packets.
        It does so only at fixed intervals, the length of which is the
        configured per-interface constant RxmtInterval.

        Each Database Description contains an indication that there are
        more packets to follow --- the M-bit.  The Database Exchange
        Process is over when a router has received and sent Database
        Description Packets with the M-bit off.

        During and after the Database Exchange Process, each router has
        a list of those LSAs for which the neighbor has more up-to-date
        instances.  These LSAs are requested in Link State Request
        Packets.  Link State Request packets that are not satisfied are
        retransmitted at fixed intervals of time RxmtInterval.  When the
        Database Description Process has completed and all Link State
        Requests have been satisfied, the databases are deemed
        synchronized and the routers are marked fully adjacent.  At this
        time the adjacency is fully functional and is advertised in the
        two routers' router-LSAs.

        The adjacency is used by the flooding procedure as soon as the
        Database Exchange Process begins.  This simplifies database
        synchronization, and guarantees that it finishes in a
        predictable period of time.


    7.3.  The Designated Router

        Every broadcast and NBMA network has a Designated Router.  The
        Designated Router performs two main functions for the routing
        protocol:

        o   The Designated Router originates a network-LSA on behalf of
            the network.  This LSA lists the set of routers (including
            the Designated Router itself) currently attached to the
            network.  The Link State ID for this LSA (see Section
            12.1.4) is the IP interface address of the Designated
            Router.  The IP network number can then be obtained by using
            the network's subnet/network mask.
Top   ToC   RFC2328 - Page 55
        o   The Designated Router becomes adjacent to all other routers
            on the network.  Since the link state databases are
            synchronized across adjacencies (through adjacency bring-up
            and then the flooding procedure), the Designated Router
            plays a central part in the synchronization process.


        The Designated Router is elected by the Hello Protocol.  A
        router's Hello Packet contains its Router Priority, which is
        configurable on a per-interface basis.  In general, when a
        router's interface to a network first becomes functional, it
        checks to see whether there is currently a Designated Router for
        the network.  If there is, it accepts that Designated Router,
        regardless of its Router Priority.  (This makes it harder to
        predict the identity of the Designated Router, but ensures that
        the Designated Router changes less often.  See below.)
        Otherwise, the router itself becomes Designated Router if it has
        the highest Router Priority on the network.  A more detailed
        (and more accurate) description of Designated Router election is
        presented in Section 9.4.

        The Designated Router is the endpoint of many adjacencies.  In
        order to optimize the flooding procedure on broadcast networks,
        the Designated Router multicasts its Link State Update Packets
        to the address AllSPFRouters, rather than sending separate
        packets over each adjacency.

        Section 2 of this document discusses the directed graph
        representation of an area.  Router nodes are labelled with their
        Router ID.  Transit network nodes are actually labelled with the
        IP address of their Designated Router.  It follows that when the
        Designated Router changes, it appears as if the network node on
        the graph is replaced by an entirely new node.  This will cause
        the network and all its attached routers to originate new LSAs.
        Until the link-state databases again converge, some temporary
        loss of connectivity may result.  This may result in ICMP
        unreachable messages being sent in response to data traffic.
        For that reason, the Designated Router should change only
        infrequently.  Router Priorities should be configured so that
        the most dependable router on a network eventually becomes
        Designated Router.
Top   ToC   RFC2328 - Page 56
    7.4.  The Backup Designated Router

        In order to make the transition to a new Designated Router
        smoother, there is a Backup Designated Router for each broadcast
        and NBMA network.  The Backup Designated Router is also adjacent
        to all routers on the network, and becomes Designated Router
        when the previous Designated Router fails.  If there were no
        Backup Designated Router, when a new Designated Router became
        necessary, new adjacencies would have to be formed between the
        new Designated Router and all other routers attached to the
        network.  Part of the adjacency forming process is the
        synchronizing of link-state databases, which can potentially
        take quite a long time.  During this time, the network would not
        be available for transit data traffic.  The Backup Designated
        obviates the need to form these adjacencies, since they already
        exist.  This means the period of disruption in transit traffic
        lasts only as long as it takes to flood the new LSAs (which
        announce the new Designated Router).

        The Backup Designated Router does not generate a network-LSA for
        the network.  (If it did, the transition to a new Designated
        Router would be even faster.  However, this is a tradeoff
        between database size and speed of convergence when the
        Designated Router disappears.)

        The Backup Designated Router is also elected by the Hello
        Protocol.  Each Hello Packet has a field that specifies the
        Backup Designated Router for the network.

        In some steps of the flooding procedure, the Backup Designated
        Router plays a passive role, letting the Designated Router do
        more of the work.  This cuts down on the amount of local routing
        traffic.  See Section 13.3 for more information.


    7.5.  The graph of adjacencies

        An adjacency is bound to the network that the two routers have
        in common.  If two routers have multiple networks in common,
        they may have multiple adjacencies between them.
Top   ToC   RFC2328 - Page 57
        One can picture the collection of adjacencies on a network as
        forming an undirected graph.  The vertices consist of routers,
        with an edge joining two routers if they are adjacent.  The
        graph of adjacencies describes the flow of routing protocol
        packets, and in particular Link State Update Packets, through
        the Autonomous System.

        Two graphs are possible, depending on whether a Designated
        Router is elected for the network.  On physical point-to-point
        networks, Point-to-MultiPoint networks and virtual links,
        neighboring routers become adjacent whenever they can
        communicate directly.  In contrast, on broadcast and NBMA
        networks only the Designated Router and the Backup Designated
        Router become adjacent to all other routers attached to the
        network.



          +---+            +---+
          |RT1|------------|RT2|            o---------------o
          +---+    N1      +---+           RT1             RT2



                                                 RT7
                                                  o---------+
            +---+   +---+   +---+                /|\        |
            |RT7|   |RT3|   |RT4|               / | \       |
            +---+   +---+   +---+              /  |  \      |
              |       |       |               /   |   \     |
         +-----------------------+        RT5o RT6o    oRT4 |
                  |       |     N2            *   *   *     |
                +---+   +---+                  *  *  *      |
                |RT5|   |RT6|                   * * *       |
                +---+   +---+                    ***        |
                                                  o---------+
                                                 RT3


                  Figure 10: The graph of adjacencies
Top   ToC   RFC2328 - Page 58
        These graphs are shown in Figure 10.  It is assumed that Router
        RT7 has become the Designated Router, and Router RT3 the Backup
        Designated Router, for the Network N2.  The Backup Designated
        Router performs a lesser function during the flooding procedure
        than the Designated Router (see Section 13.3).  This is the
        reason for the dashed lines connecting the Backup Designated
        Router RT3.


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:

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


        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
Top   ToC   RFC2328 - Page 60
        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
        directly to the neighbor. On multi-access networks, this means
        that retransmissions should be sent to the neighbor's IP
        address.

        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.
Top   ToC   RFC2328 - Page 61
    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 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:
Top   ToC   RFC2328 - Page 62
            (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.

            (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.
Top   ToC   RFC2328 - Page 63
        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.



              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.
Top   ToC   RFC2328 - Page 64
    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.  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.
Top   ToC   RFC2328 - Page 65
    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.

    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
Top   ToC   RFC2328 - Page 66
        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   ToC   RFC2328 - Page 67
    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.  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
Top   ToC   RFC2328 - Page 68
                                  +----+   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


            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
Top   ToC   RFC2328 - Page 69
            facilitate this, such interfaces are advertised in router-
            LSAs as single host routes, whose destination is the IP
            interface address.[4]

        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
Top   ToC   RFC2328 - Page 70
            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.


        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.
Top   ToC   RFC2328 - Page 71
        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.

            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
Top   ToC   RFC2328 - Page 72
            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.


         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.
Top   ToC   RFC2328 - Page 73
                    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.

           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
Top   ToC   RFC2328 - Page 74
        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

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


        The reason behind the election algorithm's complexity is the
        desire for an orderly transition from Backup Designated Router
        to Designated Router, when the current Designated Router fails.
        This orderly transition is ensured through the introduction of
        hysteresis: no new Backup 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.
Top   ToC   RFC2328 - Page 78
        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-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.
Top   ToC   RFC2328 - Page 79
        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.

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




(page 80 continued on part 4)

Next Section