Data Link Layer

3.1 Framing

The data link layer receives a bit stream and divides it into manageable frames.

Framing methods:

1. Byte count: First field specifies frame length. Vulnerable to corrupted count.
2. Flag bytes: Special flag byte (0x7E for HDLC) marks start/end. Byte stuffing with escape byte (0x7D) prevents ambiguity.
3. Bit-oriented flags: Flag pattern 01111110. Bit stuffing: insert 0 after five consecutive 1S in the data.
4. Clock-based: Manchester encoding provides self-clocking and frame boundaries.

3.2 Error Detection and Correction

Error types: Single-bit errors (one bit flipped), burst errors (multiple consecutive bits).

Hamming distance. $d(x, y)$ is the number of bit positions where codewords $x$ and $y$ differ. The minimum distance $d_{\min}$ determines capability:

• Detect up to $d_{\min} - 1$ errors.
• Correct up to $\lfloor(d_{\min} - 1)/2\rfloor$ errors.

Hamming code. Adds $r$ parity bits to $m$ data bits where $2^r \geq m + r + 1$. Each parity bit Covers positions whose binary representation has a 1 in a specific bit position.

Example (Hamming(7,4)). 4 data bits, 3 parity bits. $d_{\min} = 3$: detects 2 errors, corrects 1.

Cyclic Redundancy Check (CRC). A polynomial code widely used (Ethernet, Wi-Fi, USB).

1. Append $r$ zero bits to the message ($r$ = degree of generator polynomial $G(x)$).
2. Divide the augmented message polynomial by $G(x)$ using modulo-2 arithmetic.
3. Append the remainder (CRC) to the original message.
4. Receiver divides by $G(x)$; zero remainder means no error.

Theorem 3.1. CRC detects all single-bit errors, all double-bit errors (if $G(x)$ has factor $(x+1)$), all odd-numbered errors, and all burst errors of length $\leq r$.

3.3 MAC Protocols

ALOHA. Transmit whenever ready; if collision, wait random time and retransmit.

• Pure ALOHA: Throughput $S = G e^{-2G}$Maximum at $G = 0.5$: $S_{\max} = 1/(2e) \approx 18.4\%$.
• Slotted ALOHA: Time divided into slots; transmit at slot boundary. $S = G e^{-G}$Maximum at $G = 1$: $S_{\max} = 1/e \approx 36.8\%$.

CSMA (Carrier Sense Multiple Access). Listen before transmitting.

• 1-persistent: If busy, wait; transmit immediately when idle. High collision probability.
• Non-persistent: If busy, wait random time before sensing again. Lower collision, higher delay.
• p-persistent: If busy, wait until idle, then transmit with probability $p$.

CSMA/CD (Collision Detection). Used in wired Ethernet (802.3). Transmit and listen simultaneously; If collision detected, send jam signal and wait random backoff.

• Binary exponential backoff: After $n$-th collision, choose random $k \in \\{0, 1, \ldots, 2^{\min(n,10)} - 1\\}$ and wait $K \times 512$ bit times.
• Minimum frame size: Must be at least $2\tau$ where $\tau$ is the round-trip propagation delay. For 10 Mbps Ethernet with $\tau = 51.2\;\mu\mathrm{s}$: minimum frame = 64 bytes.

CSMA/CD collision analysis. The sender must still be transmitting when a collision signal returns From the farthest point on the network. The worst-case round-trip propagation time is $2\tau$Where $\tau = d/v$ ($d$ is the maximum cable length, $v$ is the signal propagation speed, $2 \times 10^8$ m/s in copper). The minimum frame size is therefore:

$L_{\min} = R \times 2\tau = \frac{2Rd}{v}$

Where $R$ is the data rate.

CSMA/CA (Collision Avoidance). Used in wireless (802.11). Cannot detect collisions while Transmitting (half-duplex radio). Uses RTS/CTS handshake and inter-frame spacing (IFS).

Wi-Fi (IEEE 802.11). Wireless LAN standards operating in the 2.4 GHz, 5 GHz, and 6 GHz bands.

Key 802.11 mechanisms:

• DCF (Distributed Coordination Function): CSMA/CA with random backoff. IFS priorities: SIFS (shortest, for ACKs/CTS), PIFS (PCF), DIFS (standard data), EIFS (after error).
• RTS/CTS: Sender sends Request To Send, receiver replies with Clear To Send. Reduces hidden terminal problem.
• RTS/CTS pseudocode:

void wifi_send(frame *f) {
    while (channel_busy()) wait(DIFS);
    send_RTS();
    wait_for_CTS(timeout);
    if (received_CTS()) {
        wait(SIFS);
        send_data(f);
        wait(SIFS);
        wait_for_ACK(timeout);
        if (!received_ACK()) {
            backoff = choose_random(0, 2^min(n,10) - 1) * slot_time;
            wait(backoff);
            retry_count++;
        }
    } else {
        backoff = choose_random(0, 2^min(n,10) - 1) * slot_time;
        wait(backoff);
    }
}

• MIMO: Multiple-Input Multiple-Output. Uses multiple antennas for spatial multiplexing (simultaneous streams) and diversity (reliability). 802.11n supports up to 4x4 MIMO.
• OFDM/OFDMA: Orthogonal Frequency-Division Multiplexing divides the channel into subcarriers. OFDMA (802.11ax) allows scheduling different clients on different subcarriers simultaneously.
• BSS (Basic Service Set): An access point (AP) and its associated stations. ESS (Extended Service Set): multiple BSSs connected by a distribution system.

3.4 Ethernet (IEEE 802.3)

Frame format:

MAC address: 48-bit globally unique address. First 24 bits: OUI (organisation). Last 24 bits: Device-specific. Broadcast: FF:FF:FF:FF:FF:FF. Multicast: least significant bit of the first Octet is 1.

Ethernet evolution:

Theorem 3.3 (CSMA/CD efficiency). The maximum efficiency of CSMA/CD is:

$\eta = \frac{1}{1 + 5a}$

Where $a = \tau / T_f$ is the ratio of propagation delay to frame transmission time.

Proof. In the worst case, a collision wastes $2\tau$ time and one frame transmission time $T_f$. The useful time per cycle is $T_f$. The total cycle time is $T_f + 2\tau$ in the worst case, but On average (with the binary exponential backoff), the effective overhead is approximately $5\tau$. Thus $\eta = T_f / (T_f + 5\tau) = 1 / (1 + 5a)$. $\blacksquare$

When $a \ll 1$ (large frames or short distances), efficiency approaches 1. When $a$ approaches 1 (short frames or long distances), efficiency drops significantly. This is why minimum frame sizes Are imposed.

3.5 VLANs

A Virtual LAN (VLAN) logically segments a physical LAN into separate broadcast domains at layer 2, Without requiring separate physical infrastructure.

802.1Q frame tagging. A 4-byte tag is inserted after the source MAC address:

Trunking. Links between switches that carry traffic for multiple VLANs. Frames are tagged with Their VLAN ID on trunk links.

Benefits: Security (isolation between VLANs), broadcast containment, flexible network management, Reduced cost (no need for separate switches per segment).

3.6 Switching

Circuit switching. A dedicated path is established for the entire duration. Used in traditional Telephone networks. Constant bandwidth but inefficient for bursty data.

Packet switching. Data divided into packets, each routed independently.

• Datagram: Each packet routed independently (IP). No setup; may arrive out of order.
• Virtual circuit: Logical path established before data transfer (ATM, MPLS). Ordered delivery.

Theorem 3.2. Packet switching achieves higher utilisation than circuit switching for bursty Traffic.

Proof. Circuit switching reserves the peak rate per connection. Packet switching uses statistical Multiplexing: the sum of peak rates can exceed link capacity as long as the average aggregate rate Does not. $\blacksquare$

Switch forwarding methods. A layer-2 switch can forward frames using two strategies:

Where $L$ is the full frame length, $L_h$ is the header length (14 bytes for Ethernet), $R$ is the Link rate, and $d_{\mathrm{prop}}$ is the propagation delay.

For a path through $n$ switches:

\mathrm{Store}\mathrm{-and\mathrm}{-forward\;latency} = n \cdot \frac{L}{R} + d_{\mathrm{total}}

\mathrm{Cut}\mathrm{-through}\;latency} = \frac{L}{R} + (n-1) \cdot \frac{L_h}{R} + d_{\mathrm{total}