Different Routing Algorithms
One of the main functions of the
network layer is routing packets from source to destination. Network layer uses
routing algorithms to decide which outgoing path should be selected for
incoming packets. If network use datagram approach then the router may choose a
different path for each incoming packet, since the best route may changed since
last time. If network use virtual circuit then routing decisions are only made
when a new virtual circuit is being set up. After that all packets are follow
same route.
There exist several routing algorithms, which
can be grouped into two classes: non-adaptive
and adaptive. Non-adaptive algorithms do
not look to current traffic and topology while making decisions; instead, they
use routing tables that are downloaded at the booting time to make decisions.
Therefore, this procedure also known as static routing. Adaptive routing
algorithms change their routing decisions based on the topology and traffic.
Some of the routing methods are discuss
below,
Shortest Path Routing
In this mechanism, a graph of subnet is build
with each node of the graph representing a router and each arc of the graph
representing communication line. To select a route between a given pair of
routers, the shortest path algorithm selects the shortest path between them on
the graph. The meaning of the term shortest depend upon the algorithm, some
select the route with less number of hops, some select the route with less
distant and so on. One example of shortest path algorithm is Dijkstra’s
algorithm (1959).
Flooding
The idea is, sent
every incoming packet to every outgoing line except the one arrived on. Flooding
increase the congestion on the network, another problem is that it generates
large number of duplicate packets. To deal with this several measure are used,
one of them is to have a hop counter contained in the header of each packet,
the count is decrement at each node or router, the packet being discarded when
the count reaches to zero. For optimal functioning, the hoop counter should be
initialized to the length of the path from source node to destination node. If
it is not possible or sender does not know how long the path is, then hop
counter initialize to worst case that is diameter of the subnet. Flooding is a
static routing method.
Distance Vector Routing
Distance vector
routing algorithms operate by using a routing table. Each router maintains a
table giving the best distance to each hop and which line use to reach there.
The routing tables are uploaded dynamically
by exchanging data with the other routers especially neighbors. The distance
vector routing algorithm is also known as Bellman-Ford routing
algorithm. It was the original ARPANET routing algorithm.
Link State Routing
Link-state routing
algorithms use the following steps to generate routing table,
1. Discover the neighbors and learn their
network address
2. calculate the delay or cost to each of its
neighbors
3. Construct a packet which include all
information it has just learned
4. Forward his packet to all other routers.
5. By using the received packet each router,
compute the shortest path to every other router in the network.
6. Use this table to take routing decisions.
Hierarchical Routing
In the case of large network, the network may
structure hierarchically. It may be necessary to group the routers into
regions, and regions into clusters, the cluster into zones, the zones into
groups and so on. Kamoun and Kleinrock (1979) discovered that optimal number of levels for an N router
subnet is lnN requires a total of elnN entries per router.
No comments:
Post a Comment