Project Based Learning Report

on
ANALYSIS AND SIMULATION OF DISTANCE VECTOR ROUTING
PROTOCOL AND LINK STATE PROTOCOL
Submitted
In partial fulfilment
For the award of the degree of
B. Tech. (Branch Computer Science Engineering)
in Department of Computer Science

Submitted by:
Jayati Vijaywargiya (140234)
Ojaswi Bharadwaj(140235)
Aahana Mehar(140236)
Shivangi Singh(140237)
Shailja Singh(140238)
BTech CSE-E III year

May, 2017

Mody University of Science & Technology

College of Engineering & Technology
Lakshmangarh, Sikar – 332311 (Rajasthan)
 CERTIFICATE

This is to certify that Ms. JayatiVijaywargiya (140234) , Ms. OjaswiBharadwaj

(140245) , Ms. AahanaMehar (140236) , Ms. Shivangi Singh (140237) and Ms.
Shailja Singh (140238) has completed the Project Based Learning (PBL) project
successfully on the topic “ Comparative analysis of Distance Vector and Link State
Routing Protocol ”.

Project Mentor
(Dr. Uma kumari)

i
 TABLE OF CONTENTS
Page No.

Certificate i

Acknowledgement ii

List of Figures iii

 ACKNOWLEDGEMENT

It is my pleasure to acknowledge you that I have received a project on Comparative analysis

between Distance Vector Routing Protocol and Link State Protocol from my teacher. My first
sincere appreciation goes to Dr. Uma Kumari for her guidance throughout the project.

The satisfaction that accompanies that the successful completion of any task would be
incomplete without the mention of people whose ceaseless cooperation made it possible,whose
constant guidance and encouragement crown all efforts with success. I am very grateful to my
project supervisor Dr. Uma Kumari for the inspiration and constructive suggestions that helped
me in the preparation of this project.
I also thank my parents and family at large for their moral support during the project to ensure
successful completion of the project.

ii
 LIST OF FIGURES

Figure Title Page

1 Basic Architecture of NS2................................ 5

2 Routing table forwarding process......................... 6
3 Example network................................................ 6
4 Example network................................................ 7

iii
 CONTENTS
Abstract…………………………………………………………………………………………..01
Chapter 1: Introduction…………………………………………………………………………..02
1.1 Routing………………………………………………………………………...........02
1.2 Distance Vector Routing Protocol………………………………………...………..02
1.3 Link State Protocol……………………………………….………………………....03
Chapter 2: Software Required………………………………………………………………..….04
Chapter 3: Distance Vector Routing protocol………………………………………………..….05
3.1 Bellman-Ford Algorithm…………………………………………………...............06
3.2 Example………………………………………………………………….................06
Chapter 4: Link State Protocol…………………………………………………………………...07
4.1 Steps for link state routing protocol…………………………………………………08
Chapter 5: Comparative Study
5.1 Theoretical analysis……………………………………………………………........10
5.2 Difference table……………………………………………………………..............12
Chapter 6: Screenshots..................................................................................................................13
Chapter 7: Future scope.................................................................................................................15
Chapter 8: Conclusion...................................................................................................................16
Chapter 9: References....................................................................................................................17
Abstract

Mobile Adhoc networks are primarily classified for their dynamic topology and lack of
infrastructure. The key role of Adhoc network routing protocols is to establish routes efficiently
and accurately among nodes and ensure the packet delivery in time. In this work the technique
has selected two proactive, tables driven routing protocols from Distance Vector Routing (DVR)
and Link State Routing(LSR) and evaluated their performance on the basis of specified network
parameters. The results of a detailed simulation for mobile Adhoc networks, comparing two
proactive, table driven routing protocols: DVRP and LINK STATE PROTOCOL on various
scenarios of mobility, scalability and traffic load. The primary goal of such an adhoc network
routing protocal is correct and efficient route establishment between a pair of nodes so that
messages can be delivered in a timely manner. Finally the analysis discussed the functionality
and behaviour of both the protocols and their comparison based on simulation results.

1
Chapter 1

INTRODUCTION

