Home > BSCI, CCNP, ROUTE > SPF algorithm

SPF algorithm

As I mentioned on my EIGRP Metric Lab, this post is dedicated to SPF algorithm and the cool  Dijkstra’s algorithm. I do not want to get too techie in this post, just to get the general concept. I’ll point you at the end of the post to some good in-depth reads.

Dijkstra's algorithm

OSPF and IS-IS are link-state protocols, they use Shortest Path First (SPF) to calculate distance between the routers and create the routing table.

For the SPF algorithm to work, it requires all routers in the OSPF\IS-IS network to know about links and all the other routers in the same network.

OSPF encode its link-state information in Link State Advertisements (LSAs) and floods it. IS-IS encode its information in a Link State Packet (LSP).

When the initial data collection process is completed, OSPF \ IS-IS process runs the Dijkstra Shortest Path First algorithm to find the shortest path from itself to all the other routers in the network. The same process happen on each router in the network. When the algorithm processing is completed, all the routers have a similar table and consistent routing can start.

How does it work?
Dijkstra algorithm put the router as the root of a tree and calculate the shortest path to each destination. While the overall picture on all routers is similar (they all have the same routers and links), each router look differently at the result as the point of view is personal. It is just like in life – you share a room with 3 other people, each one stand in a different corner. When you are asked to describe an object you describe the exact same object but it does look a bit different from different angels.

When any change is noticed (link state change), SPF start the calculation all over and re-build the map. OSPF ability to use many areas is a way to reduce these frequent updates as it has less routers per area. This is a major consideration when using a link-state protocol.

Two recommended reads that actually describe the shortest path calculation step by step are:
1. Example & descriptive explanation to how does SPF algorithm work in OSPF and IS-IS.
2. RFC 2328 is also a good read to get better understanding on the OSPF protocol.

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: