lOMoARcPSD|28201683

COMPUTER NETWORKS

MODULE-3: NETWORK LAYER

1. NETWORK-LAYER
1.1 Network Layer Services
1.2 Packet Switching
1.3 IPv4 Addresses
1.4IPv4 Datagram
1.5 IPv6 Datagram
2. INTRODUCTION TO ROUTING ALGORITHMS
2.1 Introduction
2.2 Routing Algorithms
2.3 Unicast Routing Protocols:DVR, LSR, PVR
2.4 Unicast Routing Protocols:RIP, OSPF,BGP
2.5 Multicast Routing:MOSPF

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 1

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

1. NETWORK-LAYER

The network layer in the TCP/IP protocol suite plays a crucial role in ensuring host-to-host
delivery of data. It operates between the data-link layer and the transport layer, providing services
to the latter while receiving services from the former. It is responsible for routing and delivering
packets across various networks, encapsulating data into packets, and decapsulating them at the
destination.
1.1 Network Layer Services

The Internet, a combination of LANs and WANs, consists of many networks connected through
routers and switches. The network layer is involved in:

• Source Host (e.g., Alice): It encapsulates the transport layer packet into a datagram and
hands it over to the data-link layer for transmission.

• Destination Host (e.g., Bob): It decapsulates the received datagram to retrieve the packet and
deliver it to the transport layer.

• Routers (R2, R4, R5, R7): They forward the datagrams across multiple networks until they
reach the destination.

Figure 3.1:Communication at the network layer

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 2

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Functions of the Network Layer

1. Packetizing:

o The network layer encapsulates data from the transport layer into packets (datagrams)
at the source and decapsulates them at the destination.

o The source adds necessary headers, including source and destination addresses, to the
packet.

2. Routing:

o The network layer selects the best route for packets to travel across multiple
networks (LANs, WANs).

o Routers use algorithms to determine the most efficient path from source to
destination.

3. Forwarding:

o Forwarding refers to how routers handle packets upon arrival. Routers look up the
forwarding table or routing table to determine which network interface to send the
packet through.

o The decision is based on packet headers (e.g., destination address, labels).

Figure 3.2: Forwarding process

Additional Services Provided by the Network Layer

• Error Control:

o Although the network layer itself doesn’t handle errors directly, the ICMP protocol
helps detect errors, such as when a packet cannot be delivered.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 3

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• Flow Control:

o The network layer helps prevent the receiver from becoming overwhelmed with data
by ensuring the sender doesn't send more data than the receiver can process.

• Congestion Control:

o The network layer helps in managing and avoiding congestion in the network by
controlling the flow of packets, especially in high-traffic conditions.

• Quality of Service (QoS):

o QoS ensures the network layer delivers data with a certain performance level,
managing delays, throughput, and packet loss.

1.2 Packet Switching

➢ Packet switching is a method of data transmission in which information is broken into small,
manageable pieces called packets. Each packet is sent independently through a network, and
they may take different routes to reach the destination. Once all packets arrive, they are
reassembled in the correct order to recreate the original message
➢ Although in data communication switching techniques are divided into two broad categories,
circuit switching and packet switching, only packet switching is used at the network layer
because the unit of data at this layer is a packet.
➢ Circuit switching is mostly used at the physical layer; the electrical switch mentioned earlier
is a kind of circuit switch.
➢ At the network layer, a message from the upper layer is divided into manageable packets and
each packet is sent through the network.
➢ The source of the message sends the packets one by one; the destination of the message
receives the packets one by one.
➢ The destination waits for all packets belonging to the same message to arrive before
delivering the message to the upper layer

Today, a packet-switched network can use two different approaches to route the packets: the
datagram approach and the virtual circuit approach.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 4

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Types of Packet Switching:

• Datagram Packet Switching:

o Each packet is treated independently with no pre-established path.
o Routing decisions are made for each packet at every node.
o Examples: User Datagram Protocol (UDP).

Fig 3.3: A connectionless packet-switched network

• Virtual Circuit Packet Switching:

o A logical path (virtual circuit) is established between sender and receiver before any
packets are sent.
o Packets follow the same route, which helps maintain the order of transmission.
o Examples: Transmission Control Protocol (TCP), Frame Relay.

Fig 3.4 A virtual-circuit packet-switched network

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 5

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

The virtual-circuit approach is a type of connection-oriented service used in data communication

networks. Before transmitting data, a logical connection, known as a virtual circuit, is established
between the sender and receiver. All data packets then follow this predefined path throughout the
communication session.

Fig 3.5: Forwarding process in a router when used in a virtual-circuit network

➢ To create a connection-oriented service, a three-phase process is used: setup, data transfer,

and teardown.
➢ In the setup phase, the source and destination addresses of the sender and receiver are used to
make table entries for the connection-oriented service.
➢ In the teardown phase, the source and destination inform the router to delete the
corresponding entries. Data transfer occurs between these two phases.

1. Setup Phase

• Goal: Establish a virtual circuit between Source A and Destination B using request and
acknowledgment packets.
• Steps in Setup:
o Request Packet:
1. Source A sends a request packet to Router R1.
2. Router R1:

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 6

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

▪ Identifies the outgoing port for packets to B (Port 3).

▪ Assigns:
▪ Incoming Port: 1
▪ Incoming Label: 14
▪ Outgoing Port: 3
▪ Forwards the packet to Router R3.
3. Router R3:
▪ Fills its routing table with:
▪ Incoming Port: 1
▪ Incoming Label: 66
▪ Outgoing Port: 3
▪ Forwards the packet to Router R4.
4. Router R4:
▪ Assigns:
▪ Incoming Port: 1
▪ Incoming Label: 22
▪ Outgoing Port: 4
▪ Sends the request packet to Destination B.
5. Destination B assigns Label 77 to incoming packets from A.

Fig: 3.6: Sending request packet in a virtual-circuit network

o Acknowledgment Packet:
1. Destination B sends an acknowledgment packet back to Router R4:
▪ Router R4 fills the outgoing label as 77.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 7

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

2. Router R4 sends the acknowledgment to Router R3, which fills its outgoing
label as 22.
3. Router R3 sends an acknowledgment to Router R1, which fills its outgoing
label as 66.
4. Router R1 sends the acknowledgment to Source A, which fills its outgoing
label as 14 for future packets.

Fig: 3.7: Sending acknowledgments in a virtual-circuit network

2. Data Transfer Phase

• Goal: Transfer data between Source A and Destination B once the virtual circuit is
established.
• Steps:
1. Source A labels the packets with Label 14 (from R1).
2. Router R1:
▪ Receives packets with Label 14.
▪ Changes the label to 66 and forwards to Router R3.
3. Router R3:
▪ Receives packets with Label 66.
▪ Changes the label to 22 and forwards to Router R4.
4. Router R4:
▪ Receives packets with Label 22.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 8

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

▪ Changes the label to 77 and forwards to Destination B.

5. Destination B receives the packets with Label 77 (which it recognizes from setup).

3. Teardown Phase

• Goal: End the virtual circuit once data transmission is complete.

