Computer Networks (BIC401)

MODULE-3
Network Layer: Network layer Services, Packet Switching, lPv4 Address,
IPv4 Datagram, IPv6 Datagram, Introduction to Routing Algorithms, Unicast
Routing Protocols: DVR, LSR, PVR, Unicast Routing protocols: RIP, OSPF,
BGP, Multicasting Routing-MOSPF

Textbook 1: Chapters. 18.1, 18.2, 18.4,20.1-20.3, 21.3.2, 22.2

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 154
Computer Networks (BIC401)

Chapter-18
The network layer in the TCP/IP protocol suite is responsible for the host-to-host
delivery of datagrams. It provides services to the transport layer and receives services
from the data-link layer. In this chapter, we introduce the general concepts and issues in
the network layer. This chapter also discusses the addressing mechanism used in the
network layer.

18.1. NETWORK-LAYER SERVICES

Before discussing the network layer in the Internet today, let’s briefly discuss the
network-layer services that, in general, are expected from a network-layer protocol.
Figure 18.1 shows the communication between Alice and Bob at the network layer.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 155
Computer Networks (BIC401)

 The above figure shows that the Internet is made of many networks (or links)
connected through the connecting devices.
 In other words, the Internet is an internetwork, a combination of LANs and WANs.
To better understand the role of the network layer (or the internetwork layer), we
need to think about the connecting devices (routers or switches) that connect the
LANs and WANs.

Explanation to Diagram 18.1

As the figure shows,
 The network layer is involved at the source host, destination host, and all routers in
the path (R2, R4, R5, and R7).
 At the source host (Alice), the network layer accepts a packet from a transport
layer, encapsulates the packet in a datagram, and delivers the packet to the data-
link layer.
 At the destination host (Bob), the datagram is decapsulated, and the packet is
extracted and delivered to the corresponding transport layer.
 Although the source and destination hosts are involved in all five layers of the
TCP/IP suite, the routers use three layers if they are routing packets only; however,
they may need the transport and application layers for control purposes.
 A router in the path is normally shown with two data-link layers and two physical
layers, because it receives a packet from one network and delivers it to another
network.

1. 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.
 The network layer is doing the service of a carrier such as the postal office, which
is responsible for delivery of packages from a sender to a receiver without
changing or using the contents.
 Packetizing happens at Source Host, Destination Host and Router

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 156
Computer Networks (BIC401)

At the Source Host

 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 (as discussed later) 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.
At the Destination Host
 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.
At the Router
 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.
 They just inspect the addresses for the purpose of forwarding the packet to the next
network on the path.
 However, if a packet is fragmented, the header needs to be copied to all fragments
and some changes are needed

2. Routing and Forwarding

Other duties of the network layer, which are as important as the first, are routing and
forwarding, which are directly related to each other.

Routing
 The network layer is responsible for routing the packet from its source to the
destination.
 A physical network is a combination of networks (LANs and WANs) and routers
that connect them. This means that there is more than one route from the source to
the destination.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 157
Computer Networks (BIC401)

 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.
 In the Internet today, this is done by running some routing protocols to help the
routers coordinate their knowledge about the neighbourhood and to come up with
consistent tables to be used when a packet arrives.
 The routing protocols, should be run before any communication occurs.

Forwarding
If routing is applying strategies and running some routing protocols to create the
decision-making tables for each router, forwarding can be defined as the action applied
by each router when a packet arrives at one of its interfaces.
 The decision-making table a router normally uses for applying this action is
sometimes called the forwarding table and sometimes 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. Figure 18.2 shows the idea of the
forwarding process in a router.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 158
Computer Networks (BIC401)

3. Other Services

Let us briefly discuss other services expected from the network layer.
Error Control
 Error control also can be implemented in the network layer, the designers of the
network layer in the Internet ignored this issue for the data being carried by the
network layer.
 One 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.
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. This
checksum may prevent any changes or corruptions in the header of the datagram.
Flow Control
Flow control regulates the amount of data a source can send without overwhelming the
receiver.
 If the upper layer at the source computer produces data faster than the upper layer
at the destination computer can consume it, the receiver will be overwhelmed with
data.
 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.
The datagrams are sent by the sender when they are ready, without any attention to the
readiness of the receiver.
Reasons for the lack of flow control in the design of the network layer can be
mentioned.
 First, since there is no error control in this layer, the job of the network layer at the
receiver is so simple that it may rarely be overwhelmed.
 Second, the upper layers that use the service of the network layer can implement
buffers to receive data from the network layer as they are ready and do not have to
consume the data as fast as it is received.
 Third, flow control is provided for most of the upper-layer protocols that use the
services of the network layer, so another level of flow control makes the network
layer more complicated and the whole system less efficient.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 159
Computer Networks (BIC401)

Congestion Control
Another issue in a network-layer protocol is 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 (Packets).
However, 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.
 If the congestion continues, sometimes a situation may reach a point where the
system collapses and no datagrams are delivered.

Quality of Service
As the Internet has allowed new applications such as multimedia communication (in
particular real-time communication of audio and video), the quality of service (QoS) of
the communication has become more and more important.
The Internet has thrived by providing better quality of service to support these
applications. However, to keep the network layer untouched, these provisions are mostly
implemented in the upper layer.
Security
Another issue related to communication at the network layer is security. Security was not
a concern when the Internet was originally designed because it was used by a small
number of users at universities for research activities; other people had no access to the
Internet. The network layer was designed with no security provision.
Today, however, security is a big concern. 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.

18.2 PACKET SWITCHING

From the discussion of routing and forwarding in the previous section, we infer that 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), just as an
electrical switch connects the input to the output to let electricity flow.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 160
Computer Networks (BIC401)

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
 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.
 Today, a packet-switched network can use two different approaches to route the
packets: the datagram approach and the virtual circuit approach.

1. Datagram Approach: Connectionless Service

When the Internet started, to make it simple, the network layer was designed to provide a
connectionless service in which the network-layer protocol treats each packet
independently, with each packet having no relationship to any other packet.
 The idea was that the network layer is only responsible for delivery of packets
from the source to the destination.
 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.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 161
Computer Networks (BIC401)

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

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

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 162
Computer Networks (BIC401)

 Although it looks as though the use of the label may make the source and
destination addresses unnecessary during the data transfer phase, parts of the
Internet at the network layer still keep these addresses.
 One reason is that part of the packet path may still be using the connectionless
service. Another reason is that the protocol at the network layer is designed with
these addresses, and it may take a while before they can be changed.
Figure 18.5 shows the concept of connection-oriented service.

Each packet is forwarded based on the label in the packet. To follow the idea of
connection-oriented design to be used in the Internet, we assume that 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, as it is
sometimes called.

To create a connection-oriented service, a three-phase process is used: Setup, Data

Transfer, and Teardown.
 In the Setup phase, the source and destination address of the sender and receiver
are used to make table entries for the connection-oriented service.
 In the Teardown phase, the source and destination inform the router to delete the
corresponding entries.
 Data Transfer occurs between these two phases.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 163
Computer Networks (BIC401)

1. 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.
a). Request packet
A 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.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 164
Computer Networks (BIC401)

Explanation to the Figure-18.7

1. Source A sends a request packet to router R1.
2. Router R1 receives the request packet. It knows that a packet going from A to B
goes out through port 3. How the router has obtained this information is a point
covered later. For the moment, assume that it knows the output port. 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.
3. 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).
4. Router R4 receives the setup request packet. Again, three columns are completed:
incoming port (1), incoming label (22), and outgoing port (4).
5. 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, as
shown in Figure 18.8. This label lets the destination know that the packets come
from A, and not from other sources.

b). Acknowledgment Packet

A special packet, called the acknowledgment packet, completes the entries in the
switching tables. Figure 18.8 shows the process.
Explanation to the Figure-18.7
1. The destination sends an acknowledgment to router R4. The acknowledgment
carries the global source and destination address 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.
2. Router R4 sends an acknowledgment to router R3 that contains its incoming label
in the table, chosen in the setup phase. Router R3 uses this as the outgoing label in
the table.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 165
Computer Networks (BIC401)

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

in the table, chosen in the setup phase. Router R1 uses this as the outgoing label in
the table.
4. Finally, router R1 sends an acknowledgment to source A that contains its incoming
label in the table, chosen in the setup phase.
5. The source uses this as the outgoing label for the data packets to be sent to
destination B.

2. 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, but the process is the same for
1, 2, or 100 packets.
 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.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 166
Computer Networks (BIC401)

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

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

18.4 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 they may be
changed.
IPv4 addresses are unique in the sense that each address defines one, and only one,
connection to the Internet. If a device has two connections to the Internet, via two
networks, it has two IPv4 addresses. IPv4 addresses are universal in the sense that the
addressing system must be accepted by any host that wants to be connected to the
Internet.

1. Address Space
A protocol like IPv4 that defines addresses has an address space. An address space is the
total number of addresses used by the protocol.
If a protocol uses b bits to define an address, the address space is 2b because each bit can
have two different values (0 or 1). IPv4 uses 32-bit addresses, which means that the
address space is 232 or 4,294,967,296 (more than four billion). If there were no
restrictions, more than 4 billion devices could be connected to the Internet.

a). Notation
There are three common notations to show an IPv4 address:
1. Binary Notation (Base 2)
2. Dotted-Decimal Notation (Base 256)
3. Hexadecimal Notation (base 16).

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 167
Computer Networks (BIC401)

 In binary notation, an IPv4 address is displayed as 32 bits. To make the address

more readable, one or more spaces are usually inserted between each octet (8 bits).
Each octet is often referred to as a byte.
 To make the IPv4 address more compact and easier to read, it is usually written in
decimal form with a decimal point (dot) separating the bytes. This format is
referred to as dotted-decimal notation. Note that because each byte (octet) is only 8
bits, each number in the dotted-decimal notation is between 0 and 255.
 We sometimes see an IPv4 address in hexadecimal notation. Each hexadecimal
digit is equivalent to four bits. This means that a 32-bit address has 8 hexadecimal
digits. This notation is often used in network programming. Figure 18.16 shows an
IP address in the three discussed notations.

b). Hierarchy in Addressing

In any communication network that involves delivery, such as a telephone network or a
postal network, the addressing system is hierarchical.
Example: In a postal network, the postal address (mailing address) includes the country,
state, city, street, house number, and the name of the mail recipient. Similarly, a
telephone number is divided into the country code, area code, local exchange, and the
connection.
A 32-bit IPv4 address is also hierarchical, but divided only into two parts.
 The first part of the address, called the prefix, defines the network;
 The second part of the address, called the suffix, defines the node (connection of a
device to the Internet).
Figure 18.17 shows the prefix and suffix of a 32-bit IPv4 address. The prefix length is n
bits and the suffix length is (32 − n) bits.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 168
Computer Networks (BIC401)

A prefix can be fixed length or variable length. The network identifier in the IPv4 was
first designed as a fixed-length prefix

2. Classful Addressing
When the Internet started, an IPv4 address was designed with a fixed-length prefix, but to
accommodate both small and large networks, three fixed-length prefixes were designed
instead of one (n = 8, n = 16, and n = 24). The whole address space was divided into five
classes (class A, B, C, D, and E), as shown in Figure 18.18. This scheme is referred to as
Classful Addressing.

Explanation
 In class A, the network length is 8 bits, but since the first bit, which is 0, defines
the class, we can have only seven bits as the network identifier. This means there
are only 27 = 128 networks in the world that can have a class A address.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 169
Computer Networks (BIC401)

 In Class B, the network length is 16 bits, but since the first two bits, which are
(10)2, define the class, we can have only 14 bits as the network identifier. This
means there are only 214 = 16,384 networks in the world that can have a class B
address.
 All addresses that start with (110)2 belong to class C. In Class C, the network
length is 24 bits, but since three bits define the class, we can have only 21 bits as
the network identifier. This means there are 221 = 2,097,152 networks in the world
that can have a class C address.
 Class D is not divided into prefix and suffix. It is used for multicast addresses.
 All addresses that start with 1111 in binary belong to Class E. As in Class D, Class
E is not divided into prefix and suffix and is used as reserve.

a). Address Depletion

The reason that classful addressing has become obsolete is address depletion. Since the
addresses were not distributed properly, the Internet was faced with the problem of the
addresses being rapidly used up, resulting in no more addresses available for
organizations and individuals that needed to be connected to the Internet.

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

b) Subnetting and Supernetting

To alleviate address depletion, two strategies were proposed and, to some extent,
implemented: subnetting and supernetting.
Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 170
Computer Networks (BIC401)

Subnetting
 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.
 For example, if a network in class A is divided into four subnets, each subnet has a
prefix of nsub = 10. At the same time, if all of the addresses in a network are not
used, subnetting allows the addresses to be divided among several organizations.
 This idea did not work because most large organizations were not happy about
dividing the block and giving some of the unused addresses to smaller
organizations.
Supernetting
 While subnetting was devised to divide a large block into smaller ones,
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.
 This idea did not work either because it makes the routing of packets more
difficult.

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.
 In other words, the prefix length in classful addressing is inherent in the address;
no extra information is needed to extract the prefix and the suffix.

3. Classless Addressing
Subnetting and supernetting in classful addressing did not really solve the address
depletion problem. With the growth of the Internet, it was clear that a larger address
space was needed as a long-term solution. The larger address space, however, requires
that the length of IP addresses also be increased, which means the format of the IP
packets needs to be changed.
Although the long-range solution has already been devised and is called IPv6 (discussed
later), a short-term solution was also devised to use the same address space but to change
the distribution of addresses to provide a fair share to each organization. The short-term

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 171
Computer Networks (BIC401)

solution still uses IPv4 addresses, but it is called classless addressing. In other words, the
class privilege was removed from the distribution to compensate for the address
depletion.
Motivation for classless addressing. During the 1990s, Internet Service Providers
(ISPs) came into prominence. An ISP is an organization that provides Internet access for
individuals, small businesses, and midsize organizations that do not want to create an
Internet site and become involved in providing Internet services (such as electronic mail)
for their employees. An ISP can provide these services. An ISP is granted a large range
of addresses and then subdivides the addresses (in groups of 1, 2, 4, 8, 16, and so on),
giving a range of addresses to a household or a small business. The customers are
connected via a dial-up modem, DSL, or cable modem to the ISP. However, each
customer needs some IPv4 addresses.
In 1996, the Internet authorities announced a new architecture called classless
addressing. In classless addressing, variable-length blocks are used that belong to no
classes. We can have a block of 1 address, 2 addresses, 4 addresses, 128 addresses, and
so on.
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 20, 21, 22, . . . , 232 addresses. One of the
restrictions, as we discuss later, 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.

Unlike classful addressing, the prefix length in classless addressing is variable. We can
have a prefix length that ranges from 0 to 32. The size of the network is inversely
proportional to the length of the prefix. A small prefix means a larger network; a large
prefix means a smaller network.
An address in class A can be thought of as a classless address in which the prefix length
is 8. An address in class B can be thought of as a classless address in which the prefix is
16, and so on. In other words, classful addressing is a special case of classless
addressing.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 172
Computer Networks (BIC401)

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

In other words, an address in classless addressing does not, per se, define the block or
network to which the address belongs; we need to give the prefix length also.
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. Since the value of prefix length, n, is given, we can
easily find these three pieces of information, as shown in Figure 18.21.
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.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 173
Computer Networks (BIC401)

Example 18.1
A classless address is given as [Link]/27. We can find the above three pieces of
information as follows.
1. The number of addresses in the network is 232 − n = 25 = 32 addresses.
2. The first address can be found by keeping the first 27 bits and changing the rest of
the bits to 0s.
Address: [Link]/27 10100111 11000111 10101010 01010010
First address: [Link]/27 10100111 11000111 10101010 01000000

3. 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 01011111
Last address: [Link]/27 10100111 11000111 10101010 01011111

b). 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. A computer can easily find the address mask because it
is the complement of (232 − n − 1). The reason for defining a mask in this way is that it
can be used by a computer program to extract the information in a block, using the three
bit-wise operations NOT, AND, and OR.
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 18.2
We repeat Example 18.1 using the mask. The mask in dotted-decimal notation is
[Link]. The AND, OR, and NOT operations can be applied to individual bytes
using
calculators and applets at the book website.
Figure 18.21 Information extraction in classless addressing
Address: [Link]/27 10100111 11000111 10101010 01010010
First address: [Link]/27 10100111 11000111 10101010 01000000
Address: [Link]/27 10100111 11000111 10101010 01011111

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 174
Computer Networks (BIC401)

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

Number of addresses in the block: N = NOT (mask) + 1= [Link] + 1 = 32 addresses
First address: First = (address) AND (mask) = [Link]
Last address: Last = (address) OR (NOT mask) = [Link]

Example 18.3
In classless addressing, an address cannot per se define the block the address belongs to.
For example, the address [Link] can belong to many blocks. Some of them are
shown below with the value of the prefix associated with that block.

c). Network Address

The above examples show that, given any address, we can find all information about the
block. The first address, the network address, is particularly important because it is used
in routing a packet to its destination network.
For the moment, let us assume that an internet is made of m networks and a router with m
interfaces.
 When a packet arrives at the router from any source host, the router needs to know
to which network the packet should be sent: from which interface the packet
should be sent out.
 When the packet arrives at the network, it reaches its destination host using
another strategy. Figure 18.22 shows the idea.
 After the network address has been found, the router consults its forwarding table
to find the corresponding interface from which the packet should be sent out. The
network address is actually the identifier of the network; each network is identified
by its network address

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 175
Computer Networks (BIC401)

d). Block Allocation

The next issue in classless addressing is block allocation. How are the blocks allocated?
The ultimate responsibility of block allocation is given to a global authority called the
Internet Corporation for Assigned Names and Numbers (ICANN).
 However, ICANN does not normally allocate addresses to individual Internet
users. It assigns a large block of addresses to an ISP (or a larger organization that
is considered an ISP in this case).
 For the proper operation of the CIDR, two restrictions need to be applied to the
allocated block.
The number of requested addresses, N, needs to be a power of 2. The reason is that N =
232 − n or n = 32 − log2N. If N is not a power of 2, we cannot have an integer value for
n.
The requested block needs to be allocated where there is an adequate number of
contiguous addresses available in the address space. However, there is a restriction on
choosing the first address in the block. The first address needs to be divisible by the
number of addresses in the block. The reason is that the first address needs to be the
prefix followed by (32 − n) number of 0s. The decimal value of the first address is then
First Address = (prefix in decimal) × 232 − n = (prefix in decimal) × N.

e). Subnetting
More levels of hierarchy can be created using subnetting. An organization (or an ISP)
that is granted a range of addresses may divide the range into several subranges and

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 176
Computer Networks (BIC401)

assign each subrange to a subnetwork (or subnet). Note that nothing stops the
organization from creating more levels. A subnetwork can be divided into several sub-
subnetworks. A sub-subnetwork can be divided into several sub-sub-subnetworks, and so
on.

Designing Subnets
The subnetworks in a network should be carefully designed to enable the routing of
packets. We assume the total number of addresses granted to the organization is N, the
prefix length is n, the assigned number of addresses to each subnetwork is Nsub, and the
prefix length for each subnetwork is nsub. Then the following steps need to be carefully
followed to guarantee the proper operation of the subnetworks.
❑ 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.

Finding Information about Each Subnetwork

After designing the subnetworks, the information about each subnetwork, such as first
and last address, can be found using the process we described to find the information
about each network in the Internet.

Example 18.5
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.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 177
Computer Networks (BIC401)

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

If we add all addresses in the previous subblocks, the result is 208 addresses, which
means 48 addresses are left in reserve. The first address in this range is [Link]. The
last address is [Link]. We don’t know about the prefix length yet. Figure 18.23
shows the configuration of blocks. We have shown the first address in each block.

f). Address Aggregation

One of the advantages of the CIDR strategy is address aggregation (sometimes called
address summarization or route summarization). When blocks of addresses are combined
to create a larger block, routing can be done based on the prefix of the larger block.
ICANN 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.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 178
Computer Networks (BIC401)

g). Special Addresses

Before finishing the topic of addresses in IPv4, we need to mention five special addresses
that are used for special purposes: this-host address, limited-broadcast address, loopback
address, private addresses, and multicast addresses.
i. 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.
ii. 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. The routers in the network, however, block the packet having this address as the
destination; the packet cannot travel outside the network.
iii. 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.
Any address in the block is used to test a piece of software in the machine.
For example, we can write a client and a server program in which one of the addresses in
the block is used as the server address. We can test the programs using the same host to
see if they work before running them on different computers.
iv. Private Addresses
Four blocks are assigned as private addresses: [Link]/8, [Link]/12, [Link]/16,
and [Link]/16.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 179
Computer Networks (BIC401)

v. Multicast Addresses
The block [Link]/4 is reserved for multicast addresses.

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

DHCP Explanation
DHCP has found such widespread use in the Internet that it is often called a plug and-
play protocol.
 In can be used in many situations. 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-fourth 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.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 180
Computer Networks (BIC401)

a). 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.
 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 field.
 There are several tag fields that are mostly used by vendors. If the tag field is 53,
the value field defines one of the 8 message types shown in Figure 18.26. We show
how these message types are used by DHCP.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 181
Computer Networks (BIC401)

b). DHCP Operation

Figure 18.27 shows a simple scenario.

Explanation to figure 18.27

1. The joining host creates a DHCPDISCOVER message in which only the
transaction- ID field is set to a random number. No other field can be set because
the host has no knowledge with which to do so. This message is encapsulated in a
UDP user datagram with the source port set to 68 and the destination port set to 67.
We will discuss the reason for using two well-known port numbers later. 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 reason is that the joining host knows neither its own address nor the
server address.
Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 182
Computer Networks (BIC401)

2. The DHCP server or servers (if more than one) responds with a DHCPOFFER
message in which 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, in which the server allows other DHCP servers to receive the offer and
give a better offer if they can.
3. 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.
4. 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.

i. Two Well-Known Ports

We said that the DHCP uses two well-known ports (68 and 67) instead of one well-
known and one ephemeral. The reason for choosing the well-known port 68 instead of
an ephemeral port for the client is that the response from the server to the client is
broadcast.
 Both hosts receive the response message from the DHCP server and deliver the
message to their clients.
 The DHCP client processes the message; the DAYTIME client is totally
confused with a strange message received.
 Using a well-known port number prevents this problem from happening. The
response message from the DHCP server is not delivered to the DAYTIME
client, which is running on the port number 56017, not 68. The temporary port
numbers are selected from a different range than the well-known port numbers.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 183
Computer Networks (BIC401)

ii. Using FTP

The server does not send all of the information that a client may need for joining the
network. In the DHCPACK message, the server defines the pathname of a file in which
the client 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.

iii. Error Control

DHCP uses the service of UDP, which is not reliable. To provide error control, DHCP
uses two strategies.
 First, DHCP requires that UDP use the checksum, the use of the checksum in UDP
is optional.
 Second, the DHCP client uses timers and a retransmission policy if it does not
receive the DHCP reply to a request.
However, to prevent a traffic jam when several hosts need to retransmit a request (for
example, after a power failure), DHCP forces the client to use a random number to set its
timers.

iv. Transition States

The previous scenarios we discussed for the operation of the DHCP were very simple. To
provide dynamic address allocation, the DHCP client acts as a state machine that
performs transitions from one state to another depending on the messages it receives or
sends. Figure 18.28 shows the transition diagram with the main states.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 184
Computer Networks (BIC401)

Explanation to figure 18.28

 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. 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.
 Note that the client can use the IP address only when it is in the BOUND,
RENEWING, or REBINDING state. The above procedure requires that the client
uses three timers:
 Renewal timer (set to 50 percent of the lease time)
 Rebinding timer (set to 75 percent of the lease time)
 Expiration timer (set to the lease time).

5. Network Address Resolution (NAT)

The distribution of addresses through ISPs has created a new problem. 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.
In most situations, however, only a portion of computers in a small network need access
to the Internet simultaneously. This means that the number of allocated addresses does
not have to match the number of computers in the network.
For example, assume that in a small business with 20 computers the maximum number
of computers that access the Internet simultaneously is only 4. Most of the computers are

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 185
Computer Networks (BIC401)

either doing some tasks that does not need Internet access or communicating with each
other. This small business can use the TCP/IP protocol for both internal and universal
communication. The business can use 20 (or 25) addresses from the private block
addresses (discussed before) for internal communication; five addresses for universal
communication can be assigned by the ISP

 Technology that can provide the mapping between the private and universal
addresses, and at the same time support virtual private networks, is Network
Address Translation (NAT).
 The technology allows a site to use a set of private addresses 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. Figure 18.29 shows a simple
implementation of NAT.

As the figure shows, the private network uses private addresses. The router that connects
the network to the global address uses one private address and one global address. The
private network is invisible to the rest of the Internet; the rest of the Internet sees only the
NAT router with the address [Link].

a). 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. Figure 18.30 shows an
example of address translation.
Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 186
Computer Networks (BIC401)

b). Translation Table

