Module-3, Network Layer, Computer Networks

MODULE-3
NETWORK LAYER

NETWORK-LAYER SERVICES:

The Network Layer is the third layer in the OSI model of computer networks. Its main function is to transfer
network packets from the source to the destination.

Figure 18.1 shows the communication between Alice and Bob at the network layer.

The services which are offered by the network layer protocol are as follows:

i. Packetizing
ii. Routing and Forwarding
iii. Error Control
iv. Flow Control
v. Congestion Control

i. Packetizing:

The first duty of the network layer is definitely packetizing: encapsulating the payload (data received from
upper layer) in a network-layer packet at the source and decapsulating the payload from the network-layer
packet at the destination. In other words, one duty of the network layer is to carry a payload from the source
to the destination without changing it or using it.

1|Page
Module-3, Network Layer, Computer Networks

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

The routers in the path are not allowed to decapsulate the packets they received unless the packets need to
be fragmented. The routers are not allowed to change source and destination addresses either.

ii. Routing and Forwarding:

Routing:

The network layer is responsible for routing the packet from its source to the destination.

A physical network is a combination of networks and routers that connect them. This means that 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. The network layer
needs to have some specific strategies for defining the best route.

There are a number of routing protocols that are used in this process and they should be run to help the
routers coordinate with each other and help in establishing communication throughout the network.

Forwarding:

Forwarding is simply defined as the action applied by each router when a packet arrives at one of its
interfaces.

When a router receives a packet from one of its attached networks, it needs to forward the packet to another
attached network (unicast routing) or to some attached networks (in the case of 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.

2|Page
Module-3, Network Layer, Computer Networks

iii. Error Control:

Although it can be implemented in the network layer, it is usually not preferred because the data packet in
a network layer may be fragmented at each router, which makes error-checking inefficient in the network
layer. The designers of the network layer, however, have added a checksum field to the datagram to control
any corruption in the header.

iv. Flow Control:

It regulates the amount of data a source can send without overloading the receiver. If the source produces
data at a very faster rate than the receiver can consume it, the receiver will be overloaded with data. To
control the flow of data, the receiver should send feedback to the sender to inform the latter that it is
overloaded with data.

There is a lack of flow control in the design of the network layer. It does not directly provide any flow
control. The datagrams are sent by the sender when they are ready, without any attention to the readiness
of the receiver.

v. Congestion Control:

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. However, as more
datagrams are dropped, the situation may become worse.

If the congestion continues, sometimes a situation may reach a point where the system collapses and no
datagrams are delivered.

Although congestion control is indirectly implemented in the network layer, still there is a lack of
congestion control in the network layer.

PACKET SWITCHING:

A kind of switching occurs at the network layer. A router, in fact, is a switch that creates a connection
between an input port and an output port (or a set of output ports). Although in data communication
switching techniques are divided into two broad categories, circuit switching and packet switching, only
packet switching is used at the network layer because the unit of data at this layer is a packet.

Packet Switching in computer networks is a method of transferring data to a network in the form of packets.

At the network layer, a message from the upper layer is divided into manageable packets and each packet
is sent through the network.

The source of the message sends the packets one by one; the destination of the message receives the packets
one by one. The destination waits for all packets belonging to the same message to arrive before delivering
the message to the upper layer. The connecting devices in a packet-switched network still need to decide
how to route the packets to the final destination.

3|Page
Module-3, Network Layer, Computer Networks

Today, a packet-switched network can use two different approaches to route the packets:

i. The datagram approach

ii. The virtual circuit approach.

i. Datagram Approach: Connectionless Service

In this approach, the packets in a message may or may not travel the same path to their destination. Figure
18.3 shows the idea.

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. The switches
in this type of network are called routers. 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.

It has no connection setup and teardown phase, like Virtual Circuits. Packet delivery is not guaranteed in
connectionless packet switching.

Each packet is routed based on the information contained in its header: source and destination addresses.
The destination address defines where it should go; the source address defines where it comes from. The
router in this case routes the packet based only on the destination address. The source address may be used
to send an error message to the source if the packet is discarded.

Figure 18.4 shows the forwarding process in a router in this case. We have used symbolic addresses such
as A and B.

4|Page
Module-3, Network Layer, Computer Networks

ii. Virtual-Circuit Approach: Connection-Oriented Service

In a connection-oriented service (also called virtual-circuit 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.

In this type of service, not only must the packet contain the source and destination addresses, it must also
contain a flow label, a virtual circuit identifier that defines the virtual path the packet should follow.

Figure 18.5 shows the concept of connection-oriented service.

Each packet is forwarded based on the label in the packet. The packet has a label when it reaches the router.
Figure 18.6 shows the idea. In this case, the forwarding decision is based on the value of the label, or virtual
circuit identifier.

A source and destination need to go through three phases in a virtual-circuit network:

a) Setup phase
b) Data Transfer phase
c) Teardown phase

