o The Network Layer is the third layer of the OSI model.

o It handles the service requests from the transport layer and further
forwards the service request to the data link layer.
o The network layer translates the logical addresses into physical
addresses
o It determines the route from the source to the destination and also
manages the traffic problems such as switching, routing and controls
the congestion of data packets.
o The main role of the network layer is to move the packets from
sending host to the receiving host.

The main functions performed by the network layer are:

o Routing: When a packet reaches the router's input link, the router will
move the packets to the router's output link. For example, a packet
from S1 to R1 must be forwarded to the next router on the path to S2.
o Logical Addressing: The data link layer implements the physical
addressing and network layer implements the logical addressing.
Logical addressing is also used to distinguish between source and
destination system. The network layer adds a header to the packet
which includes the logical addresses of both the sender and the
receiver.
o Internetworking: This is the main role of the network layer that it
provides the logical connection between different types of networks.
o Fragmentation: The fragmentation is a process of breaking the
packets into the smallest individual data units that travel through
different networks.

Forwarding & Routing

In Network layer, a router is used to forward the packets. Every router has a
forwarding table. A router forwards a packet by examining a packet's header
field and then using the header field value to index into the forwarding table.
The value stored in the forwarding table corresponding to the header field
value indicates the router's outgoing interface link to which the packet is to
be forwarded.

For example, the router with a header field value of 0111 arrives at a router,
and then router indexes this header value into the forwarding table that
determines the output link interface is 2. The router forwards the packet to
the interface 2. The routing algorithm determines the values that are
inserted in the forwarding table. The routing algorithm can be centralized or
decentralized.

Services Provided by the Network Layer

 o Guaranteed delivery: This layer provides the service which
guarantees that the packet will arrive at its destination.
o Guaranteed delivery with bounded delay: This service guarantees
that the packet will be delivered within a specified host-to-host delay
bound.
o In-Order packets: This service ensures that the packet arrives at the
destination in the order in which they are sent.
o Guaranteed max jitter: This service ensures that the amount of time
taken between two successive transmissions at the sender is equal to
the time between their receipt at the destination.
o Security services: The network layer provides security by using a
session key between the source and destination host. The network
layer in the source host encrypts the payloads of datagrams being sent
to the destination host. The network layer in the destination host would
then decrypt the payload. In such a way, the network layer maintains
the data integrity and source authentication services.

Network Addressing
o Network Addressing is one of the major responsibilities of the network layer.
o Network addresses are always logical, i.e., software-based addresses.
o A host is also known as end system that has one link to the network. The
boundary between the host and link is known as an interface. Therefore, the
host can have only one interface.
o A router is different from the host in that it has two or more links that connect
to it. When a router forwards the datagram, then it forwards the packet to
one of the links. The boundary between the router and link is known as an
interface, and the router can have multiple interfaces, one for each of its
links. Each interface is capable of sending and receiving the IP packets, so IP
requires each interface to have an address.
o Each IP address is 32 bits long, and they are represented in the form of "dot-
decimal notation" where each byte is written in the decimal form, and they
are separated by the period. An IP address would look like 193.32.216.9
 where 193 represents the decimal notation of first 8 bits of an address, 32
represents the decimal notation of second 8 bits of an address.

 Let's understand through a simple example.

o In the above figure, a router has three interfaces labeled as 1, 2 & 3 and each
router interface contains its own IP address.
o Each host contains its own interface and IP address.
o All the interfaces attached to the LAN 1 is having an IP address in the form of
223.1.1.xxx, and the interfaces attached to the LAN 2 and LAN 3 have an IP
address in the form of 223.1.2.xxx and 223.1.3.xxx respectively.
o Each IP address consists of two parts. The first part (first three bytes in IP
address) specifies the network and second part (last byte of an IP address)
specifies the host in the network.

Classful Addressing
An IP address is 32-bit long. An IP address is divided into sub-classes:

o Class A
o Class B
 o Class C
o Class D
o Class E

An ip address is divided into two parts:

o Network ID: It represents the number of networks.

o Host ID: It represents the number of hosts.

In the above diagram, we observe that each class have a specific range of IP
addresses. The class of IP address is used to determine the number of bits
used in a class and number of networks and hosts available in the class.

Class A
In Class A, an IP address is assigned to those networks that contain a large
number of hosts.

o The network ID is 8 bits long.

o The host ID is 24 bits long.

In Class A, the first bit in higher order bits of the first octet is always set to 0
and the remaining 7 bits determine the network ID. The 24 bits determine
the host ID in any network.
The total number of networks in Class A = 27 = 128 network address

The total number of hosts in Class A = 2 24 - 2 = 16,777,214 host address

Class B
In Class B, an IP address is assigned to those networks that range from
small-sized to large-sized networks.

o The Network ID is 16 bits long.

o The Host ID is 16 bits long.

In Class B, the higher order bits of the first octet is always set to 10, and the
remaining14 bits determine the network ID. The other 16 bits determine the
Host ID.

The total number of networks in Class B = 2 14 = 16384 network address

The total number of hosts in Class B = 216 - 2 = 65534 host address

Class C
In Class C, an IP address is assigned to only small-sized networks.

o The Network ID is 24 bits long.

o The host ID is 8 bits long.

