CSS334 — Link Layer (Part 1) Cheat Sheet

Exam-ready summary | Lecture 11 | All topics included

0. Quick Recap: Encapsulation Down the Stack

Analogy: Letter → envelope (transport) → shipping box with label (network) → truck with route tag (link). Each layer adds its own wrapper and strips it on arrival.

1. Link Layer: What It Does

• Responsible for transferring a datagram from one node to the physically adjacent next node over a single link
• "Adjacent" = directly connected by a wire, fiber, or wireless channel (no router in between)
• A datagram may travel over many different link types end-to-end (e.g., Wi-Fi → Ethernet → Fiber)
• Each link type may offer different services (e.g., reliable delivery or not)

Key Terminology

Transportation Analogy

Princeton → JFK (limo) → Geneva (plane) → Lausanne (train)
SIIT device → Wi-Fi (802.11) → Ethernet (802.3ab) → Fiber to ISP

2. Link Layer Services

Core Services (always present)

Additional Services

3. Where Is the Link Layer Implemented?

• In every host and router, inside the Network Interface Card (NIC)
• NIC implements both Link Layer and Physical Layer
• Connected to host via system bus (e.g., PCI/PCIe)
• Combination of hardware + software + firmware

Sending NIC: encapsulates datagram into frame, adds error-checking bits
Receiving NIC: checks for errors, extracts datagram, passes up to network layer

Common IEEE Standards (Memorise the speeds)

4. Error Detection

$\boxed{D | EDC \xrightarrow{\text{bit-error prone link}} D' | EDC' \rightarrow \text{check if } D' \text{ is OK}}$

• D = data to protect (may include header fields)
• EDC = Error Detection and Correction bits (redundancy appended to data)

⚠️ Error detection is not 100% reliable — some errors may slip through. Larger EDC = better detection.

Three Techniques

5. Parity Checking

Single-Bit Parity

• Append one extra bit so total number of 1s is even (even parity)
• Can only detect single-bit errors — cannot correct, cannot detect 2-bit errors
• Example: 0111000110101011 → parity bit = 1 (makes total 1s even)

Two-Dimensional (2D) Bit Parity — Can Detect AND Correct

1. Arrange data bits into a grid (rows × columns)
2. Add a parity bit for each row (rightmost column)
3. Add a parity bit for each column (bottom row)
4. If 1 bit flips → both its row parity AND column parity fail → intersection = exact error location → flip it back

Data bits:          Row parity:
1 0 1 0 1      |   1
1 1 1 1 0      |   0
0 1 1 1 0      |   1
0 0 1 0 1      |   0
-----------        -
Col parity:
0 0 0 0 0          0  ← corner (parity of parities)

Analogy: Like a Sudoku cross-reference — row parity and column parity pinpoint the exact wrong cell.

6. Internet Checksum

Goal: Detect errors (flipped bits) in transmitted TCP/IP segments.

Sender:

1. Treat segment contents as sequence of 16-bit integers
2. Compute one's complement sum of all integers
3. Place result in the checksum field

Receiver:

1. Recompute checksum of received segment
2. Not equal → error detected ❌ | Equal → no error detected ✅ (errors may still exist!)

Analogy: A receipt total — if the items don't add up to the total, something was wrong.

7. CRC — Cyclic Redundancy Check

Most powerful of the three. Widely used in Ethernet and 802.11 Wi-Fi.

Terms

$\boxed{\text{CRC} = (m \cdot 2^n) \bmod d}$

Steps:

1. Append $n$ zeros to $m$ (shift left by $n$ bits)
2. XOR divide the padded message by $d$
3. Remainder = CRC bits
4. Transmit: $m | \text{CRC}$

XOR rules: $0 \oplus 0 = 0$, $0 \oplus 1 = 1$, $1 \oplus 0 = 1$, $1 \oplus 1 = 0$
Receiver: divide received bits by same $d$ → remainder = 0 means no error; non-zero = error.

CRC Worked Example

Given: $m = 101110$, $d = 1001$ (= $X^3 + 1$), $n = 3$

Step 1: Append 3 zeros → 101110000

Step 2: XOR divide by 1001:

         1 0 1 0 1 1
        ─────────────────
1001 )  1 0 1 1 1 0 0 0 0
        1 0 0 1
        ───────
          0 1 0 1
          0 0 0 0
          ───────
            1 0 1 0
            1 0 0 1
            ───────
              0 1 1 0
              0 0 0 0
              ───────
                1 1 0 0
                1 0 0 1
                ───────
                  1 0 1 0
                  1 0 0 1
                  ───────
                    0 1 1  ← remainder = CRC

