Data Link Layer: Framing, ARQ, HDLC, PPP, Channel Access and Ethernet Explained

Posted on Oct 12, 2026 in Computers

Unit 2: Data Link Layer, Complete Notes with Solved PYQs

Your exam is today, so the ★ boxes (exam-ready answers) and the PYQ solutions come first in priority. Read the basics only if you have time.

One correction to the earlier numbers: the 1 Mbps / 20 ms question has two valid answers. The textbook method (Forouzan, which the paper’s wording follows) gives 5% and 75%. The formula Tₜ/(Tₜ+RTT) gives 4.76% and 71.4%. Write the textbook method in the exam and add the formula as a one-line remark.

Topic 1: Data Link Layer (DLL) Design Issues

Basics

The DLL sits between the Network and Physical layers. It moves frames between two directly connected nodes. It is split into two sublayers:

• LLC (Logical Link Control, 802.2): flow and error control, and the interface to the Network layer.
• MAC (Medium Access Control): framing, MAC addressing and channel access.

★ Design issues (write all 5, with 1–2 lines each)

1. Services to the network layer: unacknowledged connectionless (Ethernet), acknowledged connectionless (Wi-Fi), acknowledged connection-oriented (reliable link).
2. Framing: splitting the bit stream into frames so the receiver knows where each begins and ends.
3. Error control: detect errors (CRC, parity) and fix them (ACK, NAK, timers, retransmission).
4. Flow control: stop a fast sender from overwhelming a slow receiver (feedback-based or rate-based).
5. Physical addressing and access control: MAC addresses identify nodes; the MAC sublayer decides who uses a shared channel.

Framing Methods

1. Character count: a header field gives the frame length. It breaks if the count is corrupted.
2. Flag bytes with byte stuffing: a FLAG byte marks the start and end. If FLAG or ESC appears in the data, an ESC byte is inserted before it. The receiver removes the ESC. Data A FLAG B becomes FLAG A ESC FLAG B FLAG.
3. ★ Flag bits with bit stuffing: the flag is 01111110. After five consecutive 1s in the data, the sender inserts a 0. The receiver deletes any 0 that follows five 1s. Data 0111111110 becomes 01111101110; data 01111110 becomes 011111010.
4. Physical layer coding violations: invalid signal patterns (such as Manchester violations) act as delimiters.

PYQ Solutions

• Design issues (Oct 2024, Nov 2023, Dec 2023, end term): write the 5 points above.
• Framing, byte stuffing, bit stuffing (Dec 2023, Nov 2023): methods 2 and 3 with the examples.
• Functions of the DLL and importance of flow and error control (Nov 2025): list the 5 design issues, then explain that flow control prevents buffer overflow and error control gives reliable delivery.
• DLL in IEEE 802.3 (Nov 2024): LLC (802.2) plus MAC (802.3). Ethernet’s MAC does framing, addressing, CSMA/CD and error detection (CRC-32).

Topic 2: Flow Control and Error Control (ARQ)

★ Basics

• ARQ (Automatic Repeat reQuest): detect an error, then retransmit. Uses ACK, NAK, timers and sequence numbers.
• Piggybacking: the ACK is attached to a data frame going the other way, so no separate ACK frame is needed. This saves bandwidth.

★ Stop-and-Wait (flow control)

The sender sends one frame and waits for an ACK before sending the next. It is simple but wastes the link, because the sender idles during the whole round trip.

★ Stop-and-Wait ARQ

It adds a timer and sequence numbers 0, 1. The ACK carries the number of the next expected frame.

• Frame lost or damaged: the receiver discards it and sends no ACK. The sender’s timer expires and it retransmits.
• ACK lost: the sender times out and resends. The receiver sees a duplicate (same sequence number), discards it and re-sends the ACK.
• Delayed ACK: the timer may expire early and cause a duplicate. The sequence number lets the receiver discard it.

Diagram: draw a vertical timeline for sender and receiver with arrows (Frame 0, ACK 1, Frame 1 lost ✗, timeout, Frame 1 again, ACK 0).

Sliding Window

• Several frames may be outstanding. The sender has a window of allowed sequence numbers.
• Sequence numbers run modulo 2^m (m = header bits).
• The window slides as ACKs arrive.

