Link State Routing Algorithm

Link state routing is a technique in which each router shares the knowledge of its neighborhood with every other router in the internetwork.

The three keys to understand the Link State Routing algorithm:

• Knowledge about the neighborhood: Instead of sending its routing table, a router sends the information about its neighborhood only. A router broadcast its identities and cost of the directly attached links to other routers.
• Flooding: Each router sends the information to every other router on the internetwork except its neighbors. This process is known as Flooding. Every router that receives the packet sends the copies to all its neighbors. Finally, each and every router receives a copy of the same information.
• Information sharing: A router sends the information to every other router only when the change occurs in the information.

Link State Routing has two phases:

Reliable Flooding

• Initial state: Each node knows the cost of its neighbors.
• Final state: Each node knows the entire graph.

Route Calculation

Each node uses Dijkstra's algorithm on the graph to calculate the optimal routes to all nodes.

• The Link state routing algorithm is also known as Dijkstra's algorithm which is used to find the shortest path from one node to every other node in the network.
• The Dijkstra's algorithm is an iterative, and it has the property that after k^th iteration of the algorithm, the least cost paths are well known for k destination nodes.

Algorithm

Initialization

N = {A}     // A is a root node.

for all nodes v

if v adjacent to A

then D(v) = c(A,v)

else D(v) = infinity

loop

find w not in N such that D(w) is a minimum.

Add w to N

Update D(v) for all v adjacent to w and not in N:

D(v) = min(D(v) , D(w) + c(w,v))

Until all nodes in N

In the above algorithm, an initialization step is followed by the loop. The number of times the loop is executed is equal to the total number of nodes available in the network.

where,

o    c( i , j): Link cost from node i to node j. If i and j nodes are not directly linked, then c(i , j) = ∞.

o    D(v): It defines the cost of the path from source code to destination v that has the least cost currently.

o    P(v): It defines the previous node (neighbor of v) along with current least cost path from source to v.

o    N: It is the total number of nodes available in the network.

Example:

Step 1:

The first step is an initialization step. The currently known least cost path from A to its directly attached neighbors, B, C, D are 2,5,1 respectively. 

Step 2:

In the table, we observe that vertex D contains the least cost path in step 1. Therefore, it is added in N. Now, we need to determine a least-cost path through D vertex.

Step 3:

In the table, we observe that both E and B have the least cost path in step 2. Let's consider the E vertex. Now, we determine the least cost path of remaining vertices through E.

Step 4:

In the table, we observe that B vertex has the least cost path in step 3. Therefore, it is added in N. Now, we determine the least cost path of remaining vertices through B.

Step 5:

In the table, we observe that C vertex has the least cost path in step 4. Therefore, it is added in N. Now, we determine the least cost path of remaining vertices through C.

 

Step	N	D(B),P(B)	D(C),P(C)	D(D),P(D)	D(E),P(E)	D(F),P(F)
1	A	2,A	5,A	1,A	∞	∞
2	AD	2,A	4,D		2,D	∞
3	ADE	2,A	3,E			4,E
4	ADEB		3,E			4,E
5	ADEBC					4,E
6	ADEBCF

Distance-vector routing protocol

A distance-vector routing protocol in data networks determines the best route for data packets based on distance. Distance-vector routing protocols measure the distance by the number of routers a packet has to pass, one router counts as one hop.

Some distance-vector protocols also take into account network latency and other factors that influence traffic on a given route.

To determine the best route across a network, routers, on which a distance-vector protocol is implemented, exchange information with one another, usually routing tables plus hop counts for destination networks and possibly other traffic information.

Distance-vector routing protocols also require that a router informs its neighbors of network topology changes periodically.

The Distance vector algorithm is iterative, asynchronous and distributed.

• Distributed: It is distributed in that each node receives information from one or more of its directly attached neighbors performs calculation and then distributes the result back to its neighbors.
• Iterative: It is iterative in that its process continues until no more information is available to be exchanged between neighbors.
• Asynchronous: It does not require that all of its nodes operate in the lock step with each other.

Three Keys to understand the working of Distance Vector Routing Algorithm:

• Knowledge about the whole network: Each router shares its knowledge through the entire network. The Router sends its collected knowledge about the network to its neighbors.
• Routing only to neighbors: The router sends its knowledge about the network to only those routers which have direct links. The router sends whatever it has about the network through the ports. The information is received by the router and uses the information to update its own routing table.
• Information sharing at regular intervals: Within 30 seconds, the router sends the information to the neighboring routers.

Let d_x(y) be the cost of the least-cost path from node x to node y. The least costs are related by Bellman-Ford equation,

                                        d_x(y) = min_v{c(x,v) + d_v(y)}

Where the min_v is the equation taken for all x neighbors. After traveling from x to v, if we consider the least-cost path from v to y, the path cost will be c(x,v)+d_v(y). The least cost from x to y is the minimum of c(x,v)+d_v(y) taken over all neighbors.

With the Distance Vector Routing algorithm, the node x contains the following routing information:

• For each neighbor v, the cost c(x,v) is the path cost from x to directly attached neighbor, v.
• The distance vector x, i.e., D_x = [ D_x(y) : y in N ], containing its cost to all destinations, y, in N.
• The distance vector of each of its neighbors, i.e., D_v = [ D_v(y) : y in N ] for each neighbor v of x.

Distance vector routing is an asynchronous algorithm in which node x sends the copy of its distance vector to all its neighbors. When node x receives the new distance vector from one of its neighboring vector, v, it saves the distance vector of v and uses the Bellman-Ford equation to update its own distance vector. The equation is given below:

                            d_x(y) = min_v{ c(x,v) + d_v(y)}     for each node y in N

The node x has updated its own distance vector table by using the above equation and sends its updated table to all its neighbors so that they can update their own distance vectors.

In distance vector routing, the least-cost route between any two nodes is the route with minimum distance. In this protocol, as the name implies, each node maintains a vector (table) of minimum distances to every node.

Initialization:

At the beginning, each node can know only the distance between itself and its immediate neighbors, those directly connected to it.

Assume that each node can send a message to the immediate neighbors and find the distance between itself and these neighbors. The distance for any entry that is not a neighbor is marked as infinite (unreachable).

In distance vector routing, each node shares its routing table with its immediate neighbors periodically and when there is a change.

Updating:

When a node receives a two-column(next column is not necessary) table from a neighbor, it needs to update its routing table.

Updating takes three steps:

1. The receiving node needs to add the cost between itself and the sending node to each value in the second column.

The logic is clear. If node C claims that its distance to a destination is x , and the distance between A and C is y , then the distance between A and that destination, via C, is x + y.

2. The receiving node needs to add the name of the sending node to each row as the third column if the receiving node uses information from any row. The sending node is the next node in the route.

3. The receiving node needs to compare each row of its old table with the corresponding row of the modified version of the received table.

a. If the next-node entry is different, the receiving node chooses the row with the smaller cost. If there is a tie, the old one is kept.

             b. If the next-node entry is the same, the receiving node chooses the new row.

 

For example, suppose node C has previously advertised a route to node X with distance 3. Suppose that now there is no path between C and X; node C now advertises this route with a distance of infinity. Node A must not ignore this value even though its old entry is smaller. The old route does not exist anymore. The new route has a distance of infinity.

 When D sends table to E:

When B sends table to A:

When E sends table to A:

Similarly, this goes on until all nodes are updated.