Carrier Sense Multiple Access / Collision Detection

8-port Ethernet hub with display of collisions (2nd LED from the right, yellow)

The English term Carrier Sense Multiple Access / Collision Detection ( CSMA / CD ) (in German: "Multiple access with carrier check and collision detection") denotes an asynchronous media access method (protocol) that allows different stations (e.g. computers and their network connections) to access a common Transmission medium regulates. Simultaneous sending and "listening" must be possible on the shared transmission medium, e.g. B. in the power network (see dLAN ) or with Ethernet via coaxial cable. CSMA / CD is an extension of CSMA . CSMA / CD is used, for example, in the area of computer networkswith PowerLAN ; for Ethernet it has been standardized as IEEE 802 .3. In wireless LANs a very different mechanism called is Carrier Sense Multiple Access / Collision Avoidance (CSMA / CA) used. The CAN bus used in the automotive sector uses a mechanism called Carrier Sense Multiple Access / Collision Resolution (CSMA / CR).

Function or sequence

Functional representation in a program flow chart

When a device wants to send data, it adheres to the following process:

1. Listen : First, the medium must be monitored to see whether it is occupied.

→ Free: If the medium is free for a certain period of time ( IFS ), continue with step 2.

→ Occupied: continue with step 1.

2. Sending : Information transfer, at the same time the medium is continuously monitored.

→ Success (no collision until the end of the transmission): Transmission has been successfully completed and a success message is reported to higher network layers; continue with step 5.

→ Collision: If a collision is discovered, stop the data transmission and send a short, defined interference signal (jam) on the line to ensure that all other transceivers also recognize the collision, then continue with step 3.

3. Line is busy : Check the number of transmission attempts:

→ Maximum not reached: wait a random time ( backoff , see below), then start again at step 1.

→ Maximum reached: continue with step 4.

4. Error : Maximum number of transmission attempts was exceeded. An error is reported to the higher network layers, continue with step 5.

5. End : Exit transmission mode

Collisions and collision detection

→ Main article : Collision domain

In network transmission methods such as Ethernet, packet-oriented data transmission takes place in datagrams ( data frames ) on a shared medium (radio, cable), or more abstractly, within a common collision domain . An endless stream of data is not generated, nor are access to the medium anywhere centrally controlled deterministically. It is therefore possible that several stations want to use the same medium (e.g. coaxial cable ) at the same time. This can cause collisions that make the transmitted signals unusable. The CSMA / CD method is used to handle this. The task of the CSMA / CD method is to recognize collisions that occur, react and prevent them from repeating themselves.

We speak of a collision when two (or more) signals are on a common line at the same time. The two electrical signals are superimposed to form a common voltage level. The result is that the receiver can no longer differentiate between the individual logical signals (bits) of the electrical signal.

Compared to token passing methods (e.g. Token Ring ) or master-controlled networks (e.g. ISDN ), the process is relatively simple, which has also contributed significantly to its spread. In more modern Ethernet systems (e.g. Fast Ethernet ), point-to-point connections are predominantly used, in which the sending and receiving medium are separated and therefore no more collisions can occur. For this purpose, buffered active distributors ( switches ) are used.

Physical collision detection

Signals can be measured, for example, as voltage levels, with a superposition of signals meaning an addition of the voltage levels. A collision of signals can lead to a threshold value for the DC voltage components being exceeded or other signal properties defined for “valid signals”. This deviation can be recognized by all communication partners (including those currently not involved) and identified as a collision.

Relationship: network expansion and collision detection

Shows sending from Alpha to Omega

In particular, a collision must be recognized by the transmitter so that it can repeat the transmission . Depending on the transmission rate, the signal propagation speed and the maximum distance between the participants, there is a minimum packet length (actually frame length ) so that it can be guaranteed that a collision will reach the sender before it has completely sent its packet (and as "transmitted without errors") would classify). The transmission time for a frame of minimum length must therefore be dimensioned in such a way that the maximum RoundTripDelayTime (RTDT) is not undershot - i.e. the time a data packet needs to get from one end of the network to the most distant other end of the network - and again back. This ensures that a collision that only occurs shortly before the second transmitter (worst case) can spread to the first transmitter before it has finished transmitting. Thus the sender recognizes the collision, knows that its frame could not reach the receiver correctly and sends the frame again.

In order for the collision detection to work reliably, a maximum permissible network expansion and a matching minimum frame length (64 bytes) were specified for Ethernet. If frames that are “too short” are to be transmitted, they must be extended to a permissible minimum packet length if necessary. If the packets were too small, which would have the same effect as a network that is too large (RTDT too high), collisions undetected by the transmitter could occur and the entire network traffic could be impaired. Such disruptions are treacherous, as transmissions can function normally when the network load is low or with certain packet sizes. The RTDT also includes repeaters and hubs that cause measurable delay times, but do not have any "medium expansion". Therefore it is more practical to speak of times than of medium lengths.