CRC = 011
Transmitted: 101110 + 011 = 101110011

Polynomial Notation

Can detect all burst errors of length ≤ $n+1$ bits.

8. Multiple Access Links & Protocols

Two Types of Links

The Problem: Collision

• Shared channel: if 2+ nodes transmit simultaneously → collision (signals corrupt each other)
• Need a MAC (Multiple Access Control) protocol — distributed coordination of who transmits when
• Coordination must use the channel itself (no separate control channel)

Ideal MAC Protocol (for channel of rate $R$)

1. 1 node transmitting → uses full $R$
2. $M$ nodes transmitting → each gets average $R/M$
3. Fully decentralised — no master node, no clock sync
4. Simple to implement

9. MAC Protocol Taxonomy

Multiple Access Control (MAC)
├── Channel Partitioning
│   ├── TDMA (Time Division)
│   └── FDMA (Frequency Division)
├── Random Access
│   ├── CSMA
│   ├── CSMA/CD  ← Ethernet (wired)
│   └── CSMA/CA  ← Wi-Fi 802.11 (wireless)
└── Controlled Access ("Taking Turns")
    ├── Polling
    └── Token Passing

10. Channel Partitioning Protocols

TDMA — Time Division Multiple Access

• Channel time divided into rounds; each of $N$ stations gets a fixed slot per round
• Unused slots go idle — even if only 1 station has data
• Each station max rate = $R/N$ regardless of demand

Round: [ Sta.1 ][ Sta.2 ][ Sta.3 ][ Sta.4 ][ idle ][ idle ]

Analogy: Round-table meeting — everyone gets exactly 1 minute to speak, even if they have nothing to say.

FDMA — Frequency Division Multiple Access

• Channel spectrum divided into fixed frequency bands
• Each station assigned its own band — transmits anytime within its band
• Unused bands go idle

Analogy: Radio stations — each gets its own frequency, no interference, but frequency is wasted when not broadcasting.

11. Random Access Protocols

• No pre-coordination — when a node has data, it transmits at full rate $R$
• Collision → detect it → recover via randomised retransmission

CSMA — Carrier Sense Multiple Access

• "Listen before you talk"
  • Channel idle → transmit
  • Channel busy → defer

⚠️ Collisions still happen due to propagation delay — two nodes listen, both hear idle, both start transmitting, then signals collide mid-wire before either hears the other.

• Longer cable = more propagation delay = higher collision probability
• Wasted time = entire frame transmission time when collision occurs

CSMA/CD — Collision Detection (Ethernet)

