Routing algorithms can be divided into two groups:

i. Nonadaptive algorithms:

• For this type of algorithms, the routing decision is not based on the measurement or estimations of current traffic and topology.
• However the choice of the route is done in advance, and known as static routing.

ii. Adaptive algorithms:

• For these algorithms the routing decision can be changed if there are any changes in topology or traffic etc.

• This is called as dynamic routing.

  The examples of static algorithms are:

i. Shortest path routing:

• Given a network topology and a set of weights describing the cost to send data across each link in the network
• Find the shortest path from a specified source to all other destinations in the network.

D. The arrows indicate the working node

• Shortest path algorithm first developed by E. W. Dijkstra

  a. Mark the source node as permanent.

  b. Designate the source node as the working node.

  c. Set the tentative distance to all other nodes to infinity.

  d. While some nodes are not marked permanent

  Compute the tentative distance from the source to all nodes adjacent to the working node. If this is shorter than the current tentative distance replace the tentative distance of the destination and record the label of the working node there. Examine ALL tentatively labelled nodes in the graph. Select the node with the smallest value and make it the new working node. Designate the node permanent.

ii. Flooding:

• In this algorithm every incoming packet is sent out on every outgoing line except the line on which it has arrived.
• One disadvantage of flooding is that it generate a large number of duplicate packets. In fact it produces infinite number of duplicate packets unless we somehow dump the process. Therefore, we use selective flooding.
• In this algorithm every incoming packet is not sent out on every output line.
• Instead packet is sent only on those lines which are approximately going in the right direction.

iii. Flow Based Routing

• Flow-based routing uses network topology, traffic matrices, and capacity matrices to determine static routes.
• For example in figure below,there is always a huge traffic from A to B and/or B to D.

• Then the traffic from A to D should not be routed through B.
• Instead route it through ACFED even though it is a longer path than ABD. This is called flow based routing.

The example of Dynamic Routing Algorithms are:

i. Distance vector Routing Algorithm

• In this algorithm, each router maintains a table called vector, such a table gives the best known distance to each destination and the information about which line to be used to reach there.
• In this, we assume that each router knows the identity of every other router in the network, but the shortest path to each router is not known.

ii. Count to Infinity problem:

Consider a linear subnet of Figure 4.4 which has five nodes. The delay metric used is the number of hops.

• Assume that A is initially down and that all the other routers know this. So all the routers have recorded that the delay to A is infinity.
• When A becomes OK, the other routers come to know about it via the vector exchanges. Then suddenly a vector exchanges at all the routers will take place simultaneously.
• At the time of first vector exchange, B comes to know that its left neighbor has a zero delay to A. So as shown in Figure 4.4.B makes an entry in its routing table that A is one hop away to the left.
• All the other routers still think that A is down. So in the second row of Figure 4.4, the entries below C D E are ∞
• On the Second vector exchange, C comes to know that B has a path of 1 hop length to A, so C updates its routing table and indicates a path of 2 hop length. But D and E do not change their table entries.

iii. Link State Routing

The link state routing is simple and each router has to perform the following operations

• Each router should discover its neighbours and obtain their network addresses.
• Then it should measure the delay or cost to each of these neighbours.
• It should construct a packet containing the network addresses and the delays of all the neighbours.
• Send this packet to all other routers
• Compute the shortest path to every other router.

Sometimes the network becomes so large that the size of the router table becomes excessively large and practically it becomes impossible for every router to have an entry for every other router. Then the hierarchical routing such as the one used in telephone networks should be adopted.