5|Page
Module-3, Network Layer, Computer Networks

a. 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 B. Two steps are required: the setup request and the acknowledgment.

Setup Request packet: A setup request packet is sent from the source to the destination. This auxiliary
packet carries the source and destination addresses. Figure 18.7 shows the process.

Acknowledgment: A special frame, called the acknowledgment frame, completes the entries in the
switching tables and the receiver will send the acknowledgement frame to sender. Figure 18.8 shows the
process.

b. Data Transfer Phase:

The second phase is called the 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. In Figure 18.9, we show the flow of a single packet.

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,

6|Page
Module-3, Network Layer, Computer Networks

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.

c. Teardown Phase:

In this phase, source A, after sending all frames to B, sends a special frame called a teardown request.
Destination B responds with a teardown confirmation frame. All switches delete the corresponding entry
from their tables.

In the teardown phase, the source and destination inform the switches to delete the corresponding entry.

IPV4 ADDRESSES:

An IPv4 address (Internet Protocol version 4 address) is a numerical label used to identify devices on a
network. 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.

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.

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.

IPv4 uses 32-bit addresses, which means that the address space is 2^32 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.

7|Page
Module-3, Network Layer, Computer Networks

Notation:

There are three common notations to show an IPv4 address:

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

Figure 18.16 shows an IP address in the three discussed notations.

Hierarchy in Addressing:

A 32-bit IPv4 address is 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 (connection
of a device to the Internet). Figure 18.17 shows the prefix and suffix of a 32-bit IPv4 address.

8|Page
Module-3, Network Layer, Computer Networks

CLASSFUL ADDRESSING:

The whole address space was divided into five classes (class A, B, C, D, and E), as shown in Figure 18.18.
This scheme is referred to as 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).

i. class A: Used for large networks. 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
2^7 = 128 networks in the world that can have a class A address.

ii. class B: Used for medium-sized networks; 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 2^14 = 16,384 networks in the world that can have a class B address.

iii. Class C: Used for small networks. All addresses that start with 110 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 2^21 = 2,097,152 networks in the world that can have a
class C address.

iv. Class D: It is not divided into prefix and suffix. It is used for multicast addresses. First four bits are
1110.

v. Class E: All addresses that start with 1111 in binary belong to class E. Class E is not divided into
prefix and suffix and is used as reserved for future use.

Advantage of Classful Addressing:

Although classful addressing had several problems and became obsolete, it had one advantage: Given an
address, we can easily find the class of the address and, since the prefix length for each class is fixed, we
can find the prefix length immediately.

9|Page
Module-3, Network Layer, Computer Networks

Address Depletion:

The reason that classful addressing has become obsolete is address depletion i.e. Host addresses are not
used properly.

To understand the problem, let us think about class A. This class can be assigned to only 128 organizations
in the world, but each organization needs to have a single network (seen by the rest of the world) with
16,777,216 nodes (computers in this single network). Since there may be only a few organizations that are
this large, most of the addresses in this class were wasted (unused).

Class B addresses were designed for midsize organizations, but many of the addresses in this class also
remained unused.

Subnetting and Supernetting:

To alleviate address depletion, two strategies were proposed and, to some extent, implemented: subnetting
and supernetting.

 Subnetting divides an IP network into smaller networks, which can be helpful in managing IP
addresses more efficiently within large organizations.

 Supernetting was devised to combine several class C blocks into a larger block to be attractive to
