Data link & MAC formulas

Data link layer: error detection, medium access control and Ethernet. 8 formulas for GATE CS Computer Networks, each with when to use it. Each is explained in the topic notes.

All 8 Data link & MAC formulas

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.

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.

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.

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.

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.

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.

Where this was asked: 2018 (1), 2024 (1), 2026 (1). See the 3 previous-year questions on Data link & MAC. This shows what was asked, not what will be asked.

KEEP GOING

Data link & MAC: the notes and 3 solved previous-year questions