Although there are a large number of routing strategies that have been proposed and are being used, most routing strategies have evolved from the requirements of packet-switching networks. These are basically four strategies that have been used in routing: 1. Fixed Routing 2. Flooding 3. Random Routing 4. Adaptive Routing.
1. Fixed Routing:
A single permanent route is configured and established for each pair of source-destination nodes. For this a fixed cost routing (or one of its variants), is used. A central routing matrix is created and stored at the network control centre.
The matrix displays, for each source-destination node combination, the next node. It may be noted that for each node it is not necessary to store the complete route; it is sufficient to know the identity of the next node.
From the overall matrix, routing tables can be developed and stored at each node. It should be obvious that each node needs to know only the next node, the route after that will be decided by the next node and therefore, only the next node information needs to be retained by any particular node. The following samples of a central routing directory and the directory of node number 1 may clarify this issue.
Incidentally, it may be remembered that in case of fixed routing, there is no difference between routing for data-grams and virtual circuits. A refinement in fixed routing that would accommodate link and node outages would be to supply the nodes for with an alternate ‘next node’ for each destination. In case of the above table for node 1, for example, the alternate next nodes could be 4, 3, 2, 3, 3 instead of 2, 4, 4, 4, 4.
2. Flooding:
A routing technique that is simple is flooding. Implementing this technique does not require any network information. In this, a packet is sent by a source node to each neighbour.
At each node the incoming packet is transmitted on all outgoing links—except the link on which it arrived. For example, in Fig. 8.2 if node 1 has a packet to be sent to node 6, it will send a copy of that packet—along with the final destination address—to nodes 2, 3 and 4.
ADVERTISEMENTS:
Node 2 will send a copy of the packet to nodes 3 and 4. Node 4 will send a copy to nodes 3 and 5, and so on. Eventually, a number of copies of the packet will arrive at node 6. The packet must have some unique identifier—for example, the source node and sequence number or sequence number and virtual circuit number 0 so that the receiving node—in this case node 6—knows to discard all but the first received copy.
This scheme obviously requires some checks otherwise the number of packets in the network will proliferate. There are two ways suggested so that the numbers of packets do not proliferate. One way is for each node to remember the identity of those packets it has already transmitted.
If duplicate copies of the packet arrive, they are discarded. The other method suggested is to include a ‘hop count’ field with each packet.
The count can originally be set at some maximum value—the diameter of the network—such as the length of the longest minimum-hop path through the network. (For each pair of end systems attached to the network, there is a minimum-hop path. The length of the longest such minimum-hop path is the diameter of the network.)
ADVERTISEMENTS:
This flooding technique has three remarkable properties. These are:
1. All possible routes between source and destination are tried. Thus, no matter what link or node outages have occurred, a packet will always get through if at least one path between source and destination exists.
2. Because all routes are tried, at least one copy of the packet to arrive at the destination will have used a minimum-hop route.
3. All node that are directly or indirectly connected to the source node are visited.
3. Random Routing:
ADVERTISEMENTS:
Like Flooding, Random routing is a simple and robust routing technique and also has some advantages over flooding—it results in reduced traffic load. The outgoing link is chosen at random after, quite naturally, excluding the incoming link.
If the likely probabilities of choosing any link are equal, it amounts to choosing the outgoing link in around-robin fashion. There is, however, a likely refinement. This is to assign probabilities to each outgoing link and to select a link based on these probabilities. These probabilities could be based on the data rate. In that case, we have
where Pi = probability of selecting link i and
ADVERTISEMENTS:
Ri = data rate of link i.
This scheme could provide good traffic distribution when the sum Ri is taken over all the possible outgoing links. The probabilities could also be based on fixed link costs apart from data rates.
Flooding and random routing do not require any network information and in case of random routing, the actual route will unlikely to be either the least-cost or the minimum-hop route. The network will, therefore, probably carry a higher than optimum traffic load—though not as much as in the case of flooding.
4. Adaptive Routing:
The three examples of routing discussed above are all examples of static routing. These schemes do not take into account the changes in network conditions and traffic and are, therefore, non-adaptive. There is another class of routing schemes that do look at the changes around them.
Whenever routing decisions are taken according to the present network environment and traffic, the routing is dynamic and called adaptive routing. Adaptive algorithms may vary in as much as from where they get their information from about the network and traffic status, that is, whether locally, from adjacent nodes, from adjacent routers or from all routers in the network.
The conditions that affect routing decisions are:
1. When a node or trunk fails, it can no longer be used as part of a route.
2. When a certain portion of the network is heavily congested. In this case, it would be desirable to route packets around the congested portion rather than through it.
Naturally, for adaptive routing to function, each node must have information about the state of the network. While the advantages of adaptive routing seem to be obvious, there are also certain drawbacks which may be pointed out, compared to fixed routing.
These are:
a. The processing burden on the nodes increases because of complex routing decisions.
b. There is obviously a trade-off between the amount of information collected and the additional cost.
c. The adaptive strategy may react too quickly, causing the system to oscillate or to react too slowly making the extra burden useless. The oscillation may cause congestion. Oscillation may mean switching between two choices repeatedly.
But in spite of these possible drawbacks, adaptive strategies are quite prevalent because for the network user it will show improved performance and it can aid congestion control.