Tutorial 6.3: Multiple Access Protocols and Channel Sharing

(b) 1/(2e) ≈ 0.184. Pure ALOHA maximum throughput is 18.4%.

(b) CSMA/CA. Wi-Fi uses virtual carrier sensing via RTS/CTS and NAV.

(a) One slot time. Transmission starts only at slot boundaries; collisions only occur if another node transmits in the same slot.

(b) Collision detection is difficult because the transmitter cannot listen and transmit simultaneously. In wireless, a node cannot detect collisions while transmitting due to the half-duplex nature and signal attenuation.

(c) FDMA. FDMA (Frequency Division Multiple Access) partitions the frequency spectrum.

(b) Binary exponential backoff. Ethernet uses this to reduce collision probability.

(b) Wireless networks. Hidden terminals occur when nodes are out of range of each other but can cause collisions at a common receiver.

(c) 0.5 × e^{-1} ≈ 0.184. S = G × e^{-2G} = 0.5 × e^{-1} ≈ 0.184.

(d) CSMA/CD. Under low load, collisions are rare, and CSMA/CD allows immediate transmission with detection, achieving near 100% throughput.

(b) Virtual carrier sensing. NAV indicates the duration of a channel reservation, allowing nodes to defer even if they cannot sense the carrier.

(b) Polling. Polling is a taking-turns protocol where a master node grants permission.

(b) 1. Throughput S = G e^{-G}, derivative gives G=1.

(b) Hidden terminal. RTS/CTS reserves the channel and makes other nodes aware of the ongoing transmission, mitigating hidden terminal collisions.

(b) Two frame times. Because collisions can occur if another transmission starts within one frame time before or after.

(a) The maximum propagation delay and the need to detect collisions. A frame must be long enough to be transmitted while the sender can still detect a collision (i.e., before the first bit reaches the farthest node).

(c) TDMA. TDMA provides guaranteed time slots and low jitter, ideal for constant-bit-rate traffic like voice.

(a) A node can hear a transmission but is not in the same collision domain. The node defers unnecessarily, reducing throughput.

(b) Waits for the channel to become idle, then transmits with probability 1. That is the "1-persistent" behavior.

(b) Token Ring. Token Ring uses a token-passing protocol.

(b) No need for frequency or time coordination. CDMA allows all nodes to transmit simultaneously using different codes, simplifying network planning.

(c) Ensure the channel is idle before transmission. DIFS is a period of idle time before a node can attempt to transmit.

(b) It requires synchronization. Slotted ALOHA needs all nodes to be synchronized to slot boundaries.

(b) Decreases throughput because the probability of collisions increases. Longer propagation delay means nodes may sense the channel idle while a transmission is already in progress.

(b) A designated node generates a new token. Token Ring uses a monitor node to detect token loss and regenerate it.

(b) To ensure all nodes detect a collision. The jamming signal propagates to ensure all stations are aware of the collision.

(b) CSMA/CA. Wi-Fi uses CSMA/CA for distributed channel access.

(a) e^{-1} ≈ 0.368. The probability of no other transmission in the vulnerable period (2T) is e^{-2G} = e^{-1} ≈ 0.368.

(c) No access control needed (no collisions). In full-duplex switched Ethernet, each link is point-to-point, so collisions cannot occur.

(c) CDMA. In CDMA, a nearby transmitter may overpower a distant one, making it difficult to decode the distant signal.

(c) No collisions and deterministic access. Taking-turns protocols eliminate collisions and provide guaranteed access times.

S = G × e^{-2G}.

For G=0.8: S = 0.8 × e^{-1.6} = 0.8 × 0.2019 = 0.1615 (16.15%).

For G=1.2: S = 1.2 × e^{-2.4} = 1.2 × 0.0907 = 0.1088 (10.88%).

Throughput decreases because the collision probability increases with higher offered load.

S(G) = G e^{-G}. Derivative: S'(G) = e^{-G} - G e^{-G} = e^{-G}(1 - G). Set S'=0 ⇒ 1 - G = 0 ⇒ G=1.

Second derivative: S''(G) = -e^{-G}(1-G) - e^{-G} = e^{-G}(G-2). At G=1, S''(1) = e^{-1}(-1) < 0, so it's a maximum.

Propagation delay one way = distance / speed = 2500 / (2×10^8) = 1.25×10^{-5} s = 12.5 µs.

Round-trip time = 2 × 12.5 = 25 µs.

At 10 Mbps, bits transmitted in 25 µs = 10×10^6 × 25×10^{-6} = 250 bits.

Thus, minimum frame size = 250 bits (including headers). Ethernet uses 512 bits (64 bytes) to be safe.

1. Node A sends an RTS (Request to Send) frame to node B, indicating the duration of the upcoming data transmission.

