UNIT – II : Data Link Layer

 Fundamentals of Error Detection and Error

Correction, Block coding, Hamming Distance, CRC;
 Flow Control and Error control protocols - Stop and
Wait, Goback-N ARQ, Selective Repeat ARQ, Sliding
Window, Piggybacking,
 Random Access,Multiple access protocols - Pure
ALOHA, Slotted ALOHA, CSMA/CD, CDMA/CA
Services

 Framing
 Flow Control
 Error Control
 Physical addressing
 Access Control (Medium
Access Control)
Basic concepts
 Networks must be able to transfer data from
one device to another with complete
accuracy.
 Data can be corrupted during transmission.
 For reliable communication, errors must be
detected and corrected.
 Error detection and correction are
implemented either at the data link layer or
the transport layer of the OSI model
Note

Data can be corrupted

during transmission.

Some applications require that

errors be detected and corrected.
Types of Errors
Note

In a single-bit error, only 1 bit in the data

unit has changed.
Single-bit error
Causes

• Thermal noise
• Random electrical interference
• Short disturbance on the channel
Characteristics

Rare in wired, reliable channels

Easy to detect using:
• Parity check
• Checksum
• CRC
Note

A burst error means that 2 or more bits

in the data unit have changed.
Burst error of length 8

Burst length = distance from the first corrupted bit to the last corrupted
bit, inclusive.
Causes

 Noise lasting for a longer duration

 Signal fading
 Crosstalk
 Wireless channel interference
Characteristics

• Very common in wireless and long-distance

communication
• Harder to detect and correct
• CRC is highly effective for burst errors
Note

•Single bit error: Only one bit of the data unit is changed during transmission.
•Burst error: Two or more bits in a data unit are corrupted, often over a continuous
span.
ERROR DETECTION

 Error detection means to decide whether

the received data is correct or not without
having a copy of the original message.
 Error detection uses the concept of
redundancy, which means adding extra
bits for detecting errors at the destination
 There are 3 ways in which we can detect
errors in the received message :
1. Parity Bit
2. CheckSum
3. Cyclic Redundancy Check (CRC)
What is parity bit?

 A parity bit is an extra bit that is added to

the message bits or data-word bits on the
sender side.
 Data-word bits along with parity bits is
called a codeword.
 The parity bit is added to the message
bits on the sender side, to help in error
detection at the receiver side.
A parity bit is an extra bit added to a data
unit to make the total number of 1s even or
odd, used for error detection.
Parity check

 The parity check is done by adding an

extra bit, called parity bit, to the data to
make the number of 1s either even or odd
depending upon the type of parity.
 The parity check is suitable for single bit
error detection only.
Note

To detect or correct errors, we need to

send extra (redundant) bits with data.
 Note
Redundant bits are added by the sender and removed by the receiver.
Their presence allows the receiver to detect or correct corrupted bits.
Even Parity Check

Total number of 1’s in the given data bit should be even. So if the total number of 1’s
in the data bit is odd then a single 1 will be appended to make total number of 1’s
even else 0 will be appended(if total number of 1’s are already even). Hence, if any
error occurs, the parity check circuit will detect it at the receiver’s end.
Example
 Suppose that a sender wants to send the data 1001101 using even parity
check method. It will add the parity bit as shown below.

 The receiver will decide whether an error has occurred by counting

whether the total number of 1s is even.
Odd Parity
 In odd parity system, if the total number of 1’s in the
given binary string (or data bits) are even then 1 is
appended to make the total count of 1’s as odd else 0 is
appended.
 The receiver knows that whether sender is an odd parity
generator or even parity generator. Suppose if sender is
an odd parity generator then there must be an odd
number of 1’s in received binary string.
 If an error occurs to a single bit that is either bit is
changed to 1 to 0 or 0 to 1, received binary bit will have
an even number of 1’s which will indicate an error.
The structure of encoder and decoder
Error Detection Using Parity
Single Bit Error – DETECTED
Transmitted (even parity):
10110010
Received:
10100010
Number of 1s = 3 (odd) ❌
➡ Error detected

❌ Two Bit Error – NOT Detected

Received:
10000010
Number of 1s = 2 (even) ✔
➡ Error not detected

Parity fails for even number of errors

Note

A simple parity-check code can detect

an odd number of errors.
What Parity Can and Cannot Do

Feature Parity Bit

Detect single bit error ✅ Yes
Detect burst error ❌ No (generally)
Detect odd number of errors ✅ Yes
Detect even number of errors ❌ No
Error correction ❌ No
Two-dimensional parity
 Two-dimensional parity is exactly what the
name suggests
 It is based on “simple” (one-dimensional)
parity, which usually involves adding one
extra bit to a 7-bit code to balance the
number of 1s in the byte.
Two-dimensional parity
 Two-dimensional parity does a similar calculation for each bit position
across each of the bytes contained in the frame
 This results in an extra parity byte for the entire frame, in addition to a
parity bit for each byte
 Two-dimensional parity catches all 1-, 2-, and 3-bit errors and most 4-bit
errors
 Two-dimensional Parity check bits are calculated for each row, which is
equivalent to a simple parity check bit.
 Parity check bits are also calculated for all columns, then both are sent
along with the data.
 At the receiving end, these are compared with the parity bits calculated on
the received data.
Two-dimensional parity

Two Dimensional Parity

Example
CHECKSUM
What is a Checksum?
• A checksum is an error-detection technique used in computer
networks and data storage to verify the integrity of data during
transmission or storage.
• It works by computing a small fixed-size value (the checksum) from the
data and sending it along with the data.

Why is Checksum needed?

During transmission, data may get corrupted due to:
• Noise
• Interference
• Hardware faults
The checksum helps the receiver detect whether errors occurred.
Checksum at Sender Side
• Data is divided into fixed-size words (e.g., 16 bits).
• All words are added using 1’s complement arithmetic.
• The 1’s complement of the sum is the checksum.
• Checksum is sent along with the data.

Checksum at Receiver Side

• Receiver adds all received data words + checksum.
• Takes 1’s complement of the result.
• If result = ALL 0s → No error
• Else → Error detected
 Internet Checksum Example
 Note
 When adding numbers, a carryout from the
most significant bit needs to be added to
the result
 Example: add two 16-bit integers

1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

wraparound 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1

1
sum 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0
checksum 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1
Solve?
W1 = 1010101010101010
W2 = 0101010101010101
Where is Checksum Used?
 Transport Layer: TCP, UDP
 Internet protocols
 File transfer
 Disk storage
 Email transmission
Advantages
✔ Simple
✔ Fast
✔ Low computational cost

Limitations
 Cannot detect all types of errors
 Less powerful than CRC
 Not suitable for cryptographic security
CRC
Process of error detection in block coding
BLOCK CODING

In block coding, we divide our message into blocks,

each of k bits, called datawords. We add r redundant
bits to each block to make the length n = k + r. The
resulting n-bit blocks are called codewords.
CYCLIC CODES

Cyclic codes are special linear block codes with one

extra property. In a cyclic code, if a codeword is
cyclically shifted (rotated), the result is another
codeword.
Cyclic Redundancy Check CRC
CYCLIC REDUNDANCY CHECK
 Given a k-bit frame or message, the transmitter
generates an n-bit sequence, known as a frame
check sequence (FCS), so that the resulting
frame, consisting of (k+n) bits, is exactly
divisible by some predetermined number.
 The receiver then divides the incoming frame by
