Computer Networks (CN)

Unit - 4
Network Layer

Prepared by:
Vidhi D Patel
Assistant Professor
SSASIT.
INTRODUCTION
Forwarding and Routing
• The role of the network layer is to move packets from a
sending host to a receiving host.
• To do so, two important network-layer functions can be
identified: forwarding and routing.
• Forwarding: When a packet arrives at a router’s input
link, the router must move the packet to the appropriate
output link.
- For example, a packet arriving from Host H1 to Router
R1 must be forwarded to the next router on a path to
H2.
• Routing: The network layer must determine the route or
path taken by packets as they flow from a sender to a
receiver.
- The algorithms that calculate these paths are referred
to as routing algorithms.
- A routing algorithm would determine, for example,
the path along which packets flow from H1 to H2.
• The terms forwarding and routing are often used
interchangeably by authors discussing the network layer.
• Forwarding refers to the router-local action of
transferring a packet from an input link interface to the
appropriate output link interface.
• Routing refers to the network-wide process that
determines the end-to-end paths that packets take from
source to destination.
• Every router has a forwarding table.
• A router forwards a packet by examining the value of a
field in the arriving packet’s header, and then using this
header value to index into the router’s forwarding table.
• The value stored in the forwarding table entry for that
header indicates the router’s outgoing link interface to
which that packet is to be forwarded.
• Depending on the network-layer protocol, the header
value could be the destination address of the packet or
an indication of the connection to which the packet
belongs.
• Figure 1 provides an example.
Figure 1: Routing algorithms determine values in forwarding tables
• In Figure 1, a packet with a header field value of 0111
arrives to a router.
• The router indexes into its forwarding table and
determines that the output link interface for this packet
is interface 2.
• The router then internally forwards the packet to
interface 2.
• You might now be wondering how the forwarding tables
in the routers are configured.
• This is a crucial issue, one that exposes the important
interplay between routing and forwarding.
• As shown in Figure 1, the routing algorithm determines
the values that are inserted into the routers’ forwarding
tables.
• The routing algorithm may be centralized (e.g., with an
algorithm executing on a central site and downloading
routing information to each of the routers) or
decentralized (i.e., with a piece of the distributed routing
algorithm running in each router).
• In either case, a router receives routing protocol
messages, which are used to configure its forwarding
table.
Network Service Models
• The network service model defines the characteristics of
end-to-end transport of packets between sending and
receiving end systems.
• In the sending host, when the transport layer passes a
packet to the network layer, specific services that could
be provided by the network layer for individual
datagrams include:
- Guaranteed delivery: This service guarantees that the
packet will eventually arrive at its destination.
- Guaranteed delivery with bounded delay: This
service not only guarantees delivery of the packet, but
delivery within a specified host-to-host delay bound
(for example, within 100 msec).
• Furthermore, the following services could be provided to
a flow of packets between a given source and
destination:
- In-order packet delivery: This service guarantees that
packets arrive at the destination in the order that they
were sent.
- Guaranteed minimal bandwidth: This network-layer
service emulates the behavior of a transmission link of
a specified bit rate (for example, 1 Mbps) between
sending and receiving hosts.
- As long as the sending host transmits bits (as part of
packets) at a rate below the specified bit rate, then no
packet is lost and each packet arrives within a
prespecified host-to-host delay (for example, within
40 msec).
- Guaranteed maximum jitter: This service guarantees that
the amount of time between the transmission of two
successive packets at the sender is equal to the amount of
time between their receipt at the destination.
- Security services: Using a secret session key known only
by a source and destination host, the network layer in the
source host could encrypt the payloads of all datagrams
being sent to the destination host.
- The network layer in the destination host would then be
responsible for decrypting the payloads.
- With such a service, confidentiality would be provided to
all transport-layer segments (TCP and UDP) between the
source and destination hosts.
- In addition to confidentiality, the network layer could
provide data integrity and source authentication services.
VIRTUAL CIRCUIT AND DATAGRAM
NETWORKS
• In all major computer network architectures to date
(Internet, ATM, frame relay, and so on), the network
layer provides either a host-to-host connectionless
service or a host-to-host connection service, but not
both.
• Computer networks that provide only a connection
service at the network layer are called virtual-circuit (VC)
networks; computer networks that provide only a
connectionless service at the network layer are called
datagram networks.
• Virtual-circuit and datagram networks are two
fundamental classes of computer networks.
• They use very different information in making their
forwarding decisions.
Virtual-Circuit Networks (Connection Oriented Service)
• A Virtual Circuit (VC) consists of
1) a path (that is, a series of links and routers) between
the source and destination hosts,
2) VC numbers, one number for each link along the
path, and
3) entries in the forwarding table in each router along
the path.
• A packet belonging to a virtual circuit will carry a VC
number in its header.
• Because a virtual circuit may have a different VC number
on each link, each intervening router must replace the VC
number of each traversing packet with a new VC number.
• The new VC number is obtained from the forwarding
table.
• To illustrate the concept, consider the network shown in
Figure 2.

Figure 2: A simple virtual

circuit network

• The numbers next to the links of R1 in Figure 2 are the

