UNIT-3 1 CS8591- COMPUTER NETWORKS

UNIT III - NETWORK LAYER

Network Layer Services – Packet switching – Performance – IPV4 Addresses – Forwarding of IP
Packets - Network Layer Protocols: IP, ICMP v4 – Unicast Routing Algorithms – Protocols –
Multicasting Basics – IPV6 Addressing – IPV6 Protocol.

NETWORK-LAYER SERVICES
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.

Figure.3.1 Communication at the network layer

 As the figure.3.1 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.
Duties of network layer
They are
1. Internetworking-Internetworking is the process or technique of connecting different
networks by using intermediary devices such as routers or gateway devices.
2. Addressing- The addresses must be uniquely and universally define the sole connection
of a (host/router/machine/device/user) to the internet. Two devices on the internet can
never have the same address. (Address per connection)
3. Routing and Forwarding
UNIT-3 2 CS8591- COMPUTER NETWORKS
Routing
– The network layer is responsible for routing the packet from its source to the destination.
– It is also 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.
Forwarding
– 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.
– 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.3.2 shows the idea of the forwarding process in a
router.

Figure.3.2 Forwarding process

4. Packetizing
– 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.
– 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.
5. Fragmenting
– A packet can travel through different networks. Each router decapsulates the IP
datagram from the received frame, processes it and then encapsulates it in another
frame.
– The format & size depend on the physical network. The network layer must be able to
fragment transport layer PDUs(protocol data unit) into smaller units so that they can
be transferred over various data-link layer technologies.
UNIT-3 3 CS8591- COMPUTER NETWORKS
– 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.
Other Services
Error Control
– Although the network layer in the Internet does not directly provide error control, the
Internet uses an auxiliary protocol, ICMP that provides some kind of error control if the
datagram is discarded.
– Flow control regulates the amount of data a source can send without overwhelming the
receiver.
– To control the flow of data, the receiver needs to send some feedback to the sender to
inform the latter that it is overwhelmed with data.
– The network layer in the Internet, however, does not directly provide any flow control.
Congestion Control
– Another issue in a network-layer protocol is congestion control. Congestion in the
network layer is a situation in which too many data grams are present in an area of the
Internet.
– Congestion may occur if the number of data grams sent by source computers is beyond
the capacity of the network or routers. If the congestion continues, sometimes a situation
may reach a point where the system collapses and no data grams 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.
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.

PERFORMANCE
The performance of a network can be measured in terms of delay, throughput, and packet
loss. Congestion control is an issue that can improve the performance.
Delay
The delays in a network can be divided into four types: transmission delay, propagation
delay, processing delay, and queuing delay.
Transmission Delay
A source host or a router cannot send a packet instantaneously. A sender needs to put the
bits in a packet on the line one by one. If the first bit of the packet is put on the line at time t1 and
the last bit is put on the line at time t2, transmission delay of the packet is (t2 −t1). So the
transmission delay is
Delaytr = (Packet length) / (Transmission rate).
UNIT-3 4 CS8591- COMPUTER NETWORKS
For example, in a Fast Ethernet LAN with the transmission rate of 100 million bits per
second and a packet of 10,000 bits, it takes (10,000)/(100,000,000) or 100 microseconds for all
bits of the packet to be put on the line.
Propagation Delay
Propagation delay is the time it takes for a bit to travel from point A to point B in the
transmission media. The propagation delay is
Delaypg= (Distance) / (Propagation speed).
For example, if the distances of a cable link in a point-to-point WAN is 2000 meters and
the propagation speed of the bits in the cable is 2×10 8 meters/second, then the propagation delay
is 10 microseconds.
Processing Delay
The processing delay is the time required for a router or a destination host to receive a
packet from its input port, remove the header, perform an error detection procedure, and deliver
the packet to the output port (in the case of a router) or deliver the packet to the upper-layer
protocol (in the case of the destination host). The processing delay may be different for each
packet, but normally is calculated as an average.
Delaypr = Time required to process a packet in a router or a destination host
Queuing Delay
Queuing delay can normally happen in a router. A router has an input queue connected to
each of its input ports to store packets waiting to be processed; the router also has an output
queue connected to each of its output ports to store packets waiting to be transmitted. So the
queuing delay for a packet in a router is
Delayqu = the time a packet waits in input and output queues in a router
Total Delay
Assuming equal delays for the sender, routers, and receiver, the total delay (source-to
destination delay) a packet encounters can be calculated if we know the number of routers, n, in
the whole path.
Total delay = (n +1) (Delaytr +Delaypg +Delaypr) + (n) (Delayqu)
Note that if we have n routers, we have (n +1) links. Therefore, we have (n +1)
transmission delays related to n routers and the source, (n +1) propagation delays related to (n
+1) links, (n +1) processing delays related to n routers and the destination, and only n queuing
delays related to n routers.
Throughput
Throughput at any point in a network is defined as the number of bits passing through the
point in a second, which is actually the transmission rate of data at that point.
In a path from source to destination, a packet may pass through several links (networks),
each with a different transmission rate.
In this figure.3.3, the data can flow at the rate of 200 kbps in Link1. However, when the
data arrives at router R1, it cannot pass at this rate. Data needs to be queued at the router and sent
at 100 kbps. When data arrives at router R2, it could be sent at the rate of 150 kbps, but there is
not enough data to be sent.
UNIT-3 5 CS8591- COMPUTER NETWORKS

Figure.3.3 Throughput in a path with three links in a series

In other words, the average rate of the data flow in Link3 is also 100 kbps. We can
conclude that the average data rate for this path is 100 kbps, the minimum of the three different
data rates. We can simulate the behaviour of each link with pipes of different sizes; the average
throughput is determined by the bottleneck, the pipe with the smallest diameter. In general, in a
path with n links in series, we have
Throughput = minimum {TR1, TR2 ...TRn}.
Packet Loss
Another issue that severely affects the performance of communication is the number of
packets lost during transmission. When a router receives a packet while processing another
packet, the received packet needs to be stored in the input buffer waiting for its turn.
A router, however, has an input buffer with a limited size. A time may come when the
buffer is full and the next packet needs to be dropped.
The effect of packet loss on the Internet network layer is that the packet needs to be
resent, which in turn may create overflow and cause more packet loss.
Congestion Control
Congestion control is a mechanism for improving performance. Congestion at the
network layer is related to two issues, throughput and delay.
Congestion Control Techniques
Congestion control refers to the mechanisms and techniques used to control congestion and
keep the traffic below the capacity of the network. The congestion control techniques can be
broadly classified two broad categories:
1. Open loop (prevention): Protocols to prevent or avoid congestion, ensuring that the
system (or network under consideration) never enters a Congested State.
2. Close loop (removal): Protocols that allow system to enter congested state, detect it, and
remove it.
1. Open-Loop Congestion Control
In open-loop congestion control, policies are applied to prevent congestion before it happens.
Retransmission Policy
If sent packet is lost or corrupted, the packet needs to be retransmitted. The retransmission
policy and the retransmission timers must be designed to optimize efficiency and at the same
time prevent congestion.
Window Policy
The type of window at the sender may also affect congestion. The Selective Repeat
window is better than the Go-Back-N window for congestion control.
Acknowledgment Policy
The acknowledgment policy imposed by the receiver may also affect congestion. Sending
fewer acknowledgments means imposing fewer loads on the network.
Discarding Policy
UNIT-3 6 CS8591- COMPUTER NETWORKS
A good discarding policy by the routers may prevent congestion and at the same time
may not harm the integrity of the transmission.
Admission Policy
An admission policy, which is a quality-of-service mechanism, can also prevent
congestion in virtual-circuit networks
2. Closed-Loop Congestion Control
Closed-loop congestion control mechanisms try to alleviate congestion after it happens.
Backpressure
Backpressure is a node-to-node congestion control that starts with a node and propagates,
in the opposite direction of data flow, to the source.

Figure.3.4 Backpressure method for alleviating congestion

Choke packet
A choke packet is a packet sent b y a node to the source to inform it of congestion.

Figure.3.5 Choke packet

Implicit Signaling
In implicit signaling, there is no communication between the congested node or nodes
and the source. The source guesses that there is congestion somewhere in the network from other
symptoms.
Explicit Signaling
The node that experiences congestion can explicitly send a signal to the source or
destination. In the choke packet method, a separate packet is used for this purpose; they are
Backward Signaling-A bit can be set in a packet moving in the direction opposite to the
congestion. This bit can warn the source that there is congestion.
Forward Signaling-A bit can be set in a packet moving in the direction of the congestion. This
bit can warn the destination that there is congestion.

IPV4 ADDRESSES
– An IPv4 address is a 32-bit address that uniquely and universally defines the connection
of a device (for example, a computer or a router) to the Internet.
– The address space of IPv4 is 232 or 4,294,967,296.
Notation
There are three common notations to show an IPv4 address:
– Binary notation (base 2)
UNIT-3 7 CS8591- COMPUTER NETWORKS
– dotted-decimal notation (base 256)
– hexadecimal notation (base 16)
1. Binary Notation
– In binary notation, the IPv4 address is displayed as 32 bits.
– Each octet is often referred to as a byte. So it is common to hear an IPv4 address referred
to as a 32-bit address or a 4-byte address.
2. Dotted-Decimal Notation
– To make the IPv4 address more compact and easier to read, Internet addresses are usually
written in decimal form with a decimal point (dot) separating the bytes.
3. 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.3.6 Three different notations in IPv4 addressing

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. Figure.3.7 shows the prefix and suffix of a
32-bit IPv4 address. The prefix length is n bits and the suffix length is (32 − n) bits.

