BCS502 - COMPUTER NETWORKS Module 3 Notes

Module-3
Network Layer

It provides services to the transport layer and receives services from the
data-link layer.

Network Layer Services

Packetizing

Encapsulating the payload (data received from upper layer) into a network-
layer packet at the source and decapsulating the payload from the network-
layer packet at the destination.

The source host receives the payload from an upper-layer protocol, adds a
header that contains the source and destination addresses and some other
information that is required by the network-layer protocol.

Network layer delivers the packet to the data-link layer. The source is not
allowed to change the content of the payload unless it is too large for
delivery and needs to be fragmented.

The destination host receives the network-layer packet from its data-link
layer, decapsulates the packet, and delivers the payload to the
corresponding upper-layer protocol.

If the packet is fragmented at the source or at routers along the path, the
network layer is responsible for waiting until all fragments arrive,
reassembling them, and delivering them to the upper-layer protocol.

Routing and Forwarding

Routing

Dept. of CSE Page 1 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Routing is the process of determining the optimal path for data packets to
travel from the source to the destination across a network. There is more
than one route from the source to the destination. The network layer is
responsible for finding the best one among these possible routes.

Routing is achieved by running routing protocols like OSPF and BGP.

Forwarding

Forwarding is the process of moving packets from one interface to another

on a router based on the routing table.

When a router receives a packet from one of its attached networks, it needs
to forward the packet to another attached network (in unicast routing) or
to some attached networks (in multicast routing).

To make this decision, the router uses a piece of information in the packet
header, which can be the destination address or a label, to find the
corresponding output interface number in the forwarding table.

Forwarding Process
Error Control

The designers of the network layer in the Internet ignored this issue for the
data being carried by the network layer, reason for this decision is the fact
that the packet in the network layer may be fragmented at each router,
which makes error checking at this layer inefficient.

Dept. of CSE Page 2 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

The designers of the network layer, however, have added a checksum field
to the datagram to control any corruption in the header, but not in the
whole datagram.

The checksum may prevent any changes or corruptions in the header of the
datagram.

Internet uses an auxiliary protocol, ICMP, that provides some kind of error
control if the datagram is discarded or has some unknown information in
the header.

Flow Control

To control the flow of data, the receiver needs to send some feedback to
the sender to inform the latter that it is overwhelmed with data.

The network layer in the Internet, however, does not directly provide any
flow control.

Congestion Control

Congestion in the network layer is a situation in which too many datagrams

are present in an area of the Internet.

Congestion may occur if the number of datagrams sent by source

computers is beyond the capacity of the network or routers. In this
situation, some routers may drop some of the datagrams.

As more datagrams are dropped, the situation may become worse because,
due to the error control mechanism at the upper layers, the sender may
send duplicates of the lost packets.

To control congestion network layer uses QoS, dynamic routing, traffic

engineering, packet dropping strategies etc.

Quality of Service

As the Internet has allowed new applications such as multimedia

communication (in particular real-time communication of audio and video),

Dept. of CSE Page 3 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

the quality of service (QoS) of the communication has become more and
more important.

Network layer implements various techniques for classification,

prioritization, and management of traffic to provide QoS

Security

The network layer was designed with no security provision To provide

security for a connectionless network layer, we need to have another virtual
level that changes the connectionless service to a connection-oriented
service.

Packet Switching

Packet switching is a method of data transmission used in computer

networks where data is broken into smaller packets before being sent over
the network. Each packet is transmitted independently and can take
different routes to reach its destination.

There are two approaches in packet switching, datagram approach and

virtual circuit switching approach.

Datagram packet switching

When the network layer provides a connectionless service, each packet

traveling in the Internet is an independent entity. There is no relationship
between packets belonging to the same message.

A packet belonging to a message may be followed by a packet belonging

to the same message or to a different message. A packet may be followed
by a packet coming from the same or from a different source.

Dept. of CSE Page 4 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

A connectionless packet-switched network

Each packet is routed based on the information contained in its header:

source and destination addresses. The router routes the packet to the
destination address. The source address may be used to send an error mes
sage to the source if the packet is discarded.

Forwarding process in a router when used in a connectionless network

Virtual-Circuit Approach: Connection-Oriented Service

In this approach there is a relationship between all packets belonging to a
message. Before all datagrams in a message can be sent, a virtual
connection should be set up to define the path for the datagrams. After
connection setup, the datagrams can all follow the same path.

Dept. of CSE Page 5 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

The packets in this approach along with source and destination address
should have a flow label, a virtual circuit identifier (VCI) that defines
the virtual path the packet should follow.

A virtual-circuit packet-switched network

To create a connection-oriented service, a three-phase process is used:
setup, data transfer, and teardown.
Setup Phase
• In the setup phase, a router creates an entry for a virtual circuit.
• For example, suppose source A needs to create a virtual circuit to
destination B.
• Two auxiliary packets need to be exchanged between the sender and
the receiver the request packet and the acknowledgment packet.

Forwarding process in a router when used in a virtual-circuit network

Request packet

Dept. of CSE Page 6 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

A request packet is sent from the source to the destination. This auxiliary
packet carries the source and destination addresses. The process shown
below.

Source A sends a request packet to router R1.

Router R1 receives the request packet. It knows that a packet going from
A to B goes out through port 3. The router creates an entry in its table for
this virtual circuit, but it is only able to fill three of the four columns. The
router assigns the incoming port (1) and chooses an available incoming
label (14) and the outgoing port (3). It does not yet know the outgoing
label, which will be found during the acknowledgment step. The router then
forwards the packet through port 3 to router R3.