link interface numbers.
• Suppose now that Host A requests that the network
establish a VC between itself and Host B.
• Suppose also that the network chooses the path
A-R1-R2-B and assigns VC numbers 12, 22, and 32 to the
three links in this path for this virtual circuit.
• In this case, when a packet in this VC leaves Host A, the
value in the VC number field in the packet header is 12;
when it leaves R1, the value is 22; and when it leaves R2,
the value is 32.
• How does the router determine the replacement VC
number for a packet traversing the router?
• For a VC network, each router’s forwarding table includes
VC number translation; for example, the forwarding table
in R1 might look something like this:
• Whenever a new VC is established across a router, an
entry is added to the forwarding table.
• Similarly, whenever a VC terminates, the appropriate
entries in each table along its path are removed.
• A path from the source router to the destination router
must be established before any data packets can be sent.
• This connection is called a VC (virtual circuit), and the
subnet is called a virtual-circuit subnet.
• When a connection is established, a route from the
source machine to the destination machine is chosen as
part of the connection setup and stored in tables inside
the routers.
• That route is used for all traffic flowing over the
connection, exactly the same way that the telephone
system works.
 Figure 3: Virtual-circuit setup

• There are three identifiable phases in a virtual circuit:

1. VC Setup
2. Data transfer
3. VC teardown
1. VC Setup: During the setup phase, the sending
transport layer contacts the network layer, specifies
the receiver’s address, and waits for the network to set
up the VC.
- The network layer determines the path between
sender and receiver, that is, the series of links and
routers through which all packets of the VC will travel.
- The network layer also determines the VC number for
each link along the path.
- Finally, the network layer adds an entry in the
forwarding table in each router along the path.
- During VC setup, the network layer may also reserve
resources (for example, bandwidth) along the path of
the VC.
2. Data transfer: As shown in Figure 3, once the VC has
been established, packets can begin to flow along the
VC.
3. VC teardown: This is initiated when the sender (or
receiver) informs the network layer of its desire to
terminate the VC.
- The network layer will then typically inform the end
system on the other side of the network of the call
termination and update the forwarding tables in each
of the packet routers on the path to indicate that the
VC no longer exists.
• There is a subtle but important distinction between VC
setup at the network layer and connection setup at the
transport layer.
• Connection setup at the transport layer involves only the
two end systems. During transport-layer connection
setup, the two end systems alone determine the
parameters (for example, initial sequence number and
flow-control window size) of their transport-layer
connection.
• Although the two end systems are aware of the
transport-layer connection, the routers within the
network are completely unaware to it.
• On the other hand, with a VC network layer, routers
along the path between the two end systems are
involved in VC setup, and each router is fully aware of all
the VCs passing through it.
• The messages that the end systems send into the
network to initiate or terminate a VC, and the messages
passed between the routers to set up the VC (that is, to
modify connection state in router tables) are known as
signaling messages, and the protocols used to exchange
these messages are often referred to as signaling
protocols.
• VC setup is shown pictorially in Figure 3.
Datagram Networks (Connection-Less Service)
• In a datagram network, each time an end system wants
to send a packet, it stamps the packet with the address
of the destination end system and then pops the packet
into the network.
• As shown in Figure 4, there is no VC setup and routers do
not maintain any VC state information.

Figure 4: Datagram network

• As a packet is transmitted from source to destination, it
passes through a series of routers.
• Each of these routers uses the packet’s destination
address to forward the packet.
• Specifically, each router has a forwarding table that maps
destination addresses to link interfaces; when a packet
arrives at the router, the router uses the packet’s
destination address to look up the appropriate output
link interface in the forwarding table.
• The router then intentionally forwards the packet to that
output link interface.
• Because forwarding tables in datagram networks can be
modified at any time, a series of packets sent from one
end system to another may follow different paths
through the network and may arrive out of order.
Difference Between Virtual Circuits And
Datagram Networks
BASIS OF
VIRTUAL CIRCUITS DATAGRAM NETWORKS
COMPARISON
Virtual circuits are computer Datagram networks are computer
networks that provide only a networks that provide only a
Description
connection service at the network connectionless service at the
layer. network layer.
There is a reservation of resources
There is no need for reservation
like buffers, CPU, bandwidth, etc. for
Reservation of of resources as there is no
the time in which the newly setup VC
Resource dedicated path for a connection
is going to be used by a data transfer
session.
session.
Datagram networks are
Virtual circuits are implemented at
implemented in the routers in the
Implementation the edge of the network in the end
network core as well as in the end
systems.
systems.
Packets always reach their intended Packets reach their intended
Packets destination in the same order in destination in a different order in
which they were sent. which they were sent.
 BASIS OF
VIRTUAL CIRCUITS DATAGRAM NETWORKS
COMPARISON
First packet goes and reserves All packets are free to go to any
resources for the subsequent packets path which is decided on the go by
Path
which as a result follow the same dynamically changing routing
path for the whole connection time. tables on routers.
Datagram networks are not
The virtual circuit provides a reliable
reliable because the
communication function to ensure
connectionless property makes
Reliability that each group arrives correctly, and
data packets reach the destination
the group remains in the original
in any order, different from the
order in which they were sent.
order in which they were sent.
Virtual circuits are costly to Datagram networks are always
implement because each time a new cost effective and easy to
Cost connection has to be set up with implement, there is no problem of
reservation of resources and extra reserving resources each time an
information handling at routers. application has to communicate.
It is used by the ATM (Asynchronous It is generally used in the IP
Application Transfer Mode) Network, which is network which is used for data
used for telephone calls. service like internet.
Routing Processor
• The routing processor executes the routing protocols,
maintains routing tables and attached link state
information, and computes the forwarding table for the
router.
• It also performs the network management functions.
THE INTERNET PROTOCOL (IP):
FORWARDING AND ADDRESSING IN THE
INTERNET
• The forwarding and addressing in the internet are
important components of the Internet Protocol (IP).
• There are two versions of IP in use today.
1. the widely deployed IP version 4, which is usually
referred to simply as IPv4.
2. The IP version 6, which has been proposed to
replace IPv4.
• As shown in the Figure below, the internet’s network
layer has three major components.
 Figure: A look inside