• Extension of CSMA: also monitors the wire while transmitting
• Collision detected immediately → abort transmission (don't waste sending the whole frame)
• Collision detection: easy in wired (compare sent vs received signal), difficult in wireless

Analogy: Polite conversationalist — starts talking, but immediately stops if someone else also starts.

Ethernet CSMA/CD Algorithm (Step-by-Step)

1. Receive datagram from network layer → create frame
2. Sense channel:
     Idle → begin transmitting
     Busy → wait until idle, then transmit
3. No collision during entire transmission → DONE ✅
4. Collision detected mid-transmission:
     → Abort transmission
     → Send JAM SIGNAL (alerts all nodes a collision occurred)
5. Binary Exponential Backoff:
     After m-th collision:
       Pick K randomly from {0, 1, 2, …, 2^m − 1}
       Wait K × 512 bit-times
     → Go back to step 2

$\boxed{K \in {0, 1, \ldots, 2^m - 1}, \quad \text{wait} = K \times 512 \text{ bit-times}}$

More collisions = longer and more random wait — prevents nodes from colliding again immediately.
After 10 collisions, $K$ drawn from ${0, \ldots, 1023}$ — very spread out.

12. Taking Turns Protocols

Why "Taking Turns"?

Polling

• A master node invites each slave node to transmit in turn (round-robin)
• Slave can only transmit when invited (polled)
• Used with "dumb" devices (e.g., Bluetooth keyboard)

Drawbacks: polling overhead, latency, single point of failure (master node fails → whole system stops)

Token Passing

• A token (special control frame) is passed sequentially from node to node
• A node can transmit only when it holds the token
• After transmitting (or if nothing to send), pass token to next node
• Used in: Token Ring (IEEE 802.5), FDDI

Drawbacks: token overhead, latency, single point of failure (token lost → system stops)

Analogy: Microphone passed around at a meeting — you can only speak when you're holding it.

MAC Protocol Comparison

CSMA/CD → Ethernet (wired)
CSMA/CA → Wi-Fi 802.11 (wireless — Collision Avoidance because detection is impossible wirelessly)

13. MAC Address

• 48-bit hardware address, written as 6 hex bytes separated by colons or dashes
• Example: 02:0A:95:9D:68:16

$\boxed{\underbrace{OO:1A:3F}_{\text{OUI — Organisationally Unique Identifier (manufacturer)}} : \underbrace{F1:4C:C6}_{\text{UAA — device-specific serial}}}$

• OUI = first 3 bytes, assigned to each manufacturer by IEEE
• UAA = last 3 bytes, assigned by manufacturer per device
• Fixed — assigned at manufacture, tied to the NIC hardware (doesn't change when you move networks)
• Each NIC port has its own MAC address (3-port NIC = 3 different MACs)
• Broadcast MAC: FF:FF:FF:FF:FF:FF — all nodes on the LAN receive it

Bit 7 of First Byte (U/L bit)

• 0 = Universally administered (real, manufacturer-assigned)
• 1 = Locally administered (virtual / randomly generated MAC — modern phones randomise this for privacy)

MAC vs IP Address

IP changes when you move networks (DHCP gives you a new one).
MAC never changes — it's the hardware identity.

14. ARP — Address Resolution Protocol

Problem: You know a neighbour's IP address, but you need its MAC address to send a frame.

ARP works only within the same subnet — to reach a different subnet, you send to the router's MAC instead.

ARP Table

• Every IP node maintains an ARP table (also called ARP cache)
• Entry format: < IP address ; MAC address ; TTL >
• TTL ≈ 20 minutes — entries auto-expire and are re-learned

ARP Process (Step-by-Step)

Scenario: Host A wants to send to Host B, but B's MAC is not in A's ARP table.

Step 1 — ARP Request (Broadcast)

A sends to: FF:FF:FF:FF:FF:FF  (all nodes on LAN receive this)
  Source MAC:  71-65-F7-2B-08-53  (A)
  Source IP:   137.196.7.23
  Target IP:   137.196.7.14       ← "Who has this IP?"
  Target MAC:  00-00-00-00-00-00  (unknown)

Step 2 — ARP Reply (Unicast)

B responds directly back to A:
  Target IP:   137.196.7.14
  Target MAC:  58-23-D7-FA-20-B0  ← "That's me, here's my MAC"

Step 3 — Cache Entry

A adds to ARP table:
  IP addr       | MAC addr          | TTL
  137.196.7.14  | 58-23-D7-FA-20-B0 | 20 min

Analogy: Shouting in a room: "Does anyone know the address for 137.196.7.14?" The right person raises their hand and replies directly.

Promiscuous Mode

• Normally, a NIC checks if the destination MAC matches its own MAC before accepting a frame
• Promiscuous mode: NIC accepts all frames regardless of destination MAC
• Used by: packet sniffers (Wireshark), network analysers
• This is how you can capture all traffic on a network segment

15. Routing to Another Subnet — MAC Changes at Every Hop ⚠️

Scenario: A (111.111.111.111) → Router R → B (222.222.222.222)

Critical exam point: MAC addresses change at every hop. IP addresses stay the same end-to-end.

Step 1 — A sends frame to Router R (not to B!)

Frame:
  MAC src:  74-29-9C-E8-FF-55   ← A's MAC
  MAC dst:  E6-E9-00-17-BB-4B   ← R's LEFT interface MAC (NOT B's MAC!)
  IP src:   111.111.111.111
  IP dst:   222.222.222.222

A knows R's MAC via ARP (A ARPs for R's IP = first-hop gateway address)

Step 2 — Router R receives frame

• Strips frame header → extracts IP datagram
• Looks up routing table for 222.222.222.222
• Determines outgoing interface → ARPs for B's MAC if not cached

Step 3 — R sends new frame to B

Frame:
  MAC src:  1A-23-F9-CD-06-9B   ← R's RIGHT interface MAC (changed!)
  MAC dst:  49-BD-D2-C7-56-2A   ← B's MAC
  IP src:   111.111.111.111      ← unchanged
  IP dst:   222.222.222.222      ← unchanged

Step 4 — B receives frame

• Strips frame header → IP datagram reaches B's network layer
• IP src/dst unchanged throughout entire journey ✓

The Key Rule (Exam Critical ⚠️)

Analogy: IP is like the final destination label on a package (never changes). MAC is like the "next truck" sticker (replaced at every warehouse/router along the way).