• Steps:
1. Source A sends a teardown packet to Destination B.
2. Destination B responds with a confirmation packet.
3. Each router along the path (R4, R3, R1) deletes the virtual circuit entries from its
routing table.

1.3 IPv4 Datagram

• Packetizing is the primary service provided by IPv4. It defines the format of a packet (called a
datagram) to encapsulate data from the upper layers.
• An IPv4 datagram is a variable-length packet, with a header (20 to 60 bytes) and payload
(data).

• A datagram consists of two main parts:

o Header (20–60 bytes): Contains control and routing information.
o Payload (data): The actual data being transmitted from the upper layers (e.g., TCP/UDP).

Fig 3.8: IPv4 datagram format.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 9

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

IPv4 Datagram Structure

• Header:
o 20 to 60 bytes in length.
o Contains crucial fields to ensure the proper routing and handling of the packet.
o Shown in 4-byte (32-bit) sections for easy reference.
• Payload:
o Contains the data from the upper-layer protocols, such as TCP, UDP, or other
transport or network protocols.

2. Key Header Fields

1. Version (4 bits):
o Specifies the IP version. For IPv4, the value is always 4.
2. Header Length (HLEN) (4 bits):
o Indicates the length of the header in 4-byte words.
o Helps identify where the header ends and the data (payload) begins.
3. Service Type (8 bits):
o Originally called Type of Service (TOS), now redefined as Differentiated Services
(DiffServ).
o Used for prioritizing different types of network traffic (e.g., voice over IP).
4. Total Length (16 bits):
o Specifies the total length of the datagram, including both header and data, in bytes.
o Helps receivers distinguish between actual data and any padding that might be added
(e.g., in Ethernet frames).
5. Identification, Flags, and Fragmentation Offset:
o Used for fragmenting datagrams that exceeds the maximum transmission unit (MTU)
of the network.
o Allows reassembly of fragmented packets at the destination.
6. Time-to-Live (TTL) (8 bits):
o Limits the number of hops a datagram can take.
o Each router decrements this value, and if it reaches zero, the datagram is discarded.
o Prevents datagrams from endlessly circulating due to routing errors.
7. Protocol (8 bits):
o Identifies the protocol of the encapsulated payload (e.g., TCP = 6, UDP = 17).
o Ensures the correct upper-layer protocol receives the data at the destination
(demultiplexing).
8. Header Checksum (16 bits):
o Used to verify the integrity of the header (not the payload).
o Each router recalculates the checksum since fields like TTL change with every hop.
9. Source and Destination IP Addresses (32 bits each):

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 10

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

o Source IP Address: The IP address of the sender.

o Destination IP Address: The IP address of the receiver.
o These fields remain unchanged as the datagram travels across the network.
10. Options (0–40 bytes):
o Optional field used for network testing, debugging, or special features.
o Adds flexibility, but may require routers to recalculate the checksum if options are
altered.

3. Payload (Data)

• The payload is the data encapsulated in the datagram, which comes from upper-layer
protocols (e.g., TCP, UDP).
• The payload is the primary reason for sending the datagram, with the header providing the
necessary instructions for delivery.

4. Important Concepts

• Multiplexing and Demultiplexing:

o The Protocol field in the IP header functions like port numbers in the transport
layer.
o It ensures data is delivered to the correct upper-layer protocol.
• Fragmentation:
o Large datagrams are fragmented when they exceed the size limit of the network’s
maximum transmission unit (MTU).
o The Identification, Flags, and Fragmentation Offset fields help in reassembling the
fragments at the destination.
• TTL and Loop Prevention:
o The TTL field prevents infinite looping by limiting the number of hops the packet can
traverse.
o If the TTL reaches zero, the datagram is discarded.

• An IPv4 address is a 32-bit identifier used to uniquely define the connection of a device (host
or router) to the Internet.

THE IPv6 PROTOCOL

• Better header format: IPv6 uses a new header format in which options are
separated from the base header and inserted, when needed, between the base
header and the data. This simplifies and speeds up the routing process because
most of the options do not need to be checked by routers.
• New options: IPv6 has new options to allow for additional functionalities.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 11

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• Allowance for extension: IPv6 is designed to allow the extension of the

protocol if required by new technologies or applications.
• Support for resource allocation: In IPv6, the type-of-service field has been
removed, but two new fields, traffic class and flow label, have been added to
enable the source to request special handling of the packet. This mechanism can
be used to support traffic such as real-time audio and video.
• Support for more security: The encryption and authentication options in IPv6
provide confidentiality and integrity of the packet

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 12

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

1.4 IPv4 Addresses

• The address is assigned to the connection (not the device), meaning if a device changes its
network, its IP address may also change.
• IPv4 addresses are both unique and universal, ensuring global consistency and uniqueness
across all devices connected to the Internet
1. 4.1 Address Space

• The address space is the total number of addresses available for use in the IPv4 protocol.
• IPv4 uses 32 bits, so the address space is 2³² (or 4,294,967,296 addresses).
• In theory, this would allow more than 4 billion devices to connect to the Internet, but practical
limitations such as network design reduce the usable address space.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 13

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

1.4.2. IPv4 Address Notations

IPv4 addresses can be represented in three main formats:

• Binary Notation (Base 2):

o The address is shown as 32 bits, separated into 8-bit octets for readability (e.g.,
11000000 10101000 00000001 00000001).
• Dotted-Decimal Notation (Base 256):
o The address is written in decimal format, with each octet separated by dots (e.g.,
[Link]).
o Each octet is a value between 0 and 255.
• Hexadecimal Notation (Base 16):
o The address is represented as 8 hexadecimal digits (e.g., C0A80101).
o This format is often used in network programming.

1.4.3. Hierarchy in IPv4 Addressing

• IPv4 addresses are hierarchical, divided into two parts:

o Prefix: Defines the network (similar to a postal country or city code).
o Suffix: Defines the specific node (device or connection) on that network (similar to a
house number in postal addressing).
• There are two main types of address hierarchy:
o Classful Addressing: Original fixed-length prefix system (now obsolete).
o Classless Addressing: Modern variable-length prefix system.

4Classful Addressing (Obsolete)

• Classful Addressing divides the IPv4 address space into five classes (A, B, C, D, E),
designed to accommodate different network sizes.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 14

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

IPv4 Address Classes:

Fig 3.9: classful addressing

1. Class A:
o Prefix length: 8 bits (first bit is always 0, so only 7 bits are available for network
identification).
o Supports up to 128 networks.
o Address range: [Link] to [Link].
2. Class B:
o Prefix length: 16 bits (first two bits are 10, so 14 bits for network identification).
o Supports up to 16,384 networks.
o Address range: [Link] to [Link].
3. Class C:
o Prefix length: 24 bits (first three bits are 110, so 21 bits for network identification).
o Supports up to 2,097,152 networks.
o Address range: [Link] to [Link].
4. Class D (Multicast):
o First four bits are 1110.
o Reserved for multicast addresses (group communication).
o Address range: [Link] to [Link].
5. Class E (Experimental):
o First four bits are 1111.
o Reserved for experimental purposes.
o Address range: [Link] to [Link].

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 15

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Address Depletion

Problem: Classful addressing led to rapid depletion of IPv4 addresses due to inefficient
distribution.

