International Journal of Computer Trends and Technology ( IJCTT ) – Volume 62 Number 2 - August 2018

Introduction of Routing and its types

Er.Navneet Kaur
#
Aassistant professor of CSE, ASIAN College, Patiala

Abstract packets follow. Various routing algorithm are used

A computer network is a set of computers that are followed:
that are connected together the purpose of sharing
resources and information. The most common A. Adaptive Algorithm
resource shared today is an Internet. Routing is an The adaptive algorithms base their routing
important function of computer network. Routing is decision on measurement or estimate of the current
process of established the routes that data packets traffic and topology. Adaptive algorithm are divided
must follow to reach the destination. This paper into three parts:
discussed the various routing algorithms that are a) Isolated routing
adaptive and non-adaptive routing algorithms. b)Centralized routing
c)Distributed routing
Keywords: computer network, routing, adaptive and
non-adaptive, algorithm, path. 1) Isolated Routing
In this method, the node decides the routing
I. INTRODUCTION without seeking information other nodes. The
Today internet is the fastest infrastructure in sending node does not know about status of a
everyday life .Human being is able to send and particular link.
receive any form of data. The routing algorithm is
described by as network layer protocol that guides the
packets through the communication layer to their
correct destination. The performance of routing is
assessed according the throughput in network. The
main function is routing algorithm is deciding which
route is better for packet.

Routing process is classified into two parts

that are adaptive and non-adaptive algorithms. There
are certain properties that are desirable in the routing
algorithm.
1. Routing algorithm should be done properly and Fig: 2.1.1
correctly.
2. Routing algorithm should be simple. There are some example of isolated routing that is
3. Routing algorithm should be stable under all Hot Potato and Backward Learning.
circumstances.
4. Every node connected to the network should get a Hot Potato: Hot potato routing is a routing technique
fair chance of transmitting their packets. enabling packet routing without storing them in
5. Routing algorithm should be optimal in term of buffer.
throughput and minimize mean packets delays.
Backward Learning: This method routing tables at
Moreover, a routing algorithm must be able each node gets modified information from incoming
to the global and distribute nature of physical packet. The packets contain address of source
networks. Routing algorithm need to cope with events machine too.
such as node and link failure and recalculate paths.
Finally, routing algorithm need to calculate paths to 2) Central Routing
allow nodes to achieve high performance. All routers are connected to centralized
control core called Routing Control Center (RCC).
II. ROUTING ALGORITHMS Every router tells RCC which its neighbours and use
Routing is process of establishing the routes information to create the map of network. Compute
that data packets must follow to reach the destination. routing tables and communicate them to all routers.
In this process, a routing table is created which
contains information regarding routes which data

ISSN: 2231-2803 http://www.ijcttjournal.org Page 80

 International Journal of Computer Trends and Technology ( IJCTT ) – Volume 62 Number 2 - August 2018

b) Link State Vector:

Link state vector was used in ARPANET up
to 1979. After that it was replaced by Link state
vector .The Link state vector is simple and each
router has to perform the following five operations.
1. Each router should discover its neighbour and
obtain their network.
2. It should measure the delay or cost to each of these
neighbours.
3. It should construct a packet containing the network
addresses and delay of all neighbours.
4. Send this packet to all other routers.
Fig: 2.1.2 5. Compute the shortest path every other routers.
a) Advantages of Central Routing Link state vector is used two types protocols that are
1. Routers have not a high computational capacity, all OPSF and Is-Is Intermediate system.
focused on single device.
2. The network administrator can get the map of
whole network from a single device to check its
correctness.
3. To update the algorithm just the control canter has
to be update.

b) Disadvantages of Central Routing

1. The control canter is single point of failure that
impact on all network.
2. It is not suitable for wide network such as Internet.
Fig: 2.1.3(b)
3) Distributed Routing
Distributed architecture is also convenient for B. Non-Adaptive Algorithm:
adding a remotely installed control module onto an In Non adaptive algorithm routing the of
available data communications circuit, to minimize route is computed in advanced. The route distance
the installation costs of potentially long cable runs line is computed off and down loaded IMP when
back to the access control panel location. There are network is booted.
two types of Distributed routing that are followed.
a)Distance vector Features of Non-Adaptive Algorithm:
b) Link state vector 1. In this algorithm, routing decision are not
based on the measurement or estimate of current
a) Distance Vector: traffic and topology.
A Distance vector routing protocol requires 2. The route from a particular source to destination is
that a router in form its neighbours of topology calculated in advanced.
changes periodically. 3. Non-Adaptive Algorithm have some types that are
followed:
 Shortest path routing algorithm.
 Multipath routing algorithm.
 Flooding algorithm.
 Flow based algorithm.

1) Shortest Path Routing Algorithm:

In this technique to choose a route the
algorithm find shortest path between two nodes. For
measuring path length it can use number of hops,
geographical distance in kilometres.
Fig: 2.1.3(a) - The labelling of arcs can be done with queue and
transmissions delay for a standard test of packet. It
- A Distance vector is defined as the list of is based on hourly basis or daily basis or can be
<destination, cost> tuples, on tuple per destination computed as function of bandwidth distance,
Each routers maintains a distance vector. communication cost and some other factors.
- The cost in each tuple is equal the sum of costs on
shortest path to the destination.

