101
0/228
Loading content...
Token passing promises collision-free, fair access—but at what cost? The token itself consumes bandwidth as it circulates. Stations must wait for the token even when the network is lightly loaded. How do we quantify this trade-off?
Efficiency analysis transforms intuition into mathematics. By deriving precise formulas for throughput and latency, we can answer critical questions:
This analytical foundation enables engineers to design token networks correctly the first time, rather than discovering performance problems after deployment. The formulas we derive here are directly applicable to Token Ring, FDDI, and any token-based protocol.
By the end of this page, you will be able to derive and apply token passing efficiency formulas—calculating maximum throughput under light and heavy load, understanding the impact of the 'a' parameter (propagation/transmission ratio), analyzing latency bounds, and determining when token passing is preferable to contention protocols.
Before deriving efficiency formulas, we must define the parameters that characterize a token passing network.
Network Parameters:
| Parameter | Symbol | Description |
|---|---|---|
| Data Rate | R (or C) | Channel capacity in bits per second |
| Number of Stations | N | Stations on the ring |
| Ring Latency | τ (tau) | Total propagation delay around the ring |
| Frame Size | L | Size of data frame in bits |
| Token Size | T_token | Size of token in bits |
| Token Holding Time | THT | Maximum time a station may hold token |
Derived Parameters:
| Parameter | Symbol | Formula | Meaning |
|---|---|---|---|
| Frame Transmission Time | T_f | L / R | Time to transmit one frame |
| Token Transmission Time | T_t | T_token / R | Time to transmit token |
| Propagation Parameter | a | τ / T_f | Ratio of propagation to transmission |
| Ring Latency in Frames | — | τ × R / L = a | Frames that "fit" on the ring |
The Critical 'a' Parameter:
The propagation parameter a characterizes the relationship between signal propagation and data transmission:
a = τ / T_f = (propagation delay) / (frame transmission time)
= (d/v) / (L/R)
= (d × R) / (v × L)
where:
Interpretation of 'a':
| Value of a | Network Characteristic | implication |
|---|---|---|
| a << 1 | Short ring, large frames | High efficiency possible |
| a ≈ 1 | Ring delay ≈ frame time | Moderate efficiency |
| a >> 1 | Long ring, small frames | Significant overhead |
The 'a' parameter appears in nearly every MAC protocol efficiency formula. It captures how much of the channel is 'occupied' by propagation delay relative to useful transmission. Large 'a' means much of the time, bits are traveling through the medium rather than carrying useful data.
Example Calculation:
Given:
τ = d / v = 100,000 m / (2 × 10⁸ m/s) = 0.5 ms = 500 μs
T_f = L / R = 36,000 bits / (100 × 10⁶ bps) = 360 μs
a = τ / T_f = 500 μs / 360 μs ≈ 1.39
With a ≈ 1.39, the ring delay exceeds the frame transmission time—this is a challenging environment for any MAC protocol.
For Token Ring (4 Mbps, 200m, 1000-byte frames):
τ = 200 / (2 × 10⁸) = 1 μs
T_f = 8000 / (4 × 10⁶) = 2000 μs = 2 ms
a = 1 μs / 2000 μs = 0.0005
With a = 0.0005 << 1, propagation delay is negligible—very favorable for efficiency.
Let's first analyze the original 4 Mbps Token Ring with late token release—the station releases the token only after its transmitted frame returns.
Scenario: All N Stations Have One Frame to Send
Time Line for One Complete Cycle:
Station 1:
- Receives token (token circled the ring): τ time
- Transmits frame: T_f time
- Frame circles ring and returns: τ time
- Releases new token
Station 2:
- Token arrives: τ/N time (avg)
- Transmits frame: T_f time
- Frame returns: τ time
- Releases token
... (repeat for all N stations)
Per-Station Time (Late Token Release):
Time per station = T_f (transmit) + τ (frame return) + token overhead
≈ T_f + τ (ignoring small token transmission time)
Total Cycle Time:
T_cycle = N × (T_f + τ)
Useful Data in Cycle:
Useful = N × T_f (each station transmits one frame)
Efficiency:
η = Useful / Total = (N × T_f) / [N × (T_f + τ)]
= T_f / (T_f + τ)
= 1 / (1 + τ/T_f)
= 1 / (1 + a)
Notice that efficiency depends on 'a' but NOT on N (number of stations). Adding more stations doesn't change efficiency—it just increases total throughput (more frames per cycle) and cycle time proportionally.
Late Token Release Efficiency Formula:
┌─────────────────────────────────┐
│ │
│ η_late = 1 / (1 + a) │
│ │
└─────────────────────────────────┘
Numerical Examples:
| Scenario | a value | Efficiency η |
|---|---|---|
| Token Ring (4Mbps, small ring) | 0.0005 | 99.95% |
| Token Ring (16Mbps, 1km) | 0.002 | 99.8% |
| FDDI (100Mbps, 100km) | 1.39 | 41.8% |
| Satellite token (500ms RTT) | 100 | 0.99% |
Key Insight:
Late token release works excellently when a << 1 (local networks). But for large rings or high-speed networks, efficiency drops dramatically because the sender must wait for frame return before releasing the token.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
def calculate_a(ring_length_m: float, data_rate_bps: float, frame_size_bits: int, prop_velocity: float = 2e8) -> float: """ Calculate the 'a' parameter for a token ring network. Args: ring_length_m: Total ring length in meters data_rate_bps: Data rate in bits per second frame_size_bits: Frame size in bits prop_velocity: Signal velocity (default: 2e8 m/s for fiber/copper) Returns: The 'a' parameter (propagation/transmission ratio) """ tau = ring_length_m / prop_velocity # Propagation delay (seconds) t_f = frame_size_bits / data_rate_bps # Transmission time (seconds) return tau / t_f def late_release_efficiency(a: float) -> float: """Calculate efficiency for late token release.""" return 1 / (1 + a) def early_release_efficiency(a: float, N: int) -> float: """Calculate efficiency for early token release.""" if a < 1: return 1 / (1 + a/N) else: return 1 / (a * (1 + 1/N)) # Example calculationsprint("=== Token Ring Efficiency Analysis ===\n") # Scenario 1: Classic Token Ringa_tr4 = calculate_a(200, 4e6, 8000)print(f"4 Mbps Token Ring (200m, 1KB frames):")print(f" a = {a_tr4:.6f}")print(f" Late release η = {late_release_efficiency(a_tr4):.4%}")print() # Scenario 2: 16 Mbps Token Ringa_tr16 = calculate_a(1000, 16e6, 8000)print(f"16 Mbps Token Ring (1km, 1KB frames):")print(f" a = {a_tr16:.6f}")print(f" Late release η = {late_release_efficiency(a_tr16):.4%}")print(f" Early release η (N=50) = {early_release_efficiency(a_tr16, 50):.4%}")print() # Scenario 3: FDDIa_fddi = calculate_a(100000, 100e6, 36000)print(f"FDDI (100km, 4.5KB frames):")print(f" a = {a_fddi:.4f}")print(f" Late release η = {late_release_efficiency(a_fddi):.2%}")print(f" Early release η (N=100) = {early_release_efficiency(a_fddi, 100):.2%}")Early Token Release (used in 16 Mbps Token Ring and FDDI) dramatically improves efficiency on large or high-speed rings. The station releases the token immediately after transmitting its last bit, without waiting for the frame to return.
Why Early Release Helps:
With late release, the channel is idle while the frame circles back. With early release, the next station can capture the token and start transmitting immediately, potentially overlapping with the previous frame's propagation.
Analysis (Heavy Load, All Stations Active):
Case 1: a < 1 (Ring delay < Frame time)
The token is small and propagates quickly. Multiple frames can be in transit simultaneously.
Time between token arrivals at successive stations ≈ T_f / N
Cycle time = N × (T_f/N + token transit)
≈ T_f + τ (one frame's worth of data continuously)
With N stations each sending 1 frame:
Efficiency = N × T_f / (N × T_f/N + τ) = N×T_f / (T_f + τ)
But normalized to single-frame time:
η = 1 / (1 + a/N) for a < 1
Case 2: a > 1 (Ring delay > Frame time)
Common in large FDDI rings. The ring delay dominates.
When a > 1:
Token must traverse the ring (τ time) before returning
Even with early release, ring latency limits throughput
Cycle time ≈ N × τ/N + processing
≈ τ (ring latency dominates)
Useful time per cycle = N × T_f
But τ = a × T_f, so:
Efficiency = N × T_f / (a × T_f × (1 + 1/N))
= 1 / (a × (1 + 1/N))
For large N:
η ≈ 1/a for a > 1
Combined Early Release Efficiency Formula:
┌────────────────────────────────────────────┐
│ │
│ η_early = 1 / (1 + a/N) if a < 1 │
│ │
│ η_early = 1 / (a(1 + 1/N)) if a ≥ 1 │
│ │
│ η_early ≈ 1/(1+a/N) general approx │
│ │
└────────────────────────────────────────────┘
| Network | a | N | η (Late) | η (Early) | Improvement |
|---|---|---|---|---|---|
| Token Ring 4Mbps | 0.0005 | 20 | 99.95% | 99.998% | Minimal |
| Token Ring 16Mbps | 0.002 | 50 | 99.8% | 99.996% | Minimal |
| FDDI (1km ring) | 0.014 | 100 | 98.6% | 99.986% | 1.4% |
| FDDI (100km ring) | 1.39 | 100 | 41.8% | 71.1% | 70%! |
| Very large ring | 5.0 | 100 | 16.7% | 49.5% | 196%! |
For FDDI with a=1.39, late release gives only 41.8% efficiency—unacceptable for a 100 Mbps backbone. Early release improves this to 71%, and with 100 active stations, approaches 72%. This is why FDDI mandated early release from the start.
Beyond efficiency percentages, we need to understand absolute throughput—how many bits per second can the network actually carry?
Maximum Throughput:
S_max = η × R
where:
η = efficiency (from previous formulas)
R = raw data rate (bps)
Token Ring Throughput Examples:
| Network | R | η | S_max |
|---|---|---|---|
| TR 4Mbps (late) | 4 Mbps | 99.95% | 3.998 Mbps |
| TR 16Mbps (early) | 16 Mbps | 99.996% | 15.999 Mbps |
| FDDI 100km (early) | 100 Mbps | 71% | 71 Mbps |
Normalized Throughput:
Often we express throughput as a fraction of channel capacity:
S = (useful bits transmitted) / (total channel capacity)
= Throughput / R
= η
So normalized throughput equals efficiency—the fraction of channel capacity carrying useful data.
Throughput as a Function of Load:
Unlike CSMA/CD (where throughput collapses under overload), token passing maintains near-maximum throughput even under heavy load:
Throughput (S)
▲
│
S_max ─┼───────────────────────* Token passing
│ /
│ /
│ /
│ /
│ /
│ *─────────* CSMA/CD (collapses)
│ /
│ /
│ /
│ /
│/
└──────────────────────────► Offered Load (G)
1 2 3
Token Passing Advantage:
| Load Condition | Token Passing | CSMA/CD |
|---|---|---|
| Light load | Slight latency overhead | Excellent |
| Medium load | Near maximum throughput | Good |
| Heavy load | Maintains efficiency | Collapses to ~18% |
| Overload | Deterministic degradation | Severe throughput collapse |
Token passing has higher latency at light load because a station must wait for the token even when the channel is idle. CSMA/CD allows immediate transmission on an idle channel. For latency-critical applications with sparse traffic, this token wait can be problematic.
Throughput Under Varying Frame Sizes:
Frame size affects the 'a' parameter and thus efficiency:
a = τ/T_f = τ × R / L
Smaller frames → larger 'a' → lower efficiency.
Example: FDDI (100 km ring, 100 Mbps)
| Frame Size | a | η (early, N=100) | Throughput |
|---|---|---|---|
| 100 bytes | 6.25 | 13.8% | 13.8 Mbps |
| 500 bytes | 1.25 | 44.2% | 44.2 Mbps |
| 1500 bytes | 0.42 | 70.4% | 70.4 Mbps |
| 4500 bytes | 0.14 | 87.7% | 87.7 Mbps |
This strong dependency on frame size is why FDDI encouraged large frames (up to 4,500 bytes) and why small-frame protocols on large rings perform poorly.
Latency measures the time from when a frame is ready until it's delivered. Token passing provides bounded worst-case latency—a critical property for real-time systems.
Components of Token Ring Latency:
Token Rotation Time (TRT):
The Token Rotation Time is the time for the token to make one complete circuit:
Under light load (only one station transmitting):
TRT_min = τ + T_token ≈ τ
Under heavy load (all N stations transmitting):
TRT_max = N × THT + τ
where:
THT = Token Holding Time (max time each station holds token)
τ = Ring latency
Worst-Case Access Delay:
A station's worst-case wait for the token occurs when:
┌─────────────────────────────────────────────────────┐
│ │
│ Worst-case delay = TRT_max - ε │
│ │
│ ≈ N × THT + τ │
│ │
└─────────────────────────────────────────────────────┘
Example: N=50 stations, THT=10ms, τ=1ms
Worst-case ≈ 50 × 10ms + 1ms = 501ms
With THT=1ms:
Worst-case ≈ 50 × 1ms + 1ms = 51ms
Key Insight:
The worst-case latency is bounded and deterministic. Unlike CSMA/CD where a station might wait indefinitely during heavy load, token passing guarantees access within TRT_max.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
from dataclasses import dataclassfrom typing import Tuple @dataclassclass TokenRingLatencyParams: """Parameters for token ring latency analysis.""" num_stations: int # N token_holding_time_ms: float # THT ring_latency_ms: float # τ frame_size_bytes: int # L data_rate_mbps: float # R @property def frame_transmission_ms(self) -> float: """Time to transmit one frame in milliseconds.""" return (self.frame_size_bytes * 8) / (self.data_rate_mbps * 1e6) * 1000 def token_rotation_time(self, active_stations: int = None) -> Tuple[float, float]: """ Calculate TRT under various loads. Returns: (min_trt, max_trt) in milliseconds """ if active_stations is None: active_stations = self.num_stations # Minimum: no station has data, token just circulates min_trt = self.ring_latency_ms # Maximum: all active stations use full THT max_trt = active_stations * self.token_holding_time_ms + self.ring_latency_ms return (min_trt, max_trt) def worst_case_access_delay(self) -> float: """Calculate worst-case access delay (just missed token).""" _, max_trt = self.token_rotation_time() return max_trt def average_access_delay(self) -> float: """Approximate average access delay (50% load, uniform arrival).""" min_trt, max_trt = self.token_rotation_time() avg_trt = (min_trt + max_trt) / 2 # Average wait is half the TRT return avg_trt / 2 def end_to_end_latency(self, source_pos: int, dest_pos: int) -> Tuple[float, float]: """ Calculate min/max end-to-end latency from source to destination. Assumes positions are 0 to N-1, going clockwise. """ # Propagation delay from source to destination if dest_pos >= source_pos: hops = dest_pos - source_pos else: hops = self.num_stations - source_pos + dest_pos prop_delay = (hops / self.num_stations) * self.ring_latency_ms # Minimum: token arrives immediately, transmit, propagate min_latency = self.frame_transmission_ms + prop_delay # Maximum: wait full TRT, then transmit and propagate max_latency = self.worst_case_access_delay() + self.frame_transmission_ms + prop_delay return (min_latency, max_latency) # Example analysisparams = TokenRingLatencyParams( num_stations=50, token_holding_time_ms=10.0, ring_latency_ms=0.5, frame_size_bytes=1500, data_rate_mbps=16) print(f"Token Ring Latency Analysis")print(f"===========================")print(f"Stations: {params.num_stations}")print(f"THT: {params.token_holding_time_ms} ms")print(f"Ring latency: {params.ring_latency_ms} ms")print(f"Frame transmission: {params.frame_transmission_ms:.3f} ms")print() min_trt, max_trt = params.token_rotation_time()print(f"Token Rotation Time:")print(f" Minimum (idle): {min_trt:.2f} ms")print(f" Maximum (full load): {max_trt:.2f} ms")print() print(f"Access Delay:")print(f" Worst-case: {params.worst_case_access_delay():.2f} ms")print(f" Average: {params.average_access_delay():.2f} ms")Token Holding Time creates a trade-off: larger THT improves throughput (fewer token passes) but increases worst-case latency. For real-time applications, THT must be small enough to meet deadline requirements. FDDI's TTRT mechanism explicitly manages this balance.
FDDI's Timed Token Rotation (TTR) protocol provides guaranteed bandwidth for synchronous (real-time) traffic while maximizing utilization with asynchronous traffic.
Key FDDI Parameters:
| Parameter | Symbol | Description |
|---|---|---|
| Target Token Rotation Time | TTRT | Negotiated target for token cycle |
| Token Rotation Time | TRT | Actual time since last token |
| Token Holding Time | THT | Time available for async transmission |
| Synchronous Allocation | SA | Guaranteed bandwidth per station |
FDDI Token Operation:
When token arrives:
1. Calculate THT = TTRT - TRT
(where TRT = time since token last arrived)
2. Always transmit synchronous traffic (up to SA allocation)
3. IF THT > 0 THEN
// Token arrived early, extra time available
Transmit asynchronous traffic for up to THT
ELSE
// Token arrived late, no async allowed
Pass token immediately after sync traffic
ENDIF
FDDI Synchronous Bandwidth Guarantee:
Let:
Maximum Synchronous Utilization:
Total synchronous time per TTRT cycle ≤ TTRT - τ
Σ SA_i ≤ TTRT - τ
or:
Σ SA_i ≤ TTRT × (1 - a/N) approximately
Guaranteed Bandwidth per Station:
With synchronous allocation SA_i:
Bandwidth_i = SA_i / TTRT_max
where TTRT_max ≤ 2 × TTRT (under worst-case conditions)
To guarantee SA_i bandwidth even in worst case:
Bandwidth_i ≥ SA_i / (2 × TTRT)
Asynchronous Capacity:
Async capacity = (time available) - (sync time) - (token overhead)
available_async = TTRT - Σ SA_i - τ
Async efficiency ≈ available_async / TTRT
| Parameter | Value | Calculation |
|---|---|---|
| TTRT | 8 ms | Negotiated |
| Ring latency τ | 0.5 ms | 100 km ring |
| Available sync time | 7.5 ms | TTRT - τ |
| Station 1 sync | 1 ms | 12.5% of capacity |
| Station 2 sync | 1 ms | 12.5% of capacity |
| Station 3-50 sync | 0 ms | No guaranteed BW |
| Total sync | 2 ms | 25% of TTRT |
| Async capacity | 5.5 ms | 68.75% of TTRT |
FDDI's TTR ensures that synchronous traffic always gets through within 2×TTRT (worst case), regardless of async load. This makes FDDI suitable for industrial control and multimedia, where deadline guarantees matter.
Ethernet (CSMA/CD) and Token Ring were fierce competitors in the LAN market. Understanding their performance differences illuminates when each approach excels.
Efficiency Comparison at Heavy Load:
CSMA/CD Efficiency:
η_csma = 1 / (1 + 5.4a) (approximate formula)
Token (Early Release) Efficiency:
η_token = 1 / (1 + a/N)
Crossover Point:
Token passing is more efficient when:
1/(1 + a/N) > 1/(1 + 5.4a)
Solving: a > N/5.4 ≈ N/5
So token passing wins for large 'a' (high-speed, large networks), while CSMA/CD wins for small 'a' (low-speed, small networks).
| a | CSMA/CD η | Token (N=50) η | Winner |
|---|---|---|---|
| 0.001 | 99.5% | 99.998% | Token (marginal) |
| 0.01 | 95.0% | 99.98% | Token |
| 0.1 | 64.9% | 99.8% | Token |
| 0.5 | 27.0% | 99.0% | Token |
| 1.0 | 15.6% | 98.0% | Token |
| 5.0 | 3.6% | 90.9% | Token (25× better) |
Latency Comparison:
| Load | CSMA/CD | Token Ring |
|---|---|---|
| Light | Immediate (channel idle) | Wait for token (up to TRT) |
| Medium | Low collision rate | Predictable, bounded |
| Heavy | Unpredictable, can spike | Bounded: max = N×THT |
| Overload | Collapse, extreme delays | Graceful degradation |
The Key Trade-off:
Despite token ring's superior heavy-load efficiency, Ethernet dominated the market. Why? Lower cost, simpler installation, good-enough performance for typical office traffic (bursty, light-to-medium load), and the economic advantages of commodity hardware. Performance isn't everything—TCO (Total Cost of Ownership) matters.
We've analyzed token passing efficiency in depth. Let's consolidate the key formulas and insights:
What's Next:
In the final page, we'll compare all controlled access protocols—polling, token passing, and reservation—side by side. We'll analyze when to use each, their trade-offs, and how modern protocols combine their best features.
You now have quantitative tools for analyzing token passing efficiency. You can calculate throughput, bound latency, and understand the trade-offs that make token passing suitable for high-speed, large-ring, or real-time applications. These analytical skills apply to any deterministic MAC protocol design.