• Class A:
o Designed for very large organizations.
o Only 128 networks available, each with 16,777,216 addresses.
o Most organizations didn't need so many addresses, leading to significant waste.
• Class B:
o Designed for midsize organizations.
o Despite more networks available, many addresses remained unused.
• Class C:
o Intended for smaller networks.
o Each network had only 256 addresses, which was often too few for organizations.
• Class E: Reserved and almost never used, leading to wastage of the entire class.

Solutions to Address Depletion

• Subnetting:
o Concept: Divides a large class A or class B network into smaller subnets.
o Method: Increases the prefix length, creating multiple smaller networks from a single
large network.
o Issue: Not widely adopted because large organizations were reluctant to share unused
addresses with smaller ones.
• Supernetting:
o Concept: Combines several smaller class C networks into a larger block.
o Purpose: Designed to create larger address blocks for organizations needing more
than 256 addresses.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 16

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

o Issue: Made packet routing more complex, limiting its effectiveness.

Advantage of Classful Addressing

• Simplicity: The class of an address is easily identifiable from the address itself.
• Fixed Prefix Length:
o Each address class (A, B, C) has a predefined prefix length.
o No additional information is required to determine the prefix and suffix, making it
easier to understand and manage

[Link] to Classless Addressing:

• Classless addressing was introduced to solve the IPv4 address depletion problem.
• It eliminates the rigid class structure (A, B, C) of classful addressing and allows variable-
length blocks of IP addresses.
• Provides more efficient and flexible distribution of IP addresses to organizations and ISPs.
• Classful addressing wasted many IP addresses due to fixed-size blocks; classless addressing
resolves this by allowing different block sizes.

2. Why Classless Addressing Was Introduced:

• Address Depletion: The Internet’s growth led to a shortage of IPv4 addresses.

• ISPs (Internet Service Providers): ISPs required a flexible address allocation system to
serve individuals, small businesses, and organizations efficiently.
• Efficient Allocation: Classless addressing allowed ISPs to assign blocks of addresses based
on actual needs, rather than forcing organizations to take larger, unused ranges.

3. Variable-Length Blocks:

• In classless addressing, IP addresses are grouped into blocks of varying sizes, which can be 2,
4, 8, 16, 32, 64 addresses, and so on.
• The block sizes must be a power of 2, such as 21, 22, 23 and so on.

Fig: 3.10: Variable-length blocks in classless addressing

4. Prefix Length and Slash Notation (CIDR):

• The length of the network portion of the IP address is indicated by the prefix length.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 17

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• Slash Notation or CIDR (Classless Interdomain Routing) is used to specify the prefix
length, written as /n, where n is the number of bits used for the network part.
o Example: [Link]/24 means the first 24 bits are for the network and the remaining
8 bits are for hosts.
• Larger prefix length = smaller network (fewer hosts).
• Smaller prefix length = larger network (more hosts).

Fig: 3.11: Slash notation (CIDR)

5. Block of Addresses:

• A block of addresses is determined by the prefix (network part) and the suffix (host part).
• The size of the block is based on the prefix length.
• The number of addresses in a block is calculated using the formula: N=232-n where n is the
prefix length.

6. How to Extract Information from a Block:

• To extract key information from any given IP address block:

1. Number of addresses: Use N=232−n where n is the prefix length.
2. First address: Set the last (32−n) bits to 0.
3. Last address: Set the last (32 – n) bits to 1.

Fig 3.11: Information extraction in classless addressing

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 18

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Example : A classless address is given as [Link]/27. We can find the above three pieces of
information as follows. The number of addresses in the network is 232 − n = 25 = 32 addresses.

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

Network Address
The above examples show that, given any address, we can find all information about the block.
The first address, the network address, is particularly important because it is used in routing a
packet to its destination network.

Fig 3.12: Network address

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 19

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

For the moment, let us assume that an internet is made of m networks and a router with m interfaces.
When a packet arrives at the router from any source host, the router needs to know to which network
the packet should be sent: from which interface the packet should be sent out.

7. Advantages of Classless Addressing:

• Efficient use of IP addresses: Avoids the waste of addresses that occurs with classful
addressing.
• Scalability: Allows for more precise address allocation based on actual need, which is crucial
as the number of devices connected to the Internet grows.
• Better management by ISPs: ISPs can assign blocks of different sizes to customers,
ensuring everyone gets only the number of addresses they need.

Classless addressing (CIDR) was a crucial development in managing the limited IPv4 address space.
By allowing variable-length prefixes and more flexible block sizes, it ensures a more efficient and
scalable distribution of IP addresses across the Internet.

8. Block Allocation in Classless Addressing:

• Global Authority (ICANN): The Internet Corporation for Assigned Names and Numbers
(ICANN) is responsible for assigning IP address blocks.
o ICANN does not assign addresses to individual users but allocates large blocks to
ISPs or large organizations.
• Responsibilities of ISPs: ISPs receive large blocks of addresses from ICANN, which they
further subdivide and assign to customers.

Restrictions for Block Allocation:

Two main restrictions ensure the proper functioning of CIDR:

1. Number of Addresses (N):

o The number of requested addresses must be a power of 2.
o This is because N=232−nN = 2^{32 - n}N=232−n, and nnn must be an integer. If
NNN is not a power of 2, nnn will not be a valid integer.
o Example: If 1000 addresses are requested, since 1000 is not a power of 2, the next
power of 2 (1024) addresses will be allocated.
2. First Address Requirement:
o The first address of the block must be divisible by the number of addresses in the
block.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 20

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

o The first address should be represented as the prefix followed by (32−n) mzeros in
binary.
o The decimal value of the first address must be divisible by the number of addresses.

Example (Block Allocation):

• An ISP requests 1000 addresses.

• Since 1000 is not a power of 2, 1024 addresses are allocated instead.
• The prefix length n is calculated as n=32−log21024=22 The ISP is assigned the block
[Link]/22. The first address in this block (in decimal) is 302,910,464, which is divisible
by 1024.

1. Overview of Subnetting:

• Subnetting: The process of dividing a larger block of IP addresses (assigned to an

organization or ISP) into smaller blocks called subnetworks (or subnets).
• Multi-level Hierarchy: Subnetting can be performed at multiple levels. For example, a
subnet can be further divided into sub-subnets, sub-sub-subnets, etc.
• Subnetting provides more granular control over IP address allocation and network design,
allowing for efficient use of address space and easier management of smaller networks.

2. Designing Subnets:

To design subnetworks efficiently, the following steps must be followed:

1. Number of Addresses in Subnet:

o The number of addresses in each subnetwork (Nsub) must be a power of 2.
o This ensures that subnetting adheres to the same principles as block allocation, where
the address block size must be a power of 2.
2. Prefix Length for Each Subnetwork:
o The prefix length for each subnetwork (nsub) can be calculated using the formula:
nsub=32−log⁡2(Nsub)nsub = 32 - \log_2 (Nsub)nsub=32−log2(Nsub)
o This formula helps determine how many bits in the IP address are used for the
network part, and how many are left for the hosts.
3. Starting Address of Each Subnet:
o The starting address of each subnet must be divisible by the number of addresses in
the subnet.
o This can be achieved by assigning addresses to larger subnetworks first and then
working down to smaller subnets.