Router R3 receives the setup request packet. The same events happen here
as at router R1; three columns of the table are completed: in this case,
incoming port (1), incoming label (66), and outgoing port (3).

Router R4 receives the setup request packet. Again, three columns are
completed: incoming port (1), incoming label (22), and outgoing port (4).

Dept. of CSE Page 7 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Destination B receives the setup packet, and if it is ready to receive packets

from A, it assigns a label to the incoming packets that come from A, in this
case 77. This label lets the destination know that the packets come from A,
and not from other sources.

Acknowledgment Packet

A special packet, called the acknowledgment packet, completes the entries

in the switching tables. The process shown below.

Sending acknowledgments in a virtual-circuit network

The destination sends an acknowledgment to router R4. The
acknowledgment carries the global source and destination addresses so the
router knows which entry in the table is to be completed. The packet also
carries label 77, chosen by the destination as the incoming label for packets
from A. Router R4 uses this label to complete the outgoing label column for
this entry. Note that 77 is the incoming label for destination B, but the
outgoing label for router R4.

Dept. of CSE Page 8 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Router R4 sends an acknowledgment to router R3 that contains its incoming

label (22) in the table, chosen in the setup phase. Router R3 uses this as
the outgoing label in the table.

Router R3 sends an acknowledgment to router R1 that contains its incoming

label (66) in the table, chosen in the setup phase. Router R1 uses this as
the outgoing label in the table.

Finally router R1 sends an acknowledgment to source A that contains its

incoming label (14) in the table, chosen in the setup phase.

The source uses this as the outgoing label for the data packets to be sent
to destination B.

Data-Transfer Phase

After all routers have created their forwarding table for a specific virtual
circuit, then the network-layer packets belonging to one message can be
sent one after another.

The source computer uses the label 14, which it has received from router
R1 in the setup phase. Router R1 forwards the packet to router R3, but
changes the label to 66.

Router R3 forwards the packet to router R4, but changes the label to 22.

Finally, router R4 delivers the packet to its final destination with the label
77.

All the packets in the message follow the same sequence of labels, and the
packets arrive in order at the destination.

Dept. of CSE Page 9 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Flow of one packet in an established virtual circuit

Teardown Phase

• In the teardown phase, source A, after sending all packets to B, sends

a special packet called a teardown packet.

• Destination B responds with a confirmation packet. All routers delete

the corresponding entries from their tables.

IPV4 ADDRESSES

The identifier used in the IP layer of the TCP/IP protocol suite to identify
the connection of each device to the Internet is called the Internet address
or IP address.

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.

Dept. of CSE Page 10 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

IPv4 addresses 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.

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).
Notation
There are 3 notations
1. binary notation (base 2),
2. dotted-decimal notation (base 256),
3. hexadecimal notation (base 16)
In binary notation, an IPv4 address is displayed as 32 bits. 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 it is referred
to as dotted decimal notation. In hexadecimal notation 4 bits are used each
hexadecimal digit is equivalent to four bits.

Three different notations in IPv4 addressing

Hierarchy in Addressing
A 32-bit IPv4 address is divided into two parts. The first part is called prefix,
defines the network the second part of the address, called the suffix,
defines the node.

Dept. of CSE Page 11 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Hierarchy in addressing
Classful Addressing
Classful addressing is an early method of IP address allocation that divided
the IP address space into several classes based on fixed lengths.

Class A
Network length, n = 8
First bit is reserved with a value 0
With remaining 7 bits we can have 27 = 128, networks in the world that
can have class A address.

Class B
Network length, n = 16
First 2 bit is reserved with a value 10
With remaining 14 bits we can have 214 = 16,384 networks in the world
that can have a class B address.

Class C

Dept. of CSE Page 12 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Network length, n = 24
First 3 bit is reserved with a value 110
With remaining 21 bits we can have 221 = 2,097,152 networks in the world
that can have a class B address.

Class D
It is not divided into prefix and suffix
Starts with 1110, used for multicast addressing

Class E
It is not divided into prefix and suffix
Starts with 1111, reserved for future use.

Address Depletion
Classful addressing has become obsolete, since the addresses were not
distributed properly.
Consider class A, it can be assigned to only 128 organizations in the world,
but each organization needs to have a single network with 16,777,216
nodes. Since there can be only few organizations that can have around
16,777,216 nodes most of the addresses in this class are wasted.
Class B addresses were designed for midsize organizations, but many of
the addresses in this class also remained unused.
Class C addresses have a completely different flaw in design. The number
of addresses that can be used in each network (256) was so small that
most companies were not comfortable using a block in this address class.
Class E addresses were almost never used, wasting the whole class.

Subnetting and Supernetting

In subnetting, a class A or class B block is divided into several subnets.
Each subnet has a larger prefix length than the original network.
Supernetting was devised to combine several class C blocks into a larger
block.

Dept. of CSE Page 13 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Advantage of Classful Addressing

Given an address, we can easily find the class of the address, from the class
we can determine the prefix length.

Classless Addressing
In classless addressing, variable-length blocks are used that belong to no
classes. The prefix length in classless addressing is variable. The notation
used to represent classless addressing is known as slash notation or CIDR
(Classless Inter Domain Routing).

Slash notation (CIDR)