the Internet’s
network layer

1. The first component is the IP.

2. The second major component is the routing component, which
determines the path a datagram follows from source to
destination.
3. The final component of the network layer is a facility to report
errors in datagrams and respond to requests for certain
network-layer information.
IPv4 Datagram Format
• A network-layer packet is referred to as a datagram.
• The IPv4 datagram format is shown in Figure below.

Figure: IPv4 datagram format

• The key fields in the IPv4 datagram are the following:
• Version number: These 4 bits specify the IP protocol version
of the datagram. By looking at the version number, the router
can determine how to interpret the remainder of the IP
datagram. Different versions of IP use different datagram
formats.
• Header length: Because an IPv4 datagram can contain a
variable number of options (which are included in the IPv4
datagram header), these 4 bits are needed to determine
where in the IP datagram the data actually begins. Most IP
datagrams do not contain options, so the typical IP datagram
has a 20-byte header.
• Type of service: The type of service (TOS) bits were included
in the IPv4 header to allow different types of IP datagrams
(for example, datagrams particularly requiring low delay, high
throughput, or reliability) to be distinguished from each
other.
• Datagram length: This is the total length of the IP datagram
(header plus data), measured in bytes. Since this field is 16 bits
long, the theoretical maximum size of the IP datagram is 65,535
bytes. However, datagrams are rarely larger than 1,500 bytes.
• Identifier: Uniquely identifies the datagram. It is incremented
by 1 each time a datagram is sent. All fragments of a datagram
contain the same identification value. This allows the
destination host to determine which fragment belongs to which
datagram.
• Flags: The flags field has three bits: one unused bit, one “don’t
fragment”(DF) bit, and one “more fragment”(MF) bit. If the DF
bit is set to 1, it forces the router not to fragment the packet. If
there are more, the MF bit is set to 1; otherwise it is set to 0.
• Fragmentation offset: When fragmentation of a message
occurs, this field specifies the offset, or position, in the overall
message where the data in this fragment goes. It is specified in
units of 8 bytes (64 bits).
• Time-to-live: The time-to-live (TTL) field is included to ensure
that datagrams do not circulate forever in the network. This
field is decremented by one each time the datagram is
processed by a router. If the TTL field reaches 0, the datagram
must be dropped.
• Protocol: This field is used only when an IP datagram reaches
its final destination. The value of this field indicates the specific
transport-layer protocol to which the data portion of this IP
datagram should be passed. For example, a value of 6 indicates
that the data portion is passed to TCP, while a value of 17
indicates that the data is passed to UDP.
• Header checksum: The header checksum aids a router in
detecting bit errors in a received IP datagram.
• Source and destination IP addresses: When a source creates a
datagram, it inserts its IP address into the source IP address
field and inserts the address of the ultimate destination into
the destination IP address field.
• Options: The options fields allow an IP header to be extended.
It stores optional information such as source route. Due to the
presence of options, the size of the datagram header can be of
variable length (20 bytes to 60 bytes).
• Data (payload): In most circumstances, the data field of the IP
datagram contains the transport-layer segment (TCP or UDP) to
be delivered to the destination. However, the data field can
carry other types of data, such as ICMP messages.
IPv4 Addressing
• An IPv4 address is a 32-bit address that uniquely and
universally defines the connection of a host or a router to
the Internet.
• The IP address is the address of the connection, not the
host or the router, because if the device is moved to
another network, the IP address may be changed.
• IPv4 addresses are unique in the sense that each address
defines one, and only one, connection to the Internet.
• If a device has two connections to the Internet, via two
networks, it has two IPv4 addresses.
• IPv4 addresses are universal in the sense that the
addressing system must be accepted by any host that
wants to be connected to the Internet.
Address Space
• A protocol like IPv4 that defines addresses has an
address space. An address space is the total number of
addresses used by the protocol.
• If a protocol uses b bits to define an address, the address
space is 2b because each bit can have two different
values (0 or 1).
• IPv4 uses 32-bit addresses, which means that the address
space is 232 or 4,294,967,296 (more than four billion).
• If there were no restrictions, more than 4 billion devices
could be connected to the Internet.
• Notation: There are 3 notations to show an IPv4 address:
• binary notation (base 2),
• dotted-decimal notation (base 256), and
• hexadecimal notation (base 16).
 Figure 11: Three different notations in IPv4 addressing
• In binary notation, an IPv4 address is displayed as 32 bits.
To make the address more readable, one or more spaces
are usually inserted between each octet (8 bits). Each
octet is often referred to as a byte.
• To make the IPv4 address more compact and easier to
read, it is usually written in decimal form with a decimal
point (dot) separating the bytes. This format is referred
to as dotted-decimal notation. Note that because each
byte (octet) is only 8 bits, each number in the
dotted-decimal notation is between 0 and 255.
• We sometimes see an IPv4 address in hexadecimal
notation. Each hexadecimal digit is equivalent to four
bits. This means that a 32-bit address has 8 hexadecimal
digits. This notation is often used in network
programming.
• Figure above shows an IP address in the three discussed
notations.
• Example - Find the error, if any, in the following IPv4
addresses.
a. 111.56.045.78
b. 221.34.7.8.20
c. 75.45.301.14
d. 11100010.23.14.67
• Solution -
a. There must be no leading zero (045).
b. There can be no more than four numbers in an IPv4
address.
c. Each number needs to be less than or equal to 255
(301 is outside this range).
d. A mixture of binary notation and dotted-decimal
notation is not allowed.
• Hierarchy in Addressing: In any communication network
that involves delivery, such as a telephone network or a
postal network, the addressing system is hierarchical. In
a postal network, the postal address (mailing address)
includes the country, state, city, street, house number,
and the name of the mail recipient. Similarly, a telephone
number is divided into the country code, area code, local
exchange, and the connection.
• A 32-bit IPv4 address is also hierarchical, but divided only
into two parts. The first part of the address, called the
prefix, defines the network; the second part of the
address, called the suffix, defines the node.
• Figure below shows the prefix and suffix of a 32-bit IPv4
address.
• The prefix length is n bits and the suffix length is (32 − n)
bits.
 Figure: Hierarchy in
