Carrier sense multiple access with collision detection

In communications, CSMA/CD (from Carrier Sense Multiple Access with Collision Detection) or, in Spanish, multiple access with carrier listening and collision detection , is a shared media access algorithm. Its use is especially widespread in Ethernet networks where it is used to improve its performance. In CSMA/CD, network devices listen to the medium before transmitting, that is, it is necessary to determine if the channel and its resources are available for transmission. Additionally, it improves CSMA performance by terminating sending when a collision has been detected.

A station waits before transmitting because the channel is occupied.

History

A network where the equipment can simultaneously transmit several packets is prone to collisions that generate, in the best of cases, delays in the delivery of these packets and, in others, the loss of information. To avoid these situations, media access control techniques were developed.

The low performance of the first mechanisms used: Aloha and slotted Aloha, led to the appearance of new techniques aimed at more efficient management of network resources, giving rise to the CSMA algorithm and later to its CSMA/CD evolution (CSMA with collision detection).

Procedure

The following procedure is used to start a transmission. The procedure is completed when the frame is successfully transmitted or a collision is detected during transmission.

1. Is there a plot ready to transmit? If not, wait for a plot.
2. Is the middle inactive? If not, wait until you're ready.
3. Start transmitting and monitoring collisions during transmission.
4. Did a collision happen? If so, go to the collision procedure detected.
5. Restore the relay counters and complete the transmission of the plot.

The following procedure is used to resolve a detected collision. The procedure is completed when the retransmission is started or the retransmission is canceled due to numerous collisions.

1. Continue transmission (with a jam signal instead of a plot/data/CRC header) until the minimum time is reached to ensure that all receptors detect the collision.
2. Increase the relay counter
3. Were the maximum number of transmission attempts reached? If so, abort the transmission.
4. Calculate and expect the random waiting period according to the number of collisions.
5. Return to the main procedure in step 1.

Methods for collision detection are media dependent. On a shared electrical bus, such as 10BASE5 or 10BASE2, collisions can be detected by comparing transmitted data with received data or by recognizing a higher than normal signal amplitude on the bus. In all other media, a carrier detected on the receive channel while transmitting triggers a collision event. Repeaters or hubs detect collisions by themselves and propagate jam signals.

The collision recovery procedure can be compared to what happens at a dinner party, where all the guests talk to each other through a common medium (the air). Before speaking, each guest politely waits for the current speaker to finish. If two guests start talking at the same time, they both stop and wait for short, random periods of time (on Ethernet, this time is measured in microseconds). The hope is that by choosing a random time period, both guests won't choose the same time to try to talk again, thus avoiding another collision.

CSMA/CD Plot

Example of CSMA/CD plot

The frame used in CSMA/CD is made up of eight fields:

• The preamble preamble preamble preamble preamble preamble preamble preamble preamble preamble preamble preamble preamble preamble preamble preamble preamble preamble preamble preamble prea preamble preamble preamble preamble prea preamble preamble prea preamble preamble preamble prea prea prea preamble preamble prea preamble prea prea prea preamble preamble preamble preamble prea prea preamble preamble preamble preamble prea prea prea preamble preamble preamble preamble prea preamble preamble preamble preamble preamble preamble preamble preamble preamble preamble preamble prea prea prea preamble preamble preamble preamble preamble preamble preamble prea prea prea prea pre preamble prea preamble preamble prea preamble prea prea preamble, consisting of 7 octetos, is responsible for the receiver being able to synchronize with the transmitter so that the principle of the plot can be located.

• Start limiter: is a byte used to indicate to the receiver the beginning of the plot.

• Destination direction: contains the physical address (MAC) of the target team of the plot.

• Direction of origin: contains the MAC address of the transmitter station of the plot and has a format similar to that of the destination address.

• Length: indicates the length of the data field below. It is necessary to determine the length of the data field in cases that a filling field is used.

• Information: contains the data transmitted. It is variable length, so it can have any length between 42 and 1500 bytes.

• Filling: is used for the plot to reach the required minimum length. A plot should contain a minimum number of bytes so that stations can detect collisions accurately.

• Chequeo: contains a 32-bit cyclic redundancy code. It is used as an error control mechanism in transmission.

CSMA/CD Types

The CSMA/CD algorithm can be based on any of the following procedures:

• CSMA 1-persistent: when a station wants to transmit, first listen to the channel. If this is free then transmit immediately. In the opposite case, he remains in listening until he is free. At the time the station considers that the channel is available, it is transmitted immediately. The problem is that several stations may be waiting for the channel to be free to transmit, leading to a collision of their plots.

• Non-persistent CSMS: it works similarly to the previous except in the fact that when it detects that the channel is occupied, instead of staying waiting listening to it, it waits for a random time and listens again to the channel. This method reduces collisions if traffic is high, improving the use of the channel. However, delays for low traffic loads increase.