the same number and, if there is no remainder,
assumes that there was no error.
CRC encoder and decoder
Division in CRC encoder
Division in the CRC decoder for two cases
Note

The divisor in a cyclic code is normally

called the generator polynomial
or simply the generator.
A polynomial to represent a binary word
Standard polynomials
Q1

 A bit stream 1101011011 is transmitted

using the standard CRC method. The
generator polynomial is x4+x+1. What is
the actual bit string transmitted?
Q2

 A bit stream 10011101 is transmitted

using the standard CRC method. The
generator polynomial is x3+[Link] is the
actual bit string transmitted? Suppose the
third bit from the left is inverted during
transmission. How will receiver detect this
error?
Q3
Q4
Note

An error-detecting code can detect

only the types of errors for which it is
designed; other types of errors may
remain undetected.
Structure of encoder and decoder in error correction
Note

The Hamming distance between two

words is the number of differences
between corresponding bits.
 Example

Let us find the Hamming distance between two pairs of

words.

1. The Hamming distance d(000, 011) is 2 because

2. The Hamming distance d(10101, 11110) is 3 because

Note

The minimum Hamming distance is the

smallest Hamming distance between
all possible pairs in a set of words.
 Example

Find the minimum Hamming distance of the coding

scheme
Solution
We first find all Hamming distances.

The dmin in this case is 2.

The structure of the encoder and decoder for a Hamming code
Note

To guarantee the detection of up to s

errors in all cases, the minimum
Hamming distance in a block
code must be dmin = s + 1.

Why?
More than s-bit error is possible to detect,
but not guaranteed.
Figure 10.8 Geometric concept for finding dmin in error detection
 Figure 10.9 Geometric concept for finding dmin in error correction

10.65
Note

To guarantee correction of up to t errors

in all cases, the minimum Hamming
distance in a block code
must be dmin = 2t + 1.
 U N I T - II
 Data Link Layer: Fundamentals of Error Detection
and Error Correction, Block coding, Hamming
Distance, CRC;
 Flow Control and Error control protocols - Stop and
Wait, Goback-N ARQ, Selective Repeat ARQ,
Sliding Window, Piggybacking,
 Random Access,Multiple access protocols - Pure
ALOHA, Slotted ALOHA, CSMA/CD, CDMA/CA
Flow Control
Stop and Wait Protocol
 The Stop-and-Wait Protocol is a fundamental flow
control mechanism used in data communication where
the sender transmits a single data packet and waits for
an acknowledgment (ACK) from the receiver before
sending the next packet.
 This ensures reliable data transmission but can lead to
inefficiency in high-latency networks.
Working Mechanism
• Sender transmits Frame 1
• Sender stops and waits
• Receiver receives Frame 1
• Receiver sends acknowledgment (ACK)
• Sender sends next frame only after ACK
Data transmission in the stop-and-wait protocol
Note
 Suppose there is a situation where the sender is sending
the data at a rate higher than the rate of the receiver to
process and receive the data. Flow Control protocol
ensures that the data does not get lost.
 The flow control protocols ensure that the sender sends
the data only at a rate that the receiver can receive and
process it.
 This is a flow control protocol that works in a noiseless
channel.
 Noiseless channel is an idealistic channel in which no data
frames are lost, corrupted, or duplicated.
 After sending the data, the sender will stop and wait until
he/she receives an acknowledgment from the receiver.
 Flow control service is provided by the data link layer.
No error control in basic Stop−and−Wait
Features
• Very simple protocol
• Only one frame in transit at any time
• Works well for short-distance communication

Problem
If the channel has high delay, the sender wastes time
waiting.
Example Scenario

• Consider a sender transmitting a 1 KB

packet over a network.
• The round-trip time (RTT) is 100 ms.
• The sender must wait for 100 ms before
sending the next packet.
• This leads to poor utilization of the
link.
Stop-and-Wait ARQ (Automatic
Repeat Request)

Stop-and-Wait ARQ is the error control version

of Stop-and-Wait.
It ensures reliable delivery by handling:
• Lost frames
• Damaged frames
• Lost acknowledgments

Error Control + Flow Control

Extra Mechanisms in ARQ
1. Sequence Numbers (0 and 1)
To avoid duplicate frames, sender labels frames:
Frame 0
Frame 1
Frame 0
Frame 1…

2. Timeout Timer
Sender starts a timer after sending a frame.
If ACK not received before timeout → retransmit frame

3. ACK and NAK

Receiver sends:
ACK → frame received correctly
NAK → frame received with error (optional)
Stop-and-Wait ARQ Working

Case 1: Normal Transmission

Sender Receiver
Frame 0 ------------> Received OK
ACK 0 <------------ Sent
Frame 1 ------------> Received OK
ACK 1 <------------ Sent
Case 2: Frame Lost

Sender sends Frame 0

(no frame reaches receiver)

Timer expires → Sender retransmits Frame 0

Receiver sends ACK 0
Case 3: ACK Lost

Sender sends Frame 0

Receiver receives correctly

Receiver sends ACK 0 (lost)

Sender timeout → retransmits Frame 0

Receiver detects duplicate using sequence number

Receiver sends ACK 0 again
Comparison

Stop-and-Wait
Feature Stop-and-Wait
ARQ
Error Control No Yes
Retransmission No Yes
Timer used No Yes
Sequence numbers No Yes
Reliable delivery No Yes
Advantages of Stop-and-Wait ARQ
• Simple
• Reliable transmission
• Handles frame loss and corruption

Disadvantages
• Low efficiency
• Poor performance in long-delay networks
Problem
A sender uses Stop-and-Wait ARQ to transmit data over a link.
Given:
Frame size = 1000 bits
Bandwidth = 1 Mbps
One-way propagation delay = 25 ms
ACK size is negligible
Find:
(i) Transmission time
(ii) Total cycle time
(iii) Efficiency of Stop-and-Wait
(iv) Throughput
Step 1: Transmission Time 𝑇𝑓
Frame size
𝑇𝑓 =
Bandwidth
1000
𝑇𝑓 =
1 × 106
𝑇𝑓 = 0.001 sec = 1 ms
So,
𝑇𝑓 = 1 𝑚𝑠
Step 2: Propagation Delay 𝑇𝑝
Given:
𝑇𝑝 = 25 𝑚𝑠
Round Trip Propagation Delay:
2𝑇𝑝 = 2 × 25 = 50 𝑚𝑠
Step 3: Total Cycle Time
Stop-and-Wait cycle:
𝑇𝑐𝑦𝑐𝑙𝑒 = 𝑇𝑓 + 2𝑇𝑝
𝑇𝑐𝑦𝑐𝑙𝑒 = 1 + 50 = 51 𝑚𝑠
So,
𝑇𝑐𝑦𝑐𝑙𝑒 = 51 𝑚𝑠
Step 4: Efficiency 𝜂
Efficiency formula:
𝑇𝑓
𝜂=
𝑇𝑓 + 2𝑇𝑝
Substitute:
1
𝜂=
51
𝜂 = 0.0196
Convert to percentage:
𝜂 = 1.96%
So,
𝜂 = 1.96%
Step 5: Throughput
Throughput = Efficiency × Bandwidth
Throughput = 0.0196 × 1 𝑀𝑏𝑝𝑠
= 0.0196 𝑀𝑏𝑝𝑠
Convert to kbps:
0.0196 × 1000 = 19.6 𝑘𝑏𝑝𝑠
So,
Throughput = 19.6 𝑘𝑏𝑝𝑠

