Subscribe by Email

Friday, July 19, 2013

What are the goals and properties of a routing algorithm?

Routing requires the use of routing algorithms for the construction of the routing tables.
A number of routing algorithms are today available with us such as:
1.   Distance vector algorithm (bellman ford algorithm)
2.   Link state algorithm
3.   Optimized link state routing algorithm (OLSR)
- In a number of web applications, there are a number of nodes which require communicating with each other via communication channels.
- Few examples of such applications are telecommunication networks (such as POTS/ PSTN, internet, mobile phone networks, and local area networks), distributed applications, multiprocessor computers etc.
- All nodes cannot be connected to each other since doing so will require many high powered transceivers, wires and cables.
- Therefore, the implementation is such that the transmissions of nodes are forwarded by the other nodes till the data or info reaches its correct destination.
- Thus, routing is the process of determining where the packets have to be forwarded and doing so.

Properties of Routing Algorithm
- The packets must reach their destination if there are no factors preventing this such as congestion.
- The transmission of data should be quick.
- There should be high efficiency in the data transfer.
- All the computations involved must not be long. They should be as easy and quick as possible.
- The routing algorithm must be capable of adapting to the two factors i.e., changing load and changes in topology (this includes the channels that are new and the deleted ones.)
- All the different users must be treated fairly by the routing algorithm.
The second and the third properties can be achieved using fastest or the shortest route algorithms.
- Graphical representation of the network is a crucial part of the routing process.
- Each network node is represented by a vertex in the graph whereas an edge represents a connection or a link between the two nodes.
- The cost of each link is represented as the weight of the edge in the graph.
- There are 3 typical weight functions as mentioned below:
1.   Minimum hops: The weight of all the edges in the graph is same.
2.  Shortest path: The weight of all the edges is a constant non – negative value.
3.   Minimum delay: The weight of every edge depends up on the traffic on its link and is a non – negative value.
However in real networks, the weights are always positive.

Goals of Routing Algorithms
- The goal of these routing algorithms is to find the shortest path based up on some specified relationships that if used will result in the maximum routing efficiency.
- Another point is to use as minimum information as possible.
- Goal of the routing algorithm is also to keep the routing tables update with all alternative paths so that if one fails, the other one can be used.
- The channel or the path that fails is removed from the table.
- The routing algorithms need to be stable in order to provide meaningful results but at the same time is quite difficult to detect the stable state of an algorithm.
- Choosing a routing algorithm is like choosing different horses for different courses.
- The frequency of the changes in the network is one thing to be considered.
Other things to be considered include the cost function that is needed to be minimized and the calculation of the routing tables in a centralized fashion.
- For static networks the routing tables are fixed and therefore they require only simple routing algorithms for calculation.
- On the other hand, the networks that are dynamic nature require distributed routing algorithms which are of course complex.