Lecture 19:

母 1. Internet Protocol (IP)

The Internet Protocol (IP) operates at the Network Layer (Layer 3) of the OSI model. Its main
responsibilities are:
• Logical addressing (assigning IP addresses)
• Packet forwarding (routing)
• Fragmentation and reassembly
• Best-effort delivery (no guarantee of delivery, order, or duplication)
』 IP is connectionless and unreliable:

• No acknowledgment

• No retransmission
• No flow control

) 2. IPv4 Datagram Format (Packet

Structure)
An IPv4 datagram consists of:
+------------------- +
| Header (20–60 B) |
+------------------- +
| Data (Payload) |
+------------------- +

叹 Detailed Header Fields

1. Version (4 bits)
• Indicates IP version
• Always 4 for IPv4

2. Internet Header Length (IHL)

• Size of header in 32-bit words
• Minimum = 5 (20 bytes)
• Maximum = 15 (60 bytes)
3. Type of Service (ToS) / DSCP
• Defines packet priority
• Used in QoS (e.g., VoIP vs file transfer)

4. Total Length (16 bits)

• Entire packet size (header + data)
• Range: 20 to 65,535 bytes

5. Identification
• Unique number for each datagram
• Used for fragmentation/reassembly

6. Flags (3 bits)
• Control fragmentation:
• DF (Don’t Fragment) → Packet must not be split
• MF (More Fragments) → More fragments follow

7. Fragment Offset
• Indicates position of fragment
• Measured in 8-byte units

8. Time To Live (TTL)

• Limits packet lifetime
• Decremented by each router
• If TTL = 0 → packet discarded

9. Protocol
• TCP → 6
• Identifies upper-layer protocol:

• TCP → 6
 • UDP → 17
• ICMP → 1

10. Header Checksum

• Error detection for header only
• Recomputed at each router

11. Source Address

• Sender’s IPv4 address

12. Destination Address

• Receiver’s IPv4 address

13. Options (Optional)

• Rarely used
• Can include routing, timestamp, etc.

14. Data (Payload)

• Contains actual data (e.g., TCP segment)

固 Fragmentation (Important
Concept) When packet size exceeds MTU:
• It is split into fragments
• Each fragment has:

• Same Identification
• Different Fragment Offset
• Reassembled at destination only
 3. IPv4 Addressing
+ Structure of IPv4 Address
• 32 bits (4 bytes)
• Written in dotted decimal:
Example: 1 9 2 . 1 6 8 . 1 0 . 5

Each octet = 8 bits

+ Network vs Host
Portion An IP address is divided
into:
• Network ID → identifies network
• Host ID → identifies device
This division is defined by the subnet mask

+ Classful Addressing
Class A
• Range: [Link] – [Link]
• Default mask: [Link]
• Large networks

Class B
• Range: [Link] – [Link]
• Default mask: [Link]

Class C
• Range: [Link] – [Link]
• Default mask: [Link]

Class D
• 224–239 → Multicast
Class E
• 240–255 → Experimental

+ Special IP
Addresses Private IP
Ranges
• [Link] – [Link]
• [Link] – [Link]
• [Link] – [Link]
Used inside LANs (notroutable on internet)

Loopback Address
• [Link] → localhost

Broadcast Address
• All host bits = 1
• Sends packet to all devices in network

圜 4. Subnetting (Very Important Topic)

Subnetting is the process of dividing a large network into smaller networks (subnets).

Why Subnetting?
• Reduces network congestion
• Improves performance
• Enhances security

• Efficient IP allocation
+ Subnet Mask
Defines which bits belong to network vs host.
Example:

IP Address: [Link]
Subnet Mask: [Link]

• Network: [Link]
• Host: 10

+ CIDR
Notation Compact
format:
[Link] /24

• /24 → first 24 bits = network

• Remaining 8 bits = host

+ Subnetting Example (Step-by-Step)

Given:
Network: 192 .168 .1 .0/24

Need: 4 subnets

Step 1: Borrow bits

• Need 4 subnets → 2 bits (2² = 4)

Step 2: New subnet mask

• /24 + 2 = /26
• Mask = [Link]
Step 3: Subnet ranges
Subnet Network Address Host Range Broadcast

1 [Link] .1 – .62 .6
3
2 [Link] .65 – .126 .12
7
3 [Link] .129 – .19
.190 1
4 [Link] .193 – .25
.254 5
+ Key Formulas
Number of Subnets
2^n (n = borrowed bits)

Hosts per Subnet

2^h - 2

• h = remaining host bits

• subtract 2 for:
• Network address
• Broadcast address

+ Example
For /26:
• Host bits = 6
• Hosts = 2⁶ − 2 = 62 usable hosts

固 How Everything Works Together

1. Applicationsends data
2. Data encapsulated into IP datagram

3. Source & destination IP added

4. Routers forward packet using IP addressing
5. Subnetting helps determine routing paths
6. TTL prevents infinite loops
7. Destination reassembles fragments

⚡ Final Summary
• IP Protocol → Handles addressing & routing
• Datagram Format → Defines packet structure
• IPv4 Addressing → Identifies devices
• Subnetting → Divides networks efficiently
Lecture 20:
1. Supernetting (Route Aggregation)
What is Supernetting?
Supernetting (also called route aggregation) is the process of combining multiple smaller IP
networks into one larger network to reduce routing table size.

Why is it needed?
• Reduces routing table entries
• Improves routing efficiency
• Saves memory and processing in routers

Example
Instead of having four separate networks:

• [Link]/24
• [Link]/24
• [Link]/24
• [Link]/24

They can be combined into:

• [Link]/22

Key Idea
• Borrow bits from the network portion
• Use a shorter prefix (CIDR notation)

Formula Insight
If combining (2^n) networks → reduce prefix by n bits

2. IPv6 Addressing
Why IPv6?
IPv4 (32-bit) provides ~4.3 billion addresses → not enough.
IPv6 solves this using:
• 128-bit addresses
 • Vast address space (≈ (3.4 \times 10^{38}))

IPv6 Address Format

128\text{-bit address written as 8 groups of 16
bits} Example:

2001:0db8: 85a3: 0000: 0000: 8a 2e:0370:7334

Simplification Rules
1. Remove leading zeros

• 0db8 → db8
2. Replace consecutive zeros with ::
2001:db8:: 8a2e: 370:7 334

Types of IPv6 Addresses

1. Unicast
• One-to-one communication
• Like traditional IP

2. Multicast
• One-to-many (selected group)

[Link]
• One-to-nearest (best route)

Special IPv6 Addresses

• Loopback → ::1

• Unspecified → ::

3. Applications of IPv6
1. Internet of Things (IoT)
• Every device can have a unique IP
 • No need for NAT

2. Better Routing Efficiency

• Hierarchical addressing
• Smaller routing tables

3. Built-in Security
• Native support for IPsec

4. Auto-configuration
• Devices configure themselves (SLAAC)

5. Improved Multimedia Support

• Better QoS (Quality of Service)

4. Key Differences: IPv4 vs IPv6

Feature IPv4 IPv6
Address 32-bit 128-bit
Size
Decim Hexadeci
For
al mal Not
mat
Requir needed
NA
ed Built-in
T
Optio
Security nal
Address Space Limited Huge

Quick Summary
• Supernetting → combines networks to simplify routing
• IPv6 → solves address exhaustion with 128-bit addressing
• Applications → IoT, security, auto-config, efficient routing
Great—let’s work through exam-style numerical problems on supernetting and
IPv6 addressing, with step-by-step solutions.
Part 1: Supernetting Numericals

Problem 1: Combine Networks

Combine the following networks into one supernet:

• [Link]/24
• [Link]/24
• [Link]/24
• [Link]/24

Step 1: Count networks

There are 4 networks → (4 = 2^2)

Step 2: Reduce prefix

Each network is /24 → reduce by 2 bits → /22

Step 3: Find starting network

Lowest network = [Link]

Final Answer
[Link]/22

Problem 2: Check if Supernetting is Possible

Given:

• [Link]/24
• [Link]/24

Analysis
Networks must be:
• Contiguous
• Aligned in powers of 2
Here:

• Missing [Link] → not continuous