Even though bandwidth is 1 Mbps, Stop-and-Wait gives only:

19.6 𝑘𝑏𝑝𝑠
because most time is wasted waiting for ACK.
Go-Back-N ARQ (Automatic Repeat
reQuest)

• Go-Back-N ARQ is a sliding window

protocol used for error control in data
communication.
• It allows the sender to send multiple
frames continuously without waiting for
ACK after every frame.
Why Go-Back-N?
• Stop-and-Wait wastes time:
• Send 1 frame → wait → send next
• Go-Back-N improves efficiency by: Sending N frames at once
GBN
GBN stands for:
Go−Back−N
It describes the mechanism:
• If an error occurs at frame k
• Sender goes back and retransmits frame k and all frames after it

ARQ emphasizes that it is used for:

Error detection, Retransmission,
Reliable delivery
Key Concepts:
1. Sliding Window:
 The sender maintains a window of frames that can be sent without waiting for
an ACK.
 The window size is determined by the sequence number range and the buffer

capacity.
2. Sequence Numbers:
 Each frame is assigned a unique sequence number.
 The sequence numbers are used to identify frames and ensure they are

processed in the correct order.

3. Acknowledgments (ACKs):
 The receiver sends an ACK for the last correctly received in-order frame.
 If a frame is received out of order, the receiver discards it and does not send an

ACK.
4. Timeout and Retransmission:
 If the sender does not receive an ACK within a specified timeout period, it
retransmits all frames starting from the unacknowledged frame.
How Go-Back-N ARQ Works:
1. Sender Side:
 The sender transmits frames within the window size.
 It waits for an ACK for the oldest unacknowledged frame.

 If an ACK is received, the window slides forward, allowing new frames to

be sent.
 If a timeout occurs, the sender retransmits all frames starting from the

unacknowledged frame.
2. Receiver Side:
 The receiver accepts frames in order and sends an ACK for the last
correctly received in-order frame.
 If a frame is received out of order, it is discarded, and no ACK is sent for
it.
 The receiver continues to wait for the missing frame.
 In the Go-Back-N ARQ protocol, N refers to the window size, which is the maximum number
of frames (or packets) the sender can transmit without receiving an acknowledgment (ACK)
from the receiver.
 Key Points About N:
1. Window Size:
 N determines how many frames the sender can send before it must stop and wait for an
ACK.
 It is also called the sender's window size or the sliding window size.
2. Sequence Numbers:
 The sequence numbers of the frames range from 0 to N-1 (if N is the window size).
 For example, if N = 4, the sequence numbers are 0, 1, 2, and 3. After 3, the sequence
numbers wrap around to 0.
3. Sliding Window Mechanism:
 The sender can send up to N frames without waiting for an ACK.
 Once an ACK is received for the oldest unacknowledged frame, the window "slides"
forward, allowing the sender to transmit new frames.
4. Relationship to Buffering:
 The sender must buffer all unacknowledged frames in case they need to be
retransmitted.
 The receiver, however, does not need to buffer out-of-order frames in Go-Back-N ARQ;
it simply discards them.
Go−Back−N is primarily an Error Control protocol, but it also provides
Flow Control using sliding window.
Window Size Rule
If sequence number field = m bits:
Max window size = 2𝑚 − 1
Example:
If m = 3:
𝑊 = 23 − 1 = 7
Limitations:

• If N is too large, the sender may need to

retransmit many frames unnecessarily in case
of an error.
• If N is too small, the sender may not fully
utilize the available bandwidth, leading to
lower throughput.
Advantages:
• Efficiency: Allows multiple frames to be in transit, improving
throughput.
• Simplicity: Easier to implement compared to Selective Repeat
ARQ.
Disadvantages:
• Inefficiency: If a single frame is lost, all subsequent frames in
the window are retransmitted, even if they were received
correctly.
• Bandwidth Usage: Can lead to unnecessary retransmissions,
wasting bandwidth.

Go-Back-N ARQ is suitable for environments with low error

rates and where simplicity is more critical than efficiency.
Go-Back-N in action
sender window (N=4) sender receiver
012345678 send pkt0
012345678 send pkt1
send pkt2 receive pkt0, send ack0
012345678
send pkt3 Xloss receive pkt1, send ack1
012345678
(wait)
receive pkt3, discard,
012345678 rcv ack0, send (re)send ack1
012345678 pkt4
rcv ack1, send receive pkt4, discard,
pkt5 (re)send ack1
ignore duplicate ACK receive pkt5, discard,
(re)send ack1
pkt 2 timeout
012345678 send pkt2
012345678 send pkt3
012345678 send pkt4 rcv pkt2, deliver, send ack2
012345678 send pkt5 rcv pkt3, deliver, send ack3
rcv pkt4, deliver, send ack4
rcv pkt5, deliver, send ack5
Note

 Sender side will go back to the

unacknowledged frame and retransmit
that frame, along with all the frames
shared after that frame with the receiver.
 This represents the Go-Back-N ARQ
protocol method.
Receiver discards all frames in receiver buffer
Go-Back-N(GBN): sender

 Window slides forward over the sequence number space

 N – Window size
 G B N – sliding window protocol

 base – Seq# of the oldest unacknowledged packet

 nextseqnum – smallest unused sequence number
 [0, base-1]
 [base, nextseqnum-1]
 [nextseqnum, base+N-1]
 Seq#>= base+N
Important things
 A packet’s sequence number is carried in a fixed length field
in the packet header.
 If k is the number of bits in the packet sequence number field, the
range of sequence numbers is [0 , 2k-1]
 With a finite range of Seq numbers, all arithmetic involving sequence
numbers must be done using modulo 2k arithmetic
 Can be thought of as a ring of size 2k where seq# 2k-1 is
immediately followed by 0
Go Back N Receiver

 Suppose packet n is expected but

packet n+1 arrives…What happens?
Go-Back-N: receiver
 If packet k has been received and delivered then all packets with a
seq# lower than k have also been delivered.
 Use of cumulative acknowledgements is a natural choice for
GBN
 Receiver discards out-of-order packets
 Suppose packet n is expected but packet n+1 arrives…What
happens?
 If packet n is lost ,both n and n+1 will be retransmitted
 Receiver discards packet n+1
 Adv : Simplicity of buffering – Receiver need not buffer any out-of-
order packets.
 Disadv : Retransmissions
Characteristics of Go-Back-N ARQ
 The size of the sender window in Go Back N ARQ is
equal to N.
 The size of the receiver window in Go Back N ARQ
is equal to 1.
 When the acknowledgment for one frame is not
received by the sender or the frames received by the
receiver are out of order, then the whole window
starting from the corrupted frame is retransmitted.
Advantages of Go-Back-N ARQ

 It can send multiple frames at once.

 Pipelining is present in the Go-Back-N ARQ
i.e. a frame can be sent by the sender before
receiving the acknowledgment of the
previously sent frame. This results in a
shorter waiting time for the frame.
 It handles corrupted as well as out-of-
order frames which result in minimal frame
loss.
Disadvantages of Go-Back-N ARQ
 If acknowledgment for a frame is not received, the
whole window of frames is retransmitted instead of
just the corrupted frame. This makes the Go Back N
ARQ protocol inefficient.

 Retransmission of all the frames on detecting a

corrupted frame increases channel congestion and
also increases the bandwidth requirement.

 It is more time-consuming because while

retransmitting the frames on detecting a corrupted
frame, the error-free frames are also retransmitted.
Selective repeat(SR): the approach

