[Computer Networking] 15. Link Layer: Error Detection and Multiple Access Protocols

Services Provided by the Link Layer
======================================

1. Framing
   - Encapsulates network layer datagrams into frames
   - Includes MAC addresses in frame header

2. Link Access
   - Access control on shared media (multiple access protocols)
   - Frame delivery using MAC addresses

3. Reliable Delivery
   - Uses ARQ on error-prone links (wireless)
   - Usually not used on wired links

4. Error Detection and Correction
   - Bit error detection: parity, CRC, etc.
   - Error correction: FEC (Forward Error Correction)

Link Layer Implementation
===========================

[Application Layer]
[Transport Layer]        CPU / Software
[Network Layer]
-----------------------
[Link Layer]             NIC (Hardware + Firmware)
[Physical Layer]

Single Parity Bit (Even Parity)
=================================

Data:        1011010
Parity bit:  0  (so that the count of 1s is even)
Transmitted: 10110100

Received:    10110110  (5th bit error)
Count of 1s: 5 (odd) --> Error detected!

Limitation: Cannot detect even number of simultaneous bit errors

Two-Dimensional Parity
========================

Data + Row Parity:
  1 0 1 1 | 1
  0 1 1 0 | 0
  1 1 0 1 | 1
  ----------
  0 0 0 0   (Column parity)

Error occurred:
  1 0 1 1 | 1
  0 1 0 0 | 0  <-- Row parity mismatch
  1 1 0 1 | 1
  ----------
  0 0 1 0    <-- Column parity mismatch
        ^
  3rd column, 2nd row --> Error location identified and correctable

Internet Checksum Computation
================================

1. Divide data into 16-bit words
2. Add all words using one's complement addition
3. Take the one's complement of the result as the checksum

