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.


MPLS with Internet Failover – The Challenge!


I’M BACK!!!  Let’s get right into it!

I have always been interested in automated failover techniques for networks.  We pay all this money for expensive routers, switches, and firewalls, so these devices should provide multiple ways to make a resilient network.  Well, we are lucky because they do!  This project focuses on using MPLS as the primary way to communicate between branches.  If the primary MPLS link fails, we should use the local broadband internet connection to make a site to site VPN back the headquarters.  I threw in a little twist with one branch and made it so it has NO broadband internet connection for failover.  It challenges us to get clever with the design so that if the primary MPLS link dies at the HQ, the branch can still reach it and other branches through its MPLS tunnel.  For this…..we brought in an ASA to act as a VPN concentrator in the provider network to redistribute routes into the customers VRF.  I hope you enjoy the challenge!


The tasks:

– Create simple MPLS network running OSPF internally using Process ID 1 and Area 0
– Share all needed backbone interfaces within the MPLS IGP domain to ensure full connectivity for all routed and routing protocols
– Create an iBGP relationship between all needed PE routers to make sure the solution will work (hint: may not need full mesh iBGP). Use the AS numbers provided in the picture
– Source the BGP relationship from the loopback address of each PE router
– Send both standard and extended BGP community updates using the new format to all iBGP peers
– Create a VRF called “RED” to share all customer routes within the MP-BGP network.
– Create the following eBGP relationships:
○ CE1 <-> PE1
○ CE2 <-> PE2
○ CE3 <-> PE3
– Only customer facing interfaces and routes should be in the RED Routing table
– Use OSPF as the IGP for the HQ, Detroit, and Chicago networks
– Redistribute all learned BGP routes into the IGPs of all customer networks.
– Only allow Vlan10 of the Core switches to be redistributed into BGP at Detroit and Chicago
– When Detroit’s MPLS link fails, routes to the HQ and Chicago should go through the Site to Site VPN to HQ’s firewall.
– When HQ’s MPLS link dies, it should establish a site to site VPN to the Concentrator in the MPLS service provider cloud.
– Failover should be automatic and the tunnel should be able to be established when traffic is generated for any site.
– When failback (MPLS link is restored) occurs, traffic should reroute to the MPLS link again. The site to site VPN’s are for failover only.

The address list is attached to this post along with the topology.  I used 7200 Series routers for this design with an Advanced Enterprise image for the routers and 8.4(2) code rev for the ASA.

Files: MPLS-BGP-VPN-Failover Challenge Lab

Good luck,

Andrew (irc name – anetnerd)