Answer
× Supernetting NOT possible
Problem 3: Find Number of Addresses
Supernet:

[Link]/20 Use

formula:

\text{Number of addresses} = 2^{(32 -

\text{prefix})} [

= 2^{(32 - 20)} = 2^{12} =

4096 ]

Answer
4096 IP addresses

Problem 4: Find Range of Supernet

Network: [Link]/21

Step 1: Calculate size

[
2^{(32-21)} = 2^{11} =
2048 ]

Step 2: Range
• Start: [Link]
• End: [Link]

Answer
Range = [Link] → [Link]

Part 2: IPv6 Numerical Problems

Problem 5: Expand IPv6 Address

Short form:
2 00 1: db8 ::1
Expand:
2ΘΘ1:Θdb8:ΘΘΘΘ:ΘΘΘΘ:ΘΘΘΘ:ΘΘΘΘ:ΘΘΘΘ:ΘΘΘ1

Problem 6: Compress IPv6 Address

Given:
2ΘΘ1:Θdb8:ΘΘΘΘ:ΘΘΘΘ:ΘΘΘΘ:ffΘΘ:ΘΘ42:8329

Steps:
• Remove leading zeros
• Replace longest zero sequence

Answer:
2ΘΘ1:db8::ffΘΘ:42:8329

Problem 7: Number of IPv6 Addresses in /64

Formula:
\text{Number of IPv6 addresses} = 2^{(128 -
\text{prefix})} [

= 2^{(128 - 64)} =
2^{64} ]

Answer:
≈ 18 quintillion addresses

Problem 8: Identify Address Type

Addre
ss:
FFΘΘ
::1

Rule:
• IPv6 multicast starts with FF
Answer:
Multicast Address
Problem 9: Subnetting IPv6
Given:
• Network: 2001:db8::/48
• Required subnets: 256

Step 1:
256 = (2^8)

Step 2:
New prefix:
[
48 + 8 = 56
]

Answer:
New subnet prefix = /56

Quick Exam Tips

• Supernetting → reduce prefix
• Subnetting → increase prefix
• Always check power of 2

• IPv6 → remember 128 bits

Here are clear, exam-style subnetting numericals (IPv4 + a bit of IPv6) with step-by-step
solutions.
Part 1: IPv4 Subnetting Numericals

Problem 1: Find Subnets and Hosts

Given network: [Link]/26

Step 1: Number of subnets

Original (Class C default) =
/24 New = /26 → borrowed
= 2 bits

[
\text{Subnets} = 2^2
=4]

Step 2: Hosts per subnet

\text{Hosts per subnet} = 2^{(32 - \text{prefix})}
-2[

= 2^{(32-26)} - 2 = 2^6 - 2 = 64 - 2 =
62 ]

Answer
• Subnets = 4
• Hosts per subnet = 62

Problem 2: List All Subnets

Network:

[Link]/26 Block

size = 64

Subnets:
1. [Link] – [Link]
2. [Link] – [Link]
3. [Link] – [Link]
4. [Link] – [Link]
Problem 3: Find Network, Broadcast, Usable Range
IP: [Link]/27
Step 1: Block size
[
2^{(32-27)} = 32
]
Subnets increment by 32:

• 0, 32, 64, 96...

70 lies in 64–95

Answer
• Network = [Link]
• Broadcast = [Link]
• Usable = [Link] – [Link]

Problem 4: Required Hosts

You need 100 hosts per subnet

Step 1:
Find nearest power:
[
2^7 = 128
]

Step 2:
Hosts usable:
[
128 - 2 = 126
]

Step 3:
Prefix:
[
32 - 7 = 25
]

Answer
Use /25 subnet
Problem 5: Required Subnets
Given: [Link]/24
Need: 8 subnets

Step 1:

[
8 = 2^3
]

Step 2:
New prefix:
[
24 + 3 = 27
]

Answer
New subnet mask = /27

Problem 6: Mixed (Hosts + Subnets)

Network: [Link]/24
Requirement:

• At least 4 subnets
• Each subnet ≥ 50 hosts

Step 1: Hosts
[
2^6 = 64 → usable = 62
]

Step 2: Prefix:
[
32 - 6 = 26
]
Step 3: Subnets:
[
/24 → /26 → 2^2 = 4
]
Answer
Use /26

Part 2: IPv6 Subnetting Numericals

Problem 7: Subnet IPv6 Network

Given:
• Network: 2001:db8::/48
• Need: 16 subnets

Step 1:
[
16 =
2^4 ]

Step 2:
[
48 + 4 =
52 ]

Answer
New prefix = /52
Problem 8: Hosts in IPv6 Subnet
Subnet: /64

Formula:
2^{(128 - 64)}
[
=
2^{64}
]

Answer
Extremely large (~18 quintillion)
Quick Tricks for Exams
✅ Block Size Shortcut
[
\text{Block size} = 256 - \text{subnet mask (last octet)}
]

Example:
• /27 → [Link]
• Block size = 32

✅ Fast Steps
1. Find required hosts or subnets
2. Convert to power of 2
3. Adjust prefix
4. Find range using block size
Lecture: 21
母 Routing in Computer Networks
(Unicast, Broadcast, Multicast, NAT, ICMP)
Routing is a core concept in Computer Networks that allows data packets to move from one
network/device to another through routers.
When you send a message, open a website, or stream a video, routing determines:

✅ Where packets should go

✅ Which path they should take

✅ How devices communicate over the Internet

1. What is Routing?
Routing is the process of:
Selecting the best path for data packets from source to

destination. This is done by:

• Routers
• Routing tables
• Routing protocols

贏 Example of Routing
Suppose:
Laptop → Home Router → ISP → Internet → Google

Server The router checks:

• Destination IP address
• Best next
hop/path Then
forwards the packet.
毯 Components of Routing
Component
Purpose
Router
Connects networks
IP Address
Identifies device
Routing Table Stores paths
Next Hop
Next router/device
Routing Protocol
Finds best route

篁 2. Unicast Communication
堕 Definition
Unicast means:
One sender communicates with one receiver.

★ Characteristics
• Most common communication type

• One-to-one transmission
• Uses unique destination IP

霭
Example
When you:
• Open YouTube
• Visit Google
• Send email
Your computer communicates with one server.

觑 Diagram
Sender ─────────► Receiver
甲 Real Example
PC IP: 1 92. 16 8.1 .1 0
Google IP: [Link]

Packets go directly to Google server.

✅ Advantages
• Efficient for private communication
• Reliable delivery
• Easy error checking

× Disadvantages
• More bandwidth if same data sent to many users

3. Broadcast Communication
堕 Definition
Broadcast means:
One sender sends data to ALL devices in the network.

Characteristics
• One-to-all communication
• Uses broadcast IP address
• Limited to local network (LAN)

Diagram
┌──► PC1
Sender ────┼──► PC2

└──► PC3
甲 Broadcast Address
Example subnet:
IP Address: [Link]
Subnet Mask: [Link]
Broadcast IP: [Link]

霭 Example Uses
ARP (Address Resolution Protocol)
A computer asks:
“Who has IP

[Link]?” All devices

receive the message.

✅ Advantages
• Useful for discovery protocols
• Easy communication to all hosts

× Disadvantages
• Creates unnecessary traffic
• Reduces network performance
• Routers usually block broadcasts

昱 4. Multicast Communication
堕 Definition
Multicast means:
One sender sends data to a selected group of receivers.

★ Characteristics
• One-to-many (selected)
 • Efficient group communication

• Uses multicast IP addresses

Diagram
┌──► Member1
Sender ────┤

└──► Member2

Non-members do NOT receivedata.

甲 Multicast IP
Range Class D IP addresses:
[Link] → [Link]

霭 Examples
• Live video streaming

• Online classes
• IPTV
• Video conferencing

✅ Advantages
• Saves bandwidth
• Efficient for group applications

× Disadvantages
• More complex routing
• Requires multicast support
囹 Comparison: Unicast vs Broadcast vs
Multicast
Feature Unicast Broadcast Multicast

Communicati One-to-One One-to-All One-to-

on Group
Efficiency Medium Low High
Traffic Low Very High Optimized
IP Type Normal IP Broadcast Class D IP
IP
Example Web ARP Live
browsing streaming

