Link State Routing Protocols

Link State Routing Protocol

Link State Routing Protocols was developed due to the drawbacks that RIP, distance vector routing protocol,  brought to large networks. The two can be though of as, a distance vector router gets its information the same as if we where traveling along a road and getting our directions from a road sign. As with link state router is like us using a road map to get to our destination, we know how to get to our destination before we start our journey. A link state router cannot be fooled as easily into making bad routing decisions, because it has a complete picture of the network. The reason is that unlike the routing-by-rumor approach of distance vector, link state routers have firsthand information from all their peers. The information within a link state network is passed around to each router, the router will take a copy of the information but will never change it. The ultimate objective is that every router has identical information about the network, and each router will independently calculate its own best paths.

Link state protocols are built around a well-known algorithm from graph theory, E. W. Dijkstra’s shortest path algorithm. Some link state routing protocols are;

  • Open Shortest Path First (OSPF) for IP
  • The ISO’s Intermediate System-to-Intermediate System (IS-IS) for CLNS and IP

Link state protocols work with the following functionality;

  • Each router establishes a relationship and adjacency with each of its neighbors.
  • Each router sends a data unit to each neighbor, these are called LSA in OSPF.The LSA lists each of the router’s links, and for each link, it identifies the link, the state of the link, the metric cost of the router’s interface to the link, and any neighbors that might be connected to the link. Each neighbor receiving an advertisement in turn forwards (floods) the advertisement to its own neighbors.
  • Each router stores a copy of all the LSAs it has seen in a database. If all works well, the databases in all routers should be identical.
  • The completed link state database, is used by the Dijkstra algorithm to compute a graph of the network indicating the shortest path to each router. The information for each best path is then sent to the routing table.

Neighbor

Neighbor discovery is the first step in getting a link state environment up and running. A Hello protocol is used between two routers when forming neighbor adjacency.  At a minimum, the Hello packet will contain a router ID (RID) and the address of the network on which the packet is being sent. Other fields of the packet might carry a subnet mask, Hello intervals, a specified maximum period the router will wait to hear a Hello before declaring the neighbor “dead,” a descriptor of the circuit type, and flags to help in bringing up adjacency.

When two routers have discovered each other as neighbors, they go through a process of synchronizing their databases in which they exchange and verify database information until their databases are identical. This can been seen as exchanging information in a controlled fashion.

Hello packets also serve as keepalives to monitor the adjacency. If Hellos are not heard from an adjacent neighbor within a certain established time, the neighbor is considered unreachable and the adjacency is broken.

Link State Flooding

After the adjacencies are established, the routers might begin sending out LSAs. These advertisements are sent to every neighbor. In turn, each received LSA is copied and forwarded to every neighbor except the one that sent the LSA.

When a router floods its LSAs onto a network it will run into the following difficulty with flooding, routers further down the path might receive old LSAs and when the flooding must stop. To overcome these drawbacks when a router receives an LSA it will have a sequence number within the packet that has been updated from its connected neighbor. So take a network that has four routers, R1, R2, R3, R4, R5 and R6;

So if R1 lost the subnet 10.10.10.0/24, it would send out a LSA telling everyone in the network of this lost subnet. So R1 will send a LSA packet to R2 and R4 with a sequence number of 1 and a time value of 0. R2 and R4 will update their link state databases while send on a copy of the LSA onto R3 and R6 with a sequence number of 1 and a time value of 1. R3 repeats the same procdure as R2 and R4 but will send on the LSA with a sequence number of 1 to R5 and a time value of 2. R5 will take this LSA and pass it to R6 with the  sequence number 1 and a time value of 3. So as you can now see R6 has now received 2 LSA with same sequence number but with two different time values of 1 and 3. So what will R6 do with these two LSA?

R6 will have already updated it link state database with the information it received from R4, sequence number 1. It will will not send this LSA onto R4 as it knows that R4 already has this information. R6 knows this because the sequence number of the LSA it received from R5 is the same as the sequence number of the LSA it received earlier from R4.

So that is one why the sequence numbers can help LSA from been passed around a network endlessly. But the sequence numbers really come into play when we say the subnet 10.10.10.0/24 comes back online again. If we follow the same path as before, R1->R2->R3->R5->R6 and R1->R4->R6, R6 will receive a LSA with a sequence number of 1 telling it about the network as been down. R6 will get this LSA from R4 before R5. Now the subnet 10.10.10.0/24 has come back online R1 will send out a LSA with a sequence number of 2. R6 receives this new LSA from R4 before R5 has sent the LSA with sequence number of 1. When R6 receives the LSA from R5 with the sequence number of 1, it knows the information within that LSA is old and will discard the LSA. It will then tell R5 that the LSA he has sent is old and will pass on the LSA with the sequence number of 2. This will stop old LSA from been passed through the network and routers making routing decisions from old routing information.

