Carrier sense multiple access
Carrier sense multiple access (CSMA) is a contention-based MAC scheme that closely resembles the dynamics of human communication. It implements a rule we all learned in childhood: Don’t interrupt! With CSMA, circuitry is provided through which a LAN adapter can determine if the medium is being used by another LAN adapter. When the LAN adapter receives a message, to be transmitted across the LAN, from its host computer, it first checks the medium to determine if the medium is currently in use (i.e., the “carrier sense” part). If the medium is in use by another system, the LAN adapter must not transmit. If it is idle, the LAN adapter is free to transmit. By obeying the “don’t interrupt” rule, CSMA avoids a significant number of collisions.
CSMA is an access scheme that requires a broadcast medium and is capable of supporting multiple systems in the same LAN (i.e., the “multiple access” part). Therefore, CSMA is designed to function over a logical bus topology.
Notice this means that when the medium is not being used, the LAN adapter has immediate access—we say there is no low load delay. This seems like a very desirable feature, however, there is a somewhat hidden cost associated with it. Notice that if two LAN adapters need to transmit and decide that the medium is available at exactly the same time, a collision will occur and bandwidth will be lost.
CSMA and a Busy LAN
In carrier sense multiple access (CSMA), operation when the medium is idle is trivial. The LAN adapter simply transmits. But what happens when the medium is busy?
There are two basic flavors of CSMA, distinguished by their performance when a busy medium is detected. These are classified as nonpersistent CSMA and persistent CSMA. An analogy will underscore the difference.
Every office environment requires a certain degree of interaction between the people who work there. It is fairly common for someone to walk up to a colleague's office to ask them a question or pass on a message. What happens if the colleague is busy? Perhaps they are on the phone or already in conversation with another colleague. Some people will casually walk by, return to their office, and check back later. Others will stand by the door, leaning on the door frame, until the person completes their conversation. If everyone in the office uses the latter approach, some employees could end up with a line outside their door!
The first type of employee is practicing nonpersistent CSMA. In nonpersistent CSMA, a LAN adapter wanting to transmit, but detecting a busy medium, waits a random interval of time and checks back again later. The second type of employee is practicing persistent CSMA. When a LAN adapter wanting to transmit detects a busy medium, it continues to monitor the medium until it returns to the idle state (i.e., the currently transmitting station finishes its transmission). Non-persistent CSMA has never been broadly implemented. LAN adapters that implement a version of CSMA all use some form of persistent CSMA.
What happens in a persistent CSMA environment when the medium returns to an idle state? Again, there are two basic flavors of persistent CSMA. In 1 persistent CSMA, a LAN adapter waiting for the medium to return to the idle state begins to transmit as soon as this transition takes place, allowing for only a small interframe separation time. This is the algorithm depicted on the visual. In p persistent CSMA, a LAN adapter waiting for the medium to return to the idle state transmits with probability p. For example, in .5 persistent CSMA, the LAN adapter flips a hypothetical coin (i.e., a random number generator) and, if it's heads, it transmits. If it's tails, it waits a random period of time and starts the whole process all over again.
The CSMA-based LAN adapters on the market use 1 persistent CSMA. While p persistent CSMA has the potential for better performance under high loads, a problem arises in determining the appropriate value of p. The ideal value is the inverse of the number of LAN adapters wishing to transit at that instance. However, because there is no way to determine this number, there is no way to appropriately tailor the value of p for optimal performance. 1 persistent CSMA is simple and has reasonable performance characteristics.
The choice of 1 persistent CSMA as the MAC scheme in contention-based networks is largely due to its dynamics in low-to-moderate load environments. As the load becomes high and the number of LAN adapters increases, all CSMA schemes have the tendency to become unstable (i.e., the time a given adapter might have to wait before getting access to the LAN can grow to infinity). This is due to a significant increase in the number of collisions, with the resulting loss of bandwidth. Collisions on a LAN have much the same effect as collisions on a superhighway: They can congest the network by making less of the “road” available for traffic. If there are enough collisions, the network can grind to a complete halt.
Consider the possible causes of a collision. In a 1 persistent carrier sense multiple access (CSMA) system, there are two possibilities. First, a collision occurs if two LAN adapters determine a need to transmit at nearly the same time, detect an idle medium, and proceed to transmit. The probability of this occurring is fairly low. Second, if two or more LAN adapters become ready to transmit while another LAN adapter is transmitting, a collision occurs when the medium returns to the idle state. As the load on a CSMA-based LAN increases, the probability of this occurring increases significantly.
As an aside, it should be clear that there is a bounded period of time during which such a collision could occur. This period of time is directly related to the end-to-end propagation delay of the LAN. Once a signal has traveled the length of the LAN, all attached LAN adapters can detect the signal and no collision can occur. If this “collision window” is increased, the probability of collisions also increases. This is one of the reasons why LANs that implement a form of collision detection (CD) place strict limits on the physical size of the LAN.
Collisions are unavoidable. Sooner or later, the laws of probability will catch up and transmissions will collide. What is needed is a strategy to minimize the effect of the collision. This is the role of collision detection. If a LAN adapter is capable of detecting when the medium is idle, it should also be possible for the LAN adapter to detect when two or more adapters are transmitting at the same time. As it turns out, this is indeed the case. This means that, upon detecting a collision, a LAN adapter can issue a short jamming signal to ensure all attached devices have detected the collisions, and then “back off” (i.e., terminate its transmission prematurely and wait a randomly selected period of time), thereby conserving bandwidth.
To summarize, 1 persistent CSMA/CD describes a contention-based MAC scheme in which a LAN adapter wishing to transmit first senses the medium (the carrier sense part). If it is idle, the LAN adapter transmits immediately. If it is busy (the multiple access part), the station waits until it returns to the idle state (the persistent part), then proceeds to transmit (the 1 part). As the LAN adapter transmits, it monitors the medium for the occurrence of a collision (the collision detection part). If a collision occurs, the LAN adapter terminates the transmission, emits a short jamming signal, waits a random period of time, and tries all over again.
1-persistent CSMA/CD is still widely found, largely due to its use in shared-bandwidth Ethernet networks. In fact, Robert Metcalf, the inventor of Ethernet, might argue that 1-persistent CSMA/CD is synonymous with Ethernet, and that all that has happened to Ethernet since is not Ethernet at all. However, the broad success of Ethernet can be traced to its cost, availability, and simplicity. It certainly cannot be traced to its efficiency.
1-persistent CSMA/CD actually causes collisions, under the right circumstances: two or more LAN adapters becoming ready to transmit while another is in the process of transmitting. When the transmitting adapter finishes, the waiting LAN adapters will be forced into a collision by the very rules they are following. The busier the LAN gets, the more likely this is to happen. The rules ensure that some amount of throughput will always get through. But it also ensures that a very busy shared-bandwidth Ethernet will see a significant percentage of its bandwidth lost to collisions.
The contention-based scheme also makes it difficult, if not impossible, to ensure any quality of service (QoS). How can a device be given assured access to the medium if it depends completely on the laws of probability to gain eventual access?
A second problem arises in environments where collisions cannot be detected in a timely fashion, or at all. Detecting them in a timely fashion can be ensured by limiting the size of the network, which is done for such networks. But what if a bus topology existed in which detecting collisions was impossible? This can happen in wireless networks for two reasons.
First, it is often difficult for a radio-based system to simultaneously transmit and receive. It requires additional equipment to do so (e.g., antennae), which means greater cost. If a system cannot simultaneously transmit and receive, it cannot detect collisions of its own transmissions.
Second, there is the problem of the “hidden node.” Consider the case of Stations A and C, both of which are in range of Station B, but are too far apart to see one another. If both stations transmit to Station B, they will collide with one another. However, the transmitters (Stations A and C) are oblivious to the collision. Only Station B can see it. As the receiver, it cannot resolve the problem. Only the transmitter can recover from this problem.
This suggests that CSMA/CD, while appropriate for shared-bandwidth wired LANs, might not be very appropriate for wireless environments. This, it turns out, is indeed the case.
In some environments it is not possible or not desirable, to detect collisions. For example, if the end-to-end propagation delay of a transmission is extremely high (e.g., satellite transmission), the transmitter might actually complete the transmission before it reaches the receiver. If the transmission collides after the transmitter is done transmitting, any collision goes undetected by the transmitter. Alternatively, the implementer of a LAN adapter might decide that the circuitry to detect collisions would unacceptably increase the cost of their device (i.e., Apple Computers made this decision when they built LocalTalk into their original Macintosh line of computers).
There is an alternative to CSMA/CD called carrier sense multiple access with collision avoidance (CSMA/CA).This name is somewhat inappropriate. Every contention-based MAC scheme (except pure contention) attempts, in one way or another, to avoid collisions. That is what CSMA is all about. CSMA/CA simply adds another twist to avoid more collisions than CSMA/CD or simple CSMA.
CSMA/CA is very similar to p-persistent CSMA. As with CSMA/CD, the LAN adapter first checks the state of the medium. If it is idle, transmission can begin immediately. If it is busy, the LAN adapter waits for the medium to return to the idle state.
When the line returns to an idle state, however, the LAN adapter does not transmit immediately. Instead, it waits for a randomly selected period of time. At the end of that time, if the medium is still idle, the device transmits. Any collision that occurs at that point goes undetected. The LAN adapter completes its transmission oblivious to the problem. To deal with this, some CSMA/CA environments require the receiver to acknowledge a transmission. If a transmission is in progress, the other devices are required to wait not only for the end of the transmission, but also to allow a reasonable gap for the receiver to respond. If the transmitter does not receive the acknowledgement, it knows it must retransmit.
Note that this scheme has the same performance characteristics as CSMA/CD under low loads. If the LAN is idle, access is immediate. Under high loads, this scheme tends to be slightly more stable than CSMA/CD. Collisions can only occur in two conditions: First, (like CSMA/CD) if two devices determine a need to transmit at nearly the same instance and detect an idle medium; second, if two or more devices determine a need to transmit and detect a busy medium—then select the same random period to wait, which is the smallest interval selected by any device needing to transmit. It is this latter condition that tends to avoid more collisions than simple 1-persistent CSMA/CD. Unfortunately, it also means that a certain amount of bandwidth is lost to this wait period. Variations on CSMA/CA are found in many wireless LANs.
CSMA/CA deals with the problem of significantly reducing “forced” collisions caused by 1-persistent CSMA/CD. Positive acknowledgements will help deal with undetected collisions. However, neither of these seeks to minimize collisions in contexts where collisions are hard or impossible to detect.
To achieve this, some CSMA/CA environments inject a simple form of polling into the protocol. Before actually transmitting a frame, the transmitter is required to send a brief Request to Send (RTS) message to the receiver. This message includes an expected period of time required for the transmission. Assuming the RTS does not collide in the network, the receiver responds with a Clear to Send (CTS) message and includes the expected time of the transmission. Only when this is received does the transmitter begin to send its frame.
To see how this would reduce collisions and deal with the hidden node problem, consider the case of Stations A and C, both of which can see Station B but are too far apart to see one another. If Station A wishes to transmit a frame to Station B, it first sends an RTS indicating Station A wants to transmit to Station B. Station C cannot see this request. If the request arrives intact at Station B, Station B responds with a CTS. Assuming no collisions, Station C can see Station B’s response and knows a device outside of its radio range is asking to transmit. It also knows how long that transmission is expected to last.
Station A then proceeds to transmit, which Station C again cannot see. But it is patiently waiting. It will now remain silent for at least the specified period of time, or until it sees the acknowledgement from Station B, whichever comes first.
These strategies do not completely eliminate collisions, but they greatly reduce them and they ensure that the transmitter can detect failures to communicate.
<mp3>http://podcast.hill-vt.com/podsnacks/2007q1/csma-cd.mp3%7Cdownload</mp3> | CSMA/CD