GATE CS

Data link layer

Error detection, medium access control and Ethernet

The data link layer moves frames reliably across one link or one shared network. This topic covers framing, error detection and correction (parity, checksum, CRC, Hamming), how stations share a medium (ALOHA, CSMA, CSMA/CD, token passing), and Ethernet with its switches and bridges. Typical questions ask for a quick numerical result: a CRC remainder, a throughput, a minimum frame size, a count of collision domains.

3 previous-year questions · 3 solved · 5 practice questions

Framing and error-control basics

The data link layer cuts the bit stream into frames so the receiver can tell where each one starts and ends. A frame carries a header, the payload and a trailer holding the error-detecting code. Conventions used throughout: 1 byte = 8 bits, and data rates use kilo = $1 0^{3}$ and mega = $1 0^{6}$ (1 Mbps = $1 0^{6}$ bits/s) unless a question says otherwise.

Method	Flag / marker	Sender's rule	Receiver's rule
Byte stuffing	A flag byte marks each frame boundary	Put an escape byte (ESC) before any flag byte or ESC byte that occurs in the data	Remove each ESC and keep the byte after it as data
Bit stuffing	Flag `01111110`	After five consecutive 1s in the data, insert a 0	After five consecutive 1s, delete the 0 that follows

Bit stuffing example: the data 0111111011111 (13 bits) is sent as 011111010111110 (15 bits). A 0 goes in after the first five 1s (the sixth 1 follows it), and another after the final run of five 1s. The count of consecutive 1s starts again after every stuffed 0. Stuffing makes the frame longer, so when a question asks for the transmitted length, count the inserted bits.

The Hamming distance between two codewords of equal length is the number of positions in which they differ. The minimum distance $d$ of a code is the smallest distance between any two distinct codewords. It decides how many errors the code can handle.

DETECTION WITH MINIMUM DISTANCE D

errors always detected = d - 1

A code of minimum distance d detects every pattern of up to d - 1 bit errors.

CORRECTION WITH MINIMUM DISTANCE D

errors always corrected = ⌊ \frac{d - 1}{2} ⌋

Decoding to the nearest codeword corrects up to this many bit errors.

EXAM TIP

To detect s errors and correct t errors at the same time (t <= s), the code needs d >= s + t + 1. Detecting d - 1 errors and correcting floor((d - 1)/2) errors are two separate guarantees. A code gives both at once only if this condition holds.

Error detection: parity, checksum and CRC

Single parity bit: one extra bit makes the number of 1s even (even parity) or odd (odd parity). It detects every odd number of bit errors and misses every even number.
Two-dimensional parity: arrange the data in rows, add a parity bit to each row and a parity row for the columns. It detects all 1-, 2- and 3-bit errors. A single-bit error shows up in one failing row and one failing column, so it can be corrected. Some 4-bit errors are missed: four flips at the corners of a rectangle leave every row and column parity unchanged.
Internet checksum: split the data into 16-bit words and add them in one's complement arithmetic (a carry out of the top bit is added back at the bottom). The checksum is the complement of that sum. The receiver adds all the words, checksum included. If no error is seen, the result is all 1s (0xFFFF).

CRC (cyclic redundancy check). Treat the data as a polynomial over GF(2): arithmetic is mod 2, so addition and subtraction are both XOR. Let the generator $G (x)$ have degree $r$ , so it has $r + 1$ bits. The sender appends $r$ zeros to the data, divides by the generator using modulo-2 division, and replaces those zeros with the $r$ -bit remainder. The frame sent is then exactly divisible by the generator. The receiver divides the received frame by $G$ and accepts it only if the remainder is zero. The length of a burst error is the number of bit positions from the first flipped bit to the last, both included.

CRC FRAME LENGTH

n = m + r, r = de g G (x)

m data bits plus an r-bit remainder give an n-bit frame; the generator has r + 1 bits.

Error pattern	Detected by a CRC whose generator has...
Any single-bit error	Two or more terms
Any burst of length <= r	Degree r with constant term 1 (always detected)
A burst of length r + 1	Degree r with constant term 1: all are detected except a fraction 2^(-(r-1))
A burst longer than r + 1	Degree r with constant term 1: all are detected except a fraction 2^(-r)
Any odd number of bit errors	(x + 1) as a factor of G(x)
Any double-bit error	A G(x) that divides x^k + 1 for no k from 1 to n - 1 (n = frame length). A primitive polynomial of degree r works for frames of up to 2^r - 1 bits.

WORKED EXAMPLE

Find the CRC remainder for data 1101011 with generator 1011 (that is, $x^{3} + x + 1$ ), and write the transmitted frame.

