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
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
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.
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.
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.
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
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.
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
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. 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 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. 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. (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. 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. 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. 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.
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
+----+ 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
facilitate this, such interfaces are advertised in router- LSAs as single host routes, whose destination is the IP interface address. 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. 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. 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. 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. 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 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,
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) 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 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. 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-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. 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.