★ Go-Back-N ARQ

• Sender window = 2^m − 1, receiver window = 1 (it accepts only the next expected frame).
• ACKs are cumulative: ACK n means all frames up to n−1 are received.
• If a frame is lost or damaged, the receiver discards it and every later frame. The sender resends that frame and all frames after it.
• Example (m = 3): the sender sends 0–5 and frame 2 is lost. The receiver discards 3, 4, 5. The sender resends 2, 3, 4, 5.

★ Limitations of Go-Back-N:

1. It resends frames that were received correctly, wasting bandwidth.
2. It performs badly with a large window or high error rates.
3. The receiver cannot buffer out-of-order frames.

★ Selective Repeat ARQ (solves the limitation)

• Sender window = receiver window = 2^(m−1).
• The receiver accepts and buffers out-of-order frames, then delivers them in order once the gap is filled.
• It sends a NAK for the missing frame and individual ACKs for each frame received.
• The sender has a timer per frame and retransmits only the lost frame.

Why 2^(m−1)? If both windows were 2^m − 1, a retransmitted old frame could be mistaken for a new one.

★ GBN vs Selective Repeat

★ Utilization Formulas

• Let a = Tₚ / Tₜ. RTT = 2Tₚ.
• Stop-and-Wait: η = Tₜ / (Tₜ + RTT) = 1 / (1 + 2a)
• Sliding window with window N: η = min(1, N·Tₜ / (Tₜ + RTT))
• Bandwidth-delay product = bandwidth × RTT = bits that fit in one round trip.

★ PYQ Numericals

1. Oct 2024 and Nov 2024: bandwidth 1 Mbps, round trip 20 ms.

• (i) Bits per round trip = 1×10⁶ × 20×10⁻³ = 20,000 bits.
• (ii) 1000-bit frames, one per round trip: utilization = 1000 / 20,000 = 5%.
• Nov 2024 variant, 15 frames per round trip: 15,000 / 20,000 = 75%.
• Remark: Tₜ = 1 ms, so η = 1/(1+20) = 4.76%, and 15 frames give 15/21 = 71.4%.

2. Nov 2025 Q3(b): 1000 bytes, RTT 20 ms, link 10 Mbps.

• Tₜ = 8000 / (10×10⁶) = 0.8 ms.
• η = 0.8 / (0.8 + 20) = 3.85%. Using the BDP method (frame size / BDP): 8000 / 200,000 = 4%.

3. Dec 2023 / Nov 2023 (flow control, Stop-and-Wait, Sliding Window): write the Stop-and-Wait and sliding-window sections above and finish with the efficiency comparison.

Topic 3: HDLC and PPP

★ HDLC (High-level Data Link Control)

• Bit-oriented (ISO), uses bit stuffing, works on point-to-point and multipoint links.
• Station types: primary (commands), secondary (responses), combined.
• Modes: NRM (Normal Response Mode: secondary replies only when polled) and ABM (Asynchronous Balanced Mode: either station can start).

★ Frame structure:

• Flag: 01111110. Address: the secondary station’s address. Control: defines the frame type. FCS: CRC error check.

Frame types (by control-field start bits):

• I-frame (starts with 0): user data, with N(S), P/F bit, N(R) (piggybacked ACK).
• S-frame (starts with 10): flow and error control only. Types: RR, RNR, REJ (Go-Back-N), SREJ (selective reject).
• U-frame (starts with 11): link management, such as SABM, DISC, UA.

★ PPP (Point-to-Point Protocol)

• Byte-oriented, for point-to-point links (dial-up, DSL), using byte stuffing.
• Provides authentication and carries many network protocols.

★ Frame structure:

• Address is the fixed broadcast value. Control is fixed and means “unnumbered”. The Protocol field says what the payload is (IP, LCP, NCP).
• Escape byte for stuffing: 0x7D.

PPP phases:

1. Dead: no link.
2. Establish: LCP negotiates options.
3. Authenticate: PAP (simple) or CHAP (more secure).
4. Network: NCP (such as IPCP) configures the network layer.
5. Open: data transfer.
6. Terminate: link closed.