Solution

The generator has 4 bits, so r = 3. Append three zeros: 1101011000.
Divide by 1011. Each step looks at 4 bits: XOR with 1011 if the leading bit is 1, otherwise just shift. First four bits: 1101 XOR 1011 = 0110, so the running remainder is 110.
Bring down the next bit (0): 1100 XOR 1011 = 0111, remainder 111.
Bring down 1: 1111 XOR 1011 = 0100, remainder 100.
Bring down 1: 1001 XOR 1011 = 0010, remainder 010.
Bring down 0: 0100 starts with 0, so no XOR; remainder 100. Bring down 0: 1000 XOR 1011 = 0011, remainder 011. Bring down the last 0: 0110 starts with 0; remainder 110.
The remainder is 110, so the frame sent is 1101011 followed by 110. Check: dividing 1101011110 by 1011 leaves remainder 0.

Answer: Remainder 110; transmitted frame 1101011110.

EXAM TIP

The remainder always has exactly r bits, so keep any leading zeros (a remainder of 1 with r = 3 is written 001). A CRC only detects errors; it does not correct them.

Hamming codes

A Hamming code adds $r$ check bits to $m$ data bits so that any single-bit error can be located and corrected. The $r$ check bits must be able to name any one of the $m + r$ bit positions, or report that there is no error.

NUMBER OF HAMMING CHECK BITS

2^{r} \geq m + r + 1

The smallest r for which the syndrome can point to any single-bit error in an (m + r)-bit codeword.

Number the codeword positions 1, 2, 3, ... from the left. Positions that are powers of two (1, 2, 4, 8, ...) hold check bits; all other positions hold data bits.
The check bit at position $2^{i}$ covers every position whose binary index has bit $i$ set, itself included. It is set so that the number of 1s across those positions is even (use odd parity only if the question says so).
At the receiver, recompute each of these parity checks. Write the results as a binary number, 1 for a failed check, with the position-1 check as the lowest bit. This syndrome is the position of the wrong bit; a syndrome of 0 means there is no single-bit error.
Flip the bit at the syndrome position to correct it.

Example sizes: 4 data bits need r = 3, giving the (7,4) code ( $2^{3} = 8 \geq 8$ ); 11 data bits need r = 4 ( $16 \geq 16$ ). A basic Hamming code has minimum distance 3, so it can correct one error or detect two, but not both. Adding one overall parity bit raises the distance to 4, which gives single-error correction with double-error detection.

Medium access control: ALOHA and CSMA

On a shared channel, the MAC sublayer decides who may transmit. Let $T$ (also written $T_{t}$ ) be the frame transmission time, frame length divided by bandwidth. Let $G$ be the mean number of transmission attempts per frame time, new frames and retransmissions together. Arrivals are assumed to be Poisson.

TRANSMISSION TIME AND THE RATIO A

T_{t} = \frac{L}{B}, a = \frac{T _{p}}{T _{t}}

L = frame length in bits, B = bandwidth in bits per second, T_p = one-way propagation delay. A small a means a station hears another's frame early in its transmission, so carrier sensing works well.

Protocol	Rule	Vulnerable period	Throughput S
Pure ALOHA	Send whenever a frame is ready	2T	G e^{-2G}, maximum 1/(2e) ≈ 0.184 at G = 0.5
Slotted ALOHA	Send only at the start of a time slot (slot = T)	T	G e^{-G}, maximum 1/e ≈ 0.368 at G = 1

PURE ALOHA THROUGHPUT

S = G e^{- 2 G}

S is the fraction of time that carries a successful frame; the maximum is about 18.4% at G = 0.5.

SLOTTED ALOHA THROUGHPUT

S = G e^{- G}

The maximum is about 36.8% at G = 1.

CSMA (carrier sense multiple access) cuts collisions by listening before sending. Collisions still happen because signals take time to travel: a station can find the channel idle just before another station's signal reaches it. The variants:

Variant	Channel idle	Channel busy
1-persistent	Send at once (probability 1)	Keep sensing; send as soon as the channel becomes idle
Non-persistent	Send at once	Wait a random time, then sense again
p-persistent (slotted channels)	Send with probability p; otherwise wait for the next slot and repeat. If that slot is busy, act as after a collision (wait a random time and start again)	Wait for the next slot and sense again

CSMA/CD and token passing

CSMA/CD adds collision detection. A station keeps listening while it sends; when it detects a collision it stops at once and sends a short jam signal so that every station notices. The collision must be detected before the sender finishes the frame, so the frame must last at least one round-trip time. Otherwise the sender could finish and wrongly believe the frame got through.

