This paper presents a scheme to improve the efficiency of radio MAC protocols in the case of broadcast and multicast transmissions, like TCP/IP multicasting. First, the reliability problems with broadcast packets and their consequences are analysed. Then the Robust Broadcast scheme is presented, which decreases the probability of loss of broadcast packets over MAC protocols based on CSMA/CA. Finally, the new protocol is simulated against other simple solutions to show how it performs.
Common Wireless LANs based on CSMA/CA MAC protocol do include broadcasting, directly translated from their wired counterpart. However transmission by radio is fundamentally different than on a wire, and unicast transmission by radio already includes specific mechanisms to adapt to the specific channel conditions, whereas broadcast transmission includes usually none.
The first main use of broadcast messages is for network management. Protocols such as TCP/IP try to minimise the use of broadcasting, but still requires it for functionalities related to discovery, such as ARP, DHCP and network autoconfiguration in IPv6. Netbios (Windows networking) over TCP/IP or Netbeui makes a very extensive use of broadcast messages to discover and keep track of the state of the network.
Broadcast and multicast messages are also used by some applications which need to distribute information to multiple nodes. These are mostly multimedia applications, such as gaming, audio/video multicasting or conferencing.
Of course, those applications using broadcast and multicast take into account the fact that broadcast transmissions are unreliable. Network management messages are repeated (for example, the number of ARP requests is 4) and multimedia coding accommodates data loss [2] (usually up to a few percent).
For broadcast and multicast packets, the problem is even worse than just performance. The transport layer can't include any acknowledgment and retransmission mechanism, due to the non defined number of recipient and the disparity of the reception conditions between them. The MAC level can't provide either any acknowledgment and retransmission scheme for the exact same reason.
On the other hand, the level of reliability expected for broadcast
messages is not as high as for unicast (there is no performance
problem). The data loss rate accommodated by the broadcast
applications is usually in the order of one percent (see previous
section).
3.1 Unicast techniques
To overcome packet losses on the medium, the MAC protocols used on
Wireless LANs use MAC level acknowledgments and retransmissions.
For each packet received correctly, the receiver immediately sends back a positive acknowledgment to the sender. This acknowledgment is embedded in the protocol, so guaranteed not to collide with any other transmission. The sender will keep retransmitting its packet until it receives the acknowledgment (or its timeout expires).
The main restriction is that this mechanism supposes a unique receiver, and can't work with an undefined number of receivers (none or multiple) as in the case of broadcast messages.
Another technique to detect collisions is RTS/CTS [4]. Each packet is preceded by a handshake between the sender and the receiver to ensure that the medium is free. The handshake is composed of a request transmitted by the sender (the RTS) and a reply by the receiver (the CTS) which confirm that it is able to receive. The information contained in the RTS and CTS packets performs medium reservation and solves the hidden node problem [4].
The same restriction as for acknowledgment applies : the receiver must be unique, so this scheme doesn't work with broadcast messages.
3.2 Channel errors
The Bit Error Rate (BER) on the radio waves is much higher that on a
wire, due to propagation phenomena (attenuation and fading). The
normal condition on a wire is a BER lower than 10-9. The
BER on a radio is usually much higher and goes up under certain
conditions (large range, obstacles, noise...).
The BER experienced over the radio depends on the transmission and reception techniques, but is closely linked to the attenuation between the sender and the receiver. This relation between BER and attenuation is generally of exponential form, which implies that when the attenuation is lower than the value corresponding to the sensitivity, the packet losses are marginal, and that they tend to be high otherwise (the system works well, or poorly).
Section 6.1 details simulation results showing channel errors for broadcast and unicast transmissions.
To overcome channel errors for broadcast packets, the protocol can use some very classical techniques like FEC or multiple transmissions, or limit the range of the device.
In CSMA/CD (Ethernet), the physical layer is able to detect collisions in the transmitter and so is able to retransmit the failed packets. The radio hardware doesn't have this ability, so the protocol relies on the MAC level acknowledgments to detect collisions. As broadcast packets are not acknowledged, the protocol can't detect collisions.
Most wireless data MAC protocols use CSMA/CA, with a slotted contention. The probability of collision derive from the probability of two nodes choosing the same slot for transmission. 802.11 has a 16 slots contention window, so in theory a 1/16 probability of having two nodes contending for the medium to collide (in fact, as the node having chosen the lowest slot number transmits and contends immediately for the next packet before the other has elapsed its count of slots, this probability is higher). Of course, a higher number of nodes contending will yield a higher probability of collision, and a higher contention window a lower collision rate.
Section 6.2 details simulations showing collision rate for broadcast and unicast messages.
Robust Broadcast is a technique trying to overcome those protocol collisions with minimal impact on the network performance.
Using RTS/CTS is the most interesting solution, because of its transparency and the medium reservation feature of the mechanism (giving an advantage towards hidden nodes). Using RTS/CTS for broadcast messages requires almost no change of the MAC protocol. No new field is added in the packet header and no change is required in the receiver or in the collision detector, which ensures backward compatibility. The only change is that before each broadcast, the sender has to choose a collision detector and to perform the RTS/CTS handshake with it.
Because of the possibility of hidden nodes, this scheme can't avoid all collisions in every nodes, but the range extension given by the CTS should help in that respect.
Another way to detect collisions would be to use packet acknowledgment for broadcast : the collision detector has just to acknowledge each broadcast packet on the medium. It would require a few modifications to the protocol : the broadcast packet must include a new field for the address of the collision detector and the collision detector must be able to read that field and act upon it. This might also lead to packets repeated on the medium and in the network stacks of the receivers.
Packet acknowledgment in theory is more powerful than RTS/CTS, because it guarantees that the message was correctly received by the sender of the acknowledgment, whereas RTS/CTS doesn't detect channel errors. In practice, for broadcasting, this doesn't make any difference because the medium condition between each pair of nodes is totally uncorrelated, so the correct or bad reception of the message by one node doesn't give us any hint on the state at the other nodes.
Then, the sender transmits a RTS addressed to the collision detector. If the node receives the corresponding CTS returned by the collision detector, the node sends the broadcast packet (to the broadcast address). If no CTS is received, the node performs a backoff and retries later (as it would do for an unicast packet).
No change is needed in the receiver behaviour, and any node can be a collision detector.
A simple optimisation of the scheme is to send the packet without RTS/CTS for the last attempt (before to timeout), avoiding problems due to a bad collision detector.
In networks having a base station (or a central coordinator), the scheme can use the base station for that purpose. But, this strategy doesn't cover the base station itself (as a broadcast sender) and the case of ad-hoc networks.
Another strategy is to use the source of the last message sent over the medium that wasn't sent by the node itself. The scheme knows for sure that this node exists and is active.
An advantage of this second solution is that each attempt to send the broadcast message is likely to use a different collision detector. This second strategy should also provide a timeout to discard the address used as the collision detector, and if there hasn't been a message on the medium for a period of time, not to try to detect collisions at all. In this case, the traffic is low, so the probability of collision is also low.
The model implements MAC level acknowledgments and retransmissions (up to 4), and RTS/CTS (for packets larger than 250 B).
Robust Broadcast (when selected) applies to every broadcast packet regardless of its size except for the last attempt.
The maximum packet size is 1500 B (non fragmented). All other parameters conform to 802.11 [1] (CWmin = 16 ; SIFS = 28 µs ; Slot = 50 µs ; Headers = 50 B).
The voice traffic model simulates a voice stream over IP. It generates constant size packet at fixed interval. The load is 32 kb/s, the interval between packets 20 ms and the IP overhead 32 B.
We have taken voice traffic as an example, because it is easy to characterise, but all the results will apply to other multimedia applications (like gaming), and to a large extent to management messages.
The data traffic model simulates a large data transfer over TCP. It is a simple bimodal distribution. Each packet is either big (maximum size) or small (40 B), the probability of being small is 1/3. Packets are sent as fast as the link can manage (fully loaded).
More information on the traffic models and their behaviour may be found in [5].
This confirms the analysis of section 3.1. Retransmission, as any diversity technique, allows a gain of a few dB in the usable attenuation, adding in this case nearly 10 dB of attenuation to unicast packets compared to broadcast packets (however, unicast transmissions need a much better reliability than broadcast).
At the same time, the simulation shows that in most of the usable
range of the device, the rate of failure of broadcast packets remains
low (below 0.5 %).
6.2 Packet failures
This set of simulations compares Robust Broadcast with using standard
broadcast and unicast techniques (for reference). We have also
evaluated two other solutions to reduce the collision losses, the
first is to transmit each broadcast packet on the medium twice
(x2) and the second is to simply increase the size of the
contention window for every node of the network to 64 slots instead of
16 (CW64).
The network is composed of one broadcast (or unicast) node loaded with a voice traffic and an increasing number of unicast nodes (using the data traffic model) contending for the medium. Figure 6.2 shows the packet failure rate of these different solutions. As we measure only the packet failure rate, these results are quite independent of the traffic nature (arrival rate, packet size...).
With only one unicast node fully loaded, the probability of loosing a broadcast packet is already 10 %, and increases with a higher contention rate. The four retransmission of unicast packets is usually enough to bring that value to reasonable level (but due to the unicast TCP performance problem [3], this parameter should be set to a higher value for such highly loaded networks).
Robust Broadcast reduces the level of failures to the one experienced by unicast packets (and again with only 4 retransmissions). On the other hand, duplicating each broadcast message (x2) or increasing the contention window to 64 (CW64) give a significant improvement, but still leave a significant packet failure rate.
To analyse how those results scale with a different traffic, the same simulations have been performed with the throughput of the broadcast node being 128 kb/s instead of 32 kb/s (quadruple the size of each broadcast packet). The results are shown in figure 6.4 (the failure rates in this case are the same as in figure 6.2).
Duplicating each broadcast message (x2) reduces the available network throughput by the amount of information duplicated (in this case, 32 kb/s or 128 kb/s, plus the overhead, minus the packets discarded due to timeout). Increasing the contention window to 64 (CW64) has also a significant impact on the network performance, especially for small number of contending nodes.
On the other hand, the impact of using Robust Broadcast is very small (comparable to the difference between using broadcast and unicast). The curve of unicast and Robust Broadcast are very similar because the sender in both case has exactly the same behaviour (backoff and then retransmit). The added overhead per packet of RTS/CTS in the case of Robust Broadcast is compensated by the reduced penalty of collisions over the unicast and broadcast solutions.
An interesting feature of RTS/CTS shown on those graph is that when the number of nodes increase, the throughput increase. This is because the overhead of collision with RTS/CTS is low, and increasing the number of nodes decrease the average number of slots between packets. The additional reason is that the available bandwidth is fairly shared between all the nodes contending, and, with a higher number of nodes, the portion of the broadcast traffic is proportionally reduced (and it uses a less efficient packet size than the data nodes).
Robust Broadcast fits totally transparently in a 802.11 network and
allows it to overcome most of the collision losses for broadcast
transmissions. Simulations have shown that it reduces those losses to
very low level, as low as for unicast transmissions, without adding
any significant overhead to the network.
8 References