In Class C, the higher order bits of the first octet is always set to 110, and the
remaining 21 bits determine the network ID. The 8 bits of the host ID
determine the host in a network.

The total number of networks = 221 = 2097152 network address

The total number of hosts = 28 - 2 = 254 host address

Class D
In Class D, an IP address is reserved for multicast addresses. It does not
possess subnetting. The higher order bits of the first octet is always set to
1110, and the remaining bits determines the host ID in any network.

Class E
In Class E, an IP address is used for the future use or for the research and
development purposes. It does not possess any subnetting. The higher order
bits of the first octet is always set to 1111, and the remaining bits
determines the host ID in any network.

Rules for assigning Host ID:

The Host ID is used to determine the host within any network. The Host ID is
assigned based on the following rules:

o The Host ID must be unique within any network.

o The Host ID in which all the bits are set to 0 cannot be assigned as it is used
to represent the network ID of the IP address.
o The Host ID in which all the bits are set to 1 cannot be assigned as it is
reserved for the multicast address.
Rules for assigning Network ID:
If the hosts are located within the same local network, then they are
assigned with the same network ID. The following are the rules for assigning
Network ID:

o The network ID cannot start with 127 as 127 is used by Class A.

o The Network ID in which all the bits are set to 0 cannot be assigned as it is
used to specify a particular host on the local network.
o The Network ID in which all the bits are set to 1 cannot be assigned as it is
reserved for the multicast address.

Classful Network Architecture

Clas Higher NET ID HOST ID No.of No.of hosts per Range

s bits bits bits networks network

A 0 8 24 27 224 0.0.0.0 t
127.255.255.255

B 10 16 16 214 216 128.0.0.0 t

191.255.255.255

C 110 24 8 221 28 192.0.0.0 t

223.255.255.255

D 1110 Not Not Not Defined Not Defined 224.0.0.0 t

Defined Defined 239.255.255.255

E 1111 Not Not Not Defined Not Defined 240.0.0.0 t

Defined Defined 255.255.255.255
Virtual Circuits vs Datagram Networks
Virtual Circuits are computer networks that offer connection-oriented
services, whereas Datagram networks offer connection-less services. The
Internet that we use is actually built on a Datagram network (connection-
less) at the network level since not all packets that travel from a source to a
destination use the same route.

Virtual Circuits
Connection-oriented switching is another name for virtual circuits. Before
messages are sent, a virtual circuit switching sets a predetermined routing.
This route is referred to as a virtual circuit since it gives the user the
impression that a passionate physical circuit exists. The call request and call
accept packets are used to establish the connection between the sender and
the recipient.

The term "virtual circuit" refers to a logical link between two network nodes,
typically in a communications network. The path consists of many network
parts that are connected by switches.

To better comprehend the virtual circuits, let's look at the diagram shown
below:

Backward Skip 10sPlay VideoForward Skip 10s

The transmitter and receiver in the aforementioned diagram are A and B.
The sender and receiver are linked together using the call request and call
accept packets. Once a path has been established, data will be transferred.

The receiver transmits an acknowledgementsignal after receiving the data to

confirm receipt of the message. If a user wants to break the connection, a
clear signal is sent.

Datagram Networks
It is a method of switching packets in which every packet, or "datagram," is
seen as a distinct entity. The switch uses the destination information
contained in each packet to direct it to the intended location. Since no
specific channel is classified for a connection session, there is no need to
reserve resources. As a result, packets have a header with all of the
information about the destination. A packet's header is examined by the
intermediate nodes, which then select an appropriate link to another node
that is closer to the destination.

Datagram networks assign resources according to the First-Come-First-Serve

(FCFS) principle. Regardless of its source or destination, if another packet is
being processed when a packet arrives at a router, it must wait.
Datagram packets transmitted between hosts H1 and H2 are shown in the
diagram above. The same message is being carried by the four datagram
packets bearing the labels A, B, C, and D, each of which is being sent by a
separate path. The packets of the message reach their destination out of
order. It is H2's responsibility to rearrange the packets in order to recover
the original message.

Difference between Virtual Circuits and Datagram Networks

Let's look at the key distinctions between these two highly contested topics
now:

S. Comparison Virtual Circuits Datagram Networks

no. Criteria

1. Definition It is connection-oriented, which means The service isconnection-less

that resources like buffers, CPU, Since there isn't a pat
bandwidth, etc., are reserved for the specifically designated for
 period of time that a data transfer connection session, n
session will use the newly established resource reservations ar
VC. required.

2. Path Each server along the path has Every packet is permitted t
resources reserved when the first follow any accessible path
packet is sent. For the duration of the Because routing tables o
connection, subsequent packets will routers change continuously
take the same route as the first one intermediary routers mus
transmitted. constantly calculate routes.

3. Header A global header is needed because All packets must be linked to

every packet will take the same route. header that has the correc
The remaining packets often do not information about the sourc
need global headers; just the first and the upper layer data sinc
packet of the connection does. every packet has the freedom
to select any path.

4. Data Flow All packets follow a precise path, so The connection-less attribut
when they arrive at their destination, allows data packets to arriv
they are all received in sequence. at their destination in an
sequence, which raises th
possibility that they will not b
received in the correct orde
at the receiver's end.

