Question:
OSPF — Open Shortest Path First — the mechanism behind this link state routing protocol

Answer:
OSPF is an IP routing protocol. It is registered with the Network Information Center (NIC) under protocol number 89. OSPF is a Link-state algorithm based routing protocol. Link-state or shortest path first (SPF) algorithms are alternatives to the vector distance algorithms (RIP uses this algorithm).

Before we understand how OSPF routing works, let us define the meaning of the term area:

An area refers to a set of networks that are grouped together. When networks are grouped into areas, routing traffic is substantially reduced. Routers within the same area use the same topology database. Therefore, routing inside a given area is based on the same topology database. Routers that are connects to multiple areas maintain multiple topology databases and are referred to as area border routers.

Two routers that have interfaces to a common network are neighboring routers.

Adjacency refers to a relationship that is formed between neighboring routers. The purpose of this relationship is the need for exchange of routing information.

An interface is the connection that exists between a router and its attached network(s). An interface also contains state information that is associated with it, gathered from the lower-layer protocol and the routing protocol itself.

Examples of some of these states are:

• DR: The router is the Designated Router on the attached network. This router carries the responsibility of sending out link state advertisements for the network.
• Backup: This is the state that designates a router as a backup designated router for the network. This router will be promoted to DR if the designated router fails.

A link state advertisement reflects the state of the router’s interfaces and adjacencies, and is flooded throughout the routing domain. When all link state advertisements are collected from all routers in all networks, we have a topological view of the entire network.

Type of Service (TOS) metrics are part of the link state advertisement. TOS 0 for OSPF routing protocol packets must always be specified. Lower TOS metrics will attract higher bandwidth traffic.

The topological database is a collection of the link state advertisements. This is also referred to as a directed graph or a link state database. Each router can then run the SPF algorithm on its link-state database and generate a shortest-path-first tree, which will provide a map to any given destination network or host.

OSPF permits contiguous networks to group together into areas. Each area will therefore have its own topology database. The topology of an area is invisible to routers outside the area. Routing can now take place at two levels: intra-area routing, the routing of packets within the same area (this can be accomplished by using the area’s topological database alone); and inter-area routing, the routing of packets between areas.

Now that we have defined the relevant terms, let us examine how OSPF functions:

1. When OSPF routers are initialized, the first task they perform is neighbor discovery. The hello protocol is used to establish bi-directional communications with neighboring routers. When a router recognizes itself in another router’s hello packet, it knows that it just discovered a neighbor.
2. A designated router and the backup designated router are now elected. This is done using the OSPF hello protocol. The election proceeds by the process of elimination. Each router’s adjacencies and priority are examined. Any routers with less than full two-way adjacencies are eliminated first. The hello packets that are being exchanged are checked to see if backup designated routers exist. If so, the one with the highest router priority is elected the new backup designated router. If no backup designated router information is being exchanged, then of the remaining routers, the router priority is used to break the tie and elect the new backup designated router. The designated router is now elected. If no routers have declared themselves the designated router, the backup is promoted to become the designated router.
3. The adjacencies between the routers are now brought up. Decisions are made as to whether adjacencies are formed between neighboring routers. When bi-directional communication is established between two neighboring routers or when the designated router changes, adjacencies must be established. The mechanism to establish adjacencies between OSPF routers takes place via the database exchange process, in which link-state database descriptions are exchanged between routers. A poll-response communication ensures that the master sends out the database packets and the slaves acknowledge receipt of same.
4. The databases are now synchronized, and each router has a list of link state information that was gathered during the database exchange process. The routers are now said to be fully adjacent.
5. The routing table can now be calculated using the shortest path first (SPF) Dijkstra algorithm.

OSPF is a sophisticated routing method that offers many advantages such as TOS (type of service) features, in which different routes can be configured for each type of service. Metrics can add weight to different types of links; for example, a 56 Kbps links can have a metric of six while a T1 can carry a metric of two, therefore attracting more traffic. OSPF also provides load balancing, because gateways can now calculate more than one path to the destination from the routing table. In addition, OSPF supports variable-length IP subnetting, host-specific and network-specific routes. It also greatly reduces the amount of broadcast traffic on the network.