5. NAT (Network Address Translation)

堕 Definition
NAT is a technique where:
A router converts private IP addresses into public IP addresses.

? Why NAT is Needed

Private IPs cannot directly access the
Internet. Example private IPs:

• 192.168.x.x
• 10.x.x.x
• 172.16.x.x
Internet requires public IPs.
 NAT Process
Private
Network
[Link]
│

▼
Router (NAT)
Public IP = 3 9 . 4 5 . 1 0 0 . 7
│

Internet
霭 Example
Suppose:
• Your laptop IP = [Link]

• Router public IP = [Link]

When browsing Google:

Inside LAN:
Source IP = 1 9 2 . 1 6 8 . 1 . 5

Router changes it to:

Source IP = 1 8 2 . 1 7 6 . 2 0 . 1

Google replies to router → router forwards to laptop.

d Types of NAT
1⃞⃞ Static NAT
One private IP ↔ one public IP

2⃞⃞ Dynamic NAT

Pool of public IPs assigned dynamically

3⃞⃞ PAT (Port Address Translation)

Most common.
Many devices share one public IP using ports.

✅ Advantages of NAT
• Saves IPv4
• addresses
• Provides security
Hides internal network
× Disadvantages
• Adds processing delay
• Breaks end-to-end connectivity sometimes

四 6. ICMP (Internet Control

Message Protocol)
堕 Definition
ICMPis a protocol used for:
Error reporting and network

diagnostics. It works with IP protocol.

★ Purpose of ICMP
Routers/devices use ICMP to send:
• Error messages
• Network status
• Diagnostic information

觑 ICMP Example
PC ─────► Router ─────►
Server ×

Destination unreachable

Router sends ICMP error message back.

霭 Common ICMP Messages

Message Purpose
Echo Request Ping request
Echo Reply Ping response
Destination Unreachable Cannot reach host
 Message Purpose
Time Exceeded TTL expired

Redirect Better route exists

) Ping Command (Uses ICMP)

Example
ping [Link]

Process
Your PC sends:
ICMP Echo Request

Google replies:
ICMP Echo Reply

⏳ TTL and ICMP

Each IP packet has:
TTL = Time To Live

Every router decreases TTL by

1. If TTL becomes 0:

• Router discards packet

• Sends ICMP Time Exceeded message

贾 Traceroute Uses ICMP

Command:
traceroute [Link]

It discovers:
 • All routers between source and destination
Using ICMP TTL expiration.
 ICMP and Security
Attackers may misuse ICMP:
• Ping flood

• Smurf attack
So firewalls sometimes block ICMP.

母 Real Internet Communication

Flow Example: Opening YouTube
Step 1
Laptop creates packet.

Step 2
Router performs NAT.

Step 3
Packet routed across Internet.

Step 4
ICMP may report errors if route fails.

Step 5
YouTube server replies.

霭 Summary
Concept Meaning
Routing Finding path for packets

Unicast One-to-one communication

Conce Meaning
pt
Broadca One-to-all communication
st
Multica One-to-group
st communication

NAT Private ↔ Public IP

conversion

ICMP Error reporting &

diagnostics

Important Exam Questions

Short Questions
1. Define routing.

2. Difference between unicast and multicast.

3. What is NAT?
4. Purpose of ICMP.

5. What is broadcast address?

Long Questions
1. Explain routing with diagram.
2. Compare unicast, multicast, and broadcast.
3. Explain NAT types with examples.
4. Explain ICMP messages and ping operation.
『 Numerical Example (Broadcast IP)
Given:
IP = [Link]
Mask = 25 5. 2 55 . 25 5. 0

Network bits = first 24

bits Broadcast IP:

[Link]
Lecture 22:

DHCP (Dynamic Host Configuration Protocol)

Introduction
Dynamic Host Configuration Protocol is a network management protocol used to automatically
assign IP addresses and other network configuration parameters to devices on a network.
Without DHCP, a network administrator would have to manually configure:

• IP Address
• Subnet Mask
• Default Gateway
• DNS Server
DHCP automates this process.

Why DHCP is Needed

Suppose a university lab has:

• 100 computers
• Multiple printers
• Student laptops
Manually assigning IP addresses to every device would:

• Take a lot of time

• Cause configuration errors
• Lead to duplicate IP addresses
DHCP solves these problems automatically.

Main Functions of DHCP

DHCP provides:

1. IP Address
2. Subnet Mask
3. Default Gateway
 4. DNS Server Address
5. Lease Time

Components of DHCP

1. DHCP Server
A server that assigns IP
addresses. Examples:

• Windows Server
• Linux DHCP Server
• Router acting as DHCP server

2. DHCP Client
A device requesting an IP
address. Examples:

• Laptop
• Mobile
phone • PC

3. DHCP Relay Agent

Used when DHCP server is on another network.

DHCP Working Process

DHCP uses a 4-step process called:

DORA Process

Step 1: Discover
The client broadcasts a message:
“Is there any DHCP server available?”
Step 2: Offer
DHCP server replies:
“Yes, I can provide this IP address.”

Step 3: Request
Client responds:

“I want to use this IP address.”

Step 4: Acknowledgment (ACK)

Server confirms:
“The IP address is assigned to you.”

DHCP Communication Diagram

Client DHCP Server

Discover -------------------->

< - -- - -- - -- -- - -- - -- -- - Offer

Request - - -- - - - - -- - - - - -- - - - - >

< -- --- -- -- --- -- --- -- - ACK

DHCP Ports
DHCP uses UDP protocol.

Device Port Number

DHCP Server
67 DHCP
Client 68
DHCP Lease
An IP address is assigned for a temporary time called a Lease.
Example:

• Lease Time = 24 hours

After expiration:

• Client renews the lease

• Or gets a new IP address

Types of DHCP Allocation

1. DynamicAllocation
IP changes over
time. Example:

• Public WiFi

[Link] Allocation
Permanent IP assigned automatically.

3. Manual/Static Allocation
Administrator binds MAC address with fixed
IP. Example:

• Printer
• Server

Advantages of DHCP
Advantage Centralized Management Efficient IP Usage
Automatic Configuration
Prevents IP Conflicts
 Explanation dministration
Reuses addresses
R
e
d
u
c
e
s

m
a
n
u
a
l

w
o
r
k

A
v
o
i
d
s

d
u
p
l
i
c
a
t
e

I
P
s

E
a
s
y

a
Disadvantages of DHCP
Disadvantage Explanation
Single Point of If DHCP server fails, clients cannot get
Failure Security IPs Rogue DHCP servers possible
Risks
Devices rely on DHCP server
Dependency

DHCP Example
Suppose a laptop joins a university
WiFi: DHCP assigns:

• IP: [Link]
• Subnet Mask: [Link]
• Gateway: [Link]
• DNS: [Link]
The laptop can now communicate on the network.

Distance Vector Routing

Protocol Introduction
Distance Vector Routing is a routing method in computer networks where routers share
routing information with neighboring routers to determine the best path to a destination.

It is called:
• Distance → Metric (usually hopcount)
• Vector → Direction/path to destination

Basic Concept
Each router maintains a Routing Table containing:

• Destination Network
• Distance (Metric)
• Next Hop
Routers periodically exchange routing tables with neighbors.

How Distance Vector Routing Works

Each router:
1. Knows directly connected networks
2. Shares routing table with neighbors
3. Updates routing table based on received information
4. Chooses shortest path

Routing Table
Example Router A
Destination Distance Next Hop

Network 0 Direct
1
Network 1 Router B
2
Network 2 Router C
3

Distance Metric
The metric measures path
cost. Common metrics:

• Hop Count
• Delay
• Bandwidth
Most distance vector protocols use:

Hop Count
Hop Count Example
Router A ---- Router B ---- Router C
From A to C:
• Hop Count = 2

Bellman-Ford Algorithm
Distance Vector Routing
uses: Bellman-Ford
Algorithm

The algorithm calculates:

• Shortest path
• Lowest cost route

Distance Vector Routing Process

Step 1
Router sends routing table to neighbors.

Step 2
Neighbor compares routes.