5. Resource By using virtual circuit switching, all That a packet can only b
Requirements packets are guaranteed to reach their transmitted if resources lik
& Utilization destination. No packet will be the buffer, CPU, an
discarded because there are no bandwidth are available is
resources available. key disadvantage of datagram
packet switching. If not, th
packet will be thrown away.

6. Phases Setup, data transfer, and teardown are Any type of communicatio
the threephases of the transmission phase does not exist i
process. Datagram Networks.

7. Addressing The routing and addressing are Each datagram packe

chosen during setup. The VC number contains a complete list of th
 is the only thing each packet contains source and destinatio
as a result. addresses.

8. Reliability The aforementioned information leads Datagram networks are les

to the conclusion that Virtual Circuits reliable than virtual circuits.
are a very dependable means of data
transport.

9. Implementatio Virtual circuits have the drawback that However, implementin

n and Cost every time a new connection is datagram networks is usuall
established, resources and additional simple and inexpensiv
data must be allocated at every router because there isn't the adde
along the line. This can be a problem if hassle of building a dedicate
numerous customers are attempting channelevery time a
to reserve a router's resources at the application needs to interact.
same time.

10. Applications Specifically for phone conversations, it It is commonly employed b

is utilized by the ATM (Asynchronous the IP network, which
Transfer Mode) Network. utilized for data services suc
as the Internet.

Conclusion
o Connection-oriented switching is another name for virtual circuits. Prior to
message transmission, virtual circuit switching creates a predetermined path.
o Since it seems to the user to be a devoted physical circuit, the path in virtual
circuits is referred to as a virtual circuit.
o Each packet, referred to as a datagram, is considered as an independent
entity in datagram networks(known as a packet-switching technology). Each
packet contains destination information, which the switch makes use of to
direct the packet to the desired location.
o Because there is no designated channel for a connection session in Datagram
Networks, no resource reservations are required. The effect is that packets
have a header with all of the destination's data.
 o First-come, first-serve (FCFS) scheduling governs resource distribution in
datagram networks.
o A virtual circuit is easier to understand than a network of datagrams.
o Datagram-based networks require substantially less setup and upkeep.

What is Switching?





In computer networking, Switching is the process of transferring data

packets from one device to another in a network, or from one network
to another, using specific devices called switches. A computer user
experiences switching all the time for example, accessing the Internet
from your computer device, whenever a user requests a webpage to
open, the request is processed through switching of data packets only.
Switching takes place at the Data Link layer of the OSI Model. This
means that after the generation of data packets in the Physical Layer,
switching is the immediate next process in data communication. In this
article, we shall discuss different processes involved in switching, what
kind of hardware is used in switching, etc.
What is a Network Switching?
A switch is a dedicated piece of computer hardware that facilitates the
process of switching i.e., incoming data packets and transferring them
to their destination. A switch works at the Data Link layer of the OSI
Model. A switch primarily handles the incoming data packets from a
source computer or network and decides the appropriate port through
which the data packets will reach their target computer or network.
A switch decides the port through which a data packet shall pass with
the help of its destination MAC(Media Access Control) Address. A
switch does this effectively by maintaining a switching table, (also
known as forwarding table).
A network switch is more efficient than a network Hub or repeater
because it maintains a switching table, which simplifies its task and
reduces congestion on a network, which effectively improves the
performance of the network.
Process of Switching
The switching process involves the following steps:
Frame Reception: The switch receives a data frame or packet from a
computer connected to its ports.
 MAC Address Extraction: The switch reads the header of the data
frame and collects the destination MAC Address from it.
 MAC Address Table Lookup: Once the switch has retrieved the
MAC Address, it performs a lookup in its Switching table to find a
port that leads to the MAC Address of the data frame.
 Forwarding Decision and Switching Table Update: If the
switch matches the destination MAC Address of the frame to the
MAC address in its switching table, it forwards the data frame to the
respective port. However, if the destination MAC Address does not
exist in its forwarding table, it follows the flooding process, in which
it sends the data frame to all its ports except the one it came from
and records all the MAC Addresses to which the frame was
delivered. This way, the switch finds the new MAC Address and
updates its forwarding table.
 Frame Transition: Once the destination port is found, the switch
sends the data frame to that port and forwards it to its target
computer/network.
Types of Switching
There are three types of switching methods:
 Message Switching
 Circuit Switching
 Packet Switching
 Datagram Packet Switching
 Virtual Circuit Packet Switching

Let us now discuss them individually:

Message Switching: This is an older switching technique that has
become obsolete. In message switching technique, the entire data
block/message is forwarded across the entire network thus, making it
highly inefficient.
Circuit Switching: In this type of switching, a connection is
established between the source and destination beforehand. This
connection receives the complete bandwidth of the network until the
data is transferred completely.
This approach is better than message switching as it does not involve
sending data to the entire network, instead of its destination only.
Packet Switching: This technique requires the data to be broken
down into smaller components, data frames, or packets. These data
frames are then transferred to their destinations according to the
available resources in the network at a particular time.
This switching type is used in modern computers and even the
Internet. Here, each data frame contains additional information about
the destination and other information required for proper transfer
through network components.
Datagram Packet Switching: In Datagram Packet switching, each
data frame is taken as an individual entity and thus, they are
processed separately. Here, no connection is established before data
transmission occurs. Although this approach provides flexibility in data
transfer, it may cause a loss of data frames or late delivery of the data
frames.
Virtual-Circuit Packet Switching: In Virtual-Circuit Packet switching,
a logical connection between the source and destination is made
before transmitting any data. These logical connections are called
virtual circuits. Each data frame follows these logical paths and
provides a reliable way of transmitting data with less chance of data
loss.