pipelining: multiple packets in flight(Window size is

Large)
In GBN – a single packet error will cause GBN to
retransmit a large no. of packets ,many unnecessarily.
As the Prob. Of channel error increases, pipeline can
become filled with unnecessary retransmissions.
SR avoids unnecessary retransmissions by having the
sender retransmit only those packets in error.
Unlike GBN, the sender will have already received
ACKs for some of the packets in the window.
The selective repeat protocol can perform
the following actions
• The receiver is capable of sorting the frame in a proper
sequence, as it receives the retransmitted frame whose
sequence is out of order of the receiving frame.

• The sender must be capable of searching the frame

for which the NAK has been received.

• The receiver must contain the buffer to store all the

previously received frame on hold till the retransmitted
frame is sorted and placed in a proper sequence.
Note

 SR Receiver will acknowledge a correctly

received packet whether or not it is in
order.
 Out-of-order packets are buffered until
any missing packets are received at which
point a batch of packets can be delivered
in order to the upper layer.
Selective Repeat in action
sender window (N=4) sender receiver
012345678 send pkt0
012345678 send pkt1
012345678 send pkt2 receive pkt0, send ack0
012345678 send pkt3 Xloss receive pkt1, send ack1
(wait)
receive pkt3, buffer,
012345678 rcv ack0, send send ack3
012345678 pkt4
rcv ack1, send
receive pkt4, buffer,
pkt5
record ack3 arrived send ack4
receive pkt5, buffer,
pkt 2 timeout send ack5
012345678 send pkt2
012345678 (but not 3,4,5)
012345678 rcv pkt2; deliver pkt2,
012345678 pkt3, pkt4, pkt5; send ack2

Q: what happens when ack2 arrives?

Example:

 Suppose the sender transmits frames 0, 1,

2, 3, and 4.
 Frame 1 is lost, but frames 2, 3, and 4 are
received successfully.
 What will the receiver do now?
The receiver:

 Buffers frames 2, 3, and 4.

 Sends ACKs for frames 2, 3, and 4.
 The sender retransmits frame 1 upon
timeout.
 After receiving frame 1, the receiver
delivers frames 1, 2, 3, and 4 to the
application layer in order.
The receiver will always send ACKs for any correctly received packets, even if they
arrive after a lost frame. This helps the sender avoid retransmitting unnecessary
frames and improves the protocol's efficiency.
 Selective Repeat
Feature Stop-and-Wait Go-Back-N (GBN)
(SR)
Frames sent at
1 N N
once
Sender window
1 N N
size
Receiver window
1 1 N
size
Receiver accepts
No No Yes
out-of-order?
Retransmission One frame Lost + all after it Only lost frame
Efficiency Low Medium High
Complexity Simple Moderate Complex
Buffer
Minimal Small Large
requirement
IMPORTANT FORMULAS

 To achieve 100% efficiency, the optimal

Sender window size should be 1+2a

 In Go-back-N
Note
 Max no of frames that can be sent in a window is : 1+2a
 Min no of seq numbers required is : 1+2a
 To have 1+2a seq numbers, the min no of bits required in seq no field is : [log2(1+2a)]
PROBLEM #1

 A 3000 km long trunk operates at 1.536

Mbps and is used to transmit 64 byte
frames and uses sliding window protocol.
If the propagation speed is 6 μsec / km,
how many bits should the sequence
number field be?
Solution

Given-

 Distance = 3000 km
 Bandwidth = 1.536 Mbps
 Packet size = 64 bytes
 Propagation speed = 6 μsec / km
Transmission delay (Tt)

 = Packet size / Bandwidth

 = 64 bytes / 1.536 Mbps

 = (64 x 8 bits) / (1.536 x 106 bits per sec) = 333.33 μsec

For 1 km, propagation delay = 6 μsec

 For 3000 km, propagation delay = 3000 x 6 μsec = 18000 μsec

a = Tp / Tt

 a = 18000 μsec / 333.33 μsec

 a = 54
Bits required in sequence number field

 = ⌈log2(1+2a)⌉
 = ⌈log2(1 + 2 x 54)⌉

 = ⌈log2(109)⌉ = ⌈6.76⌉ = 7 bits

 Minimum number of bits required in sequence number field

=7
 With 7 bits, number of sequence numbers possible = 128
 We use only (1+2a) = 109 sequence numbers and rest remains
unused.
PROBLEM #2

 Station A uses 32 byte packets to transmit

messages to station B using a sliding
window protocol. The round trip delay
between A and B is 80 msec and the
bottleneck bandwidth on the path
between A and B is 128 Kbps. What is the
optimal window size that A should use?
Solution

 Given-

 Packet size = 32 bytes

 Round Trip Time = 80 msec
 Bandwidth = 128 Kbps
Transmission delay (Tt)
 = Packet size / Bandwidth

 = 32 bytes / 128 Kbps

 = (32 x 8 bits) / (128 x 103 bits per sec)

 = 2 msec
Propagation delay (Tp)

 = Round Trip Time / 2

 = 80 msec / 2

 = 40 msec
 a = Tp / Tt

 a = 40 msec / 2 msec

 a = 20
 Calculating Optimal Window Size-
 Optimal window size = 1 + 2a

 = 1 + 2 x 20

 = 41
PROBLEM #3
 If transmission delay and propagation delay in a sliding
window protocol
are 1 msec and 49.5 msec respectively, then:
1 What should be the sender window size to get the
maximum efficiency?
2 What is the minimum number of bits required in the
sequence number field?
3 If only 6 bits are reserved for sequence numbers,
then what will be the efficiency?
SOLUTION
Given
 Transmission delay = 1 msec.

 Propagation delay = 49.5 msec.

 Calculating sender window size to get the maximum efficiency:

 To get the maximum efficiency, sender window size

 = 1 + 2a
 = 1 + 2 x (Tp / Tt)
 = 1 + 2 x (49.5 msec / 1 msec)
 = 1 + 2 x 49.5
 = 100
a) For maximum efficiency, sender window size = 100.
b)Calculating the minimum number of bits required in the sequence
number field:
 Minimum number of bits required in the sequence number field

 = ⌈log2(1+2a) ⌉
 = ⌈log2(100) ⌉
 = ⌈6.8⌉
 =7
 Minimum number of bits required in the sequence number field = 7.

c)Calculating the efficiency according to sequence numbers:

 If only 6 bits are reserved in the sequence number field, then

Maximum sequence numbers possible = 26 = 64

 Efficiency = Sender window size in the protocol / Optimal sender
window size
 = 64 / 100 = 0.64 = 64%
PROBLEM #4

 A 20 Kbps satellite link has a propagation

delay of 400 ms, the transmitter employs
the “Go back N” ARQ” scheme with N set
to [Link] that each frame is 100
bytes long, what is the maximum data
rate possible?
SOLUTION
Given:
 Bandwidth = 20 Kbps
 Propagation delay (Tp) = 400 msec.
 Frame size = 100 bytes
 Go back N is used where N = 10.
Transmission delay (Tt) = Frame size / Bandwidth
 = 100 bytes / 20 Kbps
 = (100 x 8 bits) / (20 x 10^3 bits per sec)
 = 0.04 sec
 = 40 msec.
Calculating Value of ‘a’:
 a = Tp / Tt
 a = 400 msec. / 40 msec.
 a = 10
Calculating Efficiency:
 Efficiency (η) = N / (1+2a)

 = 10 / (1 + 2 x 10)
 = 10 / 21
 = 0.476
 = 47.6 %.
