What are common examiner traps in Data Link Layer?

Unit mismatch: Failing to convert between bytes and bits (multiplying or dividing by 8) for frame size or bandwidth. Metric prefixes: Confusing 1 kbps = 103 bps (networking convention) with 210 bps, or mixing milliseconds (10-3 s) with microseconds (10-6 s) and nanoseconds (10-9 s). One-way vs. Round-Trip Time: Forgetting that total cycle time includes 2 Tp (round-trip propagation) rather than single Tp. Useful vs. Total Transmission Time: Neglecting to subtract header/overhead bytes when computing useful transmission efficiency if distinct overheads are specified. CRC 0-padding: Appending k zeros instead of (k - 1) zeros for a generator pattern of length k bits. Confusing Selective Repeat sequence space (N 2Ws) with Go-Back-N sequence space (N Ws + 1). Failing to ceil the continuous value of window size 1 + 2a to an integer before multiplying by 2 for Selective Repeat sequence space. Unit conversion errors between bits and bytes (e.g., 1 KB = 1024 8 bits or 1000 8 bits) and milliseconds to seconds. Confusing one-way propagation delay (Tp) with round-trip propagation time (RTT = 2Tp). Misinterpreting polynomial degree: appending r+1 zeros instead of r zeros (where divisor length is r+1). Omitting zero-coefficient terms when converting the polynomial to binary (e.g., mistaking X3 + X + 1 as 111 instead of 1011). Using standard binary division with carry/borrow rather than bitwise XOR (modulo-2) division. Stopping division prematurely or padding leading zeros incorrectly in the final r-bit remainder. Appending the number of bits in the generator instead of its degree (e.g., appending 4 zeros for a 4-bit polynomial of degree 3). Translating polynomials to bitstrings incorrectly by omitting zero coefficients (e.g., writing x3 + x + 1 as `111` instead of `1011`). Confusing error-detection capability (d -1) with error-correction capability ( (d -1)/2 ). Misidentifying bit index directions (1-based index vs 0-based, or LSB-to-MSB vs MSB-to-LSB) when setting up parity equations in Hamming codes. Confusing bits vs. bytes when calculating Tt = L/B (e.g., 1 KB = 8192 bits or 8000 bits vs. 1 Kb). Forgetting that Selective Repeat requires M 2 WS while Go-Back-N requires M WS + 1 when determining sequence bit field width. Neglecting the factor of 2 in round-trip propagation time (2 Tp) or omitting non-zero ACK transmission time (Tt(ack)) when specified in the prompt. Mixing up Pure ALOHA (e-2G) and Slotted ALOHA (e-G) exponents. Destuffing error: removing zeros that were part of original payload instead of strictly removing a '0' only immediately following five consecutive '1's. Neglecting acknowledgement transmission time (Tt,ack) by assuming ACKs are negligible in size. Multiplying propagation delay only once instead of two-way round-trip (2 Tp). Unit mismatch errors, such as confusing bits and bytes (e.g., 1000 bytes = 8000 bits) or standard metric conversions (1 Kbps = 1000 bps vs 1024 bps). Reporting throughput in bits/second when the question explicitly requests bytes/second. Confusing the broadcast MAC address at layer 2 with a broadcast IP address at layer 3 during ARP request framing. Assuming the default gateway resolves or proxies MAC addresses for hosts located within the same local subnet. Confusing the ARP request (broadcast) with the ARP reply (unicast). Forgetting to multiply byte frame sizes by 8 when working with bandwidth in bps (1250 bytes = 10000 bits). Confusing CSMA/CD with CSMA/CA: assuming RTS/CTS is used for collision detection rather than collision avoidance. Omitting the factor of 2 in Tt 2 Tp (the round-trip propagation time required to hear a collision). Off-by-one station counts in Token Ring when computing token holding time (whether to include N vs N-1 non-monitor stations). Unit mismatch traps: confusing (10-6 s) with ms (10-3 s), and km/s with m/s. Confusing the function of a jamming signal (alerting network to a collision) with frame padding (ensuring minimum frame length). Assuming carrier sensing occurs only before transmission begins, overlooking that CSMA/CD must continuously sense while transmitting. Believing a node completes sending its frame/packet even after collision detection occurs.

Data Link Layer

27 Qs · since 2013 · 49 marks · 1.9 marks/paperMedium yield

Take topic test

Medium Access Control (MAC) in GATE CS is predominantly tested through quantitative numerical problems and conceptual protocol comparisons. The focus is split between random access… Guide

Type

