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.

Routing Information Protocol (RIP)

Characteristics of RIP

- RIP (Routing Information Protocol) is a standard for exchange of routing information among gateways and hosts.
- RIP is most useful as an "interior gateway protocol".
- All RIP routing protocols are based on a distance vector algorithm called the Bellman-Ford algorithm, after Bellman's development of the equation used as the basis of dynamic programming, and Ford's early work in the area.
- RIP is considered an effective solution for small homogeneous networks.
- For larger, more complicated networks, RIP's transmission of the entire routing table every 30 seconds may put a heavy amount of extra traffic in the network.
- RIP sends routing-update messages at regular intervals and when the network topology changes. When a router receives a routing update that includes changes to an entry, it updates its routing table to reflect the new route.
- Each router sends a list of distance-vectors each of its neighbours periodically.
- The metric must be a positive integer. This metric measures the cost to get to the destination. In RIP, this cost describes number of hops.
- Each hop is assigned a hop count value, which is typically 1. The router adds 1 to the metric value when a router receives a routing update and enters the network in the routing table.
- RIP prevents routing loops from continuing indefinitely by implementing a limit on the number of hops allowed in a path from the source to a destination. The maximum number of hops in a path is 15.
- RIP implements the split horizon and holddown mechanisms to prevent incorrect routing information from being propagated.
- RIP uses numerous timers to regulate its performance. These include a routing-update timer, a route-timeout timer, and a route-flush timer.

Limitations of the protocol

- The protocol is limited to networks whose longest path involves 15 hops.
- The protocol depends upon "counting to infinity" to resolve certain unusual situations.
- This protocol uses fixed "metrics" to compare alternative routes.
- It is not appropriate for situations where routes need to be chosen based on real-time parameters such a measured delay, reliability, or load.