Medium Access Control: Stochastic Methods - Optimizing CSMA/CD

In this lesson, we'll learn about techniques to optimize CSMA/CD

We'll cover the following

Removing Acknowledgements

On the wired networks where CSMA/CD is used, collisions are almost the only cause of transmission errors that affect frames. Transmission errors that only affect a few bits inside a frame seldom occur in these wired networks. For this reason, the designers of CSMA/CD chose to completely remove the acknowledgment frames in the data link layer.

  • When a host transmits a frame, it verifies whether its transmission has been affected by a collision.

  • If not, given the negligible Bit Error Ratio of the underlying network, it assumes that the frame was received correctly by its destination. So, the bit errors might be detected or corrected using a checksum field. If not, we can rely on the layers above to implement retransmission.

  • Otherwise, the frame is retransmitted after some delay.

Edge Case: Short Frames

Removing acknowledgments reduces the number of frames that are exchanged on the network and the number of frames that need to be processed by the hosts. However, to use this optimization, we must ensure that all hosts will be able to detect all the collisions that affect their frames. The problem is important for short frames.

Let us consider two hosts, A and B, that are sending a small frame to host C as illustrated in the slides below. If the frames sent by A and B are very short, the situation illustrated below may occur.

  1. Hosts A and B send their frame and stop transmitting (first slide). Since until the end of the transmission, no collision was detected, hosts A and B are content that they were successfully able to use the channel to transmit the frame.

  2. When the two short frames arrive at the location of host C, they collide and host C cannot decode them (second slide).

  3. The two frames are absorbed by the ends of the wire. Neither host A nor host B has detected the collision. They both consider their frame to have been received correctly by its destination.

Press + to interact
The short-frame collision problem
The short-frame collision problem
1 of 3

To solve this problem, networks using CSMA/CD require hosts to transmit for at least 2×2 \times ττ seconds. Since the network transmission speed is fixed for a given network technology, this implies that a technology that uses CSMA/CD enforces a minimum frame size. In the most popular CSMA/CD technology, Ethernet, 2×2 \times ττ is called the slot time.

Retransmission Timeout

The last innovation introduced by CSMA/CD is the computation of the retransmission timeout.

Setting such a timeout is always a compromise between the network access delay and the number of collisions.

  • A short timeout would lead to a low network access delay but with a higher risk of collisions.
  • On the other hand, a long timeout would cause a long network access delay but a lower risk of collisions.

The binary exponential back-off algorithm was introduced in CSMA/CD networks to solve this problem.

To understand binary exponential back-off, let us consider a collision caused by exactly two hosts.

  • Once it has detected the collision, a host can either retransmit its frame immediately or defer its transmission for some time.

  • If each colliding host flips a coin to decide whether to retransmit immediately or to defer its retransmission, four cases are possible:

    1. Both hosts retransmit immediately and a new collision occurs.

    2. The first host retransmits immediately and the second defers its retransmission.

    3. The second host retransmits immediately and the first defers its retransmission.

    4. Both hosts defer their retransmission and a new collision occurs.

  • In the second and third cases, both hosts have flipped different coins. The delay chosen by the host that defers its retransmission should be long enough to ensure that its retransmission will not collide with the immediate retransmission of the other host.

  • However, the delay should not be longer than the time necessary to avoid the collision, because if both hosts decide to defer their transmission, the network will be idle during this delay.

  • The slot time is the optimal delay since it is the shortest delay that ensures that the first host will be able to retransmit its frame completely without any collision.

Performance

  • If two hosts are competing, the algorithm above will avoid a second collision 50% of the time.

  • However, if the network is heavily loaded, several hosts may be competing at the same time. In this case, the hosts should be able to automatically adapt their retransmission delay. The binary exponential back-off performs this adaptation based on the number of collisions that have affected a frame:

    • After the first collision, the host flips a coin and waits 00 or 11 slot time.
    • After the second collision, it generates a random number and waits 0,1,20, 1, 2 or 33 slot times, and so on.
    • The duration of the waiting time is doubled after each collision.

Pseudocode

The complete pseudocode for the CSMA/CD algorithm is shown in the figure below.

Press + to interact
N=1
while N <= max:
  wait(channel_becomes_free)
  send(frame)
  wait_until (end_of_frame) or (collision)
  if collision detected:
      stop transmitting
      end(jamming)
      k = min (10, N)
      r = random(0, 2k - 1)*slotTime
      wait(r*slotTime)
      N=N+1
  else:
      wait(inter-frame_delay)
      break
  # end of while loop
# Too many transmission attempts

The inter-frame_delay used in this pseudocode is a short delay corresponding to the time required by a network adapter to switch from transmitting to receiving mode. It’s also used to prevent a host from sending a continuous stream of frames without leaving any transmission opportunities for other hosts on the network. This contributes to the fairness of CSMA/CD.

Despite this delay, there are still conditions where CSMA/CD is not completely fair. Consider for example a network with two hosts: a server sending long frames and a client sending acknowledgments. Measurements reported have shown that there are situations where the client could suffer from repeated collisions that lead it to wait for long periods of time due to the exponential back-off algorithm.

Quick Quiz!

1

Why is a minimum frame size necessary?

A)

To decrease the chances of a bit error

B)

To allow sending hosts to be able detect collision while sending a frame

C)

To allow receiving hosts to be able detect collision while sending a frame

Question 1 of 20 attempted

Now that we’re done with stochastic algorithms, we’ll study some key data link layer technologies.

Get hands-on with 1400+ tech skills courses.