Extracting Information from an Address
If prefix length (n) is known we can find the following imformation.
1. The number of addresses in the block is found as N = 232−n.
2. To find the first address, we keep the n leftmost bits and set the (32
− n) rightmost bits all to 0s.
3. To find the last address, we keep the n leftmost bits and set the (32
− n) rightmost bits all to 1s.
Example:
A classless address is given as [Link]/27.
We can find the above three pieces of information as follows.
The number of addresses in the network is 232 − n = 25 = 32 addresses.
Address: [Link]/27 10100111 11000111 10101010 01010010
First ad.: [Link]/27 10100111 11000111 10101010 01000000

The last address can be found by keeping the first 27 bits and changing
the rest of the bits to 1s.

Address: [Link]/27 10100111 11000111 10101010 01010010

Last adr: [Link]/27 10100111 11000111 10101010 01011111

Dept. of CSE Page 14 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Address Mask
Another way to find the first and last addresses in the block is to use the
address mask. The address mask is a 32-bit number in which the n leftmost
bits are set to 1s and the rest of the bits (32 − n) are set to 0s.
1. The number of addresses in the block N = NOT (mask) + 1.
2. The first address in the block = (Any address in the block) AND (mask).
3. The last address in the block = (Any address in the block) OR [(NOT
(mask)]
Example:
A classless address is given as [Link]/27
Mask : [Link] : 11111111 11111111 11111111 11100000
Not(Mask) : 00000000 00000000 00000000 00000111
Not(Mask) + 1 : 00000000 00000000 00000000 00001000 = 32
To find first address
Lets take one address in the block as [Link]
[Link] : 101001011 11000111 10101010 01010010
Mask : 11111111 11111111 11111111 11100000
[Link] AND Mask we get
[Link] : 101001011 11000111 10101010 01000000
To find last address
[Link] : 101001011 11000111 10101010 01010010
Not Mask : 00000000 00000000 00000000 00011111
[Link]: 101001011 11000111 10101010 01011111

Network Address

Dept. of CSE Page 15 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

From the destination address we can find network address the router
consults its forwarding table to find the corresponding interface from which
the packet should be sent out.
Designing Subnets
To guarantee the proper operation of the subnetworks following rules need
to be considered.
• The number of addresses in each subnetwork should be a power of
2.
• The prefix length for each subnetwork should be found using the
following formula: nsub = 32 − log2Nsub
• The starting address in each subnetwork should be divisible by the
number of addresses in that subnetwork. This can be achieved if we
first assign addresses to larger subnetworks.
Example
An organization is granted a block of addresses with the beginning address
[Link]/24. The organization needs to have 3 subblocks of addresses
to use in its three subnets: one subblock of 10 addresses, one subblock of
60 addresses, and one subblock of 120 addresses. Design the subblocks.
Solution :
There are 232 – 24 = 256 addresses in this block. The first address is
[Link]/24; the last address is [Link]/24. To satisfy the third
requirement, we assign addresses to subblocks, starting with the largest
and ending with the smallest one.
a. The number of addresses in the largest subblock, which requires 120
addresses, is not a power of 2. We allocate 128 addresses. The subnet mask
for this subnet can be found as n1 = 32 −log2128 = 25. The first address
in this block is [Link]/25; the last address is [Link]/25.
b. The number of addresses in the second largest subblock, which requires
60 addresses, is not a power of 2 either. We allocate 64 addresses. The
subnet mask for this subnet can be found as n2 = 32 − log264 = 26. The
first address in this block is [Link]/26; the last address is
[Link]/26.

Dept. of CSE Page 16 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

c. The number of addresses in the smallest subblock, which requires 10

addresses, is not a power of 2 either. We allocate 16 addresses. The subnet
mask for this subnet can be found as n3 = 32 − log216 = 28. The first
address in this block is [Link]/28; the last address is
[Link]/28.

Address Aggregation
When blocks of addresses are combined to create a larger block, routing
can be done based on the prefix of the larger block.
ICANN (Internet Corporation for Assigned Names and Numbers) assigns a
large block of addresses to an ISP.
Each ISP in turn divides its assigned block into smaller subblocks and grants
the subblocks to its customers.

Example of address aggregation

Dept. of CSE Page 17 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Special Addresses
• This-host Address - The only address in the block [Link]/32 is called
the this-host address. It is used whenever a host needs to send an
IP datagram but it does not know its own address to use as the source
address.
• Limited-broadcast Address - The only address in the block
[Link]/32 is called the limited-broadcast address. It is
used whenever a router or a host needs to send a datagram to all
devices in a network.
• Loopback Address - The block [Link]/8 is called the loopback
address. A packet with one of the addresses in this block as the
destination address never leaves the host; it will remain in the host.
• Private Addresses - Four blocks are assigned as private addresses:
[Link]/8, [Link]/12, [Link]/16, and [Link]/16.
• Multicast Addresses - The block [Link]/4 is reserved for multicast
addresses.

Dynamic Host Configuration Protocol (DHCP)

Network Address assignment in an organization can be done automatically
using the Dynamic Host Configuration Protocol (DHCP).
DHCP is an application-layer program, using the client-server paradigm, it
actually helps TCP/IP at the network layer.
A network manager can configure DHCP to assign permanent IP addresses
to the host and routers. DHCP can also be configured to provide temporary,
on demand, IP addresses to hosts.
DHCP Message Format

Dept. of CSE Page 18 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Opcode : Operation Code, set to 1 for request and 2 for response

Htype: Hardware type (Ethernet, ….)
HLen: Length of hardware address.
Hcount: Maximum number of hops the packet can travel.
Transaction ID: An integer set by the client and repeated by server.
Time elapsed: The number of seconds since the client started to boot.
Flags: first bit if it is 0 indicate unicast if it is 1 indicate multicast. Other 15
bits are not used.
Client IP address: set to 0 if the client does not know its address.
Your IP address: The client IP address sent by the server.
Server IP address: A broadcast IP address if the client does not know it.
Gateway IP address: The address of default reouter.
Server Name: A 64 byte domain name of the server
File name : A 128 byte file name holding extra information.
Options: A 64 byte field. It can carry either additional information or some
specific vendor information. The server uses a number, called a magic
cookie, in the format of an IP address with the value of [Link]. When
the client finishes reading the message, it looks for this magic cookie. If
present, the next 60 bytes are options. An option is composed of three
fields: a 1-byte tag field, a 1-byte length field, and a variable-length value

Dept. of CSE Page 19 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

field. If the tag field is 53, the value field defines one of the 8 message
types shown in below

Option format

DHCP Operation

The joining host creates a DHCPDISCOVER message in which only the

transaction- ID field is set to a random number. Other fields are not set.

Dept. of CSE Page 20 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

This message is encapsulated in a UDP user datagram with the source port
set to 68 and the destination port set to 67. The user datagram is
encapsulated in an IP datagram with the source address set to [Link] (“this
host”) and the destination address set to [Link] (broadcast
address).
The DHCP server responds with a DHCPOFFER message in which the your
address field defines the offered IP address for the joining host and the
server address field includes the IP address of the server. The message also
includes the lease time for which the host can keep the IP address. This
message is encapsulated in a user datagram with the same port numbers,
but in the reverse order. The user datagram in turn is encapsulated in a
datagram with the server address as the source IP address, but the
destination address is a broadcast address.
The joining host receives one or more offers and selects the best of them.
The joining host then sends a DHCPREQUEST message to the server that
has given the best offer. The fields with known value are set. The message
is encapsulated in a user datagram with port numbers as the first message.
The user datagram is encapsulated in an IP datagram with the source
address set to the new client address, but the destination address still is
set to the broadcast address to let the other servers know that their offer
was not accepted.

Finally, the selected server responds with a DHCPACK message to the client
if the offered IP address is valid. If the server cannot keep its offer (for
example, if the address is offered to another host in between), the server
sends a DHCPNACK message and the client needs to repeat the process.
This message is also broadcast to let other servers know that the request
is accepted or rejected.

Well known ports (67 and 68) are used to indicate that the message is
DHCP message.
The server does not send all of the information that a client may need for
joining the network. DHCPACK contains pathname of a file in which the client

Dept. of CSE Page 21 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

can find complete information such as the address of the DNS server. The client
can then use a file transfer protocol to obtain the rest of the needed information.
DHCP uses checksum for error detection. DHCP client uses timers and a
retransmission policy if it does not receive the DHCP reply to a request. DHCP
forces the client to use a random number to set its timers to prevent traffic jam.

Transition States

• When the DHCP client first starts, it is in the INIT state (initializing state).
• The client broadcasts a discover message.
• When it receives an offer, the client goes to the SELECTING state.
• While it is there, it may receive more offers.
• After it selects an offer, it sends a request message and goes to the
REQUESTING state.
• If an ACK arrives while the client is in this state, it goes to the BOUND
state and uses the IP address.
• When the lease is 50 percent expired, the client tries to renew it by moving
to the RENEWING state.
• If the server renews the lease, the client moves to the BOUND state again.

Dept. of CSE Page 22 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

• If the lease is not renewed and the lease time is 75 percent expired, the
client moves to the REBINDING state.
• If the server agrees with the lease (ACK message arrives), the client moves
to the BOUND state and continues using the IP address; otherwise, the client
moves to the INIT state and requests another IP address.

Network Address Translation (NAT)

Assume that an ISP has granted a small range of addresses to a small business or
a household. If the business grows or the household needs a larger range, the ISP
may not be able to grant the demand because the addresses before and after the
range may have already been allocated to other networks.
A set of private addresses can be used for internal communication and a set of
global Internet addresses (at least one) for communication with the rest of the
world.
The site must have only one connection to the global Internet through a NAT-
capable router that runs NAT software.

Address Translation
• All of the outgoing packets go through the NAT router, which replaces the
source address in the packet with the global NAT address.
• All incoming packets also pass through the NAT router, which replaces the
destination address in the packet (the NAT router global address) with the
appropriate private address.
Translation Table

Dept. of CSE Page 23 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Translating the source addresses for an outgoing packet is straightforward. To

translate destination address of incoming packet will be easy if the router has a
translation table.

Using One IP Address

• In its simplest form, a translation table has only two columns, the private
address and the external address (destination address of the packet).
• When the router translates the source address of the outgoing packet, it also
makes note of the destination address— where the packet is going.
• When the response comes back from the destination, the router uses the
source address of the packet (as the external address) to find the private
address of the packet.
• In this strategy, communication must always be initiated by the private
network.

Using a Pool of IP Addresses

Dept. of CSE Page 24 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

• The use of only one global address by the NAT router allows only one
private-network host to access a given external host.
• To remove this restriction, the NAT router can use a pool of global
addresses.
• For example, instead of using only one global address ([Link]), the
NAT router can use four addresses ([Link], [Link], [Link], and
[Link]).
• In this case, four private-network hosts can communicate with the same
external host at the same time because each pair of addresses defines a separate
connection.
Using Both IP Addresses and Port Addresses
• To allow a many-to-many relationship between private-network hosts and
external server programs, we need more information in the translation table.
• For example, suppose two hosts inside a private network with addresses
[Link] and [Link] need to access the HTTP server on external host
[Link].
• If the translation table has five columns, instead of two, that include the
source and destination port addresses and the transport-layer protocol, the
ambiguity is eliminated.

The IPv4 Datagram

Dept. of CSE Page 25 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Version Number: The 4-bit version number (VER) field defines the version of
the IPv4 protocol, which, obviously, has the value of 4.
Header Length: 4-bit header length (HLEN) field defines the total length of the
datagram header in 4-byte words. The IPv4 datagram has a variable-length
header.
Service Type: It tells how the datagram should be handled.
Total Length: This 16-bit field defines the total length (header plus data) of the
IP datagram in bytes.
Length of data = total length − (HLEN) × 4
Identification, Flags, and Fragmentation Offset: These three fields are related
to the fragmentation of the IP datagram when the size of the datagram is larger
than the underlying network can carry.
Time-to-live : Due to some malfunctioning of routing protocols datagram may
be circulating in the Internet, visiting some networks over and over without
reaching the destination.

Dept. of CSE Page 26 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

This may create extra traffic in the Internet. The time-to-live (TTL) field is used
to control the maximum number of hops (routers) visited by the datagram.
When a source host sends the datagram, it stores a number in this field. This value
is approximately two times the maximum number of routers between any two
hosts.
Each router that processes the datagram decrements this number by one. If this
value, after being decremented, is zero, the router discards the datagram.
Protocol: It defines the higher-level protocol that uses the services of the IP layer.
An IP datagram can encapsulate data from several higher level protocols such as
TCP, UDP, ICMP, and IGMP.
Header checksum: It is used to detect error in the delivery of packet header.
Source and Destination Addresses: 32-bit source and destination address fields
define the IP address of the source and destination respectively.
Options: A datagram header can have up to 40 bytes of options. Options can be
used for network testing and debugging.
Payload: Payload is the packet coming from other protocols that use the service
of IP.

The IPv6 Datagram

Dept. of CSE Page 27 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Packet Format: Each packet is composed of a base header followed by the

payload. The base header occupies 40 bytes, whereas payload can be up to 65,535
bytes of information.
Version: The 4-bit version field defines the version number of the IP. For IPv6,
the value is 6.
Traffic class: The 8-bit traffic class field is used to distinguish different payloads
with different delivery requirements. It replaces the type-of-service field in IPv4.
Flow label: The flow label is a 20-bit field that is designed to provide special
handling for a particular flow of data.
Payload length: The 2-byte payload length field defines the length of the IP
datagram excluding the header
Next header: The next header is an 8-bit field defining the type of the first
extension header (if present) or the type of the data that follows the base header
in the datagram.
Hop limit: The 8-bit hop limit field serves the same purpose as the TTL field in
IPv4.
Source and destination addresses: The source address field is a 16-byte (128-
bit) Internet address that identifies the original source of the datagram. The
destination address field is a 16-byte (128-bit) Internet address that identifies the
destination of the datagram.
Payload: Compared to IPv4, the payload field in IPv6 has a different format and
meaning.

Dept. of CSE Page 28 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Payload in an IPv6 datagram

The payload in IPv6 means a combination of zero or more extension headers

options) followed by the data from other protocols (UDP, TCP, and so on).
The payload can have as many extension headers as required by the situation.
Each extension header has two mandatory fields, next header and the length,
followed by information related to the particular option.
Next header field value (code) defines the type of the next header (hop-by-hop
option, source-routing option, . . .);

