Computer Networks (AD-602) Unit 2 Notes - RGPV

How unit 2 is examined

This unit covers framing, error and flow control, sliding window ARQ protocols, and the MAC methods (ALOHA, CSMA family, IEEE 802); the marks sit in CSMA/CD with its frame-size numerical, error and flow control, and the sliding window protocols.

Data Link Layer: Need, Services Provided, Framing, Flow Control, Error control

Medium weight

Definition. The data link layer is layer 2 of the OSI model; it turns the raw, error-prone bit pipe of the physical layer into a reliable node-to-node link by framing bits, controlling errors and controlling flow.

Key points.

Need: noise, attenuation and interference flip bits on the physical medium, so a layer must detect and repair errors before data reaches the network layer.
Services: it provides framing, physical (MAC) addressing, error control, flow control and access control of the shared medium.
Framing: the bit stream is split into frames using character count, flag bytes with byte stuffing, or flag bits with bit stuffing (a 0 is inserted after every five consecutive 1s).
Flow control stops a fast sender from swamping a slow receiver, using feedback in stop-and-wait or a window in sliding window.
Error detection uses parity (single bit), checksum (sum of words), or CRC (remainder of division by a generator polynomial, catches burst errors).
Error correction uses Hamming code, where $2^r \ge m + r + 1$ redundant bits let the receiver locate and fix a single-bit error.
ARQ (Automatic Repeat reQuest) corrects by retransmission: the receiver sends ACK or NAK, and the sender resends on NAK or timeout (Stop-and-Wait, Go-Back-N, Selective Repeat).
Detection needs fewer redundant bits than correction, so wired links use detection with ARQ and noisy wireless links use forward correction.

Answer frame. Open with the definition; list need and services; then error control (detection: parity, checksum, CRC; correction: Hamming, ARQ) and flow control (stop-and-wait, sliding window) in that order; draw a frame with header, data and trailer (CRC); close with one line on how ARQ combines both.

Asked: [7 marks] (May 2023) Explain in detail about the error and flow control mechanisms employed at data link layer. Asked: [7 marks] (May 2024) Why is error control necessary in data communication? Describe the methods used for error detection and correction in the Data Link Layer.

Data Link Layer Protocol: Elementary & Sliding Window protocol

Definition. In sliding window flow control the sender may transmit up to W unacknowledged frames, and the window slides forward as acknowledgements arrive.

Key points.

Frames carry sequence numbers; with $n$ bits the numbers run $0$ to $2^n-1$ and wrap around.
The sender window holds the sent-but-unacknowledged frames plus those allowed to be sent; the receiver window holds the sequence numbers it will accept.
On each ACK the sender window slides right, freeing space for new frames.
It keeps the pipe full, so utilisation is far higher than stop-and-wait, and it gives flow control because W limits the unacknowledged data.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 424 80" width="424" height="80" role="img" aria-label="Sender window of 3 frames slides right when ACK 3 returns from the receiver"><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M58.7,43.5 Q212,72 363.4,43.8" marker-end="url(#ah3)"/><path class="e" d="M365.3,36.5 Q212,8 60.6,36.2" marker-end="url(#ah3)"/><g class="wl"><rect x="177.2" y="48.8" width="68.7" height="18" rx="9"/><text class="t" x="211.5" y="57.8" dy=".35em" text-anchor="middle">F0-F1-F2</text></g><g class="wl"><rect x="192.1" y="13.2" width="40.8" height="18" rx="9"/><text class="t" x="212.5" y="22.2" dy=".35em" text-anchor="middle">ACK3</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">R</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Sender window of 3 frames slides right when ACK 3 returns from the receiver</figcaption></figure>

Answer frame. Open with the definition; draw the sender and receiver windows with the frames and ACK; explain sequence numbers and window movement; close with the efficiency gain.

Asked: [7 marks] (May 2023) Explain the working principle of Sliding Window protocol with suitable diagram.

1-bit protocol

Definition. The 1-bit sliding window protocol is a sliding window with window size 1 and sequence numbers 0 and 1, i.e. stop-and-wait with piggybacked acknowledgements.

Key points.

Elementary (utopian) protocols assume simplex flow, error-free channel, infinite buffers and a receiver that is always fast enough; they are stop-and-wait in nature.
In the 1-bit protocol the sender sends frame 0, waits for the ACK, then sends frame 1, alternating.
Data flows both ways, and the ACK is piggybacked on the reverse data frame to save bandwidth.
A duplicate caused by a lost ACK is recognised by its repeated sequence number and discarded.

Asked: [7 marks] (May 2024) What are the key characteristics of the elementary protocol? Explain the operation of the 1-bit sliding window protocol in the Data Link Layer.

Go-Back-N

Definition. Go-Back-N is a sliding window ARQ protocol with sender window $2^n-1$ and receiver window 1; on an error the sender retransmits the damaged frame and every frame after it.

