4 Main Strategies 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.
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.)
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:
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
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.