CSMA/CD: Ethernets Multiple Access Protocol Part-02

A few comments about the CSMA/CD protocol are certainly in order. The purpose of the jam signal is to make sure that all other transmitting adapters become aware of the collision.

Lets look at an example. Suppose adapter A begins to transmit a frame, and just before As signal reaches adapter B, adapter B begins to transmit.  

So B will have transmitted only a few bits when it aborts its transmission. These few bits will indeed propagate to A, but they may not constitute enough energy for A to detect the collision. To make sure that A detects the collision (so that it too can abort), B transmit the 48-bit jam signal.
Next consider the exponential back off algorithm. The first thing to notice here is that a bit time (that is, the time to transmit a single bit) is very short; for a 10 Mbps Ethernet, a bit time is 0.1 microsecond. Now lets look at an example.

Suppose that an adapter attempts to transmit a frame for the first time and while transmitting it detects a collision. The adapter then chooses K = 0 with probability 0.5 or chooses K = 1 with probability 0.5. If the adapter chooses K = 0, then it immediately jumps to Step 2 after transmitting the jam signal.

If the adapter chooses K = 1, it waits 51.2 microseconds before returning to Step 2. After a second collision, K is chosen with equal probability from {0,1,2,3}. After three collisions, K is chosen with equal probability from {0,1,2,3,4,5,6,7}.

After 10 or more collisions, K is chosen with equal probability from {0,1,2, . . . , 1023}. Thus the size of the sets from which K is chosen grows exponentially with the number of collisions (until n = 10); it is for this reason that Ethernet's back off algorithm is referred to as exponential back off.

The Ethernet standard imposes limits on the distance between any two nodes. These limits ensure that if adapter A chooses a lower value of K than all the other adapters involved in a collision, then adapter A will be able to transmit its frame without experiencing a new collision. 
Why use exponential backoff? Why not, for example, select K from {0,1,2,3,4,5,6,7} after every collision? The reason is that when an adapter experiences its first collision, it has no idea how many adapters are involved in the collision.

If there are only a small number of colliding adapters, it makes sense to choose K from a small set of small values. On the other hand, if many adapters are involved in the collision, it makes sense to choose K from a larger, more dispersed set of values (why?).

By increasing the size of the set after each collision, the adapter appropriately adapts to these different scenarios. 
We also note here that each time an adapter prepares a new frame for transmission, it runs the CSMA/CD algorithm presented above, not taking into account any collisions that may have occurred in the recent past.

So it is possible that an adapter with a new frame will immediately be able to sneak in a successful transmission while several other adapters are in the exponential back off state.

Ethernet Efficiency

When only one node has a frame to send, the node can transmit at the full rate of the Ethernet technology (e.g., 10 Mbps, 100 Mbps, or 1 Gbps).

However, if many nodes have frames to transmit, the effective transmission rate of the channel can be much less. We define the efficiency of Ethernet to be the long-run fraction of time during which frames are being transmitted on the channel without collisions when there is a large number of active nodes, with each node having a large number of frames to send.

In order to present a closed-form approximation of the efficiency of Ethernet, let dprop denotes the maximum time it takes signal energy to propagate between any two adapters. Let dtrans be the time to transmit a maximum-size Ethernet frame (approximately 1.2 msec for a 10 Mbps Ethernet). 

A derivation of the efficiency of Ethernet is beyond the scope of this blog. Here we simply state the following approximation:

We see from this formula that as dprop approaches 0, the efficiency approaches 1. This matches our intuition that if the propagation delay is zero, colliding nodes will abort immediately without wasting the channel. Also, as d-trans becomes very large, efficiency approaches 1.

This is also intuitive because when a frame grabs the channel, it will hold on to the channel for a very long time; thus the channel will be doing productive work most of the time.