The reader may have noticed that translating the source addresses for an outgoing packet
is straightforward. But how does the NAT router know the destination address for a
packet coming from the Internet? There may be tens or hundreds of private IP addresses,
each belonging to one specific host. The problem is solved if the NAT router has a
translation table

i. 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. Figure 18.31 shows the idea.
In this strategy, communication must always be initiated by the private network. The
NAT mechanism described requires that the private network start the communication.
 As we will see, NAT is used mostly by ISPs that assign a single address to a
customer. The customer, however, may be a member of a private network that has
many private addresses.
 In this case, communication with the Internet is always initiated from the customer
site, using a client program such as HTTP, TELNET, or FTP to access the
corresponding server program.
 For example, when e-mail that originates from outside the network site is received
by the ISP e-mail server, it is stored in the mailbox of the customer until retrieved
with a protocol such as POP.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 187
Computer Networks (BIC401)

ii. Using a Pool of IP Addresses

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]).
iii. 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. Table 18.1 shows
an example of such a table.

Note that when the response from HTTP comes back, the combination of source address
([Link]) and destination port address (1401) defines the private network host to which
the response should be directed. Note also that for this translation to work, the ephemeral
port addresses (1400 and 1401) must be unique.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 188
Computer Networks (BIC401)

CHAPTER-20

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. If the datagram is destined for several destinations
(one-to-many delivery), we have multicast routing.

20.1 INTRODUCTION
Unicast routing in the Internet, with a large number of routers and a huge number of
hosts, can be done only by using hierarchical routing: routing in several steps using
different routing algorithms.
In this section, we first discuss the general concept of unicast routing in an internet: an
internetwork made of networks connected by routers. After the routing concepts and
algorithms are understood, we show how we can apply them to the Internet using
hierarchical routing

1. 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). Although a packet
needs to visit the source and the destination routers, the question is what other routers the
packet should visit.

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

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 189
Computer Networks (BIC401)

 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, modelled as a weighted graph, in which each edge is
associated with a cost.
 If a weighted graph is used to represent a geographical area, the nodes can be
cities and the edges can be roads connecting the cities; the weights, in this case,
are distances between cities.
 In routing, however, the cost of an edge has a different interpretation in different
routing protocols, which we discuss in a later section.
For the moment, we assume that there is a cost associated with each edge. If there is no
edge between the nodes, the cost is infinity. Figure 20.1 shows how an internet can be
modelled as a graph.

2. 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.
 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 criterion.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 190
Computer Networks (BIC401)

a). 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; we have N least-cost
trees for the whole internet. We show how to create a least-cost tree for each node later in
this section; for the moment, Figure 20.2 shows the seven least-cost trees for the internet
in Figure 20.1.

The least-cost trees for a weighted graph can have several properties if they are created
using consistent criteria.
1. The least-cost route from X to Y in X’s tree is the inverse of the least-cost route
from Y to X in Y’s tree; the cost in both directions is the same.
For example, in Figure 20.2,
The route from A to F in A’s tree is (A → B → E → F), but the route from F
to A in F’s tree is (F → E → B → A), which is the inverse of the first route.
The cost is 8 in each case.
2. Instead of travelling from X to Z using X’s tree, we can travel from X to Y using
X’s tree and continue from Y to Z using Y’s tree.
For example, in Figure 20.2,
we can go from A to G in A’s tree using the route (A → B → E → F → G).
We can also go from A to E in A’s tree (A → B → E) and then continue in
E’s tree using the route (E → F → G). The combination of the two routes in
the second case is the same route as in the first case. The cost in the first
case is 9; the cost in the second case is also 9 (6 + 3).
Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 191
Computer Networks (BIC401)

20.2 ROUTING ALGORITHMS

After discussing the general idea behind least-cost trees and the forwarding tables that
can be made from them, now we concentrate on the routing algorithms. Several routing
algorithms have been designed in the past. The differences between these methods are in
the way they interpret the least cost and the way they create the least-cost tree for each
node. In this section, we discuss the common algorithms;
1. Distance-Vector Routing
The distance-vector (DV) routing uses the goal we discussed in the introduction, 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 neighbours.
 The incomplete trees are exchanged between immediate neighbours 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