IPv4 and IPv6 comparison

IPv4 IPv6
IPv4 has a 32-bit address length IPv6 has a 128-bit address length
It can generate 4.29×109 address space The address space of IPv6 is quite
large it can produce 3.4×1038 address
space
Fragmentation performed by Sender In IPv6 fragmentation is performed
and forwarding routers only by the sender
In IPv4 Packet flow identification is In IPv6 packet flow identification are
not available Available and uses the flow label field
in the header
In IPv4 checksum field is available In IPv6 checksum field is not available

Dept. of CSE Page 29 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

In IPv4 Encryption and Authentication In IPv6 Encryption and Authentication

facility not provided are provided
IPv4 has a header of 20-60 bytes. IPv6 has a header of 40 bytes fixed
IPv4’s IP addresses are divided into IPv6 does not have any classes of the
five different classes. Class A , Class IP address.
B, Class C, Class D , Class E.

Unicast routing
In unicast routing, a packet is routed, hop by hop, from its source to its destination
by the help of forwarding tables. The source host needs no forwarding table
because it delivers its packet to the default router in its local network. The
destination host needs no forwarding table either because it receives the packet
from its default router in its local network. Only the routers that glue together the
networks in the internet need forwarding tables.
An Internet as a Graph
To find the best route, an internet can be modelled as a graph. A graph in computer
science is a set of nodes and edges (lines) that connect the nodes. To model an
internet as a graph, we can think of each router as a node and each network
between a pair of routers as an edge.