★ HDLC vs PPP

PYQ Solutions

• HDLC frame structure (Oct 2024) and PPP frame structure (Nov 2024, Dec 2023): use the tables above, with one line on each field.
• How PPP establishes a connection (Dec 2023): the phases Dead, Establish, Authenticate, Network, Open, Terminate.
• Compare HDLC and PPP with frame diagrams (end term): the comparison table and both frame diagrams.

Topic 4: Channel Allocation and Multiple Access

Channel allocation problem

Many users share one channel. Who transmits, and when?

Static allocation (FDM/TDM):

• Divide the channel into N fixed parts, one per user.
• Poor for bursty traffic: idle users waste their share.
• Delay: a single channel of capacity C has delay T = 1/(μC − λ). Splitting it into N parts makes each part’s delay N × T, so static allocation is N times worse.

★ Dynamic allocation assumptions: N independent stations; a single shared channel; collision when two frames overlap; time continuous or slotted; carrier sense available or not.

Solution families:

• Random access: ALOHA, CSMA, CSMA/CD, CSMA/CA.
• Controlled access: reservation, polling, token passing.
• Channelization: FDMA, TDMA, CDMA.

Example: ten stations share an Ethernet segment, and CSMA/CD lets each transmit when the line is idle, instead of each getting a fixed 1/10 share.

ALOHA

• Pure ALOHA: transmit any time. If no ACK arrives before the timeout, wait a random backoff and resend.
  • Vulnerable time = 2Tfr.
  • Throughput S = G·e^(−2G), maximum 18.4% at G = 0.5.
• Slotted ALOHA: time is divided into slots, and stations transmit only at slot starts.
  • Vulnerable time = Tfr.
  • S = G·e^(−G), maximum 36.8% at G = 1.

★ Nov 2025 Q1(d): slotted ALOHA, 5 nodes, p = 0.2.
A slot succeeds if exactly one node transmits:
η = 5 × 0.2 × (0.8)⁴ = 5 × 0.2 × 0.4096 = 0.4096 ≈ 41%.

CSMA (Carrier Sense Multiple Access)

Listen before transmitting (“sense before talk”). Collisions can still occur because of propagation delay. Vulnerable time = propagation time.

• 1-persistent: if idle, send at once; if busy, keep sensing and send as soon as free (collisions likely).
• Non-persistent: if busy, wait a random time, then sense again.
• p-persistent: if idle, send with probability p; otherwise wait one slot and repeat.

★ CSMA/CD (Collision Detection), wired Ethernet

1. Sense the channel. If idle, start transmitting.
2. While transmitting, keep listening. If a collision is detected, stop and send a jam signal.
3. Wait a random backoff using binary exponential backoff: after the k-th collision, pick K from [0, 2^k − 1] and wait K × 51.2 µs. Give up after 16 attempts.
4. Retry.

★ Minimum frame size: the sender must still be transmitting when the collision signal returns, so Tfr ≥ 2·Tₚ, meaning frame size ≥ 2 × Tₚ × bandwidth.

Oct 2024 Q1(c): “Frame transmission time must be at least twice the propagation time, so frame size ≥ 2·Tₚ·Bandwidth.”

Sep 2025 Q3(b): 10 Mbps, maximum propagation time 25.6 µs (jam time ignored).

• Round trip = 2 × 25.6 = 51.2 µs.
• Frame size ≥ 51.2×10⁻⁶ × 10×10⁶ = 512 bits = 64 bytes.

Flowchart to draw: Start → Sense channel → Idle? (No: keep sensing) → Transmit and listen → Collision? (No: success, end) (Yes: jam signal → attempts > 16? (Yes: abort) (No: backoff wait → sense again)).

★ CSMA/CA (Collision Avoidance), wireless LAN

Why not CD in wireless: a radio cannot reliably transmit and listen together (its own signal swamps the received one), and the hidden terminal problem means not every station hears every other.

Steps:

1. Sense the channel. If idle for DIFS, continue.
2. Pick a random backoff in the contention window and count it down while the channel stays idle. Freeze the counter when the channel becomes busy.
3. At zero, transmit (optionally send RTS and wait for CTS to reserve the channel; other stations set their NAV timers).
4. The receiver replies with an ACK after SIFS (SIFS < DIFS, so ACKs get priority).
5. No ACK means loss, so double the contention window and retry.

