in Network

Routing Algorithms

Introduction Routing Algorithms

Had to focus myself on networks and once again decided to make a small summary. Thought people would appreciate it if I would share this on the internet. This document is all about routing, forwarding, routing algorithms, distance vectors, link states and Dijkstra’s algorithm. If you have any suggestions or questions about this summary please let me know down below in the comments!

 

Interplay between Routing and Forwarding

Routing Algorithm Forwarding

Routing

Our goal is to determine a ‘good’* path (as in sequence of routers) through the network from the source to the/its destination. A small abstraction for the graph shown down below:

The graph nodes are routers, the graph edges are physical links. The numbers shown is the delay, cost or congestion level. The lower the better.

Routing Cost

* A ‘good’ path often means the path that costs less than others. Other definitions are possible so this is not always the case!

In the graph above we move all items in subsets:

G = (N,E)

N = set of routers = { u, v, w, x, y, z }

E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }

Graph abstraction can also be useful in other contexts. An example is P2P. Where N is the set of peers and E is the set of TCP connections.

 

Routing Algorithm Classification

Global vs. decentralized information:

Global: All routers have complete topology and its link costs information. Uses ‘Link State’ algorithms.

Decentralized: Routers knows physically-connected neighbors and link costs to neighbors. Iterative process of computation and exchange of information with neighbors. Uses ‘distance vector’ algorithm.

 

Static vs. dynamic:

Static: Routes change slowly over time.

Dynamic: Routes change more quickly, there is a periodic update as it also needs to know if there are any link cost changes.

 

Dijkstra’s Algorithm

Network topology. The links cost is known to all nodes. Accomplished via link state broadcast. All nodes have the same information.

Computes least cost paths from one node (source node) to all other nodes. It gives a forward table for that node.

Iterative: after k iterations, it knows the least costs path to k destinations.

 

Notations:

c(x,y): link cost from node x to y;  = ∞ if not direct neighbors

D(v): current value of cost of path from source to dest. V

p(v): predecessor node along path from source to v

N’: set of nodes whose least cost path definitively known

Dijkstra's Algorithm Table

Construct the shortest path tree by tracing predecessor nodes. Ties can exist (and can be broken arbitrarily). Another example:

Dijkstra's Table 3

Distance Vector Algorithm

Dx(y)= estimate of least cost from x to y – where x maintains  distance vector: D x= [Dx(y): y єN ]

 

Node X:

Knows cost to each neighbor v: c(x,v)

Maintains its neighbors distance vectors. For each neighbor v, x maintains Dv= [Dv(y): y єN ]

 

Iterative, asynchronous: Each local iteration is caused by: local link cost change or DV update message from neighbor.

Distributed: each node notifies neighbors only when its DV changes. Neighbors then otify their neighbors if necessary.

 

Each node:

 Node Change

An example of the Distance Vector:

Distance Vector Example

 

Red: invalid route or passes to itself

Grey: not neighbors

 

 

Tables:

Distance Vector Table

Distance Vector: Link Lost changes

  • Node detects local link cost change
  • Updates routing information and recalculates the distance vector
  • If Distance Vector changes, it notifies its neighbors.

 

Example of link cost change:

Link Cost Change

As you can see: the travel cost from Y to X (or the other way around) changes from 4 to 1.

  1. t0 : y detects link-cost change, updates its DV, informs its neighbors.
  2. t1 : z receives update from y, updates its table, computes new least cost to x, sends its neighbors its DV.
  3. t2 : y receives z’s update, updates its distance table. y’s least costs does not change, so y does not send a message to z.

 

Comparison of Link State & Distance Vector Algorithms

Link state is noted as ‘LS’. Distance Vector is noted as ‘DV’.

 

Message Complexity

LS: With n nodes, E links, O(nE) messages sent.

DV: Exchange between neighbors only. Convergence time varies.

 

Speed of Convergence

LS: O(n2) algorithm requires O(nE) messages. May have oscillations.

DV: Convergence time varies. May be routing loops (count-to-infinity problem).

 

What happens if a router malfunctions?

LS: Node can advertise incorrect link cost. Each node computes only its own table.

DV: DV node can advertise incorrect path cost. Each node’s table used by others, error propagate througyh network.

 

I recently added another summary to my website regarding TCP & UDP and some of its concepts. If you’ve read this document I’m sure you appreciate this one!

Related Posts