OSPF

Short for Open Shortest Path First. A link-state IGP standardized in RFC 2328.

Each router builds a complete topology map of its area using LSAs, then runs Dijkstra’s algorithm to compute shortest paths. Operates over IP directly using protocol number 89. Supports VLSM and CIDR. Faster convergence than RIP.

Cost Metric

Lower cost is preferred. A $100$ Mbps link has cost $1$; a $10$ Mbps link has cost $10$.

Hello Protocol

OSPF routers discover neighbors and maintain adjacency using Hello packets. Sent to multicast address 224.0.0.5 every Hello interval.

Key fields in a Hello packet:

• Router ID
  Unique 32-bit identifier, typically the highest loopback IP.
• Hello interval
  Default $10$ s on broadcast networks, $30$ s on NBMA.
• Dead interval
  Default $4\times$ Hello interval. Neighbor declared dead if no Hello received within this window.
• Area ID
  Must match between neighbors.
• DR and BDR
  Current Designated Router and Backup Designated Router on the segment.

2 routers form a neighbor relationship only if Hello interval, Dead interval, Area ID, and authentication match.

Adjacency States

OSPF neighbor relationships progress through 7 states:

• Down
  No Hello received from neighbor.
• Init
  Hello received, but own Router ID not yet seen in neighbor’s Hello.
• 2-Way
  Own Router ID seen in neighbor’s Hello. DR/BDR election occurs here on broadcast segments.
• ExStart
  Master/slave relationship established; initial sequence number negotiated.
• Exchange
  Database Description (DBD) packets exchanged to summarize LSDB.
• Loading
  Link State Request packets sent for missing LSAs; Link State Update packets received in response.
• Full
  LSDBs are synchronized. Adjacency is complete.

DR and BDR Election

On broadcast segments (Ethernet), OSPF elects a Designated Router (DR) and Backup Designated Router (BDR) to reduce the number of adjacencies from $O(n^2)$ to $O(n)$.

All routers form Full adjacency only with the DR and BDR. Non-DR/BDR routers (DROthers) send LSAs to 224.0.0.6; DR floods them to 224.0.0.5.

Election process:

• Router with highest OSPF priority wins DR. Default priority is $1$.
• Tie broken by highest Router ID.
• Priority $0$ makes a router ineligible for DR/BDR.
• Election is non-preemptive. A new higher-priority router joining does not displace the current DR.

Areas

OSPF uses a 2-level hierarchy to scale. All areas must connect to the backbone area (Area 0).

• Backbone area (Area 0)
  Core area. All inter-area traffic passes through it.
• Regular area
  Receives all LSA types including external routes.
• Stub area
  Blocks Type 5 LSAs (external routes). Uses a default route instead.
• Totally stubby area
  Blocks Type 3, 4, and 5 LSAs. Only intra-area routes and a default route.

Routers connecting 2 areas are called Area Border Routers (ABR). Routers connecting OSPF to another routing domain are Autonomous System Boundary Routers (ASBR).

LSA Types

OSPF routers flood Link State Advertisements to share topology information.

• Type 1 (Router LSA)
  Generated by every router. Describes the router’s links within an area. Flooded within the area only.
• Type 2 (Network LSA)
  Generated by the DR on broadcast segments. Lists all routers on the segment. Flooded within the area only.
• Type 3 (Summary LSA)
  Generated by ABRs. Advertises routes from one area into another. Flooded between areas.
• Type 4 (ASBR Summary LSA)
  Generated by ABRs. Tells routers in other areas how to reach the ASBR.
• Type 5 (AS External LSA)
  Generated by ASBRs. Advertises external routes (redistributed from other protocols). Flooded throughout the OSPF domain except stub areas.