Least-Cost Routing
When an internet is modelled as a weighted graph, one of the ways to interpret
the best route from the source router to the destination router is to find the least
cost between the two.

Dept. of CSE Page 30 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

The best route between A and E is A-B-E, with the cost of 6. This means that each
router needs to find the least-cost route between itself and all the other routers to
be able to route a packet using this criterion.

Least-Cost Trees

If there are N routers in an internet, there are (N − 1) least-cost paths from each
router to any other router. This means we need N × (N − 1) least-cost paths for
the whole internet. If we have only 10 routers in an internet, we need 90 least-
cost paths. A better way to see all of these paths is to combine them in a least-cost
tree. A least-cost tree is a tree with the source router as the root that spans the
whole graph (visits all other nodes) and in which the path between the root and
any other node is the shortest.

Dept. of CSE Page 31 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

ROUTING ALGORITHMS

Distance-Vector Routing
In distance-vector routing, the first thing each node creates is its own least-cost
tree with the rudimentary information it has about its immediate neighbors. The
incomplete trees are exchanged between immediate neighbors to make the trees
more and more complete and to represent the whole internet.

Bellman-Ford Equation
Distance-vector routing uses Bellman-Ford equation. This equation is used to find
the least cost (shortest distance) between a source node, x, and a destination node,
y, through some intermediary nodes (a, b, c, . . .) when the costs between the
source and the intermediary nodes and the least costs between the intermediary
nodes and the destination are given.

