Link state Routing(dynamic)

Distance Vector routing was used in ARPANET (1979) till it is replaced by Link State Routing.

The two problems in Distance Vector Routing are

  1. DVR doesn’t take line Band width into account since the design metric is delay.(initially all lines are 56 Kbps so line Band width is not an issue but when lines are upgraded with 230 Kbps, 1.54 Kbps then the problem arises if we will not consider Band width).
  2. one more problem that occurs in DVR is count-to infinity problem.

for these reasons it was replaced by new algorithm known as  Link State  Routing algorithm (LSR) algorithm.

the main idea of LSR is as follows(for a Router)

Step 1:- Discover it’s neighbors and learn their N/W addresses.

Step 2:-Measure the delay (or) cost to each of it’s neighbors.

Step 3:- Construct a packet with the information a Router has learned.

Step 4:- Send this packet to all the Routers.

Step 5:-Compute the shortest path to every other Router.

for example,

S 1:-Learning about the neighbors

first of all, when a Router is booted to learn about it’s neighbors it will send a packet called ‘HELLO’ on each point-to- point line.

the Router on the other hand is expected to send back a reply saying who it is?

when two (or) more Routers are connected by a LAN, the situation is more complicated and the Routers are named uniquely to avoid any conflicts.

In the LAN A, C and F are connected to LAN, when a distance Router hears that 3 Routers are all connected to F, it is essential to know whether all 3 means same F (or) not?

To avoid this we can treat LAN as an additional node N as below

N in the above figure is an artificial node, the path from A to C is represented as ANC.

S2:- each Router in LSR requires to know an estimate of delay to each of it’s neighbors.

one way to measure delay send an ECHO packet and get reply immediately and then calculate the round-trip-delay t/2 .

for better results perform this same no.of times and use the average.

while measuring delay one question that arises is to consider the load (or) not? If load is considered, the round trip timer must be started when ECHO packet is queued.

when load is ignored the timer shouted be started when the ECHO packet reaches the front queue.

when a Router has a choice between 2 lines with the same Band width one of which is loaded all the time and the other one  is not loaded at all.

Then Router will chose the time with less load as the shortest path, this will result in better performance.

Consider a Sub net which is divided into 2 parts X and Y an is connected by 2 lines CF and EI.

Suppose the line CF is heavily loaded with long delays(including Queuing delay) after the new Routing tables have been installed most of the traffic will now go on EI.

Consequently in the nest update CF will appear as best path. Routing Tables may oscillate wildly causing some potential problems.

One solution to this is to divide the load equally among the lines but that may disturb the concept of best path.

S3:- Building link state Packets

Once the transformation needed for the exchange has been collected the next step is for each Router is to build a link state packet.

link state packet consists of information regarding to sender , sequence no, Age, neighbors delays.

for example consider the Sub net 

These link state packets have to build periodically and also when a Router going down etc.

S4:- Distributing the Link State Packets

The net thing is to distribute the  Ls packets reliably. in order to distribute the packets we may use flooding , to make flooding more efficient we use sequence numbers to packets.

The main problem is with sequence no’s repetition of Seq.nos one solution is to use a 32 bit which may take 137 years to repeat the same no.

If a Router crashes the sequence no becomes a zero then there is a possibility a Router may discards it.

To avoid all the above problems we use a parameter called Age whenever Age=0 the Router discards a packet .

after distribution process we use refinements to this distribution process(flooding).

whenever a packet arrives it first placed in a holding area later on another packet arrives the 2 Seq.nos are compared , if they are equal the duplicate is discarded.

The figure shows the buffer space at Router B

Suppose a packet is coming from source A with 21 and Age as 60 

we may expect an Acknowledgement from C and F but not from A.

Computing the new Routes for a Router :-

after constructing the LS packets to all the Routers 

we may use Dijkstra’s algorithm to construct the shortest path to all the destinations and this can be updated from time to time. 


1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)





Author: Lakshmi Prasanna Ponnala

Completed M.Tech in Digital Electronics and Communication Systems and currently working as a faculty.