Example:

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 21

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• Suppose an organization is granted 1024 addresses (/22).

• The organization can divide the range into subnetworks based on the number of required
addresses per subnet.
o For a subnet that needs 256 addresses, the prefix length would be
nsub=32−log2256=24
o The starting address of each subnet must be divisible by the size of the subnet (256 in
this case).

3. Finding Information About Each Subnetwork:

After designing the subnetworks, key information about each subnet (such as the first address and
last address) can be calculated using the same method applied to larger networks. The process is as
follows:

1. First Address:
o The first address of the subnet is found by setting the host bits (the last 32−n sub bits)
to 0.
2. Last Address:
o The last address is found by setting the host bits to 1.

Steps to Find First and Last Address:

• If a subnet has a prefix length of /24, the first address will have the last 8 bits set to 0, and the
last address will have the last 8 bits set to 1.

Key Points to Remember:

• Subnetting allows an organization to efficiently use its allocated IP address block by

dividing it into smaller subnetworks.
• Each subnetwork must contain a power-of-2 number of addresses.
• The prefix length for each subnetwork is calculated based on the number of addresses it
requires.
• Proper design of subnets is crucial for efficient routing and network management.
• Once designed, the first and last address of each subnet can be determined using the prefix
length.

This approach ensures optimal usage of IP addresses, simplifies routing, and improves the scalability
of network infrastructure.

Address Aggregation

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 22

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

One of the advantages of the CIDR strategy is address aggregation (sometimes called address
summarization or route summarization). When blocks of addresses are combined to create a larger
block, routing can be done based on the prefix of the larger block. ICANN assigns a large block of
addresses to an ISP. Each ISP in turn divides its assigned block into smaller sub blocks and grants
the sub locks to its customers.

Problem : Example: An organization has been granted a block of 256 addresses, starting at
[Link]/24. The organization needs to divide this block into three subnets with the following
requirements:

1. Subnet 1: 120 addresses

2. Subnet 2: 60 addresses
3. Subnet 3: 10 addresses

The solution involves allocating a number of addresses that are powers of 2, which are larger than or
equal to the required number. The subnets are designed by starting with the largest requirement and
working down to the smallest.

Steps and Subnet Design:

1. Total Addresses:
o The block [Link]/24 has a total of: 232−24=256 addresses
o First address: [Link]
o Last address: [Link]

Subnet A: Largest Subnet (120 addresses)

• Required: 120 addresses, but this is not a power of 2.

• Allocated: 128 addresses (since 128=is the next power of 2).
• Prefix length: n1=32−log2(128)=25
• First address: [Link]/25
• Last address:
o The block starts at [Link], and since there are 128 addresses, the last address is
[Link]/25.

Subnet B: Second Largest Subnet (60 addresses)

• Required: 60 addresses, but this is not a power of 2.

• Allocated: 64 addresses (since 64=26 is the next power of 2).
• Prefix length: n2=32−log2(64)=26

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 23

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• First address: The next available address after the first block is [Link]/26.
• Last address:
o The block starts at [Link], and since there are 64 addresses, the last address is
[Link]/26.

Subnet C: Smallest Subnet (10 addresses)

• Required: 10 addresses, but this is not a power of 2.

• Allocated: 16 addresses (since 16=24 is the next power of 2).
• Prefix length: n3=32−log2(16)=28
• First address: The next available address after the second block is [Link]/28.
• Last address:
o The block starts at [Link], and since there are 16 addresses, the last address is
[Link]/28.

Remaining Addresses:

• After assigning the three subnets, the total number of allocated addresses is:
128+64+16=208 addresses
• This leaves 48 addresses unused.
• First address of unused range: [Link]
• Last address of unused range: [Link]
• Prefix length: To be determined, but the range can be used for future subnets or other
purposes.

Summary of Subblocks:

• Subnet A:
o 120 required, 128 allocated
o First address: [Link]/25
o Last address: [Link]/25
• Subnet B:
o 60 required, 64 allocated
o First address: [Link]/26
o Last address: [Link]/26
• Subnet C:
o 10 required, 16 allocated
o First address: [Link]/28
o Last address: [Link]/28
• Unused Block:
o First address: [Link]

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 24

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

o Last address: [Link]

o 48 addresses left for future use.

This method ensures efficient utilization of IP addresses while allowing for potential future
expansions.

Special IPv4 Addresses

IPv4 includes several special-purpose addresses used for specific functions in networking. Here are
five important types:

1. This-host Address ([Link]/32)

• Address: [Link]/32
• Purpose: Used when a host doesn't know its own IP address and needs to communicate.
• Use Case: A host might use this address as a source address before it knows its IP (e.g.,
during DHCP requests).

2. Limited-broadcast Address ([Link]/32)

• Address: [Link]/32
• Purpose: Sends a datagram to all devices on the local network.
• Restrictions: Routers block these packets from being forwarded to other networks (they stay
within the local network).
• Use Case: A host can broadcast to all devices within the same local network segment.

3. Loopback Address ([Link]/8)

• Address: [Link]/8 (commonly, [Link])

• Purpose: Used for testing and local communications within the same host. Packets sent to
this address never leave the device.
• Use Case: Software testing (e.g., running a client-server application on the same host using
[Link] as the server address).

4. Private Addresses

• Blocks:
o [Link]/8
o [Link]/12
o [Link]/16
o [Link]/16 (link-local addresses)

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 25

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• Purpose: Used for internal/private networks. These addresses are not routable on the public
Internet.
• Use Case: Networks within homes, businesses, or organizations. They require Network
Address Translation (NAT) for accessing the Internet.

5. Multicast Addresses ([Link]/4)

• Address Block: [Link]/4

• Purpose: Used for multicasting, where a datagram is sent to multiple destinations
simultaneously.
• Use Case: Applications like video conferencing, live streaming, or network services that need
to send data to a group of devices.

Summary of Special IPv4 Addresses:

Type Address/Block Purpose

This-host [Link]/32 Host doesn't know its IP address

Limited- Broadcast to all devices in the local

[Link]/32
broadcast network

Testing local applications (remains

Loopback [Link]/8
on host)

Private [Link]/8, [Link]/12, [Link]/16,

Internal, non-routable IP addresses
Addresses [Link]/16

Send data to multiple devices

Multicast [Link]/4
simultaneously

These addresses serve distinct roles in networking, ensuring proper communication, testing, and
private address use within internal networks.

Dynamic Host Configuration Protocol (DHCP)

• Plug and-play protocol.

• Address assignment in an organization.
• A network manager can configure DHCP to assign permanent IP addresses to the host and
routers.
• DHCP can also be con figured to provide temporary, on demand, IP addresses to hosts.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 26

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

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

DHCP Message Format:

The 64-byte option field has a dual purpose. It can carry either additional information or some
specific vendor information. The server uses a number, called a magic cookie, in the format of an IP
address with the value of [Link]. When the client finishes reading the message, it looks for this
magic cookie. If present, the next 60 bytes are options.