addressing

• A prefix can be fixed length or variable length.

• The network identifier in the IPv4 was first designed as a
fixed-length prefix. This scheme, which is now obsolete,
is referred to as classful addressing.
• The new scheme, which is referred to as classless
addressing, uses a variable-length network prefix.
Classful Addressing

Figure: Occupation of the address space in classful addressing

• When the Internet started, an IPv4 address was designed
with a fixed-length prefix, but to accommodate both
small and large networks, three fixed-length prefixes
were designed instead of one (n = 8, n = 16, and n = 24).
• The whole address space was divided into five classes
(class A, B, C, D, and E), as shown in above figure. This
scheme is referred to as classful addressing.
• In class A, the network length is 8 bits, but since the first
bit, which is 0, defines the class, we can have only seven
bits as the network identifier. This means there are only
27 = 128 networks in the world that can have a class A
address.
• In class B, the network length is 16 bits, but since the first
two bits, which are (10)2, define the class, we can have
only 14 bits as the network identifier. This means there
are only 214 = 16,384 networks in the world that can have
a class B address.
• All addresses that start with (110)2 belong to class C. In
class C, the network length is 24 bits, but since three bits
define the class, we can have only 21 bits as the network
identifier. This means there are 221 = 2,097,152 networks
in the world that can have a class C address.
• Class D is not divided into prefix and suffix. It is used for
multicast addresses. All addresses that start with 1110 in
binary belong to class D.
• As in Class D, Class E is not divided into prefix and suffix
and is used as reserve.
• 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 A address.
• b. The first 2 bits are 1; the third bit is 0. This is a class C
address.
• c. The first byte is 14 (between 0 and 127); the class is A.
• d. The first byte is 252 (between 240 and 255); the class
is E.
• Classes and Blocks: One problem with classful addressing
is that each class is divided into a fixed number of blocks
with each block having a fixed size as shown in table
below.
Table: Number of blocks and block size in classfulIPv4 addressing

• A block in class A address is too large for almost any

organization. This means most of the addresses in class A
were wasted and were not used.
• A block in class B is also very large, probably too large for
many of the organizations that received a class B block.
• A block in class C is probably too small for many
organizations.
• Class D addresses were designed for multicasting. Each
address in this class is used to define one group of hosts
on the Internet. The Internet authorities wrongly
predicted a need for 268,435,456 groups. This never
happened and many addresses were wasted here too.
• And lastly, the class E addresses were reserved for future
use; only a few were used, resulting in another waste of
addresses.
• 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.
• Note that 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.
• 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), a 32-bit
number made of contiguous 1s followed by contiguous
0s.
• The masks for classes A, B, and C are shown in table
below.
• The concept does not apply to classes D and E.
Table: Default masks for classful addressing
• The mask can help us to find the netid and the hostid.
• For example, the mask for a class A address has eight 1s,
which means the first 8 bits of any address in class A
define the netid; the next 24 bits define the hostid.
• The last column of table shows the mask in the form /n
where n can be 8, 16, or 24 in classful addressing. This
notation is also called slash notation or Classless
Interdomain Routing (CIDR) notation.

• Subnetting: If an organization was granted a large block

in class A or B, it could divide the addresses into several
contiguous groups and assign each group to smaller
networks (called subnets) or, in rare cases, share part of
the addresses with neighbors.
• Supernetting: In supernetting, an organization can
combine several class C blocks to create a larger range of
addresses. In other words, several networks are
combined to create a supernetwork or a supernet. An
organization can apply for a set of class C blocks instead
of just one.
• Address Depletion: The flaws in classful addressing
scheme combined with the fast growth of the Internet
led to the near depletion of the available addresses.
• Yet the number of devices on the Internet is much less
than the 232 address space. We have run out of class A
and B addresses, and a class C block is too small for most
midsize organizations.
• One solution that has alleviated the problem is the idea
of classless addressing.
Classless Addressing
• To overcome address depletion and give more
organizations access to the Internet, classless addressing
was designed and implemented.
• In this scheme, there 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.
• For example, a household may be given only two
addresses; a large organization may be given thousands
of addresses.
• An ISP, as the Internet service provider, may be given
thousands or hundreds of thousands based on the
number of customers it may serve.
• 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 (1, 2, 4, 8, ... ).
3. The first address must be evenly divisible by the number
of addresses.
• Example - Figure below shows a block of addresses, in
both binary and dotted-decimal notation, granted to a
small business that needs 16 addresses.

Figure 14: A block of 16 addresses granted to a small organization

