Data Link Layer Protocols: Flow and Medium Access Control

Welcome to the second major topic in this module: Computer Networks. Having built a solid understanding of how to structure and manage data within a database, we now turn our attention to how data is reliably transmitted across physical distances. This lesson marks our first step into the layered architecture that governs modern computer communication.

In our last session, we focused on the dynamic aspect of databases, ensuring correct concurrent execution using serializability analysis and locking protocols. Today, we move from a single system to interconnected systems and explore the responsibilities of the Data Link Layer (Layer 2). This layer is the "local traffic cop" of the network, managing communication between machines on the same physical link.

Our learning outcome is to analyze Data Link Layer protocols for flow control (Stop-and-Wait, GBN, SR) and medium access control (CSMA/CD). We will dissect how we prevent a fast sender from overwhelming a slow receiver (flow control) and how multiple devices on a shared wire decide who talks next without causing chaos (medium access control). These protocols are not just theoretical; they are fundamental to how technologies like Ethernet and Wi-Fi operate, and their analysis is a frequent source of numerical questions in the GATE exam.

The Role of the Data Link Layer

Before diving into the protocols, let's place the Data Link Layer (DLL) in context. In network models like OSI or TCP/IP, the DLL sits between the Physical Layer (which deals with raw bit transmission) and the Network Layer (which handles routing across different networks). The DLL's job is to ensure reliable data transfer over a single link or local network.

It accomplishes this through several key functions, but today we focus on two:

Flow Control: A mechanism to regulate the rate of data transmission between a specific sender and receiver. It's a point-to-point concern, ensuring the receiver's buffer doesn't overflow.
Medium Access Control (MAC): A set of rules needed when the communication channel is a shared medium (like an old Ethernet cable or a Wi-Fi channel). The MAC sublayer of the DLL decides which station gets to use the channel at any given time, aiming to prevent or manage collisions.

Let's explore the classic protocols for each of these functions.

Part 1: Flow Control Protocols

Imagine a sender transmitting data much faster than the receiver can process it. The receiver's buffer would quickly fill up, and any subsequent data would be dropped, leading to wasteful retransmissions. Flow control protocols provide feedback from the receiver to the sender to manage this flow. The main mechanism for this is the sliding window.

The sender maintains a "window" of sequence numbers corresponding to frames it is permitted to send. As it receives acknowledgements (ACKs) from the receiver, this window "slides" forward, allowing new frames to be sent. We will examine three implementations of this idea: Stop-and-Wait, Go-Back-N, and Selective Repeat.

Lec-25: Various Flow Control Protocols | Stop&Wait , GoBackN & Selective repeat in Data Link Layer

This Gate Smashers video provides an excellent, comparative overview of the three main flow control protocols. It focuses on the key parameters and formulas you'll need for the GATE exam.

Watch the entire video from start to finish. As you watch, focus on creating a mental comparison table for the three protocols based on these critical parameters: Sender Window Size (SWS) and Receiver Window Size (RWS): How many frames can the sender transmit, and how many can the receiver buffer? Efficiency/Utilization: What fraction of the channel's capacity is used for transmitting useful data? Acknowledgement (ACK) Strategy: Does the receiver acknowledge every frame individually or cumulatively? Retransmission Strategy: If a frame is lost, does the sender retransmit just that frame or the entire window?

Let's consolidate and build upon what you've just watched. A key parameter in all efficiency calculations is $a$ , defined as the ratio of propagation delay to transmission time: $a = T_{p} / T_{t}$ .

Transmission Time ( $T_{t}$ ): The time it takes to put the frame onto the wire. $T_{t} = \frac{Frame Size}{Bandwidth}$ .
Propagation Delay ( $T_{p}$ ): The time it takes for the first bit of the frame to travel from the sender to the receiver. $T_{p} = \frac{Distance}{Propagation Speed}$ .

Stop-and-Wait

This is the simplest protocol. The sender sends one frame and waits for its acknowledgement before sending the next.

Window Sizes: Sender Window Size (SWS) = 1, Receiver Window Size (RWS) = 1.
Efficiency ( $η$ ): The sender is active only for the $T_{t}$ duration in a total cycle of $T_{t} + 2 T_{p}$ . This gives the efficiency: $η = \frac{T _{t}}{T _{t} + 2 T _{p}} = \frac{1}{1 + 2 a}$
Sequence Numbers: To distinguish a new frame from a retransmission of the previous one, we only need two sequence numbers (e.g., 0 and 1). The total number of sequence numbers required is SWS + RWS = 1 + 1 = 2.

Go-Back-N (GBN)

GBN improves upon Stop-and-Wait by allowing the sender to transmit multiple frames (up to the window size) without waiting for an ACK.

Window Sizes: SWS = $2^{k} - 1$ , RWS = 1, where $k$ is the number of bits used for the sequence number.
The Bottleneck (RWS = 1): The receiver's window size of 1 is the defining feature of GBN. It will only accept frames in perfect order. If frame $i$ is lost, the receiver will discard all subsequent frames ( $i + 1, i + 2, \dots$ ) until it receives frame $i$ correctly.
Acknowledgement: GBN uses cumulative acknowledgements. An ACK for frame $n$ implies that all frames up to and including $n$ have been received correctly.
Retransmission: If a timeout occurs for frame $i$ , the sender "goes back" and retransmits frame $i$ and all subsequent frames in the window ( $i + 1, i + 2, \dots$ ). This can be very inefficient.
Efficiency: In the ideal case (no errors), the sender can continuously pump frames into the network. The efficiency is: $η = \frac{S W S}{1 + 2 a} = \frac{2 ^{k} - 1}{1 + 2 a}$

Selective Repeat (SR)

SR (also called Selective Reject) improves upon GBN by allowing the receiver to accept and buffer out-of-order frames.