2. Node B responds with a CTS (Clear to Send) frame, also containing the duration. CTS is heard by all nodes within range of B, including hidden nodes that could not hear A.

3. Other nodes (like C) that hear the CTS set their NAV (Network Allocation Vector) for the duration, deferring transmission.

4. A then sends the data frame to B.

5. B acknowledges with an ACK.

This ensures that hidden nodes defer during the data transmission.

Nodes: A, B, C, D in a line. A is transmitting to B. C can hear B's transmission (so senses busy) but C wants to transmit to D. Since C is not in B's transmission range (or not causing interference at B), C could actually transmit to D without causing collisions. However, C defers because it senses the channel busy, wasting throughput.

This reduces overall efficiency because C unnecessarily waits.

With TDMA, each node gets 1 slot per frame. The channel is fully utilized only if all nodes have data; otherwise some slots are wasted. Efficiency = (number of nodes with data) / 10 on average. Expected number of busy nodes = 10 × 0.1 = 1, so efficiency ≈ 1/10 = 10% (plus overhead).

With Slotted ALOHA, G = total attempts per slot = 10 × 0.1 = 1. Throughput S = 1 × e^{-1} = 0.368 = 36.8%, much higher. So random access is more efficient for bursty traffic.

After 1st collision: CW=31, range [0,30].

After 2nd: CW=63, range [0,62].

After 3rd: CW=127, range [0,126].

After 4th: CW=255, range [0,254].

The node picks a random integer in that range, multiplied by the slot time.

For each cycle, the master polls each station: 5 polls × 1 ms = 5 ms overhead. Each station sends data: 5 × 10 ms = 50 ms data. Total cycle time = 55 ms. Throughput = data time / cycle time = 50/55 ≈ 0.909 = 90.9%.

If both nodes sense idle, they transmit. The collision occurs if the transmission from one node hasn't reached the other before it starts. In the worst case, the second node starts within the propagation delay of the first. The probability depends on the timing. With a small a, collisions are rare. A crude approximation: collision probability roughly a (since if the second node starts within a of the first, it may not yet have detected the carrier). More precise analysis requires modeling.

In this case, a=0.01, so ~1% chance.

Propagation delay = 1000 / (2×10^8) = 5×10^{-6} s = 5 µs.

Station delay = 10 stations × 1 bit = 10 bits. At 100 Mbps, 1 bit = 10 ns, so 10 bits = 100 ns = 0.1 µs.

Total latency = 5 µs + 0.1 µs = 5.1 µs.

Pure ALOHA max = 1/(2e) ≈ 0.184.

Slotted ALOHA max = 1/e ≈ 0.368.

Improvement factor = (1/e) / (1/(2e)) = 2. So slotted ALOHA doubles the maximum throughput.

Round-trip time = 2 × (200 / 2×10^8) = 2 × 1×10^{-6} = 2×10^{-6} s = 2 µs.

At 100 Mbps, bits in 2 µs = 100×10^6 × 2×10^{-6} = 200 bits.

Minimum frame size = 200 bits (plus some margin). Ethernet uses 512 bits.

Transmitted signals: A: 1 × (+1 +1 -1 -1) = (+1 +1 -1 -1). B: -1 × (+1 -1 +1 -1) = (-1 +1 -1 +1).

Composite = (+1-1, +1+1, -1-1, -1+1) = (0, +2, -2, 0).

Receiver A correlates with its code: dot product = (0×1) + (2×1) + (-2×-1) + (0×-1) = 0 + 2 + 2 + 0 = 4. Divide by code length (4) → data = 1. Correct.

Backoff values: 0..7 (8 choices). Probability that two nodes pick the same value = 1/8 ≈ 0.125.

If they pick the same, they will collide again on retransmission.

Recommend Slotted ALOHA or CSMA/CA with low overhead. Since traffic is bursty and infrequent, random access avoids the inefficiency of TDMA (wasted slots). Slotted ALOHA is simple and efficient for low load. Alternatively, CSMA/CA can be used with a small contention window to reduce energy consumption. Polling would be inefficient due to overhead.

Let G be the average number of frame transmission attempts per slot (including retransmissions). The vulnerable period is one slot time. A transmission is successful if no other node transmits in that slot. The number of transmissions in a slot follows a Poisson distribution with mean G. The probability that exactly zero other transmissions occur in the same slot is e^{-G}. The throughput S is the fraction of slots that contain successful transmissions, which is the probability that a transmission attempt is successful times the average number of attempts? More formally: S = G × (probability that a given attempt is successful). The probability that a given attempt is successful is the probability that no other attempts occur in that slot, which is e^{-G}. Thus S = G e^{-G}. Maximum at G=1, S=1/e.

• 1-persistent: Transmit as soon as channel is idle. High collision probability if multiple nodes are waiting, but low delay under light load.
• Non-persistent: If busy, wait a random time and try again. Reduces collisions but increases delay.
• p-persistent: With probability p transmit when idle, else wait. Used in slotted systems to balance collisions and delay.