Step 3
If better route found:
• Update routing table

Step 4
Repeat periodically.

Example of Distance Vector Routing

A ----- B ----- C

Initially:
 • A knows only B

• B knows A and C
• C knows only B
After updates:

• A learns route to C through B

• C learns route to A through B

Characteristics of Distance Vector Routing

Feature Description
Periodic Updates Routers send updates
Neighbor Sharing regularly Only neighbors
Simple exchange info Easy to
Implementation configure
Slow Convergence Takes time after topology changes

Common Distance Vector Routing Protocols

1. RIP (Routing Information Protocol)
Routing Information
Protocol Features:

• Uses hop count

• Maximum 15 hops
• Simple protocol

2. IGRP
Interior Gateway Routing Protocol
Developed by:

• Cisco
Uses:
• Bandwidth
• Delay
• Reliability
Problems in Distance Vector Routing

1. Routing Loops
Packets circulate endlessly.

2. Count to Infinity Problem

Routers continuously increase hop count after link
failure. Example:

A thinks B knows route

B thinks A knows route

Both keep increasing distance.

Solutions to Distance Vector Problems

1. Split Horizon
Do not advertise route back to source.

2. Route Poisoning
Mark failed route with infinite metric.

3. Hold Down Timer

Prevents immediate incorrect updates.
Advantages of Distance Vector Routing
Advantage Explanation
Simple Easy to understand
Low CPU Usage Requires fewer resources
Easy Configuration Suitable for small
networks
Disadvantages of Distance Vector Routing
Disadvantage Explanation
Slow Convergence Slow response to changes
Limited Scalability Not ideal for large networks
Routing Loops Possible instability

DHCP vs Distance Vector Routing

Feature DHCP Distance Vector Routing
Purpose Assign IP Find best route
Works At addresses Host
Router
configuration
Main communication
DHCP Server
Device Router
Protocol Configuration
Protocol Routing Protocol
Type

Real-Life Analogy

DHCP
Like a hotel receptionist assigning room numbers to guests automatically.

Distance Vector Routing

Like people asking neighboring cities for the shortest road to another city.

Conclusion

DHCP
• Automates IP configuration

• Reduces manual effort

• Essential in modern networks
Distance Vector Routing
• Helps routers discover best paths
• Uses neighbor-to-neighbor updates
• Simple but less efficient for large networks
Lecture 23:

Link State Routing Protocol

Introduction
Link State Routing is a routing method in computer networks where each router builds a complete
map (topology) of the entire network and independently calculates the shortest path to every

destination.
Unlike Distance Vector Routing:
• Distance Vector shares routing tables with neighbors only.
• Link State Routing shares link information with all routers.

Basic Idea of Link State Routing

Each router:
1. Discovers its neighbors

2. Measures link costs

3. Creates Link State Advertisements (LSAs)
4. Floods LSAs throughout the network
5. Builds a complete topology database
6. Runs shortest path algorithm

Important Concepts
Ter Meaning
m
Connection between
Link
routers Condition/cost of
State
link
Topolo
gy Complete network
Cost map Metric of path
LSA Link State Advertisement
Working of Link State Routing

Step 1: Neighbor Discovery

Routers identify directly connected neighbors using HELLO packets.
Example:

Router A ----- Router B

A and B discover each other.

Step 2: Measure Link Cost

Router calculates:
• Delay
• Bandwidth
• Congestion

•
Reliability
Example:

• A to B cost = 2

Step 3: Create Link State Packet (LSP)

Each router creates packet containing:

• Router ID
• Neighbor list
• Link costs
• Sequence number

Step 4: Flooding
Router sends LSP to all routers in the
network. Flooding ensures:

• Every router gets identical topology information.

Step 5: Build Topology Database
Every router constructs a complete network graph.
Example:

B
/ \
A---C

All routers know the full structure.

Step 6: Run Dijkstra’s Algorithm

Routers compute shortest path tree using:

Dijkstra's
Algorithm This
determines:

• Best route
• Lowest cost path

Dijkstra’s Algorithm
The algorithm calculates shortest path from source router to all destinations.

Example Network
A ---1---
B |
| 4
2 |
| C ---1-
-- D

Shortest path from A to D:

• A →B → D
• Cost = 3

Shortest Path Formula

D(v)=\min{D(v),D(u)+c(u,v)}
Where:

• (D(v)) = distance to node (v)

 • (c(u,v)) = cost between nodes

Characteristics of Link State Routing

Feature Description
Complete Topology Every router knows entire
Knowledge
network Quickly adapts to
Fast Convergence changes
Event-Driven
Sends updates only on
Updates High CPU
Usage changes Complex
calculations required

Advantages of Link State Routing

Advantage Explanation
Fast Quickly detects failures
Convergence
Better path selection
Accurate
Routing Works well in large
Scalable networks Less chance of
Loop Reduction routing loops

Disadvantages of Link State Routing

Disadvantage Explanation
Complex Configuration Harder to
manage Higher Memory Usage
Stores full topology
CPU Intensive Runs shortest path calculations
Common Link State Routing Protocols

1. OSPF
Open Shortest Path
First Features:

• Open standard
• Uses Dijkstra algorithm

• Fast convergence
• Supports hierarchical routing
2. IS-IS
Intermediate System to Intermediate System
Commonly used by:

• Internet Service Providers (ISPs)

Distance Vector vs Link State Routing

Feature Distance Vector Link State
Network Knowledge Neighbor information only Full
topology Algorithm Bellman-Ford
Dijkstra
Updates Periodic Event-driven
Convergence Slow Fast
Complexity Simple Complex

Routing in the
Internet Introduction
The Internet is a massive collection of interconnected
networks. Routing in the Internet involves:

• Delivering packets across different networks

• Selecting best routes
• Managing scalability
The Internet uses a hierarchical routing structure.

Autonomous System (AS)

An Autonomous System is a group of routers and networks managed by a single organization.
Examples:

• University network

• ISP network
 • Company network
Each AS has:

• Unique ASN (Autonomous System Number)

Types of Routing in the Internet
Routing Type Description
Intra-AS Routing Routing within same AS
Inter-AS Routing Routing between different ASes

Intra-AS Routing

Definition
Routing inside a single Autonomous
System. Also called:

Interior Gateway Routing

Protocols
used: •
RIP

• OSPF
• IS-IS

Characteristics of Intra-AS Routing

Feature Description
Single Administration One organization controls
routing Faster Communication Internal optimization

Common Policies Same routing rules

Example of Intra-AS Routing
AS 1 0 0
A ----- B ----- C

All routers belong to same

organization. Routing occurs
internally.
Intra-AS Routing Protocols

1. RIP
Routing Information Protocol

• Distance Vector
• Hop count metric

• Small networks

2. OSPF
Open Shortest Path First
• Link State
• Fast convergence
• Large enterprise networks

3. IS-IS
Intermediate System to Intermediate System
• ISP backbone routing

Inter-AS Routing

Definition
Routing between different Autonomous
Systems. Also called:

Exterior Gateway Routing

Main
protoco
l: •
BGP
BGP (Border Gateway Protocol)
Border Gateway Protocol is the protocol used for routing between Autonomous Systems on the
Internet.

It is called:
• Path Vector Protocol

Why BGP is Needed

Different organizations:
• Have different policies
• Use different routing protocols
internally BGP allows communication
between them.

Example of Inter-AS Routing

AS1 --- -- -- - AS2 - -- --- -- AS3

Packets travel across multiple Autonomous Systems.

BGP Working
Routers called:

Border Routers
exchange:
• Reachability information
• AS path information

AS-PATH
BGP stores sequence of ASes a packet must travel through.
Example:

AS1 → AS5 → AS9

Helps:
• Avoid loops
• Select policies

BGP Route Selection Factors

BGP chooses routes based on:
1. AS Path Length
2. Policies
3. Next Hop
4. Local Preference

Types of BGP
Type Description
eBGP Between different
ASes iBGP Within same
AS

Hot Potato Routing

A router forwards packet to closest exit point as quickly as
possible. Purpose:

• Reduce internal network cost

Hierarchical Routing in Internet

The Internet uses hierarchy because:

• Millions of routers exist