Routing
o A Router is a process of selecting path along which the data can be
transferred from source to the destination. Routing is performed by a special
device known as a router.
o A Router works at the network layer in the OSI model and internet layer in
TCP/IP model
o A router is a networking device that forwards the packet based on the
information available in the packet header and forwarding table.
o The routing algorithms are used for routing the packets. The routing
algorithm is nothing but a software responsible for deciding the optimal path
through which packet can be transmitted.
o The routing protocols use the metric to determine the best path for the
packet delivery. The metric is the standard of measurement such as hop
 count, bandwidth, delay, current load on the path, etc. used by the routing
algorithm to determine the optimal path to the destination.
o The routing algorithm initializes and maintains the routing table for the
process of path determination.

Routing Metrics and Costs

Routing metrics and costs are used for determining the best route to the
destination. The factors used by the protocols to determine the shortest
path, these factors are known as a metric.

Metrics are the network variables used to determine the best route to the
destination. For some protocols use the static metrics means that their value
cannot be changed and for some other routing protocols use the dynamic
metrics means that their value can be assigned by the system administrator.

The most common metric values are given below:

o Hop count: Hop count is defined as a metric that specifies the number of
passes through internetworking devices such as a router, a packet must
travel in a route to move from source to the destination. If the routing
protocol considers the hop as a primary metric value, then the path with the
least hop count will be considered as the best path to move from source to
the destination.
o Delay: It is a time taken by the router to process, queue and transmit a
datagram to an interface. The protocols use this metric to determine the
delay values for all the links along the path end-to-end. The path having the
lowest delay value will be considered as the best path.
o Bandwidth: The capacity of the link is known as a bandwidth of the link. The
bandwidth is measured in terms of bits per second. The link that has a higher
transfer rate like gigabit is preferred over the link that has the lower capacity
like 56 kb. The protocol will determine the bandwidth capacity for all the links
along the path, and the overall higher bandwidth will be considered as the
best route.
 o Load: Load refers to the degree to which the network resource such as a
router or network link is busy. A Load can be calculated in a variety of ways
such as CPU utilization, packets processed per second. If the traffic increases,
then the load value will also be increased. The load value changes with
respect to the change in the traffic.
o Reliability: Reliability is a metric factor may be composed of a fixed value. It
depends on the network links, and its value is measured dynamically. Some
networks go down more often than others. After network failure, some
network links repaired more easily than other network links. Any reliability
factor can be considered for the assignment of reliability ratings, which are
generally numeric values assigned by the system administrator.

Types of Routing
Routing can be classified into three categories:

o Static Routing
o Default Routing
o Dynamic Routing

Static Routing

o Static Routing is also known as Nonadaptive Routing.

o It is a technique in which the administrator manually adds the routes in a
routing table.
 o A Router can send the packets for the destination along the route defined by
the administrator.
o In this technique, routing decisions are not made based on the condition or
topology of the networks

Advantages Of Static Routing

Following are the advantages of Static Routing:

o No Overhead: It has ho overhead on the CPU usage of the router. Therefore,

the cheaper router can be used to obtain static routing.
o Bandwidth: It has not bandwidth usage between the routers.
o Security: It provides security as the system administrator is allowed only to
have control over the routing to a particular network.

Disadvantages of Static Routing:

Following are the disadvantages of Static Routing:

o For a large network, it becomes a very difficult task to add each route
manually to the routing table.
o The system administrator should have a good knowledge of a topology as he
has to add each route manually.

Default Routing

o Default Routing is a technique in which a router is configured to send all the

packets to the same hop device, and it doesn't matter whether it belongs to a
particular network or not. A Packet is transmitted to the device for which it is
configured in default routing.
o Default Routing is used when networks deal with the single exit point.
o It is also useful when the bulk of transmission networks have to transmit the
data to the same hp device.
o When a specific route is mentioned in the routing table, the router will choose
the specific route rather than the default route. The default route is chosen
only when a specific route is not mentioned in the routing table.
Dynamic Routing

o It is also known as Adaptive Routing.

o It is a technique in which a router adds a new route in the routing table for
each packet in response to the changes in the condition or topology of the
network.
o Dynamic protocols are used to discover the new routes to reach the
destination.
o In Dynamic Routing, RIP and OSPF are the protocols used to discover the new
routes.
o If any route goes down, then the automatic adjustment will be made to reach
the destination.

The Dynamic protocol should have the following features:

o All the routers must have the same dynamic routing protocol in order to
exchange the routes.
o If the router discovers any change in the condition or topology, then router
broadcast this information to all other routers.

Advantages of Dynamic Routing:

o It is easier to configure.
o It is more effective in selecting the best route in response to the changes in
the condition or topology.

Disadvantages of Dynamic Routing:

o It is more expensive in terms of CPU and bandwidth usage.

o It is less secure as compared to default and static routing.

Network Layer Protocols

TCP/IP supports the following protocols:

ARP
 o ARP stands for Address Resolution Protocol.
o It is used to associate an IP address with the MAC address.
o 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.

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.
Steps taken by ARP protocol
If a device wants to communicate with another device, the following steps
are taken by the device:

o The device will first look at its internet list, called the ARP cache to check
whether an IP address contains a matching MAC address or not. It will check
the ARP cache in command prompt by using a command arp-a.
 o If ARP cache is empty, then device broadcast the message to the entire
network asking each device for a matching MAC address.
o The device that has the matching IP address will then respond back to the
sender with its MAC address
o Once the MAC address is received by the device, then the communication
can take place between two devices.
o If the device receives the MAC address, then the MAC address gets stored in
the ARP cache. We can check the ARP cache in command prompt by using a
command arp -a.

Note: ARP cache is used to make a network more efficient.

In the above screenshot, we observe the association of IP address to the MAC

address.

There are two types of ARP entries:

 o 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.
o Static entry: It is an entry where someone manually enters the IP to MAC
address association by using the ARP command utility.

RARP
o RARP stands for Reverse Address Resolution Protocol.
o 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.
o The protocol which is used to obtain the IP address from a server is known
as Reverse Address Resolution Protocol.
o The message format of the RARP protocol is similar to the ARP protocol.
o Like ARP frame, RARP frame is sent from one machine to another
encapsulated in the data portion of a frame.
ICMP
o ICMP stands for Internet Control Message Protocol.
o The ICMP is a network layer protocol used by hosts and routers to send the
notifications of IP datagram problems back to the sender.
o ICMP uses echo test/reply to check whether the destination is reachable and
responding.
o ICMP handles both control and error messages, but its main function is to
report the error but not to correct them.
o 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.
o ICMP protocol communicates the error messages to the sender. ICMP
messages cause the errors to be returned back to the user processes.
o ICMP messages are transmitted within IP datagram.

The Format of an ICMP message

o The first field specifies the type of the message.

o The second field specifies the reason for a particular message type.
o The checksum field covers the entire ICMP message.

Error Reporting
ICMP protocol reports the error messages to the sender.

Five types of errors are handled by the ICMP protocol:

o Destination unreachable
o Source Quench
o Time Exceeded
o Parameter problems
o Redirection
 o Destination unreachable: The message of "Destination Unreachable" is
sent from receiver to the sender when destination cannot be reached, or
packet is discarded when the destination is not reachable.
o Source Quench: The purpose of the source quench message is congestion
control. The message sent from the congested router to the source host to
reduce the transmission rate. ICMP will take the IP of the discarded packet
and then add the source quench message to the IP datagram to inform the
source host to reduce its transmission rate. The source host will reduce the
transmission rate so that the router will be free from congestion.
o Time Exceeded: Time Exceeded is also known as "Time-To-Live". It is a
parameter that defines how long a packet should live before it would be
discarded.

There are two ways when Time Exceeded message can be

generated:

Sometimes packet discarded due to some bad routing implementation, and

this causes the looping issue and network congestion. Due to the looping
issue, the value of TTL keeps on decrementing, and when it reaches zero, the
router discards the datagram. However, when the datagram is discarded by
the router, the time exceeded message will be sent by the router to the
source host.

When destination host does not receive all the fragments in a certain time
limit, then the received fragments are also discarded, and the destination
host sends time Exceeded message to the source host.

o Parameter problems: When a router or host discovers any missing value in

the IP datagram, the router discards the datagram, and the "parameter
problem" message is sent back to the source host.
 o Redirection: Redirection message is generated when host consists of a
small routing table. When the host consists of a limited number of entries due
to which it sends the datagram to a wrong router. The router that receives a
datagram will forward a datagram to a correct router and also sends the
"Redirection message" to the host to update its routing table.

IGMP
o IGMP stands for Internet Group Message Protocol.
o The IP protocol supports two types of communication:
o Unicasting: It is a communication between one sender and one
receiver. Therefore, we can say that it is one-to-one communication.
o 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.
o The IGMP protocol is used by the hosts and router to support multicasting.
o The IGMP protocol is used by the hosts and router to identify the hosts in a
LAN that are the members of a group.

o IGMP is a part of the IP layer, and IGMP has a fixed-size message.

 o The IGMP message is encapsulated within an IP datagram.

The Format of IGMP message

Where,

Type: It determines the type of IGMP message. There are three types of
IGMP message: Membership Query, Membership Report and Leave Report.

Maximum Response Time: This field is used only by the Membership

Query message. It determines the maximum time the host can send the
Membership Report message in response to the Membership Query
message.

Checksum: It determines the entire payload of the IP datagram in which

IGMP message is encapsulated.

Group Address: The behavior of this field depends on the type of the
message sent.

o For Membership Query, the group address is set to zero for General Query
and set to multicast group address for a specific query.
o For Membership Report, the group address is set to the multicast group
address.
o For Leave Group, it is set to the multicast group address.

IGMP Messages
o Membership Query message
o This message is sent by a router to all hosts on a local area network to
determine the set of all the multicast groups that have been joined by
the host.
o It also determines whether a specific multicast group has been joined
by the hosts on a attached interface.
o The group address in the query is zero since the router expects one
response from a host for every group that contains one or more
members on that host.
o Membership Report message
o The host responds to the membership query message with a
membership report message.
o Membership report messages can also be generated by the host when
a host wants to join the multicast group without waiting for a
membership query message from the router.
o Membership report messages are received by a router as well as all
the hosts on an attached interface.
o Each membership report message includes the multicast address of a
single group that the host wants to join.
 o IGMP protocol does not care which host has joined the group or how