• We can see that the restrictions are applied to this block.
The addresses are contiguous.
• The number of addresses is a power of 2 (16 = 24), and
the first address is divisible by 16.
• 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 1s and the 32 - n rightmost bits are 0s.
• 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).
• In IPv4 addressing, a block of addresses can be defined as
x.y.z.t/n in which x.y.z.t defines one of the addresses and
the /n defines the mask.
• The address and the /n notation completely define the
whole block (the first address, the last address, and the
number of addresses).
• First Address - The first address in the block can be found
by setting the 32 - n rightmost bits in the binary notation
of the address to 0s.
• 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 = 4 rightmost bits to 0, we get
11001101 00010000 00100101 00100000 or 205.16.37.32.
• This is actually the block shown in Figure.
• Last Address - The last address in the block can be found
by setting the 32 - n rightmost bits in the binary notation
of the address to 1s.
• Example - Find the last address for the block in previous
example (205.16.37.39/28).
• Solution - The binary representation of the given address
is 11001101 00010000 00100101 00100111.
• If we set 32 - 28 = 4 rightmost bits to 1, we get
11001101 00010000 00100101 00101111 or 205.16.37.47.
• This is actually the block shown in Figure.
• Number of Addresses - The number of addresses in the
block is the difference between the last and first address.
• It can easily be found using the formula 232-n.
• Example - Find the number of addresses in previous
example (205.16.37.39/28).
• Solution - The value of n is 28, which means that number
of addresses is 232- 28 = 24 or 16.
• Example - Another way to find the first address, the last
address, and the number of addresses is to represent the
mask as a 32-bit binary (or 8-digit hexadecimal) number.
This is particularly useful when we are writing a program
to find these pieces of information. In our previous
example (205.16.37.39/28) the /28 can be represented
as 11111111 11111111 11111111 11110000
(twenty-eight 1s and four 0s).
Find
a. The first address
b. The last address
c. The number of addresses
• Solution (a) - The first address can be found by ANDing
the given addresses with the mask. ANDing here is done
bit by bit. The result of ANDing 2 bits is 1 if both bits are
1s; the result is 0 otherwise.

• Solution (b) - The last address can be found by ORing the

given addresses with the complement of the mask. ORing
here is done bit by bit. The result of ORing 2 bits is 0 if
both bits are 0s; the result is 1 otherwise. The
complement of a number is found by changing each 1 to
0 and each 0 to 1.
• Solution (c) - The number of addresses can be found by
complementing the mask, interpreting it as a decimal
number, and adding 1 to it.
Dynamic Host Configuration Protocol (DHCP)
• Dynamic Host Configuration Protocol (DHCP) is an
application layer protocol used to distribute network
configuration parameters, such as IP addresses, subnet
masks, default gateways, etc. to hosts on a TCP/IP
network.
• Assigning network parameters using DHCP reduces the
amount of work of a network administrator, since there
is no need to statically configure parameters on each
device.
• DHCP employs a client-server architecture; a DHCP client
is configured to request network parameters from a
DHCP server.
• A DHCP server is configured with a pool of available IP
addresses and assigns one of them to the DHCP client.
How DHCP Works?

Figure: DHCP Process