Calculating Maximum Data Rate Possible:
 Maximum data rate possible or Throughput = Efficiency x

Bandwidth
 = 0.476 x 20 Kbps
 = 9.52 Kbps ≅ 10 Kbps
PROBLEM #5

 A 1 Mbps satellite link connects two

ground stations. The altitude of the
satellite is 36504 km and speed of the
signal is 3 x 10^8 m/sec. What should be
the packet size for a channel utilization of
25% for a satellite link using go back 127
sliding window protocol?
SOLUTION
Given
 Bandwidth = 1 Mbps
 Distance = 2 x 36504 km = 73008 km
 Propagation speed = 3 x 10^8 m/sec
 Efficiency = 25% = 1/4
 Go back N is used where N = 127
 Let the packet size be L bits.
Calculating Transmission Delay (Tt) = Packet size / Bandwidth
 = L bits / 1 Mbps
 = L μsec.
Calculating Propagation Delay (Tp) = Distance / Speed
 = (73008 x 10^3 m) / (3 x 10^8 m/sec)
 = 24336 x 10^-5 sec = 243360 μsec.
Calculating Value of ‘a’:
 a = Tp / Tt
 a = 243360 μsec / L μsec
 a = 243360 / L
Calculating Packet Size:
 Efficiency (η) = N / (1+2a)
 Substituting the values, we get
 1/4 = 127 / (1 + 2 x 243360 / L)
 1/4 = 127 x L / (L + 486720)
 L + 486720 = 508 x L

Get all the terms involving L on one side by subtracting L from both sides
 L – L +486720 = 508 * L - L

508×L−L=(508−1)×L=507×L

 507 x L = 486720 ……So, L = 960 bits.

 From here, packet size = 960 bits or 120 bytes.
Go-Back-N & SR Animation

 [Link]
[Link]/teaching/rn/animations/gbn_sr/
Piggybacking

Piggybacking is a technique used in full-duplex data

communication where an acknowledgment (ACK) for
received data is not sent immediately as a separate frame.
Instead, it is attached (piggybacked) to the next outgoing
data frame.
It is commonly used in sliding window protocols like:
• Stop-and-Wait
• Go-Back-N (GBN)
• Selective Repeat (SR)
Why Piggybacking?

In full-duplex communication, both sender and receiver can send data

simultaneously.
Instead of sending:
• Frame 1 →
ACK 1 ←
Frame 2 →
ACK 2 ←
We combine:
• Frame 1 →
Frame 2 + ACK 1 ←
Frame 3 + ACK 2 →
This reduces overhead.
How Piggybacking Works

Suppose:
A sends data to B
B also has data to send to A
When B receives a frame from A:
B waits for a short time
If B has data to send → it attaches ACK to that data frame.
If B has no data to send within timeout → it sends a separate ACK.
Advantages

✔ Reduces bandwidth consumption

✔ Improves channel efficiency
✔ Reduces number of frames
✔ Useful in sliding window protocols
Disadvantages

✖ Requires waiting time (ACK delay)

✖ Slight complexity in implementation
✖ Not useful in simplex communication
Note

• Works only in full-duplex communication

• Used in data link layer
• ACK is delayed but only for a short time
• Timeout ensures reliability
 UNIT - II
 Data Link Layer: Fundamentals of Error
Detection and Error Correction, Block coding,
Hamming Distance, CRC;
 Flow Control and Error control protocols - Stop
and Wait, Goback-N ARQ, Selective Repeat
ARQ, Sliding Window, Piggybacking,
 Random Access,Multiple access protocols -
Pure ALOHA, Slotted ALOHA, CSMA/CD,
CDMA/CA
Random Access Protocols
• Random Access Protocols are MAC (Medium
Access Control) protocols where multiple nodes
share a common communication channel and
transmit whenever they have data, accepting
the possibility of collisions.
• These protocols are covered under the MAC
sublayer of the Data Link Layer in Computer
Networks.
ALOHA
 The ALOHA protocol was one of the earliest networking
protocols designed to allow multiple devices to share a
common communication channel.
 Originally developed at the University of Hawaii in the
1970s.
 First used for satellite and radio communications in
Hawaii.
 It introduced the concept of random access, where
devices could transmit data packets whenever they
wanted, and retransmit in case of collisions.
 This laid the foundation for many modern wireless
communication systems like Ethernet and Wi-Fi.
Concept

• Stations transmit whenever they have data

• No time synchronization
• Collisions can happen anytime
Types of ALOHA:
1. Pure ALOHA:
 In Pure ALOHA, devices transmit data whenever they have data to
send without checking if the channel is busy. This leads to collisions
when multiple devices send data simultaneously.
 After sending, the sender waits for an acknowledgment. If none is received
(due to a collision), the sender waits for a random amount of time before
retransmitting.
2. Slotted ALOHA:
 Slotted ALOHA introduces time slots, where devices can only begin
transmitting at the start of a slot. This reduces the chance of collisions
since transmissions are more organized.
 If a collision occurs, retransmission still follows a random delay, but
because of time-slotting, the efficiency is improved compared to Pure
ALOHA.
UNSLOTTED ALOHA/PURE ALOHA

 Unslotted, fully decentralized

 In pure ALOHA, when a frame first arrives the node
immediately transmits the frame in its entirety into the
broadcast channel.
 If a transmitted frame experiences a collision with one
or more other transmissions, the node will then
immediately retransmit the frame with a prob p.
 Otherwise the node waits for a frame transmission
time.
 After this wait, it then transmits the frame with prob p
or waits for another frame time with prob 1-p.
Pure Aloha

Vulnerable Period
If a frame takes time T to transmit,
Vulnerable Period = 𝟐𝑻
Because collision can occur before or after the transmission starts.
Throughput Formula
𝑺 = 𝑮𝒆−𝟐𝑮
G=Average number of
Where: transmission attempts
𝐺= Offered load per time slot
𝑆= Throughput It includes:
Maximum Throughput New transmissions
Occurs at 𝐺 = 0.5 Retransmissions (after
𝟏 collisions)
𝑺𝒎𝒂𝒙 = ≈ 𝟎. 𝟏𝟖𝟒
𝟐𝒆
Maximum efficiency ≈ 18.4%
 Slotted ALOHA

t0 t0+1

Assumptions: Operation:
 all frames consist of exactly L bits  when node obtains fresh
 time divided into equal size slots frame,transmits in next slot
(time to transmit 1 frame)
• if no collision: node can send
 nodes start to transmit frame only
new frame in next slot
at the beginning of a slot
 nodes are synchronized
• if collision: node retransmits
frame in each subsequent
 if 2 or more frames collide in a slot,
all nodes detect collision before the slot with probability p until
slot ends. success
Slotted ALOHA

node 1 1 1 1 1

node 2 2 2 2
C: collision
S: success
node 3 3 3 3
E: empty
C E C S E C E S S

Pros: Cons:
 single active node can  collisions, wasting slots
continuously transmit at full rate  idle slots
of channel  nodes may be able to detect collision in
 highly decentralized: only slots in less than time to transmit packet
nodes need to be in sync
 clock synchronization
 simple