Flowchart to draw: Start → Channel idle for DIFS? (No: wait) → Pick backoff → Count down (freeze if busy) → Send frame (RTS/CTS optional) → ACK received? (Yes: done) (No: double window, retry up to a limit).

★ CSMA/CD vs CSMA/CA

★ Controlled Access (Oct 2024, Nov 2024)

Stations take turns, so there are no collisions.

1. Reservation: time is split into a reservation interval and data intervals. Each of N stations has one mini-slot to reserve; only reserving stations send data afterwards. Efficient under heavy load.
2. Polling: a primary station controls the link.
   • Select: the primary asks a secondary to receive.
   • Poll: the primary asks a secondary whether it has data.
   • Disadvantages: polling overhead and a single point of failure.
3. Token passing: stations form a logical ring and a special token passes around. Only the holder may transmit. Disadvantages: a lost token must be regenerated, and delay grows with ring size.

Channelization

• FDMA: each station gets its own frequency band.
• TDMA: each station gets a time slot in a repeating frame.
• CDMA: all stations use the same band and time, each with a unique orthogonal chip code (Walsh codes). The receiver multiplies by the sender’s code to recover the data.
  • Example: c1 = [+1 +1], c2 = [+1 −1]. Their inner product is 0, so they are orthogonal.

Topic 5: IEEE 802.3, 802.11 and High-Speed LANs

★ IEEE 802.3 (Ethernet)

• Wired LAN using CSMA/CD, with bus or star topology.
• Frame format:

• The preamble (alternating 1010…) synchronises the receiver clock. The SFD is 10101011.
• Minimum frame = 64 bytes (without preamble/SFD), maximum 1518.
• MAC address = 6 bytes (48 bits).
• Generations: Standard Ethernet 10 Mbps, Fast Ethernet 100 Mbps, Gigabit 1 Gbps, 10-Gigabit.

★ IEEE 802.11 (Wireless LAN / Wi-Fi)

• Architecture: BSS (stations plus an AP), ESS (several BSSs joined by a distribution system), and ad hoc (no AP).
• MAC: DCF (the main mode, uses CSMA/CA) and PCF (optional, uses polling).
• Frame: Frame control (2), Duration (2), Address 1–4 (6 each), Sequence control (2), Frame body (0–2312), FCS (4).
• Frame types: management (association), control (RTS, CTS, ACK) and data.

★ 802.3 vs 802.11

Token Ring (IEEE 802.5)

• A ring topology with a token. A station seizes the token, sends its frame, which circulates; the destination copies it, and the sender removes it and releases the token.
• Speeds 4 and 16 Mbps. An active monitor handles lost tokens and orphan frames.
• Advantages: deterministic access, no collisions, good under heavy load. Disadvantages: token management; one break stops the ring.

FDDI (Fiber Distributed Data Interface)

• Dual counter-rotating fibre rings at 100 Mbps. The primary ring carries data; the secondary is a backup.
• Uses a timed token protocol.
• If a link or station fails, the ring wraps back on itself and self-heals.
• Covers up to about 100 km (200 km for dual ring) and 500 stations. Used for campus or metropolitan backbones.

Topic 6: Network Devices

★ Switch vs hub (Nov 2024, end term):

• A hub repeats every signal to all ports. A switch learns MAC addresses, so frames go only to the destination.
• A switch gives each port its own collision domain and full-duplex operation. A hub is half-duplex and all ports share bandwidth.
• Switches are more secure and faster than hubs.

Practical examples (Nov 2024 Q4a):

• Repeater: extend a 100 m cable run across a large warehouse.
• Hub: connect a few PCs in a tiny office (now obsolete).
• Switch: connect all PCs in a computer lab, so simultaneous conversations do not interfere.

How each manages traffic flow (end term): a repeater regenerates the signal with no filtering; a hub copies the frame to all ports; a bridge filters by MAC between two segments; a switch gives a dedicated path per port. Bridges and switches reduce collisions and so improve performance.

Complete PYQ Answer Map for Unit 2