organizations that need more than the 256 addresses available in a class C block.

CLASSLESS ADDRESSING:

Classless IPv4 addressing, also known as Classless Inter-Domain Routing (CIDR), is a method for
allocating IP addresses more efficiently than traditional IP address classes (Class A, B, and C). CIDR was
introduced in 1993 to replace the original class-based system and help prevent IPv4 address exhaustion by
offering more flexibility in assigning IP addresses.

In classless addressing, the whole address space is divided into variable length blocks. The prefix in an
address defines the block (network); the suffix defines the node (device). Theoretically, we can have a block
of 2^0, 2^1, 2^2, . . . , 2^32 addresses. One of the restrictions is that the number of addresses in a block
needs to be a power of 2. An organization can be granted one block of addresses. Figure 18.19 shows the
division of the whole address space into nonoverlapping blocks.

10 | P a g e
Module-3, Network Layer, Computer Networks

Prefix Length: Slash Notation

The first question that we need to answer in classless addressing is how to find the prefix length if an address
is given. Since the prefix length is not inherent in the address, we need to separately give the length of the
prefix. In this case, the prefix length, n, is added to the address, separated by a slash. The notation is
informally referred to as slash notation and formally as classless interdomain routing or CIDR (pronounced
cider) strategy. An address in classless addressing can then be represented as shown in Figure 18.20.

Extracting Information from an Address:

Given any address in the block, we normally like to know three pieces of information about the block to
which the address belongs: the number of addresses, the first address in the block, and the last address.

Example 18.1

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 2^(32 − n) = 2^5 = 32 addresses.

Dynamic Host Configuration Protocol (DHCP):

We have seen that a large organization or an ISP can receive a block of addresses directly from ICANN
and a small organization can receive a block of addresses from an ISP. After a block of addresses are
assigned to an organization, the network administration can manually assign addresses to the individual
hosts or routers. However, 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, that actually helps TCP/IP at the network layer.

11 | P a g e
Module-3, Network Layer, Computer Networks

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. The second capability can
provide a temporary IP address to a traveller to connect her laptop to the Internet while she is staying in the
hotel. It also allows an ISP with 1000 granted addresses to provide services to 4000 households, assuming
not more than one-forth of customers use the Internet at the same time.

In addition to its IP address, a computer also needs to know the network prefix (or address mask). Most
computers also need two other pieces of information, such as the address of a default router to be able to
communicate with other networks and the address of a name server to be able to use names instead of
addresses.

In other words, four pieces of information are normally needed: the computer address, the prefix, the
address of a router, and the IP address of a name server. DHCP can be used to provide these pieces of
information to the host.

DHCP Message Format:

DHCP is a client-server protocol in which the client sends a request message and the server returns a
response message. Before we discuss the operation of DHCP, let us show the general format of the DHCP
message in Figure 18.25. Most of the fields are explained in the figure, but we need to discuss the option
field, which plays a very important role in DHCP. The 64-byte option field has a dual purpose. It can carry
either additional information or some specific vendor information.

12 | P a g e
Module-3, Network Layer, Computer Networks

IPV4 DATAGRAM:

IPv4 defines the format of a packet in which the data coming from the upper layer or other protocols are
encapsulated. Packets used by the IP are called datagrams. Figure 19.2 shows the IPv4 datagram format. A
datagram is a variable-length packet consisting of two parts: header and payload (data). The header is 20 to
60 bytes in length and contains information essential to routing and delivery.

A brief description of each field is in order.

 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: The 4-bit header length (HLEN) field defines the total length of the datagram
header in 4-byte words.

 Service Type: In the original design of the IP header, this field was referred to as type of service
(TOS), which defined how the datagram should be handled. Used to specify the priority and quality
of service for the packet.

 Total Length. This 16-bit field indicates the total size of the datagram, including header and data,
in bytes. Maximum size is 65,535 bytes.

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

13 | P a g e
Module-3, Network Layer, Computer Networks

 The time-to-live (TTL): This 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.

 Protocol: In TCP/IP, the data section of a packet, called the payload, carries the whole packet from
another protocol. Specifies the protocol used by the data.

 Header checksum: The datagram header is added by IP, and its error-checking is the responsibility
