The multiple access problem; collisions; channel partitioning

1. How many CRC bits does G = 1101 produce?
   Stuck? Peek at 2.2.4 CRC: generator polynomial, modulo-2 division, what CRC catches

   • G of degree r (r + 1 bits); append r zeros, divide modulo 2, send data + r-bit remainder.
   • Receiver divides the whole frame: remainder 0 → accept.
   • Undetected ⇔ error pattern E is a multiple of G.
   • Catches: all single-bit errors (≥ 2 terms), all odd counts (x + 1 | G), all bursts ≤ r; (r+1)-bursts missed w.p. 2⁻⁽ʳ⁻¹⁾, longer 2⁻ʳ.

   Read lesson 2.2.4

2. Which errors does 1-D parity miss?
   Stuck? Peek at 2.2.1 Single-bit vs burst errors; redundancy; 1-D and 2-D parity

   • Single-bit vs burst; burst length = first to last damaged bit inclusive.
   • Codeword = dataword (k) + r check bits.
   • 1-D parity: detects odd numbers of flips only.
   • 2-D parity: R + C + 1 check bits; detects all 1–3-bit errors, corrects 1, misses some 4-bit rectangles.

   Read lesson 2.2.1

3. What happens on a broadcast link if two nodes send at once?
   Stuck? Peek at 0.1.2 Nodes, links, topologies, LAN/WAN and the boxes in the middle

   • Node = any device; host = node where messages start/end.
   • Point-to-point (2 nodes) vs broadcast (all hear all).
   • Simplex (one way) · half-duplex (two ways, one at a time) · full-duplex (both at once).
   • Links: mesh n(n−1)/2, star n, ring n, tree n−1, bus 1 backbone.
   • LAN (building) ⊂ WAN (cities) ⊂ the Internet (network of networks).
   • Hub repeats to all · switch delivers within a LAN · router picks the next network.

   Read lesson 0.1.2

A classroom where everyone talks at once: nobody is understood. Teachers solve it in three ways — fixed speaking turns, raising hands and being called on, or just speaking and apologising if you clash. A shared (broadcast) link needs exactly such rules, called medium access control (MAC). Our frame cannot leave the laptop until the rules say it may.

Ten stations share a 1 Mbps link by taking strict turns of equal length. Only one station has data right now. What rate does it get?

Only 100 kbps — one turn in ten — even though the other nine have nothing to send. Fixed partitioning is fair and collision-free, but wasteful when traffic is bursty.

The multiple access problem and collisions

A MAC protocol (medium access control) decides who may transmit when on a shared link. It runs in a distributed way — there is usually no referee.

Three families of MAC protocols

TDMA and FDMA (channel partitioning)

• TDMA (time division multiple access): time is cut into rounds of N slots; station i always uses slot i. Each station gets R/N, never collides, but waits for its own slot and wastes empty slots.
• FDMA (frequency division): the band is cut into N sub-bands; each station gets its own band at R/N.

Putting it together

• Shared links need a MAC protocol to avoid or recover from collisions.
• Partitioning is fair and collision-free but wastes idle capacity.
• Random access and taking turns are the alternatives.

• Channel partitioning has no collisions but wastes capacity when stations are idle.
• A collision ruins all frames involved, not just the later one.

"Fixed turns are fair but slow; free talk is fast but clashes."

Partitioning wastes idle time. Next (2.3.2): the opposite extreme — let any station send whenever it has a frame, and simply resend after collisions. How much of the channel is then actually useful?

1. NAT

   FDMA divides a 2 Mbps channel among 8 stations. Rate per station in kbps?

   Write your answer before opening the key.

2. MCQ

   Which MAC family can have collisions?

   1. TDMA
   2. FDMA
   3. Random access
   4. Taking turns
3. MSQ

   Which are true of TDMA?

   1. Each station gets R/N.
   2. Unused slots can be borrowed by busy stations.
   3. There are no collisions.
   4. A station may have to wait for its slot.
4. NAT

   TDMA, 20 stations, slot 0.5 ms. Worst-case wait (ms) for a station that just missed its slot?

   Write your answer before opening the key.

• Collision: overlapping transmissions on a shared link; all involved frames lost.
• MAC families: partitioning (TDMA/FDMA), random access (send freely, recover from collisions), taking turns (an orderly schedule).
• TDMA/FDMA: R/N per station, no collisions, idle shares wasted, wait up to (N − 1) slots.

• multiple access problem
• collision
• MAC protocol (medium access control)
• channel partitioning: TDMA, FDMA
• random access
• controlled access (taking turns)

1. Three MAC families?
   Reveal answer

   Channel partitioning, random access, taking turns.
2. TDMA rate per station?
   Reveal answer

   R/N.
3. Collision?
   Reveal answer

   Overlapping transmissions on a shared link — all frames lost.

• TDMA/FDMA share = R / N; worst-case wait = (N − 1) slot times. — N stations, equal fixed slots or bands.