many hosts are present in a single group. It only cares whether one or
more attached hosts belong to a single multicast group.
o The membership Query message sent by a router also includes a
"Maximum Response time". After receiving a membership query
message and before sending the membership report message, the
host waits for the random amount of time from 0 to the maximum
response time. If a host observes that some other attached host has
sent the "Maximum Report message", then it discards its
"Maximum Report message" as it knows that the attached router
already knows that one or more hosts have joined a single multicast
group. This process is known as feedback suppression. It provides the
performance optimization, thus avoiding the unnecessary transmission
of a "Membership Report message".
o Leave Report
When the host does not send the "Membership Report message", it means
that the host has left the group. The host knows that there are no members
in the group, so even when it receives the next query, it would not report the
group.

Routing algorithm
o In order to transfer the packets from source to the destination, the network
layer must determine the best route through which packets can be
transmitted.
o Whether the network layer provides datagram service or virtual circuit
service, the main job of the network layer is to provide the best route. The
routing protocol provides this job.
o The routing protocol is a routing algorithm that provides the best path from
the source to the destination. The best path is the path that has the "least-
cost path" from source to the destination.
 o Routing is the process of forwarding the packets from source to the
destination but the best route to send the packets is determined by the
routing algorithm.

Classification of a Routing algorithm

The Routing algorithm is divided into two categories:

o Adaptive Routing algorithm

o Non-adaptive Routing algorithm

Adaptive Routing algorithm

o An adaptive routing algorithm is also known as dynamic routing algorithm.

o This algorithm makes the routing decisions based on the topology and
network traffic.
o The main parameters related to this algorithm are hop count, distance and
estimated transit time.

An adaptive routing algorithm can be classified into three parts:

o Centralized algorithm: It is also known as global routing algorithm as it

computes the least-cost path between source and destination by using
complete and global knowledge about the network. This algorithm takes the
connectivity between the nodes and link cost as input, and this information is
obtained before actually performing any calculation. Link state algorithm is
 referred to as a centralized algorithm since it is aware of the cost of each link
in the network.
o Isolation algorithm: It is an algorithm that obtains the routing information
by using local information rather than gathering information from other
nodes.
o Distributed algorithm: It is also known as decentralized algorithm as it
computes the least-cost path between source and destination in an iterative
and distributed manner. In the decentralized algorithm, no node has the
knowledge about the cost of all the network links. In the beginning, a node
contains the information only about its own directly attached links and
through an iterative process of calculation computes the least-cost path to
the destination. A Distance vector algorithm is a decentralized algorithm as it
never knows the complete path from source to the destination, instead it
knows the direction through which the packet is to be forwarded along with
the least cost path.

Non-Adaptive Routing algorithm

o Non Adaptive routing algorithm is also known as a static routing algorithm.

o When booting up the network, the routing information stores to the routers.
o Non Adaptive routing algorithms do not take the routing decision based on
the network topology or network traffic.

The Non-Adaptive Routing algorithm is of two types:

Flooding: In case of flooding, every incoming packet is sent to all the

outgoing links except the one from it has been reached. The disadvantage of
flooding is that node may contain several copies of a particular packet.

Random walks: In case of random walks, a packet sent by the node to one
of its neighbors randomly. An advantage of using random walks is that it
uses the alternative routes very efficiently.

Differences b/w Adaptive and Non-Adaptive Routing Algorithm

Basis Of Adaptive Routing algorithm Non-Adaptive Routing algorithm
Comparison

Define Adaptive Routing algorithm is an The Non-Adaptive Routing algorithm

algorithm that constructs the an algorithm that constructs the stati
routing table based on the network table to determine which node to sen
conditions. the packet.

Usage Adaptive routing algorithm is used The Non-Adaptive Routing algorithm

by dynamic routing. used by static routing.

Routing Routing decisions are made based Routing decisions are the static tables.
decision on topology and network traffic.

Categorization The types of adaptive routing The types of Non Adaptive routin
algorithm, are Centralized, isolation algorithm are flooding and random walks
and distributed algorithm.

Complexity Adaptive Routing algorithms are Non-Adaptive Routing algorithms ar

more complex. simple.

Distance Vector Routing Algorithm

o The Distance vector algorithm is iterative, asynchronous and
distributed.
o Distributed: It is distributed in that each node receives information
from one or more of its directly attached neighbors, performs
calculation and then distributes the result back to its neighbors.
o Iterative: It is iterative in that its process continues until no more
information is available to be exchanged between neighbors.
o Asynchronous: It does not require that all of its nodes operate in the
lock step with each other.
 o The Distance vector algorithm is a dynamic algorithm.
o It is mainly used in ARPANET, and RIP.
o Each router maintains a distance table known as Vector.

Three Keys to understand the working of Distance