Figure.3.7 Hierarchy in addressing

– A prefix can be fixed length or variable length. The network identifier in the IPv4 was
first designed as a fixed-length prefix. This is referred to as classful addressing. The new
scheme, which is referred to as classless addressing, uses a variable-length network
prefix.
There are two type of addressing. They are
1. Classful addressing
2. Classless addressing
1. Classful Addressing
– The whole address space was divided into five classes (class A, B, C, D, and E), as
shown in Figure.3.8. This scheme is referred to as classful addressing.
UNIT-3 8 CS8591- COMPUTER NETWORKS
– 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 2 7 = 128
networks in the world that can have a class A address.
– In class B, the network length is 16 bits, but since the first two bits, which are (10) 2,
define the class, we can have only 14 bits as the network identifier. This means there are
only 214 = 16,384 networks in the world that can have a class B address.
– All addresses that start with (110) 2 belong to class C. In class C, the network length is 24
bits, but since three bits define the class, we can have only 21 bits as the network
identifier. This means there are 2 21 = 2,097,152 networks in the world that can have a
class C address.

Figure.3.8 Occupation of the address space in classful addressing

– 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.
Example-1:
Change the following IP addresses from binary notation to dotted-decimal notation.
a. 10000001 00001011 00001011 11101111
b. 11111001 10011011 11111011 00001111
Solution:
We replace each group of 8 bits with its equivalent decimal number and add dots for separation:
a. 129.11.11.239
b. 249.155.251.15
Example-2:
Change the following IP addresses from dotted-decimal notation to binary notation.
a. 111.56.45.78
b. 75.45.34.78
Solution:
We replace each decimal number with its binary equivalent
a. 01101111 00111000 00101101 01001110
b. 01001011 00101101 00100010 01001110
Example-3
Find the class of each address.
a. 00000001 00001011 00001011 11101111
b. 11000001 10000011 00011011 11111111
c. 14.23.120.8
d. 252.5.15.111
UNIT-3 9 CS8591- COMPUTER NETWORKS
Solution:
a. The first bit is 0. This is a class A address.
b. The first 2 bits are 1; the third bit is 0. This is a class C
c. The first byte is 14; the class is A.
d. The first byte is 252; the class is E.
Address Depletion
– The reason that classful addressing has become obsolete is address depletion. One
problem with classful addressing is that each class is divided into a fixed number of
blocks with each block having a fixed size.
– Class A addresses were designed for large organizations with a large number of attached
hosts or routers. (Wasted and not used).Class B addresses were designed for midsize
organizations with tens of thousands of attached hosts or routers (too large for many
organizations)
– Class C addresses were designed for small organizations with a small number of attached
hosts or routers. (too small for many organizations).Class D addresses were designed for
multicasting. (waste of addresses)
– Class E addresses were reserved for future use (waste of addresses)
– In classful addressing, a large part of the available addresses were wasted.
Subnetting and Supernetting
To alleviate address depletion, two strategies were proposed: subnetting and supernetting.
Subnetting
If an organization was granted a large block in class A or B, it could divide the addresses
into several contiguous groups and assign each group to smaller networks (called subnets) or, in
rare cases, share part of the addresses with neighbors.
Supernetting
In super netting, an organization can combine several class C blocks to create a larger
range of addresses. In other words, several networks are combined to create a super network or
super net. Super netting decreases the number of 1s in the mask.
Advantage of Classful Addressing
Although classful addressing had several problems and became obsolete, it had one
advantage: the prefix length in classful addressing is inherent in the address; no extra information
is needed to extract the prefix and the suffix.
2. Classless Addressing
– Sub netting and super netting in classful addressing did not really solve the address
depletion problem.
– 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. The prefix
in an address defines the block (network); the suffix defines the node (device).
Address Blocks
– Theoretically, we can have a block of 2 0, 21, 22…232 addresses. One of the restrictions is
that the number of addresses in a block needs to be a power of 2.
– 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.
 For example, a household may be given only two addresses; a large organization may
UNIT-3 10 CS8591- COMPUTER NETWORKS
be given thousands of addresses.
 An ISP, as the Internet service provider, may be given thousands or hundreds of
thousands based on the number of customers it may serve.
Prefix Length: Slash Notation
– 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.3.9.

Figure.3.9 Slash notation (CIDR)

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

Figure.3.10 Information extraction in classless addressing

Example-4
A classless address is given as 167.199.170.82/27. We can find the above three pieces of
information as follows. The number of addresses in the network is 232 − n = 25 = 32 addresses.
The first address can be found by keeping the first 27 bits and changing the rest of the bits to 0s.
Address: 167.199.170.82/27
10100111 11000111 10101010 01010010
First address: 167.199.170.64/27
10100111 11000111 10101010 01000000
The last address can be found by keeping the first 27 bits and changing the rest of the bits to 1s.
Address: 167.199.170.82/27
10100111 11000111 10101010 01011111
Last address: 167.199.170.95/27
UNIT-3 11 CS8591- COMPUTER NETWORKS
10100111 11000111 10101010 01011111
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.
 The number of addresses in the block N = NOT (mask) + 1.
 The first address in the block = (Any address in the block) AND (mask).
 The last address in the block = (Any address in the block) OR [(NOT (mask)].
Example-5
Another way to find the first address, the last address, and the number of addresses is to
represent the mask as a 32-bit binary (or 8-digit hexadecimal) number. This is particularly useful
when we are writing a program to find these pieces of information. In Example-4 the /28 can be
represented as 11111111 11111111 11111111 11110000 (twenty-eight 1s and four 0s). Find
a. The first address
b. The last address
c. The number of addresses
Solution
a. The first address can be found by ANDing the given addresses with the mask.
ANDing here is done bit by bit. The result of ANDing 2 bits is 1 if both bits are 1s; the
result is 0 otherwise.
Address: 11001101 00010000 00100101 00100111
Mask: 11111111 11111111 11111111 11110000

First address: 11001101 00010000 00100101 00100000

b. The last address can be found by ORing the given addresses with the complement of the mask.
ORing here is done bit by bit. The result of ORing 2 bits is 0 if both bits are Os; the result is 1
otherwise. The complement of a number is found by changing each 1 to 0 and each 0 to 1.

Address: 11001101 00010000 00100101 00100111

Mask complement: 00000000 00000000 00000000 00001111
Last address: 11001101 00010000 00100101 00101111
c. The number of addresses can be found by complementing the mask, interpreting it as a
decimal number, and adding 1 to it.

000000000 00000000 00000000

Mask complement: 00001111
Number of addresses: 15 + 1 =16
Network Address
The first address, the network address, is particularly important because it is used in
routing a packet to its destination network. 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. Figure.3.11 shows the idea.
UNIT-3 12 CS8591- COMPUTER NETWORKS

Figure.3.11 Network Address

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.
Example-6
Given the address
132.6.17.85 and 23.56.7.91, find the network address?
Solution
1. The class is B. The first 2 bytes defines the netid. We can find the network address by
replacing the hostid bytes (17.85) with 0s. 132.6.0.0.
2. The class is A. Only the first byte defines the netid. We can find the network address by
replacing the hostid bytes (56.7.91) with 0s. Therefore, the network address is 23.0.0.0.
Hierarchy
 IP addresses have levels of hierarchy. For example, a telephone network in North
America has three levels of hierarchy.
 The leftmost three digits define the area code, the next three digits define the exchange,
the last four digits define the connection of the local loop to the central office.
Figure.3.12 shows the structure of a hierarchical telephone number.

Figure.3.12 Hierarchy in a telephone network in North America

Two-level Hierarchy: No sub netting
An IP address can define only two levels of hierarchy when not sub netted.
Prefix: the leftmost n bits define the network.
Suffix: the rightmost 32 - n bits define the particular host (computer or router). Prefix is common
to all network address.
Three-level hierarchy in an IPv4 address (Sub netted)
An organization that is granted a large block of addresses may want to create clusters of
networks (called subnets) and divide the addresses between the different subnets. Figure.3.13
shows two level and three level hierarchy in an IPv4 address

Figure.3.13 Two level and Three level hierarchy in an IPv4 address

UNIT-3 13 CS8591- COMPUTER NETWORKS
Block Allocation
The next issue in classless addressing is block allocation. 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. For the proper operation
of the CIDR, two restrictions need to be applied to the allocated block.
1. 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.
2. 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

Example-7
An ISP has requested a block of 1000 addresses. Since 1000 is not a power of 2, 1024
addresses are granted. The prefix length is calculated as n = 32 − log21024 = 22. An available
block, 18.14.12.0/22, is granted to the ISP. It can be seen that the first address in decimal is
302,910,464, which is divisible by 1024.
Subnetting
More levels of hierarchy can be created using subnetting. 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.
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 in to smaller
subblocks and grants the subblocks to its customers.
Special Addresses
There are five special addresses used for special purposes: this-host address, limited-
broadcast address, loopback address, private addresses, and multicast addresses.
This-host Address
UNIT-3 14 CS8591- COMPUTER NETWORKS
The only address in the block 0.0.0.0/32 is called this-host address. It is used whenever a
host needs to send an IP datagram but it does not know its own address to use as the source
address.
Limited-broadcast Address
The only address in the block 255.255.255.255/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.
Loopback Address
The block 127.0.0.0/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.
Private Addresses
Four blocks are assigned as private addresses: 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16,
and 169.254.0.0/16.
Multicast Addresses
The block 224.0.0.0/4 is reserved for multicast addresses.
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.
– Address assignment in an organization can be done automatically using the Dynamic
Host Configuration Protocol (DHCP).
– It is also called as plug and- play protocol. A network manager can configure DHCP to
assign permanent IP addresses to the host and routers.
– It 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.
– 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 uses two well-known ports (68 and 67) instead of one well-known and one
ephemeral.
DHCP Message Format
– DHCP is a client-server protocol in which the client sends a request message and the
server returns a response message.
– 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 99.130.83.99.
UNIT-3 15 CS8591- COMPUTER NETWORKS

Figure.3.14 DHCP message format

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

Figure.3.15Option format
DHCP Operation
Figure.3.16 shows a simple scenario.
1. The joining host creates a DHCPDISCOVER message in which only the transaction- ID field
is set to a random number.

Figure.3.16 Operation of DHCP

UNIT-3 16 CS8591- COMPUTER NETWORKS
2. The DHCP server 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.
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.
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, the server sends a DHCPNACK message and
the client needs to repeat the process.
Transition States
– 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 shows the transition diagram with the main states.

Figure.3.17 FSM for the DHCP client

– 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), and expiration timer (set to the lease time).
UNIT-3 17 CS8591- COMPUTER NETWORKS
Network Address Resolution (NAT)
– In the beginning, a user was connected to the Internet with a dial-up line, which means
that she was connected for a specific period of time.
– An ISP with a block of addresses could dynamically assign an address to this user. An
address was given to a user when it was needed.
– But now home users and small businesses can be connected by an ADSL line or cable
modem.
– With the shortage of addresses, this is a serious problem. A quick solution to this problem
is called network address translation (NAT).
– NAT enables a user to have a large set of addresses internally and one address, or a small
set of addresses, externally. The traffic inside can use the large set; the traffic outside, the
small set.
– To separate the addresses used inside the home or business and the ones used for the
Internet, the Internet authorities have reserved three sets of addresses as private
addresses, shown in Table.3.2.
Table: Addresses for private networks

