Unit 3: Data link layer

I. Orientation — Node-to-Node Delivery

The data link layer is Layer 2 of the OSI model and provides reliable or controlled transfer of data across a single physical link. It receives packets from the network layer, encapsulates them into frames, and coordinates access to the transmission medium.

• Service unit: The protocol data unit is the frame, containing a header, payload, and often a trailer.
• Addressing: Frames commonly use physical or MAC addresses, such as a 48-bit Ethernet address.
• Node-to-node scope: Functions apply between directly connected devices, unlike network-layer end-to-end routing.
• Core responsibilities:
  • Framing: Separating a bit stream into identifiable units.
  • Flow control: Preventing a fast sender from overwhelming a slow receiver.
  • Error control: Detecting corruption and arranging correction or retransmission.
  • Access control: Determining which device may use a shared medium.
• Sublayers:
  • Logical Link Control (LLC): Supports flow, error, and protocol identification functions.
  • Media Access Control (MAC): Handles physical addressing and shared-channel access.
• Link categories: A link may be point-to-point, with two endpoints, or multipoint, with several devices sharing capacity.

II. Transmission Errors — Corruption During Data Transfer

Transmission errors occur when received bits differ from transmitted bits because of noise, attenuation, interference, or synchronization problems.

A. Types of errors

Errors are classified according to the number and distribution of altered bits.

• Single-bit error: Exactly one bit in a data unit changes from 0 to 1 or from 1 to 0.
  • Example: 1011001 becomes 1010001.
  • It is more likely in parallel transmission or low-speed communication.
• Burst error: Two or more bits within a span are corrupted, although not every bit in that span must change.
  • Burst length: Measured from the first corrupted bit through the last corrupted bit.
  • Example: if errors occur at positions 3, 5, and 6, the burst length is four bits.
• Cause: Impulse noise lasting longer than one bit interval typically produces burst errors.
• Practical significance: At high data rates, a brief disturbance overlaps many bit intervals; therefore, burst errors are more common than isolated errors.

B. Error detection and correction techniques

Error-control techniques add redundant bits so that a receiver can identify or repair corrupted data.

• Redundancy principle: If a message contains k data bits and r check bits, the transmitted codeword contains n = k + r bits.
• Parity check: One parity bit makes the total number of 1s even or odd.
  • It detects every odd number of bit errors but can miss an even number.
• Two-dimensional parity: Data is arranged in rows and columns, each with parity; this can locate a single-bit error and detect many bursts.
• Checksum: Fixed-size words are added using one’s-complement arithmetic; the complement of the sum is transmitted.
  • The receiver obtains an all-1 result when the words and checksum are valid.
• Cyclic redundancy check (CRC): A codeword is treated as a polynomial and divided modulo 2 by a generator polynomial.

R = (D × 2^r) mod G
T = (D × 2^r) XOR R

• D = data value, G = generator, r = degree of G, R = remainder, and T = transmitted codeword.
• Forward error correction: Codes such as Hamming code allow correction without retransmission.
• Hamming distance: To detect s errors, minimum distance must be at least s + 1; to correct t errors, it must be at least 2t + 1.

III. Frame Construction — Organizing the Bit Stream

Framing marks the beginning and end of each data-link-layer unit so that the receiver can identify addresses, control fields, payload, and error-checking information.

A. Framing

Framing converts an unstructured bit stream into independently processed frames.

• Character count: A header field specifies frame length; corruption of that count can destroy synchronization.
• Byte stuffing: Special bytes mark frame boundaries, and an escape byte is inserted before the same pattern inside data.
  • The receiver removes inserted escape bytes before passing up the payload.
• Bit stuffing: Bit-oriented protocols use a flag such as 01111110; the sender inserts a 0 after every sequence of five consecutive 1s in data.
  • The receiver removes that stuffed 0, ensuring that payload cannot imitate the flag.
• Physical-layer coding violations: Reserved signal patterns that do not represent ordinary data mark boundaries.
• Frame fields: A typical frame includes destination and source addresses, control information, payload, and a frame check sequence.
• Trade-off: Small frames reduce retransmission cost after errors but increase header and processing overhead.