Vector Routing Algorithm:
o Knowledge about the whole network: Each router shares its knowledge
through the entire network. The Router sends its collected knowledge about
the network to its neighbors.
o Routing only to neighbors: The router sends its knowledge about the
network to only those routers which have direct links. The router sends
whatever it has about the network through the ports. The information is
received by the router and uses the information to update its own routing
table.
o Information sharing at regular intervals: Within 30 seconds, the router
sends the information to the neighboring routers.

Distance Vector Routing Algorithm

Let dx(y) be the cost of the least-cost path from node x to node y. The least
costs are related by Bellman-Ford equation,

dx(y) = minv{c(x,v) + dv(y)}

Where the minv is the equation taken for all x neighbors. After traveling
from x to v, if we consider the least-cost path from v to y, the path cost will
be c(x,v)+dv(y). The least cost from x to y is the minimum of c(x,v)+d v(y)
taken over all neighbors.

With the Distance Vector Routing algorithm, the node x contains the
following routing information:

o For each neighbor v, the cost c(x,v) is the path cost from x to directly
attached neighbor, v.
o The distance vector x, i.e., D x = [ Dx(y) : y in N ], containing its cost to all
destinations, y, in N.
 o The distance vector of each of its neighbors, i.e., D v = [ Dv(y) : y in N ] for
each neighbor v of x.

Distance vector routing is an asynchronous algorithm in which node x sends

the copy of its distance vector to all its neighbors. When node x receives the
new distance vector from one of its neighboring vector, v, it saves the
distance vector of v and uses the Bellman-Ford equation to update its own
distance vector. The equation is given below:

dx(y) = minv{ c(x,v) + dv(y)} for each node y in N

The node x has updated its own distance vector table by using the above
equation and sends its updated table to all its neighbors so that they can
update their own distance vectors.

Algorithm
At each node x,

Initialization

for all destinations y in N:

Dx(y) = c(x,y) // If y is not a neighbor then c(x,y) = ∞
for each neighbor w
Dw(y) = ? for all destination y in N.
for each neighbor w
send distance vector Dx = [ Dx(y) : y in N ] to w
loop
wait(until I receive any distance vector from some neighbor w)
for each y in N:
Dx(y) = minv{c(x,v)+Dv(y)}
If Dx(y) is changed for any destination y
Send distance vector Dx = [ Dx(y) : y in N ] to all neighbors
forever

Note: In Distance vector algorithm, node x update its table when it either see any cost
change in one directly linked nodes or receives any vector update from some neighbor.

Let's understand through an example:

Sharing Information
o In the above figure, each cloud represents the network, and the number
inside the cloud represents the network ID.
o All the LANs are connected by routers, and they are represented in boxes
labeled as A, B, C, D, E, F.
o Distance vector routing algorithm simplifies the routing process by assuming
the cost of every link is one unit. Therefore, the efficiency of transmission can
be measured by the number of links to reach the destination.
o In Distance vector routing, the cost is based on hop count.
In the above figure, we observe that the router sends the knowledge to the
immediate neighbors. The neighbors add this knowledge to their own
knowledge and sends the updated table to their own neighbors. In this way,
routers get its own information plus the new information about the
neighbors.

Routing Table
Two process occurs:

o Creating the Table

o Updating the Table

Creating the Table

Initially, the routing table is created for each router that contains atleast
three types of information such as Network ID, the cost and the next hop.
 o NET ID: The Network ID defines the final destination of the packet.
o Cost: The cost is the number of hops that packet must take to get there.
o Next hop: It is the router to which the packet must be delivered.

o In the above figure, the original routing tables are shown of all the routers. In
a routing table, the first column represents the network ID, the second
column represents the cost of the link, and the third column is empty.
o These routing tables are sent to all the neighbors.

For Example:

1. A sends its routing table to B, F & E.

2. B sends its routing table to A & C.
3. C sends its routing table to B & D.
4. D sends its routing table to E & C.
5. E sends its routing table to A & D.
6. F sends its routing table to A.

Updating the Table

o When A receives a routing table from B, then it uses its information to update
the table.
o The routing table of B shows how the packets can move to the networks 1
and 4.
o The B is a neighbor to the A router, the packets from A to B can reach in one
hop. So, 1 is added to all the costs given in the B's table and the sum will be
the cost to reach a particular network.

o After adjustment, A then combines this table with its own table to create a
combined table.

o The combined table may contain some duplicate data. In the above figure,
the combined table of router A contains the duplicate data, so it keeps only
those data which has the lowest cost. For example, A can send the data to
network 1 in two ways. The first, which uses no next router, so it costs one
hop. The second requires two hops (A to B, then B to Network 1). The first
option has the lowest cost, therefore it is kept and the second one is dropped.
 o The process of creating the routing table continues for all routers. Every
router receives the information from the neighbors, and update the routing
table.

Final routing tables of all the routers are given below:

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:

o 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.
 o 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.
o Information sharing: A router sends the information to every other router
only when the change occurs in the information.

Link State Routing has two phases:

Reliable Flooding

o Initial state: Each node knows the cost of its neighbors.

o Final state: Each node knows the entire graph.

Route Calculation
Each node uses Dijkstra's algorithm on the graph to calculate the optimal
routes to all nodes.

o 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.
o 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.

Let's describe some notations:

o c( i , j): Link cost from node i to node j. If i and j nodes are not directly linked,
then c(i , j) = ∞.
o D(v): It defines the cost of the path from source code to destination v that
has the least cost currently.
o P(v): It defines the previous node (neighbor of v) along with current least
cost path from source to v.
o N: It is the total number of nodes available in the network.
Algorithm
Initialization
N = {A} // A is a root node.
for all nodes v
if v adjacent to A
then D(v) = c(A,v)
else D(v) = infinity
loop
find w not in N such that D(w) is a minimum.
Add w to N
Update D(v) for all v adjacent to w and not in N:
D(v) = min(D(v) , D(w) + c(w,v))
Until all nodes in N

In the above algorithm, an initialization step is followed by the loop. The

number of times the loop is executed is equal to the total number of nodes
available in the network.

Let's understand through an example:

In the above figure, source vertex is A.

 Step 1:

The first step is an initialization step. The currently known least cost path
from A to its directly attached neighbors, B, C, D are 2,5,1 respectively. The
cost from A to B is set to 2, from A to D is set to 1 and from A to C is set to 5.
The cost from A to E and F are set to infinity as they are not directly linked to
A.

Step N D(B),P(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),P(F)

1 A 2,A 5,A 1,A ∞ ∞

Step 2:

In the above table, we observe that vertex D contains the least cost path in
step 1. Therefore, it is added in N. Now, we need to determine a least-cost
path through D vertex.

a) Calculating shortest path from A to B

1. v = B, w = D
2. D(B) = min( D(B) , D(D) + c(D,B) )
3. = min( 2, 1+2)>
4. = min( 2, 3)
5. The minimum value is 2. Therefore, the currently shortest path from A to B is 2.

b) Calculating shortest path from A to C

1. v = C, w = D
2. D(B) = min( D(C) , D(D) + c(D,C) )
3. = min( 5, 1+3)
4. = min( 5, 4)
5. The minimum value is 4. Therefore, the currently shortest path from A to C is 4.</
p>

c) Calculating shortest path from A to E

1. v = E, w = D
2. D(B) = min( D(E) , D(D) + c(D,E) )
3. = min( ∞, 1+1)
4. = min(∞, 2)
5. The minimum value is 2. Therefore, the currently shortest path from A to E is 2.

Note: The vertex D has no direct link to vertex E. Therefore, the value of D(F) is infinity.

Step N D(B),P(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),P(F)

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

Step 3:

In the above table, we observe that both E and B have the least cost path in
step 2. Let's consider the E vertex. Now, we determine the least cost path of
remaining vertices through E.

a) Calculating the shortest path from A to B.

1. v = B, w = E
2. D(B) = min( D(B) , D(E) + c(E,B) )
3. = min( 2 , 2+ ∞ )
4. = min( 2, ∞)
5. The minimum value is 2. Therefore, the currently shortest path from A to B is 2.

b) Calculating the shortest path from A to C.

1. v = C, w = E
2. D(B) = min( D(C) , D(E) + c(E,C) )
3. = min( 4 , 2+1 )
4. = min( 4,3)
5. The minimum value is 3. Therefore, the currently shortest path from A to C is 3.

c) Calculating the shortest path from A to F.

1. v = F, w = E
2. D(B) = min( D(F) , D(E) + c(E,F) )
3. = min( ∞ , 2+2 )
4. = min(∞ ,4)
5. The minimum value is 4. Therefore, the currently shortest path from A to F is 4.

Step N D(B),P(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),P(F)

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 ADE 2,A 3,E 4,E

Step 4:

In the above table, we observe that B vertex has the least cost path in step
3. Therefore, it is added in N. Now, we determine the least cost path of
remaining vertices through B.

a) Calculating the shortest path from A to C.

1. v = C, w = B
2. D(B) = min( D(C) , D(B) + c(B,C) )
3. = min( 3 , 2+3 )
4. = min( 3,5)
5. The minimum value is 3. Therefore, the currently shortest path from A to C is 3.

b) Calculating the shortest path from A to F.

1. v = F, w = B
2. D(B) = min( D(F) , D(B) + c(B,F) )
3. = min( 4, ∞)
4. = min(4, ∞)
5. The minimum value is 4. Therefore, the currently shortest path from A to F is 4.

Step N D(B),P(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),P(F)

 1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 ADE 2,A 3,E 4,E

4 ADEB 3,E 4,E

Step 5:

In the above table, we observe that C vertex has the least cost path in step
4. Therefore, it is added in N. Now, we determine the least cost path of
remaining vertices through C.

a) Calculating the shortest path from A to F.

1. v = F, w = C
2. D(B) = min( D(F) , D(C) + c(C,F) )
3. = min( 4, 3+5)
4. = min(4,8)
5. The minimum value is 4. Therefore, the currently shortest path from A to F is 4.

Step N D(B),P(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),P(F)

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 ADE 2,A 3,E 4,E

4 ADEB 3,E 4,E

5 ADEBC 4,E
Final table:

Step N D(B),P(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),P(F)

1 A 2,A 5,A 1,A ∞ ∞

2 AD 2,A 4,D 2,D ∞

3 ADE 2,A 3,E 4,E

4 ADEB 3,E 4,E

5 ADEBC 4,E

6 ADEBCF

Disadvantage:
Heavy traffic is created in Line state routing due to Flooding. Flooding can
cause an infinite looping, this problem can be solved by using Time-to-leave
field