An option is composed of three fields: a 1-byte tag field, a 1-byte length field, and a variable-length
value field. There are several tag fields that are mostly used by vendors.

If the tag field is 53, the value field defines one of the 8 message types shown in Figure 18.26. We
show how these message types are used by DHCP.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 27

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

DHCP Operation :

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 28

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

1. The joining host creates a DHCP DISCOVER message in which only the transaction ID field is set
to a random number. No other field can be set because the host has no knowledge with which to do
so. This message is encapsulated in a UDP user datagram with the source port set to 68 and the
destination port set to 67.

The user datagram is encapsulated in an IP datagram with the source address set to [Link] (“this
host”) and the destination address set to [Link] (broadcast address). The reason is that the
joining host knows neither its own address nor the server address.

2. The DHCP server or servers (if more than one) responds with a DHCPOFFER message in which
your address field defines the offered IP address for the joining host and the server address field
includes the IP address of the server. The message also includes the lease time for which the host can
keep the IP address. This message is encapsulated in a user datagram with the same port numbers,
but in the reverse order. The user datagram in turn is encapsulated in a datagram with the server
address as the source IP address, but the destination address is a broadcast address, in which the
server allows other DHCP servers to receive the offer and give a better offer if they can.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 29

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

3. The joining host receives one or more offers and selects the best of them. The joining host then
sends a DHCPREQUEST message to the server that has given the best offer. The fields with known
value are set. The message is encapsulated in a user datagram with port numbers as the first message.
The user datagram is encapsulated in an IP datagram with the source address set to the new client
address, but the destination address still is set to the broadcast address to let the other servers know
that their offer was not accepted.

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

Two Well-Known Ports of DHCP:

DHCP uses two well-known ports (68 and 67) instead of one well-known and one ephemeral to
bifurcate the operations and to DHCP requests and response.

DHCP client uses timers and a retransmission policy if it does not receive the DHCP reply to a
request. However, to prevent a traffic jam when several hosts need to retransmit a request (for
example, after a power failure), DHCP forces the client to use a random number to set its timers.

Transition States

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 30

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

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

Network Address Resolution (NAT)

Network address translation (NAT) is a technique that allows multiple devices to share a single
public IP address. It works by translating the private IP addresses of a local network into a public IP
address before sending packets to the internet.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 31

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

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

Address Translation

All of the outgoing packets go through the NAT router, which replaces the source address in the
packet with the global NAT address. All incoming packets also pass through the NAT router, which

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 32

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

replaces the destination address in the packet (the NAT router global address) with the appropriate
private address. Figure 18.30 shows an example of address translation.

Translation Table

• Using One IP Address.

• Using a Pool of IP Addresses
• Using Both IP Addresses and Port Addresses

1. Using One IP Address

A translation table has only two columns: the private address and the external address (destination
address of the packet). When the router translates the source address of the outgoing packet, it also
makes note of the destination address— where the packet is going. When the response comes back
from the destination, the router uses the source address of the packet (as the external address) to find
the private address of the packet. Figure 18.31 shows the idea. In this strategy, communication must
always be initiated by the private network. The NAT mechanism described requires that the private
network start the communication.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 33

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

2. Using a Pool of IP Addresses

NAT can be connected to more than one private network by using more IP addresses. The NAT
router can use four addresses ([Link], [Link], [Link], and [Link]), so four private-
network hosts can communicate with the same external host at the same time because each pair of
addresses defines a separate connection. But no more than four connections can be made to the same
destination.

3. Using Both IP Addresses and Port Addresses

To allow a many-to-many relationship between private-network hosts and external server programs,
translation table with port numbers can be used. For example, suppose two hosts inside a private
network with addresses [Link] and [Link] need to access the HTTP server on external host
[Link]. If the translation table has five columns, instead of two, that include the source and
destination port addresses and the transport-layer protocol, the ambiguity is eliminated. Table 18.1
shows an example of such a table.

Unicast Routing

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

• Goal - to find the best route

• each node creates is its own least-cost tree with the rudimentary information it has about its
immediate neighbors
• The incomplete trees are exchanged between immediate neighbors to make the trees more
and more complete and to represent the whole internet
◦ router continuously tells all its neighbors about what it knows about the whole internet
(although the knowledge can be incomplete).
• Uses two important topics: the Bellman- Ford equation and the concept of distance vectors

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 34

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

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.

Link-State 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.
• Creating least-cost trees and forwarding tables is link-state (LS) routing.
• This method uses the term link-state to define the characteristic of a link (an edge) that
represents a network in the internet.
• 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.
• 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).

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 35

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

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 20.9 for our internet in Figure
20.1.

Formation of Least-Cost Trees

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 36

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

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.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 37

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 38

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 39

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Distance-Vector Routing

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.

Bellman-Ford Equation

• Find the least cost (shortest distance) between a source node, x, and a destination node, y,
through some intermediary nodes (a, b, c, …) , when following are given
◦ the costs between the source and the intermediary nodes
◦ the least costs between the intermediary nodes and the destination
• General case in which Dij is the shortest distance and cij is the cost between nodes i and j
◦ Dxy = min {(cxa + Day), (cxb + Dby), (cxc + Dcy), …}
• Bellman-Ford equation enables us to build a new least-cost path from previously established
least-cost paths.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 40

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 41

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Link State and distant vector problem- Refer class notes and PPT’s

Path-Vector Routing

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

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 42

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• In path-vector routing, the path from a source to all destinations is also determined by
the best spanning tree.
• 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.

Creation of Spanning Trees:

Path-vector routing, like distance-vector routing, is an asynchronous and distributed routing

algorithm. The spanning trees are made, gradually and asynchronously, by each node. When a node
is booted, it creates a path vector based on the information it can obtain about its immediate
neighbor. A node sends greeting messages to its immediate neighbors to collect these pieces of
information. Figure 20.12 shows all of these path vectors for our internet in Figure 20.11. Note,
however, that we do not mean that all of these tables are created simultaneously; they are created
when each node is booted. The figure also shows how these path vectors are sent to immediate
neighbors after they have been created (arrows). Each node, after the creation of the initial path
vector, sends it to all its immediate neighbors. Each node, when it receives a path vector from a
neighbor, updates its path vector using an equation similar to the Bellman-Ford, but applying its own
policy instead of looking for the least cost. We can define this equation as