• Flat routing is impossible
Hierarchy improves:

• Scalability
• Efficiency
• Management
Internet Routing Architecture
Internet

| | |
AS1 AS2 AS3

Each AS:
• Uses internal routing
• Connects externally through BGP

Comparison: Intra-AS vs Inter-AS Routing

Feature Intra-AS Inter-AS
Scope Within AS Between ASes
Protocols RIP, OSPF, IS-IS BGP
Goal Performance Policy & scalability
Administration Single organization Multiple
organizations

Real-Life Analogy

Intra-AS Routing
Like roads inside a university campus.

Inter-AS Routing
Like highways connecting different cities or countries.
Key Differences Between Routing Protocols
Protocol Type Algorithm
RIP Distance Vector Bellman-Ford
OSPF Link State Dijkstra
BGP Path Vector Policy-based
Conclusion

Link State Routing

• Routers maintain full network topology
• Uses Dijkstra’s algorithm

• Fast and scalable

• Used in OSPF and IS-IS

Routing in the Internet

• Internet divided into Autonomous Systems
• Intra-AS routing handles internal communication
• Inter-AS routing uses BGP between organizations
• Hierarchical routing enables scalability of the global Internet
Lecture 24:

Link Layer (Data Link Layer) — Detailed

Explanation
The Link Layer is the second layer of the OSI Model and the lowest layer in the TCP/IP protocol
stack that deals with communication between directly connected devices.
It is responsible for transferring data from one node to another node over a single
communication link.
Examples:
• Computer → Switch
• Switch → Router
• Laptop → WiFi Access Point
The Link Layer is covered in Chapter 5 of the book by James F. Kurose.

1. Introduction to Link Layer

Position in OSI Model

OSI Layer
Function
Application
Transport User services

Network End-to-end delivery

Routing
Link Layer
Node-to-node delivery
Physical Transmission of bits
The Link Layersits between:
• Network Layer (IP)
• Physical Layer

Main Purpose of Link Layer

The Link Layer performs:

1. Framing
2. Error Detection
 3. Error Correction
4. Flow Control
5. Medium Access Control
6. Link Access

What is a Frame?
At the Link Layer, data is encapsulated into a structure called a

Frame. Encapsulation Process

Layer Data Unit

Transp Segm
ort ent
Netwo Packe
rk t
Link Fra
Layer me
Physical Bits
Example:
[Header][Payload][Trailer]

The trailer often contains error detection bits.

Example of Link Layer

Technologies Wired Technologies
• Ethernet
• PPP (Point-to-Point Protocol)

Wireless Technologies
• WiFi (802.11)
• Bluetooth
2. Link Layer Services
The Link Layer provides several services to the Network Layer.
A. Framing
The Link Layer groups bits into frames.

Why Framing is Needed

The receiver must know:
• Where data starts
• Where data ends

Example:
| Header | Data | CRC |

B. Link Access (Medium Access Control)

Determines:
“Who can use the communication channel?”

Especially important in:

• Ethernet LANs
• WiFi networks
Example:
If multiple devices send simultaneously, collision occurs.
Protocols used:

• CSMA/CD (Ethernet)
• CSMA/CA (WiFi)

C. Reliable Delivery
Ensures frames arrive correctly.
Used mostly in:

• Wireless networks
• Noisy channels
Techniques:
• ACKs
• Retransmission
D. Flow Control
Prevents sender from overwhelming
receiver. Example:

• Fast sender
• Slow receiver
The Link Layer controls transmission speed.

E. Error Detection
Detects whether bits changed during
transmission. Methods:

1. Parity Check
2. Checksum
3. CRC

F. Error Correction
Some protocols can automatically correct
errors. Example:

• Hamming Code

3. Link Layer Addressing

Each device at the Link Layer has a unique physical address called:

MAC Address (Media Access Control

• 48 bits long
Address)

MAC Address Characteristics

• 48 bits long
 • Written in hexadecimal
Example:

00:1A:2B:3C:4D:5E

Structure of MAC Address

Part Meaning
First 24 bits Manufacturer
ID Last 24 bits Device ID

MAC Address vs IP Address

MAC Address IP Address
Physical address Logical address

Permanent Can change

Used in Used on
LAN Link Internet
Layer Network
Layer

Communication Example
Suppose:
• Laptop A sends data to Laptop
B Steps:

1. IP packet created at Network Layer

2. Link Layer adds MAC addresses

3. Frame transmitted
4. Receiver checks destination MAC
5. Data passed upward

Frame Format Example (Ethernet)

 Field Purpose
Destination MAC Receiver
Source MAC Sender
Type Protocol
 Field Purpose
Data Payload
CRC Error Detection

4. Error Detection Techniques

Transmission media may introduce:

• Noise
• Signal distortion
• Bit
flipping
Example:

Sent:
1011001

Receiv
ed:
101000
1

One bit changed.

The Link Layer uses error detection methods.

A. Parity Check
One of the simplest error detection methods.
Idea of Parity Bit
An extra bit is added to
data. Purpose:

• Make number of 1s either:

• Even (Even parity)
• Odd (Odd parity)

Even Parity
If number of 1s is odd:
 • Add parity bit = 1
If already even:

• Add parity bit = 0

Example 1
Data:
1011001

Number of 1s = 4 (even)
Parity bit
= 0
Transmitte
d:
10110010

Example 2
Data:
1011011

Number of 1s = 5 (odd)
Parity bit
= 1
Transmitte
d:
10110111

How Receiver Checks

Receiver counts number of
1s. If parity rule violated:

• Error detected
Advantages of Parity Check
• Simple
• Low cost
 • Easy implementation

Disadvantages
Cannot detect:
• Multiple bit errors in some cases

Example:
If two bits change:
• Parity may still remain correct

Types of Parity
Type Description
Single-bit parity One parity bit
Two-dimensional parity Row & column parity

B. Check Summing Method (Checksum)

A more powerful error detection
technique. Widely used in:

• IP

•
TCP
•
UDP
Basic Idea
1. Divide data into fixed-size words
2. Add all words
3. Store result as checksum
4. Receiver repeats calculation
5. Compare results
Example of Checksum
Supposedata:
1010
1100
1001

Step 1: Add binary values

1010
1100
1001

11111

Step 2:
Overflow wrapped around.

Step 3:
Complement result.

This becomes checksum.

At Receiver
Receiver:
• Adds received data
• Adds
checksum If result is
correct:

• No error
Otherwise:
• Error detected
Advantages of Checksum
• Better than parity

• Detects many common errors

• Efficient
Disadvantages
Cannot detect all possible errors.

Comparison: Parity vs Checksum

Feature Parity Checksum
Complexity Very low Moderate

Extra bits 1 bit Several bits

Error detection capability Weak Better

Detects single-bit Y Yes

errors Detects burst es Better
errors P
o
or

Real-World Example
Suppose you download a
file. During transmission:

• Noise changes
bits. The checksum at
receiver:

• Detects
corruption. Then:

• Packet retransmission occurs.

Important Terms
 Term Meaning
Frame Link Layer data unit
MAC Physical device address
Address Detect transmission
Error errors Extra bit for
Detection parity
Parity Sum used for validation
Bit
Checks
um

Summary
The Link Layer is responsible for:

• Node-to-node communication
 • Framing
• Physical addressing

• Error detection
• Medium access control
Important concepts include:

• MAC addressing

• Frames
• Parity checking

• Checksum method
Error detection ensures reliable communication by identifying corrupted frames before data reaches
upper layers.
Lecture 25:

CRC (Cyclic Redundancy Check)

CRC is one of the most powerful and widely used error detection techniques in computer
networks.

It is used in:
• Ethernet
• WiFi
• Hard disks
• USB
• Satellite communication
CRC belongs to the Link Layer (Data Link Layer).

Why CRC is Needed

During transmission:

• Noise
• Signal interference
• Electromagnetic disturbance
may change bits.

Example:
Sent:

110101

Received:
110111

One bit changed.

CRC helps detect such errors efficiently.
Basic Idea of CRC
CRC treats data as a binary number and performs:
 • Binary division
using:
• A predefined divisor called the Generator Polynomial
The remainder obtained after division is called:

CRC bits
These bits are appended to the original data.