Slotted ALOHA
Concept
• Improved version of Pure ALOHA.
• Time divided into equal slots
• Transmission allowed only at slot boundaries
• Requires synchronization
Vulnerable Period
Vulnerable Period = 𝑻
(half of Pure ALOHA)
Throughput Formula
𝑺 = 𝑮𝒆−𝑮
Maximum Throughput
Occurs at 𝐺 = 1
𝟏
𝑺𝒎𝒂𝒙 = ≈ 𝟎. 𝟑𝟔𝟖
𝒆
Maximum efficiency ≈ 36.8%
Slotted ALOHA: efficiency
long-run fraction of successful slots
efficiency:
(many nodes, all with many frames to send)
 suppose: N nodes with many frames to send, each

transmits in slot with probability p

 Prob that a given node transmits is p

 Prob that remaining nodes do not transmit (1-p)N-1

 prob that given node has success in a slot = p(1-p)N-1
 prob that any node has a success = Np(1-p)N-1
 max efficiency = 1/e = .37
 at best: channel used for useful transmissions 37% of time!
Why Slotted ALOHA is Better

• Reduces vulnerable time by half

• Doubles maximum throughput
• More efficient use of bandwidth
Note

 Allows a node to transmit at the full rate R

bps when that node is the only active node.
 Highly decentralized – each node detects
collisions but decides independently when to
retransmit
 Extremely simple
 A slot in which exactly one node transmits is said
to be successful slot.
Note

•Pure ALOHA efficiency = 1 / 2e

•Slotted ALOHA efficiency = 1 / e
•Slotted ALOHA is exactly 2 times more efficient
Observation

 In both slotted and pure ALOHA, a node’s

decision to transmit is made independent of
the activity of the other nodes attached to the
broadcast channel.
 A node neither pays attention to whether
another node happens to be transmitting
when it begins to transmit nor stops
transmitting if another node begins to
interfere with its transmission.
Comparison Table

Feature Pure ALOHA Slotted ALOHA

Time Slots No Yes
Synchronization Not required Required
Vulnerable Period 2T T
Max Efficiency 18.4% 36.8%
Collision Probability High Lower
SOLVE??

 There are 5 stations in slotted LAN. Each

station attempts to transmit with a
probability P=0.2 in each time slot. What
is the probability that ONLY one station
transmits in a given time slot?
Solution

Given
Number of stations = N = 5
Transmission probability per station = P = 0.2
We need:
Probability that exactly ONE station transmits in a slot

Step 1: Understand the Event

For “only one station transmits”:
One station transmits → probability = P
The remaining 4 stations do NOT transmit → probability = (1 − P)^4
But any one of the 5 stations can be that transmitter.
So we multiply by 5 combinations.
Step 2: Formula
For exactly one transmission in N stations:
𝑷 exactly one = 𝑵 ⋅ 𝑷 ⋅ ቀ𝟏 − 𝑷)𝑵−𝟏

Step 3: Substitute Values

= 5 ⋅ 0.2 ⋅ ቀ1 − 0.2)4
= 5 ⋅ 0.2 ⋅ ቀ0.8)4
= 5 ⋅ 0.2 ⋅ 0.4096
= 1 ⋅ 0.4096
= 𝟎. 𝟒𝟎𝟗𝟔
Applications of ALOHA:

• Ethernet: The CSMA/CD (Carrier Sense Multiple

Access/Collision Detection) protocol used in
Ethernet networks builds on ALOHA by adding
mechanisms to detect and avoid collisions.
• Wi-Fi: The CSMA/CA (Carrier Sense Multiple
Access/Collision Avoidance) used in Wi-Fi networks
also inherits concepts from ALOHA, particularly in
how devices handle contention for a shared medium.
CSMA (carrier sense multiple
access)
CSMA (carrier sense multiple access)

 Two important rules for polite human

conversation
1. Listen before speaking – Carrier Sensing( a

node listens to the channel before

transmitting)
2. If someone else begins talking at the same