IV. Link Management — Reliable Frame Exchange

A data link protocol specifies frame formats, sender and receiver behavior, timing, acknowledgment rules, and responses to loss or damage.

A. Data link layer protocols

Data link layer protocols coordinate communication over both noiseless and noisy links.

• Protocol rules: Define when frames may be sent, how they are numbered, and how acknowledgments are interpreted.
• Connection modes:
  • Connectionless: Frames are delivered independently without setup or guaranteed recovery.
  • Connection-oriented: A logical link is established and sequence control supports ordered, reliable delivery.
• Representative protocols: Ethernet governs LAN framing and MAC access; PPP carries network-layer packets over point-to-point links; HDLC is a bit-oriented synchronous protocol.
• Noisy-channel operation: Sequence numbers, timers, acknowledgments, and retransmissions implement automatic repeat request, or ARQ.

B. Flow and error control

Flow and error control jointly regulate transmission rate and recover from damaged, duplicated, or missing frames.

1. Flow control:

   • Purpose: Limits outstanding data to available receiver buffer capacity.
   • Feedback: Acknowledgments or advertised windows tell the sender how much data may be transmitted.
   • Methods: Stop-and-wait permits one outstanding frame; sliding-window protocols permit several.

2. Error control:

   • Detection: CRC or another check identifies damaged frames.
   • Recovery: The receiver discards corruption, while the sender retransmits after a negative acknowledgment or timeout.
   • Sequence numbers: Distinguish new frames from duplicates caused by lost acknowledgments.
   • Piggybacking: In full-duplex links, an acknowledgment can be included in an outgoing data frame.

V. Stop-and-Wait Operation — One Outstanding Frame

Stop-and-wait provides simple flow control by requiring feedback after every transmitted frame.

A. Stop-and-wait ARQ

Stop-and-wait ARQ adds error recovery, sequence numbers, and a timer to basic stop-and-wait flow control.

• Operation: The sender transmits one frame, starts a timer, and waits for an acknowledgment before proceeding.
• Alternating sequence numbers: Frames use sequence numbers 0 and 1; this one-bit field lets the receiver reject duplicates.
• Lost or damaged frame: No valid acknowledgment arrives, so timer expiration causes retransmission.
• Lost acknowledgment: The sender retransmits; the receiver recognizes the duplicate, discards its data, and repeats the acknowledgment.
• Utilization:

U ≈ Tframe / (Tframe + 2Tprop + Tack)

• U = utilization, Tframe = frame transmission time, Tprop = one-way propagation delay, and Tack = acknowledgment transmission time.
• Limitation: Long propagation delay leaves the channel idle while the sender waits, producing poor bandwidth utilization.

VI. Go-Back-N Operation — Pipelined Cumulative Recovery

Go-back-N increases utilization by allowing multiple sequential frames to remain unacknowledged.

A. Go-back-N ARQ

Go-back-N ARQ uses a sender window and retransmits a failed frame together with all later outstanding frames.

• Sender window: With an m-bit sequence field, the maximum window size is 2^m − 1.
• Receiver window: Its size is one; only the next expected frame is accepted.
• Cumulative acknowledgment: An acknowledgment for sequence n confirms all frames before the next expected number.
• Error response: If frame 2 is lost while frames 3 and 4 arrive, the receiver discards 3 and 4; timeout causes retransmission beginning at frame 2.
• Timer policy: Usually the oldest unacknowledged frame controls the retransmission timer.
• Advantage: Pipelining raises throughput, particularly when the window covers the bandwidth-delay product.
• Limitation: A single error can force retransmission of several correctly transmitted frames.

VII. Selective-Repeat Operation — Targeted Retransmission

Selective repeat reduces recovery traffic by retaining valid out-of-order frames and retransmitting only missing or damaged ones.

A. Selective repeat ARQ

Selective repeat ARQ maintains sender and receiver windows and acknowledges frames individually.