1. ↑ To determine the RoundTripDelayTime, an entire data packet does not have to get from one end of the medium to the other and back again - a beginning section is sufficient that is long enough for reliable collision detection.
2. ↑ Worst case: Sender_1 and Sender_2 are at the extreme ends of a maximum length medium, Sender_2 begins to send when the signal from Sender_1 has almost reached it.

example

In a network with maximum extension (~ maximum RoundTripDelayTime) the stations Alpha and Omega are the two most distant stations. The medium is free and Alpha begins transmitting. Before Omega notices that Alpha is transmitting, it takes exactly half a RoundTripDelayTime - the time it takes the signals from Alpha to get to the Omega station . If Omega now has something to transmit and starts sending immediately before the signals from Alpha arrive - when, from Omega’s point of view, the line was still free - a collision initially occurs just before Omega . Omega notices the interference with its transmission, sends "JAM" and cancels the transmission. Until Alpha notices the collision, it takes another half RTDT - the time it takes the (first) signals from Omega to get to Alpha station . So that Alpha notices the collision (and can later initiate a retransmission), Alpha must continue to transmit until sufficient signals have been received from Omega . In addition, all stations that have received the (partial) packet from Alpha must be informed (in good time) of the collision (-> JAM). The minimum transmission time (~ minimum packet size) must therefore always be greater than the RTDT (~ twice the maximum signal propagation time of the network).

Example calculation for the maximum length

To calculate the maximum extent between two stations at which collision detection is still guaranteed, the following applies:

${\displaystyle 2\cdot s_{\mathrm {max} }=v\cdot t_{\text{Frame}}}$, Signal speed and transmission time ${\displaystyle v}$ ${\displaystyle t_{\text{Frame}}}$

The signal speed results from the speed of light multiplied by the shortening factor VKF. With coaxial cable this is approx. 0.7. ${\displaystyle v}$ ${\displaystyle c}$

The transmission time is calculated from the transmission time for one bit , multiplied by the number of bits. The number of bits in an Ethernet frame is 512 (= 64 bytes). The transmission time of a bit depends on the bit transmission speed . At 10 Mbit / s, one bit takes 100 ns. The minimum Ethernet frame thus lasts 51.2 µs. ${\displaystyle t}$ ${\displaystyle v_{\mathrm {bit} }}$

${\displaystyle 2\cdot s_{\mathrm {max} }=v\cdot t_{\text{Frame}}=c\cdot VKF\cdot 512\cdot {\frac {1}{v_{\mathrm {Bit} }}}=3\cdot 10^{8}\,\mathrm {\frac {m}{s}} \cdot 0{,}7\cdot 512\cdot 100\,\mathrm {ns} =10752\,\mathrm {m} }$

The maximum length for 10BASE5 is 2500 m. The collision detection is guaranteed.

The backoff procedure for Ethernet

Procedure diagram

If the transmission has to be aborted due to a conflict, there would be another conflict immediately if the transmitting stations involved were to send again immediately after the abort. You must therefore take a pause of generally different lengths so that only one of the stations repeats its transmission first.

In the case of Ethernet, the parties to the conflict choose a random integer z from the interval (the so-called contention window), where i stands for the number of conflicts that have already occurred in succession. The range of possible waiting periods increases exponentially, which is why this procedure is called binary exponential backoff . The sending station now waits for the period of z * Slot_time (see above) and then sends again if the medium is free. The station with the smallest z no longer experiences a conflict unless the other parties involved in the collision have drawn the same z-value. ${\displaystyle [0;(2^{i})-1]}$

Since the spread of the possible waiting times increases exponentially with the number of subsequent collisions that have occurred, the probability that many conflicts will occur one after the other is very low, since the conflicting parties would have to regularly draw the same random number. The send attempt is therefore aborted after 16 conflicts in a row and a system error is assumed.

The disadvantage of the method is that there is no mathematical guarantee that a package has already arrived at a certain point in time. The success of the transfer only has a certain probability . The process is not real-time capable , as is the case with Token Ring , for example .

Due to the collisions that occur, it is not possible to fully utilize the theoretical transmission capacity of a medium. In practice, it can be assumed that in the best case around 70% of the nominal output can be achieved, under less favorable conditions it is less than 30%. The more computers participate in the network and the higher the load increases, the more collisions occur and the data throughput actually achieved drops significantly.

CSMA / CD and the duplex mode

CSMA / CD is assigned to the data link layer of the OSI model. It is carried out by the Ethernet interface (e.g. network card) if it is operated in half-duplex mode - the network here has a bus topology in terms of signaling .

Ethernet networks can also be interconnected in (signaling) star topology , with the individual connections becoming point-to-point connections. Here the interface can be reconfigured to full duplex mode (sometimes automatically), which switches off CSMA / CD, since collisions can no longer occur here. This means that the interface can send and receive at the same time.

There are also completely collision-free transmission principles such as token passing . B. used with ARCNET or Token Ring .

literature

• Gerhard Schnell and Bernhard Wiedemann: Bus systems in automation and process technology, Vieweg + Teubner Verlag, Wiesbaden 2008, ISBN 978-3-8348-0425-9 .

Web links

• IEEE 802.3 IEEE 802.3 CSMA / CD (ETHERNET)