# Routing Algorithms

Routing is the process of forwarding of a packet in a network so that it reaches its intended destination.

Classification of Routing Algorithms

The routing algorithms may be classified as follows:

**Adaptive Routing Algorithm:**These algorithms change their routing decisions to reflect changes in the topology and in traffic as well. These get their routing information from adjacent routers or from all routers. The optimization parameters are the distance, number of hops and estimated transit time. This can be further classified as follows:**Centralized:**In this type some central node in the network gets entire information about the network topology, about the traffic and about other nodes. This then transmits this information to the respective routers.**Isol****ated:**In this method the node decides the routing without seeking information from other nodes. The sending node does not know about the status of a particular link.

**Non-Adaptive Routing Algorithm:**These algorithms do not base their routing decisions on measurements and estimates of the current traffic and topology. Instead the route to be taken in going from one node to the other is computed in advance, off-line, and downloaded to the routers when the network is booted. This is also known as static routing. This can be further classified as:**Flooding:**Flooding adapts the technique in which every incoming packet is sent on every outgoing line except the one on which it arrived. One problem with this method is that packets may go in a loop. As a result of this a node may receive several copies of a particular packet which is undesirable. Some techniques adapted to overcome these problems are as follows:

**Sequence Numbers****Hop Count****Spanning Tree**

**Random Walk:**In this method a packet is sent by the node to one of its neighbours randomly. This algorithm is highly robust. When the network is highly interconnected, this algorithm has the property of making excellent use of alternative routes. It is usually implemented by sending the packet onto the least queued link.

# Delta Routing

Delta routing is a hybrid of the centralized and isolated routing algorithms. Here each node computes the cost of each line (i.e some functions of the delay, queue length, utilization, bandwidth etc) and periodically sends a packet to the central node giving it these values which then computes the **k** best paths from node **i** to node **j**. Let**Cij1** be the cost of the best **i-j** path, **Cij2** the cost of the next best path and so on.If **Cijn - Cij1 < delta**, (**Cijn** - cost of **nâ€™th** best **i-j** path, **delta** is some constant) then path **n** is regarded equivalent to the best **i-j** path since their cost differ by so little. When **delta -> 0** this algorithm becomes centralized routing and when **delta -> infinity** all the paths become equivalent.

# Multipath Routing

In the above algorithms it has been assumed that there is a single best path between any pair of nodes and that all traffic between them should use it. In many networks however there are several paths between pairs of nodes that are almost equally good. Sometimes in order to improve the performance multiple paths between single pair of nodes are used. This technique is called multipath routing or bifurcated routing. In this each node maintains a table with one row for each possible destination node. A row gives the best, second best, third best, etc outgoing line for that destination, together with a relative weight. Before forwarding a packet, the node generates a random number and then chooses among the alternatives, using the weights as probabilities. The tables are worked out manually and loaded into the nodes before the network is brought up and not changed thereafter.

# Hierarchical Routing

This is essentially a â€˜Divide and Conquerâ€™ strategy. The network is divided into different regions and a router for a particular region knows only about its own domain and other routers. Thus, the network is viewed at two levels:

- The Sub-network level, where each node in a region has information about its peers in the same region and about the regionâ€™s interface with other regions. Different regions may have different â€˜localâ€™ routing algorithms. Each local algorithm handles the traffic between nodes of the same region and also directs the outgoing packets to the appropriate interface.
- The Network Level, where each region is considered as a single node connected to its interface nodes. The routing algorithms at this level handle the routing of packets between two interface nodes, and is isolated from intra-regional transfer.

In Hierarchical routing, the interfaces need to store information about:

- All nodes in its region which are at one level below it.
- Its peer interfaces.
- At least one interface at a level above it, for outgoing packages.

# Non-Hierarchical Routing

In this type of routing, interconnected networks are viewed as a single network, where bridges, routers and gateways are just additional nodes.

- Every node keeps information about every other node in the network
- In case of adaptive routing, the routing calculations are done and updated for all the nodes.

# Source Routing

Source routing is similar in concept to virtual circuit routing. It is implemented as under:

- Initially, a path between nodes wishing to communicate is found out, either by flooding or by any other suitable method.
- This route is then specified in the header of each packet routed between these two nodes. A route may also be specified partially, or in terms of some intermediate hops.

# Policy Based Routing

In this type of routing, certain restrictions are put on the type of packets accepted and sent. e.g.. The IIT- K router may decide to handle traffic pertaining to its departments only, and reject packets from other routes. This kind of routing is used for links with very low capacity or for security purposes.

# Shortest Path Routing

A network is represented as a graph, with its terminals as nodes and the links as edges. A â€˜lengthâ€™ is associated with each edge, which represents the cost of using the link for transmission. Lower the cost, more suitable is the link. The cost is determined depending upon the criteria to be optimized.

Shortest Path Algorithm

**Dijktstraâ€™s Algorithm:**

At the end each node will be labeled with its distance from source node along the best known path. Initially, no paths are known, so all nodes are labeled with infinity. As the algorithm proceeds and paths are found, the labels may change reflecting better paths. Initially, all labels are tentative. When it is discovered that a label represents the shortest possible path from the source to that node, it is made permanent and never changed thereafter.Look at the weighted undirected graph where the weights represent, for example, distance. We want to find shortest path from A to D. We start by making node A as permanent, indicated by a filled in circle.Then we examine each of the nodes adjacent to A (the working node), relabeling each one with the distance to A. Whenever a node is relabeled, we also label it with the node from which the probe was made so that we can construct the final path later. Having examined each of the nodes adjacent to A, we examine all the tentatively labeled nodes in the whole graph and make the one with the smallest label permanent, This one becomes new working node.

We now start at B, and examine all nodes adjacent to it. If the sum of the label on B and the distance from B to the node being considered is less than the label on the node, we have a shorter path, so the node is relabeled. After all the nodes adjacent to the working node have been inspected and the tentative labels changed if possible, the entire graph is searched for the tentatively labeled node with the smallest value. This node is made permanent and becomes the working node for the next round.

**Bellman Fordâ€™s Algorithm:**

We look at the distributed version which works on the premise that the information about far away nodes can be had from the adjoining links.

The algorithm works as follows.

- Compute the link costs from the starting node to every directly connected node.
- Select the cheapest links for every node (if there is more than one).
- For every directly connected node, compute the link costs for all these nodes.
- Select the cheapest route for any node.

Repeat until all nodes have been processed.

Every node should have the information about itâ€™s immediate neighbors and over a period of time we will have information about other nodes. Within n units of time , where n is the diameter of the network, every node will have the complete information. We do not need to be synchronized i.e. do not need to exchange information at the same time.

Routing algorithms based on Dijkstraâ€™s algorithm are called Link State Algorithms. Distance Vector Protocols are based on distributed Bellmanâ€™s algorithm. In the former we are sending little information to many nodes while in the latter we send huge information to few neighbors.

Count-to-Infinity problem:

Suppose the link between A and E is down events may occur are:

- F tells A that it has a path to E with cost 6
- A sets cost to E to be 11, and advertise to F again
- F sets the cost to E to be 16, and advertise to A again

This cycle will continue and the cost to E goes to infinity. The core of the problem is that when X tells Y that it has a path somewhere ,Y has no way to know whether it itself is on the path.

During this process of counting to infinity, packets from A or F destined to E are likely to loop back and forth between A and F, causing congestion for other packets.