Figure.3.18 NAT
– Any organization can use an address out of this set without permission from the Internet
authorities. Figure.3.18 shows a simple implementation of NAT.
– Everyone knows that these reserved addresses are for private networks. They are unique
inside the organization, but they are not unique globally.
– No router will forward a packet that has one of these addresses as the destination address.
Address Translation
– All 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.3.19 shows an example of address translation.

Figure.3.19 Addresses in a NAT

UNIT-3 18 CS8591- COMPUTER NETWORKS
Translation Table
 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.
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.3.20
shows the idea.

Figure.3.20 Translation
– In this strategy, communication must always be initiated by the private network. The
NAT mechanism described requires that the private network start the communication.
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.
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 (200.24.5.8), the NAT router can use
four addresses (200.24.5.8, 200.24.5.9, 200.24.5.10, and 200.24.5.11).

FORWARDING OF IP PACKETS
Forwarding means to place the packet in its route to its destination. Since the Internet
today is made of a combination of links (networks), forwarding means to deliver the packet to
UNIT-3 19 CS8591- COMPUTER NETWORKS
the next hop (which can be the final destination or the intermediate connecting device).
When IP is used as a connectionless protocol, forwarding is based on the destination
address of the IP datagram; when the IP is used as a connection-oriented protocol, forwarding is
based on the label attached to an IP datagram.
Forwarding Based on Destination Address
In this case, forwarding requires a host or a router to have a forwarding table. When a
host has a packet to send or when a router has received a packet to be forwarded, it looks at this
table to find the next hop to deliver the packet to.
In classless addressing, the whole address space is one entity; there are no classes. The
table needs to be searched based on the network address (first address in the block).
Unfortunately, the destination address in the packet gives no clue about the network address.
To solve the problem, we need to include the mask (/n) in the table. In other words, a
classless forwarding table needs to include four pieces of information: the mask, the network
address, the interface number, and the IP address of the next router.

Figure.3.21 Simplified forwarding module in classless address

The job of the forwarding module is to search the table, row by row. In each row, the n
leftmost bits of the destination address (prefix) are kept and the rest of the bits (suffix) are set to
0s. If the resulting address (which we call the network address), matches with the address in the
first column, the information in the next two columns is extracted; otherwise the search
continues. Normally, the last row has a default value in the first column (not shown in the
figure), which indicates all destinations address that did not match the previous rows.
Address Aggregation
When we use classful addressing, there is only one entry in the forwarding table for each
site outside the organization. The entry defines the site even if that site is subnetted. When a
packet arrives at the router, the router checks the corresponding entry and forwards the packet
accordingly.
When we use classless addressing, it is likely that the number of forwarding table entries
will increase. This is because the intent of classless addressing is to divide up the whole address
space into manageable blocks. The increased size of the table results in an increase in the amount
of time needed to search the table. To alleviate the problem, the idea of address aggregation was
designed.
In Figure.3.22, we have two routers.R1 is connected to networks of four organizations
that each use 64 addresses. R2 is somewhere far from R1. R1 has a longer forwarding table
because each packet must be correctly routed to the appropriate organization. R2, on the other
hand, can have a very small forwarding table. For R2, any packet with destination 140.24.7.0 to
140.24.7.255 is sent out from interface m0 regardless of the organization number. This is called
address aggregation because the blocks of addresses for four organizations are aggregated into
UNIT-3 20 CS8591- COMPUTER NETWORKS
one larger block. R2 would have a longer forwarding table if each organization had addresses
that could not be aggregated into one block.

Figure.3.22 Address aggregation

Longest Mask Matching
This principle states that the forwarding table is sorted from the longest mask to the
shortest mask. In other words, if there are three masks, /27, /26, and /24, the mask /27 must be
the first entry and /24 must be the last. Let us see if this principle solves the situation in which
organization 4 is separated from the other three organizations.
Hierarchical Routing
To solve the problem of gigantic forwarding tables, we can create a sense of hierarchy in
the forwarding tables. Internet is divided into backbone and national ISPs. National ISPs are
divided into regional ISPs, and regional ISPs are divided into local ISPs. If the forwarding table
has a sense of hierarchy like the Internet architecture, the forwarding table can decrease in size.
Inside the local ISP, the router must recognize the subblocks and route the packet to the
destined customer. If one of the customers is a large organization, it also can create another level
of hierarchy by subnetting and dividing its subblock into smaller subblocks (or sub-subblocks).
In classless routing, the levels of hierarchy are unlimited as long as we follow the rules of
classless addressing.
Geographical Routing
To decrease the size of the forwarding table even further, we need to extend hierarchical
routing to include geographical routing. We must divide the entire address space into a few large
blocks. We assign a block to America, a block to Europe, a block to Asia, a block to Africa, and
so on. The routers of ISPs outside of Europe will have only one entry for packets to Europe in
their forwarding tables. The routers of ISPs outside of America will have only one entry for
packets to America in their forwarding tables, and so on.
Forwarding Table Search Algorithms
In classless addressing, there is no network information in the destination address. The
simplest, but not the most efficient, search method is called the longest prefix match. The
forwarding table can be divided into buckets, one for each prefix. The router first tries the
UNIT-3 21 CS8591- COMPUTER NETWORKS
longest prefix. If the destination address is found in this bucket, the search is complete. If the
address is not found, the next prefix is searched, and so on. It is obvious that this type of search
takes a long time. One solution is to change the data structure used for searching. Instead of a
list, other data structures (such as a tree or a binary tree) can be used. One candidate is a trie (a
special kind of tree).
Forwarding Based on Label
In a connectionless network (datagram approach), a router forwards a packet based on the
destination address in the header of the packet. On the other hand, in a connection-oriented
network (virtual-circuit approach), a switch forwards a packet based on the label attached to the
packet. Routing is normally based on searching the contents of a table; switching can be done by
accessing a table using an index.
Multi-Protocol Label Switching (MPLS)
During the 1980s, several vendors created routers that implement switching technology.
Later IETF approved a standard that is called Multi-Protocol Label Switching. In this standard,
some conventional routers in the Internet can be replaced by MPLS routers, which can behave
like a router and a switch. When behaving like a router, MPLS can forward the packet based on
the destination address; when behaving like a switch, it can forward a packet based on the label.
A New Header
To simulate connection-oriented switching using a protocol like IP, the first thing that is
needed is to add a field to the packet. The IPv4 packet format does not allow this extension. The
solution is to encapsulate the IPv4 packet in an MPLS packet (as though MPLS were a layer
between the data-link layer and the network layer). The whole IP packet is encapsulated as the
payload in an MPLS packet and an MPLS header is added.
Hierarchical Switching
A stack of labels in MPLS allows hierarchical switching. This is similar to conventional
hierarchical routing. For example, a packet with two labels can use the top label to forward the
packet through switches outside an organization; the bottom label can be used to route the packet
inside the organization to reach the destination subnet.
Routers as Packet Switches
The packets switches are used in the network layer are called routers. Routers can be
configured to act as either a datagram switch or a virtual-circuit switch.

