Carrier Sense Multiple Access with Collision Detection (CSMA/CD)

To reduce the impact of collisions on the network performance, Ethernet uses an algorithm called CSMA with Collision Detection (CSMA / CD): CSMA/CD is a protocol in which the station senses the carrier or channel before transmitting frame just as in persistent and non-persistent CSMA. If the channel is busy, the station waits. it listens at the same time on communication media to ensure that there is no collision with a packet sent by another station. In a collision, the issuer immediately cancel the sending of the package. This allows to limit the duration of collisions: we do not waste time to send a packet complete if it detects a collision. After a collision, the transmitter waits again silence and again, he continued his hold for a random number; but this time the random number is nearly double the previous one: it is this called back-off (that is to say, the “decline”) exponential. In fact, the window collision is simply doubled (unless it has already reached a maximum). From a packet is transmitted successfully, the window will return to its original size.

Again, this is what we do naturally in a meeting room if many people speak exactly the same time, they are realizing account immediately (as they listen at the same time they speak), and they interrupt without completing their sentence. After a while, one of them speaks again. If a new collision occurs, the two are interrupted again and tend to wait a little longer before speaking again.

The entire scheme of CSMA/CD is depicted in the fig

Frame format of CSMA/CD

The frame format specified by IEEE 802.3 standard contains following fields.

1. Preamble: It is seven bytes (56 bits) that provides bit synchronization. It consists of alternating Os and 1s. The purpose is to provide alert and timing pulse.

2. Start Frame Delimiter (SFD): It is one byte field with unique pattern: 10 10 1011. It marks the beginning of frame.

3. Destination Address (DA): It is six byte field that contains physical address of packet’s destination.

4. Source Address (SA): It is also a six byte field and contains the physical address of source or last device to forward the packet (most recent router to receiver).

5. Length: This two byte field specifies the length or number of bytes in data field.

6. Data: It can be of 46 to 1500 bytes, depending upon the type of frame and the length of the information field.

7. Frame Check Sequence (FCS): This for byte field contains CRC for error detection.

CSMA/CD Procedure:

Fig. Shows a flow chart for the CSMA/CD protocol.

Explanation:

• The station that has a ready frame sets the back off parameter to zero.

• Then it senses the line using one of the persistent strategies.

• If then sends the frame. If there is no collision for a period corresponding to one complete frame, then the transmission is successful.

• Otherwise the station sends the jam signal to inform the other stations about the collision.

• The station then increments the back off time and waits for a random back off time and sends the frame again.

• If the back off has reached its limit then the station aborts the transmission.

• CSMA/CD is used for the traditional Ethernet.

• CSMA/CD is an important protocol. IEEE 802.3 (Ethernet) is an example of CSMNCD. It is an international standard.

• The MAC sublayer protocol does not guarantee reliable delivery. Even in absence of collision the receiver may not have copied the frame correctly.

The CSMA/CD Based LAN

To understand the CSMA / CD protocol well, it is required to have some knowledge about the earlier access techniques. A brief overview of the evolution of media access techniques presented here.

ALOHA: In packet radio networks of the earlier days transmission media was shared by several stations; ALOHA technique provided fair conflict-free channel access to stations. This scheme is suitable for any system using shared media. Whenever a station has frames to send, it sends them immediately. It listens for an acknowledgment for a specific duration, equal to the maximum round trip delay for the farthest station on the network, plus some latency time. If the acknowledgment not received during this interval, it sends the next frame. Otherwise, it resends the same. If the station fails to receive the frame, it defers the transmission process. The receiving station checks the frame for its correctness. If the destination address field of the frame matches with the receiving station address, then it sends an acknowledgment. For the receipt of the incorrect frame, a station ignores it. Noise or collision may cause a frame to be invalid. The problem with the ALOHA access method is that as more and more users start to access the network, there is an ever-increasing chance that two people transmit at the same time. Collision is due to the interference of two frames so that neither of them gets through. A collision represents wasted capacity. Neither transmission is successful nor will both have to send again.

As the number of collisions increases over time, the likelihood of further collisions also increases. It is because of the increase in retransmissions. Through some quick mathematics, it can show that the maximum utilization of an ALOHA network is only 18%. If the number of collisions increases to a certain point, the network throughput begins to fall. Further increase in transmissions and retransmissions means that throughput collapse. The network has saturated with collisions.

Slotted ALOHA: ALOHA scheme provides poor collision control. The efficiency of the ALOHA can further be improved by organizing the channel time into equal time slots. A centralized clock is used to control all stations. Stations are permitted to transmit only at the beginning of every clock. This scheme provides better collision prevention capability than a pure ALOHA scheme.