• CSMA p-persistent: as in the previous cases the channel is heard, however if it is free, instead of transmitting immediately, it is transmitted with a probability p, or the issue is delayed a temporary slot with a probability q=1-p. This time slot is usually equal to the maximum delay of signal propagation.

Usually the 1-persistent algorithm is used, since it is used in the IEEE_802.3 standard.

Operation

General operation

CSMA/CD operation and algorithm backoff.

In CSMA/CD, each station that wants to transmit must listen to the medium –carrier detection– to check if it is free, that is, to check that no other station is currently transmitting a message. If the medium is free then said transmission takes place. Even so, it may happen that several stations have messages to send and start transmitting a frame at the same time. When this happens, it is said that a collision has occurred in the network. The station that has detected the collision will proceed to send a 32-bit jam message to the rest of the stations to notify said event. Once all stations have been notified, all transmissions are automatically stopped and a backoff (or postponement) algorithm is executed, which consists of waiting for a random time (backoff) before retrying the transmission. During the first 10 attempts, the average value of the waiting time is doubled, while during the next 6 additional attempts, it is maintained. After 16 failed attempts, the algorithm will report an error to the upper layers.

Advantages

• Collision detection on wired LAN networks is easy.
• The average time required to detect a collision is relatively low.
• It can be used in continuous process control systems if the network traffic load is low (inferior at 20%)
• It offers greater performance especially when there are few collisions.

Disadvantages

• One of the most important disadvantages is that it is not possible to guarantee a finite maximum time for accessing the plots to the communication channel, so it is not suitable for real-time applications.
• Normally the CSMA/CD networks are half-duplex, which means that while a station sends information it is incapable of listening to the existing traffic.
• Problem in wireless networks (see below)

Problems in wireless networks

Hidden Node Problem

In wireless networks, listening to the medium and therefore detecting the collisions produced can be complicated. This manifests itself in two problems:

• Hidden Node Problem: a station may believe that the channel (media) is free when it is actually occupied by another station that it does not hear. The following image shows how A and C transmit to B as both detected that the channel was free. However B listens to both nodes, giving rise to a collision.

Problem of the node exposed

• Problem of the node exposed: a station may believe that the channel is occupied when it is actually occupied by another station that would not interfere with its transmission to another destination. The figure shows how C is communicating with B. As D detects that the channel is occupied, it cannot transmit to E, when the ideal thing would be that it could.

These problems were solved with the implementation of the CSMA/CA algorithm (MultiAccess Collision Avoidance)

Efficiency and features

CSMA/CD can be in one of the following states:

• Period of contention or containment: is the time interval during which a plot is vulnerable to collisions
• Transmission period: time interval during which a station transmits obtaining channel control
• Empty period: time interval during which the channel is empty

The contention period is made up of slots of length 2τ and will be the time it takes for a station to realize that its frame has collided: if a station A starts transmitting at instant t0, the signal will take a time τ (frame transmission time) to reach the station furthest away from it (let's call it B). Now, B will be able to start transmitting up to an instant before A's signal arrives; if it does so immediately it will then realize that there was a collision and abort its transmission. However, the "noise" caused by the collision will not reach station A until a time equal to twice the propagation of the signal between A and B, that is, 2τ. This implies that a station cannot be sure that it got the channel until it has transmitted for 2τ without having a collision.

Taking the above into account, some of the CSMA/CD parameters are defined as:

Maximum efficiency and parameter dependence a,G

• Efficiency:

MIL MIL =Ge− − 2aG1+(G− − 2aG)e− − 2aG{displaystyle eta ={frac {Ge^{-2aG}}{1+(G-2aG)e^{-2aG}}}}}}}

G = traffic intensity offered

• Maximum efficiency:

MIL MIL m≈ ≈ 11+(3.44a){displaystyle eta _{m}approx {frac {1}{1+(3.44a)}}}}

• Probability of the medium being free:

p(mediorlibre)=11+(G− − 2aG)e− − 2aG{displaystyle p(mediafree)={frac {1}{1+(G-2aG)e^{-2aG}}}}}}}}

• Time of transmission of the plot:

Δ Δ =LtC{displaystyle tau ={frac {L_{t}}{C}}}}

Lt = Trama length

• Relationship between propagation and delay time:

a=tpΔ Δ {displaystyle a={frac {t_{p}}{tau }}}}

Parameters according to IEEE 802.3 standard

Applications

CSMA/CD was used in the now obsolete variants of Ethernet 10BASE5 and 10BASE2. Currently, modern Ethernet networks built with switches and full-duplex connections maintain it as a backward compatibility mode.