Introduction

            The OSPF protocol (Open Shortest Path First) is a link-state routing protocol created in 1988 by IETF (RFC 2328). It's actually the most common IGP (Interior Gateway Protocol) : it's a non-owner and free protocol.

            The link-state allows to the router to have a global vision of network and its topology, and the update's broadcasting is launching only when there is a topology modification. OSPF protocol is a classless routing protocol which hold VLSM.

            To generate routing table, OSPF protocol uses a SPF Tree (Short Path First Tree) and an SPF algorithm called Dijkstra algorithm : it specifies the best path in cost term.

            An OSPF network can be composed of one or several routing domains, the areas, in a same autonomous system : area 0 is the backbone area.

            The topological updates will be executed with a multicast address and non-broadcast : each router gets knowledge on his own interfaces state, then this informations are sent to all neighbors routers.  All routers'll have the same database on connections's state of all others routers in the same area.

OSPF interfaces differenciate four network's types :
• Point-to-Multipoint network
• Point-to-Point network
• Point-to-Multipoint broadcast network
• Point-to-Multipoint non-broadcast network (NBMA : non-broadcast multi-access)

            To reduce the number of routing's informations exchanged among all routers in a same network, routers will elect a DR (Designated Router) and a BDR (Backup Designated Router) which will be the central point of exchange.

            OSPF routers establish links with theirs neighbors to share link-state informations. OSPF permits to send 5 packets type :

1. Seven states of OSPF

The 7 states OSPF split in two parts : discovery of neighbors routers (3 first states) and discover the routes (4 next states).

Down State : in this state, there isn't information exchange between neighbors. OSPF waits to enter in the next step.

Init State : routers OSPF send theirs HELLO packets (type 1) with regular intervals to establish a relationship between neighbors routers. When an interface receives the first HELLO packet, the router enters in Init-State : it means that the router knows there is a neighbor and waits to enter in relationship in the next step.

Two-Way State : using HELLO message, a router tries to establish a two-way communication with all neighbors of the same network. HELLO packet contains a known neighbors list : the router enter in this state when it sees itself in the list sent by a neighbor.

            The Two-Way State is the primary relationship that an OSPF neighbor can establish, but any routing information is shared. To learn the link-state of others routers and build a routing table, each router have to make an adjacency with its neighbor(s).

ExStart State : ExStart is establish using Database Description packets. The two neighbors routers use HELLO packets to negociate who will be the master or the slave of the relationship. The router with the highest OSPF ID will become the master. When theses roles are defined, the next step begins with sending of routing informations.

Exchange State : in this state, the neighbors routers use Database Description packets (type 2) to send informations. The routers describe their link-state database to others. If they learn new informations, they ask a fully update to their neighbor. The fully routing informations are exchanged in the next step.

Loading State : routers used Link-Sate Request packets (type 3) to ask fully routing informations. When a router receives a LSR, he answers with an update using Link-State Update packet (type 4).

Full Adjacency : when the loading state is complete, the routers are fully adjacency. Each router keeps a list of its neighbors called adjacency database.

2. Election of DR and BDR

            A neighbor relationship is necessary between OSPF routers to shared routing informations. A router will try to become adjacent with one router at which it is connected. Some routers try to become adjacent with each neighbor router, others try with one or two. All that is determined functions of network type. When there is an adjacency between two neighbors, the link-state informations are exchanged.

Network type	Features	Election of a DR ?
Broadcast multiaccess	Ethernet, Token Ring, ou FDDI	Yes
Nonbroadcast multiaccess	Frame Relay, X.25, SMDS	Yes
Point-to-point	PPP, HDLC	No
Point-to-multipoint	Configured by administrator	No

              If each router had to establish a fully adjacency with all others routers and exchanged link-state informations with their neighbors, the network and all routers will be overcharged : the election of a DR (Designated Router) will resolve the problem. This router becomes adjacent with all routers on the same broadcast segment. All others routers send theirs link-state informations to the DR. The DR is the mouthpiece for the segment : it will send link-state informations to all others routers of the segment with multicast address 224.0.0.5.               The election of DR is followed by the election of BDR (Backup Designated Router) which is the backup if DR is down. The multicast address 224.0.0.6 is used to see the link-state of all routers in the segment.

3. Example of configuration

            This example allows us to review what we've seen and how OSPF makes election of DR and BDR functions of network type.

            First, we have to configure routers, and then, we'll describe different operations of OSPF protocol :

1 - Configuration of routers
2 - Establish adjacency of routers
3 - Election of DR and BDR
4 - Routes discovery
5 - Routes selection
6 - Maintenance of routing informations

 

