Controlled access: polling, token passing and its efficiency

1. After the 3rd collision, K is chosen from which range?
   Stuck? Peek at 2.3.4 Binary exponential backoff; probability of winning

   • After the n-th collision: K uniform in {0, …, 2^min(n,10) − 1}; wait K × slot; abort after 16.
   • Slot = 512 bit times (51.2 µs at 10 Mbps).
   • P(A wins) = #{K_A < K_B} / (a·b); both at range 2: win 1/4, tie 1/2.
   • Capture: A at range 2 vs B at range 4 → A wins 5/8.

   Read lesson 2.3.4

2. Name the three MAC families.
   Stuck? Peek at 2.3.1 The multiple access problem; collisions; channel partitioning

   • 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.

   Read lesson 2.3.1

3. a = ?
   Stuck? Peek at 1.3.3 RTT, bandwidth-delay product, utilisation and a = Tp/Tt

   • RTT = 2·T_p for tiny signals (add T_t / queuing if stated).
   • BDP = B × T_p bits in flight; B × RTT before any reply.
   • a = T_p / T_t.
   • Send-and-wait: U = T_t/(T_t + 2T_p) = 1/(1 + 2a); throughput = U·B.
   • To keep the link busy: about 1 + 2a units in flight.

   Read lesson 1.3.3

A teacher can call students one by one ("Ravi? Anything to say?"), or the class can pass a talking stick around the circle — only the holder may speak. Both avoid collisions completely. Networks call these polling and token passing; GATE asks for their efficiency.

A token circles a ring of N stations. A station that grabs the token sends one frame and then releases the token. Does it matter whether it releases the token right after sending, or only after its frame has gone all the way round the ring and come back?

Yes. Releasing immediately (early release) lets the next station start almost at once. Waiting for the frame to return (delayed release) idles the ring for a whole trip around it each time — a big loss when the ring is long compared with the frame.

Polling

A primary (master) node asks each station in turn whether it has data. The station sends, then the primary polls the next one. No collisions, but each poll costs time and the primary is a single point of failure.

If each station sends one frame of time T_t per poll and a poll costs T_poll, efficiency = T_t / (T_t + T_poll). E.g. T_poll = T_t/4 → 0.8.

Token passing and the ring

Ring latency = time for a bit to go once round the ring = propagation round the ring + the small delay each station adds (b bits per station): d/v + N·b/R.

Token ring efficiency

With N stations, each sending one frame per token visit, a = T_p/T_t where T_p is the propagation time once round the ring:

Where the formulas come from

ETR: each of the N stations sends T_t; the token walks once round the ring (T_p) per cycle: η = N·T_t / (N·T_t + T_p) = 1/(1 + a/N).

DTR: each station also holds the ring for its frame's full trip (T_p) before releasing: η = N·T_t / (N·T_t + N·T_p + T_p) = 1/(1 + a(N + 1)/N).

Putting it together

• Taking turns avoids collisions at the cost of polls or token walks.
• Early token release keeps a long ring busy; delayed release wastes a ring trip per frame.
• Token-ring efficiency falls as a grows.

• In token-ring a, T_p is the propagation time once round the whole ring.
• Delayed release adds the frame's return trip for every station — it hurts most when a is large.
• Polling's primary is a single point of failure; token passing must handle a lost token.

"Pass the stick early and the circle keeps talking."

Chapter 2.3 is complete: partitioning, random access, taking turns. Next (Ch 2.4): the link layer that actually carries our frame from the laptop on most wired LANs — its frame format, address types and size limits, all of which follow from what we just learned.

1. NAT

   Token ring, N = 20, a = 1. Early token release efficiency (3 decimals)?

   Write your answer before opening the key.

2. NAT

   Token ring, N = 4, a = 1. Delayed token release efficiency (3 decimals)?

   Write your answer before opening the key.

3. MCQ

   In polling, which node decides who sends next?

   1. Any idle node
   2. The primary (master)
   3. The node with the token
   4. Nobody — random choice
4. NAT

   Ring of 1 km (v = 2 × 10⁸ m/s), 100 stations each adding 2 bits, at 100 Mbps. Ring latency in µs?

   Write your answer before opening the key.

5. MSQ

   Which are true?

   1. Token passing has no collisions.
   2. DTR is never better than ETR.
   3. Polling has no overhead.
   4. Higher a lowers token ring efficiency.

• Polling: primary asks each station; η = T_t/(T_t + T_poll); single point of failure.
• Token passing: only the token holder sends (token holding time).
• Ring latency = d/v + N·b/R.
• ETR η = 1/(1 + a/N); DTR η = 1/(1 + a(N+1)/N).

• polling, primary
• token passing, token, token holding time
• token ring, ring latency
• early vs delayed token release efficiency

1. ETR efficiency?
   Reveal answer

   1/(1 + a/N).
2. DTR efficiency?
   Reveal answer

   1/(1 + a(N + 1)/N).
3. Ring latency?
   Reveal answer

   d/v + N·b/R.

• ETR 1/(1 + a/N); DTR 1/(1 + a(N+1)/N). — N stations, one frame per token visit, a = ring propagation / frame time.
• Ring latency = d/v + N·b/R. — b = bits of delay added at each station.