of IP. Errors in the IP header can be a disaster. IP adds a header checksum field to check the header,
but not the payload. IP puts the burden of error checking of the payload on the protocol that owns
the payload, such as UDP or TCP.

 Source and Destination Addresses: These 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. Optional field for special control settings, such as for security, route
recording, etc.

 Payload: Payload, or data, is the main reason for creating a datagram. Payload is the packet coming
from other protocols that use the service of IP. Payload is the content of the package; the header is
only the information written on the package. The payload size is calculated by subtracting the
header length from the total length of the datagram.

14 | P a g e
Module-3, Network Layer, Computer Networks

IPV6 DATAGRAM:

Packet Format:

The IPv6 packet is shown in Figure 22.6. 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.

The description of fields:

i. Version. The 4-bit version field defines the version number of the IP. For IPv6, the value is 6.

ii. 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. It is used for prioritizing packets.

iii. Flow label: The flow label is a 20-bit field that is designed to provide special handling for a particular
flow of data. Used to label packets of a specific flow for quality of service (QoS) management.

iv. Payload length: The 2-byte payload length field defines the length of the IP datagram excluding the
header. It indicates size of the payload in bytes.

v. 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. This field is similar to the protocol field
in IPv4.

vi. Hop limit: The 8-bit hop limit field serves the same purpose as the TTL field in IPv4.

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

viii. Payload:

Compared to IPv4, the payload field in IPv6 has a different format and meaning, as shown in Figure 22.7.

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

15 | P a g e
Module-3, Network Layer, Computer Networks

In IPv6, options, which are part of the header in IPv4, are designed as extension headers. 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.

Note that each next header field value (code) defines the type of the next header (hop-by-hop option, source
routing option, . . .); the last next header field defines the protocol (UDP, TCP, . . .) that is carried by the
datagram.

ix. Extension Header:

An IPv6 packet is made of a base header and some extension headers. The length of the base header is fixed
at 40 bytes. However, to give more functionality to the IP datagram, the base header can be followed by up
to six extension headers. Many of these headers are options in IPv4.

Six types of extension headers have been defined. These are hop-by-hop option, source routing,
fragmentation, authentication, encrypted security payload, and destination option (see Figure 22.8).

 The hop-by-hop option is used when the source needs to pass information to all routers visited by
the datagram.
 The destination option is used when the source needs to pass information to the destination only
 The source route option is called the source route extension header
 The concept of fragmentation in IPv6 is the same as that in IPv4.
 The authentication extension header has a dual purpose: it validates the message sender and ensures
the integrity of data.
 The encrypted security payload (ESP) is an extension that provides confidentiality and guards
against eavesdropping.

16 | P a g e
Module-3, Network Layer, Computer Networks

UNICAST ROUTING:

In an internet, the goal of the network layer is to deliver a datagram from its source to its destination or
destinations. If a datagram is destined for only one destination (one-to-one delivery), we have unicast
routing.

General Idea:

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. This means that only the routers that glue together the networks in the
internet need forwarding tables.

With the above explanation, routing a packet from its source to its destination means routing the packet
from a source router (the default router of the source host) to a destination router (the router connected to
the destination network).

In other words, there are several routes that a packet can travel from the source to the destination; what
must be determined is which route the packet should take.

An Internet as a Graph:

To find the best route, an internet can be modeled 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. An internet is, in fact, modeled as a weighted
graph, in which each edge is associated with a cost. Figure 20.1 shows how an internet can be modeled as
a graph.

Least-Cost Routing:

When an internet is modeled 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. In other words, the source router
chooses a route to the destination router in such a way that the total cost for the route is the least cost among
all possible routes. In Figure 20.1, 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 criteria.

17 | P a g e
Module-3, Network Layer, Computer Networks

Least-Cost Trees:

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. In this way, we can have only
one shortest-path tree for each node. Figure 20.2 shows the seven least-cost trees for the internet in Figure
20.1.

UNICAST ROUTING ALGORITHMS:

There are three types of unicast routing algorithms: DVR, LSR and PVR

DISTANCE-VECTOR ROUTING:

The distance-vector (DV) routing is used to find the best route. 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.

