Loading learning content...
Many indigenous cultures use a talking stick—a ceremonial object passed among participants during council meetings. Only the person holding the stick may speak; everyone else must listen respectfully. When finished, the speaker passes the stick to the next person. No one is interrupted. No one is silenced. Everyone gets their turn.
Token passing implements precisely this protocol for computer networks. Instead of a talking stick, a special control frame called a token circulates among stations. Only the station holding the token may transmit. When finished, it passes the token to the next station. The result: collision-free, fair access without requiring any central controller.
This elegant distributed algorithm eliminates polling's single point of failure while preserving its deterministic access guarantees. Token passing represents a masterclass in distributed systems design—coordination without centralization.
By the end of this page, you will understand token passing architectures—how tokens circulate in logical rings, the distinction between token ring (IBM 802.5) and token bus (IEEE 802.4), token capture and release protocols, priority mechanisms, and the critical fault tolerance features that allow token networks to recover from station failures and lost tokens.
Token passing is a distributed controlled access protocol where stations form a logical ring, and a special control frame—the token—circulates around this ring. The fundamental rules are:
Token Passing Rules:
The Token Frame:
The token is a small, special-purpose frame that conveys transmission rights:
+------------+--------+---------+-----------+
| Delimiter | Access | Status | Delimiter |
| (1 byte) | (1 B) | (1 byte)| (1 byte) |
+------------+--------+---------+-----------+
Access byte:
- Token bit: 0 = free token, 1 = busy (data frame follows)
- Priority bits: current priority level (0-7)
- Reservation bits: requested priority for next token
Status byte:
- Address recognized
- Frame copied
- Error indicators
Token States:
| State | Meaning | What Happens Next |
|---|---|---|
| Free Token | No station is transmitting | Stations may capture token |
| Busy (Data Following) | Token holder is transmitting | Other stations relay frames |
| Captured | Station has taken token | Station transmits its data |
| Released | Station finished transmitting | Token becomes free |
The logical ring determines token flow, but the physical topology can be different. Token Ring (802.5) uses a physical ring or star-wired ring topology. Token Bus (802.4) uses a physical bus but creates a logical ring through explicit successor addresses. This separation provides deployment flexibility.
IEEE 802.5 Token Ring is the most widely known token passing protocol, developed by IBM and standardized by IEEE. It uses a physical ring topology (or star-wired ring using a central hub called a MAU - Multistation Access Unit).
Token Ring Operation Sequence:
Token Ring Frame Format:
+------+------+--------+--------+--------+---------+------+------+
| SD | AC | FC | DA | SA | Data | FCS | ED |
| 1B | 1B | 1B | 6B | 6B | ≤4500B | 4B | 1B |
+------+------+--------+--------+--------+---------+------+------+
SD = Start Delimiter (unique bit pattern violating encoding rules)
AC = Access Control (token bit, priority, reservation)
FC = Frame Control (frame type: LLC data, MAC control, etc.)
DA = Destination Address (48-bit MAC address)
SA = Source Address (48-bit MAC address)
Data = Payload (up to 4500 bytes for 4 Mbps, larger for 16 Mbps)
FCS = Frame Check Sequence (32-bit CRC)
ED = End Delimiter (unique bit pattern)
Critical Design Elements:
| Element | Purpose | Implementation |
|---|---|---|
| Differential Manchester | Self-clocking encoding | Bit flip at mid-bit always |
| Start/End Delimiters | Mark frame boundaries | Code violations (no mid-bit transition) |
| Active Monitor | Ring integrity maintenance | One station elected as monitor |
| Latency Buffer | Minimum ring latency | 24-bit buffer in monitor station |
| Frame Stripping | Prevent endless circulation | Sender removes its own frames |
Original Token Ring required stations to wait until their transmitted frame returned before releasing the token. 16 Mbps Token Ring introduced 'early token release'—the sender releases the token immediately after transmitting the last bit of its frame. This dramatically improves efficiency on larger rings.
IEEE 802.4 Token Bus combines the deterministic access of token passing with the simpler cabling of a bus topology. Stations are connected to a shared bus, but they form a logical ring by each station knowing its successor address.
Why Token Bus?
Token Ring requires physical ring wiring (or star-wired ring). Token Bus provides:
Token Bus Operation:
Token Bus Token Frame:
+----------+-------------+-------------+---------+
| Preamble | Frame Ctrl | Dest Addr | FCS |
| (≥1 byte)| (1 byte) | (2 or 6 B) | (4 bytes)|
+----------+-------------+-------------+---------+
Frame Control = Token frame type identifier
Dest Addr = Address of successor station (next in logical ring)
Key Differences from Token Ring:
| Aspect | Token Ring (802.5) | Token Bus (802.4) |
|---|---|---|
| Physical topology | Ring (or star-wired ring) | Bus (linear or branched) |
| Logical ring | Implicit (physical order) | Explicit (successor addresses) |
| Token passing | Token bit in circulating frame | Separate token frame to successor |
| Frame stripping | By sender (frame circles ring) | All stations hear; sender confirms receipt |
| Cable type | Shielded twisted pair | Coaxial (75Ω broadband) |
| Speed | 4/16/100 Mbps | 1/5/10 Mbps |
| Primary use | Office LANs | Industrial networks (MAP) |
Token Bus requires complex ring maintenance algorithms: adding stations to the logical ring, removing failed stations, initializing the ring on startup. These algorithms (Claim Token, Solicit Successor, etc.) add significant protocol complexity compared to Token Ring's simpler physical ring approach.
The precise rules for capturing and releasing the token determine the protocol's efficiency and fairness characteristics.
Token Capture Rules:
A station may capture the token if:
Token Holding Time (THT):
To ensure fairness, a station may hold the token for a maximum time called THT:
When token arrives:
THT_remaining = Token_Holding_Time
While (have_data AND THT_remaining > 0):
transmit_one_frame()
THT_remaining -= time_to_transmit_frame
Release token to successor
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
import timefrom dataclasses import dataclassfrom typing import Optional, Listfrom queue import Queue @dataclassclass Token: priority: int = 0 reservation: int = 0 is_free: bool = True @dataclassclass DataFrame: destination: int source: int data: bytes priority: int = 0 class TokenRingStation: """Implements a Token Ring station with priority support.""" def __init__(self, address: int, successor: int, token_holding_time_ms: float = 10.0): self.address = address self.successor = successor self.tht = token_holding_time_ms self.tx_queue: Queue[DataFrame] = Queue() self.has_token = False def receive_token(self, token: Token) -> Optional[Token]: """Handle receiving the token.""" if not token.is_free: # Token is busy, frame follows - relay it return None # Free token received - can we capture it? highest_priority_frame = self._peek_highest_priority() if highest_priority_frame is None: # No data to send - pass token immediately return self._pass_token(token) if highest_priority_frame.priority < token.priority: # Our priority too low - pass token return self._pass_token(token) # Capture token! return self._transmit_with_token(token) def _transmit_with_token(self, token: Token) -> Token: """Transmit frames while holding the token.""" self.has_token = True tht_remaining = self.tht start_time = time.time() while tht_remaining > 0 and not self.tx_queue.empty(): frame = self.tx_queue.get() # Transmit frame (in real implementation) transmission_time = self._transmit_frame(frame) tht_remaining -= transmission_time # Check if we've exceeded THT elapsed = (time.time() - start_time) * 1000 if elapsed >= self.tht: break # Release token self.has_token = False return self._release_token(token) def _release_token(self, old_token: Token) -> Token: """Create and release a new free token.""" new_token = Token( priority=old_token.reservation, # Promote reservation to priority reservation=0, is_free=True ) return new_token def _pass_token(self, token: Token) -> Token: """Pass the token without transmitting.""" # Make reservation if we have high-priority data waiting frame = self._peek_highest_priority() if frame and frame.priority > token.reservation: token.reservation = frame.priority return tokenEarly vs Late Token Release:
| Release Strategy | When Token Released | Efficiency | Use Case |
|---|---|---|---|
| Late Release | After transmitted frame returns | Lower on large rings | Original 4 Mbps Token Ring |
| Early Release | Immediately after last bit sent | Higher throughput | 16 Mbps Token Ring, FDDI |
Late Release Example (4 Mbps Token Ring):
Time 0: Station A captures token, starts transmitting frame
Time T: Frame fully transmitted
Time T+L: Frame circles ring, returns to A
Time T+L: A strips frame, releases new token
Channel idle time: L (ring latency) after each frame
Early Release (16 Mbps Token Ring):
Time 0: Station A captures token, starts transmitting frame
Time T: Frame fully transmitted, A immediately releases token
Time T: Station B can capture token while A's frame still circulating!
Channel idle time: Minimal (multiple frames in flight)
With early token release, multiple data frames can be circulating the ring simultaneously—each from a different sender. This dramatically increases throughput on large rings where ring latency would otherwise dominate. FDDI (Fiber Distributed Data Interface) uses early release to achieve high utilization on its 100 Mbps, 100 km rings.
Token Ring implements a sophisticated priority mechanism that allows urgent traffic to preempt normal traffic. This is crucial for time-sensitive applications like voice and video.
Priority and Reservation Bits:
The Access Control byte contains:
Access Control Byte:
+-----+---+-----+---+
| PPP | T | RRR | M |
+-----+---+-----+---+
3b 1b 3b 1b
P = Priority bits (0-7)
T = Token bit (0=free, 1=busy)
R = Reservation bits (0-7)
M = Monitor bit (1=seen by active monitor)
Priority Operation Rules:
When a station receives a free token:
IF my_frame_priority >= token_priority THEN
Capture token, transmit frame
Set token priority = my_frame_priority
ELSE
If my_frame_priority > token_reservation THEN
Set token_reservation = my_frame_priority
Pass token
ENDIF
When a station releases the token:
IF I raised the priority THEN
New_token_priority = MAX(reservation, old_priority)
I am responsible for lowering priority later
ELSE
New_token_priority = reservation
New_reservation = 0
ENDIF
The Priority Mechanism Prevents Starvation:
A station that raises the priority becomes a stacking station and is obligated to restore the priority level after its traffic completes. This ensures low-priority traffic eventually gets served.
| Priority Level | Traffic Type | Example Applications |
|---|---|---|
| 7 (Highest) | Network Management | Ring recovery, beaconing |
| 6 | Real-time Critical | Industrial control, safety systems |
| 5 | Real-time | Voice over IP, video conferencing |
| 4 | Interactive | Telnet, SSH, database queries |
| 3 | Normal Batch | Email, web browsing |
| 2 | Background Batch | File transfers, backups |
| 1 | Low Priority | Network monitoring, logging |
| 0 (Lowest) | Best Effort | Any non-priority traffic |
Token passing protocols must handle several failure scenarios. Unlike polling (where the primary can simply retry), token passing requires distributed recovery algorithms.
Common Fault Scenarios:
The Active Monitor:
Token Ring designates one station as the Active Monitor (AM) responsible for ring maintenance:
Active Monitor Responsibilities:
- Detect and recover from lost tokens (timer-based)
- Remove orphaned frames (strip frames that circulate twice)
- Provide ring latency buffer (minimum 24 bits)
- Detect duplicate tokens
- Generate new token if lost
- Pass monitoring to Standby Monitor if it fails
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596
from enum import Enum, autoimport threadingimport time class RingState(Enum): NORMAL = auto() TOKEN_LOST = auto() BEACONING = auto() RECOVERY = auto() class ActiveMonitor: """ Active Monitor for Token Ring fault recovery. One station per ring is elected as Active Monitor. """ # Timeout values (in milliseconds) VALID_FRAME_TIMEOUT = 10 # Max time between valid frames TOKEN_ROTATION_TIMEOUT = 50 # Max time for complete token rotation BEACON_TIMEOUT = 16 # Time to beacon before recovery def __init__(self, address: int, ring): self.address = address self.ring = ring self.state = RingState.NORMAL self.last_token_seen = time.time() self.last_frame_seen = time.time() self.monitoring = True # Start monitoring thread self.monitor_thread = threading.Thread(target=self._monitor_loop) self.monitor_thread.start() def _monitor_loop(self): """Continuous monitoring for ring faults.""" while self.monitoring: current_time = time.time() if self.state == RingState.NORMAL: # Check for token timeout token_age = (current_time - self.last_token_seen) * 1000 if token_age > self.TOKEN_ROTATION_TIMEOUT: print(f"[AM] Token timeout! Age: {token_age:.1f}ms") self._handle_token_lost() elif self.state == RingState.BEACONING: # Recovery in progress pass time.sleep(0.001) # 1ms polling interval def _handle_token_lost(self): """Initiate lost token recovery.""" self.state = RingState.TOKEN_LOST # Step 1: Send Claim Token frames print("[AM] Sending Claim Token frames...") for _ in range(3): self.ring.broadcast_claim_token(self.address) time.sleep(0.001) # Step 2: If we win arbitration, generate new token if self._win_claim_arbitration(): print("[AM] Won arbitration, generating new token") self._generate_new_token() self.state = RingState.NORMAL else: print("[AM] Lost arbitration, new AM exists") self._become_standby_monitor() def _generate_new_token(self): """Create a new token and inject into ring.""" new_token = Token(priority=0, reservation=0, is_free=True) self.ring.inject_token(new_token) self.last_token_seen = time.time() def on_token_seen(self): """Called when a valid token passes through.""" self.last_token_seen = time.time() if self.state != RingState.NORMAL: print("[AM] Ring recovered, returning to normal") self.state = RingState.NORMAL def on_frame_received(self, frame): """Process received frame, strip orphans.""" self.last_frame_seen = time.time() # Check monitor bit - if set, frame has circled once if frame.monitor_bit: # Orphan frame! Strip it print(f"[AM] Stripping orphan frame from {frame.source}") return None # Don't forward else: # Set monitor bit, forward frame.monitor_bit = True return frameBeaconing:
When a station detects a hard fault (upstream neighbor failure), it enters beacon mode:
Beaconing Process:
1. Station detects no signal from upstream
2. Station transmits Beacon frames continuously:
- "Beaconing: Station X, Fault Domain: Y"
3. Downstream stations relay beacon, enter beacon mode
4. When upstream station recovers, beacon stops
5. Beacon originator (or AM) initiates ring recovery
Fault Domain:
The beacon frame identifies the fault domain—the segment between the beaconing station and its upstream neighbor (NAUN - Nearest Active Upstream Neighbor). This allows network administrators to quickly locate physical faults.
Physical Token Ring installations use relays in the MAU (hub) that can bypass failed stations. When a station loses power or is disconnected, the relay 'wraps' the ring around the failed station, maintaining ring continuity. This hardware mechanism complements the software recovery protocols.
FDDI (Fiber Distributed Data Interface) represents the evolution of token passing to backbone-scale networks. Operating at 100 Mbps over fiber optic cable spanning up to 100 km, FDDI brought token passing to metropolitan-area networks.
Key FDDI Features:
| Feature | Specification |
|---|---|
| Data Rate | 100 Mbps |
| Maximum Ring Length | 100 km (single mode fiber) |
| Maximum Stations | 500 |
| Encoding | 4B/5B + NRZI |
| Frame Size | Up to 4,500 bytes |
| Token Protocol | Timed Token Rotation (TTR) |
| Redundancy | Dual counter-rotating rings |
Timed Token Rotation (TTR):
FDDI introduces a more sophisticated token management algorithm based on Target Token Rotation Time (TTRT):
FDDI Token Management:
Target_Token_Rotation_Time (TTRT) = negotiated value (e.g., 8ms)
When token arrives:
Token_Rotation_Time (TRT) = time since token last arrived
Token_Holding_Time (THT) = TTRT - TRT
IF (TRT < TTRT) THEN
// Token arrived early - can transmit asynchronous data
Transmit async data for up to THT
ENDIF
// Always allowed to transmit synchronous data (real-time)
Transmit sync data up to pre-allocated bandwidth
Release token
This algorithm guarantees that synchronous (real-time) traffic always meets its deadlines, while asynchronous traffic uses leftover capacity.
Dual Ring Fault Tolerance:
FDDI's most distinctive feature is its dual counter-rotating rings:
This provides exceptional resilience for backbone networks where downtime is extremely costly.
While FDDI is largely superseded by Gigabit Ethernet, its timed token rotation algorithm influenced many subsequent protocols. FDDI concepts appear in industrial protocols like PROFIBUS and in wireless standards. The dual-ring architecture remains a template for resilient backbone design.
We've explored token passing as a distributed controlled access protocol. Let's consolidate the key concepts:
What's Next:
In the next page, we'll explore Reservation systems—where stations reserve future transmission slots in advance. We'll see how reservation protocols combine the determinism of controlled access with the flexibility of dynamic bandwidth allocation.
You now understand token passing as a distributed controlled access protocol—how tokens circulate, the differences between Token Ring and Token Bus, priority and reservation mechanisms, and fault recovery. Next, we'll examine reservation-based protocols that allow stations to pre-schedule their transmissions.