DATA COMMUNICATION AND COMPUTER NETWORKS

Module IV: Network Layer

Dr. Rahul Kumar

Associate Professor
Department of Computer Science & Engineering, ASET, Amity University, Gwalior, India

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Internetworking & devices: Repeaters, Hubs,
Bridges, Switches, Router, Gateway
• Internetworking devices are the building blocks that allow different computers and devices to
communicate and share resources on a network
What is a Repeater?
• Repeaters are defined as a networking device that is used to amplify and generate the incoming
signal. Repeaters work at the physical layer of the OSI model. The main aim of using a repeater is to
increase the networking distance by increasing the strength and quality of signals. The performance
of Local Area Networks (LANs) and Wide Area Networks (WANs) repeaters are used. Using repeaters
helps to reduce error, and loss of data and provides with delivery of data at specified locations only.
The major advantage of using a repeater is that it provides with transfer of data with more security
and over a long distance.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Internetworking & devices: Repeaters, Hubs,
Bridges, Switches, Router, Gateway
• Features of Repeaters
• Repeater can regenerate the signal without modifying it.
• Repeaters can be used in analog signals and digital signals.
• Repeaters can extend the range of networks.
• Dynamic networking is supported by repeater.
• Use of Repeaters reduces error and loss of data.
• Power is required for working of repeaters.
• Using repeater can add complexity in the network.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Internetworking & devices: Repeaters, Hubs,
Bridges, Switches, Router, Gateway
2. Hub – A hub is a basically multi-port repeater. A hub connects multiple wires coming from different
branches, for example, the connector in star topology which connects different stations. Hubs cannot
filter data, so data packets are sent to all connected devices. In other words, the collision domain of
all hosts connected through Hub remains one. Also, they do not have the intelligence to find out the
best path for data packets which leads to inefficiencies and wastage.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Internetworking & devices: Repeaters, Hubs,
Bridges, Switches, Router, Gateway
Types of Hub
• Active Hub:- These are the hubs that have their power supply and can clean, boost, and relay the
signal along with the network. It serves both as a repeater as well as a wiring center. These are used
to extend the maximum distance between nodes.
• Passive Hub:- These are the hubs that collect wiring from nodes and power supply from the active
hub. These hubs relay signals onto the network without cleaning and boosting them and can’t be
used to extend the distance between nodes.
• Intelligent Hub:- It works like an active hub and includes remote management capabilities. They also
provide flexible data rates to network devices. It also enables an administrator to monitor the traffic
passing through the hub and to configure each port in the hub.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Internetworking & devices: Repeaters, Hubs,
Bridges, Switches, Router, Gateway
3. Bridge – A bridge operates at the data link layer. A bridge is a
repeater, with add on the functionality of filtering content by reading
the MAC addresses of the source and destination. It is also used for
interconnecting two LANs working on the same protocol. It has a
single input and single output port, thus making it a 2 port device.
Types of Bridges
• Transparent Bridges:- These are the bridge in which the stations are
completely unaware of the bridge’s existence i.e. whether or not a
bridge is added or deleted from the network, reconfiguration of the
stations is unnecessary. These bridges make use of two processes i.e.
bridge forwarding and bridge learning.
• Source Routing Bridges:- In these bridges, routing operation is
performed by the source station and the frame specifies which route
to follow. The host can discover the frame by sending a special frame
called the discovery frame, which spreads through the entire
network using all possible paths to the destination.
Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Internetworking & devices: Repeaters, Hubs,
Bridges, Switches, Router, Gateway
4. Switch – A switch is a multiport bridge with a buffer and a design
that can boost its efficiency(a large number of ports imply less traffic)
and performance. A switch is a data link layer device. The switch can
perform error checking before forwarding data, which makes it very
efficient as it does not forward packets that have errors and forward
good packets selectively to the correct port only. In other words, the
switch divides the collision domain of hosts, but the broadcast
domain remains the same.
• Switches may operate at one or more layers of the OSI model. They
may operate in the data link layer and network layer; a device that
operates simultaneously at more than one of these layers is known
as a multilayer switch.
• A Switch can check the errors before forwarding the data, which
makes it more efficient and improves its performance. A switch is
the better version of a hub. It is a multi-port bridge device.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Internetworking & devices: Repeaters, Hubs,
Bridges, Switches, Router, Gateway
Types of Switch
1. Unmanaged switches: These switches have a simple plug-and-play design and do not offer advanced
configuration options. They are suitable for small networks or for use as an expansion to a larger
network.
2. Managed switches: These switches offer advanced configuration options such as VLANs, QoS, and
link aggregation. They are suitable for larger, more complex networks and allow for centralized
management.
3. Smart switches: These switches have features similar to managed switches but are typically easier to
set up and manage. They are suitable for small- to medium-sized networks.
4. Layer 2 switches: These switches operate at the Data Link layer of the OSI model and are responsible
for forwarding data between devices on the same network segment.
5. Layer 3 switches: These switches operate at the Network layer of the OSI model and can route data
between different network segments. They are more advanced than Layer 2 switches and are often
used in larger, more complex networks.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Internetworking & devices: Repeaters, Hubs,
Bridges, Switches, Router, Gateway
5. Routers – A router is a device like a switch that routes data packets based on their IP addresses. The
router is mainly a Network Layer device. Routers normally connect LANs and WANs and have a
dynamically updating routing table based on which they make decisions on routing the data packets. The
router divides the broadcast domains of hosts connected through it.
• Routers are small physical devices that operate at the network layer to join multiple networks together.
• A router is a device like a switch that routes data packets based on their IP addresses.
• Routers normally connect LANs and WANs and have a dynamically updating routing table based on
which they make decisions on routing the data packets.
• A Router divides the broadcast domains of hosts connected through it.
• Routers perform the traffic directing functions on the Internet. A data packet is typically forwarded
from one router to another through the networks that constitute the internetwork until it reaches its
destination code.
• Routers may also be used to connect two or more logical groups of computer devices known as
subnets, each with a different subnetwork address. The subnet addresses recorded in a router do not
necessarily map directly to the physical interface connections.
Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Internetworking & devices: Repeaters, Hubs,
Bridges, Switches, Router, Gateway
Two types of routers −
1. Static routers – Static routers are configured manually and route data packets based on the
information in a router table.
2. Dynamic routers – Dynamic routers use adaptive routing which is a process where a router can
forward data by a different route.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Internetworking & devices: Repeaters, Hubs,
Bridges, Switches, Router, Gateway
A gateway is a device that can connect networks that use different protocols. It acts as a translator
between different networks. A gateway is an internetworking capable of joining together two networks
that use different base protocols.
• A network gateway can be implemented completely in software, hardware, or a combination of both,
depending on the types of protocols they support.
• A network gateway can operate at any level of the OSI model. A broadband router typically serves as
the network gateway, although ordinary computers can also be configured to perform equivalent
functions.
• A gateway is a router or proxy server that routes between networks.
• A gateway belongs to the same subnet to which the PC belongs.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
 IP ADDRESSES

 An IP address is a numeric identifier assigned to each machine on an IP network.

 It designates the specific location of a device on the network.
 An IP address is a software address, not a hardware address—the latter is hard-coded on a