GATE CSE 2026 Set 1Q45MCQ2 marksMediumConsider the implementation of sliding window protocol over a lossless link, with a window size of $W$ frames, where each frame is of size 1000 bits (including header). The bandwidth of the link is 100 kbps ( $1\text{k} = 10^3$ ) and the one-way propagation delay is 100 milliseconds. Assume that processing times at…
GATE CSE 2026 Set 2Q43MCQ2 marksMediumConsider the transmission of data bits 110001011 over a link that uses Cyclic Redundancy Check (CRC) code for error detection. If the generator bit pattern is given to be 1001, which one of the following options shows the remainder bit pattern appended to the data bits before transmission?
GATE CSE 2026 Set 2Q65NAT2 marksMediumIt is necessary to design a link-layer protocol between two hosts that are directly connected over a lossless link of length 3000 kilometers. Assume that the link bandwidth is $10^8$ bits per second and that the propagation delay in the link is 5 nanoseconds per meter. Every transmitted data byte is assigned a…
GATE CSE 2025 Set 2Q36MCQ2 marksEasySuppose we are transmitting frames between two nodes using Stop-and-Wait protocol. The frame size is 3000 bits. The transmission rate of the channel is 2000 bps (bits/second) and the propagation delay between the two nodes is 100 milliseconds. Assume that the processing times at the source and destination are…
GATE CSE 2024 Set 2Q55NAT2 marksEasyConsider an Ethernet segment with a transmission speed of $10^8$ bits/sec and a maximum segment length of 500 meters. If the speed of propagation of the signal in the medium is $2\times 10^8$ meters/sec, then the minimum frame size ( $\textit{in bits}$ ) required for collision detection is ________
GATE CSE 2023Q17MCQ1 markEasySuppose two hosts are connected by a point-to-point link and they are configured to use Stop-and-Wait protocol for reliable data transfer. Identify in which one of the following scenarios, the utilization of the link is the lowest.
GATE CSE 2021 Set 1Q8MCQ1 markEasyConsider the following two statements. $S_1 : \quad \text{Destination MAC address of an ARP reply is a broadcast address.}$ $S_2 : \quad \text{Destination MAC address of an ARP request is a broadcast address.}$ Which one of the following choices is correct?
GATE CSE 2021 Set 1Q29MCQ2 marksMediumDiagramAssume that a 12-bit Hamming codeword consisting of 8-bit data and 4 check bits is $d_8d_7d_6d_5c_8d_4d_3d_2c_4d_1c_2c_1$ , where the data bits and the check bits are given in the following tables: Which one of the following choices gives the correct values of $x$ and $y$ ?
GATE CSE 2021 Set 1Q49NAT2 marksMediumConsider the sliding window flow-control protocol operating between a sender and a receiver over a full-duplex error-free link. Assume the following: • The time taken for processing the data frame by the receiver is negligible. • The time taken for processing the acknowledgement frame by the sender is negligible. •…
GATE CSE 2021 Set 2Q34MCQ2 marksMediumConsider the cyclic redundancy check (CRC) based error detecting scheme having the generator polynomial $X^3 + X + 1$ . Suppose the message $m_4 m_3 m_2 m_1 m_0 = 11000$ is to be transmitted. Check bits $c_2 c_1 c_0$ are appended at the end of the message by the transmitter using the above CRC scheme. The…
GATE CSE 2021 Set 2Q54NAT2 marksEasyConsider a network using the pure ALOHA medium access control protocol, where each frame is of length 1,000 bits. The channel transmission rate is 1 Mbps ( $= 10^6$ bits per second). The aggregate number of transmissions across all the nodes (including new frame transmissions and retransmitted frames due to…
GATE CSE 2019Q29MCQ2 marksEasySuppose that in an IP-over-Ethernet network, a machine X wishes to find the MAC address of another machine Y in its subnet. Which one of the following techniques can be used for this?
GATE CSE 2017 Set 1Q32MCQ2 marksMediumA computer network uses polynomials over $GF(2)$ for error checking with 8 bits as information bits and uses $x^3 + x + 1$ as the generator polynomial to generate the check bits. In this network, the message 01011011 is transmitted as
GATE CSE 2017 Set 1Q45NAT2 marksMediumThe values of parameters for the Stop-and-Wait ARQ protocol are as given below: Bit rate of the transmission channel = 1 Mbps. Propagation delay from sender to receiver = 0.75 ms. Time to process a frame = 0.25 ms. Number of bytes in the information frame = 1980. Number of bytes in the acknowledge frame = 20. Number…
GATE CSE 2017 Set 2Q34MCQ2 marksEasyConsider a binary code that consists of only four valid codewords as given below: $00000, 01011, 10101, 11110$ Let the minimum Hamming distance of the code be $p$ and the maximum number of erroneous bits that can be corrected by the code be $q$ . Then the values of $p$ and $q$ are
GATE CSE 2016 Set 1Q55NAT2 marksMediumA sender uses the Stop-and-Wait ARQ protocol for reliable transmission of frames. Frames are of size 1000 bytes and the transmission rate at the sender is 80 Kbps (1Kbps = 1000 bits/second). Size of an acknowledgement is 100 bytes and the transmission rate at the receiver is 8 Kbps. The one-way propagation delay is…
GATE CSE 2016 Set 2Q24MCQ1 markMediumIn an Ethernet local area network, which one of the following statements is TRUE?
GATE CSE 2016 Set 2Q53NAT2 marksEasyA network has a data transmission bandwidth of $20 \times 10^6$ bits per second. It uses CSMA/CD in the MAC layer. The maximum signal propagation time from one node to another node is $40$ microseconds. The minimum size of a frame in the network is _______ bytes.
GATE CSE 2016 Set 2Q54MCQ2 marksMediumFor the IEEE 802.11 MAC protocol for wireless communication, which of the following statements is/are TRUE? I. At least three non-overlapping channels are available for transmissions. II. The RTS-CTS mechanism is used for collision detection. III. Unicast frames are ACKed.
GATE CSE 2016 Set 2Q55NAT2 marksMediumConsider a $128 \times 10^3$ bits/second satellite communication link with one way propagation delay of 150 milliseconds. Selective retransmission (repeat) protocol is used on this link to send data with a frame size of 1 kilobyte. Neglect the transmission time of acknowledgement. The minimum number of bits required…
GATE CSE 2015 Set 1Q29NAT2 marksMediumConsider a LAN with four nodes $S_1, S_2, S_3$ and $S_4$ . Time is divided into fixed-size slots, and a node can begin its transmission only at the beginning of a slot. A collision is said to have occurred if more than one node transmit in the same slot. The probabilities of generation of a frame in a time slot by $S_1, S_2, S_3$ …
GATE CSE 2015 Set 1Q53NAT2 marksEasySuppose that the stop-and-wait protocol is used on a link with a bit rate of 64 kilobits per second and 20 milliseconds propagation delay. Assume that the transmission time for the acknowledgement and the processing time at nodes are negligible. Then the minimum frame size in bytes to achieve a link utilization of at…
GATE CSE 2015 Set 3Q6MCQ1 markEasyConsider a CSMA/CD network that transmits data at a rate of 100 Mbps ( $10^8$ bits per second) over a 1 km (kilometer) cable with no repeaters. If the minimum frame size required for this network is 1250 bytes, what is the signal speed (km/sec) in the cable?
GATE CSE 2014 Set 1Q26NAT2 marksMediumConsider a token ring network with a length of 2 km having 10 stations including a monitoring station. The propagation speed of the signal is $2 \times 10^8\text{ m/s}$ and the token transmission time is ignored. If each station is allowed to hold the token for $2\text{ }\mu\text{sec}$ , the minimum time for which…
GATE CSE 2014 Set 1Q28NAT2 marksMediumConsider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilization of 60%, the minimum number of bits required to represent the sequence number field is _________.
GATE CSE 2014 Set 3Q24MCQ1 markEasyA bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string is
GATE CSE 2013Q36MCQ2 marksEasyDetermine the maximum length of the cable (in km) for transmitting data at a rate of 500 Mbps in an Ethernet LAN with frames of size 10,000 bits. Assume the signal speed in the cable to be 2,00,000 km/s.

Topic guide

What does GATE test in Data Link Layer?

Medium Access Control (MAC) in GATE CS is predominantly tested through quantitative numerical problems and conceptual protocol comparisons. The focus is split between random access protocols (CSMA/CD collision detection constraints and slotted ALOHA transmission probabilities), controlled access (Token Ring round-trip delays and token holding limits), and wireless MAC protocols (IEEE 802.11 CSMA/CA features, channels, and ACK mechanisms). Most questions carry 2 marks and appear in NAT format requiring unit conversions.

Core concepts

Stop-and-Wait Protocol and ARQ efficiency
Sliding Window Protocols (Go-Back-N, Selective Repeat)
Bandwidth-Delay Product (BDP) and Channel Utilization
Sequence Number Field sizing and wrap-around time constraints
Error Detection using Cyclic Redundancy Check (CRC) modulo-2 division
Transmission delay vs. Propagation delay vs. Processing delay trade-offs
Selective Repeat (SR) ARQ Mechanics
Propagation Delay (Tp) vs Transmission Time (Tt)
Link Utilization and Efficiency ( )
Window Sizing (Ws, Wr)
Sequence Number Space Sizing (2k Ws + Wr)
Cyclic Redundancy Check (CRC) mechanism
Generator polynomial degree and binary bit representation
Appending r zero bits for a degree-r polynomial
Modulo-2 arithmetic (bitwise XOR division)
Codeword construction (M R)
Modulo-2 arithmetic and polynomial division over GF(2)
Cyclic Redundancy Check (CRC) generator polynomial encoding and check-bit calculation
Pairwise Hamming distance and minimum Hamming distance (d )
Error-detecting vs error-correcting capability trade-offs
Hamming Code structure, power-of-two check bit placement, and parity equations
CSMA/CD collision detection constraint (Tt 2 Tp)
Sliding Window Protocols (Stop-and-Wait, Go-Back-N, Selective Repeat)
Window sizing vs. sequence number space requirements (WS + WR 2k)
Bit-stuffing and bit-destuffing algorithms (e.g., HDLC 5 consecutive 1s rule)
ARP Request (Broadcast MAC) and ARP Reply (Unicast MAC) addressing
Pure ALOHA vs Slotted ALOHA throughput and vulnerable time periods
Stop-and-Wait ARQ protocol timing
Transmission delay vs Propagation delay
Acknowledgement transmission overhead (Tt,ack)
Asymmetric bandwidth rates (Sender vs Receiver)
Throughput calculation in bytes per second
Address Resolution Protocol (ARP) Request and Reply mechanics
Ethernet broadcast MAC address (FF:FF:FF:FF:FF:FF)
Intra-subnet vs. Inter-subnet communication (Direct delivery vs. Default Gateway)
Data Link Layer frame encapsulation of Network Layer packets
CSMA/CD collision detection principle (Tt 2 Tp)
Slotted ALOHA collision and success probability modeling
Token Ring propagation delay, station holding time, and monitor station duties
IEEE 802.11 CSMA/CA mechanism and why CD fails in wireless
RTS/CTS mechanism for hidden terminal problem / collision avoidance
Link-layer ACK requirement for wireless unicast frames
Non-overlapping channel allocation in IEEE 802.11 (e.g. 1, 6, 11 in 2.4 GHz)
Carrier Sense Multiple Access with Collision Detection (CSMA/CD)
Continuous channel sensing during transmission
Jamming signal function vs. Frame padding
Immediate transmission abortion upon collision
Binary Exponential Backoff algorithm and collision probability reduction

Recurring question patterns

Stop-and-Wait Protocol Efficiency and Parameter Sizing
common · mixed · 2 marks · 2025, 2017, 2015
Calculations involving link utilization $\eta = \frac{T_t}{T_{\text{total}}}$ , determining minimum frame size for target utilization, or finding efficiency with detailed parameters including ACK transmission time, processing overheads, and packet headers.
Sliding Window Sizing and Sequence Number Constraints
common · mixed · 2 marks · 2026
Calculating optimal sender window size $W = 1 + 2a$ for 100% link utilization, or determining the sequence number bit width $N$ under dual constraints of maximum link utilization and sequence number wrap-around time.
Cyclic Redundancy Check (CRC) Modulo-2 Division
occasional · MCQ · 2 marks · 2026
Given a data bit sequence and a generator polynomial bit pattern of length $k$ , finding the $(k-1)$ -bit CRC remainder appended to the frame by performing XOR-based modulo-2 division.
Qualitative Analysis of Protocol Utilization
occasional · MCQ · 1 marks · 2023
Identifying the relationship between protocol efficiency $\eta = \frac{1}{1 + 2a}$ and physical parameters like link distance, bandwidth, frame size, and propagation velocity.
Sequence Number Field Sizing for Sliding Window Protocols
occasional · NAT · 2 marks · 2016
Given channel bandwidth, one-way propagation delay, frame length, and protocol type (e.g., Selective Repeat), compute the frame transmission time, required sender window size for target link utilization (often 100%), total sequence number space size ( $W_s + W_r$ ), and the minimum number of sequence number bits required.
CRC Remainder / Checkbit Calculation
common · MCQ · 2 marks · 2021
Given a generator polynomial $G(X)$ of degree $r$ and a binary data word / message $M$ , calculate the $r$ -bit CRC code (remainder) generated by modulo-2 polynomial division of $(M \cdot 2^r)$ by $G(X)$ .
CRC Transmitted Codeword Computation
common · MCQ · 2 marks · 2017
Given a generator polynomial over GF(2) and a binary information bit sequence, append r zeros (where r is the degree of the polynomial), perform modulo-2 binary division (XOR), and append the remainder to form the transmitted codeword.
Minimum Hamming Distance and Error Bounds
occasional · MCQ · 2 marks · 2017
Given a finite set of binary codewords, compute all pairwise Hamming distances to find the minimum distance $d_{\min}$ , and determine the error detection ( $e$ ) and error correction ( $q$ ) limits.
Hamming Code Parity and Bit Reconstruction
occasional · MCQ · 2 marks · 2021
Given a Hamming code layout with check bits at powers-of-two positions and partial data/check bit assignments, formulate even/odd parity equations to solve for unknown bit values.
CSMA/CD Collision Detection Limit Calculation
common · mixed · 2 marks · 2024, 2013
Given three of the four parameters (bandwidth $B$ , segment length $d$ , propagation velocity $v$ , frame size $L$ ), calculate the missing critical threshold using the fundamental collision detection condition $T_t \ge 2 T_p$ .
Sliding Window Protocol Efficiency and Sequence Sizing
common · NAT · 2 marks · 2021, 2014
Calculate sender window size, total cycle time (including data transmission, round-trip propagation, and optionally ACK transmission delay), or the minimum sequence number field bits required for Go-Back-N or Selective Repeat to achieve a target link utilization.
Random Access Throughput (ALOHA)
occasional · NAT · 2 marks · 2021
Compute the offered load $G = \lambda \times T_{\text{fr}}$ from aggregate Poisson arrival rates and frame transmission time, and evaluate network throughput using the success probability models of Pure or Slotted ALOHA.
Framing Mechanics and Link Layer Addressing
occasional · MCQ · 1 marks · 2021, 2014
Evaluate exact bit/byte stuffing and destuffing patterns given standard flag delimiters (such as 01111110), or determine the unicast vs. broadcast addressing nature of control frames like ARP request/reply.
Stop-and-Wait ARQ Throughput Calculation with ACK Transmission Delay
common · NAT · 2 marks · 2016
Given frame size, sender transmission rate, ACK packet size, receiver transmission rate, and one-way propagation delay, calculate total cycle time and resulting throughput in bytes/second or bps.
Intra-Subnet Address Resolution (ARP over Ethernet)
occasional · MCQ · 2 marks · 2019
Questions asking how a source host resolves the MAC address of a destination host within the same local subnet using ARP broadcast at the Data Link layer.
CSMA/CD Minimum Frame Size & Timing Constraint
common · NAT · 2 marks · 2016, 2015
Given bandwidth, distance/propagation delay, and signal speed or frame size, use the fundamental CSMA/CD constraint $T_t \ge 2 \times T_p$ to calculate the missing parameter (minimum frame size in bytes, signal speed in km/s, or maximum cable length).
Discrete Slot Collision and Success Probability
occasional · NAT · 2 marks · 2015
Calculate the probability that exactly one node transmits successfully in a given time slot without collision, given independent transmission/frame generation probabilities for each node in a slotted LAN environment.
Token Ring Maximum Cycle Time & Timer Limits
occasional · NAT · 2 marks · 2014
Compute the total ring latency and token timer threshold before a monitor station declares the token lost, by summing total ring propagation delay and cumulative token holding times across stations.
Wireless MAC (IEEE 802.11) Protocol Properties
occasional · MCQ · 2 marks · 2016
Conceptual multi-statement evaluation regarding IEEE 802.11 wireless LAN characteristics, including CSMA/CA vs. CSMA/CD, RTS/CTS virtual carrier sensing, non-overlapping 2.4 GHz channels, and unicast ACK requirements.
Conceptual Statement Evaluation of CSMA/CD Protocols
common · MCQ · 1 marks · 2016
Questions present four statements describing operations of the MAC sublayer in Ethernet (such as continuous sensing, collision abortion, jamming signal usage, or backoff window expansion) and ask to identify the TRUE/FALSE statement.

Formulas GATE uses

Transmission Time and Propagation Delay

T_t = \frac{L}{B}, \quad T_p = \frac{d}{v}

Used to compute data/ACK packet transmission times and one-way propagation delays from frame length $L$ , bandwidth $B$ , distance $d$ , and signal speed $v$ .

Stop-and-Wait Efficiency (Standard / Ideal)

\eta = \frac{T_t}{T_t + 2T_p} = \frac{1}{1 + 2a}, \quad \text{where } a = \frac{T_p}{T_t}

Used when processing delay and ACK transmission time are negligible.

Stop-and-Wait ARQ Efficiency (Detailed with Overheads)

\eta = \frac{T_{\text{useful}}}{T_t + 2T_p + T_{\text{proc}} + T_{\text{ack}}}

Used when ACK size, node processing time, or header/payload byte separations are explicitly specified.

Sliding Window Optimal Window Size for 100% Utilization

W \ge 1 + 2a = 1 + 2\left(\frac{T_p}{T_t}\right)

Used to find the minimum sender window size $W$ (in frames) needed to achieve full link utilization.

Sequence Number Space and Wrap-around Time

$2^N \ge \text{Bandwidth (bytes/s)} \times T_{\text{wrap-around}}$ and $2^N \ge W_s + W_r$

Used when determining the minimum sequence number bits $N$ under maximum throughput and lifetime/wrap-around constraints.

CRC Modulo-2 Arithmetic

\text{Appended Bits} = (k - 1) \text{ zeros}, \quad \text{Remainder} = (\text{Data} \cdot 2^{k-1}) \pmod_2 G

Used to compute CRC checksum/FCS bits for an error-detecting generator $G$ of length $k$ .

Frame Transmission Time

T_t = \frac{L}{B}

Used to find the time taken to transmit a data frame of size $L$ over a link of bandwidth $B$ .

Normalized Propagation Delay (a-parameter)

a = \frac{T_p}{T_t}

Used to relate one-way propagation delay $T_p$ to packet transmission delay $T_t$ .

Sliding Window Utilization and Sender Window Size

\eta = \frac{W_s}{1 + 2a} \implies W_s = \lceil 1 + 2a \rceil \quad (\text{for } \eta = 1)

Used to find the minimum integer sender window size $W_s$ required to achieve 100% link utilization.

Selective Repeat Sequence Number Space

N \ge W_s + W_r = 2 W_s

Used to calculate the minimum distinct sequence numbers required in Selective Repeat where $W_r = W_s$ .

Sequence Number Bits Requirement

k = \lceil \log_2 N \rceil

Used to determine the minimum number of bits $k$ allocated in the frame header for the sequence number field.

Polynomial to Binary Generator Divisor Mapping

G(X) = \sum_{i=0}^{r} g_i X^i \implies G = g_r g_{r-1} \dots g_0

Converting a given generator polynomial of degree $r$ into an $(r+1)$ -bit binary divisor.

Augmented Message Construction

M^{\prime}(X) = M(X) \cdot X^r

Appending $r$ zeros to the right of an $n$ -bit message before executing modulo-2 division.

Modulo-2 CRC Remainder Relation

M^{\prime}(X) = Q(X) \cdot G(X) \oplus R(X) \quad \text{where } \deg(R(X)) < r

Finding the $r$ -bit remainder $R$ that serves as the CRC checkbit sequence appended to form the transmitted codeword.

Error-Correcting Capability Bound

d_{\min} \ge 2q + 1 \implies q = \left\lfloor \frac{d_{\min} - 1}{2} \right\rfloor

Used to compute the maximum number of erroneous bits $q$ that a block code with minimum distance $d_{\min}$ can correct.

Error-Detecting Capability Bound

d_{\min} \ge e + 1 \implies e = d_{\min} - 1

Used to compute the maximum number of error bits $e$ guaranteed to be detected.

CRC Appended Zero Count

r = \deg(G(x))

Determines the number of zero bits appended to the message before polynomial division, where $G(x)$ is the generator polynomial.

Hamming Parity Coverage Rule

c_{2^k} = \bigoplus \{ b_i \mid \text{the } k\text{-th bit of binary index } i \text{ is } 1 \}

Used to identify which bit positions are covered by parity bit $c_{2^k}$ under even parity.

CSMA/CD Minimum Frame / Maximum Distance Condition

T_t \ge 2 T_p \implies \frac{L}{B} \ge 2 \frac{d}{v}

Determining minimum frame size, maximum bus distance, or maximum transmission speed in Ethernet CSMA/CD networks.

Sliding Window Protocol Efficiency (with ACK delay)

\eta = \frac{W_S \times T_{t(\text{frame})}}{T_{t(\text{frame})} + 2 T_p + T_{t(\text{ack})}}

Finding link utilization $\eta$ or solving for sender window size $W_S$ given data rate, packet sizes, and round-trip propagation delay.

Selective Repeat Sequence Number Constraint

\text{Total Sequence Numbers } M \ge W_S + W_R = 2 W_S \implies k = \lceil \log_2(2 W_S) \rceil

Computing the minimum number of bits ( $k$ ) in the sequence number field for Selective Repeat ARQ.

Pure ALOHA Throughput

S = G e^{-2G}, \quad \text{where } G = \lambda \times T_{\text{fr}} = \lambda \times \frac{L}{B}

Calculating successfully transmitted frames per unit time under Poisson arrivals with rate $\lambda$ in Pure ALOHA.

Data Transmission Delay

T_{t,\text{data}} = \frac{L_{\text{data}}}{B_{\text{sender}}}

Used to compute the time required by the sender to put all bits of a data frame onto the link.

Acknowledgement Transmission Delay

T_{t,\text{ack}} = \frac{L_{\text{ack}}}{B_{\text{receiver}}}

Used when the acknowledgement frame size is non-negligible and receiver bandwidth is provided.

Total Cycle Time for Stop-and-Wait

T_{\text{total}} = T_{t,\text{data}} + 2 \cdot T_p + T_{t,\text{ack}} + T_{\text{proc}}

Used to calculate the complete elapsed time from the start of frame transmission until full receipt of the acknowledgement.

Sender Throughput

\text{Throughput} = \frac{L_{\text{data}}}{T_{\text{total}}}

Used to calculate useful data delivered per unit time (in bytes/sec or bits/sec).

CSMA/CD Collision Detection Condition

T_t \ge 2 \times T_p \implies \frac{L}{B} \ge 2 \times \frac{d}{v}

Used to find minimum frame length ( $L$ ), maximum distance ( $d$ ), bandwidth ( $B$ ), or propagation speed ( $v$ ) such that collisions are detected before transmission completes.

Propagation Delay

T_p = \frac{\text{Distance } (d)}{\text{Propagation Speed } (v)}

Used to calculate signal transit time over physical media (coaxial, twisted pair, optical fiber, or ring loops).

Transmission Delay

T_t = \frac{\text{Frame Size in bits } (L)}{\text{Bandwidth in bps } (B)}

Used to find the time needed to push all bits of a frame onto the transmission channel.

Token Ring Lost-Token Timeout

T_{\text{timeout}} = T_p + \sum_{i} T_{\text{hold}, i}

Used to determine the maximum round-trip delay a token can take around the ring before the monitoring station assumes loss.

Single Slot Success Probability (Heterogeneous Nodes)

P(\text{Success}) = \sum_{i=1}^{n} \left( P(S_i) \prod_{j e i} (1 - P(S_j)) \right)

Used in slotted ALOHA / synchronous slot models when nodes have distinct transmission probabilities $P(S_i)$ and exactly one node must transmit.

Binary Exponential Backoff Contention Range

R \in \{0, 1, 2, \dots, 2^k - 1\} \quad \text{where } k = \min(i, 10) \text{ on collision } i

Used to determine the random backoff multiplier range and evaluate the probability of collision on subsequent retransmissions.

Examiner traps in Data Link Layer

Unit mismatch: Failing to convert between bytes and bits (multiplying or dividing by 8) for frame size or bandwidth.
Metric prefixes: Confusing 1 kbps = 103 bps (networking convention) with 210 bps, or mixing milliseconds (10-3 s) with microseconds (10-6 s) and nanoseconds (10-9 s).
One-way vs. Round-Trip Time: Forgetting that total cycle time includes 2 Tp (round-trip propagation) rather than single Tp.
Useful vs. Total Transmission Time: Neglecting to subtract header/overhead bytes when computing useful transmission efficiency if distinct overheads are specified.
CRC 0-padding: Appending k zeros instead of (k - 1) zeros for a generator pattern of length k bits.
Confusing Selective Repeat sequence space (N 2Ws) with Go-Back-N sequence space (N Ws + 1).
Failing to ceil the continuous value of window size 1 + 2a to an integer before multiplying by 2 for Selective Repeat sequence space.
Unit conversion errors between bits and bytes (e.g., 1 KB = 1024 8 bits or 1000 8 bits) and milliseconds to seconds.
Confusing one-way propagation delay (Tp) with round-trip propagation time (RTT = 2Tp).
Misinterpreting polynomial degree: appending r+1 zeros instead of r zeros (where divisor length is r+1).
Omitting zero-coefficient terms when converting the polynomial to binary (e.g., mistaking X3 + X + 1 as 111 instead of 1011).
Using standard binary division with carry/borrow rather than bitwise XOR (modulo-2) division.
Stopping division prematurely or padding leading zeros incorrectly in the final r-bit remainder.
Appending the number of bits in the generator instead of its degree (e.g., appending 4 zeros for a 4-bit polynomial of degree 3).
Translating polynomials to bitstrings incorrectly by omitting zero coefficients (e.g., writing x3 + x + 1 as `111` instead of `1011`).
Confusing error-detection capability (d -1) with error-correction capability ( (d -1)/2 ).
Misidentifying bit index directions (1-based index vs 0-based, or LSB-to-MSB vs MSB-to-LSB) when setting up parity equations in Hamming codes.
Confusing bits vs. bytes when calculating Tt = L/B (e.g., 1 KB = 8192 bits or 8000 bits vs. 1 Kb).
Forgetting that Selective Repeat requires M 2 WS while Go-Back-N requires M WS + 1 when determining sequence bit field width.
Neglecting the factor of 2 in round-trip propagation time (2 Tp) or omitting non-zero ACK transmission time (Tt(ack)) when specified in the prompt.
Mixing up Pure ALOHA (e-2G) and Slotted ALOHA (e-G) exponents.
Destuffing error: removing zeros that were part of original payload instead of strictly removing a '0' only immediately following five consecutive '1's.
Neglecting acknowledgement transmission time (Tt,ack) by assuming ACKs are negligible in size.
Multiplying propagation delay only once instead of two-way round-trip (2 Tp).
Unit mismatch errors, such as confusing bits and bytes (e.g., 1000 bytes = 8000 bits) or standard metric conversions (1 Kbps = 1000 bps vs 1024 bps).
Reporting throughput in bits/second when the question explicitly requests bytes/second.
Confusing the broadcast MAC address at layer 2 with a broadcast IP address at layer 3 during ARP request framing.
Assuming the default gateway resolves or proxies MAC addresses for hosts located within the same local subnet.
Confusing the ARP request (broadcast) with the ARP reply (unicast).
Forgetting to multiply byte frame sizes by 8 when working with bandwidth in bps (1250 bytes = 10000 bits).
Confusing CSMA/CD with CSMA/CA: assuming RTS/CTS is used for collision detection rather than collision avoidance.
Omitting the factor of 2 in Tt 2 Tp (the round-trip propagation time required to hear a collision).
Off-by-one station counts in Token Ring when computing token holding time (whether to include N vs N-1 non-monitor stations).
Unit mismatch traps: confusing (10-6 s) with ms (10-3 s), and km/s with m/s.
Confusing the function of a jamming signal (alerting network to a collision) with frame padding (ensuring minimum frame length).
Assuming carrier sensing occurs only before transmission begins, overlooking that CSMA/CD must continuously sense while transmitting.
Believing a node completes sending its frame/packet even after collision detection occurs.

How questions are asked

Direct numerical calculation of link efficiency / utilization percentage
Finding minimum frame size or minimum window size for target efficiency
Bit-level modulo-2 XOR division for CRC remainder determination
Determining sequence number field bit-length under lifetime and utilization constraints
Qualitative comparative MCQ on link parameters (distance, bandwidth, frame size) vs. utilization
NAT calculation of header bit-fields based on physical and protocol link parameters
Compute the CRC checkbit sequence given a generator polynomial and binary message
Calculate transmitted codeword given message bits and CRC generator polynomial
Determine minimum distance and error bounds for a listed set of binary codewords
Solve for unknown bits in a Hamming codeword given a bit-position mapping table
NAT calculating minimum frame length, distance, or bandwidth under CSMA/CD
NAT calculating window size or sequence field bit-width for target sliding window utilization
NAT calculating throughput in frames/sec for Poisson-distributed ALOHA traffic
MCQ destuffing a given bit stream or identifying stuffed bit positions
MCQ statement verification regarding ARP/Ethernet frame header addressing
Numerical calculation of ARQ sender throughput or link efficiency given link characteristics
Conceptual scenario-based multiple-choice question on packet transmission and address resolution
Calculate minimum frame size in bytes given B and Tp (NAT)
Calculate signal speed in km/s given L, B, and d (MCQ/NAT)
Compute collision-free probability across heterogeneous slotted nodes (NAT)
Calculate monitor station timeout for token loss in Token Ring (NAT)
Identify TRUE/FALSE conceptual statements about IEEE 802.11 MAC features (MCQ/MSQ)
True/False protocol statement evaluation MCQ
Multi-Select conceptual validation (MSQ)

Paper trends

Questions have evolved from basic Stop-and-Wait formulas to realistic multi-parameter accounting (considering ACK transmission time, processing delay, data vs. overhead bytes) and dual-constraint window/sequence number design problems.
2026, 2017, 2015
High prevalence of numerical answer type (NAT) and 2-mark computational MCQs that test unit conversions (e.g., bits vs. bytes, kbps vs. bps, nanoseconds per meter).
2026, 2025, 2017, 2015
Emphasis is placed on end-to-end exact integer calculation formatted as Numerical Answer Type (NAT), ensuring candidates understand ceil operations at discrete window sizing and bit-allocation stages.
2016
Direct calculation of CRC checkbits via polynomial division has appeared as a high-weightage 2-mark MCQ requiring careful step-by-step XOR arithmetic.
2021
Questions consistently carry 2 marks and assess step-by-step bitwise mechanics rather than pure qualitative definitions.
2021, 2017
Testing shifted from classic CRC and code distance evaluations (2017) to structured tabular verification of Hamming parity bit relationships (2021).
2021, 2017
Shift from simple multiple-choice calculation questions to NAT questions requiring precise arithmetic (e.g., fractional window sizing rounded to nearest integer, exponential throughput evaluations).
2024, 2021, 2014
Increased precision in sliding window problems, explicitly providing finite ACK transmission frame lengths rather than assuming ACK transmission time is zero.
2021
GATE tests precise multi-component round-trip timing by explicitly specifying non-negligible acknowledgement sizes and receiver transmission rates rather than assuming instantaneous ACKs.
2016
Focuses on conceptual understanding of link-layer framing and broadcast mechanisms (MAC broadcast vs. IP broadcast and direct host vs. gateway involvement).
2019
Transition from direct calculation of protocol limits (Token Ring in 2014) to standard Ethernet CSMA/CD collision-detection constraints and probability-based slotted ALOHA success rates in 2015-2016.
2016, 2015, 2014
High prevalence of 2-mark NAT questions requiring multi-step arithmetic, precise unit conversions (bits to bytes, seconds to microseconds, meters to kilometers), and edge tolerance consideration.
2016, 2015, 2014
Direct conceptual 1-mark MCQs test precise protocol mechanics (CSMA/CD operational rules) rather than purely numerical calculations.
2016

Difficulty notes

Easy questions ask for direct application of $\eta = 1/(1+2a)$ or qualitative relationships with negligible overheads (1 mark MCQ or standard 2 mark NAT). Medium questions incorporate multiple real-world parameters (ACK frame size, processing delay, header overheads) or multi-step logic combining wrap-around time constraints and BDP for sequence number sizing (2 mark NAT or MCQ). Hard questions (rare) combine packet error rates, retransmission timeouts, and asymmetric sliding windows.

Data Link Layer

27 Qs · since 2013 · 49 marks · 1.9 marks/paperMedium yield

Take topic test

Medium Access Control (MAC) in GATE CS is predominantly tested through quantitative numerical problems and conceptual protocol comparisons. The focus is split between random access… Guide

Type

Topic guide

What does GATE test in Data Link Layer?

Core concepts

Stop-and-Wait Protocol and ARQ efficiency
Sliding Window Protocols (Go-Back-N, Selective Repeat)
Bandwidth-Delay Product (BDP) and Channel Utilization
Sequence Number Field sizing and wrap-around time constraints
Error Detection using Cyclic Redundancy Check (CRC) modulo-2 division
Transmission delay vs. Propagation delay vs. Processing delay trade-offs
Selective Repeat (SR) ARQ Mechanics
Propagation Delay (Tp) vs Transmission Time (Tt)
Link Utilization and Efficiency ( )
Window Sizing (Ws, Wr)
Sequence Number Space Sizing (2k Ws + Wr)
Cyclic Redundancy Check (CRC) mechanism
Generator polynomial degree and binary bit representation
Appending r zero bits for a degree-r polynomial
Modulo-2 arithmetic (bitwise XOR division)
Codeword construction (M R)
Modulo-2 arithmetic and polynomial division over GF(2)
Cyclic Redundancy Check (CRC) generator polynomial encoding and check-bit calculation
Pairwise Hamming distance and minimum Hamming distance (d )
Error-detecting vs error-correcting capability trade-offs
Hamming Code structure, power-of-two check bit placement, and parity equations
CSMA/CD collision detection constraint (Tt 2 Tp)
Sliding Window Protocols (Stop-and-Wait, Go-Back-N, Selective Repeat)
Window sizing vs. sequence number space requirements (WS + WR 2k)
Bit-stuffing and bit-destuffing algorithms (e.g., HDLC 5 consecutive 1s rule)
ARP Request (Broadcast MAC) and ARP Reply (Unicast MAC) addressing
Pure ALOHA vs Slotted ALOHA throughput and vulnerable time periods
Stop-and-Wait ARQ protocol timing
Transmission delay vs Propagation delay
Acknowledgement transmission overhead (Tt,ack)
Asymmetric bandwidth rates (Sender vs Receiver)
Throughput calculation in bytes per second
Address Resolution Protocol (ARP) Request and Reply mechanics
Ethernet broadcast MAC address (FF:FF:FF:FF:FF:FF)
Intra-subnet vs. Inter-subnet communication (Direct delivery vs. Default Gateway)
Data Link Layer frame encapsulation of Network Layer packets
CSMA/CD collision detection principle (Tt 2 Tp)
Slotted ALOHA collision and success probability modeling
Token Ring propagation delay, station holding time, and monitor station duties
IEEE 802.11 CSMA/CA mechanism and why CD fails in wireless
RTS/CTS mechanism for hidden terminal problem / collision avoidance
Link-layer ACK requirement for wireless unicast frames
Non-overlapping channel allocation in IEEE 802.11 (e.g. 1, 6, 11 in 2.4 GHz)
Carrier Sense Multiple Access with Collision Detection (CSMA/CD)
Continuous channel sensing during transmission
Jamming signal function vs. Frame padding
Immediate transmission abortion upon collision
Binary Exponential Backoff algorithm and collision probability reduction

Recurring question patterns

Stop-and-Wait Protocol Efficiency and Parameter Sizing
common · mixed · 2 marks · 2025, 2017, 2015
Calculations involving link utilization $\eta = \frac{T_t}{T_{\text{total}}}$ , determining minimum frame size for target utilization, or finding efficiency with detailed parameters including ACK transmission time, processing overheads, and packet headers.
Sliding Window Sizing and Sequence Number Constraints
common · mixed · 2 marks · 2026
Calculating optimal sender window size $W = 1 + 2a$ for 100% link utilization, or determining the sequence number bit width $N$ under dual constraints of maximum link utilization and sequence number wrap-around time.
Cyclic Redundancy Check (CRC) Modulo-2 Division
occasional · MCQ · 2 marks · 2026
Given a data bit sequence and a generator polynomial bit pattern of length $k$ , finding the $(k-1)$ -bit CRC remainder appended to the frame by performing XOR-based modulo-2 division.
Qualitative Analysis of Protocol Utilization
occasional · MCQ · 1 marks · 2023
Identifying the relationship between protocol efficiency $\eta = \frac{1}{1 + 2a}$ and physical parameters like link distance, bandwidth, frame size, and propagation velocity.
Sequence Number Field Sizing for Sliding Window Protocols
occasional · NAT · 2 marks · 2016
Given channel bandwidth, one-way propagation delay, frame length, and protocol type (e.g., Selective Repeat), compute the frame transmission time, required sender window size for target link utilization (often 100%), total sequence number space size ( $W_s + W_r$ ), and the minimum number of sequence number bits required.
CRC Remainder / Checkbit Calculation
common · MCQ · 2 marks · 2021
Given a generator polynomial $G(X)$ of degree $r$ and a binary data word / message $M$ , calculate the $r$ -bit CRC code (remainder) generated by modulo-2 polynomial division of $(M \cdot 2^r)$ by $G(X)$ .
CRC Transmitted Codeword Computation
common · MCQ · 2 marks · 2017
Given a generator polynomial over GF(2) and a binary information bit sequence, append r zeros (where r is the degree of the polynomial), perform modulo-2 binary division (XOR), and append the remainder to form the transmitted codeword.
Minimum Hamming Distance and Error Bounds
occasional · MCQ · 2 marks · 2017
Given a finite set of binary codewords, compute all pairwise Hamming distances to find the minimum distance $d_{\min}$ , and determine the error detection ( $e$ ) and error correction ( $q$ ) limits.
Hamming Code Parity and Bit Reconstruction
occasional · MCQ · 2 marks · 2021
Given a Hamming code layout with check bits at powers-of-two positions and partial data/check bit assignments, formulate even/odd parity equations to solve for unknown bit values.
CSMA/CD Collision Detection Limit Calculation
common · mixed · 2 marks · 2024, 2013
Given three of the four parameters (bandwidth $B$ , segment length $d$ , propagation velocity $v$ , frame size $L$ ), calculate the missing critical threshold using the fundamental collision detection condition $T_t \ge 2 T_p$ .
Sliding Window Protocol Efficiency and Sequence Sizing
common · NAT · 2 marks · 2021, 2014
Calculate sender window size, total cycle time (including data transmission, round-trip propagation, and optionally ACK transmission delay), or the minimum sequence number field bits required for Go-Back-N or Selective Repeat to achieve a target link utilization.
Random Access Throughput (ALOHA)
occasional · NAT · 2 marks · 2021
Compute the offered load $G = \lambda \times T_{\text{fr}}$ from aggregate Poisson arrival rates and frame transmission time, and evaluate network throughput using the success probability models of Pure or Slotted ALOHA.
Framing Mechanics and Link Layer Addressing
occasional · MCQ · 1 marks · 2021, 2014
Evaluate exact bit/byte stuffing and destuffing patterns given standard flag delimiters (such as 01111110), or determine the unicast vs. broadcast addressing nature of control frames like ARP request/reply.
Stop-and-Wait ARQ Throughput Calculation with ACK Transmission Delay
common · NAT · 2 marks · 2016
Given frame size, sender transmission rate, ACK packet size, receiver transmission rate, and one-way propagation delay, calculate total cycle time and resulting throughput in bytes/second or bps.
Intra-Subnet Address Resolution (ARP over Ethernet)
occasional · MCQ · 2 marks · 2019
Questions asking how a source host resolves the MAC address of a destination host within the same local subnet using ARP broadcast at the Data Link layer.
CSMA/CD Minimum Frame Size & Timing Constraint
common · NAT · 2 marks · 2016, 2015
Given bandwidth, distance/propagation delay, and signal speed or frame size, use the fundamental CSMA/CD constraint $T_t \ge 2 \times T_p$ to calculate the missing parameter (minimum frame size in bytes, signal speed in km/s, or maximum cable length).
Discrete Slot Collision and Success Probability
occasional · NAT · 2 marks · 2015
Calculate the probability that exactly one node transmits successfully in a given time slot without collision, given independent transmission/frame generation probabilities for each node in a slotted LAN environment.
Token Ring Maximum Cycle Time & Timer Limits
occasional · NAT · 2 marks · 2014
Compute the total ring latency and token timer threshold before a monitor station declares the token lost, by summing total ring propagation delay and cumulative token holding times across stations.
Wireless MAC (IEEE 802.11) Protocol Properties
occasional · MCQ · 2 marks · 2016
Conceptual multi-statement evaluation regarding IEEE 802.11 wireless LAN characteristics, including CSMA/CA vs. CSMA/CD, RTS/CTS virtual carrier sensing, non-overlapping 2.4 GHz channels, and unicast ACK requirements.
Conceptual Statement Evaluation of CSMA/CD Protocols
common · MCQ · 1 marks · 2016
Questions present four statements describing operations of the MAC sublayer in Ethernet (such as continuous sensing, collision abortion, jamming signal usage, or backoff window expansion) and ask to identify the TRUE/FALSE statement.

Formulas GATE uses

Transmission Time and Propagation Delay

T_t = \frac{L}{B}, \quad T_p = \frac{d}{v}

Used to compute data/ACK packet transmission times and one-way propagation delays from frame length $L$ , bandwidth $B$ , distance $d$ , and signal speed $v$ .

Stop-and-Wait Efficiency (Standard / Ideal)

\eta = \frac{T_t}{T_t + 2T_p} = \frac{1}{1 + 2a}, \quad \text{where } a = \frac{T_p}{T_t}

Used when processing delay and ACK transmission time are negligible.

Stop-and-Wait ARQ Efficiency (Detailed with Overheads)

\eta = \frac{T_{\text{useful}}}{T_t + 2T_p + T_{\text{proc}} + T_{\text{ack}}}

Used when ACK size, node processing time, or header/payload byte separations are explicitly specified.

Sliding Window Optimal Window Size for 100% Utilization

W \ge 1 + 2a = 1 + 2\left(\frac{T_p}{T_t}\right)

Used to find the minimum sender window size $W$ (in frames) needed to achieve full link utilization.

Sequence Number Space and Wrap-around Time

$2^N \ge \text{Bandwidth (bytes/s)} \times T_{\text{wrap-around}}$ and $2^N \ge W_s + W_r$

Used when determining the minimum sequence number bits $N$ under maximum throughput and lifetime/wrap-around constraints.

CRC Modulo-2 Arithmetic

\text{Appended Bits} = (k - 1) \text{ zeros}, \quad \text{Remainder} = (\text{Data} \cdot 2^{k-1}) \pmod_2 G

Used to compute CRC checksum/FCS bits for an error-detecting generator $G$ of length $k$ .

Frame Transmission Time

T_t = \frac{L}{B}

Used to find the time taken to transmit a data frame of size $L$ over a link of bandwidth $B$ .

Normalized Propagation Delay (a-parameter)

a = \frac{T_p}{T_t}

Used to relate one-way propagation delay $T_p$ to packet transmission delay $T_t$ .

Sliding Window Utilization and Sender Window Size

\eta = \frac{W_s}{1 + 2a} \implies W_s = \lceil 1 + 2a \rceil \quad (\text{for } \eta = 1)

Used to find the minimum integer sender window size $W_s$ required to achieve 100% link utilization.

Selective Repeat Sequence Number Space

N \ge W_s + W_r = 2 W_s

Used to calculate the minimum distinct sequence numbers required in Selective Repeat where $W_r = W_s$ .

Sequence Number Bits Requirement

k = \lceil \log_2 N \rceil

Used to determine the minimum number of bits $k$ allocated in the frame header for the sequence number field.

Polynomial to Binary Generator Divisor Mapping

G(X) = \sum_{i=0}^{r} g_i X^i \implies G = g_r g_{r-1} \dots g_0

Converting a given generator polynomial of degree $r$ into an $(r+1)$ -bit binary divisor.

Augmented Message Construction

M^{\prime}(X) = M(X) \cdot X^r

Appending $r$ zeros to the right of an $n$ -bit message before executing modulo-2 division.

Modulo-2 CRC Remainder Relation

M^{\prime}(X) = Q(X) \cdot G(X) \oplus R(X) \quad \text{where } \deg(R(X)) < r

Finding the $r$ -bit remainder $R$ that serves as the CRC checkbit sequence appended to form the transmitted codeword.

Error-Correcting Capability Bound

d_{\min} \ge 2q + 1 \implies q = \left\lfloor \frac{d_{\min} - 1}{2} \right\rfloor

Used to compute the maximum number of erroneous bits $q$ that a block code with minimum distance $d_{\min}$ can correct.

Error-Detecting Capability Bound

d_{\min} \ge e + 1 \implies e = d_{\min} - 1

Used to compute the maximum number of error bits $e$ guaranteed to be detected.

CRC Appended Zero Count

r = \deg(G(x))

Determines the number of zero bits appended to the message before polynomial division, where $G(x)$ is the generator polynomial.

Hamming Parity Coverage Rule

c_{2^k} = \bigoplus \{ b_i \mid \text{the } k\text{-th bit of binary index } i \text{ is } 1 \}

Used to identify which bit positions are covered by parity bit $c_{2^k}$ under even parity.

CSMA/CD Minimum Frame / Maximum Distance Condition

T_t \ge 2 T_p \implies \frac{L}{B} \ge 2 \frac{d}{v}

Determining minimum frame size, maximum bus distance, or maximum transmission speed in Ethernet CSMA/CD networks.

Sliding Window Protocol Efficiency (with ACK delay)

\eta = \frac{W_S \times T_{t(\text{frame})}}{T_{t(\text{frame})} + 2 T_p + T_{t(\text{ack})}}

Finding link utilization $\eta$ or solving for sender window size $W_S$ given data rate, packet sizes, and round-trip propagation delay.

Selective Repeat Sequence Number Constraint

\text{Total Sequence Numbers } M \ge W_S + W_R = 2 W_S \implies k = \lceil \log_2(2 W_S) \rceil

Computing the minimum number of bits ( $k$ ) in the sequence number field for Selective Repeat ARQ.

Pure ALOHA Throughput

S = G e^{-2G}, \quad \text{where } G = \lambda \times T_{\text{fr}} = \lambda \times \frac{L}{B}

Calculating successfully transmitted frames per unit time under Poisson arrivals with rate $\lambda$ in Pure ALOHA.

Data Transmission Delay

T_{t,\text{data}} = \frac{L_{\text{data}}}{B_{\text{sender}}}

Used to compute the time required by the sender to put all bits of a data frame onto the link.

Acknowledgement Transmission Delay

T_{t,\text{ack}} = \frac{L_{\text{ack}}}{B_{\text{receiver}}}

Used when the acknowledgement frame size is non-negligible and receiver bandwidth is provided.

Total Cycle Time for Stop-and-Wait

T_{\text{total}} = T_{t,\text{data}} + 2 \cdot T_p + T_{t,\text{ack}} + T_{\text{proc}}

Used to calculate the complete elapsed time from the start of frame transmission until full receipt of the acknowledgement.

Sender Throughput

\text{Throughput} = \frac{L_{\text{data}}}{T_{\text{total}}}

Used to calculate useful data delivered per unit time (in bytes/sec or bits/sec).

CSMA/CD Collision Detection Condition

T_t \ge 2 \times T_p \implies \frac{L}{B} \ge 2 \times \frac{d}{v}

Used to find minimum frame length ( $L$ ), maximum distance ( $d$ ), bandwidth ( $B$ ), or propagation speed ( $v$ ) such that collisions are detected before transmission completes.

Propagation Delay

T_p = \frac{\text{Distance } (d)}{\text{Propagation Speed } (v)}

Used to calculate signal transit time over physical media (coaxial, twisted pair, optical fiber, or ring loops).

Transmission Delay

T_t = \frac{\text{Frame Size in bits } (L)}{\text{Bandwidth in bps } (B)}

Used to find the time needed to push all bits of a frame onto the transmission channel.

Token Ring Lost-Token Timeout

T_{\text{timeout}} = T_p + \sum_{i} T_{\text{hold}, i}

Used to determine the maximum round-trip delay a token can take around the ring before the monitoring station assumes loss.

Single Slot Success Probability (Heterogeneous Nodes)

P(\text{Success}) = \sum_{i=1}^{n} \left( P(S_i) \prod_{j e i} (1 - P(S_j)) \right)

Used in slotted ALOHA / synchronous slot models when nodes have distinct transmission probabilities $P(S_i)$ and exactly one node must transmit.

Binary Exponential Backoff Contention Range

R \in \{0, 1, 2, \dots, 2^k - 1\} \quad \text{where } k = \min(i, 10) \text{ on collision } i

Used to determine the random backoff multiplier range and evaluate the probability of collision on subsequent retransmissions.

Examiner traps in Data Link Layer

Unit mismatch: Failing to convert between bytes and bits (multiplying or dividing by 8) for frame size or bandwidth.
Metric prefixes: Confusing 1 kbps = 103 bps (networking convention) with 210 bps, or mixing milliseconds (10-3 s) with microseconds (10-6 s) and nanoseconds (10-9 s).
One-way vs. Round-Trip Time: Forgetting that total cycle time includes 2 Tp (round-trip propagation) rather than single Tp.
Useful vs. Total Transmission Time: Neglecting to subtract header/overhead bytes when computing useful transmission efficiency if distinct overheads are specified.
CRC 0-padding: Appending k zeros instead of (k - 1) zeros for a generator pattern of length k bits.
Confusing Selective Repeat sequence space (N 2Ws) with Go-Back-N sequence space (N Ws + 1).
Failing to ceil the continuous value of window size 1 + 2a to an integer before multiplying by 2 for Selective Repeat sequence space.
Unit conversion errors between bits and bytes (e.g., 1 KB = 1024 8 bits or 1000 8 bits) and milliseconds to seconds.
Confusing one-way propagation delay (Tp) with round-trip propagation time (RTT = 2Tp).
Misinterpreting polynomial degree: appending r+1 zeros instead of r zeros (where divisor length is r+1).
Omitting zero-coefficient terms when converting the polynomial to binary (e.g., mistaking X3 + X + 1 as 111 instead of 1011).
Using standard binary division with carry/borrow rather than bitwise XOR (modulo-2) division.
Stopping division prematurely or padding leading zeros incorrectly in the final r-bit remainder.
Appending the number of bits in the generator instead of its degree (e.g., appending 4 zeros for a 4-bit polynomial of degree 3).
Translating polynomials to bitstrings incorrectly by omitting zero coefficients (e.g., writing x3 + x + 1 as `111` instead of `1011`).
Confusing error-detection capability (d -1) with error-correction capability ( (d -1)/2 ).
Misidentifying bit index directions (1-based index vs 0-based, or LSB-to-MSB vs MSB-to-LSB) when setting up parity equations in Hamming codes.
Confusing bits vs. bytes when calculating Tt = L/B (e.g., 1 KB = 8192 bits or 8000 bits vs. 1 Kb).
Forgetting that Selective Repeat requires M 2 WS while Go-Back-N requires M WS + 1 when determining sequence bit field width.
Neglecting the factor of 2 in round-trip propagation time (2 Tp) or omitting non-zero ACK transmission time (Tt(ack)) when specified in the prompt.
Mixing up Pure ALOHA (e-2G) and Slotted ALOHA (e-G) exponents.
Destuffing error: removing zeros that were part of original payload instead of strictly removing a '0' only immediately following five consecutive '1's.
Neglecting acknowledgement transmission time (Tt,ack) by assuming ACKs are negligible in size.
Multiplying propagation delay only once instead of two-way round-trip (2 Tp).
Unit mismatch errors, such as confusing bits and bytes (e.g., 1000 bytes = 8000 bits) or standard metric conversions (1 Kbps = 1000 bps vs 1024 bps).
Reporting throughput in bits/second when the question explicitly requests bytes/second.
Confusing the broadcast MAC address at layer 2 with a broadcast IP address at layer 3 during ARP request framing.
Assuming the default gateway resolves or proxies MAC addresses for hosts located within the same local subnet.
Confusing the ARP request (broadcast) with the ARP reply (unicast).
Forgetting to multiply byte frame sizes by 8 when working with bandwidth in bps (1250 bytes = 10000 bits).
Confusing CSMA/CD with CSMA/CA: assuming RTS/CTS is used for collision detection rather than collision avoidance.
Omitting the factor of 2 in Tt 2 Tp (the round-trip propagation time required to hear a collision).
Off-by-one station counts in Token Ring when computing token holding time (whether to include N vs N-1 non-monitor stations).
Unit mismatch traps: confusing (10-6 s) with ms (10-3 s), and km/s with m/s.
Confusing the function of a jamming signal (alerting network to a collision) with frame padding (ensuring minimum frame length).
Assuming carrier sensing occurs only before transmission begins, overlooking that CSMA/CD must continuously sense while transmitting.
Believing a node completes sending its frame/packet even after collision detection occurs.

How questions are asked

Direct numerical calculation of link efficiency / utilization percentage
Finding minimum frame size or minimum window size for target efficiency
Bit-level modulo-2 XOR division for CRC remainder determination
Determining sequence number field bit-length under lifetime and utilization constraints
Qualitative comparative MCQ on link parameters (distance, bandwidth, frame size) vs. utilization
NAT calculation of header bit-fields based on physical and protocol link parameters
Compute the CRC checkbit sequence given a generator polynomial and binary message
Calculate transmitted codeword given message bits and CRC generator polynomial
Determine minimum distance and error bounds for a listed set of binary codewords
Solve for unknown bits in a Hamming codeword given a bit-position mapping table
NAT calculating minimum frame length, distance, or bandwidth under CSMA/CD
NAT calculating window size or sequence field bit-width for target sliding window utilization
NAT calculating throughput in frames/sec for Poisson-distributed ALOHA traffic
MCQ destuffing a given bit stream or identifying stuffed bit positions
MCQ statement verification regarding ARP/Ethernet frame header addressing
Numerical calculation of ARQ sender throughput or link efficiency given link characteristics
Conceptual scenario-based multiple-choice question on packet transmission and address resolution
Calculate minimum frame size in bytes given B and Tp (NAT)
Calculate signal speed in km/s given L, B, and d (MCQ/NAT)
Compute collision-free probability across heterogeneous slotted nodes (NAT)
Calculate monitor station timeout for token loss in Token Ring (NAT)
Identify TRUE/FALSE conceptual statements about IEEE 802.11 MAC features (MCQ/MSQ)
True/False protocol statement evaluation MCQ
Multi-Select conceptual validation (MSQ)

Paper trends

Questions have evolved from basic Stop-and-Wait formulas to realistic multi-parameter accounting (considering ACK transmission time, processing delay, data vs. overhead bytes) and dual-constraint window/sequence number design problems.
2026, 2017, 2015
High prevalence of numerical answer type (NAT) and 2-mark computational MCQs that test unit conversions (e.g., bits vs. bytes, kbps vs. bps, nanoseconds per meter).
2026, 2025, 2017, 2015
Emphasis is placed on end-to-end exact integer calculation formatted as Numerical Answer Type (NAT), ensuring candidates understand ceil operations at discrete window sizing and bit-allocation stages.
2016
Direct calculation of CRC checkbits via polynomial division has appeared as a high-weightage 2-mark MCQ requiring careful step-by-step XOR arithmetic.
2021
Questions consistently carry 2 marks and assess step-by-step bitwise mechanics rather than pure qualitative definitions.
2021, 2017
Testing shifted from classic CRC and code distance evaluations (2017) to structured tabular verification of Hamming parity bit relationships (2021).
2021, 2017
Shift from simple multiple-choice calculation questions to NAT questions requiring precise arithmetic (e.g., fractional window sizing rounded to nearest integer, exponential throughput evaluations).
2024, 2021, 2014
Increased precision in sliding window problems, explicitly providing finite ACK transmission frame lengths rather than assuming ACK transmission time is zero.
2021
GATE tests precise multi-component round-trip timing by explicitly specifying non-negligible acknowledgement sizes and receiver transmission rates rather than assuming instantaneous ACKs.
2016
Focuses on conceptual understanding of link-layer framing and broadcast mechanisms (MAC broadcast vs. IP broadcast and direct host vs. gateway involvement).
2019
Transition from direct calculation of protocol limits (Token Ring in 2014) to standard Ethernet CSMA/CD collision-detection constraints and probability-based slotted ALOHA success rates in 2015-2016.
2016, 2015, 2014
High prevalence of 2-mark NAT questions requiring multi-step arithmetic, precise unit conversions (bits to bytes, seconds to microseconds, meters to kilometers), and edge tolerance consideration.
2016, 2015, 2014
Direct conceptual 1-mark MCQs test precise protocol mechanics (CSMA/CD operational rules) rather than purely numerical calculations.
2016