The following shows the general case in which Dij is the shortest distance and cij
is the cost between nodes i and j.

Dxy = min{(cxa + Day), (cxb + Dby), (cxc + Dcy), …}

In distance-vector routing, normally we want to update an existing least cost with

a least cost through an intermediary node, such as z, if the latter is shorter. In this
case, the equation becomes simpler, as shown below:

Dxy = min{Dxy, (cxz + Dzy)}

Distance Vectors
A least-cost tree is a combination of least-cost paths from the root of the tree to
all destinations. These paths are graphically glued together to form the tree.
Distance-vector routing unglues these paths and creates a distance vector, a one-
Dept. of CSE Page 32 of 51 Vemana IT
BCS502 - COMPUTER NETWORKS Module 3 Notes

dimensional array to represent the tree and the corresponding distance vector.
The name of the distance vector defines the root, the indexes define the
destinations, and the value of each cell defines the least cost from the root to the
destination. Each node in an internet, when it is booted, creates a very
rudimentary distance vector with the minimum information the node can obtain
from its neighborhood.

The first distance vector for an internet

Dept. of CSE Page 33 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Once the initial distance vector is created at a node it sends a copy of the vector
to all its immediate neighbors. After a node receives a distance vector from a
neighbor, it updates its distance vector using the Bellman-Ford equation (second
case).

Updating distance vectors

Distance-Vector Routing Algorithm

Distance_Vector_Routing() {
D[myself] = 0
for(y = 1 to N) {
if (y is a neighbor)
D[y] = c[myself][y]
else
D[y] = ∞
}
Send vector {D]1,D[2],…….,D[N]} to all neighbors

repeat(forever) {

wait(for a vector Dw from a neighbor w or any change in the link)

for(y = 1 to N) {

D[y] = min{D[y] , cost[myself][w]+ Dw [y]}

Dept. of CSE Page 34 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

if(any change in the vector)

Send vector {D]1,D[2],…….,D[N]} to all neighbors
}

Count to Infinity
If a link is broken (cost becomes infinity), every other router should be aware of
it immediately, but in distance-vector routing, this takes some time. This problem
is referred to as count to infinity problem.

Two-Node Loop : One example of count to infinity is the two-node loop problem.
To understand the problem, let us look at the scenario, a system with three nodes.
At the beginning, both nodes A and B know how to reach node X.

But suddenly, the link between A and X fails. Node A changes its table.

If B sends its forwarding table to A before receiving A’s forwarding table. Node
A updates its forwarding table.

Now A sends its new update to B. Now B thinks that something has been changed
around A and updates its forwarding table.

The cost of reaching X increases gradually until it reaches infinity.

Solutions to Count to Infinity

Dept. of CSE Page 35 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Split Horizon

In this strategy, instead of flooding the table through each interface, each node
sends only part of its table through each interface.

If node B thinks that the optimum route to reach X is via A, it does not need to
advertise this piece of information to A.

Node A keeps the value of infinity as the distance to X. Later, when node A sends
its forwarding table to B, node B also corrects its forwarding table.

The system becomes stable after the first update: both node A and node B know
that X is not reachable.

Poison Reverse

Poison Reverse involves advertising an unreachable route back to the neighbor

that originally advertised the route.

Specifically, if a router learns of a route to a destination from a neighbor, it will

advertise that the route to that destination has an infinite metric (or is
"unreachable") back to the same neighbor.

Three-Node Instability

The two-node instability can be avoided using split horizon combined with poison
reverse. However, if the instability is between three nodes, stability cannot be
guaranteed.

Link-State Routing

Link-State Routing uses the term link-state to define the characteristic of a link
(an edge) that represents a network in the internet.

Links with lower costs are preferred to links with higher costs; if the cost of a
link is infinity, it means that the link does not exist or has been broken.

Dept. of CSE Page 36 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

To create a least-cost tree with this method, each node needs to have a complete
map of

the network, which means it needs to know the state of each link.

The collection of states for all links is called the link-state database (LSDB).

There is only one LSDB for the whole internet; each node needs to have a
duplicate of it to be able to create the least-cost tree.

The LSDB can be represented as a two-dimensional array(matrix) in which the

value of each cell defines the cost of the corresponding link.

To create a least-cost tree with this method, each node needs to have a complete
map of the network, which means it needs to know the state of each link. The
collection of states for all links is called the link-state database (LSDB).

There is only one LSDB for the whole internet; each node needs to have a
duplicate of it to be able to create the least-cost tree.

An LSDB for the graph. The LSDB can be represented as a two-dimensional

array(matrix) in which the value of each cell defines the cost of the corresponding
link.

Now the question is how each node can create this LSDB that contains
information about the whole internet.

Dept. of CSE Page 37 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

This can be done by a process called flooding. Each node can send some greeting
messages to all its immediate neighbors (those nodes to which it is connected
directly) to collect two pieces of information for each neighboring node: the
identity of the node and the cost of the link.

