Data Link Layer

Framing

The data link layer divides the bit stream into frames using character count, byte stuffing (flag + escape bytes) or bit stuffing (insert a 0 after five consecutive 1s).

Text

Data:          0111111111110
Bit-stuffed:   011111011111010   (a 0 inserted after every five consecutive 1s)

Error Detection: CRC

Text

Data = 1101011011, Generator = 10011 (degree 4)
Append 4 zeros:   11010110110000
Divide (XOR) by 10011  →  remainder = 1110
Transmitted frame: 1101011011 1110
Receiver divides by 10011; a remainder of 0 means no error detected.

Other methods: parity bits, 2-D parity and checksum. Hamming code can also correct single-bit errors (2^r ≥ m + r + 1).

Flow and Error Control (ARQ)

Protocol	Window (sender / receiver)	On error
Stop-and-Wait	1 / 1	Retransmit the frame after timeout
Go-Back-N	2^m − 1 / 1	Resend the lost frame and all after it
Selective Repeat	2^(m−1) / 2^(m−1)	Resend only the lost frame

Text

Stop-and-wait efficiency  η = 1 / (1 + 2a),  where a = propagation delay / transmission delay
Example: Tt = 1 ms, Tp = 2 ms → a = 2 → η = 1/5 = 20%

Medium Access Control

Pure ALOHA: max throughput 18.4% (1/2e)
Slotted ALOHA: 36.8% (1/e)
CSMA/CD: classic Ethernet; minimum frame size = 2 × Tp × bandwidth
CSMA/CA: Wi-Fi (collision avoidance with RTS/CTS)

Track your progress through the Computer Networks course

← Prev Next →