3.1 Configuration of routers

Routeur A :

Router> enable
Router# configure terminal
Router(config)# hostname RTA
RTA(config)# interface loopback 1
RTA(config-if)# ip address 10.2.0.1 255.0.0.0
RTA(config-if)# no shut
RTA(config-if)# exit
RTA(config)# interface Ethernet0
RTA(config-if)# ip address 10.1.0.1 255.255.0.0
RTA(config-if)# ip ospf hello-interval 20
RTA(config-if)# ip ospf dead-interval 60
RTA(config-if)# no shut
RTA(config-if)# exit
RTA(config)# interface Ethernet1
RTA(config-if)# ip address 10.2.0.1 255.255.0.0
RTA(config-if)# ip ospf hello-interval 20
RTA(config-if)# ip ospf dead-interval 60
RTA(config-if)# no shut
RTA(config-if)# exit
RTA(config)# router ospf 1
RTA(config-router)# network 10.1.0.0 0.0.255.255 area 0
RTA(config-router)# network 10.2.0.0 0.0.255.255 area 0
RTA(config-router)# exit
RTA(config)# exit
RTA# copy running-config startup-config
RTA# exit

Routeur B :

Router> enable
Router# configure terminal
Router(config)# hostname RTB
RTB(config)# interface loopback 1
RTB(config-if)# ip address 10.3.0.1 255.0.0.0
RTB(config-if)# no shut
RTB(config-if)# exit
RTB(config)# interface Ethernet0
RTB(config-if)# ip address 10.2.0.2 255.255.0.0
RTB(config-if)# ip ospf hello-interval 20
RTB(config-if)# ip ospf dead-interval 60
RTB(config-if)# no shut
RTB(config-if)# exit
RTB(config)# interface Serial0
RTB(config-if)# ip address 10.3.0.1 255.255.0.0
RTB(config-if)# ip ospf hello-interval 20
RTB(config-if)# ip ospf dead-interval 60
RTB(config-if)# no shut
RTB(config-if)# exit
RTB(config)# router ospf 1
RTB(config-router)# network 10.2.0.0 0.0.255.255 area 0
RTB(config-router)# network 10.3.0.0 0.0.255.255 area 0
RTB(config-router)# exit
RTB(config)# exit
RTB# copy running-config startup-config
RTB# exit

Routeur C :

Router> enable
Router# configure terminal
Router(config)# hostname RTC
RTC(config)# interface loopback 1
RTC(config-if)# ip address 10.3.0.2 255.0.0.0
RTC(config-if)# no shut
RTC(config-if)# exit
RTC(config)# interface Serial0
RTC(config-if)# ip address 10.3.0.2 255.255.0.0
RTC(config-if)# ip ospf hello-interval 20
RTC(config-if)# ip ospf dead-interval 60
RTC(config-if)# no shut
RTC(config-if)# exit
RTC(config)# router ospf 1
RTC(config-router)# network 10.3.0.0 0.0.255.255 area 0
RTC(config-router)# exit
RTC(config)# exit
RTC# copy running-config startup-config
RTC# exit

Some commands of maintenance :

Router#show ip ospf
Router#show ip ospf neighbor detail
Router#show ip ospf database
Router#show ip ospf interface

Note : It's important to specify timers (ip ospf hello-interval & ip ospf dead-interval) which have to be the same on each router.

3.2 Establish adjacency of routers

            In this first step, routers'll go at least to Two-Way state to establish adjacency.

             In our example,  Router B send HELLO packets to announce its ID, by its E0 and S0 interfaces : Routers A & C receive them and enter in Init State with Router B.
Then, Router B receives HELLO packets of its 2 neighbors and will see its own ID : there is now a Two-Way State between A & B, and B & C.

            Router B will determine what is the adjacency establishment mode based on network type :
- if network is Point-to-Point type, the router become adjoining with its only neighbor
- if network is multi-access type, the router launchs election's proccess of DR and BDR.

3.3 Election of DR and BDR

            The election is made dint HELLO packets which contain router ID and a field "Router priority" (8 bits : from 0 to 255) : the router which have the highest priority will win the DR election. A priority equal to 0 assures the defeat of the router while a priority equal to 255 assures the win.

            The field "Router ID" is used to separate some routers which possibly have the same priority : it'll take the highest value of physical interface IP address on the router or loopback interface (logical interface). When the DR and BDR are elected, their roles won't change even if a router with a stronger priority is put on the network.

 

            Routers B & C are connected by Point-to -Point Protocol (PPP) : a DR isn't necessary on network 10.3.0.0/16.

            Networks 10.1.0.0/16 and 10.2.0.0/16 are Ethernet Broadcast Multiaccess network : a DR and BDR will be elected.

            Networks 10.1.0.0/16 and 10.2.0.0/16 are Ethernet Broadcast Multiaccess network : a DR and BDR will be elected.