NETWORK LAYER PROTOCOLS: IP

– The network layer in version 4 can be thought of as one main protocol and three auxiliary
ones. The main protocol, Internet Protocol version 4 (IPv4), is responsible for
packetizing, forwarding, and delivery of a packet at the network layer.
– The Internet Control Message Protocol version 4 (ICMPv4) helps IPv4 to handle some
errors that may occur in the network-layer delivery.
– The Internet Group Management Protocol (IGMP) is used to help IPv4 in multicasting.
– The Address Resolution Protocol (ARP) is used to glue the network and data-link layers
in mapping network-layer addresses to link-layer addresses. Figure.3.23 shows the
positions of these four protocols in the TCP/IP protocol suite.
UNIT-3 22 CS8591- COMPUTER NETWORKS

Figure.3.23 Position of IP and other network-layer protocols in TCP/IP protocol suite

– IP is an unreliable datagram protocol—a best-effort delivery service.By best effort we
mean that there is no error and flow control. However, IP performs error detection and
discards a packet, if it is corrupted. To achieve reliability, it is necessary to combine it
with a reliable protocol such as TCP.
– IPv4 is also a connectionless protocol that uses the datagram approach. This means that
each datagram is handled independently, and each datagram can follow a different route
to the destination.
Datagram Format
– Packets used by the IP are called datagrams. Figure.3.24 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. It is customary in TCP/IP to show the header in 4-byte sections.
Brief descriptions of each of the fields are given below:
VER (4 bits): Version of the IP protocol in use (typically 4).
HLEN (4 bits): Length of the header, expressed as the number of 32-bit words. Minimum size is
5, and maximum 15.
Total Length (16 bits): Length in bytes of the datagram, including headers. Maximum datagram
size is (216) 65536 bytes.
Service Type (8 bits): Allows packet to be assigned a priority. Router can use this field to
route packets. Not universally used.

Figure.3.24 IP datagram
UNIT-3 23 CS8591- COMPUTER NETWORKS
Time to Live (8 bits): Prevents a packet from traveling forever in a loop. Senders set a value that
is decremented at each hop. If it reaches zero, packet is discarded.
Protocol: Defines the higher level protocol that uses the service of the IP layer Source IP address
(32 bits): Internet address of the sender.
Destinations IP address (32 bits): Internet address of the destination.
Identification, Flags, Fragment Offset: Used for handling fragmentation.
Options (variable width): Can be used to provide more functionality to the IP datagram
Header Checksum (16 bits): Covers only the IP header.
Multiplexing and Demultiplexing
 IP datagram can encapsulate data from several higher-level protocols such as TCP, UDP,
ICMP, etc.
 The Protocol field in the datagram specifies the final destination protocol to which IP
datagram to be delivered.
 When the datagram arrives at the destination, the information in this field is used to
perform demultiplex the operation. The multiplexing and demultiplexing operations are
shown in Figure.3.25.

Figure.3.25 Multiplexing and demultiplexing using the value of the protocol field
Example-8
In an IPv4 packet, the value of HLEN is (1000) 2. How many bytes of options are being
carried by this packet?
Solution
The HLEN value is 8, which means the total number of bytes in the header is 8 × 4, or 32
bytes.The first 20 bytes are the base header, the next 12 bytes are the options.
Example-9
In an IPv4 packet, the value of HLEN is 5, and the value of the total length field is
(0028)16. How many bytes of data are being carried by this packet?
Solution
The HLEN value is 5, which means the total number of bytes in the header is 5 × 4, or 20
bytes (no options). The total length is (0028)16 or 40 bytes, which means the packet is carrying 20
bytes of data (40 − 20).
Fragmentation
Each network imposes a limit on maximum size, known as maximum transfer unit
(MTU) of a packet because of various reasons. One approach is to prevent the problem to occur
in the first place, i.e. send packets smaller than the MTU. Second approach is to deal with the
problem using fragmentation.
When a gateway connects two networks that have different maximum and or minimum
packet sizes, it is necessary to allow the gateway to break packets up into fragments, sending
each one as an internet packet. The technique is known as fragmentation.
UNIT-3 24 CS8591- COMPUTER NETWORKS
The following fields of an IP datagram are related to fragmentation:
 Identification: A16-bit field identifies a datagram originating from the source host.
 Flags: There are 3 bits, the first bit is reserved, the second bit is do not fragment bit, and
the last bit is more fragment bit.
 Fragmentation offset: This 13-bit field shows the relative position of the segment with
respect to the complete datagram measured in units of 8 bytes.

Figure.3.26 Fragmentation example

The reverse process, known as reassembly, which puts the fragments together, is a more
difficult task. There are two opposing strategies for performing the re-assembly. The bytes in the
original datagram are numbered 0 to 3999.
The first fragment carries bytes 0 to 1399. The offset for this datagram is 0/8 = 0. The
second fragment carries bytes 1400 to 2799; the offset value for this fragment is 1400/8 = 175.
Finally, the third fragment carries bytes 2800 to 3999. The offset value for this fragment is
2800/8 = 350.
The figure.3.27 also shows what happens if a fragment itself is fragmented. In this case
the value of the offset field is always relative to the original datagram. For example, in the figure,
the second fragment is itself fragmented later into two fragments of 800 bytes and 600 bytes, but
the offset shows the relative position of the fragments to the original data.

Figure.3.27 Detailed fragmentation example

UNIT-3 25 CS8591- COMPUTER NETWORKS
Example-10
A packet has arrived in which the offset value is 100, the value of HLEN is 5, and the value of
the total length field is 100. What are the numbers of the first byte and the last byte?
Solution
The first byte number is 100 × 8 = 800. The total length is 100 bytes, and the header length is 20
bytes (5 × 4), which means that there are 80 bytes in this datagram. If the first byte number is
800, the last byte number must be 879.
Security of IPv4 Datagrams
There are three security issues that are particularly applicable to the IP protocol: packet
sniffing, packet modification, and IP spoofing.
Packet Sniffing
An intruder may intercept an IP packet and make a copy of it. Packet sniffing is a passive
attack, in which the attacker does not change the contents of the packet. This type of attack is
very difficult to detect because the sender and the receiver may never know that the packet has
been copied.
Packet Modification
The second type of attack is to modify the packet. The attacker intercepts the packet,
changes its contents, and sends the new packet to the receiver. The receiver believes that the
packet is coming from the original sender. This type of attack can be detected using a data
integrity mechanism.
IP Spoofing
An attacker can masquerade as somebody else and create an IP packet that carries the
source address of another computer. An attacker can send an IP packet to a bank pretending that
it is coming from one of the customers. This type of attack can be prevented using an origin
authentication mechanism
ICMPv4
– The IPv4 has no error-reporting or error-correcting mechanism. The IP protocol also
lacks a mechanism for host and management queries. A host sometimes needs to
determine if a router or another host is alive. And sometimes a network manager needs
information from another host or router.
– The Internet Control Message Protocol version 4 (ICMPv4) has been designed to
compensate for the above two deficiencies. It is a companion to the IP protocol. ICMP
itself is a network-layer protocol. However, its messages are not passed directly to the
data-link layer as would be expected.
– Instead, the messages are first encapsulated inside IP datagrams before going to the lower
layer. When an IP datagram encapsulates an ICMP message, the value of the protocol
field in the IP datagram is set to 1 to indicate that the IP payroll is an ICMP message.
Messages
– ICMP messages are divided into two broad categories: error-reporting messages and
query messages. The error-reporting messages report problems that a router or a host
(destination) may encounter when it processes an IP packet.
– The query messages, which occur in pairs, help a host or a network manager get specific
information from a router or another host.
– An ICMP message has an 8-byte header and a variable-size data section. As Figure.3.28
shows, the first field, ICMP type, defines the type of the message. The code field
UNIT-3 26 CS8591- COMPUTER NETWORKS
specifies the reason for the particular message type. The last common field is the
checksum field. The rest of the header is specific for each message type.

Figure.3.28 General Format of ICMP messages

Error Reporting Message
 One of the main responsibilities of ICMP is to report errors. ICMP does not correct
errors-it simply reports them. Error correction is left to the higher-level protocols.
 Error messages are always sent to the original source because the only information
available in the datagram about the route is the source and destination IP addresses.
 ICMP uses the source IP address to send the error message to the source (originator) of
the datagram.
 Five types of errors are handled: destination unreachable, source quench, time exceeded,
parameter problems, and redirection
Query Message
 In addition to error reporting, ICMP can diagnose some network problems.
 This is accomplished through the query messages, a group of four different pairs of
messages. They are Echo, Timestamp, Address mask and Router solicitation.
 In this type of ICMP message, a node sends a message that is answered in a specific