Important Terms in CRC

Term Meaning
Dataword Original data
Generator Divisor
polynomial Codeword Data
+ CRC bits

CRC remainder Error checking bits

CRC
Process
Sender Side
Step 1: Select Generator Polynomial
Examp
le:
1011

Length = 4
bits Degree
=3

Step 2: Append Zeros

If generator length is 4:
• Append 3 zeros to data.
Supposedata:

110101

Append 3 zeros:
110101000
Step 3: Binary Division (Modulo-2 Division)
Perform XOR division using
generator. Rules:

• No borrowing
• No carrying
• XOR operation
only XOR rules:

A B XOR
0 0 0
0 1 1
1 0 1
1 1 0

Step 4: Obtain Remainder

Suppose remainder
is: 011

Step 5: Create Final Frame

Final transmitted
codeword: 110101011

(Data + remainder)

Receiver Side
Receiver performs the same division.

If remainder = 0
→ No error detected

If remainder ≠ 0
→ Error detected
Why CRC is Powerful
CRC can detect:
• Single-bit errors

• Double-bit errors
• Burst errors
Especially effective for burst errors.

Burst Error
Multiple consecutive bits become
corrupted. Example:

111000111

↓
110111111

Several bits changed together.

CRC is very effective against this.

Advantages of CRC
Advantage Explanation
High Detects many error patterns
accuracy Fast hardware
Efficient implementation Used in
Reliable realnetworks
Detects burst Better than parity/checksum
errors

Disadvantages of CRC
• Slightly complex
• Requires polynomial division hardware/software
Polynomial Representation
Binary:
1011

Polynomial:
x³ + x + 1

CRC Example Concept

Suppose:
• Data = 100100

• Generator =
1101 The sender:

1. Appends zeros
2. Divides using XOR

3. Adds remainder
Receiver:
1. Repeats division

2. Checks remainder
Channel Partitioning Protocols
In a shared communication channel:
• Multiple users want to transmit
simultaneously. Question:

How should the channel be shared fairly?

Channel partitioning protocols divide the channel among

users. Main techniques:

1. TDMA
2. FDMA
3. CDMA
These are called:

Multiple Access Protocols

1. TDMA (Time Division Multiple Access)
In TDMA:
• Time is divided into slots.
• Each user gets a fixed timeslot.

Working of TDMA
Example:

Suppose 4
users: •
A

•
B
•
C

• D
Time division:

Time Slot User

1
A 2
B 3
C 4
D Then
repeats.

Visualization
| A | B | C | D | A | B | C | D

| Only one user transmits at a time.

Features of TDMA
Feature Description
Shared channel Yes
Collision
Avoided Synchronization
needed Yes
Advantages of TDMA
• No collisions
• Efficient channel sharing

• Simple concept

Disadvantages
• Time synchronization required
• Empty slots waste bandwidth

Example:
If user B has no data:
• Slot remains unused

Real-World Uses
• GSM mobile networks
• Satellite communication

2. FDMA (Frequency Division

Multiple Access)
In FDMA:
• Frequency spectrum divided into bands.
• Each user gets separate frequency.

Working of FDMA
Example:

F4 D
Frequency Band User
F1 A
F2 B
F3 C

F4 D
All users transmit simultaneously.

Visualization
Frequency
Spectrum
|A|B|C|D|

Features of FDMA
Feature Description
Separate frequencies
Yes Simultaneous
transmission Yes Guard
bands needed Yes

Guard Bands
Small unused frequency gaps to prevent interference.

Advantages of FDMA
• Continuous transmission possible
• No time synchronization needed
• Low delay

Disadvantages
• Bandwidth wastage
• Guard bands reduce efficiency
• Limited frequencies

Real-World Uses
• Radio broadcasting
• Traditional telephone systems
3. CDMA (Code Division Multiple Access)
CDMA is more
advanced. In CDMA:

• All users use:

• Same frequency

• Same time
But:
• Different unique codes are assigned.

Basic Idea of CDMA

Each sender has:
• Unique binary code
Receiver extracts desired signal using matching code.

Analogy
Imagine:
• Many people speaking in different languages
simultaneously. You understand only:

• Your
language.
Similarly:

• Receiver extracts matching coded signal.

Working of CDMA
Suppose:
• User A code = 1010
• User B code = 1100
Signals overlap.
Receiver:
• Uses correlation techniques

• Retrieves intended data

Features of CDMA
Feature Description
Same frequency
Yes Same time
Yes Different
codes Yes

Advantages of CDMA
• High capacity

• Better bandwidth utilization

• Resistant to interference
• More secure

Disadvantages
• Complex implementation
• Difficult code management
• Expensive hardware

Real-World Uses
• 3G mobile
systems • GPS

• Military communication
Comparison of TDMA,FDMA, and CDMA
Feature TDMA FDMA CDMA

Division Basis Time Frequenc Code

y
Simultaneous No Yes Yes
Users

Synchronization Requir Not Complex

ed needed coding
Efficiency Mediu Medium High
m
Complexity Low Low High

Example Analogy
Imagine a classroom:

TDMA
Students speak one after another.

FDMA
Students speak at same time but different rooms.

CDMA
Students speak together in same room but different languages.

Summary

CRC
• Powerful error detection technique

• Uses modulo-2 division

• Detects burst errors effectively
TDMA
• Divides channel using timeslots

FDMA
• Divides channel using frequencies
CDMA
• Uses unique codes for multiple users
These techniques are fundamental in:

• Wireless communication
• Cellular networks
• Satellite systems
• Modern networking systems
Lecture 26:

Multiple Access Protocols

In computer networks, many devices often share a single communication channel.
Example:

• Multiple computers connected to the same WiFi

• Multiple users using a satellite channel
• Devices connected to Ethernet LAN
A major problem arises:

“How can multiple users transmit data without interfering with each other?”

To solve this problem, networks use:

Multiple Access Protocols

These protocols decide:

• When a device can transmit

• How collisions are handled
• How shared channels are used efficiently

Types of Multiple Access Protocols

There are three major categories:

Category Examples
Channel TDMA, FDMA, CDMA
Partitioning
Random Access ALOHA, Slotted ALOHA,
CSMA
Taking Turns Polling, Token Passing
Here we focus on:

1. ALOHA

2. Slotted ALOHA
These are:

Random Access Protocols

Random Access Protocols
In random access protocols:
• Any station can transmit whenever it has data.

• No fixed schedule exists.

Problem:
If two stations transmit simultaneously:

Collision occurs

What is Collision?
Collision occurs when:
• Two or more devices send frames at the same time on the same
channel. Result:

• Frames become corrupted

• Data must be retransmitted

ALOHA Protocol
ALOHA is one of the earliest random access protocols.

Developed at:
University of
Hawaii Used
originally for:

• Wireless radio communication

Basic Idea of ALOHA

Rule:
“Transmit whenever you have data.”

No checking.
No synchronization.
If collision occurs:
 • Wait random time
• Retransmit

Working of Pure ALOHA

Suppose Station A has a frame.

Step 1
Station A transmits immediately.

Step 2
Receiver sends acknowledgment
(ACK). If ACK received:

• Transmission
successful If ACK not
received:

• Collision assumed

Step 3
Station waits random amount of time.
Then retransmits.

Visualization of Pure ALOHA

Suppose:
A transmits at time t

B transmits at time t+1

Signals overlap:
Collision occurs

Both frames lost.

Vulnerable Time in Pure ALOHA
Very important concept.

Vulnerable Time
The time during which another transmission can cause collision.
For Pure ALOHA:

Vulnerable Time = 2 × Frame Transmission Time

Why 2T?
Suppose:
• Frame transmission time = T
Collision occurs if another frame starts:
• T time before transmission
• T time after transmission

Tot
al:
2T

Throughput of Pure ALOHA

Throughput means:
Successful data transmission

rate Maximum throughput:

genui {"math_block_widget_always_prefetch_v2":{"content":"S = Ge^{-2G}"}}

Maximum efficiency:

18 .4%

Meaning:
• Only 18.4% of channel capacity used
successfully. Very inefficient.
Advantages of Pure ALOHA
Advantage Explanation
Simple Easy implementation
No synchronization Stations independent
Flexible Easy for distributed systems