CSMA Both ALOHA and slotted ALOHA schemes do not provide the expected channel utilization. In both schemes, none of the stations worry about what the other stations are doing before start transmission. CSMA scheme is known as Carrier Sense Multiple Access, in which a station willing to transmit data first listens to the channel to know whether someone is already transmitting or not. This property is known as Carrier Sense. If the station hears a transmission, it must wait. If the channel is idle, then the station starts transmission. However, there are still chances for the collision. It may happen when two or more stations simultaneously sense the idle channel and start transmission at once. The data from the channel is garbled. The station transmitting the frame waits for an acknowledgment. The waiting time can be decided, based on the round trip propagation delay. If no acknowledgment received within this time, the station assumes a collision and retransmits the frame again. If the channel is busy, then the station waits until the channel sensed as idle. CSMA algorithm provides better channel utilization than the algorithms discussed earlier.

CSMA/CD: In all the schemes discussed so far, when frame transmission started, whether the transmission completed successfully or not, the frame transmitted completely. Even if there is a collision detected by the transmitting station during the transmission process, the station continues the frame transmission. If the length of the frame is long, the channel capacity wasted is also more. It is meaningful to stop the transmission abruptly after hearing the collision information. The CSMA/CD algorithm performs this. The working of the CSMA/CD algorithm can be best described, using the following steps.

Step 1: Before starting the transmission, the station senses the medium for the presence of any transmission from other stations.
Step 2: If the medium is idle, the station starts transmission and goes to step 4; otherwise, it goes to step 3.
Step 3: If the medium is busy, it continuously listens until the channel becomes idle, then it starts immediately.
Step 4: If a collision detected during the transmission, a brief jamming signal is transmitted to inform all the stations to stop transmission immediately.
Step 5: After transmitting the jamming signal, the station waits for a random time and attempts to start from step 1 again.

This CSMA/CD is a significant protocol. It has included in the IEEE standard.
CSMA/CD bus-based LAN: It is also known as Ethernet. Baseband coaxial cables are used to construct an Ethernet LAN. Typical operating speeds of these LANs are in the order of 10 Mbps. For a detailed discussion on Ethernet and types, are frame format.

The Interface

The magnified view of the Ethernet interface shown in Figure.

In a network using thick Ethernet, a Vampire Tap is used to connect the station to the coaxial cable.
Every station connected to a transceiver. A transceiver performs the following functions.

• Send and receive data to and from the cable.
• Detect collision on the cable.
• Provide the electrical isolation between cable and cable interface.
• Protecting the cable from transceiver and station malfunctioning.

The repeater again connected to the MAC unit. The MAC unit performs the following functions.

• Encapsulate and de-encapsulate frames for transmission and reception.
• Performs error detection.
• It implements the MAC algorithm.

Each MAC unit uses a dual-port Random Access Memory (RAM), also known as a buffer. The main reason for this buffer is to receive and transmit data at a very high rate. It also allows the host computer to read and write frames.

Frame Transmission Procedure

The MAC layer encapsulates the frame. Before starting the frame transmission, the MAC Unit monitors the channel to detect the presence of any other signal. If it hears a signal, it defers the transmission for a random time interval, to allow the current transmission to complete. After beginning the transmission, the MAC Unit simultaneously monitors the echo of the transmitted signal to detect the presence of a collision. If no collision heard, the transmission is allowed to continue until it completed. Otherwise, the transmission stopped abruptly, and a brief warning (jamming) signal is sent to all stations to intimate the presence of the collision.

When a collision occurs, the retransmission of data done after a randomly selected interval. Collision may repeatedly occur when a large number of stations become busy. There is a limit to the number of attempts when collisions occur repeatedly. It is known as the attempt limit. Under such conditions, the MAC unit reduces the load on the channel by increasing the time delay. It uses a unique algorithm known as binary exponential back off to schedule retransmissions. The worst-case time needed by the MAC unit to detect the presence of a collision is equal to the time taken by the first bit from the transmitting station to reach the farthest station and return to the originating station. This time interval is known as slot time.

Slot time = 2*Transmission delay + Safety margin

Hence, the worst-case time delay needed by any station to determine the presence of a collision is less than or equal to the slot time. The transmission delay is equal to the worst-case signal propagation delay from any transmitting station to any receiving station on the network.

A. Algorithm for frame transmission

Step 1: Wait for frame arrival.

Step 2: If the frame arrives, then format the frame for transmission, else go to step 1.

Step 3: Check for the carrier; if detected, then keep checking.

Step 4: If no carrier is detected, then start frame transmission.

Step 5: Check for a collision.

If a collision is detected:

Stop transmission and transmit a brief jamming signal.

Compute and wait for back-off time.

Go to step 3.

Else

Complete the transmission successfully and go to step 1.

B. Algorithm for frame reception

Step 1: Keep checking for an incoming frame.

Step 2: Set carrier sense signal on.

Step 3: Obtain the bit synchronization signal and wait for Start of Frame Delimiter (SFD).

Step 4: Receive the frame.

Step 5: Compute and verify the Frame Check Sequence (FCS) and Frame length values.

Step 6: If the Frame Check Sequence and Frame Length is correct, proceed to the next step.

    Else

Discard the frame and go to step 1.

Step 7: If Destination address matches with the frame address, pass the frame to higher order layer for processing.

Else

Discard the frame and go to step 1.