The combination of these two pieces of information is called the LS packet (LSP);
the LSP is sent out of each interface for our internet.

When a node receives an LSP from one of its interfaces, it compares the LSP with
the copy it may already have.

If the newly arrived LSP is older than the one it has (found by checking the
sequence number), it discards the newly arrived LSP. If it is newer or the first one
received, the node discards the old LSP (if there is one) and keeps the received
one.

It then sends a copy of it out of each interface except the one from which the
packet arrived.

After receiving all new LSPs, each node creates the comprehensive LSDB.

Dept. of CSE Page 38 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

In the distance-vector routing algorithm, each router tells its neighbors what it
knows about the whole internet; in the link-state routing algorithm, each router
tells the whole internet what it knows about its neighbors.

Formation of Least-Cost Trees

To create a least-cost tree for itself, using the shared LSDB, each node needs to
run the famous Dijkstra Algorithm.

Dijkstra’s algorithm() {
Tree = {root}
for(y = 1 to N) {
if(y is the root)
D[y] = 0
else if(y is neighbor)
D[y]=c[root][y]
else
D[y]= ∞

}
}
repeat {
find a node w, with D[w] minimum among all nodes not in the Tree
Tree = Tree ∪ {w}
for(every node x, which is neighbor of w and not in the Tree) {
D[x] = min{D[x], (D[w]+c[x][w])}
}
}
In the distance-vector routing algorithm, each router tells its neighbors what it
knows about the whole internet; in the link-state routing algorithm, each router
tells the whole internet what it knows about its neighbors.

Dept. of CSE Page 39 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Path Vector Routing