• As you can see from the Figure above, a DHCP client goes
through the four-step process:
1. A DHCP client sends a broadcast packet
(DHCPDiscover) to discover DHCP servers on the
network.
2. The DHCP server receives the DHCPDiscover packet
and respond with a DHCPOffer packet, offering IP
addressing information to the DHCP client.
3. If there is more than one DHCP server on the network
segment and the DHCP client receives more than one
DHCPOffer packets, the client will accept the first
DHCPOffer packet. The DHCP client responds by
broadcasting a DHCPRequest packet, requesting
network parameters from the DHCP server.
4. The DHCP server approves the lease with a DHCPACK
(Acknowledgement) packet. The packet includes the
lease duration and other configuration information.
Components of DHCP
• Following are the list of components in DHCP:
• DHCP Server: DHCP server is a networked device running
the DCHP service that holds IP addresses and related
configuration information.
• This is typically a server or a router but could be anything
that acts as a host.
• DHCP client: DHCP client is the endpoint that receives
configuration information from a DHCP server.
• This can be any device like computer, laptop, IoT
endpoint or anything else that requires connectivity to
the network.
• Most of the devices are configured to receive DHCP
information by default.
• IP address pool: IP address pool is the range of addresses
that are available to DHCP clients. IP addresses are
typically handed out sequentially from lowest to the
highest.
• Subnet: Subnet is the partitioned segments of the IP
networks. Subnet is used to keep networks manageable.
• Lease: Lease is the length of time for which a DHCP client
holds the IP address information. When a lease expires,
the client has to renew it.
• DHCP relay: A host or router that listens for client
messages being broadcast on that network and then
forwards them to a configured server. The server then
sends responses back to the relay agent that passes them
along to the client.
• DHCP relay can be used to centralize DHCP servers
instead of having a server on each subnet.
Benefits of DHCP
• There are following benefits of DHCP:
• Centralized administration of IP configuration: DHCP IP
configuration information can be stored in a single location
and enables that administrator to centrally manage all IP
address configuration information.
• Dynamic host configuration: DHCP automates the host
configuration process and eliminates the need to manually
configure individual host.
• Seamless IP host configuration: The use of DHCP ensures
that DHCP clients get accurate and timely IP configuration
without user intervention.
• Flexibility and scalability: Using DHCP gives the
administrator increased flexibility, allowing the
administrator to move easily change IP configuration when
the infrastructure changes.
Network Address Translation (NAT)
• There are several situations where we need address
translation such as –
- a network which do not have sufficient public IP
addresses want to connect with the Internet,
- two networks which have same IP addresses want to
merge, or
- due to security reason a network want to hide its
internal IP structure from the external world.
• NAT (Network Address Translation) is the process which
translates IP address.
• NAT can be performed at firewall, server and router.
NAT Terminology
• Before we understand NAT in details let’s get familiar
with four basic terms used in NAT.
Term Description
Inside Local IP Before translation source IP address located
Address inside the local network.
Inside Global After translation source IP address located
IP Address outside the local network.
Outside
Before translation destination IP address located
Global IP
outside the remote network.
Address
Outside Local After translation destination IP address located
IP Address inside the remote network.
• Let’s understand these terms with an example.
• Suppose a user is browsing a website from his home
computer. The network which connects his computer
with internet is considered as a local network for him.
• Same as the network which connects the webserver
where the website is located with internet is considered
as a local network for webserver.
• The network which connects both networks on internet
is considered as a global network.
• On router the interface which is connected with local
network will be configured with inside local IP address
and the interface which is connected with global network
will be configured with inside global IP address.
• Inside and outside depend on where we are standing
right now.
• For example in above network for user router R1 is inside
and router R2 is outside.
• While for webserver router R2 is inside and router R1 is
outside.
• Basically on a NAT enabled router there are two types of
interface inside local and inside global.
• So, what about outside global and outside local?
• These terms are used to explain the NAT process
theoretically.
• Practically we never need to configure the outside local
and outside global as they sound.
• For example let’s discuss above example once again.
• On R1 we will configure inside local address (10.0.0.1)
and inside global address (100.0.0.1) which will become
outside local address (10.0.0.1) and outside global
address (100.0.0.1) for R2 respectively.
• Same way on R2 we will configure inside local address
(192.168.1.1) and inside global address (100.0.0.2) which
will become outside local address (192.168.1.1) and
outside global address (100.0.0.2) for R1 respectively.
• So practically we only configure inside local and inside
global.
• What is inside for one side is the outside for other side.
How NAT Works?
• To understand how NAT works, let’s take one more
example.
• In this example a user is accessing a web server.
• User and Webserver both are connected through the
NAT devices.
• Both user and webserver are using private IP addresses
which are not routable on the internet.
• Now let’s understand how NAT makes this
communication possible.
• User generates a data packet for web server. This packet
has source address 10.0.0.1 and destination address
100.0.0.2.
• This packet reaches at R1. Since this packet contains
private IP address in source filed which is not routable on
internet, R1 has to update the private IP address with a
routable public IP address before forwarding this packet.
• R1 checks NAT table for available public IP addresses.
• Depending on what type of NAT (Static, Dynamic or PAT)
is configured one routable public IP will be picked from
NAT table for this packet.
• In our example 100.0.0.1 is picked for this packet. Now
R1 will replace 10.0.0.1 with 100.0.0.1 in the source filed
of the packet and forward it to the R2.
• R2 receives this packet and reads the destination IP
address. R2 looks in NAT table to find out the actual IP
address of the destination.
• Since the NAT table of R2 has an entry for the address
100.0.0.2 which maps it with the address 192.168.1.1, R2
will replace the destination address 100.0.0.2 with the
address 192.168.1.1 and forward it to the web server.
• Webserver will process this packet and reply with its own
packet.
• This packet has source address 192.168.1.1 and
destination address 100.0.0.1.
• Since webserver received this packet from 100.0.0.1 so it
will reply to it instead of 10.0.0.1.
• R2 receives this packet.
• Before forwarding this packet R2 will replace the source
IP address with the mapped IP address in NAT table. In
this example 192.168.1.1 will be replaced with 100.0.0.2.
• R1 receives this packet and checks its destination
address. R1 will perform a query in NAT table to figure
out the IP address which is associated with this
destination IP address.
• Since this destination IP address 100.0.0.1 is mapped
with 10.0.0.1, R1 will replace this destination IP address
100.0.0.1 with 10.0.0.1 and forward it to the PC.
• From user’s point of view the IP address of the webserver
is 100.0.0.2. While from web server’s point of view the IP
address of the user is 100.0.0.1.
• This way both user and webserver will never know to
whom they are communicating actually.
Types of NAT
• There are three types of NAT: Static NAT, Dynamic NAT
and PAT. These types define how inside local IP address
will be mapped with inside global IP address.
• Static NAT: In this type we manually map each inside
local IP address with inside global IP address. Since this
type uses one to one mapping we need exactly same
number of IP address on both sides.
• Dynamic NAT: In this type we create a pool of inside
global IP addresses and let the NAT device to map inside
local IP address with the available outside global IP
address from the pool automatically.
• PAT: In this type a single inside global IP address is
mapped with multiple inside local IP addresses using the
source port address. This is also known as PAT (Port
Address Translation) or NAT overload.
Advantages and Disadvantages of NAT
• NAT provides following advantages:
- NAT solves IP overlapping issue.
- NAT hides internal IP structure from external world.
- NAT allows us to connect with any network without
changing IP address.
- NAT allows us to connect multiple computers with
internet through the single public IP address.
• NAT has following disadvantages:
- NAT adds additional delay in network.
- Several applications are not compatible with NAT.
- End to end IP traceability will not work with NAT.
- NAT hides actual end device.
Internet Control Message Protocol (ICMP)
• When something unexpected occurs during packet
processing at a router, the event is reported to the
sender by the ICMP (Internet Control Message Protocol).
ICMP is also used to test the Internet.
• About a dozen types of ICMP messages are defined.
• Each ICMP message type is carried encapsulated in an IP
packet.
• The most important ones are given in table.
 Table: The principal ICMP message types