1.1 Routing

 Routing is the process of selecting paths in a network along which to send network
traffic.
 Goals of routing are correctness, simplicity, Robustness, Stability, Fairness and
Optimality.
 Routing is performed for many kinds of network, including the telephone network,
electronic data networks and transportation networks. 
 Routing Algorithms can be classified based on the following:
o Static or Dynamic Routing,
o Distributed or Centralized,
o Single path or Multi path,
o Flat or Hierarchical,
o Intra Domain or Inter Domain,
o link State or Distance Vector.
 Algorithms may be static, the routing decisions are made ahead of time, with
information about the network topology and capacity, then loaded into the routers.
 Algorithms may be dynamic, where the routers make decisions based on
information they gather, and the routes change over time, adaptively.
1.2 Distance Vector Routing Protocol

 In this routing scheme, each router periodically shares its knowledge about the
entire network with its neighbours.
 Each router has a table with information about network. These tables are updated
by exchanging information with the immediate neighbours.
 It is also known as Bellman-Ford or Ford-Fulkerson Algorithm.
 It is used in the original ARPANET, and in the Internet as RIP

2
  Distance vector protocols, such as RIP, determine the path to remote networks
using hop count as the metric.

1.3 Link State Routing

 Link State Packet(LSP) contains the following information:

1. The ID of the node that created the LSP;
2. A list of directly connected neighbours of that node, with the cost of
the link to each one;
3. A sequence number;
4. A time to live(TTL) for this packet.
 In link state routing, each router shares its knowledge of its neighbourhood with
