Data link layer — framing, error detection (CRC computation), MAC

4.3.4 · Coding › Computer Networks

1. Framing

KYUN: Receiver ko ek continuous stream milta hai ...10110101.... Markers ke bina wo ek frame ko doosre se alag nahi kar sakta. Hume delimiters chahiye — lekin delimiters galti se data ke andar bhi aa sakti hain, isliye hume ek escaping trick chahiye.

Tarikay

(a) Byte/character count — pehla field kehta hai "agle $N$ bytes mera payload hain."

Problem: agar count field khud corrupt ho jaye, toh receiver hamesha ke liye sync kho deta hai.

(b) Byte stuffing (flag bytes) — shuru aur end mein ek khaas FLAG byte daalo (jaise 0x7E). Agar FLAG ya escape byte ESC data mein aaye, toh usse ESC se prefix karo.

(c) Bit stuffing — frame ko flag pattern 01111110 se delimit karte hain. Data mein ye pattern aane se rokne ke liye, sender data mein har 5 consecutive 1s ke baad ek 0 insert karta hai.

2. Error Detection — CRC

GF(2) arithmetic KYA hai? Coefficients bits hain. Addition = subtraction = XOR (koi carries nahi!). $1 + 1 = 0$ . Isliye polynomial long division mein subtraction ki jagah XOR use hota hai.

Scratch se derivation — CRC remainder use se ye divisible kyun hota hai

Maano:

$M (x)$ = message polynomial, degree $m - 1$ (message mein $m$ bits hain).
$G (x)$ = generator, degree $r$ (toh $r + 1$ bits).

Step 1 — jagah banao. Message ko $x^{r}$ se multiply karo, yaani $r$ zeros append karo: $M (x) \cdot x^{r}$ Kyun? Ye message ko left shift karta hai, $r$ low-order slots check bits ke liye reserve karta hai.

Step 2 — divide karo. GF(2) par: $M (x) \cdot x^{r} = Q (x) G (x) + R (x), de g R < r$ $R (x)$ CRC remainder hai ( $r$ bits, FCS = Frame Check Sequence).

Step 3 — transmit karo. Bhejo: $T (x) = M (x) \cdot x^{r} + R (x)$ Ye divisible kyun hai? Kyunki GF(2) mein addition = subtraction: $T (x) = Q (x) G (x) + R (x) + R (x) = Q (x) G (x) + 0$ kyunki $R (x) + R (x) = 0$ (XOR). Toh $T (x)$ $G (x)$ ka ek exact multiple hai.

Worked example (poora long division)

Message $M = 1101$ , generator $G = 1011$ (toh $r = 3$ ).

3 zeros kyun append karo? $de g G = 3 \Rightarrow$ 3 check bits → dividend = 1101000.

1101000 ÷ 1011   (XOR division)

1101000
1011
----
0110000
 1011
 ----
 01110 0
  1011
  ----
  01010
   1011
   ----
   0001   → remainder R = 001

Step-by-step (har step kyun?): jab bhi leading bit 1 ho, $G$ ko XOR karo, shift karo, tab tak repeat karo jab tak bits khatam na ho jaayein. Leading 0 ⇒ agle bit ko neeche laao (000 se XOR karo).

Transmit $T = 1101 \underline{001} = 1101001$ .

Receiver check: 1101001 ko 1011 se divide karo → remainder 000 ⇒ accept karo. Agar koi bit flip ho, remainder ≠ 0 hoga (un errors ke liye jo $G$ pakad sakta hai).

Figure — Data link layer — framing, error detection (CRC computation), MAC

CRC kaunsi errors pakadta hai? (Acha $G$ kyun chuno)

Error pattern $E (x)$ hai; received = $T (x) + E (x)$ . Error undetected hogi agar $E (x)$ , $G (x)$ se divisible ho. Toh hum $G$ aisa choose karte hain ki wo rare ho:

Saari single-bit errors ( $E = x^{i}$ ): pakdi jaati hain agar $G$ mein $\geq 2$ terms hain.
Bit errors ki saari odd sankhya: pakdi jaati hain agar $G$ mein factor $(x + 1)$ ho.
Length $\leq r$ ke saare burst errors: pakde jaate hain (ek burst $x^{i} \cdot B (x)$ hai jahan $de g B < r$ ; $G ∤ x^{i}$ aur $de g B < de g G$ ).

3. MAC — Medium Access Control

Do flavours:

(a) CSMA/CD (wired Ethernet): Carrier Sense (baat karne se pehle suno), Multiple Access, Collision Detection (bhejte waqt bhi sunta raho; agar kuch aisa suna jo tumhare bits se match nahi karta → collision). Collision par: jam + binary exponential backoff ( $k$ -th collision ke baad $[0, 2^{k} - 1]$ slots mein random time wait karo).

(b) CSMA/CA (Wi-Fi): radio par collisions reliably detect nahi ho saktin, isliye avoid karo — bhejne se pehle random backoff wait karo, ACKs use karo, optional RTS/CTS.

Active Recall

Recall CRC remainder append karne se frame

$G (x)$ se divisible kyun ho jaata hai? Kyunki GF(2) mein $+$ aur $-$ dono XOR hain. $T = M x^{r} + R$ ; kyunki $M x^{r} = QG + R$ , hume milta hai $T = QG + R + R = QG$ , ek exact multiple.

Recall CSMA/CD mein

$L_{m i n} \geq 2 B τ$ kyun zaroori hai? Sender ko tab bhi transmit karte rehna chahiye jab worst-case collision signal (round trip $2 τ$ ) wapas aaye, taaki wo use detect kar sake.

Recall Bit stuffing ka rule?

Data mein har paanch consecutive 1s ke baad ek 0 insert karo, taaki flag 01111110 payload mein kabhi na aa sake.

Recall (Feynman, ek 12 saal ke bacche ko samjhao)

Socho ek lambi sentence bina spaces ke bhej rahe ho. Framing = clear START/END marks lagana taaki tumhara dost jaane har word kahan hai. CRC = end mein ek chhota "magic number" lagana; tumhara dost wahi calculation dubara karta hai — agar match nahi karta, koi letter dak mein bigad gaya. MAC = ye rule ki "ek waqt mein sirf ek hi insaan baat kare" taaki ek shor-bharey kamrey mein sab ko samjha ja sake.

Data link layer ke teen kaam kya hain?

Framing, error detection, aur medium access control (MAC).

Bit stuffing ka rule kya hai?

Data mein har 5 consecutive 1s ke baad ek 0 insert karo taaki flag 01111110 payload mein na aaye.

CRC mein

r

kya hai aur message mein kitne zeros append karte hain?

r = de g G (x)

;

r

zeros append karo (

M (x)

x^{r}

se multiply karo).

Transmitted CRC frame

T (x)

G (x)

se divisible kyun hai?

T = M x^{r} + R

aur

M x^{r} = QG + R

; GF(2) mein

R + R = 0

, isliye

T = QG

(exact multiple).

CRC division mein kaun si arithmetic use hoti hai?

GF(2): addition/subtraction dono XOR hain, koi carries nahi.

CRC error E(x) kab undetected rehti hai?

Jab

E (x)

G (x)

se divisible ho.

Factor

(x + 1)

wala generator kaun si errors pakadta hai?

Saari wo errors jinmein odd number of bit flips hain.

CSMA/CD ko minimum frame size kyun chahiye?

Taaki sender tab bhi transmit kar raha ho jab worst-case collision ki khabar round-trip

2 τ

ke baad wapas aaye; isliye

L_{m i n} \geq 2 B τ

Collision ke baad CSMA/CD kya karta hai?

Jam signal, phir binary exponential backoff (random wait

[0, 2^{k} - 1]

slots mein).

Wi-Fi mein CD ki jagah CSMA/CA kyun?

Radios transmit karte waqt collisions reliably detect nahi kar sakten, isliye collisions avoid kiye jaate hain (backoff + ACKs/RTS-CTS).

MAC address kitne bits ka hota hai aur kya ye hierarchical hai?

48 bits, flat (hierarchical nahi), local link delivery ke liye use hota hai.

Kya CRC errors correct karta hai?

Nahi — ye sirf detect karta hai; correction ke liye Hamming jaise codes chahiye.

CRC: message 1101, G=1011, FCS dhundo.

000 append karo → 1101000 ko 1011 se divide karo → remainder 001; 1101001 transmit karo.

Connections

Physical Layer — raw bit pipe provide karta hai jis par framing kaam karti hai.
Polynomials over GF(2) — CRC ka math foundation.
Hamming Code — error correction vs CRC ki detection.
Ethernet — CSMA/CD use karta hai, 64-byte min frame, MAC addresses.
Network Layer (IP) — hierarchical addressing ko flat MAC se contrast karta hai.
Stop-and-Wait & Sliding Window — framing + error detection ke upar bani reliability.