GATE CS - COMPUTER NETWORKS:Data Link Layer

Data Link Layer for GATE CS

GATE Data Link questions favour CRC/checksum, framing, and sliding-window / ARQ (stop-and-wait already in Transport — here emphasize Go-Back-N / Selective Repeat and sequence bits).

Jobs of the layer

Framing, physical addressing (MAC), error detection (sometimes correction), and reliable delivery over one hop when ARQ is used.

Error detection

• Parity: even/odd; weak
• Checksum: ones’ complement sum (IP-style); GATE may ask wraparound add
• CRC: polynomial division over GF(2); remainder is the FCS

CRC sketch

Message bits followed by $r$ zeros; divide by generator polynomial; remainder ($r$ bits) appended. Receiver divides again — zero remainder ⇒ accept (undetected errors still possible).

Sliding window

Sender may have up to $W$ unacked frames outstanding.

Go-Back-N: on error, retransmit from lost frame onward.

Selective Repeat: retransmit only lost frames (receiver buffers).

Sequence number bits $n$ ⇒ at most $2^n$ distinct seq nos; window sizing constraints differ for GBN vs SR (SR typically $W \le 2^{n-1}$).

Utilization (idealized, no error) grows with $W$ until the bandwidth-delay product is filled — same delay math as stop-and-wait with a larger effective pipeline.

Next: Application Layer. Hub: GATE.