We can say that in distance-vector routing, a router continuously tells all of its neighbors what it knows
about the whole internet (although the knowledge can be incomplete).

Bellman-Ford Equation:

The heart of distance-vector routing is the famous 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.

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:

18 | P a g e
Module-3, Network Layer, Computer Networks

Figure 20.3 shows the idea graphically for both cases

We can say that the Bellman-Ford equation enables us to build a new least-cost path from previously
established least-cost paths. In Figure 20.3, we can think of (a→y), (b→y), and (c→y) as previously
established least-cost paths and (x→y) as the new least-cost path. We can even think of this equation as the
builder of a new least-cost tree from previously established least-cost trees if we use the equation repeatedly.
In other words, the use of this equation in distance-vector routing is a witness that this method also uses
least-cost trees, but this use may be in the background.

Distance Vectors:

The concept of a distance vector is the rationale for the name distance-vector routing. 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-dimensional array to represent the tree. Figure 20.4 shows the tree for node A in the internet in Figure
20.1 and the corresponding distance vector.

19 | P a g e
Module-3, Network Layer, Computer Networks

Figure 20.5 shows all distance vectors for our internet.

The nodes in the internet need to help each other by exchanging information. After each node has created
its vector, 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).

We show the whole vector instead of seven equations for each update in Figure 20.6. The figure shows
two asynchronous events, happening one after another with some time in between.

In the first event, node A has sent its vector to node B. Node B updates its vector using the cost C(BA) =
2. In the second event, node E has sent its vector to node B. Node B updates its vector using the cost C(EA)
= 4.

After the first event, node B has one improvement in its vector: its least cost to node D has changed from
infinity to 5 (via node A). After the second event, node B has one more improvement in its vector; its least
cost to node F has changed from infinity to 6 (via node E). We hope that we have convinced the reader that
exchanging vectors eventually stabilizes the system and allows all nodes to find the ultimate least cost
between themselves and any other node. We need to remember that after updating a node, it immediately
sends its updated vector to all neighbors. Even if its neighbors have received the previous vector, the
updated one may help more.

20 | P a g e
Module-3, Network Layer, Computer Networks

Distance-Vector Routing Algorithm:

Now we can give a simplified pseudocode for the distance-vector routing algorithm, as shown in Table
20.1. The algorithm is run by its node independently and asynchronously.

Lines 4 to 11 initialize the vector for the node. Lines 14 to 23 show how the vector can be updated after
receiving a vector from the immediate neighbor. The for loop in lines 17 to 20 allows all entries (cells) in
the vector to be updated after receiving a new vector. Note that the node sends its vector in line 12, after
being initialized, and in line 22, after it is updated.

21 | P a g e
Module-3, Network Layer, Computer Networks

LINK-STATE ROUTING:

A routing algorithm for creating least-cost trees and forwarding tables is link-state (LS) routing. This
method uses the term link-state to define the characteristic of a link (an edge) that represents a network in
the internet. In this algorithm the cost associated with an edge defines the state of the link. Links with lower
costs are preferred to links with higher costs

Link-State Database (LSDB):

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. Figure 20.8 shows an example of 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.

Reliable 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, as shown in Figure 20.9. 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 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 as shown in Figure 20.9. This
LSDB is the same for each node and shows the whole map of the internet. In other words, a node can make
the whole map if it needs to, using this LSDB.

22 | P a g e
Module-3, Network Layer, Computer Networks

We can compare the link-state routing algorithm with the distance-vector routing algorithm. 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. This iterative algorithm uses the following steps:

1. The node chooses itself as the root of the tree, creating a tree with a single node, and sets the total cost
of each node based on the information in the LSDB.

2. The node selects one node, among all nodes not in the tree, which is closest to the root, and adds this to
the tree. After this node is added to the tree, the cost of all other nodes not in the tree needs to be updated
because the paths may have been changed.

3. The node repeats step 2 until all nodes are added to the tree

Table 20.2 shows a simplified version of Dijkstra’s algorithm. In this table, Lines 4 to 13 implement step
1 in the algorithm. Lines 16 to 23 implement step 2 in the algorithm. Step 2 is repeated until all nodes are
added to the tree.