format by the destination node.
Debugging Tools
 There are several tools that can be used in the Internet for debugging.
 We can determine the viability of a host or router. We can trace the route of a packet.
 We introduce two tools that use ICMP for debugging: ping and trace route.
Ping
 We can use the ping program to find if a host is alive and responding. We use ping here
to see how it uses ICMP packets.
Trace route
 The trace route program in UNIX or tracert in Windows can be used to trace the route of
a packet from the source to the destination.

ROUTING
– Routing is an act of moving information across an inter-network from a source to a
destination.
– 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.
UNIT-3 27 CS8591- COMPUTER NETWORKS
– The routing algorithm is the part of the network layer software responsible for deciding
which output line an incoming packet should be transmitted on, i.e. what should be the
next intermediate node for the packet.
– Routing protocols use metrics to evaluate what path will be the best for a packet to travel.
– A metric is a standard of measurement; such as path bandwidth, reliability, delay, current
load on that path etc; that is used by routing algorithms to determine the optimal path to a
destination.
Unicast 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. 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. In routing, however, the cost of an edge has a different interpretation in different routing
protocols. 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.3.29 shows how an internet can be
modeled as a graph.
2 .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
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.

Figure.3.29 An internet and its graphical representation

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.
UNIT-3 28 CS8591- COMPUTER NETWORKS
In this way, we can have only one shortest-path tree for each node; we have N least-cost trees for
the whole internet.

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.
1. DISTANCE-VECTOR ROUTING
The distance-vector (DV) routing is used to find the best route. Each node creates is its
own least-cost tree with the rudimentary information it has about its immediate neighbors.
A router continuously tells all of its neighbors what it knows about the whole internet.
There are two important topics: the Bellman-Ford equation and the concept of distance vectors.
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:

Distance Vectors
• A least-cost tree is a combination of least-cost paths from the root of the tree to all
destinations.
• It creates a distance vector, a one-dimensional array to represent the tree. Figure.3.30
shows the tree for node A and the corresponding distance vector.
• Note that the name of the distance vector defines the root, the indexes define the
destinations, and the value of each cell defines the least cost from the root to the
destination.
• 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.
• Each node in an internet, when it is booted, creates a very basic 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.
UNIT-3 29 CS8591- COMPUTER NETWORKS
Figure.3.30 The distance vector corresponding to a tree
• 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. When we know only
one distance between two nodes, it is the least cost.

Figure.3.31 The first distance vector for an internet

• These basic 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 . 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.

Figure.3.32 Updating distance vectors

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.
UNIT-3 30 CS8591- COMPUTER NETWORKS
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 need to remember that after updating a node, it immediately sends its updated vector to all
neighbors.
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.
Distance-Vector Routing Algorithm
Distance_Vector_Routing ( )
{
// Initialize (create initial vectors for the node)
D[myself ] = 0
for (y = 1 to N)
{
if (y is a neighbor)
D[y] = c[myself ][y]
else
D[y] = ∞
}
send vector {D[1], D[2], …, D[N]} to all neighbors
// Update (improve the vector with the vector received from a neighbor)
repeat (forever)
{
wait (for a vector Dw from a neighbor w or any change in the link)
for (y = 1 to N)
{
D[y] = min [D[y], (c[myself ][w] + Dw[y ])] // Bellman-Ford equation
}
if (any change in the vector)
send vector {D[1], D[2], …, D[N]} to all neighbors
}
} // End of Distance Vector
2. LINK STATE ROUTING
A routing algorithm creates 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; if the cost of a link is infinity, it means that
the link does not exist or has been broken.
Link-State Database (LSDB)
UNIT-3 31 CS8591- COMPUTER NETWORKS
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 in Figure.3.33. 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.

Figure.3.33 Example of a link-state database

Each node can create this LSDB that contains information about the whole internet. This
can be done by a process called flooding. Each node can send some greeting messages to all its
immediate neighbors (those nodes to which it is connected directly) to collect two pieces of
information for each neighboring node: the identity of the node and the cost of the link.
The combination of these two pieces of information is called the LS packet (LSP); the
LSP is sent out of each interface, as shown in Figure.3.34.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. This guarantees that flooding stops somewhere in
the network (where a node has only one interface).

Figure.3.34 LSPs created and sent out by each node to build LSDB
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.
UNIT-3 32 CS8591- COMPUTER NETWORKS
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.

Figure.3.35 Least-cost tree

Dijkstra’s Algorithm ( )
{
// Initialization
Tree = {root} // Tree is made only of the root
for (y = 1 to N) // N is the number of nodes
{
if (y is the root)
D[y] = 0 // D[y] is shortest distance from root to node y
else if (y is a neighbor)
D[y] = c[root][y] // c[x][y] is cost between nodes x and y in LSDB
else
D[y] = ∞
}
// Calculation
repeat
{
find a node w, with D[w] minimum among all nodes not in the Tree
UNIT-3 33 CS8591- COMPUTER NETWORKS
Tree = Tree ∪ {w} // Add w to tree
// Update distances for all neighbors of w
for (every node x, which is a neighbor of w and not in the Tree)
{
D[x] = min{D[x], (D[w] + c[w][x])}
}
} until (all nodes included in the Tree)
} // End of Dijkstra

PATH-VECTOR ROUTING
Least-cost routing does not prevent a packet from passing through an area when that area
is in the least-cost path. In other words, 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.
Aside from safety and security in which the goal of routing is merely reach ability: to
allow the packet to reach its destination more efficiently without assigning costs to the route. To
respond to these demands, a third routing algorithm, called path-vector (PV) routing has been
devised.
Path-vector routing does not have the drawbacks of LS or DV routing as described above
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.3.36 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.

Figure.3.36 Spanning trees in path-vector routing

UNIT-3 34 CS8591- COMPUTER NETWORKS
Creation of Spanning Trees
When a node is booted, it creates a path vector based on the information it can obtain
about its immediate neighbor. A node sends greeting messages to its immediate neighbors to
collect these pieces of information.
Figure.3.37 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

In this equation, the operator (+) means to add x to the beginning of the path. We also
need to be cautious to avoid adding a node to an empty path because an empty path means one
that does not exist.

Figure.3.37 Path vectors made at booting time

The policy is defined by selecting the best of multiple paths. Path-vector routing also
imposes one more condition on this equation: If Path (v, y) includes x, that path is discarded to
avoid a loop in the path. In other words, x does not want to visit itself when it selects a path to y.
Figure.3.38 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. As a
matter of fact the vector for node C after the first event is stabilized and serves as its forwarding
table.

Figure.3.38 Updating path vectors

Vector_Routing ( )
{
// Initialization
for (y = 1 to N)
{
UNIT-3 35 CS8591- COMPUTER NETWORKS
if (y is myself)
Path[y] = myself
else if (y is a neighbor)
Path[y] = myself + neighbor node
else
Path[y] = empty
}
Send vector {Path[1], Path[2], …, Path[y]} to all neighbors
// Update
repeat (forever)
{
wait (for a vector Pathw from a neighbor w)
for (y = 1 to N)
{
if (Pathw includes myself)
discard the path // Avoid any loop
else
Path[y] = best {Path[y], (myself + Pathw[y])}
}
If (there is a change in the vector)
Send vector {Path[1], Path[2], …, Path[y]} to all neighbors
}
} // End of Path Vector
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. We can
see the similarities between this algorithm and the DV algorithm.

UNICAST ROUTING PROTOCOLS

There are three common protocols used in the Internet. Routing protocols are broadly classified
as:
1. Intra domain routing
– Distance vector routing (An Adaptive Routing Algorithm) (eg. RIP)
– Link state routing (An Adaptive Routing Algorithm) (eg. OSPF)
2. Inter domain routing
– Path vector (eg. BGP)
Routing Information Protocol (RIP)
The Routing Information Protocol (RIP) is one of the most widely used intradomain
routing protocols based on the distance-vector routing algorithm.
Hop Count
First the cost is defined between a router and the network in which the destination host is
located. Second, to make the implementation of the cost simpler, 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.
UNIT-3 36 CS8591- COMPUTER NETWORKS
Figure.3.39 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.

Figure.3.39 Hop counts in RIP

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

Figure.3.40 Forwarding tables

For example, R1 defines that the next router for the path to N4 is R2; R2 defines that the
next router to N4 is R3; R3 defines that there is no next router for this path. The tree is then R1 -
>R2 -> R3 -> N4.
RIP Implementation
RIP is implemented as a process that uses the service of UDP on the well-known port
number 520. 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. 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.
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.3.41. 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.
UNIT-3 37 CS8591- COMPUTER NETWORKS