network interface card (NIC)
 IP addressing was designed to allow hosts on one network to communicate with a host on
a different network regardless of the type of LANs the hosts are participating in.
 Versions: IPv4 and IPv6
 IPv4 ADDRESSES

An IPv4 address is a 32-bit address that uniquely and

universally defines the connection of a device (for example,
a computer or a router) to the Internet..

Topics discussed in this section:

1. Address Space
2. Notations
3. Classful Addressing
4. Classless Addressing
 1. Address SPACE

• The total number of addresses used by the protocol. If a protocol uses N bits to define
an address, the address space is 2N because each bit can have two different values (0 or 1) and N bits
can have 2N values.
• The address space of IPv4 is 232 or 4,294,967,296.
• The address space of IPv6 is 2128 or 40,282,366,920,938,463,463,374,607,431,768,211,456.
 2. NOTATIONS

• There are two prevalent notations to show an IPv4 address:

a. Dotted-Decimal notation
b. Binary notation
c. Hexadecimal notation
2. a. Dotted-Decimal Notation
 To make the IPv4 address more compact and easier to read, Internet
addresses are usually written in decimal form with a decimal point (dot)
separating the bytes.
 The following is the dotted-decimal notation of the above address:
117.149.29.2
 2. NOTATIONS (contd…)

2.b. Binary notation

In binary notation, the IPv4 address is displayed as 32 bits.
Each octet is often referred to as a byte.
it is common to hear an IPv4 address referred to as a 32-bit address or a
4-byte address.
The following is an example of an IPv4 address in binary notation
Dotted-decimal notation and binary notation for an IPv4 address
 2. NOTATIONS (contd…)

2.c. Hexadecimal notation

In binary notation, the IPv4 address is displayed 8 hexadecimal digits.

Example: 10000001 00001011 00001011 11101111

Hexadecimal notation is: 810B0BEF16
 Example
Change the following IPv4 addresses from binary
notation to dotted-decimal notation.

Solution
We replace each group of 8 bits with its equivalent decimal number and add dots for
separation
 Example
Change the following IPv4 addresses from dotted-decimal notation to binary notation.