time, stop talking – Collision detection(If a

node detects that another node is transmitting
an interfering frame, it stops transmitting and
wait a random amount of time before repeating
the sense-and- transmit-when-idle-cycle.
Ethernet CSMA/CD algorithm
[Link] receives datagram from network layer, creates frame
[Link] senses channel:
if idle: start frame transmission.
if busy: wait until channel idle, then transmit
[Link] entire frame transmitted without collision - done!
[Link] another transmission detected while sending: abort, send jam
signal
[Link] aborting, enter binary (exponential) backoff:
• After nth collision, a node chooses K at random from {0,1,2, …,
2n-1}.
• For Ethernet, the actual amount of time a node waits is
K*512 bit times( K times the amount of time needed to transmit
512 bits into Ethernet), returns to Step 2
• Max value that n can take is capped at 10.
• The more the collisions, the longer the backoff interval
Binary (Exponential) Backoff
 Binary (Exponential) Backoff is an algorithm used
primarily in network communication protocols like
Ethernet (CSMA/CD) and Wi-Fi (CSMA/CA) to handle
collisions when multiple devices try to send data
simultaneously.
 The backoff mechanism plays a critical role in regulating
access to a shared communication medium, ensuring
that devices do not continuously collide and that the
network remains efficient.
How it Works
 It is used to determine the wait time before retransmitting a
packet after a collision occurs.
1. Initial Transmission: When a device wants to transmit data,
it sends the packet.
2. Collision Detection: If two devices transmit simultaneously,
a collision occurs, and the devices detect the collision.
3. Backoff Procedure:
 Each device involved in the collision waits for a random period
before attempting to retransmit.
 The wait time is calculated based on the number of collisions
encountered.
 The backoff time increases exponentially with each subsequent
collision.
2. Exponential Growth: The backoff time is chosen from a
random range that doubles with each collision. Specifically, if
the number of collisions is k, the backoff time is chosen from
the interval [0, 2^k−1] slots.
Example Scenario
Step 1: Initial Attempt
Both Device A and Device B want to send data at the same time.
They both transmit simultaneously.
Step 2: Collision Detected
A collision occurs because both devices are trying to transmit at the same
time.
Step 3: First Backoff
Each device now needs to wait a random amount of time before trying to send
again.
Since this is the first collision (k=1), each device chooses a random wait time
from the range
[0, 2^1 - 1] = [0, 1]
Device A randomly chooses 0 (waits 0 time slots).
Device B randomly chooses 1 (waits 1 time slot).
Step 4: Second Attempt
Device A sends its data immediately (after waiting 0 slots).
Device B waits for 1 time slot, then attempts to send.
If Device A successfully sends its packet without any further collisions, Device B will not
encounter a collision. However, if they collide again, they will follow the next steps.
Contd..
Step 5: Second Collision (if it occurs)
Suppose they collide again. Now both devices need to back off
again.
Since this is the second collision (k=2), they choose a random
wait time from [0, 2^2 - 1] = [0, 3].
Device A randomly chooses 2 (waits 2 time slots).
Device B randomly chooses 1 (waits 1 time slot).
Step 6: Third Attempt
Device A waits for 2 slots and then tries to send.
Device B waits for 1 slot and then tries to send.
Depending on the timing, they may or may not collide again.

This process continues, with the range of backoff

times increasing exponentially after each collision,
helping to minimize the likelihood of repeated
collisions.
SUMMARY:

1. Initial Attempt: When a device wants to send data, it listens to the communication medium to check
if it is idle.
1. In CSMA/CD (Ethernet), the device will detect a collision during transmission.

2. In CSMA/CA (Wi-Fi), the device uses a contention mechanism to avoid collisions.

2. Collision Occurs: If two or more devices transmit simultaneously, a collision occurs. The devices stop
transmitting and enter a backoff period to avoid another immediate collision.
3. Random Backoff Time: Each device chooses a random backoff time within a range (based on a
contention window), before retrying to send the data.
4. Exponential Increase: If another collision occurs, the backoff time increases exponentially.
This is where the "binary exponential backoff" comes in.
1. For the n-th retransmission attempt, the backoff time is chosen randomly from the range [0,

2^n - 1].
2. For example:

1. On the first collision (n = 1), the backoff time is randomly chosen from [0, 1].

2. On the second collision (n = 2), the backoff time is randomly chosen from [0, 3].

3. On the third collision (n = 3), the backoff time is randomly chosen from [0, 7].

3. The process repeats with the backoff range doubling each time until it reaches a predefined

maximum (usually to avoid excessively long delays).

5. Collision Avoidance: By using exponentially larger backoff times, the algorithm reduces the
probability of repeated collisions, giving each device a better chance of accessing the medium.
6. Success: Once the device successfully sends its data, the backoff counter resets, and the process
starts anew if more data needs to be transmitted.
Problem #1

 In a CSMA/CD network running at 1 Gbps

over 2 km cable with no repeaters, the
signal speed in the cable is 400000
km/sec. What is minimum frame size?
Solution

Step 1: Calculate the propagation delay

Propagation delay (𝑇𝑝) =Cable Length/Propagation Speed
=2000 m / 4×108 m/s=5 𝜇𝑠
This is the one-way propagation delay.
For CSMA/CD, we need the round-trip time (RTT)
RTT=2×𝑇𝑝=2×5 𝜇𝑠=10 𝜇𝑠
Step 2: Calculate the minimum frame size
To detect a collision, the transmission time of the frame must be greater
than or equal to the round-trip time.
The transmission time 𝑇𝑡=Frame Size (in bits) / Data Rate (bps)
To ensure collision detection:𝑇𝑡 ≥ 𝑅𝑇𝑇
Frame Size/109 ≥ 10×10−6
Frame Size ≥ 109×10×10−6=10,000 bits
Step 3: Convert bits to bytes
10,000 bits=10,000/8=1250 bytes
PROBLEM #2

In a 10 Mbps Ethernet LAN using Ethernet, the

maximum cable length is 2500 [Link] speed = 2
× 10⁸ m/[Link] the minimum frame size required for
proper CSMA/CD operation.
SOLUTION
Step 1: Calculate Propagation Delay
Distance
Propagation Delay =
Propagation Speed
2500
=
2 × 108
= 12.5𝜇𝑠

Step 2: Round Trip Time (RTT)

CSMA/CD requires:
Transmission Time ≥ 𝟐 × Propagation Delay
𝑅𝑇𝑇 = 2 × 12.5 = 25𝜇𝑠

Step 3: Minimum Frame Size

Frame Size = Data Rate × RTT
= 10 × 106 × 25 × 10−6 Minimum frame size = 250
= 250 bits bits (≈ 32 bytes)
= 31.25 Bytes (Actual Ethernet uses 64
bytes minimum for safety
margin.)
PROBLEM #3 : Collision Detection
Time Problem

A 100 Mbps Ethernet network has a maximum distance of

200 m. Propagation speed = 2 × 10⁸ m/s
Find the time required to detect collision.
SOLUTION
Step 1: One-way propagation delay
200
=
2 × 108
= 1𝜇𝑠

Step 2: Collision Detection Time

= 𝟐 × 𝟏 = 𝟐𝝁𝒔

Final Answer:
Collision detected within 2 microseconds
Efficiency of CSMA/CD

Formula
𝟏
Efficiency =
𝟏 + 𝟓𝒂
Where,
Propagation Delay
𝑎=
Transmission Time

1. Propagation to far end

2. Collision return propagation
3. Jam signal
4. Idle slot time
5. Additional contention time
Problem

Propagation delay = 5 µs
Frame transmission time = 50 µs
Find efficiency.
SOLUTION
Step 1: Calculate a
5
𝑎= = 0.1
50

Step 2: Efficiency
1
=
1 + 5 0.1
1
=
1.5
= 0.67

Final Answer:
Efficiency = 67%
Binary Exponential Backoff
Problem

Problem
In CSMA/CD, after 3 collisions, what is the range of
random numbers chosen?
SOLUTION

Rule:
After n collisions, random number is chosen from:
𝟎 to 𝟐𝒏 − 𝟏
For n = 3:
0 to 23 − 1
0 to 7

Final Answer:
Random number range = 0 to 7
Example in CSMA/CD (Ethernet):

• If a collision occurs, each device waits for

a random period, increasing the wait time
exponentially with each failed attempt,
until a maximum number of retries is
reached.
• After the maximum retries, the
transmission is aborted.
CSMA/CA

 CSMA/CA (Carrier Sense Multiple Access

with Collision Avoidance) is a network
protocol that is primarily used in wireless
communication (such as Wi-Fi).
 It is designed to avoid collisions before
they occur, unlike CSMA/CD (used in
Ethernet), which deals with collisions after
they happen.
 Key Concepts of CSMA/CA:

1. Carrier Sense: Before transmitting, a device listens to

the communication channel to check if it’s free (no
ongoing transmission). This ensures that the device
does not interrupt other ongoing transmissions.
2. Collision Avoidance: If the channel is found to be
busy, the device does not immediately retry to transmit.
Instead, it waits for a random backoff time to avoid
collisions that might occur if multiple devices attempt to
transmit simultaneously when the channel becomes
free.
3. Acknowledgment: After a successful transmission,
the receiving device sends an acknowledgment (ACK) to
the sender. If the sender does not receive the ACK
within a certain period, it assumes a collision or error
occurred, and it will try retransmitting the data.
CSMA/CA algorithm:
Step 1: Carrier Sensing (Channel Listening)
The device first senses the communication channel to check if it is idle or busy:
1. If idle, the device proceeds to transmit data.

2. If busy, the device waits for the channel to become idle before proceeding.

Step 2: Wait for Interframe Space (IFS)

After the channel is detected to be idle, the device does not immediately transmit. It waits for a specified
period called the Interframe Space (IFS). This waiting period is to ensure the channel remains idle
and to give priority to high-priority frames (if any).
Step 3: Random Backoff Time
After the IFS, the device waits for a random amount of time known as the Backoff Time. This random
waiting helps avoid multiple devices transmitting simultaneously when the channel becomes free
(collision avoidance).
1. The backoff time is calculated based on the Contention Window (CW). The CW is a range of

time slots, and the device randomly selects a slot within this range. The value of the CW increases
exponentially with each failed transmission attempt (this is called Binary Exponential Backoff).
Step 4: Transmit Data
After the backoff time has passed and if the channel is still idle, the device proceeds to transmit its data.
Step 5: Acknowledgment
After the data is successfully transmitted, the receiver sends an ACK back to the sender to confirm
successful reception. If the sender does not receive an ACK within a certain time frame, it assumes that
the transmission failed (possibly due to a hidden node problem or other interference) and repeats the
process.
SIFS and DIFS in CSMA/CA
SIFS (Short Inter Frame Space)

• SIFS is the shortest waiting time between frames.

• It is used for high-priority responses.
Used Before:
• ACK
• CTS
• Data (after RTS)
Why Short?
To give priority to the ongoing transmission exchange.
Example sequence:
DATA → SIFS → ACK
Since SIFS is very small, no other station can capture the
channel before ACK is sent.
DIFS (Distributed Inter Frame
Space)

DIFS is the waiting time before a new transmission attempt.

Used Before:
Any station starts sending DATA (after channel becomes idle)
Sequence:
Channel Idle → DIFS → Backoff → DATA

Formula
𝐃𝐈𝐅𝐒 = 𝐒𝐈𝐅𝐒 + 𝟐 × 𝐒𝐥𝐨𝐭 𝐓𝐢𝐦𝐞
So DIFS is always greater than SIFS.
Why SIFS < DIFS ?

This creates priority hierarchy.

If:
DATA → SIFS → ACK
and another station wants to transmit:
Idle → DIFS → Backoff → DATA

Since:
𝑺𝑰𝑭𝑺 < 𝑫𝑰𝑭𝑺

ACK is sent before any new station can start transmitting.

This prevents collisions of control frames.
EXAMPLE
Given:
SIFS = 10 μs
Slot time = 20 μs
Find DIFS.
𝑫𝑰𝑭𝑺 = 𝟏𝟎 + 𝟐 𝟐𝟎
= 𝟏𝟎 + 𝟒𝟎
= 𝟓𝟎𝝁𝒔
Backoff Time Calculation

Problem
In an 802.11 network:
Slot time = 20 μs
Contention Window (CWmin) = 15
A station randomly selects backoff number = 6
Find the backoff time.
Solution
Backoff Time = Random Number × Slot Time
= 6 × 20𝜇𝑠
= 120𝜇𝑠

Final Answer
Backoff Time = 120 microseconds
Contention Window After Collisions
(Binary Exponential Backoff)
Problem
Initial CWmin = 15
Find the Contention Window after:
1st collision
2nd collision
3rd collision
SOLUTION
Rule
𝑪𝑾 = 𝟐𝒏 𝑪𝑾𝒎𝒊𝒏 + 𝟏 − 𝟏
where n = number of collisions

After 1st collision (n=1)

𝐶𝑊 = 21 15 + 1 − 1
= 2 16 − 1 = 31

After 2nd collision (n=2)

𝐶𝑊 = 22 16 − 1
= 4 16 − 1 = 63

After 3rd collision (n=3)

𝐶𝑊 = 23 16 − 1
= 8 16 − 1 = 127
Transmission Delay Including
Interframe Spaces

Problem
In 802.11:
DIFS = 50 μs
SIFS = 10 μs
Backoff time = 120 μs
Data frame transmission time = 1000 μs
ACK transmission time = 200 μs
Find total time required for successful transmission.
SOLUTION
Sequence in CSMA/CA
DIFS → Backoff → DATA → SIFS → ACK

Total Time
= 𝐷𝐼𝐹𝑆 + 𝐵𝑎𝑐𝑘𝑜𝑓𝑓 + 𝐷𝐴𝑇𝐴 + 𝑆𝐼𝐹𝑆 + 𝐴𝐶𝐾
= 50 + 120 + 1000 + 10 + 200
= 1380𝜇𝑠

Final Answer
Total transmission time = 1380 μs
Throughput Calculation

Problem
Frame size = 1500 Bytes
Data rate = 54 Mbps
Total transmission time (including overhead) = 2000 μs
Find throughput.
SOLUTION
Step 1: Convert frame size to bits
1500 × 8 = 12000 bits

Step 2: Convert time to seconds

2000𝜇𝑠 = 0.002 sec

Step 3: Throughput
12000
=
0.002
= 6,000,000 bps
= 6 Mbps

Final Answer
Throughput = 6 Mbps 𝟔
Efficiency= = 𝟎. 𝟏𝟏𝟏
𝟓𝟒
EFFICIENCY
CSMA/CA efficiency approximately
1
𝜂=
1 + 2𝑎

1. Data propagation
2. ACK propagation

CSMA/CA avoids collisions using backoff and control

[Link] wasted time is mainly round-trip propagation, not
collision [Link] smaller coefficient (2).
Summary of MAC protocols

 Random Access (dynamic),

• ALOHA, S-ALOHA, CSMA, CSMA/CD
• carrier sensing: easy in some technologies (wire), hard
in others (wireless)
• CSMA/CD used in Ethernet
• CSMA/CA used in 802.11
QUIZ
#1
A block code has parameters (n = 15, k = 11). What is the minimum number
of parity bits required and what is the maximum number of error bits that can
be corrected?
A) r=4, correct 1-bit
B) r=5, correct 2-bit
C) r=4, correct 2-bit
D) r=5, correct 1-bit
#2
A code has minimum Hamming distance dmin = 5. It can:
A) Detect 4 errors, correct 2
B) Detect 5 errors, correct 2
C) Detect 4 errors, correct 3
D) Detect 3 errors, correct 2
#3
In a (7,4) Hamming code, received word is 1011010. Syndrome = 011. Error is
at:
A) Bit 1
B) Bit 3
C) Bit 4
D) Bit 6
#4
For a CRC using generator polynomial x³ + x + 1, the binary divisor is:
A) 1101
B) 1011
C) 1110
D) 1001
#5
If a CRC generator has degree r = 5, how many redundant bits are appended?
A) 4
B) 5
C) 6
D) Depends on data size
#6
If a codeword has even parity and 3 bits flip during transmission, the receiver:
A) Detects error
B) Cannot detect error
C) Corrects error
D) Detects and corrects
#7
In Stop-and-Wait ARQ, if transmission time = 2 ms and propagation time = 8
ms, efficiency is:
A) 11%
B) 20%
C) 25%
D) 33%
#8
For Go-Back-N with window size 7 and 3-bit sequence numbers:
A) Valid
B) Invalid (window too large)
C) Valid only for error-free case
D) Invalid due to wraparound
#9
If 5th frame is lost in Go-Back-N, sender retransmits:
A) Only 5
B) 5 and subsequent frames
C) Only last frame
D) Entire window
#10
Selective Repeat requires more buffer at receiver because:
A) Frames may arrive out of order
B) Larger window
C) More retransmissions
D) Piggybacking
#11
Piggybacking improves efficiency by:
A) Increasing window size
B) Combining ACK with data frame
C) Reducing propagation delay
D) Eliminating errors
#12
If sequence numbers are 4 bits in Go-Back-N, maximum sender window is:
A) 15
B) 16
C) 8
D) 7
#13
Maximum efficiency of Pure ALOHA is:
A) 18.4%
B) 36.8%
C) 50%
D) 63.2%
#14
Maximum efficiency of Slotted ALOHA is:
A) 18.4%
B) 36.8%
C) 50%
D) 63.2%
#15
In Slotted ALOHA, throughput S = Ge⁻ᴳ. Maximum throughput occurs at:
A) G=0.5
B) G=1
C) G=2
D) G=0
#16
In CSMA/CD, efficiency is approximately:
A) 1/(1+5a)
B) 1/(1+2a)
C) 1/(1+a)
D) 1/(1+3a)
#17
In CSMA/CA, efficiency is approximately:
A) 1/(1+5a)
B) 1/(1+2a)
C) 1/(1+a)
D) 1/(1+4a)
#18
In a network of 6 stations, each transmits with probability 0.2. Probability
exactly one transmits is:
A) 0.393
B) 0.262
C) 0.312
D) 0.450
#19
In Go-Back-N, if window size = 4 and frame 2 is lost, how many frames are
retransmitted if 4 frames were sent?
A) 1
B) 2
C) 3
D) 4
#20
Binary exponential backoff in CSMA/CD reduces:
A) Propagation delay
B) Collision probability under heavy load
C) Frame size
D) Channel bandwidth