Routing Algorithms

Shortest Path Routing

• each node represents router and lines communication link in the graph
• different metrics for measuring path lenght
• hop count, distance in km, mean queuing transmission delay

Dijkstra's algorithm

• solves single source shortest path problem
• only for non negative edge path costs
• the weight or length of a path is calculated as the sum of the weights of the edges in the path.
• Dijkstra's algorithm finds the shortest path from x to y in order of increasing distance from x. That is, it chooses the first minimum edge, stores this value and adds the next minimum value from the next edge it selects.
• It is similar to the minimum spanning tree algorithm, in that it is "greedy", always choosing the closest edge in hopes of an optimal solution.

How it works
1)Assign to each node a distance value zero for initial node and infinity for others
2)Mark all nodes as unvisited
3)For current node consider all its unvisited neighbours and caclulate their tentative distance.If the new distance calculated is less than previous assigned distance, overwrite it.
4)when all the neighbouring unvisited nodes of current node are visited we mark this node as visited
5)set unvisited node with smallest distane as next current node.

Unlike Dijkstra algorithm Bellman ford can be used with negative edge graphs

Flooding
every incoming packet is sent on to every outgoing line except on which it came

Dynamic Routing Algorithms

Distance Vector Routing
1)Bellman Ford Routing
2)Routing Information Protocol

Each router maintains a routing table giving best known distance to each router and which line to use
This table is updated by exchanging information with neighbours
Routing table contains entry for each router consisting of two fields  preffered outgoing line to use for that destination
Each router informs its neighbours of topological changes periodically unlike link state protocol where router has to inform all nodes in the topology