23 | P a g e
Module-3, Network Layer, Computer Networks

24 | P a g e
Module-3, Network Layer, Computer Networks

PATH-VECTOR ROUTING:

Both link-state and distance-vector routing are based on the least-cost goal. However, there are instances
where this goal is not the priority. For example, assume that there are some routers in the internet that a
sender wants to prevent its packets from going through because a router that does not provide enough
security. The least-cost goal, applied by LS or DV routing, does not allow a sender to apply specific policies
to the route a packet may take.

Path-vector routing does not have the drawbacks of LS or DV routing because it is not based on least-cost
routing. The best route is determined by the source using the policy it imposes on the route. In other words,
the source can control the path. Although path-vector routing is not actually used in an internet, and is
mostly designed to route a packet between ISPs.

Spanning Trees:

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. If there is more than one route to a destination, the source can choose the route
that meets its policy best. A source may apply several policies at the same time. One of the common policies
uses the minimum number of nodes to be visited (something similar to least-cost). Another common policy
is to avoid some nodes as the middle node in a route.

Figure 20.11 shows a small internet with only five nodes. Each source has created its own spanning tree
that meets its policy. The policy imposed by all sources is to use the minimum number of nodes to reach a
destination. The spanning tree selected by A and E is such that the communication does not pass through
D as a middle node. Similarly, the spanning tree selected by B is such that the communication does not pass
through C as a middle node.

Creation of Spanning Trees:

The spanning trees are made, gradually and asynchronously, by each node. 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. Figure 20.12 shows all of these
path vectors for our internet in Figure 20.11. Note, however, that we do not mean that all of these tables are

25 | P a g e
Module-3, Network Layer, Computer Networks

created simultaneously; they are created when each node is booted. The figure also shows how these path
vectors are sent to immediate neighbors after they have been created (arrows).

Each node, after the creation of the initial path vector, sends it to all its immediate neighbors. 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. We can define this equation
as

Figure 20.13 shows the path vector of node C after two events. In the first event, node C receives a copy of
B’s vector, which improves its vector: now it knows how to reach node A. In the second event, node C
receives a copy of D’s vector, which does not change its vector.

26 | P a g e
Module-3, Network Layer, Computer Networks

Path-vector algorithm for a node:

Lines 4 to 12 show the initialization for the node. Lines 17 to 24 show how the node updates its vector after
receiving a vector from the neighbor. The update process is repeated forever.

27 | P a g e
Module-3, Network Layer, Computer Networks

UNICAST ROUTING PROTOCOLS:

In the previous section, we discussed unicast routing algorithms; in this section, we discuss unicast routing
protocols used in the Internet.

The three common protocols used in the Internet:

i. Routing Information Protocol (RIP), based on the distance-vector algorithm,

i. ROUTING INFORMATION PROTOCOL (RIP):

RIP stands for Routing Information Protocol. RIP is an intra-domain routing protocol used within an
autonomous system. Here, intra-domain means routing the packets in a defined domain.

Hop Count:

The Routing Information Protocol is a distance vector routing protocol that helps routers determine the best
path to transfer data packets across the network. RIP works on the Network layer of the OSI model. It uses
hop count as its cost metric for determining the best path.

The hop count is the number of networks required to reach the destination.

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. Note that the network in which the
source host is connected is not counted in this calculation because the source host does not use a forwarding
table; the packet is delivered to the default router. Figure 20.15 shows the concept of hop count advertised
by three routers from a source host to a destination host.

In RIP, the maximum cost of a path can be 15, which means 16 is considered as infinity (no connection).
For this reason, RIP can be used only in autonomous systems in which the diameter of the AS is not more
than 15 hops.

28 | P a g e
Module-3, Network Layer, Computer Networks

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. Figure 20.16 shows the
three forwarding tables for the routers in Figure 20.15.

RIP Implementation:

RIP is implemented as a process that uses the service of UDP on the well-known port number 520. In BSD,
RIP is a daemon process (a process running in the background), named routed (abbreviation for route
daemon and pronounced route-dee). This means that, although 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.