ISSN: 2231-2803 http://www.ijcttjournal.org Page 81

 International Journal of Computer Trends and Technology ( IJCTT ) – Volume 62 Number 2 - August 2018

Fig: 2.2.1

2) Multipath Routing Algorithm:

In this routing, A network it is found that there are
more than one path with shortest length between pairs
of nodes.
- In such cases to reduce the load on each of
communication lines.
- This technique of using multiple routes between a
single pair of nodes is known as multiple routing also
called bifurcated routing.
- The method is applicable to both the virtual and
datagram subnets.
- Multiple routing is widely used to improve
performance and reliability of subnet.
- Routing tables are maintained at each node which
contains choices with destination node, line and
respective probability.

Fig: 2.2.3

4) Flow Based Algorithm

Flow based routing is static algorithm that uses both
topology and load for routing for deciding a route. To
use this technique, certain information must be
known advance.
- First the subnet topology must be known.
- The traffic matrix.
- The line capacity matrix.

Fig: 2.2.2

3) Flooding Algorithm
Flooding is another static routing algorithm,
in which every incoming packet is sent out on every
outgoing line except the one it arrived on.
- Flooding creates vast number of duplicate packets.
- To reduce, a counter is used with each packet
which is decremented at each hope and one whose
counter value is zero is discard.
- The sender know the path length of destination but
if in case it does not know the counter in initialized
by a number equal to full diameter of the subnet. Fig:2.2.4
- Flooding is not practical in most of applications. III. CONCLUSION
- A more practical variation is called as selective Network security is the vast topic that is
flooding. becoming a more important because the world is
highly interconnected .This paper discussed different
types of routing algorithms. The reviews made a
conclusion that the adoptive routing algorithms such

ISSN: 2231-2803 http://www.ijcttjournal.org Page 82

 International Journal of Computer Trends and Technology ( IJCTT ) – Volume 62 Number 2 - August 2018

as distance vector algorithm, link state algorithm and

so on gives better performance metric when
compared with the non adoptive routing algorithms
such as flooding, shortest path algorithm, random
walk and so on.

REFERENCES
[1] Nilesh P. Bobade, "Performance Evaluation of Ad Hoc on
Demand Distance Vector in MANETs with varying
Network Size using NS-2 Simulation", (IJCSE)
International Journal on Computer Science and
Engineering, 02(08), 2731-2735 (2010)
[2] Teressa Longjam and Neha Bagoria," Comparative Study
of Destination Sequenced Distance Vector and Ad-hoc
Ondemand Distance Vector Routing Protocol of Mobile
Adhoc Network” International Journal of Scientific and
Research Publications, ISSN 2250-3153 February (2013)
[3] Revathi Venkataraman, Pushpalatha .M, and Rama Rao.T,
"Performance Analysis of Flooding Attack Prevention
Algorithm in MANETs", World Academy of Science,
Engineering and Technology, 32 (2009)
[4] Venkateshwara Rao .K,"Dynamic Search Algorithm used
in Unstructured Peer- to-Peer Networks", International
Journal of Engineering Trends and Technology, 2(3),
(2011) .
[5] Mohammad reza soltan aghaei, "A hybrid algorithm for
finding shortest path in network routing", Journal of
Theoretical and Applied Information Technology © 2005-
2009 (2009).
[6] 5. Cheolgi Kim, Young-Bae Koy and Nitin H.Vaidya,
LinkState Routing Protocol for Multi-Channel Multi-
Interface Wireless Networks, IEEE (978–1–4244–2677–
5/08)/$25.00c (2008).
[7] Beaubrun R, Pierre S, “Routing algorithm for distributed
communication networks,” Proc 22nd IEEE Conference on
Computer Networks,LCN 97 pp. 99- 105 Nov 1997
[8] Thomas H. Cormen, Charles E. Leiserson,Ronald L.Rivest,
and Clifford Stein.Introduction to Algorithms, Second
Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-
03293-7. Section 24.1: TheBellman-Ford algorithm,
pp.588–592. Problem 24-1, pp.614–615.
[9] R. Bellman. On a routing problem.Quar . Appl. Math.,
16:87- 90, 1958.
[10] Adaptive Routing Algorithms in Distributed Networks,
K.Rangaswamy & G. Sreenivasulareddy.
[11] Computer network, S.Tanenbaum, fourth edition, Pearson
education.
[12] Vahdat A and Becker D, “Epidemic routing for partially
connected ad hoc network”, IEEE journal on Selected
Areas in Communications,2003.
[13] Hang Y, Jain S, Martonosi M, and Fall K, “ Erasure
coding based routing for opportunistic network”, In ACM
SIGCOMM Workshop on Delay Tolerant Network, 2005.

ISSN: 2231-2803 http://www.ijcttjournal.org Page 83