Solution
We replace each decimal number with its binary equivalent
 Example
Find the error, if any, in the following IPv4 addresses.

Solution
a. There must be no leading zero (045).
b. There can be no more than four numbers.
c. Each number needs to be less than or equal to 255.
d. A mixture of binary notation and dotted-decimal notation is not allowed.
 3. Classful addressing

 IPv4 addressing, at its inception, used the concept of classes.

 The address space is divided into five classes: A, B, C, D, and E. Each class occupies some
part of the address space
 We can find the class of an address when given the address in binary notation or dotted-
decimal notation.
i. If the address is given in binary notation, the first few bits can immediately tell us
the class of the address.
ii.If the address is given in decimal-dotted notation, the first byte defines the class.
Classful addressing
CLASSFUL ADDRESSING CONTD…

Finding the classes in binary and dotted-decimal notation

 CLASSFUL ADDRESSING CONTD…

Netid and Hostid

 In classful addressing, an IP address in class A, B, or C is divided into netid and hostid.
 These parts are of varying lengths, depending on the class of the address.
 The concept does not apply to classes D and E.
 In class A, one byte defines the netid and three bytes define the hostid. In class B, two
bytes define the netid and two bytes define the hostid. In class C, three bytes define the
netid and one byte defines the hostid.
CLASSFUL ADDRESSING CONTD…

Number of blocks and block size in classful IPv4 addressing

CASTING AND ITS TYPES

Casting : Casting is a method of transferring a packet to various hosts simultaneously by

using an IP address
Types of Casting
 CASTING AND ITS TYPES CONTD…

1. Unicast
Transmitting a packet from one source node to one destination node is called as unicast.
We can say, it is a one to one transmission.
 CASTING AND ITS TYPES CONTD…

2. Broadcast
 In Broadcasting, Packet is send to all residing host in the same or different network,
depending on its types.
 It is a one to all transmission.
 Broadcasting is of two types [Limited Broadcast, Direct Broadcast]
 CASTING AND ITS TYPES CONTD…

3. Multicast
Transmitting data packet from one source Node to a particular group of Nodes is known
as Multicast.
It is also an example of one to many transmission.
 CLASSFUL ADDRESSING CONTD…

Mask
 Although the length of the netid and hostid (in bits) is predetermined in classful
addressing, we can also use a mask (also called the default mask)
 32-bit number made of contiguous 1’s followed by contiguous 0’s. The masks for classes
A, B, and C. The concept does not apply to classes D and E.
 The mask can help us to find the netid and the hostid.
 Example
Find the class of each address.
a. 00000001 00001011 00001011 11101111
b. 11000001 10000011 00011011 11111111
c. 14.23.120.8
d. 252.5.15.111

Solution
a. The first bit is 0. This is a class Aaddress.
b. The first 2 bits are 1; the third bit is 0. This is a class C address.
c. The first byte is 14; the class is A.
d. The first byte is 252; the class is E.
 4. Classless addressing

 To overcome address depletion and give more organizations access to the Internet,
classless addressing was designed and implemented.
 Here are no classes, but the addresses are still granted in blocks.
Address Blocks
 In classless addressing, when an entity, small or large, needs to be connected to the
Internet, it is granted a block (range) of addresses.
 The size of the block (the number of addresses) varies based on the nature and size of
the entity.
 Classless addressing contd…

 Restriction: To simplify the handling of addresses, the Internet authorities impose three
restrictions on classless address blocks:
1.The addresses in a block must be contiguous, one after another.
2.The number of addresses in a block must be a power of 2 (I, 2, 4, 8, ... ).
3.The first address must be evenly divisible by the number of addresses.
CLASSLESS ADDRESSING CONTD…

A block of 16 addresses granted to a small organization

 Classless addressing contd…

Mask
 A better way to define a block of addresses is to select any address in the block and the
mask.
 A mask is a 32-bit number in which the n leftmost bits are I’s and the 32 - n rightmost
bits are 0’s.
 However, in classless addressing the mask for a block can take any value from 0 to 32. It is
very convenient to give just the value of n preceded by a slash (CIDR notation)
i. /n [denotes the prefix length]
ii. /(n-32) [denotes the suffix length]
 Example
A block of addresses is granted to a small organization. We know that one of the addresses is
205.16.37.39/28. What is the first address in the block?

Solution
The binary representation of the given address is
11001101 00010000 00100101 00100111
If we set 32−28 rightmost bits to 0, we get
11001101 00010000 00100101 0010000
or 205.16.37.32.
 Example