RIP has gone through two versions: RIP-1 and RIP-2. The second version is backward compatible with the
first section; it allows the use of more information in the RIP messages that were set to 0 in the first version.
We discuss only RIP-2 in this section.

RIP Messages:

Two RIP processes, a client and a server, like any other processes, need to exchange messages. RIP-2
defines the format of the message, as shown in Figure 20.17. Part of the message, which we call entry, can
be repeated as needed in a message. Each entry carries the information related to one line in the forwarding
table of the router that sends the message.

Now, we look at the structure of the RIP message format. The message format is used to share information
among different routers. The RIP contains the following fields in a message:

29 | P a g e
Module-3, Network Layer, Computer Networks

RIP has two types of messages: request and response.

 A request message is sent by a router that has just come up or by a router that has some time-out
entries. A request message can ask about specific entries or all entries.
 A response (or update) message can be either solicited or unsolicited.
A solicited response message is sent only in answer to a request message. It contains 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.

RIP Algorithm:

RIP implements the same algorithm as the distance-vector routing algorithm we discussed in the previous
section. However, some changes need to be made to the algorithm to enable a router to update its forwarding
table:

❑ Instead of sending only distance vectors, a router needs to send the whole contents of its forwarding table
in a response message.

❑ The receiver adds one hop to each cost and changes the next router field to the address of the sending
router. We call each route in the modified forwarding table the received route and each route in the old
forwarding table the old route. The received router selects the old routes as the new ones except in the
following three cases:

1. If the received route does not exist in the old forwarding table, it should be added to the route.

2. If the cost of the received route is lower than the cost of the old one, the received route should be selected
as the new one.

3. If the cost of the received route is higher than the cost of the old one, but the value of the next router is
the same in both routes, the received route should be selected as the new one. This is the case where the
route was actually advertised by the same router in the past, but now the situation has been changed. For
example, suppose a neighbor has previously advertised a route to a destination with cost 3, but now there
is no path between this neighbor and that destination. The neighbor advertises this destination with cost
value infinity (16 in RIP).

❑ The new forwarding table needs to be sorted according to the destination route (mostly using the longest
prefix first).

30 | P a g e
Module-3, Network Layer, Computer Networks

ii. OPEN SHORTEST PATH FIRST (OSPF):

Open Shortest Path First (OSPF) is also an intradomain routing protocol like RIP, but it is based on the
link-state routing protocol.

Metric:

In OSPF, like RIP, the cost of reaching a destination from the host is calculated from the source router to
the destination network. However, each link (network) can be assigned a weight based on the throughput,
round-trip time, reliability, and so on. An administration can also decide to use the hop count as the cost.
Figure 20.19 shows the idea of the cost from a router to the destination host network.

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.

Figure 20.20 shows the forwarding tables for the simple AS in Figure 20.19. Comparing the forwarding
tables for the OSPF and RIP in the same AS, we find that the only difference is the cost values. In other
words, if we use the hop count for OSPF, the tables will be exactly the same.

31 | P a g e
Module-3, Network Layer, Computer Networks

Areas:

Compared with RIP, which is normally used in small ASs, OSPF was designed to be able to handle routing
in a small or large autonomous system.

However, the formation of shortest-path trees in OSPF requires that all routers flood the whole AS with
their LSPs to create the global LSDB. Although this may not create a problem in a small AS, it may have
created a huge volume of traffic in a large AS. To prevent this, the AS needs to be divided into small
sections called areas. Each area acts as a small independent domain for flooding LSPs.

However, each router in an area needs to know the information about the link states not only in its area but
also in other areas. For this reason, one of the areas in the AS is designated as the backbone area, responsible
for gluing the areas together. The routers in the backbone area are responsible for passing the information
collected by each area to all other areas. In this way, a router in an area can receive all LSPs generated in
other areas.

OSPF Messages:

OSPF is a very complex protocol; it uses five different types of messages. In Figure 20.23, we first show
the format of the OSPF common header (which is used in all messages) and the link-state general header
(which is used in some messages). We then give the outlines of five message types used in OSPF.

 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 linkstate 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; each router
that receives a link-state update message needs to acknowledge it.

32 | P a g e
Module-3, Network Layer, Computer Networks