Figure.3.41 RIP message format

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. 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.
❑ The new forwarding table needs to be sorted according to the destination route.
Open Shortest Path First Protocol ( 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. An interesting point
about the cost in OSPF is that different service types (TOSs) can have different weights as the
cost. Figure 20.19 shows the idea of the cost from a router to the destination host network. We
can compare the figure with Figure.3.42 for the RIP.
UNIT-3 38 CS8591- COMPUTER NETWORKS

Figure.3.42 Metric in OSPF

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. 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. The reason for this
consistency is that both protocols use the shortest-path trees to define the best route from a
source to a destination.
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. In other words,
OSPF uses another level of hierarchy in routing: the first level is the autonomous system, the
second is the area.

Figure.3.43 Forwarding tables in OSPF

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. For the purpose of
communication, each area has area identification. The area identification of the backbone is zero.
Link-State Advertisement
OSPF is based on the link-state routing algorithm, which requires that a router advertise
the state of each link to all neighbors for the formation of the LSDB. When we discussed the
link-state algorithm, we used the graph theory and assumed that each router is a node and each
network between two routers is an edge. The situation is different in the real world, in which we
UNIT-3 39 CS8591- COMPUTER NETWORKS
need to advertise the existence of different entities as nodes, the different types of links that
connect each node to its neighbors, and the different types of cost associated with each link. This
means we need different types of advertisements, each capable of advertising different situations.
We can have five types of link-state advertisements: router link, network link, summary link to
network, summary link to AS border router, and external link.
OSPF Implementation
OSPF is implemented as a program in the network layer, using the service of the IP for
propagation. An IP datagram that carries a message from OSPF sets the value of the protocol
field to 89. This means that, although OSPF is a routing protocol to help IP to route its datagrams
inside an AS, the OSPF messages are encapsulated inside datagrams. OSPF has gone through
two versions: version 1 and version 2. Most implementations use version 2.
OSPF Messages
OSPF is a very complex protocol; it uses five different types of messages. In Figure.3.44,
we first show the format of the OSPF common header 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.

Figure.3.44 OSPF message formats

UNIT-3 40 CS8591- COMPUTER NETWORKS
The linkstate request message (type 3) is sent by a router that needs information about
specific LS. The link-state update message (type 4) is the main OSPF message used for building
the LSDB. This message, in fact, has five different versions (router link, network link, summary
link to network, summary link to AS border router, and external link), as we discussed before.
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.
Authentication
OSPF common header has the provision for authentication of the message sender.
OSPF Algorithm
OSPF implements the link-state routing algorithm. However, some changes and
augmentations need to be added to the algorithm:
❑ After each router has created the shortest-path tree, the algorithm needs to use it to create the
corresponding routing algorithm.
❑ The algorithm needs to be augmented to handle sending and receiving all five types of
messages.

INTERDOMAIN ROUTING
– The interdomain routing involves AS sharing their reach ability information with each
other AS.
– An Autonomous System (AS) is a connected segment of a network topology that consists
of a collection of sub networks (with hosts attached) interconnected by a set of routes.
– The goal of interdomain routing is reachability and not optimality.
– The two major interdomain routing protocols are
a. ExteriorGatewayProtocol(EGP)
b. BorderGateway Protocol (BGP).
Problems in interdomain routing
– An internet backbone must be able to route packets to any destination, i.e., there should
be a match in the routing/forwarding table.
– Each AS has its own intradomain routing protocols and chooses the metric assigns to
path. This varies from one AS to another.
– Autonomous systems may not trust each other.
Border Gateway Protocol (BGP)
1. Border Gateway Protocol (BGP) is an inter-domain routing protocol using path vector
routing
2. Traffic on the internet can be classified into two types:
- local traffic that starts/ends on nodes within an AS
- transit traffic that passes through an AS
3. AS can be classified into three types
– Stub AS has only a single connection to one other AS. This AS can carry local
traffic only, such as Small Corporation.
– Multihomed AS has connections to more than one other AS but refuses to carry
transit traffic, such as Large Corporation.
– Transit AS has connections to more than one other AS and is designed to carry
both transit and local traffic, such as the backbone providers as in fig.3.45.
UNIT-3 41 CS8591- COMPUTER NETWORKS

Figure.3.45 Today’s multibackbone internet

4. Each AS selects one of its nodes to be the BGP speaker.
5. Speaker node creates a routing table for that AS and advertises it to other BGP speakers
in the neighboring ASs.
6. Each AS also has a border gateway through which packets enter and leave the AS.
7. BGP advertises complete paths as an enumerated list of ASs to reach a particular
network. BGP ensures that paths are loop-free.
8. The attributes in a path can be well known or optional. The well known attributes are
recognized by all routers.
9. If there are different routes to a destination, the BGP speaker chooses the best one
according to local policies, and then advertises.
10. A BGP speaker need not advertise any route to a destination, even if it has one.
11. In the following example fig.3.46, the BGP speaker for provider A (AS2) advertises that
the networks 128.96, 192.4.153, 192.4.32, and 192.4.3 can be reached directly from
AS2.
12. The backbone network, on receiving this advertisement, advertises that networks 128.96,
192.4.153, 192.4.32, and 192.4.3 can be reached along the path (AS1, AS2).

Figure.3.46 Example of a network running BGP

13. BGP speakers can cancel previously advertised paths if a critical link or node on a path
goes down. This negative advertisement is known as withdrawn route.
14. The format of BGP-4 update message that carries advertisement is shown below.
UNIT-3 42 CS8591- COMPUTER NETWORKS

Figure.3.47 BGP-4 update packet format

BGP Sessions
1. The exchange of routing information between two routers takes place in a BGP session.
2. To create a reliable environment, BGP uses the services of TCP.
3. The routes need not be repeatedly sent, if there is no change. This is done by sending
keep alive messages.
4. Two types of BGP session are external BGP (E-BGP) and internal BGP (I-BGP).
– E-BGP is used to exchange routing information between two speaker nodes
belonging to two different ASs.
– I-BGP is used to exchange routing information between two routers inside an
AS.
MULTICASTING BASICS
 Multicast (one-to-many or many-to-many distribution) is group communication where
information is addressed to a group of destination computers simultaneously.
 There are also applications whose communication is many-to-many, such as multimedia
teleconferencing, online multiplayer gaming, or distributed simulations.
 In such cases, members of a group receive data from multiple senders, typically each
other. From any particular sender, they all receive the same data.
 To better support many-to-many and one-to-many communication, IP provides an IP-
level multicast analogous to the link-level multicast provided by multi-access networks
like Ethernet.
 The basic IP multicast model is a many-to-many model based on multicast groups, where
each group has its own IP multicast address.
 The hosts that are members of a group receive copies of any packets sent to that group’s
multicast address.
 A host can be in multiple groups, and it can join and leave groups freely by telling its
local router using a protocol that we will discuss shortly.
Multicast Addresses
 IP has a sub range of its address space reserved for multicast addresses. In IPv4, these
addresses are assigned in the class D address space, and IPv6 also has a portion of its
address space reserved for multicast group addresses.
 Some sub ranges of the multicast ranges are reserved for intradomain multicast, so they
can be reused independently by different domains.
 There are thus 28 bits of possible multicast address in IPv4 when we ignore the prefix
shared by all multicast addresses.
 This presents a problem when attempting to take advantage of hardware multicasting on a
local area network (LAN).
UNIT-3 43 CS8591- COMPUTER NETWORKS
 Ethernet multicast addresses have only 23 bits when we ignore their shared prefix.
 In other words, to take advantage of Ethernet multicasting, IP has to map 28-bit IP
multicast addresses into 23-bit Ethernet multicast addresses.
 This is implemented by taking the low-order 23 bits of any IP multicast address to use as
its Ethernet multicast address and ignoring the high order 5 bits. Thus, 32 (25) IP
addresses map into each one of the Ethernet addresses.
 When a host on an Ethernet joins an IP multicast group, it configures its Ethernet
interface to receive any packets with the corresponding Ethernet multicast address.
 Unfortunately, this causes the receiving host to receive not only the multicast traffic it
desired but also traffic sent to any of the other 31IP multicast groups that map to the same
Ethernet address, if they are routed to that Ethernet.
 Therefore, IP at the receiving host must examine the IP header of any multicast packet to
determine whether the packet really belongs to the desired group.
MULTICAST ROUTING
In this section, we first discuss the idea of optimal routing, common in all multicast
protocols. We then give an overview of multicast routing protocols.
Optimal Routing: Shortest Path Trees
– The process of optimal interdomain routing eventually results in the finding of the
shortest path tree. The root of the tree is the source, and the leaves are the potential
destinations.
– The path from the root to each destination is the shortest path. However, the number of
trees and the formation of the trees in unicast and multicast routing are different.
Unicast Routing and Multicast Routing
– In unicast routing, each router in the domain has a table that defines a shortest path tree to
possible destinations.
– In multicast routing, each involved router needs to construct a shortest path tree for each
group.
Source-Based Tree
– In the source-based tree approach, each router needs to have one shortest path tree for
each group.
– The shortest path tree for a group defines the next hop for each network that has loyal
member(s) for that group.
– In Fig.3.48, we assume that we have only five groups in the domain: G1,G2, G3, G4, and
G5.At the moment G1 has loyal members in four networks, G2 in three, G3 in two, G4 in
two, and G5 in two.
– We have shown the names of the groups with loyal members on each network. Fig. also
shows the multicast routing table for router R1.
– There is one shortest path tree for each group; therefore there are five shortest path trees
for five groups.
– If router Rl receives a packet with destination address G1, it needs to send a copy of the
packet to the attached network, a copy to router R2, and a copy to router R4 so that all
members of G1 can receive a copy.
– In this approach, if the number of groups is m, each router needs to have m shortest path
trees, one for each group.
UNIT-3 44 CS8591- COMPUTER NETWORKS

Figure.3.48 Source-based tree approach

Group-Shared Tree
– In the group-shared tree approach, instead of each router having m shortest path trees,
only one designated router, called the center core, or rendezvous router, takes the
responsibility of distributing multicast traffic.
– The core has m shortest path trees in its routing table. The rest of the routers in the
domain have none.
– If a router receives a multicast packet, it encapsulates the packet in a unicast packet and
sends it to the core router.
– The core router removes the multicast packet from its capsule, and consults its routing
table to route the packet. Fig.3.49 shows the idea.

Figure.3.49 Group-shared tree approach

Routing Protocols
– Some of multicast routing protocols are extensions of unicast routing protocols; others
are totally new. Fig.3.50 shows the taxonomy of common multicast protocols.
UNIT-3 45 CS8591- COMPUTER NETWORKS

Figure.3.50 Taxonomy of common multicast protocols

a. Multicast Link State Routing: MOSPF
Multicast link state routing uses the source-based tree approach. links. For multicast
routing, a node needs to revise the interpretation of state. A node advertises every group which
has any loyal member on the link. Here the meaning of state is "what groups are active on this
link." The information about the group comes from IGMP. Each router running IGMP solicits
the hosts on the link to find out the membership status.
MOSPF Multicast Open Shortest Path First (MOSPF) protocol is an extension of
theOSPF protocol that uses multicast link state routing to create source-based trees. The protocol
requires a new link state update packet to associate the unicast address of a host with the group
address or addresses the host is sponsoring. This packet is called the group-membership LSA.
b. Multicast Distance Vector: DVMRP
Unicast distance vector routing is very simple; extending it to support multicast routing is
complicated. Multicast routing does not allow a router to send its routing table to its neighbors.
The idea is to create a table from scratch by using the information from the unicast distance
vector tables.
Multicast distance vector routing uses source-based trees, but the router never actually makes a
routing table. When a router receives a multicast packet, it forwards the packet as though it is
consulting a routing table.
1. Flooding
2. Reverse Path Forwarding (RPF)
3. Reverse Path Broadcasting (RPB)
4. Reverse Path Multicasting (RPM)
1. Flooding
– A router receives a packet and, without even looking at the destination group address,
sends it out from every interface except the one from which it was received.
– There is a problem which creates loops. A packet that has left the router may come back
again from another interlace or the same interlace and be forwarded again.
– Some flooding protocols keep a copy of the packet for a while and discard any duplicates
to avoid loops. The next strategy, reverse path forwarding, corrects this defect.
2. Reverse Path Forwarding (RPF)
– RPF is a modified flooding strategy. To prevent loops, only one copy is forwarded; the
other copies are dropped.
– Fig.3.51 shows part of a domain and a source. The shortest path tree as calculated by
routers R1, R2, and R3 is shown by a thick line.
– When R1 receives a packet from the source through the interface rn1, it consults its
routing table and finds that the shortest path from R1 to the source is through interface
UNIT-3 46 CS8591- COMPUTER NETWORKS
m1. The packet is forwarded. However, if a copy of the packet has arrived through
interface m2, it is discarded because m2 does not define the shortest path from R1 to the
source. The story is the same with R2 and R3.
– You may wonder what happens if a copy of a packet that arrives at the ml interface of R3
travels through R6, R5, R2, and then enters R3 through interface ml.
– This interface is the correct interface for R3. When the packet goes from R5 to R2, it will
be discarded by R2 and never reaches R3.
– The upstream routers toward the source always discard a packet that has not gone through
the shortest path, thus preventing confusion for the downstream routers.

Figure.3.51 Reverse path forwarding (RPF)

3. Reverse Path Broadcasting (RPB)
– RPF guarantees that each network receives a copy of the multicast packet without
formation of loops. However, RPF does not guarantee that each network receives only
one copy; a network may receive two or more copies.
– Because RPF is not based on the destination address (a group address); forwarding is
based on the source address.

Figure.3.52 Problem with RPF

– Net3 in this figure receives two copies of the packet even though each router just sends
out one copy from each interface.
UNIT-3 47 CS8591- COMPUTER NETWORKS
– There is duplication because a tree has not been made; instead of a tree we have a graph.
Net3 has two parents: routers R2 andR4.To eliminate duplication, we must define only
one parent router for each network.
– We must have this restriction: A network can receive a multicast packet from a particular
source only through a designated parent router.
– For each source, the router sends the packet only out of those interfaces for which it is the
designated parent. This policy is called reverse path broadcasting (RPB).
– RPB guarantees that the packet reaches every network and that every network receives
only one copy.
4. Reverse Path Multicasting (RPM)
– RPB does not multicast the packet, it broadcasts it. This is not efficient. To increase
efficiency, the multicast packet must reach only those networks that have active members
for that particular group. This is called reverse path multicasting (RPM).
– To convert broadcasting to multicasting, the protocol uses two procedures, pruning and
grafting.Fig.3.53 shows the idea of pruning and grafting. The designated parent router of
each network is responsible for holding the membership information. This is done
through the IGMP protocol.
– The router sends a prune message to the upstream router so that it can exclude the
corresponding interface. That is, the upstream router can stop sending multicast messages
for this group through that interface.
– Now if this router receives prune messages from all downstream routers, it, in turn, sends
a prune message to its upstream router.

Figure.3.53 RPF, RPB, and RPM

– What if a leaf router has sent a prune message but suddenly realizes, through IGMP, that
one of its networks is again interested in receiving the multicast packet?
– It can send a graft message. The graft message forces the upstream router to resume
sending the multicast messages.
DVMRP
The Distance Vector Multicast Routing Protocol (DVMRP) is an implementation of
multicast distance vector routing. It is a source-based routing protocol, based on RIP.
c. CBT
– The Core-Based Tree (CBT) protocol is a group-shared protocol that uses a core as the
root of the tree. The autonomous system is divided into regions, and a core (center router
or rendezvous router) is chosen for each region.
UNIT-3 48 CS8591- COMPUTER NETWORKS
– The Core-Based Tree (CBT) is a group-shared tree, center-based protocol using one tree
per group. One of the routers in the tree is called the core. A packet is sent from the
source to members of the group following this procedure:
a) The source, which may or may not be part of the tree, encapsulates the multicast
packet inside a unicast packet with the unicast destination address of the core and sends it
to the core. This part of delivery is done using a unicast address; the only recipient is the
core router.
b) The core decapsulates the unicast packet and forwards it to all interested intetfaces.
c) Each router that receives the multicast packet, in tum, forwards it to all interested
interfaces.
d. PIM
Protocol Independent Multicast (PIM) is the name given to two independent
multicastrouting protocols: Protocol Independent Multicast, Dense Mode (PIM-DM) and
Protocol Independent Multicast, Sparse Mode (PIM-SM). Both protocols are unicast protocol-
dependent, but the similarity ends here.
PIM-DM
PIM-DM is a source-based tree routing protocol that uses RPF and pruning and grafting
strategies for multicasting. Its operation is like that of DVMRP.
PIM-SM
PIM-SM is used in a sparse multicast environment such as a WAN. PIM-SM is a group-
shared tree routing protocol that has a rendezvous point (RP) as the source of the tree.