Window Sizes: SWS = RWS = $2^{k - 1}$ . This is a critical relationship. If SWS + RWS > $2^{k}$ , ambiguity can arise where a retransmitted frame from an old window is mistaken for a new frame. Setting SWS = RWS = $2^{k - 1}$ is the standard and optimal configuration that prevents this.
The Improvement (RWS > 1): Because the receiver can buffer out-of-order frames, it doesn't need to discard correct frames that arrive after a lost one.
Acknowledgement: The receiver sends an individual ACK for each correctly received frame. It can also use Negative Acknowledgements (NAKs) to quickly inform the sender about a specific missing frame, triggering a faster retransmission.
Retransmission: The sender only retransmits the specific frames that are lost or negatively acknowledged. This is far more efficient than GBN's approach.
Efficiency: Similar to GBN, the efficiency depends on the sender's window size: $η = \frac{S W S}{1 + 2 a} = \frac{2 ^{k - 1}}{1 + 2 a}$

Quick Comparison for GATE

Feature	Stop-and-Wait	Go-Back-N (GBN)	Selective Repeat (SR)
SWS	1	$2^{k} - 1$	$2^{k - 1}$
RWS	1	1	$2^{k - 1}$
Efficiency ( $η$ )	$\frac{1}{1 + 2 a}$	$\frac{S W S}{1 + 2 a}$	$\frac{S W S}{1 + 2 a}$
ACK Type	Individual	Cumulative	Individual / NAKs
Out-of-Order Frames	N/A	Discarded	Buffered
Retransmissions	Single Frame	Entire Window	Single Frame

Part 2: Medium Access Control (MAC) - CSMA/CD

Flow control protocols assume we have a dedicated point-to-point link. But what happens on a broadcast channel like a classic Ethernet bus or a wireless network, where everyone shares the same medium? If two stations transmit simultaneously, their signals interfere, resulting in a collision. MAC protocols are designed to handle this.

We'll focus on Carrier Sense Multiple Access with Collision Detection (CSMA/CD), the protocol that was central to early Ethernet.

Let's break down the name:

Carrier Sense (CS): "Listen before you talk." A station senses the channel to see if it's idle before attempting to transmit.
Multiple Access (MA): Multiple stations share the same communication medium.
Collision Detection (CD): "Listen while you talk." A station continues to monitor the channel while transmitting. If it detects that its signal is interfering with another signal (a collision), it immediately stops, sends a jam signal, and waits for a random backoff period before trying again.

The most critical part of CSMA/CD for GATE is understanding the condition required to guarantee collision detection.

Lec-35: Carrier Sense Multiple Access/ Collision Detection | CSMA/CD | Computer Networks

This Gate Smashers video explains the core mechanism of CSMA/CD. It masterfully builds up to the worst-case scenario to derive the single most important formula related to this protocol.

Please watch the video, paying special attention to the following parts: Collision Detection Logic: Grasp the fundamental condition: a station can only be sure a collision involved its own frame if it detects the collision while it is still transmitting. Worst-Case Scenario Derivation: This is the most crucial segment. Follow the logic of why the transmission time (T_t) must be at least twice the propagation delay (T_p) to ensure collision detection across the entire network.

The key insight from the video is that a station must transmit for a long enough duration to ensure that a collision signal, originating from the farthest possible point in the network, has time to travel back to the sender before the sender finishes its transmission.

Let's formalize this "worst-case" scenario:

Station A at one end of the network starts transmitting at time $t = 0$ .
The signal from A travels towards the other end. The time taken to reach the farthest station, B, is the maximum propagation delay, $T_{p}$ .
Just an instant before A's signal arrives, at time $t = T_{p} - ϵ$ , station B senses the channel, finds it idle, and starts transmitting.
A collision occurs near station B at approximately time $t = T_{p}$ .
Now, this collision signal must travel all the way back to station A. This takes another $T_{p}$ time.
Station A will detect the collision at time $t = T_{p} + T_{p} = 2 T_{p}$ .

For A to be able to detect this collision, it must still be transmitting at time $2 T_{p}$ . This leads to the fundamental constraint of CSMA/CD:

T_{t} \geq 2 T_{p}

This relationship is the basis for many GATE numericals. Since $T_{t} = L / B$ (where L is frame size, B is bandwidth) and $T_{p} = d / v$ (where d is distance, v is propagation speed), the formula can be expanded:

\frac{L _{min}}{B} \geq 2 \times \frac{d}{v} ⟹ L_{min} = 2 \times T_{p} \times B

This shows that for a given network span and bandwidth, there is a minimum frame size. This is why Ethernet frames have a minimum size of 64 bytes.

Conclusion

In this lesson, we have moved from the world of databases into the foundational layers of computer networks. We dissected the critical Data Link Layer responsibilities of managing data flow and coordinating access to a shared medium.

Here are the key takeaways for your GATE preparation:

Flow Control Protocols (Stop-and-Wait, GBN, SR) manage the transmission rate between a single sender and receiver. Your ability to quickly compare their window sizes, efficiency, and retransmission strategies is crucial.
CSMA/CD is a random access MAC protocol for shared channels. Its governing principle is "listen before and while you talk."
The most important formula for CSMA/CD is $T_{t} \geq 2 T_{p}$ . This ensures that a station can detect the worst-case collision. This formula directly links minimum frame size, network length, and bandwidth, making it a hotspot for numerical problems.

You have now analyzed the core protocols of Layer 2. In our next lesson, we will ascend the network stack to explore Layers III, IV, and V. We will examine how the Network Layer (using IP addressing and routing algorithms) finds paths across the internet, how the Transport Layer (with TCP and UDP) provides end-to-end communication services, and finally, how the Application Layer supports the services we use every day, like DNS and HTTP.

Recommended resources