MINIMUM FRAME SIZE FOR CSMA/CD

L \geq 2 T_{p} B

L = frame length in bits, T_p = one-way propagation delay (distance divided by propagation speed), B = bandwidth in bits per second. Put another way, the transmission time must be at least 2 T_p.

WORKED EXAMPLE

A CSMA/CD bus runs at 20 Mbps (take 1 Mbps = $1 0^{6}$ bits/s). The cable is 1.5 km long and signals travel at $2 \times 1 0^{8}$ m/s. Ignore repeater delays and the jam signal. What is the minimum frame size in bits and in bytes?

Solution

One-way propagation delay: $T_{p} = 1500/ (2 \times 1 0^{8}) = 7.5 μ s$ .
Round trip: $2 T_{p} = 15 μ s$ .
Minimum frame: $L = 2 T_{p} B = 15 \times 1 0^{- 6} \times 20 \times 1 0^{6} = 300$ bits.
In bytes: $300/8 = 37.5$ , so a frame made of whole bytes needs 38 bytes (304 bits).

Answer: At least 300 bits, which is 37.5 bytes (38 whole bytes).

Binary exponential backoff. After the $i$ -th collision in a row for the same frame, the station picks an integer $K$ uniformly from ${0, 1, \dots, 2^{i} - 1}$ and waits $K$ slot times before trying again. In Ethernet, one slot is 512 bit times (51.2 $μ s$ at 10 Mbps). The exponent stops growing at 10, so $K$ is at most 1023, and the frame is dropped after 16 attempts. After the first collision $K \in {0, 1}$ ; after the second, $K \in {0, 1, 2, 3}$ .

Token passing (token ring, token bus) avoids collisions altogether. A special frame, the token, goes round the stations, and only the station holding it may send. It sends its frame(s), then passes the token to the next station. Delay has an upper bound, and the channel is used well under heavy load. The costs: a lost token needs a recovery procedure, and under light load stations waste time waiting for the token.

EXAM TIP

Check the units first: B in bits per second, T_p in seconds, and the kilo/mega convention the question states. If the question gives the round-trip time, do not double it again.

Ethernet, switches and domains

Field	Size	Note
Preamble	7 bytes	Alternating 1s and 0s (`10101010`) for clock synchronisation
Start frame delimiter	1 byte	`10101011`
Destination address	6 bytes	48-bit MAC address
Source address	6 bytes	48-bit MAC address
Type / length	2 bytes	A value of 1500 or less is the payload length; 1536 (0x0600) or more names the upper-layer protocol
Payload (data + padding)	46 to 1500 bytes	Padded up to 46 bytes if shorter
FCS (CRC-32)	4 bytes	Covers the destination address through the payload

Frame sizes are counted from the destination address to the FCS, leaving out the preamble and delimiter. The minimum frame is 64 bytes (6 + 6 + 2 + 46 + 4), which is 512 bits, and the maximum is 1518 bytes (6 + 6 + 2 + 1500 + 4). The minimum is the CSMA/CD rule $L \geq 2 T_{p} B$ applied to the original 10 Mbps Ethernet: 512 bits take 51.2 $μ s$ to send, which covers the round-trip delay of the largest network allowed. A MAC address is 48 bits. If the least significant bit of the first byte is 1, the address is a group (multicast) address; the all-ones address FF:FF:FF:FF:FF:FF is the broadcast address.

Learning bridge or switch, for every frame it receives: record the source address against the port the frame came in on, refreshing the table entry.
If the destination address is in the table and on a different port, forward the frame to that port only.
If the destination is on the port the frame came in on, discard (filter) the frame.
If the destination is unknown, or is a broadcast address, flood the frame out of every port except the one it came in on.

Spanning tree protocol: bridges connected in a loop would forward broadcast frames round the loop forever, so they run the spanning tree protocol to block redundant ports.
The bridge with the lowest bridge ID (priority, then MAC address) becomes the root bridge.
Every other bridge picks as its root port the port with the lowest path cost to the root.
Each LAN segment picks one designated port: the port on the bridge with the lowest cost to the root, with ties broken by the lower bridge ID. Ports that are neither root ports nor designated ports are blocked, and the active links form a tree.

Device	Collision domains	Broadcast domains
Hub / repeater	Extends one collision domain (all ports share it)	Same domain
Switch / bridge	Each port is its own collision domain	Does not split broadcast domains (unless VLANs are configured)
Router	Each port is separate	Each port is a separate broadcast domain

EXAM TIP

Counting domains: by the standard counting convention, each switch port is one collision domain, even when it connects a single full-duplex host that can never collide. A hub plugged into a switch port puts all of the hub's hosts into that port's single collision domain.