Aging

As we have already gone through, the aging process adds another layer of reliability to the flooding process. The protocol defines a maximum age difference (MaxAgeDiff) value for the network. A router might receive multiple copies of the same LSA with identical sequence numbers but different ages. If the difference in the ages is lower than the MaxAgeDiff, it is assumed that the age difference was the result of normal network latencies; the original LSA in the database is retained, and the newer LSA (with the greater age) is not flooded. If the difference is greater than the MaxAgeDiff value, it is assumed that an anomaly has occurred in the network in which a new LSA was sent without incrementing the sequence number. In this case, the newer LSA will be recorded, and the packet will be flooded.

The age of an LSA continues to be incremented as it resides in a link state database. If the age for a link state record is incremented up to some maximum age (MaxAge) it is flooded to all neighbors and the record is deleted from the databases.

If the LSA is to be flushed from all databases when MaxAge is reached, there must be a mechanism to periodically validate the LSA and reset its timer before MaxAge is reached. A link state refresh time (LSRefreshTime) is established; when this time expires, a router floods a new LSA to all its neighbors, who will reset the age of the sending router’s records to the new received age.

  • OSPF defines a MaxAge of 1 hour and an LSRefreshTime of 30 minutes.

Link State Database

The link state database stores the LSAs as a series of records. We have just covered a lot of some useful information of what gos on with the LSA’s, sequence numbers and timers, but the important information within a LSA are the advertising router’s ID, its attached networks and neighboring routers, and the cost associated with those networks or neighbors.

  • Router link information advertises a router’s adjacent neighbors with a triple of (Router ID, Neighbor ID, Cost), where cost is the cost of the link to the neighbor.
  • Stub network information advertises a router’s directly connected stub subnets (subnets with no neighbors) with a triple of (Router ID, Network ID, Cost).

The shortest path first (SPF) algorithm is run once for the router link information has establish shortest paths to each router.

SPF Algorithm

The SPF algorithm comes from the Dijkstra’s algorithm, which some people will also call the shortest path first routing algorithm. After all, the objective of every routing protocol is to calculate shortest paths. So Dijkstra’s algorithm is only a part of the OSPF routing process that is used to find the shortest path to every destination.

So when we look at the routing protocol with the Dijkstra’s algorithm, there are three databases been used;

  1. The Tree Database – Links are added to the shortest path tree by adding them here. When the algorithm is finished, this database will describe the shortest path tree.
  2. The Candidate Database – Links are copied from the link state database to this list in a prescribed order, where they become candidates to be added to the tree.
  3. The Link State Database – The repository of all links.

So when the router is working out its database it will follow these procedures;

  • A router initializes the Tree database by adding itself as the root. This entry shows the router as its own neighbor, with a cost of 0.
  • All triples (Router ID, Neighbor ID, Cost) in the link state database describing links to the root router’s neighbors are added to the Candidate database.
  • The cost from the root to each link in the Candidate database is calculated. The link in the Candidate database with the lowest cost is moved to the Tree database. If two or more links are an equally low cost from the root, choose one.
  • The Neighbor ID of the link just added to the Tree database is examined. With the exception of any triple whose Neighbor ID is already in the Tree database, triples in the link state database describing that router’s neighbors are added to the Candidate database.
  • If entries remain in the Candidate database, return to step 3. If the Candidate database is empty, terminate the algorithm. At termination, a single Neighbor ID entry in the Tree database should represent every router, and the shortest path tree is complete.

Areas

An area is a subset of the routers that make up a network. Dividing a network into areas is a response to three concerns commonly expressed about link state protocols:

  • The necessary databases require more memory than a distance vector protocol requires.
  • The complex algorithm requires more CPU time than a distance vector protocol requires.
  • The flooding of link state packets adversely affects available bandwidth, particularly in unstable networks.

These impacts can be greatly reduced by the use of areas. When a network is subdivided into areas, the routers within an area need to flood LSAs only within that area and therefore need to maintain a link state database only for that area. The smaller database means less required memory in each router and fewer CPU cycles to run the SPF algorithm on that database. If frequent topology changes occur, the resulting flooding will be confined to the area of the instability.

 

The routers connecting two areas (Area Border Routers) belong to both areas and must maintain separate topological databases for each. Just as a host on one network that wants to send a packet to another network only needs to know how to find its local router, a router in one area that wants to send a packet to another area only needs to know how to find its local Area Border Router. In other words, the intra-area router/inter-area router relationship is the same as the host/router relationship but at a higher hierarchical level.