Medium Access Control: Stochastic Methods - CSMA/CD

Now that we have looked at how a frame is actually transmitted as an electrical signal on a shared bus, it’s interesting to look in more detail at what happens when two hosts transmit a frame at almost the same time. This is illustrated in the slides below:

• Hosts A and B start their transmission at the same time (first slide).

• At this time, if host C senses the channel, it will consider it to be free.

• This will not last a long time, and in the second slide the electrical signals from both host A and host B reach host C.

• The combined electrical signal (shown graphically as the superposition of the two curves in the figure) cannot be decoded by host C.

• Host C detects a collision, as it receives a signal that it cannot decode. Since on a wire, this could be a voltage level that corresponds to neither 0 nor 1.

• Since host C cannot decode the frames, it cannot determine which hosts are sending the colliding frames. Note that host A (and host B) will detect the collision after host C (third slide).

• In a wired network, a host is able to detect such a collision both while it’s listening (e.g., like host C in the figure above) and also while it is sending its own frame. When a host transmits a frame, it can compare the electrical signal that it transmits with the electrical signal that it senses on the wire.

• In the first and second slides in the figure above, host A senses only its own signal.

• In the third slide, it senses an electrical signal that differs from its own signal and can thus detect the collision.

• At this point, its frame is corrupted and it can stop its transmission.

The ability to detect collisions while transmitting is the starting point for the Carrier Sense Multiple Access with Collision Detection (CSMA/CD) MAC algorithm which is used in Ethernet networks. When an Ethernet host detects a collision while it’s transmitting, it immediately stops its transmission. Compared with pure CSMA, CSMA/CD is an important improvement since when collisions occur, they only last until colliding hosts have detected it and stopped their transmission instead of continuing to transport the rest of the frame unnecessarily. In practice, when a host detects a collision, it sends a special jamming signal on the cable to ensure that all hosts have detected the collision.

Worst Case

To better understand these collisions, it’s useful to analyse what would be the worst collision on a shared bus network. Let’s consider a wire with two hosts attached at both ends, as shown in the slides below.

• Host A starts to transmit its frame and its electrical signal is propagated on the cable. Its propagation time depends on the physical length of the cable and the speed of the electrical signal. Let us use $τ$ to represent this propagation delay in seconds.

• Slightly less than $τ$ seconds after the beginning of the transmission of A’s frame, B decides to start transmitting its own frame.

• After $\epsilon$ seconds, B senses A’s frame, detects the collision and stops transmitting.

• The beginning of B’s frame travels on the cable until it reaches host A.

• Host A can thus detect the collision at time $τ$ $- \epsilon +$ $τ$ $\approx 2 \times$ $τ$.

• An important point to note is that a collision can only occur during the first $2\times$ $τ$ seconds of its transmission. If a collision did not occur during this period, it cannot occur afterward since the transmission channel is busy after $τ$ seconds and CSMA/CD hosts sense the transmission channel before transmitting their frame.

Quick Quiz!

Now that we have a basic idea of how CSMA/CD works, we’ll look at a few ways that it’s optimized in the next lesson.