Open Shortest Path First

1 Introduction

1.1 What is OSPF?

Open Shortest Path First (OSPF) is a classless link-state routing protocol developed in 1987 by the Internet Engineering Task Force (IETF) as a replacement to the distance vector routing protocol RIP. It uses a metric named cost, which is calculated using the bandwidth on all links of the determined path. It is built for scalability and it uses the concept of areas for this purpose.

1.2 Advantages

  • Scalability - it is built with this purpose in mind and it does it very well and unlike RIP, it is not limited by hop count
  • Fast Convergence - it is a very fast protocol, converging in a matter of milliseconds
  • Areas - allows the administrator to build a logical topology based on areas, which helps convergence and summarization
  • Knows the Topology - it builds a topology of the entire area

1.3 Disadvantages

  • Processor-intensive - every time there is a topology change, a full recalculation is done (can be mitigated by a featured called ISPF)
  • Requires more memory - because it knows the topology of the entire area

2 Pieces of OSPF

2.1 OSPF Tables

OSPF makes use of three tables to do its work:

  • Neighbor table - directly connected neighbors with which this router has an adjacency relationship
  • Topology table - this holds the list of LSAs that create the overview of the entire area.
  • Routing table - the best routes calculated by OSPF will end up in the global routing table

2.2 OSPF Packet Types

OSPF uses five types of Link-State Packets (LSPs):

  • Hello - establishes and maintains adjacency relationships using the Hello protocol
  • Database Descriptor (DBD) - an abbreviated list of the sending router's Link-State Database (LSD) used to check against the receiving router's database
  • Link State Request (LSR) - requests more information about an entry in the DBD
  • Link State Update (LSU) - announces route information periodically or as a reply to an LSR
  • Link State Acknowledgement (LSAck) - confirms receipt of an LSU packet

2.3 The Link-State Update (LSU) Packet

The LSU packet, used for sending rounting information updates contains one or multiple Link-State Advertisements.
An LSA can be one of the following types:

  • Type-1 (Router LSA) - information about the directly connected networks of each router and there is only one of these LSAs per router
  • Type-2 (Network LSA) - used for Broadcast Multi-Acess (BMA) and Non-Broadcast Multi-Access (NBMA) networks. It is managed by only one router in the segment (the DR router) and there is only one of these LSAs per segment
  • Type-3 (Summary-net LSA) - generated by Area Border Routers (ABRs), used to distinguish routes coming from a different area. There is only one of these LSAs per route
  • Type-4 (ASB Summary LSA) - generated by Area Border Routers (ABRs) who know an ASBR router in their area, used to tell the routers outside the area that the generating (ABR) router is the next hop for routes coming from the ASBR
  • Type-5 (ASBR Summary LSA) - external routes, one such LSA per route
  • Type-7 (NSSA LSA) - special LSAs used by Not So Stubby Areas (NSSAs). These are converted into Type-5 LSAs by Area Border Routers

This information can be used when troubleshooting OSPF. Knowing what types of LSA's are expected to be on each router allows the administrator to gather valuable information by checking each router's database.

3 The Hello Protocol

The Hello Protocol uses the first type of OSPF packet to do the following:

  • Discover OSPF neighbors and establish adjacencies
  • Advertise the parameters on which both routers must agree
  • Elect the Designated Router (DR) and Backup Designated Router on Broadcast Multi-Access (BMA) and Non-Broadcast Multi-Access (NBMA) networks.

3.1 Neighbor Establishment

Each router that is configured to run OSPF will send a Hello Packet on each OSPF-enabled interface periodically (10s on P2P, BMA networks and 20s on NBMA networks). This packet includes the router ID, area ID and list of neighbors.
The local routers checks that the parameters sent by the remote router are acceptable. The parameters that OSPF requires to be identical are: Hello Timer, Dead Timer, Area ID, interface Network Mask and Authentication Password.

The Protocol has the following states:

  1. Down State - the router has not yet received a Hello Packet from the remote router
  2. Attempt State - similar to the Down state, but for manually configured neighbors in NBMA networks
  3. Init State - received a Hello Packet from the remote router but the local router's ID is not listed as Neighbor
  4. 2-Way State - received a Hello Packet and the local router ID is listed as Neighbor. This state is also when the DR/BDR Election takes place
  5. Exstart State - the DR/BDR have been elected and the routers have begun exchanging link-state information. A slave-master relationship (per adjacency) is created here as well, based on router priority and router-id
  6. Exchange State - the routers begin exchanging DBD packets on each adjacency, beginning with the slaves
  7. Loading State - based on the DBD packets, the routers request any information and reply to any LSR packets, beginning with the slaves
  8. Full State - the neighbors are synchronized, their databases are identical and the neighbor relationship is up

Once they are in the Full state, the routers run Dijkstra's Shortest Path algorithm with themselves as root of the Shortest Path Tree (SPT) in order to find the best path.

3.2 DR/BDR Election

OSPF elects a Designated Router (DR) and Backup Designated Router (BDR) on BMA and NBMA networks. In such a network, the routers share a segment and will establish Full relationships with all routers in that segment. The result is a full mesh of neighbor relationships and a very high amount of update packets, which in turn consume processor cycles and bandwidth.

This problem is addressed by electing a DR and a BDR. Instead of being sent to all routers, updates on the segment will be sent only to the DR and BDR and the DR will decide whether the update causes any change. The DR will send it to the other neighbors only if necessary, thus eliminating a large amount of traffic. The role of the BDR is to gather information and be ready to replace the DR in case the DR fails.

Each router establishes a Full relationship with the DR and BDR, but stops at a 2-Way relationship with all other routers in the segment. Updates destinated to the DR and BDR are sent on multicast address, while updates sent to other neighbors are sent on multicast address

The election process is based on two pieces of information:

  • Router Priority - the router with the highest priority will become DR
  • Router-ID - the router with the highest router-id will become a DR if the router priority is tied

4 Configuration

The configuration example is on a separate page: Basic OSPF Configuration

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License