Path(x, y) = best {Path(x, y), [(x + Path(v, y)]}

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. 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 20.13 shows
the path vector of node C after two events. In the first event, node C receives a copy of B’s vector,
which improves its vector: now it knows how to reach node A. In the second event, node C receives
a copy of D’s vector, which does not change its vector. As a matter of fact the vector for node C after
the first event is stabilized and serves as its forwarding table.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 43

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 44

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 45

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Unicast routing protocols

• A protocol is more than an algorithm

• Protocol needs to define
◦ its domain of operation
◦ the messages exchanged
◦ Communication between routers
◦ interaction with protocols in other domains
• Three common protocols used in the Internet:
◦ Routing Information Protocol (RIP), based on the distance-vector algorithm
◦ Open Shortest Path First (OSPF), based on the link-state algorithm

Border Gateway Protocol (BGP), based on the path-vector algorithm

Internet:

• The largest internetwork in the world

• Internet (uppercase I ), is composed of thousands of interconnected networks
• Internet consists of several
• Backbones (top level)
• large networks owned by some communication companies such as Sprint,
Verizon (MCI), AT&T, and NTT

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 46

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• connected through some complex switching systems, called peering points

• provider networks (second level) - smaller networks
• use the services of the backbones for a fee
• connected to backbones and sometimes to other provider networks
• Customer networks (the edge of the Internet)
• actually use the services provided by the Internet
• pay fees to provider networks for receiving services
• Backbones and provider networks are also called Internet Service Providers (ISPs)
• Backbones = international ISPs
• provider networks = national or regional ISPs

Hierarchical Routing:

• The Internet today is made up of a huge number of networks and routers that connect them.
• Routing in the Internet cannot be done using one single protocol for two reasons:
◦ a scalability problem - the size of the forwarding tables becomes huge, searching for a
destination in a forwarding table becomes time consuming, and updating creates a
huge amount of traffic
◦ an administrative issue- related to the Internet structure
◦ each ISP is run by an administrative authority
◦ The administrator needs to have control in its system.
◦ organization must be able to use as many subnets and routers as it needs, may
desire that the routers be from a particular manufacturer, may wish to run a
specific routing algorithm to meet the needs of the organization, and may want
to impose some policy on the traffic passing through its ISP
• Hierarchical routing means considering each ISP as an autonomous system (AS)
• Each AS can run a routing protocol that meets its needs, but the global Internet runs a
global protocol to glue all ASs together
◦ The routing protocol run in each AS is referred to as intra-AS routing protocol,
intradomain routing protocol, or interior gateway protocol (IGP);
◦ RIP and OSP
◦ the global routing protocol is referred to as inter-AS routing protocol, interdomain
routing protocol, or exterior gateway protocol (EGP)
◦ BGP
• Several intradomain routing protocols -each AS is free to choose one, but only one
interdomain protocol that handles routing between these entities

Autonomous Systems:

• Each ISP is an autonomous system when it comes to managing networks and routers under its
control

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 47

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• Although we may have small, medium-size, and large ASs, each AS is given an autonomous
number (ASN) by the Internet Corporation for Assigned Names and Numbers (ICANN)
• Each ASN is a 16-bit unsigned integer that uniquely defines an AS
• The autonomous systems, however, are not categorized according to their size; they are
categorized according to the way they are connected to other Ass

Types of Autonomous Systems;

• Stub AS- has only one connection to another AS

◦ The data traffic can be either initiated or terminated in a stub AS
◦ the data cannot pass through it
◦ A good example of a stub AS is the costumer network, which is either the source or
the sink of data.
• Multihomed AS-can have more than one connection to other ASs, but it does not allow data
traffic to pass through it
• A good example of such an AS is some of the costumer ASs that may use the services of
more than one provider network, but their policy does not allow data to be passed through
them.
• Transient AS - connected to more than one other AS and also allows the traffic to pass
through
◦ The provider networks and the backbone are good examples of transient ASs

Routing Information Protocol (RIP)

• Intradomain routing protocols based on the distance-vector routing algorithm

• started as part of the Xerox Network System (XNS), but it was the Berkeley Software
Distribution (BSD) version of UNIX that helped make the use of widespread RIP
• RIP concept:
◦ Hop count
◦ Forwarding tables
◦ Implementation – RIP messages, algorithm, timers
◦ performance
• A router in an AS needs to know how to forward a packet to different networks (subnets) in
an AS so RIP routers advertise the cost of reaching different networks instead of reaching
other nodes in a theoretical graph
◦ the cost is defined between a router and the network in which the destination host is
located
• To make the implementation of the cost simpler (independent from performance factors of
the routers and links, such as delay, and bandwidth), 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

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 48

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

◦ 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.
• 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
• Routers in an autonomous system need to keep forwarding tables to forward packets to their
destination networks
• A forwarding table in RIP is a three column table
• the address of the destination network
• the address of the next router to which the packet should be forwarded
• the cost (the number of hops) to reach the destination network
• the first and third columns together convey the same information as does a distance vector,
but the cost shows the number of hops to the destination networks.

• Although a forwarding table in RIP defines only the next router in the second column, it gives
the information about the whole least-cost tree
• 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.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 49

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

◦ The tree is then R1 → R2 → R3 → N4.

• What the use of the third column?
◦ The third column is not needed for forwarding the packet, but it is needed for updating
the forwarding table when there is a change in the route
• uses the service of User Datagram Protocol (UDP) on the well-known port number 520
• In BSD, RIP is a daemon process (a process running at the background), named routed
(abbreviation for route daemon and pronounced route-dee)
◦ 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 runs at the application layer, but creates forwarding tables for IP at the
network later
• RIP has gone through two versions: RIP-1 and RIP-2 (backward-compatible )
• RIP-2 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 need to exchange messages

• Part of the message -call an entry

Each entry carries the information related to one line in the forwarding table of the router that sends
the message

• 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
◦ can ask about specific entries or all entries
• A response (or update) message
◦ Solicited - sent only in answer to a request message
◦ contains information about the destination specified in the corresponding
request message

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 50

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

◦ Unsolicited- sent periodically, every 30 s or when there is a change in the forwarding

table.

Timers in RIP;

• RIP uses three timers to support its operation

• Periodic timer controls the advertising of regular update messages
◦ Each router has one periodic timer that is randomly set to a number between 25 and
35 s (to prevent all routers sending their messages at the same time and creating
excess traffic).
◦ The timer counts down; when zero is reached, the update message is sent, and the
timer is randomly set once again
• The expiration timer governs the validity of a route
◦ When a router receives update information for a route, the expiration timer is set to
180 s for that particular route.
◦ Every time a new update for the route is received, the timer is reset.
◦ If there is a problem on an internet and no update is received within the allotted 180 s,
the route is considered expired and the hop count of the route is set to 16, which
means the destination is unreachable.

Every route has its own expiration timer.

• Garbage collection timer is used to purge a route from the forwarding table.
◦ When the information about a route becomes invalid, the router does not immediately
purge that route from its table.
◦ Instead, it continues to advertise the route with a metric value of 16.
◦ At the same time, a garbage collection timer is set to 120 s for that route.
◦ When the count reaches zero, the route is purged from the table.
◦ This timer allows neighbors to become aware of the invalidity of a route prior to
purging.

Performance of RIP

• Update messages – have a very simple format and are sent only to neighbors (local)
◦ They do not normally create traffic because the routers try to avoid sending them at
the same time.
• Convergence of forwarding tables - the distance-vector algorithm can converge slowly if
the domain is large, but, because RIP allows only 15 hops in a domain (16 is considered as
infinity), there is normally no problem in convergence
◦ The only problems that may slow down convergence are count-to-infinity and loops
created in the domain;

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 51

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

◦ Solution - use of poison-reverse and split-horizon strategies added to the

RIP extension
• Robustness - In distance-vector routing, each router sends what it knows about the whole
domain to its neighbors
◦ Calculation of the forwarding table depends on information received from immediate
neighbors, which in turn receive their information from their own neighbors
◦ If there is a failure or corruption in one router, the problem will be propagated to all
routers and the forwarding in each router will be affected.

Open Shortest Path First (OSPF)

• An Intradomain routing protocol like RIP, but it is based on the link-state routing protocol
• OSPF is an open protocol, which means that the specification is a public document.
• OSPF concept:
◦ Metric
◦ Forwarding tables
◦ Areas
◦ Link state advertisement
◦ Implementation – OSPF messages, authentication, algorithm
◦ Performance
• Cost of reaching a destination from the host is calculated from the source router to the
destination network
• 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.

• Each OSPF router can create a forwarding table after finding the shortest path tree between
itself and the destination using Dijkstra’s algorithm,

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 52

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• If we use the hop count for OSPF, the tables will be exactly the same as RIP because both
protocols use the shortest-path trees to define the best route from a source to a destination.
• RIP is normally used in small ASs, OSPF was designed to be able to handle routing in a small
or large autonomous system.
• 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
• OSPF uses another level of hierarchy in routing: The first level is the autonomous system, the
second is the area
• The AS needs to be divided into small sections called areas
• Each area acts as a small independent domain for flooding LSPs.

• However, each router in an area needs to know the information about the link states not only
in its area but also in other areas.
• For this reason, one of the areas in the AS is designated as the backbone area, responsible for
gluing the areas together.
• The routers in the backbone area are responsible for passing the information collected by each
area to all other areas.
• A router in an area can receive all LSPs generated in other areas
• For the purpose of communication, each area has an 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.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 53

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• We 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
◦ external link

1. Router link - advertises the existence of a router as a node

• In addition to giving the address of the announcing router, this type of advertisement can
define one or more types of links that connect the advertising router to other entities
◦ A transient link announces a link to a transient network, a network that is connected
to the rest of the networks by one or more routers
◦ This type of advertisement should define the address of the transient network
and the cost of the link
◦ A stub link advertises a link to a stub network, a network that is not a through network
◦ Again, the advertisement should define the address of the network and the cost

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 54

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

◦ A point-to-point link should define the address of the router at the end of the point-to-
point line and the cost to get there.

2. Network link - advertises the network as a node.

• However, because a network cannot do announcements itself (it is a passive entity), one of
the routers is assigned as the designated router and does the advertising
• In addition to the address of the designated router, this type of LSP announces the IP address
of all routers (including the designated router as a router and not as speaker of the network),
but no cost is advertised because each router announces the cost to the network when it sends
a router link advertisement.

3. Summary link to network -This is done by an area border router; it advertises the summary of
links collected by the backbone to an area or the summary of links collected by the area to the
backbone

◦ This type of information exchange is needed to glue the areas together.

4. Summary link to AS - This is done by an AS router that advertises the summary links from
other ASs to the backbone area of the current AS, information which later can be disseminated to the
areas so that they will know about the networks in other Ass

5. External link -This is also done by an AS router to announce the existence of a single network
outside the AS to the backbone area to be disseminated into the areas.

OSPF Messages

• OSPF is a very complex protocol; it uses five different types of messages

• OSPF common header format (which is used in all messages) and the link-state general
header (which is used in some messages)

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 55

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Five message types used in OSPF

• The hello message (type 1) is used by a router to introduce itself to the neighbors and
announces all neighbors that it already knows.
• The database description message (type 2) is normally sent in response to the hello message
to allow a newly joined router to acquire the full LSDB
• The link-state request message (type 3) is sent by a router that needs information about a
specific LS

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 56

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

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

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 57

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Border Gateway Protocol Version 4 (BGP4)

• It is the only interdomain routing protocol used in the Internet today

• BGP4 is based on the path-vector algorithm, but it is tailored to provide information about the
reachability of networks in the Internet
• Each autonomous system uses one of the two common intradomain protocols, RIP or OSPF
• Each router in each AS knows how to reach a network that is in its own AS, but it does not
know how to reach a network in another AS.
• To enable each router to route a packet to any network in the internet, we first install a
variation of BGP4, called external BGP (eBGP), on each border router (the one at the edge
of each AS that is connected to a router at another AS)
• We then install the second variation of BGP, called internal BGP (iBGP), on all routers
• The border routers will be running three routing protocols (intradomain, eBGP, and iBGP)
but other routers are running two protocols (intradomain and iBGP).

Operation of External BGP (eBGP)

• BGP protocol is a kind of point-to-point protocol

• When the software is installed on two routers, they try to create a TCP connection using the
well-known port 179
◦ a pair of client and server processes continuously communicate with each other to
exchange messages
• The two routers that run the BGP processes are called BGP peers or BGP speakers
• Different types of messages exchanged between two peers, but for the moment we are
interested in only the update messages that announce reachability of networks in each AS
• The eBGP variation of BGP allows two physically connected border routers in two different
ASs to form pairs of eBGP speakers and exchange messages.
• Example of an internet with four autonomous systems

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 58

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

◦ AS2, AS3, and AS4 are stub autonomous systems

◦ AS1 is a transient one
◦ Data exchange between AS2, AS3, and AS4 should pass through AS1
• The eligible routers form three pairs: R1-R5, R2-R6, and R4-R9
• The connection between these pairs is established over three physical WANs (N5, N6, and
N7)
• However, there is a need for a logical TCP connection to be created over the physical
connection to make the exchange of information possible

Operation of External BGP (eBGP)

• Circled number defines the sending router in each case

• For example, message number 1 is sent by router R1 and tells router R5 that N1, N2, N3, and
N4 can be reached through router R1. (R1 gets this information from the corresponding
intradomain forwarding table.)

• Router R5 can now add these pieces of information at the end of its forwarding table

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 59

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• When R5 receives any packet destined for these four networks, it can use its forwarding table
and find that the next router is R1.

The messages exchanged during three eBGP sessions help some routers know how to route packets
to some networks in the internet, but the reachability information is not complete.

• There are two problems that need to be addressed:

1. Some border routers do not know how to route a packet destined for non-neighbor ASs.

◦ For example, R5 does not know how to route packets destined for networks in AS3
and AS4.
◦ Routers R6 and R9 are in the same situation as R5:
◦ R6 does not know about networks in AS4
◦ R9 does not know about networks in AS3.

2. None of the nonborder routers know how to route a packet destined for any networks in other
ASs.

To address these two problems, we need to allow all pairs of routers (border or nonborder) to run the
second variation of the BGP protocol, iBGP.

Operation of Internal BGP (iBGP)

• The iBGP protocol is similar to the eBGP protocol in that it uses the service of TCP on the
well-known port 179, but it creates a session between any possible pair of routers inside an
autonomous system.
• If an AS has only one router, there cannot be an iBGP session. For example, we cannot create
an iBGP session inside AS2 or AS4 in our internet.
• If there are n routers in an autonomous system, there should be [n × (n − 1) / 2] iBGP
sessions in that autonomous system (a fully connected mesh) to prevent loops in the system.
In other words, each router needs to advertise its own reachability to the peer in the session
instead of flooding what it receives from another peer in another session.

Combination of eBGP and iBGP

• Physical networks inside ASs have not shown because a session is made on an overlay
network (TCP connection), possibly spanning more than one physical network as determined
by the route dictated by the intradomain routing protocol.
• In this stage only four messages are exchanged
◦ The first message (numbered 1) is sent by R1 announcing that networks N8 and N9
are reachable through the path AS1- AS2, but the next router is R1
Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 60

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

◦ This message is sent, through separate sessions, to R2, R3, and R4.
◦ Routers R2, R4, and R6 do the same thing but send different messages to different
destinations.
◦ The interesting point is that, at this stage, R3, R7, and R8 create sessions with their
peers, but they actually have no message to send.

The updating process does not stop here.

• For example, after R1 receives the update message from R2, it combines the reachability
information about AS3 with the reachability information it already knows about AS1 ad
sends a new update message to R5.
• Now R5 knows how to reach networks in AS1 and AS3
• The process continues when R1 receives the update message from R4.
• The point is that we need to make certain that at a point in time there are no changes in the
previous updates and that all information is propagated through all ASs.
• At this time, each router combines the information received from eBGP and iBGP and creates
what we may call a path table after applying the criteria for finding the best path.

Path tables for the routers

• For example, router R1 now knows that any packet destined for networks N8 or N9 should go
through AS1 and AS2 and the next router to deliver the packet to is router R5.
• Similarly, router R4 knows that any packet destined for networks N10, N11, or N12 should
go through AS1 and AS3 and the next router to deliver this packet to is router R1, and so on.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 61

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Path Attributes

• In both intradomain routing protocols (RIP or OSPF), a destination is normally associated with two
pieces of information:
◦ Next hop - shows the address of the next router to deliver the packet
◦ Cost - defines the cost to the final destination
• Interdomain routing is more involved and naturally needs more information about how to reach
the final destination
• In BGP these pieces are called path attributes. BGP allows a destination to be associated with
up to seven path attributes
• All attributes are inserted after the corresponding destination prefix in an update message.

• First byte in each attribute defines the four attribute flags

• The next byte defines the type of attributes assigned by ICANN (only seven types have been
assigned, as explained next).
• Next byte is the length of the attribute value field (not the length of the whole attributes
section).

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 62

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• ORIGIN (type 1) - a well-known mandatory attribute, which defines the source of the
routing information.
• This attribute can be defined by one of the three values: 1, 2, and 3.
• Value 1 means that the information about the path has been taken from an
intradomain protocol (RIP or OSPF).
• Value 2 means that the information comes from BGP.
• Value 3 means that it comes from an unknown source.
• AS-PATH (type 2)- a well-known mandatory attribute, which defines the list of
autonomous systems through which the destination can be reached.
• The AS-PATH attribute helps to prevent a loop
• Whenever an update message arrives at a router that lists the current AS as the path,
the router drops that path

• The AS-PATH can also be used in route selection

• NEXT-HOP (type 3) - a well-known mandatory attribute, which defines the next router to
which the data packet should be forwarded.
◦ It helps to inject path information collected through the operations of eBGP and iBGP
into the intradomain routing protocols such as RIP or OSPF
• MULT-EXIT-DISC (type 4) - the multiple-exit discriminator is an optional nontransitive
attribute, which discriminates among multiple exit paths to a destination.
◦ The value of this attribute is normally defined by the metric in the corresponding
intradomain protocol (an attribute value of a 4-byte unsigned integer).
◦ For example, if a router has multiple paths to the destination with different values
related to these attributes, the one with the lowest value is selected.
◦ This attribute is nontransitive, which means that it is not propagated from one AS to
another.
• LOCAL-PREF (type 5) - The local preference attribute is a well-known discretionary
attribute
◦ It is normally set by the administrator, based on an organization’s policy.
◦ The routes the administrator prefers are given a higher local preference value (an
attribute value of a 4-byte unsigned integer).
◦ For example, in an internet with five ASs, the administrator of AS1 can set the local
preference value of 400 to the path AS1-AS2-AS5, the value of 300 to AS1-AS3-
AS5, and the value of 50 to AS1-AS4-AS5.
◦ This means that the administrator prefers the first path to the second one and prefers
the second one to the third one.
◦ This may be a case where AS2 is the most secured and AS4 is the least secured AS for
the administration of AS1.
◦ The last route should be selected if the other two are not available.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 63

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

• ATOMIC-AGGREGATE (type 6)- This is a well-known discretionary attribute, which

defines the destination prefix as not aggregate; it only defines a single destination network
◦ This attribute has no value field, which means the value of the length field is zero.
• AGGREGATOR (type 7) - This is an optional transitive attribute, which emphasizes that
the destination prefix is an aggregate.
◦ The attribute value gives the number of the last AS that did the aggregation followed
by the IP address of the router that did so.

Messages

• Four types of messages for communication between the BGP speakers across the ASs and
inside an AS:
◦ Open- To create a neighborhood relationship
◦ a router running BGP opens a TCP connection with a neighbor and sends an
open message
◦ Update - heart of the BGP protocol which is used by a router to withdraw
destinations that have been advertised previously, to announce a route to a new
destination, or both
◦ BGP can withdraw several destinations that were advertised before, but it can
only advertise one new destination (or multiple destinations with the same
path attributes) in a single update message
• Keepalive- The BGP peers that are running exchange keep-alive messages regularly
(before their hold time expires) to tell each other that they are alive
• Notification-sent by a router whenever an error condition is detected or a router wants to
close the session

All BGP packets share the same common header.

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 64

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

Multicast Link State (MOSPF)

Multicast routing sends a single copy of data to multiple users simultaneously on a closed
network. It's commonly used for streaming media and videoconferencing on organizational networks.
Multicast Extensions to Open Shortest Path First (MOSPF) is a routing protocol that extends the
Open Shortest Path First (OSPF) protocol to support multicast routing:

• MOSPF builds on OSPF Version 2 to add multicast routing capabilities. It uses OSPF to
maintain a network topology image and adds a new type of link-state advertisement (LSA)
called group-membership-LSA to identify multicast group members.
• MOSPF routers can interoperate with non-multicast OSPF routers when forwarding unicast
IP data traffic.

To extend unicasting to multicasting, each router needs to have another database, as with the case of
unicast distance-vector routing, to show which interface has an active member in a particular group.

Router goes through the following steps to forward a multicast packet received from source S and to
be sent to destination G (a group of recipients:

1. The router uses the Dijkstra algorithm to create a shortest-path tree with S as the root and all
destinations in the internet as the leaves. Note that this shortest-path tree is different from the one the

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 65

Downloaded by DIVYA SHREE (divyashree@[Link])

 lOMoARcPSD|28201683

router normally uses for unicast forwarding, in which the root of the tree is the router itself. In this
case, the root of the tree is the source of the packet defined in the source address of the packet. The
router is capable of creating this tree because it has the LSDB, the whole topology of the internet; the
Dijkstra algorithm can be used to create a tree with any root, no matter which router is using it. The
point we need to remember is that the shortest-path tree created this way depends on the specific
source. For each source we need to create a different tree.

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

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

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

Chethana H R, Asst. Prof. Dept Of CSE, RNSIT 66

Downloaded by DIVYA SHREE (divyashree@[Link])