IPV6 ADDRESSING
An IPv6 address is 128 bits or 16 bytes (octets) long, four times the address length in IPv4.
Notation, representation and address space of IPv6
1. Although IPv4 is well designed and has helped the internet to grow rapidly, it has some
deficiencies, these deficiencies has made it unsuitable for the fast growing internet.
2. To overcome these deficiencies, Internet Protocol, Version 6 protocol has been proposed
and it has evolved into a standard.
3. CIDR and sub netting could not solve the address exhaustion faced by IPv4. IPv6 was
evolved to solve this problem.
4. Important features of IPv6 are highlighted below:
– IPv6 uses 128-bit address instead of 32-bit address to provide larger address space
– Resource Allocation options, which was not present in IPv4
– Support for security with the help of encryption and authentication
– Support for fragmentation at source
Addresses Space
1. IPv6 provides a 128-bit address space as opposed to IPv4's 32-bit.
2. IPv6 addresses do not have classes, but classification is based on the leading bits.
3. Large chunks of address space are left unassigned to allow for new features in the future.
4. The address spaces (0000 001 and 0000 010) are reserved for non-IP address such as IPX
5. Link local address enables a host to configure address automatically that works on the
local network.
6. Site local address allows valid addresses on a private network which is not connected to
internet.
7. Multicast address (start with a byte of 1s) serves the purpose of class D address.
UNIT-3 49 CS8591- COMPUTER NETWORKS
Address Notation
1. The standard representation is x: x: x: x: x: x: x: x where x is a hexadecimal representation
of a 16-bit address separated by colon (:) as shown below
47CD:1234:4422:ACO2:0022:1234:A456:0124
2. An IPv6 address with a large number of contiguous 0s is written compactly by omitting
the 0 fields as shown below
47CD:0000:0000:0000:0000:0000:A456:0124 is written as 47CD:: A456:0124
3. An IPv4 address can be mapped to IPv6 address by prefixing the 32-bit IPv4 address with
2 bytes of all 1s and then zero-extending the result to 128 bits.
128. 96.33.81 is written as: FFFF: 128.96.33.81
Aggregatable Global Unicast Addresses
1. The goal of the IPv6 address allocation plan is to provide aggregation of routing
information to reduce the burden on intradomain routers.
2. Aggregation is done by assigning prefixes at continental level.
3. Continental boundaries form natural divisions in the Internet topology.
4. For example, if all addresses in Europe have a common prefix, then routers in other
continents would need one routing table entry for all networks in Europe.
The format for provider-based unicast address aggregation is shown below.