1-persistent is good for low-load, low-latency; non-persistent for high-load; p-persistent for slotted channels like Wi-Fi (though Wi-Fi uses a different backoff).

G = number of nodes × probability per node = 10 × 0.2 = 2 attempts per slot.

Throughput S = G e^{-G} = 2 e^{-2} = 2 × 0.1353 = 0.2707 (27.1%).

The probability that a slot has a successful transmission is S = 0.2707.

DCF uses CSMA/CA. A node with data to send senses the channel. If idle for DIFS (Distributed InterFrame Space), it transmits. If busy, it waits until idle, then chooses a random backoff timer (slots). The timer decrements while the channel is idle; if the channel becomes busy, it freezes. When timer reaches zero, node transmits. If a collision occurs (no ACK), the node doubles the contention window and retries. SIFS (Short InterFrame Space) is used for ACK and RTS/CTS, having higher priority (shorter time).

Both use carrier sensing before transmission. Ethernet uses CSMA/CD: it detects collisions during transmission and aborts, using exponential backoff. Wi-Fi uses CSMA/CA: it avoids collisions through virtual carrier sensing (RTS/CTS), acknowledgments, and backoff; it cannot detect collisions because the transmitter cannot listen simultaneously. Wi-Fi also has variable channel conditions and hidden terminals. Therefore, CSMA/CD is not feasible in wireless.

In polling, overhead increases linearly with number of stations (each poll frame). For large N, the polling cycle becomes long, increasing delay and reducing throughput (fraction of time spent polling). Random access protocols like CSMA/CA have overhead that is relatively independent of N (only collisions cause overhead). However, as N grows, collision probability increases, reducing throughput. For very large N, TDMA or a hybrid may be better. Polling is suitable for small to medium N with steady traffic; random access is better for bursty traffic and large N.

Hidden terminal: A and C cannot hear each other, but both can hear B. They may transmit to B simultaneously, causing collisions. RTS/CTS: A sends RTS to B; B replies with CTS, which is heard by C (since C is within range of B). C defers. Drawbacks: Adds overhead (RTS, CTS frames) and increases latency; may not be efficient for small data frames; still susceptible to collisions if RTS frames collide.

Let G = average number of transmission attempts per frame time (including retransmissions). A frame is successful if no other frame is transmitted during the vulnerable period of 2 frame times (the frame itself plus one frame time before). The number of attempts in 2T is Poisson with mean 2G. Probability of zero other attempts = e^{-2G}. Throughput S = G × e^{-2G}. To maximize, differentiate: dS/dG = e^{-2G} - 2G e^{-2G} = e^{-2G}(1 - 2G). Set to 0 ⇒ G=0.5. S_max = 0.5 × e^{-1} = 1/(2e) ≈ 0.184.

The near-far problem occurs when a mobile station close to the base station transmits at high power, overpowering a distant station's signal, making it hard to decode the distant station. Mitigations include power control (adjusting transmission power so that all signals arrive at roughly equal power), and using orthogonal codes with low cross-correlation.

Round-trip delay = 2 × 5 = 10 µs. At 10 Mbps, bits in 10 µs = 10×10^6 × 10×10^{-6} = 100 bits. So minimum frame size = 100 bits (plus jam signal). If smaller, a collision might occur after the sender has finished transmitting, so the sender will not detect it and will assume successful transmission, leading to corrupted data.

Under light load: CSMA has very few collisions and high throughput (near 100%). Slotted ALOHA throughput is at most 36.8%. Under heavy load: CSMA suffers from increased collisions (especially if propagation delay is significant), but with backoff it can maintain reasonable throughput. Slotted ALOHA throughput drops as G increases beyond 1 (since S = G e^{-G} decreases). CSMA is more stable because it senses the channel; ALOHA is unstable at high loads.

Fairness is ensured because each station gets a turn to transmit when it holds the token. If a station has no data, it simply passes the token to the next station. This guarantees each station gets equal opportunity, and the token circulates continuously.

Carrier sense means listening to the channel before transmitting to check if it is busy. However, collisions can still occur due to propagation delay: two nodes may both sense the channel idle and transmit simultaneously before their signals reach each other. Also, in wireless, hidden terminals cause collisions even if carrier sense is used locally.

In basic TDMA, the slot is wasted; no other station can use it. More advanced dynamic TDMA can allocate idle slots to other stations, but standard TDMA does not. This is a major inefficiency.

NAV is a virtual carrier sensing mechanism. It is set by nodes when they hear RTS/CTS frames indicating the duration of a transmission. Nodes defer for that duration even if they cannot sense the physical carrier (e.g., due to being out of range of the sender). Physical carrier sensing detects actual energy on the channel. NAV provides additional protection against hidden terminals.