PREVIOUS-YEAR QUESTIONS

3 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 2 · GATE CSE 2024 Set 2 · GATE CSE 2018

GATE 2026 CS2 Q.43

GATE 2026 · CS2Q.43 · 2 marks · MCQ

Consider 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?

(A)
011
(B)
101
(C)
000
(D)
100

Answer and solution

GATE 2026 CS2 Q.43: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS2 Q.43: answer and solution

GATE 2024 CS2 Q.55

GATE 2024 · CS2Q.55 · 2 marks · NAT

Consider an Ethernet segment with a transmission speed of $1 0^{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 1 0^{8}$ meters/sec, then the minimum frame size (in bits) required for collision detection is ______

Answer and solution

GATE 2024 CS2 Q.55: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS2 Q.55: answer and solution

GATE 2018 CS Q.55

GATE 2018 · CSQ.55 · 2 marks · NAT

Consider a simple communication system where multiple nodes are connected by a shared broadcast medium (like Ethernet or wireless). The nodes in the system use the following carrier-sense based medium access protocol. A node that receives a packet to transmit will carrier-sense the medium for 5 units of time. If the node does not detect any other transmission in this duration, it starts transmitting its packet in the next time unit. If the node detects another transmission, it waits until this other transmission finishes, and then begins to carrier-sense for 5 time units again. Once they start to transmit, nodes do not perform any collision detection and continue transmission even if a collision occurs. All transmissions last for 20 units of time. Assume that the transmission signal travels at the speed of 10 meters per unit time in the medium.

Assume that the system has two nodes P and Q, located at a distance d meters from each other. P starts transmitting a packet at time t=0 after successfully completing its carrier-sense phase. Node Q has a packet to transmit at time t=0 and begins to carrier-sense the medium.

The maximum distance d (in meters, rounded to the closest integer) that allows Q to successfully avoid a collision between its proposed transmission and P's ongoing transmission is ______.

Answer and solution

GATE 2018 CS Q.55: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 CS Q.55: answer and solution

OTHER EXAMS

ISRO: 5 questions

From ISRO's Scientist/Engineer written test: ISRO CS 2025, ISRO CS 2023. They are not counted in the GATE numbers on this page.

ISRO CS 2025 Q.37

ISRO 2025 · CSQ.37 · 1 mark · MCQ

37. A communication system is designed using the following three 5 bit words as the only valid codewords and uses error correction using hamming distance.
Codeword A: 00000
Codeword B: 01110
Codeword C: 11000
During operation, receiver gets the word 01000. What would the system conclude?

(A)
It will correct to codeword A
(B)
It will correct to codeword B
(C)
It will correct to codeword C
(D)
It will be unable to correct the error

Answer and solution

ISRO CS 2025 Q.37: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2025 Q.37: answer and solution

ISRO CS 2023 Q.13

ISRO 2023 · CSQ.13 · 1 mark · MCQ

In a computer network using CSMA/CD, the minimum frame size for data transfer is 1500 bytes. What will be the data transfer speed in this network over 1 Km cable, if the signal speed in the cable is 250000 Km/sec and no repeaters are used in this network?

(A)
1 Gbps
(B)
100 Mbps
(C)
500 Mbps
(D)
1.5 Gbps

Answer and solution

ISRO CS 2023 Q.13: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2023 Q.13: answer and solution

ISRO CS 2023 Q.15

ISRO 2023 · CSQ.15 · 1 mark · MCQ

Match the following:

Versions of 802.11: (i) 802.11ac, (ii) 802.11 a/g, (iii) 802.11 ad, (iv) 802.11 b
Speed of Wireless LAN: (P) 7 Gbps, (Q) 11 Mbps, (R) 54 Mbps, (S) 3.5 Gbps

ISRO CS 2023 question 15: A two-column table. — Figure from the ISRO CS 2023 paper. It is part of the question.

(A)
(i) – (S), (ii) – (R), (iii) – (P), (iv) – (Q)
(B)
(i) – (S), (ii) – (R), (iii) – (Q), (iv) – (P)
(C)
(i) – (R), (ii) – (S), (iii) – (P), (iv) – (Q)
(D)
(i) – (R), (ii) – (Q), (iii) – (P), (iv) – (S)

Answer and solution

ISRO CS 2023 Q.15: answer and solution

ISRO CS 2023 Q.16

ISRO 2023 · CSQ.16 · 1 mark · MCQ

Which of the following is true?

(A)
Both Parity and Cyclic Redundancy Check are error correcting codes
(B)
Both Parity and Low Density Parity Check Code are error correcting codes
(C)
Both Reed-Solomon code and Low Density Parity Check Code are error correcting codes
(D)
Both Cyclic Redundancy Check and Low Density Parity Check Code are error correcting codes

Answer and solution

ISRO CS 2023 Q.16: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2023 Q.16: answer and solution

ISRO CS 2023 Q.22

ISRO 2023 · CSQ.22 · 1 mark · MCQ

22. Which of the following methods is used to detect double errors?

(A)
Odd Parity
(B)
Even Parity
(C)
Checksum (CRC)
(D)
Checksum (XOR)

Answer and solution

ISRO CS 2023 Q.22: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2023 Q.22: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 11 mark · NAT

A slotted ALOHA channel has a bandwidth of 2 Mbps (take 1 Mbps = $1 0^{6}$ bits/s) and operates at an offered load of $G = 1$ frame per slot. What is the useful throughput in kbps (1 kbps = $1 0^{3}$ bits/s)? Give the answer to the nearest whole number.

Answer and solution

Answer: $736$ (accepted range $\pm 1$ )

Slotted ALOHA throughput: $S = G e^{- G}$ .
At $G = 1$ : $S = e^{- 1} \approx 0.3679$ .
Useful throughput = $0.3679 \times 2000$ kbps $\approx 735.8$ kbps, which rounds to 736.

PRACTICE 21 mark · MCQ

A block code has minimum Hamming distance 8. Let $x$ be the number of bit errors it is guaranteed to detect and $y$ the number it is guaranteed to correct (each taken on its own). What is $(x, y)$ ?

(A)
(7, 3)
(B)
(8, 4)
(C)
(7, 4)
(D)
(8, 3)

Answer and solution

Answer: (A)

Detection: $d - 1 = 7$ .
Correction: $⌊(d - 1) /2 ⌋ = ⌊ 7/2 ⌋ = 3$ .
So $(x, y) = (7, 3)$ .

PRACTICE 32 marks · MSQ

A CRC uses the generator $G (x) = x^{3} + x + 1$ on codewords of 7 bits. Which of the following errors are always detected?

(A)
Every single-bit error
(B)
Every burst error of length 3 or less
(C)
Every error that flips an odd number of bits
(D)
Every double-bit error

Answer and solution

Answer: (A), (B), (D)

A: $G$ has more than one term, so no single-bit error pattern $x^{i}$ is divisible by $G$ . True.
B: $G$ has degree 3 and constant term 1, so every burst of length at most 3 is detected. True.
C: The error pattern 0001011 is $G (x)$ itself. It flips 3 bits (an odd number) and leaves remainder 0, so it goes undetected. This fits $G (1) = 1 + 1 + 1 = 1 \neq = 0$ mod 2: $x + 1$ is not a factor of $G$ . False.
D: $x^{3} + x + 1$ is primitive, so $G$ divides $x^{k} + 1$ only when $k$ is a multiple of 7. A double-bit error is $x^{i} (x^{k} + 1)$ with $1 \leq k \leq 6$ in a 7-bit codeword, and $G$ divides neither $x^{i}$ nor $x^{k} + 1$ . True.

PRACTICE 41 mark · MCQ

A 24-port switch connects 24 hosts, one host per port, with no hubs and no VLANs. How many collision domains and how many broadcast domains does this network have?

(A)
1 collision domain and 1 broadcast domain
(B)
24 collision domains and 1 broadcast domain
(C)
24 collision domains and 24 broadcast domains
(D)
1 collision domain and 24 broadcast domains

Answer and solution

Answer: (B)

A switch separates collision domains: each port is its own domain, which gives 24.
A switch forwards broadcast frames out of every port, so without VLANs all 24 hosts are in one broadcast domain.
The answer is 24 collision domains and 1 broadcast domain.

PRACTICE 52 marks · NAT

A CSMA/CD network runs at 10 Mbps (take 1 Mbps = $1 0^{6}$ bits/s). The minimum frame size is 512 bits, and signals travel at $2 \times 1 0^{8}$ m/s. Ignoring repeater and jam delays, what is the maximum cable length in metres between the two farthest stations?

Answer and solution

Answer: $5120$ (accepted range $\pm 1$ )

Minimum frame time: $512/ (10 \times 1 0^{6}) = 51.2 μ s$ .
This must be at least the round-trip time $2 T_{p}$ , so $T_{p} \leq 25.6 μ s$ .
Distance $= v \times T_{p} = 2 \times 1 0^{8} \times 25.6 \times 1 0^{- 6} = 5120$ m.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

Data link layer: error detection, Medium Access Control, Ethernet

Preparing in Kolkata? IAE Academy's course for GATE CSE.