neighbours what it knows about the whole internet (although the knowledge can be
incomplete).
Before we show how incomplete least-cost trees can be combined to make complete
ones, we need to discuss two important topics: the Bellman-Ford equation and the
concept of distance vectors

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

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 192
Computer Networks (BIC401)

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.
We will shortly show how we use the Bellman-Ford equation and the concept of distance
vectors to build least-cost paths for each node in distance-vector routing, but first we
need to discuss the concept of a distance vector.

a). 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
Note that the
 Name of the distance vector defines the root
 The indexes define the destinations,
 The value of each cell defines the least cost from the root to the destination.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 193
Computer Networks (BIC401)

 A distance vector does not give the path to the destinations as the least-cost tree
does; it gives only the least costs to the destinations
We know that a distance vector can represent least-cost paths in a least-cost tree, but the
question is how each node in an internet originally creates the corresponding vector.
 Each node in an internet, when it is booted, creates a very simple distance vector
with the minimum information the node can obtain from its neighborhood.
 The node sends some greeting messages out of its interfaces and discovers the
identity of
 the immediate neighbors and the distance between itself and each neighbor.
 It then makes a simple distance vector by inserting the discovered distances in the
corresponding cells and leaves the value of other cells as infinity.
 Do these distance vectors represent least-cost paths? They do, considering the
limited information a node has. When we know only one distance between two
nodes, it is the least cost.
Figure 20.5 shows all distance vectors for our internet. However, we need to mention that
these vectors are made asynchronously, when the corresponding node has been booted;
the existence of all of them in a figure does not mean synchronous creation of them.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 194
Computer Networks (BIC401)

These simple vectors cannot help the internet to effectively forward a packet. For
example,
 Node A thinks that it is not connected to node G because the corresponding cell
shows the least cost of infinity. To improve these vectors, 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).
 However, we need to understand that we need to update, not only one least cost,
but N of them in which N is the number of the nodes in the internet.

If we are using a program, we can do this using a loop; if we are showing the concept on
paper, we can show the whole vector instead of the N separate equations. 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 cBA = 2. In the second event, node E has
sent its vector to node B. Node B updates its vector using the cost cEA = 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.

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

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 195
Computer Networks (BIC401)

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

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 196
Computer Networks (BIC401)

c). Count to Infinity

 A problem with distance-vector routing is that any decrease in cost (good news)
propagates quickly, but any increase in cost (bad news) will propagate slowly.
 For a routing protocol to work properly, 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. The problem is referred to as count to infinity.
 It sometimes takes several updates before the cost for a broken link is recorded as
infinity by all routers.

d). 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 depicted in Figure 20.7. The figure shows a system with three
nodes. We have shown only the portions of the forwarding table needed for our
discussion.
 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 A can send its table to B immediately, everything is
fine. However, the system becomes unstable if B sends its forwarding table to A
before receiving A’s forwarding table.
 Node A receives the update and, assuming that B has found a way to reach X,
immediately 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.
 At this moment, both A and B know that X cannot be reached. However, during
this time the system is not stable.
 Node A thinks that the route to X is via B; node B thinks that the route to X is via
A.

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 197
Computer Networks (BIC401)

 If A receives a packet destined for X, the packet goes to B and then comes back to
A. Similarly, if B receives a packet destined for X, it goes to A and comes back to
B. Packets bounce between A and B, creating a two-node loop problem.

A few solutions have been proposed for instability of this kind.

1. Split Horizon
One solution to instability is called 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, according to its table, 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; the information has
come from A (A already knows).
 Taking information from node A, modifying it, and sending it back to node A is
what creates the confusion.
 In our scenario, node B eliminates the last line of its forwarding table before it
sends it to A. In this case, 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.
2. Poison Reverse
Using the split-horizon strategy has one drawback.
 Normally, the corresponding protocol uses a timer, and if there is no news about a
route, the node deletes the route from its table.
 When node B in the previous scenario eliminates the route to X from its
advertisement to A, node A cannot guess whether this is due to the split-horizon
strategy (the source of information was A) or because B has not received any news
about X recently.
In the poison reverse strategy B can still advertise the value for X, but if the source of
information is A, it can replace the distance with infinity as a warning: “Do not use this
value; what I know about this route comes from you.”

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

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 198
Computer Networks (BIC401)

Department of ICB (IoT & Cyber Security including Blockchain Technology), BIT Page 199