Disadvantages of Pure ALOHA

Disadvantage Explanation
High collisions Frequent retransmissions
Low efficiency Only 18.4%

Poor channel utilization Bandwidth wasted

Slotted ALOHA
Slotted ALOHA improves Pure
ALOHA. Idea:

Divide time into

equalslots. A station can

transmit:

• Only at beginning of a slot.

Key Rule of Slotted ALOHA

Transmit only at slot boundaries
Working of Slotted ALOHA
Supposeslots:
|Slot1|Slot2|Slot3|Slo t

4| If Station A wants to

send:

• It waits until next slot starts.

Collision in Slotted ALOHA
Collision occurs only if:

• Two stations choose same slot.

Vulnerable Time in Slotted ALOHA

For Slotted ALOHA:
Vulnerable Time =

T Only one frame

time.

This reduces collisions significantly.

Throughput of Slotted ALOHA

Maximum throughput:
genui {"math_block_widget_always_prefetch_v2":{"content":"S = Ge^{-G}"}}
Maximum efficiency:

36 .8%

Much better than Pure ALOHA.

Comparison: Pure ALOHA vs Slotted

ALOHA
Feature Pure ALOHA Slotted ALOHA
Synchronization Not needed Required
Transmission Time Anytime Slot boundaries only
Vulnerable Time 2T T
Maximum Efficiency 18.4% 36.8%
Collision Probability Higher Lower

Why Slotted ALOHA is Better

Because:
• Time synchronization reduces overlap chances.
• Devices transmit in organized intervals.
Thus:
• Fewer collisions
• Better throughput

Example Scenario
Suppose:
• 5 users share channel.

In Pure ALOHA
Users transmit anytime:
• Many overlaps

• More collisions

In Slotted ALOHA
Users wait for slots:
• Better coordination
• Fewer collisions

Mathematical Understanding
Where:
• ( G ) = average transmission attempts
• ( S ) = successful
throughput Pure ALOHA:

genui {"math_block_widget_always_prefetch_v2":{"content":"S = Ge^{-2G}"}}

Slotted ALOHA:

genui {"math_block_widget_always_prefetch_v2":{"content":"S = Ge^{-G}"}}

Since exponent is smaller in Slotted ALOHA:

• Throughput improves.
Real-World Importance
ALOHA concepts influenced:

• Ethernet
• WiFi
• Modern MAC protocols
Though Pure ALOHA is rarely used directly today, its principles are foundational in networking.

Important Terms
Term Meaning
Collision Simultaneous transmissions

Throughput Successful transmission rate

Vulnerable Time during which collision can occur

Time
Random Stations transmit freely
Access
Slot Fixed transmission interval

Summary

Pure ALOHA
• Send anytime
• Very simple
• High collisions

• Efficiency = 18.4%

Slotted ALOHA
• Time divided into slots
• Lower collision probability
• Better efficiency = 36.8%
Both are important random access protocols that laid the foundation for modern medium access
control techniques used in computer networks.
Lecture 27:

Multiple Access Protocols

In a shared communication medium:
• Multiple devices use the same channel.
• If two devices transmit simultaneously:

Collision occurs
To reduce or avoid collisions, networks use:

Multiple Access Protocols

Previously:
• ALOHA
• Slotted ALOHA
Now we discuss more efficient protocols:

1. CSMA/CD
2. CSMA/CA
3. ARP (Address Resolution Protocol)
These concepts are covered in Chapter 5 of the book by James F. Kurose.

1. CSMA (Carrier Sense Multiple Access)

Before understanding CSMA/CD and CSMA/CA, first understand CSMA.

Basic Idea of CSMA

Rule:
 “Listen before transmitting.”

A station:

1. Checks whether channel is busy or idle.

2. If idle → transmit.
 3. If busy → wait.
This reduces collisions compared to ALOHA.

Why CSMA is Better than ALOHA

In ALOHA:
• Stations transmit
anytime. In CSMA:

• Stations first sense the

channel. Thus:

• Fewer collisions
• Better efficiency

Example of CSMA
Suppose:
• Station A transmitting.
• Station B wants to
send. Station B:

• Detects busy channel.

• Waits.
After channel becomes free:
• B transmits.

Limitation of CSMA
Due to propagation delay:
• Two stations may still start transmission simultaneously.
Thus:

Collision can still occur

To improve CSMA:
 • CSMA/CD introduced
• CSMA/CA introduced

2. CSMA/CD (Carrier Sense Multiple

Access with Collision Detection)
Used mainly in:

Ethernet LANs

Basic Idea
Stations:
1. Sense channel before transmission.
2. Continue monitoring during transmission.
3. Detect collisions if they occur.
4. Stop transmission immediately after collision detection.

Key Concept
Sense → Transmit → Detect Collision → Stop → Retransmit

Working of CSMA/CD

Step 1: Carrier Sensing

Station checks
channel. If:

• Idle → transmit
• Busy → wait
Step 2: Transmission
Station starts sending frame.

Step 3: Collision Detection

While transmitting:
• Station listens to
medium. If signal differs:

• Collision detected.

Step 4: Jam Signal

Station sends:

Jam Signal
Purpose:
• Inform all devices about collision.

Step 5: Stop Transmission

All colliding stations stop immediately.

Step 6: Random Backoff

Each station waits random time before
retransmission. This uses:

Binary Exponential Backoff

Binary Exponential Backoff

After collision:
 • Random waiting time chosen.
After repeated collisions:
 • Waiting range doubles.
Example:

Collision Number Waiting Range

1st 0–1
2nd 0–3
3rd 0–7
This reduces repeated collisions.

Example of CSMA/CD
Suppose:
• A and B sense channel idle simultaneously.

• Both transmit.
• Signals collide.

Stations:
• Detect collision
• Send jam signal
• Stop transmission

• Wait random time

• Retransmit later

Collision Detection Time

Minimum frame size in Ethernet exists because:
• Sender must still be transmitting when collision returns.

Advantages of CSMA/CD
Advantage Explanation
Better efficiency Fewer
collisions Immediate collision handling
Saves bandwidth Dynamic sharing
Flexible
Disadvantages
Disadvantage Explanation
Collisions still occur Not collision-free

Not suitable for wireless Hard to detect

collisions
Performance decreases under heavy Many
load retransmissions

Why CSMA/CD Not Used in Wireless?

In wireless:
• A device cannot transmit and listen simultaneously effectively.
• Signal strength issues
occur. Therefore:

Collision detection is difficult in

wireless networks
Hence wireless uses:

CSMA/CA

3. CSMA/CA (Carrier Sense Multiple

Access with Collision Avoidance)
Used mainly in:

WiFi Networks (IEEE 802.11)

Basic Idea
Instead of detecting collisions:

Try to avoid collisions before transmission

Why Collision Avoidance?
Wireless devices cannot reliably detect collisions during transmission.
Thus:

• Prevent collisions rather than detect them.

Working of CSMA/CA

Step 1: Channel Sensing

Station listens to
channel. If busy:

•
Wait If
idle:

• Continue

Step 2: Wait Interframe Space (IFS)

Even if channel idle:
• Station waits short fixed
time. Purpose:

• Prioritize ongoing communication.

Step 3: Random Backoff Timer

Station chooses random
timer. Countdown begins
only when:

• Channel remains
idle When timer becomes
zero:

• Transmit frame
This reduces simultaneous transmissions.
Acknowledgment Mechanism
Receiver sends:

ACK (Acknowledgment)
If sender does not receive ACK:
• Collision assumed
• Retransmission occurs

RTS/CTS Mechanism
Optional feature in WiFi.

RTS = Request To Send

CTS = Clear To Send

Purpose:
• Reduce hidden terminal problem

Hidden Terminal Problem

Suppose:
• A and C cannot hear each other.
• Both communicate with B.
A and C may transmit simultaneously:

• Collision at B.
RTS/CTS helps prevent this.

RTS/CTS Working
Step 1
Sender sends RTS.
Step 2
Receiver replies CTS.

Step 3
Other devices hearing CTS remain silent.

Step 4
Sender transmits safely.