- Network 10.1.0.0/16 : router A is alone, it'll be the DR.
- Network 10.2.0.0/16 : routers A & B have the same priority (default is 1, and we didn't change the parameter). The field "Router ID" will decide who is the DR :
[ B = 10.3.0.1 ] > [ A = 10.2.0.1 ], B becomes the DR and A the BDR.

            The election of DR and BDR are terminated, routers are now ready to exchange routing informations with adjacencies routers and to build their link database.

3.4 Routes discovery

            The routers are now ready to engage in Exchange process. In ExStart state, routers will determine which one begin to send informations. Here, the rule is to establish a Master/Slave relationship between two routers. The router which announces the highest ID will begin and choreograph the exchange.

            When theses roles are established, the routers enter in real Exchange state. The master guides the slave to an exchange of DataBase Description packets (DBDs) which describe the link database of each router in details. Theses descriptions contain the type of link-state, the router address which makes exchange, the link cost and a sequence number.

            Routers confirm the reception of DBDs sending LSAck packets which contain a conformity with sequences numbers sent in DBDs. Each router compares the informations it receives with what it knows yet.
            If some DBDs announce new link-states or link-states updates, the router which receives them enter in Loading state and send LSR packets (type 3) about new informations.
In response to LSR packets, the other one will send complete link-state informations of LSUs packets (type 4). In fact, LSUs carry LSAs.
When Loading state is finished, the routers enter in full adjacency, they can create their routing table and make traffic. The routers of a same area have now the same link-state database.

3.5 Routes selection

            After that a router have completed its link-state database, it can create its routing table and begin to transfer traffic. OSPF uses the cost for metric to determine the best path. The cost default value depends on bandwith value of a link. Here are the cost default values functions of media type :

Media type	Cost
Serial line 56kbps	1785
T1 (serial line 1544kbps)	64
E1 (serial line 2048kbps)	48
Token Ring 4 Mbps	25

            To calculate the lowest cost to a destination, the router will execute SPF algorithm. If there are several paths to a destination, the path with the lowest cost will be choose. By default, OSPF notes 4 equal routes in its routing table to permit the load balancing.

3.6 Maintenance of routing informations

            When a router installed its routes in its routing table, it must maintains its routing informations. When there is a link-state modification, OSPF routers use a flooding process to inform other routers. The dead interval of HELLO protocol permits an easy mechanism to announce a link dead. When an interface don't have news of a link after this period, the link is reputed down.

            The routeur which notices the link down send a LSU with new link-state informations :
- On a Point-to-Point network, there aren't DR or BDR. The new link-state informations are sent on multicast address 224.0.0.5. All OSPF routers listen at this address.
- On a Multiaccess network, a DR and a BDR exist and maintain adjacencies with all others routers. If a DR or a BDR need to send a link-state update, it send it to address 224.0.0.5. However that may be, the others routers of network are only adjoined to DR and BDR and they send theirs LSUs to them. That's why DR and BDR have their own multicast destination address 224.0.0.6. The routers which aren't DR or BDR send theirs LSUs to 224.0.0.6.

            When a DR receives an LSU specified to 224.0.0.6, if floods others routers with LSU on 224.0.0.5. So each router will send LSAck.

            If an OSPF router is connected to another network, it floods others networks with LSU. The DR of the network will send  LSU to all routers in its network.

            When a router receives a LSU, it updates its link-state database and uses SPF algorithm to calculate the new routes to record on its routing table.

            On Cisco routers, an old route is used when SPF algorithm calculates the new routes.

            It's important to notice that even if there is any topological modification, routing informations are regularly refreshed.

            Each LSA have its own shelf life. The counter have a shelf life of 30 minutes. After this time, the router which was the source of information send a LSU to the network to verify that the link is always up.

Conclusion

            The OSPF protocol was specially formed for large networks and even if it's very greedy in process term when network subjected to frequently topological modifications, its utilization in firms is always presented.

            This article doesn't cover all differents cases which OSPF can be used : you'll find on Internet lots of examples adapted to conditions of your network.

Cisco advises documentations on OSPF configuration with examples :

http://www.cisco.com/univercd/cc/td/doc/product/software/ios122/122cgcr/fipr_c/ipcprt2/1cfospf.htm

http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/ospf.htm