Key points.

The receiver accepts only the next expected frame and discards out-of-order frames.
It uses cumulative ACKs: ACK $k$ confirms all frames up to $k-1$.
On timeout the sender goes back and resends all frames from the lost one.

Basis	Go-Back-N	Selective Repeat
Sender window	$2^n-1$	$2^{n-1}$
Receiver window	1	$2^{n-1}$
Resending	Damaged frame and all after it	Only the damaged frame
ACK	Cumulative	Individual
Receiver buffering	None	Buffers out-of-order frames
Bandwidth	Wasted on resends	Efficient
Complexity	Simple	Complex (sorting, buffers)

Asked: [7 marks] (Jun 2025) Describe and compare Go-Back-N and Selective Repeat Sliding Window protocols.

Selective Repeat

Definition. Selective Repeat is a sliding window ARQ in which only the lost or damaged frame is retransmitted.

Key points.

Both windows have size $2^{n-1}$, so the sequence space is $2^n$.
The receiver buffers out-of-order frames and sends an individual ACK (or NAK) for each.
A frame is delivered to the network layer in order once the gap is filled.
Each frame has its own timer, so it saves bandwidth at the cost of memory and complexity.

Hybrid ARQ

Definition. Hybrid ARQ (HARQ) combines forward error correction with ARQ retransmission.

Key points.

Frames carry error-correcting code, so small errors are fixed without any retransmission.
If correction fails, the receiver requests a retransmission (ARQ).
Type I resends the same frame; Type II (incremental redundancy) sends extra parity bits, which the receiver combines with the earlier copy.
It is used in noisy links such as LTE and 5G, giving higher throughput than plain ARQ.

MAC Sub layer: MAC Addressing

Definition. The MAC sub layer is the lower half of the data link layer that controls access to a shared medium; a MAC address is the 48-bit hardware address of a network interface.

Key points.

It is written as six hex bytes, e.g. 00:1A:2B:3C:4D:5E.
The first 24 bits are the OUI of the manufacturer and the last 24 bits are the device serial number.
It is unique, burned into the NIC, and works at layer 2 within a single link.
Broadcast is FF:FF:FF:FF:FF:FF.

Binary Exponential Back-off (BEB) Algorithm

Definition. BEB is the CSMA/CD collision rule: after the $n$-th successive collision a station waits a random number of slot times chosen from $0$ to $2^n-1$.

Key points.

Slot time is $2T_p$ (51.2 microseconds in 10 Mbps Ethernet).
The range doubles on every collision, so contention among many stations thins out.
The exponent is capped at 10 and the station gives up after 16 attempts, reporting an error.

Distributed Random Access Schemes/Contention Schemes

Definition. In random access (contention) schemes there is no central controller: each station transmits when it has data, and collisions are resolved by retransmission.

Key points.

No time slot is pre-assigned; stations compete for the shared channel.
Families are ALOHA, slotted ALOHA and CSMA, CSMA/CD, CSMA/CA.
They suit bursty traffic with light load, but efficiency falls as load grows.

ALOHA and Slotted ALOHA

Definition. Pure ALOHA lets a station send whenever it has a frame; Slotted ALOHA allows sending only at the start of a fixed time slot.

Key points.

Pure ALOHA: if no ACK arrives, the station waits a random time and resends; vulnerable time is $2T_{fr}$.
Slotted ALOHA: time is divided into slots of one frame time, so frames collide fully or not at all; vulnerable time is $T_{fr}$.
Throughput with $G$ frames per frame time: pure $S = Ge^{-2G}$, slotted $S = Ge^{-G}$.

Basis	Pure ALOHA	Slotted ALOHA
Vulnerable time	$2T_{fr}$	$T_{fr}$
Max throughput	18.4% at $G=0.5$	36.8% at $G=1$
Synchronisation	Not needed	Needed

Asked: [7 marks] (Jun 2025) What do you mean by Distributed Random Access Scheme? Compare and analyze the working principle of Pure and Slotted ALOHA protocols.

CSMA, CSMA/CD, CSMA/CA

Definition. CSMA (Carrier Sense Multiple Access) makes a station listen to the channel before transmitting; CSMA/CD adds collision detection, and CSMA/CA avoids collisions.

Key points.

1-persistent CSMA sends at once when idle; non-persistent waits a random time when busy; p-persistent sends with probability $p$ in each slot.
CSMA/CD (wired Ethernet) steps: sense the carrier, transmit, keep listening, and on collision send a jam signal and back off.
The jam signal (32 to 48 bits) ensures every station knows a collision occurred.
Collisions are managed by Binary Exponential Backoff: after the $n$-th collision wait $K \times$ slot time, $K \in [0, 2^n-1]$.
Detection needs the transmission time to be at least twice the propagation time, hence a minimum frame length.
CSMA/CA (Wi-Fi 802.11) cannot detect collisions, so it uses inter-frame spacing, random backoff and ACKs, optionally RTS/CTS.