Advantages of CSMA/CA
Advantage Explanation
Suitable for wireless Avoids collisions
Better wireless performance Efficient medium
sharing RTS/CTS improves reliability Handles
hidden terminals

Disadvantages
Disadvantage Explanation
More overhead ACKs,timers,
RTS/CTS Backoff
Delay due to
increases latency
waiting Not
Collisions still
collision-free
possible
Comparison: CSMA/CD vs CSMA/CA
Feature CSMA/CD CSMA/CA
Used In Ethernet WiFi
Collision Handling Detects collision Avoids collision
Collision Detection Yes No
ACK Required No Yes
RTS/CTS No Optional
Suitable for Wireless No Yes

4. ARP (Address Resolution Protocol)

ARP stands for:
Address Resolution Protocol
Used to map:

IP Address → MAC Address

Why ARP is Needed

Communication inside LAN requires:

• MAC addresses
But applications usually know:
• IP
addresses
Question:

How to find MAC address corresponding to an

IP? Answer:

ARP

Example
Suppose:
Device IP Address MAC Address
A [Link] AA-
AA B [Link]
BB-BB A wants to send
packet to B. A knows:

• B’s IP
address But needs:

• B’s MAC
address ARP resolves
this.
ARP Working

Step 1: Check ARP Cache

Device first checks:

ARP Table / ARP Cache

If mapping exists:
• Use directly

Otherwise:
• Send ARP Request

Step 2: ARP Request Broadcast

Sender broadcasts:
Who has IP 192 .168 .1
.5? Tell 1 9 2 . 1 6 8 . 1 . 2

Broadcast MAC:
FF:FF:FF:FF:FF:FF

All devices receive request.

Step 3: ARP Reply

Correct device replies:
1 9 2 . 1 6 8 . 1 . 5 is

BB- BB Reply sent

unicast.
Step 4: ARP Cache Update
Sender stores mapping:

IP MAC
[Link] BB-BB
Future communication faster.
ARP Packet Fields
Field Purpose
Sender IP Source IP
Sender MAC Source MAC
Target IP Destination IP
Target MAC Destination MAC

Types of ARP
Type Description
Standard ARP IP → MAC
Gratuitous ARP Announces own
IP/MAC Reverse ARP (RARP) MAC → IP

ARP Cache
Temporary table storing
mappings. Command in Linux:

arp - a

or
ip neigh

Advantages of ARP
Advantage Explanation
Automatic mapping Easy
communication Fast local communication
Uses cache

Essential for LANs Core protocol

Disadvantages / Security Issues

ARP has no authentication.
Thus:
ARP Spoofing / ARP Poisoning possible
Attacker sends fake ARP replies.
Can cause:

• Man-in-the-middle attacks
• Traffic interception

Summary

CSMA/CD
• Used in Ethernet
• Detects collisions
• Stops transmission immediately after collision

CSMA/CA
• Used in WiFi
• Avoids collisions before transmission
• UsesACKs and backoff timers

ARP
• Maps IP addresses to MAC addresses

• Essential for LAN communication

• Uses ARP requests and replies
These protocols are fundamental components of modern computer networking systems and enable
efficient communication over shared networks.
“Dear students Very easy just follow all steps
error Detected or error not Detected both
examples are given”

Error Detection Using Checksum — Detailed

Explanation
What is Checksum?
A Checksum is an error detection technique used in computer networks to detect whether data has
been corrupted during transmission.
It is commonly used in:
• IP

• TCP
• UDP

The checksum method belongs to the Link Layer and also used in higher layers like the Transport
Layer.

Basic Idea of Checksum

The sender:
1. Divides data into equal-sized words
2. Adds all words using binary addition
3. Takes complement of the sum
4. Sends this value as checksum
The receiver:

1. Adds received data and checksum

2. If result is all 1s (or complement becomes 0)
→ No error
 3. Otherwise
→ Error detected

Why Checksum is Needed

During transmission:

• Noise
• Signal interference
• Hardware
faults may change
bits.

Example:
Sent:
1Θ1Θ1Θ1Θ

Receiv
ed:
1Θ1Θ11
1Θ

One bit changed.

Checksum helps detect this corruption.
Steps of Checksum Method
At Sender:
1. Divide data into segments

2. Add segments
3. Add carry (if any)
4. Take 1’s complement

5. Attach checksum
At Receiver:
1. Add all segments including checksum
2. If result = all
1s → No
error

3. Else
→ Error detected
Example of Checksum (Detailed)
Suppose sender wants to transmit three 4-bit words.
Data words:

1Θ1Θ
11ΘΘ
1ΘΘ1

Step 1: Add First Two Words

We add using binary arithmetic.
1Θ1Θ
+ 11ΘΘ

1Θ11Θ

Result:
1Θ11Θ

Since we are using 4-bit words:

• Leftmost carry = 1
• Remaining bits = 0110
Add carry back:

Θ11Θ
+ 1

Θ111

Intermediate result:
Θ111

Step 2: Add Third Word

Now add:
1ΘΘΘΘ
Θ111
1ΘΘ1

Binary addition:
Θ111
+ 1ΘΘ1
------

1ΘΘΘΘ
Again:
• Carry = 1
• Remaining bits = 0000
Add carry back:

0000
+ 1

0001

Final sum:
0001

Step 3: Take 1’s Complement

Complement means:
• Change 0 → 1

• Change 1
→ 0 Complement
of:
0001

is:
11
10

This becomes:

Checksum
Step 4: Transmitted Data
Sender sends:

Data
Word 1
1010 Word 2
1100 Word 3
1001
Checksum
1110
Receiver Side Verification
Receiver receives:
1010
1100
1001
1110

Now receiver adds all values.

Step 5: Add First Two Words

1010
1100
-----
10110

Carry
wraparound:
0110 + 1 =
0111

Step 6: Add Third Word

0111
1001

10000

Carry
wraparound:
0000 + 1 =
0001
Step 7: Add Checksum
0001
1110

1111

Res
ult:
111
1
Step 8: Complement Result
Complement of:
1111

is:
0000

Since result is all zeros:

No Error Detected
Transmission successful.

Example with Error

Suppose one bit changes during transmission.
Received data:

1010
1100
1011
1110

Notice:
• Original = 1001
• Changed = 1011
Now receiver performs addition.
Final result will NOT become:

1111

Complement will not be:

0000

Thus:

Error Detected
Important Concept: 1’s Complement Addition
In checksum:
• Extra carry is wrapped around and added again.
This is very important.

Why Complement is Used

Complement improves error detection
capability. Without complement:

• Some errors may remain undetected.

Advantages of Checksum
Advantage Explanation
Sim Easy to implement
ple
Efficient
Fast
computation
Better than Detects more
parity Widely errors
used
TCP/IP protocols

Disadvantages of Checksum
Disadvantage Explanation
Cannot detect all errors Some patterns remain
undetected Less powerful than CRC CRC more reliable

Checksum vs Parity vs CRC

 Feature Parity Checksum CRC
Complexity Very Medium Higher
Error Detection low Better Very strong
Weak Moderate Excellent
Burst Error
Detection Used In Poor TCP/IP Ethernet
Simple
systems
Real-Life Analogy
Imagine:

• Teacher calculates total marks of students.

• Another teacher recalculates total.
If totals differ:

• Mistake detected.
Checksum works similarly.

Mathematical View
Supposedata
words: D1, D2,
D3

Checksum:
Checksum = Complement(D1 + D2 +

D3) Receiver verifies:

D 1 + D 2 + D 3 + Checksum = All 1 s

Practical Uses of Checksum

Used in:

•
TCP
•
UDP

• IP headers
• File downloads
• Memory systems
Example:
When downloading files:
• Checksum verifies integrity.
Summary

Checksum Error Detection Process

Sender
1. Divide data into words
2. Add all words
3. Wrap carry
4. Take complement

5. Send checksum

Receiver
1. Add all received words
2. Add checksum
3. If result = all 1s
→ No error

4. Else
→ Error detected

Key Points
• Checksum detects transmission errors.
• Uses binary addition and complement arithmetic.
• More powerful than parity checking.
• Simpler but less powerful than CRC.
• Widely used in networking protocols like TCP/IP.