Monday, February 14, 2011

The OSPF Neighbor Establishment Process

This article discusses how 2 neighboring OSPF routers on LAN establish adjacency, exchange link-state database information, and eventually route packets between the networks behind them.

At the beginning, the OSPF neighbor state on both routers is DOWN as they haven’t received any Hello packet each other. The OSPF process is enabled on RT1 at a particular time and triggered RT1 to send multicast Hello packets through all its interfaces participating in OSPF.

Figure 1: Establishing Bidirectional Communication

RT2 which was running OSPF and resides on the same subnet and area as RT1 received the Hello packet from RT1 and entered into the INIT state. RT2 added RT1 into its OSPF neighbor list.

Subsequently, RT2 sent a multicast Hello packet which lists RT1 in the OSPF neighbor list. When RT1 received the Hello packet from RT2, it noticed that another router has received its Hello packet as it is being listed in the neighbor list of RT2’s Hello packet. RT1 entered into the 2-WAY state and added RT2’s Router ID into its neighbor table. At the same time, RT1 immediately sent a unicast Hello packet that lists RT2 in the neighbor list to RT2 in order to speed up RT2 to enter the 2-WAY state as soon as possible. Both routers have established bidirectional communication as they seen each other in their own neighbor lists.
Note: Receiving a DBD packet from a neighbor in the INIT state would also cause a transition to the 2-WAY state. This is often seen in Point-to-Point network setups over serial links.

The DR/BDR election occurs during the 2-WAY state for OSPF neighboring routers reside on broadcast network, eg: Ethernet. The DR/BDR election must occur before the routers can begin to exchange link-state information.

Note: When an OSPF router joins a broadcast network which has a DR and BDR elected, it will only establish adjacency and enter into the FULL state with the DR and BDR. The neighbor state with other non-DR/BDR neighboring routers (DROTHERs) would stays in the 2-WAY state.

Note: When an OSPF router has a higher Router ID or priority than the existing DR or BDR, it does not preempt the existing DR or BDR. This prevents the DR/BDR election process from occurring whenever a new OSPF router joins a broadcast network.

Figure 2: Exchanging Basic Link-State Information

After the DR and BDR have been elected, both routers entered into the EXSTART state, in which the Master and Slave will be elected. Both routers will first claim to be the Master by sending empty DBD packets with a sequence number the Init and Master/Slave (MS) bits set. RT2 which has the higher Router ID would become the Master and controls the database synchronization process, eg: deciding the initial DD sequence number used for DBD exchange. The EXSTART state ends once the Master/Slave relationship is determined.

During the EXCHANGE state, both routers exchange link-state information with multiple DBD packets for them to determine whether they have the same LSAs in their link-state databases. A DBD packet would include one or more LSA headers in the link-state database of the sender. An OSPF router would send only LSA headers instead of the entire LSDB to a neighbor during the EXCHANGE state. The LSA Type, Link-State ID, and Advertising Router fields in an LSA header are enough to uniquely identify a particular LSA. Sequence numbers are being used to determine the newness of link-state information.

The transmission and reception of DBD packets resembles the operation of the TFTP protocol, in which only one DBD packet can be outstanding at a time. The Master will send the next DBD packet only when the previous DBD packet is acknowledged through a DBD packet with the same sequence number from the Slave. If the Master does not receive an acknowledgment for an outstanding DBD packet within the RxmtInterval, it would retransmit the previous DBD packet.

The Slave would send a DBD packet with the same sequence number to acknowledge the receipt of a DBD packet from the Master. Therefore, the last DBD packet is always sent by the Slave.

Figure 3: Exchanging Complete Link-State Information

During the LOADING state, an OSPF router would use LSR packets to request more specific, recent, and complete LSAs from a neighbor router in which the link-state information received during the EXCHANGE state is not in its LSDB or is more recent than the entry in its LSDB. Upon receiving an LSR packet, an OSPF router would reply with an LSU packet which contains the specific and complete LSAs. An LSAck packet is used to acknowledge the LSU sent from a neighbor router. Each LSA must be acknowledged separately to ensure reliable flooding. An LSA is being acknowledged by including its header in the LSAck packet, and multiple LSAs can be acknowledged in a single LSAck packet. To ensure reliability, a router will periodically retransmit an LSA sent to a neighbor until the neighbor acknowledges the receipt of the LSA.

OSPF routers generally delay the acknowledgement of LSAs to fit more LSA acknowledgements into a single LSAck packet in order to conserve bandwidth and router processing resources.

Note: Not all LSAs require explicit acknowledgment. When routing update cross, in which 2 neighboring routers send each other the same instance of LSA at about the same time, the received LSA will be treated as an implicit acknowledgment and no corresponding LSAck packet is required.

Once the database synchronization process ends, both routers conclude that they have identical LSDB and are in fully adjacency state (FULL) with each other. Routers must be in the FULL state before they can forward packets to each other. Once adjacent routers are in the FULL state, they do not repeat the database synchronization process unless the FULL state changes.
Note: At the beginning of the LSDB exchange process, both routers were in merely adjacent state.

9 comments:

  1. This is great stuff. . . .consider me your biggest fun. I hope to reach and every post. keep up the good job

    ReplyDelete
  2. Thanks for your fast comment and enjoy your stay here. More quality info to come... ^_^

    ReplyDelete
  3. grt work... plz continue the good work

    ReplyDelete
  4. The process you describe just only true with multiaccess. With Point-to-Point link, the process may be not true

    ReplyDelete
  5. excellent. after reading ur notes, i am very clear in the DR/BDR election and MASER/SLAVE election. Please continue your clear writing habbits. thanks a lot :)

    ReplyDelete
  6. Why RT2 sending hello to multicast ip (224.0.0.5) , It is in init state means it knows the neighbour so it can directly send to 10.10.10.1 (In Fig 1, second packet)

    ReplyDelete