Formula. $$T_{fr} \ge 2T_p \Rightarrow L_{min} = B \times 2T_p$$

Example. Given $B = 10$ Mbps, $T_p = 25.6\,\mu s$.

$L_{min} = 10\times10^6 \times 2 \times 25.6\times10^{-6} = 512$ bits

Minimum frame = 512 bits = 64 bytes.

Answer frame. Open with the definition of CSMA and its persistence variants; draw the CSMA/CD flow (sense, send, collision, jam, backoff); explain BEB; close with the min-frame condition and Ethernet use. For the numerical, write Given, the condition, substitution and the answer in bits and bytes.

Pitfall: Forgetting the factor 2 in $2T_p$ (round trip) gives half the correct frame size.

Asked: [7 marks] (May 2023, May 2024) Explain CSMA Protocol. Explain how collisions are handled in CSMA/CD. Asked: [7 marks] (Jun 2025) Explain the working of CSMA/CD protocol. A network using CSMA/CD has a bandwidth of 10 Mbps. If the maximum propagation time (including the delays in the devices and ignoring the time needed to send a jamming signal) is $25.6\,\mu s$, what is the minimum size of the frame?

IEEE Standards 802 series & their variant

Definition. IEEE 802 is the family of standards for LANs and MANs that defines the physical and data link layers.

Key points.

802.3 is Ethernet (CSMA/CD); 802.11 is Wi-Fi (CSMA/CA).
802.15 covers Bluetooth and PAN, and 802.16 covers WiMAX.
802.2 defines the LLC sub layer, and 802.1 covers bridging and architecture.
Variants such as 802.11a/b/g/n/ac/ax differ in frequency band and speed.

Last-minute revision

Data link layer: framing, error control, flow control, MAC addressing.
Bit stuffing: insert a 0 after five consecutive 1s.
Hamming: $2^r \ge m + r + 1$.
Go-Back-N sender window $2^n-1$, receiver 1; Selective Repeat both $2^{n-1}$.
1-bit protocol: window 1, sequence numbers 0 and 1, piggybacked ACK.
Pure ALOHA: vulnerable time $2T_{fr}$, max 18.4% ($S=Ge^{-2G}$).
Slotted ALOHA: vulnerable time $T_{fr}$, max 36.8% ($S=Ge^{-G}$).
CSMA/CD condition: $T_{fr} \ge 2T_p$, so $L_{min} = B \times 2T_p$.
10 Mbps with $T_p = 25.6\,\mu s$ gives 512 bits = 64 bytes.
BEB: wait $K \in [0, 2^n-1]$ slots after the $n$-th collision.
MAC address is 48 bits; 802.3 is Ethernet, 802.11 is Wi-Fi.

Memory hooks

"F-E-F": Framing, Error, Flow are the three jobs of the link layer.
GBN = "Go Back, Nuisance" (resends all); SR = "Selective, Resends one".
ALOHA: Pure is 2 (2T, $e^{-2G}$), Slotted is 1; efficiency 18 vs 36 (double).
CD = wired "Detect", CA = wireless "Avoid".
Slot time equals $2T_p$, and the frame must last at least that long.

Coverage checklist

Data Link Layer: Need, Services Provided, Framing, Flow Control, Error control: covers May 2023 and May 2024 error/flow control questions.
Data Link Layer Protocol: Elementary & Sliding Window protocol: covers May 2023 sliding window question.
1-bit protocol: covers May 2024 elementary and 1-bit protocol question.
Go-Back-N: covers Jun 2025 Go-Back-N vs Selective Repeat comparison.
Selective Repeat: covered by the comparison table and its own section.
Hybrid ARQ: definition and types.
MAC Sub layer: MAC Addressing: format and structure.
Binary Exponential Back-off (BEB) Algorithm: rule and limits.
Distributed Random Access Schemes/Contention Schemes: meaning, covers Jun 2025 ALOHA question.
ALOHA and Slotted ALOHA: covers Jun 2025 comparison.
CSMA, CSMA/CD, CSMA/CA: covers May 2023, May 2024 and Jun 2025 questions including the numerical.
IEEE Standards 802 series & their variant: main standards.

Account

Computer Networks (AD-602) - Unit 2 Short Notes

How unit 2 is examined

Data Link Layer: Need, Services Provided, Framing, Flow Control, Error control

Data Link Layer Protocol: Elementary & Sliding Window protocol

1-bit protocol

Go-Back-N

Selective Repeat

Hybrid ARQ

MAC Sub layer: MAC Addressing

Binary Exponential Back-off (BEB) Algorithm

Distributed Random Access Schemes/Contention Schemes

ALOHA and Slotted ALOHA

CSMA, CSMA/CD, CSMA/CA

IEEE Standards 802 series & their variant

Last-minute revision

Memory hooks

Coverage checklist