Example:
  Word 1: 0110 0110 0110 0000
  Word 2: 0101 0101 0101 0101
  -------------------------
  Sum:    1011 1011 1011 0101
  Checksum: 0100 0100 0100 1010  (one's complement)

Verification: At receiver, adding all words including checksum
              should yield 1111 1111 1111 1111

CRC Computation Process
=========================

1. Determine generator polynomial G (shared by sender and receiver)
   Example: G = 1001 (x^3 + 1), r = 3 bits

2. Append r zeros to data D
   D = 101110, D * 2^r = 101110 000

3. Compute remainder R by XOR division of D * 2^r by G

   101110 000 / 1001
   ----------------
        101110 000
   XOR  1001
        --------
         0101 10 000
   XOR    1001
          --------
          0000 1000 0
   XOR          1001
               ------
               0001 0
   Remainder R = 011

4. Transmitted bits: Concatenate D and R = 101110 011

5. Receiver: Divide received bits by G, remainder = 0 means no error

CRC's Strong Detection Capability
====================================

Errors detectable with r-bit CRC:
  - All single-bit errors
  - All 2-bit errors (with appropriate G selection)
  - Odd number of bit errors (if G contains x+1 as factor)
  - Burst errors of r bits or fewer

Standard CRC Polynomials:
  CRC-8:  x^8 + x^2 + x + 1
  CRC-16: x^16 + x^15 + x^2 + 1
  CRC-32: Used in Ethernet, WiFi, ZIP, etc.
          Very strong detection with 32-bit remainder

Multiple Access Protocol Classification
==========================================

1. Channel Partitioning
   - TDMA, FDMA, CDMA
   - No collisions but inefficient

2. Random Access
   - ALOHA, Slotted ALOHA, CSMA, CSMA/CD
   - Collisions allowed, detection/recovery mechanisms

3. Taking-Turns
   - Polling, Token Passing
   - Middle ground compromise

TDMA Operation
================

Time frame:
  [Slot1][Slot2][Slot3][Slot4][Slot1][Slot2][Slot3][Slot4]
   NodeA  NodeB  NodeC  NodeD  NodeA  NodeB  NodeC  NodeD

Advantage: No collisions
Disadvantage: Even if only Node A has data, it can only transmit in its slot
  --> Only 1/N of channel bandwidth usable (waste)

FDMA Operation
================

Frequency
  ^
  |  [Node D band]
  |  [Node C band]
  |  [Node B band]
  |  [Node A band]
  +--------------------> Time

Same pros/cons as TDMA
  - No collisions but bandwidth waste

Pure ALOHA
===========

Operation:
  1. If a frame is ready, transmit immediately
  2. On collision, retransmit immediately with probability p, wait with (1-p)

Time:
  [A transmits]
      [B transmits]  <-- Overlaps with A, collision!
                    [A retransmits]
                         [C transmits]  <-- No collision

Maximum efficiency: 1/(2e) = ~18%
  (Only 18% of channel capacity used for actual transmission)

Slotted ALOHA
===============

Time slots:
  | Slot 1  | Slot 2  | Slot 3  | Slot 4  | Slot 5  |
  | A sends | A+B col.| B sends |         | C sends |
  | Success | Failure | Success | Empty   | Success |

Maximum efficiency: 1/e = ~37%
  (Twice Pure ALOHA)

Assumptions:
  - All frames are the same size
  - Time is synchronized into slots
  - Transmission starts only at slot boundaries

CSMA Operation
================

1. Carrier Sense (Listen before talk)
   - Channel idle --> Transmit
   - Channel busy --> Wait

2. Why collisions still occur: Propagation delay!

Time
  |
  | A starts transmitting
  |   [A's signal traveling toward B...]
  |   B senses channel: "Idle!" --> B also starts transmitting
  |      [Collision!]
  v

The greater the propagation delay, the higher the collision probability

CSMA/CD Operation
====================

1. NIC receives frame and senses channel
2. If channel is idle, start transmission
3. Collision detected during transmission:
   a. Stop transmission immediately
   b. Send Jam signal (48 bits)
   c. Binary Exponential Backoff

Binary Exponential Backoff:
  After nth collision, randomly choose from 0 ~ (2^n - 1) and wait

  1st collision: Choose from 0 or 1
  2nd collision: Choose from 0, 1, 2, 3
  3rd collision: Choose from 0 ~ 7
  ...
  10th collision: Choose from 0 ~ 1023 (capped at 10)

CSMA/CD Efficiency Formula
=============================

Efficiency = 1 / (1 + 5 * d_prop / d_trans)

d_prop:  Maximum propagation delay (max distance between two nodes)
d_trans: Transmission time for maximum-size frame

Properties:
  - d_prop -> 0: efficiency -> 1 (ideal)
  - d_trans -> infinity: efficiency -> 1
  - Efficient with large frames and short distances

Polling Protocol
==================

[Master]
    |
    |--> "Node A, your turn" --> [Node A] transmits
    |
    |--> "Node B, your turn" --> [Node B] transmits (no data, pass)
    |
    |--> "Node C, your turn" --> [Node C] transmits
    |
    |--> Back to Node A...

Disadvantages:
  - Polling overhead (polling messages)
  - Polling latency (waiting for turn)
  - Single point of failure if master node fails

Token Passing Protocol
========================

   [A] --> [B] --> [C] --> [D]
    ^                       |
    |_______________________|
         (Token circulation)

Operation:
  1. Token arrives at A
  2. If A has data: transmit data, then pass token to B
  3. If A has no data: pass token directly to B
  4. Repeat

Advantages: Fairness guaranteed, no collisions
Disadvantages:
  - Token overhead
  - Recovery needed if token is lost
  - Network failure if one node fails

Protocol Comparison Summary
==============================

Protocol     | Efficiency | Delay    | Fairness | Complexity
-------------+------------+----------+----------+-----------
TDMA         | Low (1/N)  | Guaranteed| Fair    | Simple
FDMA         | Low (1/N)  | Guaranteed| Fair    | Simple
Pure ALOHA   | 18%        | Variable | Fair     | Simple
Slotted ALOHA| 37%        | Variable | Fair     | Simple
CSMA/CD      | High       | Variable | Fair     | Medium
Polling      | High       | Poll delay| Variable| Medium
Token        | High       | Token delay| Fair   | High