9/11/2025
Computer Network
DATA LINK LAYER: FRAMING, FLOW
CONTROL AND ERROR CONTROL
Topics Framing, Flow control and Error control
Why Framing?
2
Large block of data may be broken up into small frames at the source
because:
Limitedbuffer size at the receiver
A larger block of data has higher probability of error
With smaller frames, errors are detected sooner, and only a smaller amount of
data needs to be retransmitted
On a shared medium, such as Ethernet and Wireless LAN, small frame size
can prevent one station from occupying medium for long periods
A. Biswas
1
9/11/2025
Frame Structure
3
•Flag: delimit frame at both ends
•Address: identify the frame receiver
•Control: specify different frame types
•FCS: frame check sequence (error detecting code)
A. Biswas
Issues in Framing
4
Need to indicate the start and end of a block of data
Use preamble (e.g., flag byte) and postamble
If the receiver ever loses synchronization, it can just search for
the flag byte.
Frame: preamble + control info + data + postamble
Problem: it is possible that the flag byte’s bit pattern occur in
the data
A. Biswas
2
9/11/2025
Framing Methods
5
Two popular solutions:
Byte stuffing
The sender inserts a special byte (e.g., ESC) just before each “accidental” flag byte in the
data (like in C language, “ macros are replaced with values/definitions”).
The receiver’s link layer removes this special byte before the data are given to the network
layer.
Bit stuffing:
Each frame starts with a flag byte “01111110”.
Whenever the sender encounters five consecutive 1s in the data, it automatically stuffs a 0
bit into the outgoing bit stream.
When the receiver sees five consecutive incoming 1 bits, followed by a 0 bit, it
automatically deletes the 0 bit
A. Biswas
Byte Stuffing
6
A. Biswas
3
9/11/2025
Byte Stuffing Examples
7
Four examples of byte sequences before and after byte stuffing
A. Biswas
Bit Stuffing
8
The original data (a).
The data as they appear on the line (b).
The data as they are stored in the receiver’s memory after destuffing (c).
A. Biswas
4
9/11/2025
Flow Control
9
Ensuring the sending entity does not overwhelm the receiving entity
Preventing buffer overflow
Transmission time
Time taken to emit all bits into medium at the sender’s side
Determined by the data rate
Propagation time
Time for a bit to traverse the link and reach the destination
Determined by the transmission distance
We first assume error-free transmission i.e. noiseless channel.
A. Biswas
Model of Frame Transmission
10
A. Biswas
5
9/11/2025
Stop-and-Wait Flow Control
11
Source transmits a frame.
Destination receives the frame, and replies with a small frame called
acknowledgement (ACK).
Source waits for the ACK before sending the next frame.
This is the core of the protocol !
Destination can stop the flow by not sending ACK (e.g., if the
destination is busy …).
A. Biswas
Performance of Stop-and-Wait
12
Assumptions
Transmission time of the data frame is 1
Transmission time of the ACK frame is 0
Propagation time is a
Error-free transmission
The channel utilization ratio is 1/(1+2a)
In a time period of 1+2a, the transmitter is only busy with 1 unit of time.
It is not efficient for long haul transmission and high speed transmission.
Another type of protocol called “sliding-window” is designed for this situation.
A. Biswas
6
9/11/2025
Stop-and-Wait Link Utilization
13
A. Biswas
Sliding-Window Flow Control
14
Idea: allow multiple frames to transmit
Receiver has a buffer of W frames
Transmitter can send up to W frames without receiving ACK
Each frame needs to be numbered: sequence number is included in the
frame header
Sequence number is bounded by the length of “sequence number field” in
the header, e.g., k bits
Frames are numbered modulo 2k
ACK includes the sequence number of the next expected frame by the
receiver
A. Biswas
7
9/11/2025
Sliding-Window Diagram
15
Need to buffer them in
case of retransmission
A. Biswas
Example Sliding-Window
16
RR3 means the receiver has received all
frames up to frame 2 and is ready to receive
frame 3.
Have been delivered to More spaces for future
upper layer frames
A. Biswas
8
9/11/2025
Performance of Sliding-Window
17
Assumptions
Window size is W
Frame transmission time is 1
ACK transmission time is 0
Propagation time is a
Error-free transmission
The channel utilization ratio is
1 W 2a 1
U W
2 a 1 W 2a 1
A. Biswas
Performance of Sliding-Window
18
A. Biswas
9
9/11/2025
Performance of Sliding-Window
19
A. Biswas
Error Control in Noisy Channel
20
Error control: detection and correction of errors
We consider two types of errors:
Lost frames
The receiver cannot recognize that a frame received.
Damaged frames
The receiver can recognize the frame, but some bits are in error.
Two approaches for error control
ARQ: automatic repeat request, based on some or all of the following ingredients:
Error detection
Positive acknowledgment
Retransmission after timeout
Negative acknowledgement and retransmission
FEC: forward error correction
A. Biswas
10
9/11/2025
Automatic Repeat Request (ARQ)
21
The role of ARQ is to turn an unreliable data link into a reliable one.
Three versions of ARQ:
Stop-and-wait
Go-back-N
Selective-reject (or, selective repeat)
A. Biswas
Stop-and-Wait ARQ
22
Based on stop-and-wait flow control
The source station is equipped with a timer.
Source transmits a single frame, and waits for an ACK
If the frame is lost…
The timer eventually fires, and the source retransmits the frame.
If receiver receives a damaged frame, discard it
The timer eventually fires, and the source retransmits the frame.
If everything goes right, but the ACK is damaged or lost, the source will not recognize it
The timer eventually fires, the source will retransmit the frame
Receiver gets two copies of the same frame!
Solution: use sequence numbers, 1 bit is enough, i.e., frame0 and frame1, ACK0 and
ACK1
A. Biswas
11
9/11/2025
Stop-and-Wait Diagram
23
Simple, but inefficient for long distance and high
speed applications.
We can use sliding-window technique to improve the
efficiency.
Go-Back-N ARQ
24
Based on sliding-window flow control
Use window size to control the number of unacknowledged frames outstanding
If no error, the destination will send ACK as usual with next frame expected (positive
ACK, RR: receive ready)
If error, the destination will reply with rejection (negative ACK, REJ: reject)
Receiver discards that frame and all future frames, until the erroneous frame is received
correctly.
Source must go back and retransmit that frame and all succeeding frames that were
transmitted in the interim.
This makes the receiver simple, but decreases the efficiency
A. Biswas
12
9/11/2025
Go-Back-N: Damaged Frame
25
Suppose A is sending frames to B. After each transmission, A sets a
timer for the frame.
In Go-Back-N ARQ, if the receiver detects error in frame i
Receiver discards the frame, and sends REJ-i
Source gets REJ-i
Source retransmits frame i and all subsequent frames
A. Biswas
Go-Back-N: Lost Frame (1)
26
Assume receiver has received frame i-1. If frame i is lost
Source subsequently sends i+1
Receiver gets frame i+1 out of order
At data link layer, this means the lost of a frame!
Receiver sends REJ-i
Source gets REJ-i, and so goes back to frame i and retransmits frame i,
i+1, …
A. Biswas
13
9/11/2025
Go-Back-N: Lost Frame (2)
27
Assume receiver has received frame i-1
Frame i is lost and no additional frame is sent
Receiver gets nothing and returns neither acknowledgement nor
rejection
Source times out and sends a request to receiver asking for instructions
Receiver responses with RR frame, including the number of the next
frame it expects, i.e., frame i
Source then retransmits frame i
A. Biswas
Go-Back-N: Damaged RR
28
Receiver gets frame i and sends RR-(i+1) which is lost or damaged
Acknowledgements are cumulative, so the next acknowledgement, i.e.,
RR-(i+n) may arrive before the source times out on frame i
If source times out, it sends a request to receiver asking for instructions,
just like the previous example
A. Biswas
14
9/11/2025
Go-Back-N: Damaged REJ
29
It is equivalent to the case of lost frame (2).
Source times out and sends a request to receiver asking for instructions
Receiver responses with RR frame, including the number of the next
frame it expects
Source then retransmits
A. Biswas
Go-Back-N Diagram
30
Remark:
RR(P bit = 1) is a special RR which is used by the source to
ask for instructions.
For a k-bit sequence number, the window size can be at most
2k-1, otherwise RR0 is ambiguous (e.g., first sends frame 0
and gets back an RR1, and then sends frames 1,…,7,0, and
gets another RR1).
15
9/11/2025
Selective-Reject ARQ
31
Also called selective repeat
Pros:
Only rejected frames are retransmitted
Subsequent frames are accepted by the receiver and buffered
Minimizes the amount of retransmissions
Cons:
Receiver must maintain large enough buffer, and must contain logic for
reinserting the retransmitted frame in the proper sequence
Also more complex logic in the source
A. Biswas
Selective Reject -Diagram
32
For a k-bit sequence number, the window size can be at most
2k-1, because the sending and receiving windows overlap.
Assume k=3, and window size is 5.
1. A sends frames 2, 3, 4 to B.
2. B receives frames 2 and 3, and cumulatively
acknowledges with RR4.
3. The frame 4 has been lost but receiver receives frame 5
and buffers as it is out of order. Sender sends next frame 6.
4. Receiver sends SREJ-4 as frame 4 is not received yet.
5. Sender sends frame 4 and next frame 7.
6. Receiver sends RR7 when it receives frame 4.
7. When sender receives RR7 it knows upto frame 7 have
been received and it sends frame 0 (as sequence no is
modulo 23).
16
9/11/2025
Piggybacking
33
So far we have considered unidirectional data transmission.
However, in real scenarios, data transfer takes place in both directions.
Hence, for better utilization of channel and time, control information or
acknowledgement is sent along with the data frame.
This is referred as piggybacking.
A. Biswas
17