Basics of a Link State Protocol – Part 1


I am currently reading a book called “OSPF and IS-IS: Choosing an IGP for Large Scale Networks” by Jeff Doyle and I have to say, 50 pages in and I already like the book.  There is a lot of good detail about the history of link state protocols and how they came to be.  Below are some of my notes from my readings.  This first part focuses on link state protocol basics:

Differences between Distance Vector and Link State Routing Protocols

One of the primary differences between a link state protocol and a distance vector protocol is that dynamic routing protocols like EIGRP, IGRP, and RIP must process the route, increment or manipulate it with it’s own metric calculation, and then pass it to its neighbors.  Link state protocols send the update to neighbors almost as fast as it receives in and calculates best path with it’s own copy of the routing update.  This improves convergence time with the network and makes it more scalable in large scale networks.

High-level framework for a link state routing protocol

  • Every router in a network sends hello messages on its local links and listens for Hellos to discover neighboring routers
  • Every router sends an announcement identifying itself, its directly connected links, and its directly connected neighboring routers
  • Every router receiving an announcement keeps a copy of the announcement in a database, and forwards the announcement to its downstream neighbors
  • When a router has a copy of an announcement from every other router in its database, it can accurately calculate routes to destinations

Since we are calculating routes independently in every router without the influence of other neighbors (distance vector manipulates routes before sending updates to neighbors), we must have a mechanism that sends routing information, unaltered, to other neighboring routers.

OSPF uses Link State Advertisements (LSA)
IS-IS uses Link State Protocol data units (LSP)

Vector based protocols are susceptible to loops because the router is only aware of its directly connected links.  This “routing by rumor” methodology can cause slow convergence and/or inefficient routing topologies

Link state protocols allow each router to have its own “image” of the network so it can make shortest path calculations with the whole network in mind.  This does not mean link state routing protocols are immune to loops.  During a flooding of advertisements, all databases are not identical so loops can occur.

Typically a link state router only has information about it’s directly connected links and routes learned from another routing protocol.

Fundamental concepts of a link state routing protocol

  • Adjacencies
  • Flooding
  • Link State Database
  • SPF Calculations


Two routers are considered neighbors when they are both using a common routing protocol with similar parameters that allow the exchange of information.  Two routers that are neighbors in this manner are said to be adjacent.

Common attributes to a link state routing protocol:

  • Router ID (RID)
  • Authentication

Hello packets advertise different attributes about link state neighbors

  • Timer settings
  • Interface parameters
  • Authentication Information
  • Router ID

Network statements are used in cisco routers to identify which interfaces should be used to send Hello packets.  Any interface IP address matching a network statement will send multicast or broadcast Hello packets out that interface.  These Hello packets should never be forwarded out from one interface to another.  Hello packets have their TTL set to 1 to prevent this from happening.

Routers forming an adjacency must perform a handshake.  This is done to make sure a router does not accidentally create an adjacency with a router on a unidirectional link.  Packets could be lost due to:

  • bad cabling
  • packet corruption
  • incompatible link parameters
  • Unacceptable protocol parameters in the Hello packets

A handshake is performed by a router including its neighbors router ID from Hello packet information it received on it directly connected interface in its own Hellos to that neighbor.  For example:

  • Router A receives a Hello packet from Router B
  • Router A creates its own Hello packet with Router B’s Router ID (RID) and sends it out the directly connected interface attached to router A and B
  • Router B receives the Hello packet and sees its own Router ID in the Hello packet.  These Routers “see” each other now and can continue down the path to form an adjacency (as long as there are no other parameters that would stop this relationship from forming)

This process is called the “three-way handshake”

After the adjacency is formed, these Hello packets will serve as keepalives for the adjacency

One of the protocol parameters is how often Hello’s are sent between Routers during their adjacency.  The frequency and amount of Hello packets allowed to be missed before the relationship is declared dead can be negotiated in some link state protocols while others cannot.