Find the last address for the block
Solution
The binary representation of the given address is
11001101 00010000 00100101 00100111
If we set 32 − 28 rightmost bits to 1, we get
11001101 00010000 00100101 00101111
or 205.16.37.47
 Internet Protocol version 6 (IPv6)

 IPv6 was developed by Internet Engineering Task Force (IETF) to deal with the
problem of IPv4 exhaustion.
 IPv6 is a 128-bits address having an address space of 2128, which is way bigger than
IPv4.
 IPv6 use Hexa-Decimal format separated by colon (:) .
 Internet Protocol version 6 (IPv6)

Components in Address format :

 There are 8 groups and each group represents 2 Bytes (16-bits).

 Each Hex-Digit is of 4 bits (1 nibble)
 Delimiter used – colon (:)
 Internet Protocol version 6 (IPv6)

Components in Address format :

 There are 8 groups and each group represents 2 Bytes (16-bits).

 Each Hex-Digit is of 4 bits (1 nibble)
 Delimiter used – colon (:)
 Internet Protocol version 6 (IPv6)

Need for IPv6:

1. Large address space

2. Better header format
3. New options
4. Allowance for extension
5. Support for resource allocation
6. Support for more security
 Addressing methods

In IPv6 representation, we have three addressing methods :

Unicast
Multicast
Anycast

 Unicast Address

Unicast Address identifies a single network interface. A packet sent to a unicast address
is delivered to the interface identified by that address.
 Addressing methods

 Multicast Address

Multicast Address is used by multiple hosts, called as groups, acquires a multicast

destination address. These hosts need not be geographically together. If any packet is
sent to this multicast address, it will be distributed to all interfaces corresponding to
that multicast address. And every node is configured in the same way. In simple words,
one data packet is sent to multiple destinations simultaneously.

 Anycast Address

Anycast Address is assigned to a group of interfaces. Any packet sent to an anycast

address will be delivered to only one member interface (mostly nearest host possible).
 Subnetting
Introduction To Subnetting
When a bigger network is divided into smaller networks, to maintain
security, then that is known as Subnetting. So, maintenance is easier for
smaller networks. For example, if we consider a class A address, the
possible number of hosts is 224 for each network, it is obvious that it is
difficult to maintain such a huge number of hosts, but it would be quite
easier to maintain if we divide the network into small parts.
Uses of Subnetting
• Subnetting helps in organizing the network in an efficient way which
helps in expanding the technology for large firms and companies.
• Subnetting is used for specific staffing structures to reduce traffic
and maintain order and efficiency. In the above diagram, there are two
• Subnetting divides domains of the broadcast so that traffic is routed Subnets.
efficiently, which helps in improving network performance. Note: It is a class C IP so, there are 24 bits in
• Subnetting is used in increasing network security. the network id part and 8 bits in the host id
The network can be divided into two parts: To divide a network into part.
two parts, you need to choose one bit for each Subnet from the host ID
part.
 Subnetting
Benefits of Subnetting:
• Improved Network Efficiency: By dividing a large network into subnets, you can reduce broadcast traffic.
Broadcast traffic is like shouting to everyone in a city, whereas sending data within a subnet is like talking to a
specific person in their neighborhood. Less overall network traffic means better performance for everyone.
• Enhanced Security: Subnetting allows you to isolate network segments. This can be helpful for implementing
security policies and restricting access to certain parts of the network. For example, you can create a separate
subnet for guest users, limiting their access to sensitive resources.
• Better Network Management: Subnetting makes it easier to manage and troubleshoot network issues. By
isolating problems within a specific subnet, you can identify and fix them more quickly.
• Efficient IP Address Allocation: Subnetting allows you to allocate IP addresses more efficiently. With a large
network, you might end up wasting a lot of addresses if you don't subnet. Subnetting helps you create subnets
with the exact number of addresses you need.
 Subnetting