Figure.3.54 An ipv6 provider-based unicast address

– RegistryID contains identifier assigned to the continent. It is either INTERNIC (North
America), RIPNIC (Europe) or APNIC (Asia and Pacific)
– ProviderID variable-length field identifies the provider for Internet access such as an ISP.
– SubscriberID specifies the assigned subscriber identifier
– SubnetID defines a specific subnet under the territory of subscriber.
– InterfaceID contains the link level or physical address.

IPv6 PROTOCOL
The change of the IPv6 address size requires the change in the IPv4 packet format.
Packet Format
The IPv6 base header is always 40 bytes long. The packet format (as in fig.3.37) and field
description are as follows:
Version—specifies the IP version, i.e., 6.
TrafficClass—defines the priority of the packet with respect to traffic congestion. It is
either congestion-controlled or non-congestion controlled
FlowLabel—is designed to provide special handling for a particular flow of data. The
router handles flow with the help of a flow table.
PayloadLen—gives the length of the packet, excluding the IPv6 header
NextHeader—If options are required, then it is specified in one or more special headers
following the IP header, its value is contained in NextHeader field. Otherwise, it
identifies the higher-level protocol (TCP/UDP).
HopLimit—this field serves the same purpose as TTL field in IPv4.
SourceAddress and DestinationAddress—contain 16-byte address of the source and
destination host respectively.
UNIT-3 50 CS8591- COMPUTER NETWORKS

Figure.3.55 Ipv6 packet Header

Extension Header
1. To provide greater functionality to IP datagram, the base header can be followed by up to six
extension headers.
2. IPv6 treats options as extension headers, if present must appear in a specific order.
3. Each option has its own type of extension header.
4. The six types of extension header are:
a. Hop-by-Hop-This header is used when the source needs to pass information to all
routers visited by the datagram.
b. Source routing-this header accounts for both strict and loose source routing.
c. Fragmentation-In IPv6, only the original source can fragment. A source must use
a path MTU discovery technique to find the smallest MTU on the path. This
header is present only if fragmentation exists.
d. Authentication-This header validates the sender and ensures the integrity of data
e. Encrypted Security Payload-The ESP header provides confidentiality and guards
against eavesdropping.
f. Destination-This header is used when source needs to pass information to
destination only. Intermediate routers cannot access this information.
The header format is

Figure.3.56 Ipv6 fragmentation extension header

Advantages of IPv6
1. Large address space An IPv696 address is 128 bits long. Compared with the 32-bit
address of IPv4, this is a huge (2) increase in the address space.
2. Better header format IPv6 uses a new header format in which options are separated
from the base header and inserted, when needed.
3. New options IPv6 has new options to allow for additional functionalities.
4. Allowance for extension IPv6 is designed to allow the extension of the protocol if
required by new technologies or applications.
5. Support for resource allocation In IPv6, flow label has been added to enable the source
to request special handling of the packet such as real-time audio and video.
6. Support for more security The encryption and authentication options in IPv6 provide
confidentiality and integrity of the packet.
UNIT-3 51 CS8591- COMPUTER NETWORKS
Drawbacks of IPv4
1. Despite all short-term solutions, such as sub netting, classless addressing, and NAT,
address depletion is still a long-term problem in the Internet.
2. The Internet must accommodate real-time audio and video transmission that requires
minimum delay strategies and reservation of resources, which are not provided in IPv4.
3. The Internet must provide encryption and authentication of data for some applications.
4. No encryption or authentication is provided by IPv4.
Comparison of Options between IPv4 and IPv6
The following shows a quick comparison between the options used in IPv4 and the options used
in IPv6 (as extension headers).
❑ The no-operation and end-of-option options in IPv4 are replaced by Pad1 and PadN options in
IPv6.
❑ The record route option is not implemented in IPv6 because it was not used.
❑ The timestamp option is not implemented because it was not used.
❑ The source route option is called the source route extension header in IPv6.
❑ The fragmentation fields in the base header section of IPv4 have moved to the fragmentation
extension header in IPv6.
❑ The authentication extension header is new in IPv6.
❑ The encrypted security payload extension header is new in IPv6.

Example-11
An organization is granted the block 130.56.0.0/16. The administrator wants to create 1024
subnets. 1. Find the subnet mask. 2. Find the number of addresses in each subnet. 3. Find the first
and the last address in the first subnet. 4. Find the first and the last address in the last subnet
(subnet 1024).
Answer:
1) 255.255.255.192 will be the subnet mask,
2) 62 valid addresses can exist in each subnet,
3) First address in subnet 1 will be 130.56.0.1 and last address is subnet 1 will be 130.56.0.62,
4) First address is 1024 subnet will be 130.56.255.193 and last address in 1024 subnet will be
130.56.255.254.
Explanation:
1)2^n = 1024
Therefore, n = 10.
The address is here is a Class B , so, the default mask is /16. 10 bits are necessary for subnets
and hence the correct subnet mask is /(16+10) = /26.
In the format of dotted decimal format, it shall be 192 and therefore, the subnet mask will be
255.255.255.192.
2) The rest of the bits must be used for the addressed i.e. there will be 32 - 26 = 6 bits available
for the address component.
So, a total of 2^6=64 bits shall be available. Also, 2 bits per subnet cannot be allocated and
subnet mask will be able to maintain 62 valid addresses
3) First address in subnet 1 = 130.56.0.1
Last address is subnet 1 = 130.56.0.62
The first address can be estimated by ANDing the address 130.56.0.0 with the subnet mask /26
like below: 10000010 00111000 00000000 00000000 (130.56.0.0)
UNIT-3 52 CS8591- COMPUTER NETWORKS
This address cannot be allocated, so we will consider the next address: 10000010 00111000
00000000 00000001 (130.56.0.1).
In Similar manner, the last address that can be allocated before the broadcast address will be
130.56.0.62.
4) First address in the 1024 subnet = 130.56.255.193
Last address in 1024 subnet = 130.56.255.254
UNIT-3 53 CS8591- COMPUTER NETWORKS
2-Marks
1. What is routing?
Routing is a process of selecting paths in a network through which network traffic is sent.
2. State the duties of network layer (or) what are the services offered by network layer?
(or) what are the responsibilities of Network Layer?
 Responsible for the source to destination delivery of a packet.
 Logical addressing
 Routing
3. What is multicast? What is the motivation for developing multicast?
Multicasting means delivering the same packet simultaneously to a group of clients.
Motivation for developing multicast is that there are applications that want to send a packet to
more than one destination hosts.
4. Define sub netting.
Sub netting is a technique that allows a network administrator to divide one physical
network into smaller logical networks and thus, control the flow of traffic for security.
5. What is IP addressing?
An IP address is a numerical label assigned to each divide in a computer network that
uses internet protocol for communication.
Two important functions at IP address 1.Host identification 2.Location addressing
6. What are the salient features of IPv6?
Salient features are:
1. Efficient and hierarchical addressing and routing infrastructures.
2. IPv6 networks provide auto configuration capabilities.
3. Better support for QOS.
4. Large Address space.
5. Stateless and stateful address configuration.
7. Define packet switching.
A packet switch is a device with several inputs and outputs leading to and from the
hosts that the switch interconnects.
8. What is a virtual circuit?
A logical circuit made between the sending and receiving computers. The connection is
made after both computers do handshaking. After the connection, all packets follow the same
route and arrive in sequence.
9. What are data grams?
In datagram approach, each packet is treated independently from all others. Even when
one packet represents just a place of a multi packet transmission, the network treats it although
it existed alone. Packets in this technology are referred to as datagram.
10. What is VCI?
A Virtual Circuit Identifier that uniquely identifies the connection at this switch, and
which will be carried inside the header of the packets that belongs to this connection.
11. How the packet cost referred in distance vector and link state routing?
In distance vector routing, cost refer to hop count while in case of link state routing,
cost is a weighted value based on a variety of factors such as security levels, traffic or the
state of the link.
UNIT-3 54 CS8591- COMPUTER NETWORKS
12. Define Reliable flooding?
It is the process of making sure that all the nodes participating in the routing protocol
get a copy of the link state information from all the other nodes.
13. What are the features in OSPF?
• Authentication of routing messages.
• Additional hierarchy.
• Load balancing.
14. What are the rules of non-boundary level masking?
• The bytes in the IP address that corresponds to 255 in the mask will be repeated in
the sub network address
• The bytes in the IP address that corresponds to 0 in the mask will change to 0 in the
sub network address
• For other bytes, use the bit-wise AND operator.
15. What is LSP?
In link state routing, a small packet containing routing information sent by a router to all
other router by a packet called link state packet.