Routing algorithms , types of routing algorithms, Optimality Principle ?

ROUTING ALGORITHMS

·        One of the important functions of network layer is routing the packets from source machine to the destination machine.

·        To perform this routing, network layer defines several different algorithms.

·        These routing algorithms play a vital role in network and are used to define route for packets.

·        A routing algorithm is a part of network layer software that decides to which output line an incoming packet should be transmitted.

·        If the subnet uses a datagram approach, then the choice of route has to be made for each incoming packet.

·        If the subnet uses virtual circuit approach, then the decision has to be taken for every virtual circuit. This route exists till the virtual circuit is alive on the network .

·        A routing algorithm should possess some desirable properties like correctness, simplicity, robustness, stability, fairness and optimality.

1. Correctness. The routing should be done properly and correctly so that the packets may reach their proper destination.

2. Simplicity. The routing should be done in a simple manner so that the overhead is as low as possible. With increasing complexity of the routing algorithms the overhead also increases.

3. Stability. The routing algorithm should be stable under all circumstances.

4. Fairness. Every node connected to the network should get a fair chance of transmitting their packets. This is usually done on FCFS basis.

5. Robustness. Once a network becomes operational, it may be expected to run continuously for years without any failures. The algorithms designed for routing should be robust enough to handle hardware and software failure and should be able to cope with changes in the topology and traffic without requiring all jobs in all hosts to be aborted and the network rebooted every time some router goes down

6. Optimality. The routing algorithm should be optimal in terms of though put and minimizing mean packet delays.

Types of Routing Algorithms

There are two different groups of routing algorithms. One group is classified on the s of its working and the other group is based on the number of destination to which each packet is routed.

Classification on the basis of working

On the basis of its routing decision, routing algorithms are divided into two categories:

1. Non-Adaptive Algorithms

(a) In these algorithms, routing decisions are not based on the measurements or estimation of current traffic and topology.

(b) The route from a particular source to destination is calculated in advance and is downloaded to the routers, when the network is initialized .

(c) These type of algorithms are also known as static routing algorithms.

2. Adaptive Algorithms

(a) Adaptive algorithms are not static.

(b) These algorithms change their routing decisions to reflect changes in the topology and traffic.

(c) The adaptive algorithms continuously update their information about the network and                     base their routing decisions on the current state of the network.

(d) These algorithms can get their information locally from the adjacent routers or from all                  the routers of the network.  

(e) These algorithms can change their routes after specific time interval or when the load of the network changes or when the topology of the network changes.

(f) Adaptive algorithms also differ from one another depending on the metric chosen for                      optimization of network.

(g) Because of this dynamic nature, these algorithms are called dynamic  routing algorithms.

Classification on the basis of transmission technique

Depending on the number of receivers that receive each packet, the algorithms are classified into two following categories

1.      Unicast Routing Algorithms.

In one unicast routing algorithms, the packets sent from one sender are received by only receiver in the network. This means, the communication is one to one. These algorithms are designed in such a manner that they can route the packets to only one destination.

2.       Multicast Routing Algorithms.

In multicast routing algorithms, the packets sent by a sender are received by a group  of receivers. The decision on which computers will be accepting the packets is taken by looking the destination address of the packet.

Optimality Principle

·        The general statement about optimal routes without regard to network topology or traffic is known as optimality principle.

·        It states that if router J is on the optimal path from router I to router K, then the optimal path from J to K also falls along the same route.

·        This can be elaborated as, call the part of the route from I to J as ri and the rest of the route as r2. If a route better than t2 existed from J to K, it could be concatenated with ri to improve the route from I to K, contradicting our statement that ri 12 is optimal.

·        As a direct consequence of the optimality principle, we can see that the set of optimal routes from all source to a given destination form a tree rooted at the destination. Such a tree is called a sink tree and is shown in fig. In this example distance metric is the number of hops.

·        Sink tree is not necessarily unique. Other trees with the same path lengths may exist.

·        All the routing algorithms are supposed to discover and use the sink trees for all routers.