How Does Subnetting Work?
The working of subnets starts in such a way that firstly it divides the subnets into smaller subnets. For
communicating between subnets, routers are used. Each subnet allows its linked devices to communicate with
each other. Subnetting for a network should be done in such a way that it does not affect the network bits.
In class C the first 3 octets are network bits so it remains as it is.
For Subnet-1: The first bit which is chosen from the host id part is zero and the range will be from
(193.1.2.00000000 till you get all 1’s in the host ID part i.e, 193.1.2.01111111) except for the first bit which is
chosen zero for subnet id part.
Thus, the range of subnet 1 is: 193.1.2.0 to 193.1.2.127
Subnet id of Subnet-1 is : 193.1.2.0 The direct Broadcast id of Subnet-1 is: 193.1.2.127 The total number of hosts
possible is: 126 (Out of 128, 2 id's are used for Subnet id & Direct Broadcast id) The subnet mask of Subnet- 1 is:
255.255.255.128
For Subnet-2: The first bit chosen from the host id part is one and the range will be from (193.1.2.100000000 till
you get all 1’s in the host ID part i.e, 193.1.2.11111111).
Thus, the range of subnet-2 is: 193.1.2.128 to 193.1.2.255
Subnet id of Subnet-2 is : 193.1.2.128 The direct Broadcast id of Subnet-2 is: 193.1.2.255 The total number of hosts
possible is: 126 (Out of 128, 2 id's are used for Subnet id & Direct Broadcast id) The subnet mask of Subnet- 2 is:
255.255.255.128 The best way to find out the subnet mask of a subnet is to set the fixed bit of host-id to 1 and the
rest to 0.
 Subnetting
Advantages of Subnetting
• Subnetting is used to decrease the presence of Internet Protocol (IP) range.
• Subnets helps in stopping the devices or gadgets from occupying the whole network, only allowing the hosts to
control which kind of user can have access to the important information. Simply, we can tell that network is safe
just because of the subnetting concept.
• Subnetting concept increases the performance of the total network by deleting the repeated traffic causing
errors.
• We can convert the whole big network into smaller networks by using the concept of subnetting as discussed
earlier.
Disadvantages of Subnetting
• If the number of subnets increases, then the number of routers must also increase along with the subnet
increase number. This happens because each subnet has its own subnet mask, broadcast address and network
address.
• As told earlier, if we create many subnets many IP Addresses are wasted because of the wastage of Host ID Bits
• The cost of the entire network is increased by subnetting, which calls for the acquisition of pricey internal
routers, switches, hubs, and bridges, among other things.
• The complexity of the network is increased through subnetting. The subnet network must be managed by a
skilled network administrator.
Static vs. dynamic routing
What is Static Routing?
• It is also known as "non-adaptive routing". The network administrator contains the routes in the
routing table while using this routing. As a result, the router transfers data from the source to
the destination using the administrator-defined route. Routing decisions don't depend on factors
like network traffic or topology.
• Advantages
• It can easily implement in small networks.
• It doesn't need bandwidth usage between the routers.
• It doesn't need additional resources as update mechanisms are not required.
• It is a more secure routing.
• It is more predictable because the route is specified to the destination.
• Disadvantages
• It is not helpful for complicated topologies and large networks.
• When the link is failed, it may affect the traffic rerouting.
• The administrator must use extreme caution when configuring the routes.
Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Static vs. dynamic routing
What is Dynamic Routing?
• Dynamic routing is also known as "adaptive routing", and it is a method of automatic routing. In other words,
when new routers are introduced to the network, the routing tables change. When a router fails, the routing
table automatically modifies to get the destination. As a result, dynamic routing responds to network and
traffic changes. This routing method employs dynamic routing algorithms to find new routes to the destination.
As a result, all network routers should use dynamic routing protocols that are consistent.
• Dynamic routing needs fewer routes. Moreover, it offers more accurate results in determining the optimum
path based on network changes. However, this routing method needs more bandwidth and offers less security.
• Advantages
• It is very helpful to all the topologies.
• Topologies automatically support traffic rerouting.
• The activities of the router are unaffected by network size.
• Disadvantages
• Dynamic routes depend on the current topologies.
• It needs extra resources like CPU, memory, and link bandwidth.
• It may be complex to implement.
• It is less secure as routing updates are broadcast and multicast.
Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
 comparison between Static Routing and Dynamic Routing
Features Static Routing Dynamic Routing

Definition It happens when a router utilizes a manually specified It is a method in which a router may transmit data via
routing entry rather than information from dynamic a different route or to a specific destination based on
routing traffic. the current state of the network's communication
circuits.
Configuration Technique The routing tables are manually updated in static The tables are automatically updated in dynamic
routing. routing.
Routes Routes are specified by the administrative. The routes are updated according to the modifications
in the network.
Routing Algorithms It doesn't utilize any complicated routing algorithms. It utilizes complicated routing algorithms.

Link Affect When a link fails in static routing, it interrupts the The link failure doesn't affect rerouting in dynamic
other routing path. routing.
Bandwidth It needs less bandwidth. It needs more bandwidth.
Security It offers high security. It offers less security.
Network Infrastructure Its network infrastructure is minimal. Its network infrastructure is large.
Routing Protocols It doesn't utilize any protocol. It employs protocols such as eigrp, arp, and others to
calculate the routing process.

Additional Resources It doesn't need any extra resources. It needs extra resources to hold the information.

Implementation It is implemented in small networks. It is implemented in large networks.

Routing table building Routing locations are hand-typed in static routing. In dynamic routing, locations are dynamically filled in
the table.
Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Routing algorithms: shortest path algorithm
• In between sending and receiving data packets from the sender to the receiver, it will go through many routers
and subnets. So as a part of increasing the efficiency in routing the data packets and decreasing the traffic, we
must find the shortest path
What is Shortest Path Routing?
• It refers to the algorithms that help to find the shortest path between a sender and receiver for routing the data
packets through the network in terms of shortest distance, minimum cost, and minimum time.
• It is mainly for building a graph or subnet containing routers as nodes and edges as communication lines
connecting the nodes.
• Hop count is one of the parameters that is used to measure the distance.
• Hop count: It is the number that indicates how many routers are covered. If the hop count is 6, there are 6
routers/nodes and the edges connecting them.
Common Shortest Path Algorithms
• Dijkstra’s Algorithm
• Bellman Ford’s Algorithm

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Routing algorithms: shortest path algorithm
Dijkstra’s Algorithm
• The Dijkstra’s Algorithm is a greedy algorithm that is used to find the minimum distance between a node and all
other nodes in a given graph. Here we can consider node as a router and graph as a network. It uses weight of
edge .ie, distance between the nodes to find a minimum distance route.
• Algorithm:
1: Mark the source node current distance as 0 and all others as infinity.
2: Set the node with the smallest current distance among the non-visited nodes as the current node.
3: For each neighbor, N, of the current node:
Calculate the potential new distance by adding the current distance of the current node with the weight of the
edge connecting the current node to N.
If the potential new distance is smaller than the current distance of node N, update N’s current distance with the
new distance.
4: Make the current node as visited node.
5: If we find any unvisited node, go to step 2 to find the next node which has the smallest current distance and
continue this process.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Routing algorithms: shortest path algorithm
Dijkstra’s Algorithm
• Example: Now,we will start normalising graph one by one starting from
• Consider the graph G: node 0.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Routing algorithms: shortest path algorithm
Dijkstra’s Algorithm
Step 2:-Nearest neighbour of 0 are 2 and 1 so we will normalize them first .
Step4:- Similarly we will normalize other node
considering it should not form a cycle and will keep track
in visited nodes.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Routing algorithms: shortest path algorithm
• Bellman Ford’s Algorithm
• The Bell man Ford’s algorithm is a single source graph search algorithm which help us to find the shortest path
between a source vertex and any other vertex in a give graph. We can use it in both weighted and unweighted
graphs. This algorithm is slower than Dijkstra’s algorithm and it can also use negative edge weight.
• Algorithm
• 1: First we Initialize all vertices v in a distance array dist[] as INFINITY.
• 2: Then we pick a random vertex as vertex 0 and assign dist[0] =0.
• 3: Then iteratively update the minimum distance to each node (dist[v]) by comparing it with the sum of the
distance from the source node (dist[u]) and the edge weight (weight) N-1 times.
• 4: To identify the presence of negative edge cycles, with the help of following cases do one more round of edge
relaxation.
• We can say that a negative cycle exists if for any edge uv the sum of distance from the source node (dist[u]) and
the edge weight (weight) is less than the current distance to the largest node(dist[v])
• It indicates the absence of negative edge cycle if none of the edges satisfies case1.
• Example: Bellman ford detecting negative edge cycle in a graph.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Routing algorithms: shortest path algorithm
• Consider the Graph G:

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Routing algorithms: shortest path algorithm

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Distance vector routing,

Step-01:
• Each router prepares its routing table. By their local knowledge. each router knows about
• All the routers present in the network
• Distance to its neighboring routers
Step-02:
• Each router exchanges its distance vector with its neighboring routers.
• Each router prepares a new routing table using the distance vectors it has obtained from its neighbors.
• This step is repeated for (n-2) times if there are n routers in the network.
• After this, routing tables converge / become stable.
• Distance Vector Routing Example-
• Consider-
• There is a network consisting of 4 routers.
• The weights are mentioned on the edges.
• Weights could be distances or costs or delays.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Distance vector routing

Step-01:
• Each router prepares its routing table using its local knowledge.
• Routing table prepared by each router is shown below-
At Router A- At Router B- At Router C-

At Router D-

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
 Distance vector routing
Step-02:
• Each router exchanges its distance vector obtained in Step-
01 with its neighbors.
• After exchanging the distance vectors, each router prepares
a new routing table.
This is shown below-
At Router A-
Router A receives distance vectors from its neighbors B and D.
Router A prepares a new routing table as-

Cost of reaching destination B from router A = min { 2+0 , 1+7 }

= 2 via B.
Cost of reaching destination C from router A = min { 2+3 , 1+11 }
= 5 via B.
Cost of reaching destination D from router A = min { 2+7 , 1+0 }
= 1 via D.

Department of Computer Science & Engineering, Amity School of Engineering and Technology, Amity University, Gwalior, Madhya Pradesh, India
Distance vector routing
• Explanation For Destination B
• Router A can reach the destination router B via its neighbor B or neighbor D.
• It chooses the path which gives the minimum cost.
• Cost of reaching router B from router A via neighbor B = Cost (A→B) + Cost (B→B)= 2 + 0 = 2
• Cost of reaching router B from router A via neighbor D = Cost (A→D) + Cost (D→B) = 1 + 7 = 8
• Since the cost is minimum via neighbor B, so router A chooses the path via B.
• It creates an entry (2, B) for destination B in its new routing table.
• Similarly, we calculate the shortest path distance to each destination router at every router.
• Thus, the new routing table at router A is-
Distance vector routing
• Router B-
• Router B receives distance vectors from its neighbors A, C and D.
• Router B prepares a new routing table as-
•
Thus, the new routing table at router B is-
Distance vector routing
Router C-
• Router C receives distance vectors from its neighbors B and D.
• Router C prepares a new routing table as-

Thus, the new routing table at router C is-

•
Distance vector routing
• Router D-
• Router D receives distance vectors from its neighbors A, B and C.
• Router D prepares a new routing table as-

Thus, the new routing table at router D is-

Distance vector routing
Step-03:
• Each router exchanges its distance vector obtained in Step-02 with its neighboring routers.
• After exchanging the distance vectors, each router prepares a new routing table.
• This is shown below-
Router A-
• Router A receives distance vectors from its neighbors B and D.
• Router A prepares a new routing table as- Thus, the new routing table at router A is-
Distance vector routing
• Router B-
• Router B receives distance vectors from its neighbors A, C and D.
• Router B prepares a new routing table as-
Thus, the new routing table at router B is-
Distance vector routing
Router C-
• Router C receives distance vectors from its neighbors B and D.
• Router C prepares a new routing table as-
Thus, the new routing table at router C is-
Distance vector routing
• Router D-
• Router D receives distance vectors from its neighbors A, B and C.
• Router D prepares a new routing table as-
Thus, the new routing table at router D is-
Link State Routing
• Link state routing is a technique in which each router shares the knowledge of its neighborhood
with every other router in the internetwork.
• The three keys to understand the Link State Routing algorithm:
1. Knowledge about the neighborhood: Instead of sending its routing table, a router sends the
information about its neighborhood only. A router broadcast its identities and cost of the
directly attached links to other routers.
2. Flooding: Each router sends the information to every other router on the internetwork except
its neighbors. This process is known as Flooding. Every router that receives the packet sends the
copies to all its neighbors. Finally, each and every router receives a copy of the same
information.
3. Information sharing: A router sends the information to every other router only when the
change occurs in the information.
Link State Routing
Link State Routing has two phases:
1. Reliable Flooding
• Initial state: Each node knows the cost of its neighbors.
• Final state: Each node knows the entire graph.
2. Route Calculation
• Each node uses Dijkstra's algorithm on the graph to calculate the optimal routes to all nodes.
• The Link state routing algorithm is also known as Dijkstra's algorithm which is used to find the
shortest path from one node to every other node in the network.
• The Dijkstra's algorithm is an iterative, and it has the property that after kth iteration of the
algorithm, the least cost paths are well known for k destination nodes.
Link State Routing
Link State Routing
We repeat the above steps until sptSet includes all vertices of the given graph. Finally, we get the
following Shortest Path Tree (SPT).
Link State Routing
S.No. Distance Vector Routing Link State Routing

Bandwidth required is less due to local sharing, small packets and Bandwidth required is more due to flooding and sending of
1.
no flooding. large link state packets.

Based on local knowledge, since it updates table based on Based on global knowledge, it have knowledge about entire
2.
information from neighbours. network.

3. Make use of Bellman Ford Algorithm. Make use of Dijakstra’s algorithm.

4. Traffic is less. Traffic is more.

Converges slowly i.e, good news spread fast and bad news spread
5. Converges faster.
slowly.

6. Count of infinity problem. No count of infinity problem.

7. Persistent looping problem i.e, loop will be there forever. No persistent loops, only transient loops.

8. Practical implementation is RIP and IGRP. Practical implementation is OSPF and ISIS.
Link State Routing
S.No. Distance Vector Routing Link State Routing

Bandwidth required is less due to local sharing, small packets and Bandwidth required is more due to flooding and sending of
1.
no flooding. large link state packets.

Based on local knowledge, since it updates table based on Based on global knowledge, it have knowledge about entire
2.
information from neighbours. network.

3. Make use of Bellman Ford Algorithm. Make use of Dijakstra’s algorithm.

4. Traffic is less. Traffic is more.

Converges slowly i.e, good news spread fast and bad news spread
5. Converges faster.
slowly.

6. Count of infinity problem. No count of infinity problem.

7. Persistent looping problem i.e, loop will be there forever. No persistent loops, only transient loops.

8. Practical implementation is RIP and IGRP. Practical implementation is OSPF and ISIS.
Protocols: ARP,RARP, IP, ICMP
• Network Layer is responsible for the transmission of data or communication from one host to another host
connected in a network. Rather than describing how data is transferred, it implements the technique for efficient
transmission.
• The data is being grouped into packets or in the case of extremely large data it is divided into smaller sub packets.
Each protocol used has specific features and advantages.
ARP
• ARP stands for Address Resolution Protocol.
• It is used to associate an IP address with the MAC address.
• Each device on the network is recognized by the MAC address imprinted on the NIC. Therefore, we can say that
devices need the MAC address for communication on a local area network. MAC address can be changed easily.
For example, if the NIC on a particular machine fails, the MAC address changes but IP address does not change.
ARP is used to find the MAC address of the node when an internet address is known.
Note: MAC address: The MAC address is used to identify the actual device.
IP address: It is an address used to locate a device on the network.
Protocols: ARP,RARP, IP, ICMP

How ARP works?

If the host wants to know the physical address of another
host on its network, then it sends an ARP query packet that
includes the IP address and broadcast it over the network.
Every host on the network receives and processes the ARP
packet, but only the intended recipient recognizes the IP
address and sends back the physical address. The host
holding the datagram adds the physical address to the
cache memory and to the datagram header, then sends
back to the sender.
There are two types of ARP entries:
1. Dynamic entry: It is an entry which is created
automatically when the sender broadcast its message
to the entire network. Dynamic entries are not
permanent, and they are removed periodically.
2. Static entry: It is an entry where someone manually
enters the IP to MAC address association by using the
ARP command utility.
Protocols: ARP,RARP, IP, ICMP

RARP
• RARP stands for Reverse Address Resolution
Protocol.
• If the host wants to know its IP address, then it
broadcast the RARP query packet that contains its
physical address to the entire network. A RARP
server on the network recognizes the RARP
packet and responds back with the host IP
address.
• The protocol which is used to obtain the IP
address from a server is known as Reverse
Address Resolution Protocol.
• The message format of the RARP protocol is
similar to the ARP protocol.
• Like ARP frame, RARP frame is sent from one
machine to another encapsulated in the data
portion of a frame.
Protocols: ARP,RARP, IP, ICMP
ICMP
• ICMP stands for Internet Control Message Protocol.
• The ICMP is a network layer protocol used by hosts and routers to send the notifications of IP
datagram problems back to the sender.
• ICMP uses echo test/reply to check whether the destination is reachable and responding.
• ICMP handles both control and error messages, but its main function is to report the error but not
to correct them.
• An IP datagram contains the addresses of both source and destination, but it does not know the
address of the previous router through which it has been passed. Due to this reason, ICMP can only
send the messages to the source, but not to the immediate routers.
• ICMP protocol communicates the error messages to the sender. ICMP messages cause the errors to
be returned back to the user processes.
• ICMP messages are transmitted within IP datagram.
The messages in ICMP are divided into two types. They are given below:
1. Error Message: Error message states about the issues or problems that are faced by the host or
routers during processing of IP packet.
2. Query Message: Query messages are used by the host in order to get information from a router or
another host.
Protocols: ARP,RARP, IP, ICMP
IGMP
• IGMP stands for Internet Group Message Protocol.
• The IP protocol supports two types of communication:
• Unicasting: It is a communication between one sender and one receiver. Therefore, we can say that it is
one-to-one communication.
• Multicasting: Sometimes the sender wants to send the same message to a large number of receivers
simultaneously. This process is known as multicasting which has one-to-many communication.
• The IGMP protocol is used by the hosts and router to support multicasting.
• The IGMP protocol is used by the hosts and router to identify the hosts in a LAN that are the members of a
group.
• IGMP is a part of the IP layer, and IGMP has a
fixed-size message.
• The IGMP message is encapsulated within an IP
datagram.

•
Protocols: ARP,RARP, IP, ICMP
How Does IGMP Work?
• Devices that can support dynamic multicasting and multicast groups can use IGMP.
• The host has the ability to join or exit the multicast group using these devices. It is
also possible to add and remove customers from the group using these devices.
• The host and local multicast router use this communication protocol. Upon creation
of a multicast group, the packet’s destination IP address is changed to the multicast
group address, which falls inside the class D IP address range.
•