Both link-state and distance-vector routing are based on the least-cost goal.
There are instances where least-cost will not always be the goal for ex. If sender
wants to prevent routing packets through some router may be because lack of
security or it may belong to a commercial rival of the sender.
In Path vector routing the best route is determined by the source using the policy
it imposes on the route.
In path-vector routing, the path from a source to all destinations is also determined
by the best spanning tree.
The best spanning tree, however, is not the least-cost tree; it is the tree determined
by the source when it imposes its own policy.
Creation of Spanning Trees
When a node is booted, it creates a path vector based on the information it can
obtain about its immediate neighbor.
A node sends greeting messages to its immediate neighbors to collect these pieces
of information.
Each node, when it receives a path vector from a neighbor, updates its path vector
using an equation similar to the Bellman-Ford, but applying its own policy instead
of looking for the least cost.
Path(x, y) = best {Path(x, y), [(x + Path(v, y)]} for all v’s in the internet.

Dept. of CSE Page 40 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Path vectors made at booting time

Updating path vectors

Path-Vector Routing Algorithm

Path_Vector_Routing() {
for(y = 1 to N) {
if (y is myself)
Path[y]= myself
else if (y is a neighbor)
Path[y]=myself+neighbor node
else

Dept. of CSE Page 41 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Path[y]=empty
}
Sendvector{Path[1],Path[2] .. Path[N] to all neighbors
repeat(forever) {
wait(for Pathw from a neighbor w)
for(y = 1 to N) {
if(Pathw includes myself)
discard the path
else
Path[y]=best{Path[y], (myself + Pathw[y]}
}
if(any change in the vector)
Sendvector{Path[1],Path[2] .. Path[N] to all neighbors
}
}
Unicast Routing Protocols
Routing Information Protocol (RIP)
It is based on distance-vector routing algorithm.
AS (Autonomous System) refers to a collection of IP networks and routers under
the control of a single entity (ISP).
RIP routers advertise the cost of reaching different networks. The cost is defined
between a router and the network in which the destination host is located.
The cost is defined as the number of hops, which means the number of networks
(subnets) a packet needs to travel through from the source router to the final
destination host.
In RIP, the maximum cost of a path can be 15, which means 16 is considered as
infinity.

Dept. of CSE Page 42 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Hop counts in RIP

Forwarding Tables
A forwarding table in RIP is a three-column table in which the first column is the
address of the destination network, the second column is the address of the next
router to which the packet should be forwarded, and the third column is the cost
(the number of hops) to reach the destination network.

Forwarding Tables
RIP implementation
RIP is implemented as a process that uses the service of UDP on the well-known
port number 520.
RIP is a routing protocol to help IP route its datagrams through the AS, the RIP
messages are encapsulated inside UDP user datagrams, which in turn are
encapsulated inside IP datagrams. In other words, RIP runs at the application
layer, but creates forwarding tables for IP at the network later.

Dept. of CSE Page 43 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

RIP has gone through two versions: RIP-1 and RIP-2. The second version is
backward compatible with the first section.
RIP Messages
RIP has two types of messages: request and response. A request message is sent
by a router that has just come up
A response (or update) message can be either solicited or unsolicited.
A solicited
response message is sent only in answer to a request message, which has
information about the destination specified in the corresponding request message.
An unsolicited response message, on the other hand, is sent periodically, every 30
seconds or when there is a change in the forwarding table.

OSPF Open Shortest Path First

Open Shortest Path First (OSPF) is also an intradomain routing protocol like RIP,
but it is based on the link-state routing protocol
Each link (network) can be assigned a weight based on the throughput, round-trip
time, reliability, and so on.
Different service types (TOSs) can have different weights as the cost.

Dept. of CSE Page 44 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

Forwarding Tables
Each OSPF router can create a forwarding table after finding the shortest-path
tree between itself and the destination using Dijkstra’s algorithm.

OSPF is implemented as a program in the network layer, using the service of the
IP for propagation.
An IP datagram that carries a message from OSPF sets the value of the protocol
field to 89. OSPF has two versions.

Dept. of CSE Page 45 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

The hello message (type 1) is used by a router to introduce itself to the neighbors
and announce all neighbors that it already knows.
The database description message (type 2) is normally sent in response to the
hello message to allow a newly joined router to acquire the full LSDB.
The link state request message (type 3) is sent by a router that needs information
about a specific LS.
The link-state update message (type 4) is the main OSPF message used for
building the LSDB.
The link-state acknowledgment message (type 5) is used to create reliability in
OSPF.

Dept. of CSE Page 46 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

BGP Border Gateway Protocol Version 4 (BGP4)

BGP is interdomain routing protocol.
BGP4 is based on the path-vector algorithm

Each autonomous system in this figure uses one of the two common intradomain
protocols, RIP or OSPF
Border router : The router at the edge of each AS which is connected to a router
at another AS
To enable each router to route a packet to any network in the internet,
Need to install a variation of BGP4, called external BGP (eBGP), on each border
router.
Need to install the second variation of BGP, called internal BGP (iBGP), on all
routers.
Border routers will be running three routing protocols (intradomain, eBGP, and
iBGP)
Other routers will be running two protocols (intradomain and iBGP).
Operation of External BGP (eBGP)

BGP is a kind of point-to-point protocol

The two routers, try to create a TCP connection using the well-known port 179.

Dept. of CSE Page 47 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

The two routers that run the BGP processes are called BGP peers or BGP
speakers.
Message number 1 is sent by router R1 and tells router R5 that N1, N2, N3, and
N4 can be reached through router R1
Router R5 can now add these pieces of
information at the end of its forwarding table.

Operation of Internal BGP (iBGP)

The iBGP protocol is similar to the eBGP protocol in that it uses the service of
TCP on the well-known port 179, but it creates a session between any possible
pair of routers inside an autonomous system.
If an AS has only one router, there cannot be an iBGP session.
If there are n routers in an autonomous system, there should be [n × (n − 1) / 2]
iBGP sessions in that autonomous system.
BGP Path Attributes
BGP allows a destination to be associated with up to seven path attributes.
Path attributes are divided into two broad categories: well-known and optional.

Dept. of CSE Page 48 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

A well-known attribute must be recognized by all routers; an optional attribute

need not be.
ORIGIN (type 1) -
This is a well-known mandatory attribute.
It defines the source of the routing information.
This attribute can be defined by one of the three values: 1, 2, and 3.
Value 1 means that the information about the path has been taken from an
intradomain protocol (RIP or OSPF).
Value 2 means that the information comes from BGP.
Value 3 means that it comes from an unknown source.
AS-PATH (type 2)
This is a well-known mandatory attribute.
It defines the list of autonomous systems through which the destination can be
reached.
AS-PATH attribute helps prevent a loop.
NEXT-HOP (type 3)
This is a well-known mandatory attribute.
It defines the next router to which the data packet should be forwarded.
It helps to inject path information collected through the operations of eBGP and
iBGP into the intradomain routing protocols such as RIP or OSPF.
MULT-EXIT-DISC (type 4)
The multiple-exit discriminator is an optional intransitive attribute.
If a router has multiple paths to the destination with different values related to
these attributes, the one with the lowest value is selected.
LOCAL-PREF (type 5)
The local preference attribute is a well-known discretionary (optional) attribute.
It is normally set by the administrator, based on the organization policy.
The routes the administrator prefers are given a higher local preference value.

Dept. of CSE Page 49 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

For example, in an internet with five ASs, the administrator of AS1 can set the
local preference value of 400 to the path AS1 → AS2 →AS5, the value of 300
to AS1 → AS3 → AS5, and the value of 50 to AS1 → AS4 → AS5.
ATOMIC-AGGREGATE (type 6).
It is an optional attribute.
The destination prefix as not aggregate; it only defines a single destination
network
AGGREGATOR (type 7)
This is an optional transitive attribute
It emphasizes that the destination prefix is an aggregate.

BGP Route Selection

BGP Messages
BGP uses four types of messages for communication between the BGP speakers
across the ASs and inside an AS
Open Message : To create a neighborhood relationship, a router running BGP
opens a TCP connection with a neighbor and sends an open message.
Update Message :

Dept. of CSE Page 50 of 51 Vemana IT

BCS502 - COMPUTER NETWORKS Module 3 Notes

The update message is the heart of the BGP protocol.

It is used by a router to withdraw destinations that have been advertised
previously, and to announce a route to a new destination.
Keepalive Message : The BGP peers that are running, exchange keepalive
messages regularly.
Notification : A notification message is sent by a router whenever an error
condition is detected or a router wants to close the session.
Multicast Link State (MOSPF)
Multicast Open Shortest Path First (MOSPF) is the extension of the Open
Shortest Path First (OSPF) protocol,
A router goes through the following steps to forward a multicast packet received
from source S and to be sent to destination G (a group of recipients):
The router uses the Dijkstra algorithm to create a shortest-path tree with S as the
root and all destinations in the internet as the leaves.
The root of the tree is the source of the packet defined in the source address of
the packet not the router as in unicast routing. The router creates a shortest-path
subtree with itself as the root of the subtree.
The shortest-path subtree is actually a broadcast subtree with the router as the
root and all networks as the leaves.
The router uses some strategy to prune the broadcast tree and to change it to a
multicast tree
The router can now forward the received packet out of only those interfaces that
correspond to the branches of the multicast tree.

Dept. of CSE Page 51 of 51 Vemana IT