• Receiver behavior: Correct frames inside the receive window are buffered even when earlier frames are missing.
• Recovery: Only a timed-out or negatively acknowledged frame is retransmitted.
• Delivery order: Buffered frames pass to the network layer after all preceding sequence numbers arrive.
• Window limit:

W ≤ 2^(m − 1)

• W = maximum window size and m = sequence-number field length; the limit prevents old frames from being confused with new frames after wraparound.
• Advantage: It performs better than Go-back-N on noisy links or when frames are large.
• Cost: It needs more receiver memory, per-frame timers or equivalent tracking, and more complex logic.

VIII. Shared-Medium Coordination — Allocating Link Capacity

When many stations share one broadcast channel, an access protocol is needed to reduce collisions and distribute transmission opportunities.

A. Multiple access control protocols

Multiple access control protocols determine how competing stations use a common channel.

• Primary objective: Achieve high utilization while maintaining fairness and acceptable delay.
• Collision: Simultaneous transmissions overlap, making one or more frames undecodable.
• Main families:
  • Random access: Stations contend without fixed permission.
  • Controlled access: Stations coordinate turns.
  • Channelization: Capacity is divided by frequency, time, or code.
• Selection factors: Traffic pattern, propagation delay, number of stations, required quality of service, and implementation cost determine suitability.

IX. Contention-Based Sharing — Decentralized Competition

Contention methods let a station transmit according to locally observed channel conditions rather than a central schedule.

A. Random access

Random access protocols accept possible collisions and use rules for detection, avoidance, and retransmission.

• Pure ALOHA: A station transmits immediately; after collision, it waits a random time. Maximum theoretical throughput is 1/(2e), about 18.4%.
• Slotted ALOHA: Transmission begins only at slot boundaries, reducing the vulnerable period and raising maximum throughput to 1/e, about 36.8%.
• CSMA: Carrier Sense Multiple Access listens before transmitting, using persistent or nonpersistent waiting rules.
• CSMA/CD: Classic shared Ethernet detects collisions, stops transmission, sends a jam signal, and applies binary exponential backoff.
• CSMA/CA: IEEE 802.11 attempts collision avoidance through interframe spaces, random backoff, acknowledgments, and optional RTS/CTS exchange.
• Limitation: Performance deteriorates under heavy contention because collisions and backoff consume capacity.

X. Scheduled Sharing — Explicit Transmission Turns

Controlled-access methods coordinate stations before data transmission, reducing collisions at the cost of management overhead.

A. Controlled access

Controlled access grants transmission rights through reservation, polling, or token passing.

• Reservation: Stations declare their need during reservation intervals; allocated data slots then carry frames without contention.
• Polling: A primary controller asks each secondary station whether it has data.
  • Polling is predictable but controller failure can stop the network.
• Token passing: A special control frame circulates logically; only the token holder may transmit.
  • It provides bounded waiting, but token loss or duplication requires recovery.
• Strength: Under heavy load, orderly access can provide better throughput and fairness than random access.
• Limitation: Idle stations, control messages, token maintenance, and polling delay add overhead.

XI. Partitioned Sharing — Simultaneous Logical Channels

Channelization divides a shared physical link into separable resources so that multiple users can communicate with little or no contention.

A. Channelization

Channelization assigns users distinct frequency bands, time intervals, or identifying codes.

1. FDMA:

   • Division: Total bandwidth is split into frequency channels separated by guard bands.
   • Constraint: Each user occupies its assigned band continuously, even when idle.

2. TDMA:

   • Division: Users share the full bandwidth but transmit in assigned time slots.
   • Constraint: Synchronization and guard times prevent adjacent-slot overlap.

3. CDMA:

   • Division: All users transmit simultaneously over the same frequency range using distinct orthogonal or low-correlation chip sequences.
   • Recovery: The receiver correlates the combined signal with the intended user’s code.
   • Processing gain: A data bit represented by multiple chips gains resistance to interference.

• Comparison: FDMA separates by frequency, TDMA by time, and CDMA by code.
• Limitation: Fixed allocation may waste capacity during bursty traffic, while CDMA requires power control and more complex signal processing.