Carrier sense multiple access with collision detection

The English term Carrier Sense Multiple Access / Collision Detection (CSMA / CD) ( to German as: " multiple access with carrier sensing and collision detection " ) denotes an asynchronous media access method (protocol) that regulates the access of different stations on a common transmission medium. It is an extension of CSMA. Will use CSMA / CD example in the area of computer networks at the Ethernet and there has been standardized as IEEE 802.3. In wireless LANs, a similar mechanism called Carrier Sense Multiple Access / Collision Avoidance (CSMA / CA ) is used. The used in the automotive industry CAN bus uses a mechanism called Carrier Sense Multiple Access / Collision Resolution ( CSMA / CR ).

Function or sequence

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

Collisions and collision detection

In case of power transmission methods such as Ethernet is a packet-oriented data transmission in datagrams (data frames) on a shared medium ( radio, cable), or abstract, within a common collision domain instead. Neither an endless stream so it will still generates accesses are controlled otherwise deterministic to the media. Therefore, it is possible that a plurality of stations will use the same medium (e.g. coaxial cable ) at the same time. This collision can arise that make the transmitted signals useless. To prevent this effectively, the CSMA / CD method is employed. The task of the CSMA / CD method is to detect any collisions to react and prevent the repetition of these.

From a collision is called when (or more) are two signals simultaneously on a common line. Here, the two electrical signals are superimposed to a common voltage level. The consequence is that the receiver can distinguish the electrical signal is no longer in the individual logic signals (bits).

The method is compared with token passing method (eg Token Ring) or master -controlled network (eg ISDN ), relatively simple, which has also contributed significantly to its spread. More modern Ethernet method (eg Fast Ethernet), the collision education deal also. Collisions there is also prevented effectively in switched environments, for example through the use of buffered active distributors ( Switch).

Physical collision detection

Signals can be measured as a voltage level, wherein a superposition of signals is a sum of the voltage level. A collision of signals leads to exceeding a threshold value of the DC components. This voltage can be exceeded (even the currently uninvolved ) recognized by all computers and identified as collision.

Connection: Network expansion and collision detection

A collision must be especially recognized by the sender so that it can perform a retransmission. For this reason, the minimum packet length ( actually frame length ), and the transmission time for a frame of minimal length so dimensioned that the maximum round trip delay time ( RTDT ) is not fallen below. The RTDT is the time it takes a packet to travel from one end of the network to the furthest end of the other network - and back again. This ensures that a collision that occurs just before the receiver ( worst case), still can spread to the actual transmitter without this has finished sending. Thus, the transmitter detects the collision, knows that his frame is not really arrived at the receiver and sends the frame again.

Thus, the collision detection works reliably, a maximum network size and a matching minimum frame length ( 64 bytes ) has been defined for Ethernet. If " too short " frames are transmitted, they must be to be prolonged to a permissible minimum packet length. Had the packages too small, which would have the same effect as too much power (too high RTDT ), there could be undetected by the transmitter collisions, and the entire network traffic may be affected. Such disorders are tricky because transmission can function normally under low network load or even with certain packet sizes. Since repeaters and hubs included in the RTDT, but no really tangible expansion, though have measurable delay times, it is more practical to speak of times as packet lengths.

Example

In a network of maximum expansion (~ maximum round trip delay time) are Station Alpha and Omega, the two most distant stations. The media is free and Alpha starts the transmission. Until Omega noticed that Alpha sends, it takes exactly half Round Trip Delay Time - the time that need the packets / signals from Alpha to go to the station Omega. Has now Omega also something to transmit and immediately before the arrival of the packets of Alpha begun sending - as the line yes was still free from the perspective of Omega - initially occurs at Omega for collision, Omega noticed the disruption of its transmission and may accordingly respond. Up to now, also noticed the alpha collision, it will take at least another half RTDT - the time which need the signals from Omega to get to the station Alpha. Thus Alpha may noticed the conflict and initiate a retransmission, Alpha must therefore continue to send until the packets have arrived from Omega. In addition, all stations that have received the packages from Alpha, be informed about the collision. The minimum transmission time (~ minimum packet size) must therefore always be greater than the RTDT (~ twice the size of the network ).

Sample calculation for the maximum length

To calculate the maximum extent between two stops, wherein a collision detection is still ensured, the following applies:

, Signal speed and duration of transmission

The signal rate derived from the speed of light multiplied by the velocity factor of sales promotion. When coaxial cable is this about 0.7.

The transmission time t is calculated from the transmission duration for a bit, multiplied by the number of bits. The number of bits in an Ethernet frame is 512 ( = 64 bytes). The transmission duration of a bit depends upon the bit rate. At 10 Mbit / s, a bit lasts 0.1 microseconds. Thus, the minimum Ethernet frame takes 51.2 microseconds.

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

The backoff procedure Ethernet

Should the transfer be canceled because of a conflict, it would immediately to renewed conflict if the broadcast stations involved would send immediately after the crash again. Therefore, you must insert ideally a different long pause, so to give it a sending order the stations.

For Ethernet, the parties choose this, a random integer z in the interval ( the so-called contention window ), where i is the number of conflicts that occurred already. The number of possible transmit slots so increases exponentially, therefore, this method is called the binary exponential backoff. The transmitting station now waits for the period of z * slot time (see above) and then sends again if the medium is free. Has no other station pulled the same z, so there is no more conflict.

Since the dispersion of possible waiting times growing exponentially with the number of conflicts that occurred, the probability is very low that many conflicts occur one after the other, as the parties to the conflict would regularly pull the same random number for this purpose. Therefore, it is stopped after 16 conflicts as a result of the transmission attempt and adopted a system error.

The disadvantage of the method is that mathematically there is no guarantee that a packet has already arrived at a certain time. The transmission success has only a certain probability. The process is therefore not real-time capable, as is the case with Token Ring.

Due to the collisions occur, it is not possible to fully exploit the theoretical transmission capacity of a medium. In practice, one can assume that it is possible to achieve about 70 % of the nominal power at best, under less favorable conditions, it is under 30 %. The reason is simple: the more computers to participate in the network and the higher the utilization increases, the more collisions occur, hence the real scored data throughput decreases significantly.

CSMA / CD and the duplex mode

CSMA / CD is the data link layer of the OSI model assigned. It is (eg network card) performed by the Ethernet interface, as far as it is operated in half-duplex mode. By the configuration of the interface in the full duplex mode CSMA / CD is turned off. Thus, the interface can send and receive simultaneously. Collisions have to be avoided by only two stations can share the same transmission medium. This can be achieved by the use of a switch, for example. Then can be active in duplex mode, without causing collisions per segment or collision domain two nodes (stations).

Also, there are entirely collision-free transmission principles as the token passing, it comes eg ARCNET or Token Ring used.