all routers in the network.
 Link-state protocols implement an algorithm called the shortest path first (SPF,
also known as Dijkstra's Algorithm) to determine the path to a remote destination.
 There is no hop count limit.
 Only when changes occur,It sends all summary information every 30 minutes by
default. Only devices running routing algorithms listen to these updates. Updates
are sent to a multicast address.
 Link-state protocols maintain three separate tables:

o Neighbour table: It contains a list of all neighbours, and the interface each
neighbour is connected off of. Neighbours are formed by sending Hello
packets.
o Topology table (Link- State table): It contains a map of all links within an
area, including each link’s status.
o Routing table: It contains the best routes to each particular destination
 3

Chapter 2

Software Required

Network Simulator:

 Ns is a discrete event simulator targeted at networking research.

 Ns provides substantial support for simulation of TCP, routing, and multicast protocols
over wired and wireless (local and satellite) networks.

 NS2 stands for Network Simulator Version 2. It is an open-source event-driven simulator

designed specifically for research in computer communication networks. 

 Features of NS2 

 1. It is a discrete event simulator for networking research. 

 2. It provides substantial support to simulate bunch of protocols like TCP, FTP, UDP,
HTTP and DSR. 

 3. It simulates wired and wireless network. 

Basic Architecture
 Fig 1. Basic architecture of NS2

Chapter 3

Distance Vector Routing Protocol

 Distance vector means that information sent from router to router is based on an entry in
a routing table that consists of the distance and vector to destination-distance being what
it "costs" to get there and vector being the "direction" to get to the destination.
 Distance vector protocols are often referred to as Bellman-Ford protocols.
 Distance vector algorithms call for each router to send its entire routing table, but only to
its neighbors. The neighbor then forwards its entire routing table to its neighbors, and so
on.
 Fig 2.Routing table forwarding process.

 Distancevector routing protocols use the Bellman–Ford algorithmto calculate paths and

requires that a router inform its neighbors of topology changes periodically.
 The term distance vector refers to the fact that the protocol manipulates vectors (arrays)
of distances to other nodes in the network.

 Examples of distance-vector routing protocols include  RIPv1 and

RIPv2, IGRP and Babel.

 Routers using distance-vector protocol do not have knowledge of the entire path to a
destination. Instead they use two methods:

1. Direction in which router or exit interface a packet should be forwarded.

2. Distance from its destination

 Distance vector protocols are based on calculating the direction and distance to any link
in a network. "Direction" usually means the next hop address and the exit interface.
"Distance" is a measure of the cost to reach a certain node. The least cost route between
any two nodes is the route with minimum distance.
  Each node maintains a vector (table) of minimum distance to every node. The cost of
reaching a destination is calculated using various route metrics. RIP uses the hop count of
the destination whereas IGRP takes into account other information such as node delay
and available bandwidth.

3.1 Bellman–Ford algorithm

Bellman-Ford algorithm. Bellman-Ford algorithm is a procedure used to find all shortest path in

a graph from one source to all other nodes. The algorithm requires that the graph does not
contain any cycles of negative length, but if it does, the algorithm is able to detect it.

3.2 EXAMPLE

 Let the given source vertex be 0. Initialize all distances as infinite, except the distance to
source itself. Total number of vertices in the graph is 5, so all edges must be processed 4
times.

6
 Let all edges are processed in following order: (B,E), (D,B), (B,D), (A,B), (A,C), (D,C),
(B,C), (E,D). We get following distances when all edges are processed first time.
 The first row in shows initial distances.
 The second row shows distances when edges (B,E), (D,B), (B,D) and (A,B) are
processed.
 The third row shows distances when (A,C) is processed. The fourth row shows when
(D,C), (B,C) and (E,D) are processed.
  The first iteration guarantees to give all shortest paths which are at most 1 edge long. We
get following distances when all edges are processed second time (The last row shows
final values).

 The second iteration guarantees to give all shortest paths which are at most 2 edges long.
The algorithm processes all edges 2 more times. The distances are minimized after the
second iteration, so third and fourth iterations don’t update the distances.

Chapter 4

LINK STATE PROTOCOL

 Link state protocols are based on Shortest Path First (SPF) algorithm to find the best
path to a destination, also known as Dijkstra algorithm.
 Link state routing protocols maintain complete road map of the network in each router
 running a link state routing protocol. Each router running a link state routing protocol
originates information about the router, its directly connected links, and the state of
those links. This information is sent to all the routers in the network
as multicast messages. Link-state routing always try to maintain full networks topology
by updating itself incrementally whenever a change happens in network.
 Each router in the network keeps a copy of it, without changing it. After obtaining the
complete picture of network topology, each router will independently calculate its own
best paths to reach the destination networks.
 In Shortest Path First (SPF) algorithm, whenever a link's state changes, a routing update
called a Link-State Advertisement (LSA) is exchanged between routers.  When a router
receives an LSA routing update, the link-state algorithm is used to recalculate the
shortest path to affected destinations.  Each router constructs a map of the complete
network.
 Link State Protocols use multicasts to share the routing information.
 An example of Link State protocol is OSPF (Open Shortest Path First).

Some important terms related with Link State Routing Protocols

 Link-state advertisements (LSAs) – A link-state advertisement (LSA) is a small packet

of routing information that is sent between routers.
 Topological database – A topological database is a collection of information gathered
from LSAs.
 Routing tables – A list of the known paths and interfaces.

4.1 Steps for link state routing protocol

 Distribute the maps.

 Determining the neighbours of each node.
 Distributing the information for the map.
 Next, each node periodically sends a short message, the link-state advertisement, which:
 o Identifies the node which is producing it.
o Identifies all the other nodes to which it is directly connected.
o Includes a sequence number, which increases every time the source node makes
up a new version of the message.

 Calculate the routing table

 Calculate the shortest paths

9
Chapter 5

Comparative Study

 A typical distance vector routing protocol uses a routing algorithm in which routers
periodically send routing updates to all neighbours by broadcasting their entire routing
tables.
 The main features of distance vector protocols are the following: Periodic and Triggered
Updates, Broadcast and Multicast Updates, Full Routing Table Updates, Routing by
 Rumour, Timers and Stability Features; Split Horizon and Poisoned Reverse; Counting to
Infinity.
 Link State Routing Protocols require more CPU power and memory than Distance Vector
Routing Protocol algorithms.Distance vector routing algorithm and link state routing
algorithmcomes under the category of adoptive routing algorithms.

5.1 Theoretical analysis

Each node constructs a one-dimensional array containing the "distances"(costs) to all other nodes
and distributes that vector to its immediate neighbours. The starting assumption for distance-
vector routing is that each node knows the cost of the link to each of its directly connected
neighbours. A link that is down is assigned an infinite cost

Fig 5.1. Example network

10
 Table 1. Initial distances stored at each node

Table 2. final distances stored at each node

 Distance Vector or Link State protocols according to the method they use to exchange
information about the network and to use this information to calculate the best path to a
destination.
 Distance-vector routing protocols include RIPv1 and RIPv2 on the other hand link-state
routing protocols include open shortest path first (OSPF).

11
5.2 Difference table:

In the given table you can find differences between distance vector and link state routing
protocol.

DISTANCE VECTOR LINK STATE

ALGORITHM Bellman-Ford Dijkstra

NETWORK VIEW Topology knowledge from the Common and complete

neighbour point of view knowledge of the network
topology

BEST PATH Based on fewest number of hops Based on the cost

CALCULATION

UPDATES Frequently periodic updates Triggered updates

ROUTING LOOPS Needs additional procedure to avoid By construction, routing loops

them cannot happen

CPU & MEMORY Low utilisation Intensive

UPDATING Whole routing table Only changed information

CONTENTS HOP Limited Unlimited

Table 3. Comparison between distance vector protocols and link state protocols

12
Chapter 6

Screenshots

Distance Vector Routing Protocol

13
Link State Protocol

14
Chapter 7
Feasibility and future scope
This project presents the theoretical and practical analysis of Distance Vector Routing protocols
and Link State protocols. The comparison table of distance vector protocols with link state
protocol shows that distance vector protocols have frequently periodic updates, low utilization of
CPU and memory and has high simplicity whereas the link state protocols have intensive
utilization of CPU and memory with a high complexity which requires a well trained
administrator to be handled. We could work towards improving the algorithm so as to avoid the
major evils of this algorithm namely Count to Infinity, Bouncing Effect and Looping. This would
help making the algorithm more dynamic and decreasing the amount of time it takes to re-
compute the routes. Routing protocols support the delivery of packets, in spite of changes in
network topology and usage patterns, by dynamically configuring the routing tables maintained
at routers in internets. The compromise of this routing function in an internet can lead to the
denial of network service, the disclosure or modification of sensitive routing information, the
disclosure of network traffic or the inaccurate accounting of network resource usage. The future
scope of this paper is to focus on security services in routing protocols which is the protection of
routing information from threats to the integrity (the intentional corruption of routing data),
authenticity (the acceptance of routing information from an unauthorized entity by legitimate
routers), and in some cases the confidentiality (of for example sensitive policy information) of
routing updates.

15
Chapter 8
Conclusion
This project presents the theoretical and practical analysis of Distance Vector Routing protocols
and Link State protocols. The comparison table of distance vector protocols with link state
protocol shows that distance vector protocols have frequently periodic updates, low utilization of
CPU and memory and has high simplicity whereas the link state protocols have intensive
utilization of CPU and memory with a high complexity which requires a well trained
administrator to be handled. We could work towards improving the algorithm so as to avoid the
major evils of this algorithm namely Count to Infinity, Bouncing Effect and Looping. This would
help making the algorithm more dynamic and decreasing the amount of time it takes to re-
compute the routes.

16
Chapter 9
References

1. Performance Analysis of Routing Protocols for Real Time Application by Archana

Kudtarkar, Reena Sonkusare, and Dayanand Ambawade of SPIT, Mumbai in
International Journal of Advanced Research in Computer and Communication
Engineering Vol. 3, Issue 1, January 2014
2. EIGRP - A FAST ROUTING PROTOCOL BASED ON DISTANCE VECTORS by Bob
Albrightson and Joanne Boyle of Cisco Systems, and J.J. Garcia-Luna-Aceves of
University of California
3. https://www.ijarcsse.com/docs/papers/Volume_4/8_August2014/V4I8-0440.pdf
4. https://cseweb.ucsd.edu/classes/fa10/cse123/lectures/123-fa10-l13.pdf
5. http://ciscodocuments.blogspot.in/2011/06/chapter-7-selecting-routing-
protocols_3334.html

17