Message Type Description

Destination Packet could not be delivered
unreachable
Time exceeded Time to live field hit 0
Parameter problem Invalid header field
Source quench Choke packet
Redirect Teach a router about geography
Echo Ask a machine if it is alive
Echo reply Yes, I am alive
Timestamp request Same as Echo request, but with timestamp
Timestamp reply Same as Echo reply, but with timestamp
• The DESTINATION UNREACHABLE message is used when
the subnet or a router cannot locate the destination or
when a packet with the DF (Don't Fragment) bit cannot
be delivered because a ''small-packet'' network stands in
the way.
• The TIME EXCEEDED message is sent when a packet is
dropped because its counter has reached zero.
• The PARAMETER PROBLEM message indicates that an
illegal value has been detected in a header field. This
problem indicates a bug in the sending host's IP software
or possibly in the software of a router transited.
• The SOURCE QUENCH message was formerly used to
throttle hosts that were sending too many packets.
When a host received this message, it was expected to
slow down.
• The REDIRECT message is used when a router notices
that a packet seems to be routed wrong. It is used by the
router to tell the sending host about the probable error.
• The ECHO and ECHO REPLY messages are used to see if a
given destination is reachable and alive. Upon receiving
the ECHO message, the destination is expected to send
an ECHO REPLY message back.
• The TIMESTAMP REQUEST and TIMESTAMP REPLY
messages are similar, except that the arrival time of the
message and the departure time of the reply are
recorded in the reply.
IPv6 Datagram Format
• The IPv6 datagram format is shown in Figure below.

Figure: IPv6 datagram format

• Version: The size of the Version field is 4 bits. It shows
the version of IP and is set to 6.
• Traffic Class: The size of Traffic Class field is 8 bits. It is
similar to the IPv4 Type of Service (ToS) field. The Traffic
Class field indicates the IPv6 packet’s class or priority.
• Flow Label: The size of Flow Label field is 20 bits. It
provide additional support for real-time datagram
delivery and quality of service features. The purpose of
Flow Label field is to indicate that this packet belongs to
a specific sequence of packets between a source and
destination and can be used to prioritized delivery of
packets for services like voice.
• Payload Length: The size of the Payload Length field is 16
bits. It shows the length of the IPv6 payload, including
the extension headers and the upper layer protocol data.
• Next Header: The size of the Next Header field is 8 bits. It
shows either the type of the first extension (if any
extension header is available) or the protocol in the
upper layer such as TCP, UDP, or ICMPv6.
• Hop Limit: The size of the Hop Limit field is 8 bits. It
shows the maximum number of routers the IPv6 packet
can travel. This Hop Limit field is similar to IPv4 Time to
Live (TTL) field.
• Source Address: The size of the Source Address field is
128 bits. It shows the IPv6 address of the source of the
packet.
• Destination Address: The size of the Destination Address
field is 128 bits. It shows the IPv6 address of the
destination of the packet.
• Data: The data to be transmitted in the datagram, either
an entire higher-layer message or a fragment of one.
 Difference between IPv4 and IPv6
IPv4 IPv6
IPv4 has 32-bit address length IPv6 has 128-bit address length
It Supports Manual and DHCP address It supports Auto and renumbering address
configuration configuration
In IPv4 end to end connection integrity is
In IPv6 end to end connection integrity is
Unachievable Achievable
Address space of IPv6 is quite large. it can produce
It can generate 4.29×109 address space
3.4×1038 address space
Security feature is dependent on IPSec is inbuilt security feature in the IPv6
application protocol
Address representation of IPv4 in decimal Address Representation of IPv6 is in hexadecimal
Fragmentation performed by sender and
In IPv6 fragmentation performed only by sender
forwarding routers
In IPv4 Packet flow identification is not In IPv6 packet flow identification are Available and
available uses flow label field in the header
In IPv4 checksum field is available In IPv6 checksum field is not available
In IPv4 Encryption and Authentication In IPv6 Encryption and Authentication are
facility not provided provided
IPv4 has header of 20-60 bytes. IPv6 has header of 40 bytes fixed
ROUTING ALGORITHMS
• 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.
• 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.
• 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.
Types of Routing Algorithms
• The Routing algorithm is divided into two categories:
1. Adaptive (or Dynamic) Routing algorithm
2. Non-adaptive (or Static) Routing algorithm
Adaptive (or Dynamic) Routing algorithm
• An adaptive routing algorithm is also known as dynamic
routing algorithm.
• This algorithm makes the routing decisions based on the
topology and network traffic.
• The main parameters related to this algorithm are hop
count, distance and estimated transit time.
• An adaptive routing algorithm can be classified into three
types: Centralized algorithm, Isolation algorithm, and
Distributed algorithm.
• 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.
• Isolation algorithm:
- It is an algorithm that obtains the routing information
by using local information rather than gathering
information from other nodes.
• 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 (or Static) Routing algorithm
• Non Adaptive routing algorithm is also known as a static
routing algorithm.
• When booting up the network, the routing information
stores to the routers.
• 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 and Random walks.
• 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.
The Link-State (LS) Routing Algorithm
• Link state routing is a technique in which each router
shares the knowledge of its neighborhood with every
other router in the internetwork.
• 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.
• 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.
• Let's describe some notations:
Link cost from node i to node j. If i and j nodes are not
• c(i, j):
directly linked, then c(i , j) = ∞.
• D(v): cost of the least-cost path from the source node to
destination v as of this iteration of the algorithm.
• p(v): previous node (neighbor of v) along the current least-cost
path from the source to v.
• N’: subset of nodes; v is in N’ if the least-cost path from the
source to v is definitively known.
• The global routing algorithm consists of an initialization
step followed by a loop.
• The number of times the loop is executed is equal to the
number of nodes in the network.
• Upon termination, the algorithm will have calculated the
shortest paths from the source node u to every other
node in the network.
 Figure: Abstract graph model of a computer network
Table: Running the link-state algorithm on the network in above figure
• As an example, let’s consider the network in above figure
and compute the least-cost paths from u to all possible
destinations.
• A tabular summary of the algorithm’s computation is
shown in table above, where each line in the table gives
the values of the algorithm’s variables at the end of the
iteration.
• Let’s consider the few first steps in detail.
• In the initialization step, the currently known least-cost
paths from u to its directly attached neighbors, v, x, and
w, are initialized to 2, 1, and 5, respectively. Note in
particular that the cost to w is set to 5 (even though we
will soon see that a lesser-cost path does indeed exist)
since this is the cost of the direct (one hop) link from u to
w. The costs to y and z are set to infinity because they
are not directly connected to u.
• In the first iteration, we look among those nodes not yet
added to the set N’ and find that node with the least cost
as of the end of the previous iteration.
• That node is x, with a cost of 1, and thus x is added to the
set N’. Line 12 of the LS algorithm is then performed to
update D(v) for all nodes v, yielding the results shown in
the second line (Step 1) in table.
• The cost of the path to v is unchanged. The cost of the
path to w (which was 5 at the end of the initialization)
through node x is found to have a cost of 4.
• Hence this lower-cost path is selected and w’s
predecessor along the shortest path from u is set to x.
• Similarly, the cost to y (through x) is computed to be 2,
and the table is updated accordingly.
• In the second iteration, nodes v and y are found to have
the least-cost paths (2), and we break the tie arbitrarily
and add y to the set N’ so that N’ now contains u, x, and
y.
• The cost to the remaining nodes not yet in N’, that is,
nodes v, w, and z, are updated via line 12 of the LS
algorithm, yielding the results shown in the third row in
the table.
• And so on. . . .
• When the LS algorithm terminates, we have, for each
node, its predecessor along the least-cost path from the
source node.
• For each predecessor, we also have its predecessor, and
so in this manner we can construct the entire path from
the source to all destinations.
• The forwarding table in a node, say node u, can then be
constructed from this information by storing, for each
destination, the next-hop node on the least-cost path
from u to the destination.
• Figure below shows the resulting least-cost paths and
forwarding table in u for the network in above figure.

Figure: Least cost path and forwarding table for node u

The Distance-Vector (DV) Routing Algorithm
• Distributed: It is distributed in that each node receives
information from one or more of its directly attached
neighbours, performs calculation and then distributes the
result back to its neighbours.
• Iterative: It is iterative in that its process continues until no
more information is available to be exchanged between
neighbours.
• Asynchronous: It does not require that all of its nodes
operate in the lock step with each other.
• The Distance vector algorithm is iterative, asynchronous and
distributed.
• The Distance vector algorithm is a dynamic algorithm.
• It is mainly used in ARPANET (Advanced Research Projects
Agency Network), and RIP (Routing Information Protocol).
Distance Vector(DV) Algorithm
Comparison of LS and DV Routing Algorithms
Distance Vector Routing Algorithm Link State Routing Algorithm
• It is a dynamic routing algorithm in • It is a dynamic routing algorithm in
which each router computes distance which each router shares knowledge
between itself and each possible of its neighbours with every other
destination i.e. its immediate router in the network.
neighbours.
• The router shares its knowledge • The router sends its information about
about the whole network to its its neighbours only to all the routers
neighbours and accordingly updates through flooding.
table based on its neighbours.
• Information sharing takes place only
• The sharing of information with the whenever there is a change.
neighbours takes place at regular
intervals. • It makes use of Dijkstra’s Algorithm
• It makes use of Bellman Ford for making routing tables.
Algorithm for making routing tables. • Problems – Heavy traffic due to
• Problems – Count to infinity problem flooding of packets.
which can be solved by splitting Flooding can result in infinite looping which
horizon. can be solved by using Time to live (TTL) field.
• It is prone to routing loops • No routing loops.
 The Count to Infinity problem
• The distance vector routing works perfectly
theoretically but practically it has a serious problem.
The problem is that we get a correct answer but we
get it slowly.
• In other words, it reacts quickly to good news but it
reacts too slowly to bad news.
• Let us consider a router whose best route to
destination X is large. If on the next exchange
neighbour A suddenly reports a short delay to X, the
router will switch over and start using the line to A
for sending the traffic to destination X.
• Thus, in one vector exchange, the good news is
processed.
Figure 5.4 (a)

Figure 5.4 (b)

 Broadcast Routing
• Sending a packet to all destinations simultaneously is called
broadcasting.
• Various methods have been proposed for doing it.
• One broadcasting method that requires no special
features from the network is for the source to simply
send a distinct packet to each destination.
• multi-destination routing
• Flooding
• reverse path forwarding
• Not only is the method wasteful of bandwidth and slow, but
it also requires the source to have a complete list of all
destinations.
• This method is not desirable in practice, even though it is
widely applicable.
 Multicast Routing
Sending a message to a group is called multicasting, and the
routing algorithm used is called multicast routing.
Thank you