33 | P a g e
Module-3, Network Layer, Computer Networks

iii. BORDER GATEWAY PROTOCOL VERSION 4 (BGP4):

The Border Gateway Protocol version 4 (BGP4) is the only interdomain routing protocol used in the Internet
today. BGP4 is based on the path-vector algorithm.

Introduction:

BGP, and in particular BGP4, is a complex protocol. Figure 20.24 shows an example of an internet with
four autonomous systems. AS2, AS3, and AS4 are stub autonomous systems; AS1 is a transient one. In our
example, data exchange between AS2, AS3, and AS4 should pass through AS1.

Each autonomous system in this figure uses one of the two common intradomain protocols, RIP or OSPF.
Each router in each AS knows how to reach a network that is in its own AS, but it does not know how to
reach a network in another AS.

To enable each router to route a packet to any network in the internet, we first install a variation of BGP4,
called external BGP (eBGP), on each border router (the one at the edge of each AS which is connected to
a router at another AS).

We then install the second variation of BGP, called internal BGP (iBGP), on all routers.

This means that the border routers will be running three routing protocols (intradomain, eBGP, and iBGP),
but other routers are running two protocols (intradomain and iBGP).

Operation of External BGP (eBGP):

We can say that BGP is a kind of point-to-point protocol. When the software is installed on two routers,
they try to create a TCP connection using the well-known port 179. In other words, a pair of client and
server processes continuously communicate with each other to exchange messages. The two routers that
run the BGP processes are called BGP peers or BGP speakers.

34 | P a g e
Module-3, Network Layer, Computer Networks

The eBGP variation of BGP allows two physically connected border routers in two different ASs to form
pairs of eBGP speakers and exchange messages. The routers that are eligible in our example in Figure 20.24
form three pairs: R1-R5, R2-R6, and R4- R9. However, there is a need for a logical TCP connection to be
created over the physical connection to make the exchange of information possible. Each logical connection
in BGP parlance is referred to as a session. This means that we need three sessions in our example, as shown
in Figure 20.25.

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.

However, some points should be made clear:

 First, if an AS has only one router, there cannot be an iBGP session. For example, we cannot create
an iBGP session inside AS2 or AS4 in our internet.
 Second, if there are n routers in an autonomous system, there should be [n × (n − 1) / 2] iBGP
sessions in that autonomous system (a fully connected mesh) to prevent loops in the system.

35 | P a g e
Module-3, Network Layer, Computer Networks

MULTICASTING ROUTING-MOSPF:

Multicast Open Shortest Path First (MOSPF) is an extension to the Open Shortest Path First (OSPF)
protocol designed to support IP multicast routing. Developed to work within OSPF networks, MOSPF
enables routers to build multicast distribution trees for delivering data to multiple recipients efficiently. It
also uses the source based tree approach to multicasting. It uses multicast link-state routing algorithm.

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):

1. 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. Note that this shortest-path tree is different from the one the router normally
uses for unicast forwarding, in which the root of the tree is the router itself. In this case, the root of the tree
is the source of the packet defined in the source address of the packet. The router is capable of creating this
tree because it has the LSDB, the whole topology of the internet; the Dijkstra algorithm can be used to
create a tree with any root, no matter which router is using it. For each source we need to create a different
tree.

2. The router finds itself in the shortest-path tree created in the first step. In other words, the router creates
a shortest-path subtree with itself as the root of the subtree.

3. The shortest-path subtree is actually a broadcast subtree with the router as the root and all networks as
the leaves. The router now uses a strategy to prune the broadcast tree and to change it to a multicast tree.
The IGMP protocol is used to find the information at the leaf level. MOSPF has added a new type of link
state update packet that floods the membership to all routers. The router can use the information it receives
in this way and prune the broadcast tree to make the multicast tree.

4. The router can now forward the received packet out of only those interfaces that correspond to the
branches of the multicast tree. We need to make certain that a copy of the multicast packet reaches all
networks that have active members of the group and that it does not reach those networks that do not.

Figure 21.13 shows an example of using the steps to change a graph to a multicast tree. The figure shows
how a source-based tree is made with the source as the root and changed to a multicast subtree with the root
at the current router.

36 | P a g e