I've been given two PC's that are connected via Ethernet, and as such are using CSMA-CD with binary exponential backoff.

Now, both PC's, let's call them $A$ and $B$, are trying to send data simultaneously. So, the first time both randomly choose a number from $\{0,1\}$. Let's say $A$ wins (i.e. $A$ picks 0 and $B$ picks 1) and sends the first frame of its data.

Instantly after sending the frame, the next collision between $A$ and $B$ occurs.
Now, in my given scenario, for some reason $A$ only picks from $\{0,1\}$, while $B$ picks from $\{0,1,2,3\}$.

Why is that the case? I don't see how this algorithm is any better than if $B$ gave up right away after losing once.
First: Just using a wider range doesn't stop the two PC's from colliding at all. If only $A$ has enough frames to send, the next collision will occur eventually anyway.
And for every collision afterwards, the chance of $B$ losing just ever increases. So, $B$ will starve and give up eventually anyway as well.

Why not just let $B$ give up instantly, and let $B$ wait till $A$ certainly has finished? Is my given scenario somehow wrong, or am I missing the point?


You are right. This does seem like an undesirable consequence of the CSMA-CD protocol.

I suspect this behavior was selected because it is implementable, and because it is not so easy to come up with an alternative that is simple and avoids this problem.

Recall, the only thing that is observable to B when it tries to send is whether that send was successful or a collision occurred. B can't see anything about whether it "wins" or "loses"; it has no visibility of the other parties. It doesn't know that A is also trying to send at the same time. If B tries to send and succeeds, then B doesn't know whether that's because no one else wanted to send; or A wanted to send and previously "won" (already finished sending); or A wants to send but has "lost" (hasn't sent yet and has a backoff time that is still in the future) -- B has no way to distinguish between those cases.

It sounds like one of your alternative proposals is that B should give up permanently as soon as it is involved in a two consecutive collisions. That doesn't seem to make sense to me. When B gives up permanently, that means that it just powers down and never sends on the network again? You can't have permanent disconnection -- that wouldn't be useful. There has to be some point at B is going to try to send something again, so it's just a question of what that condition is.

It sounds like another of your proposals is that if B collides with A, and A gets to send first, then B should wait until A is finished. That's harder to implement, and I'm not sure it has much benefit for B (B is still stuck waiting). Why is it hard to implement? It's hard to implement, because it's not clear how B would know when A is "done" transmitting. It's not even clear what "done" means. Even A won't know when it is done; A doesn't necessarily know what other packets it might want to send in the near future. So now we get into some design space where we try to figure out what we mean by "done", and how B would know when A is done (maybe it's that A hasn't sent anything in the last 20ms?). It's not enough to have A declare how much more it currently has to send as soon as it succeeds on a retransmission attempt and then require B to wait until that much has been sent, because what if after A finishes sending that much, A discovers it has more that it wants to send? (Presumably, there's some application running on A that periodically wants to send stuff. A's ethernet card can't predict what future sends the application will want to do. Maybe the application will end up continuously trying to send packets, one after another, rapid-fire.) If A tries to send some new message as soon as it finishes the previous one, you'll be back to the same scenario where A is more likely to win, so this doesn't eliminate the problem.

Or, if you were proposing that each PC remembers who won the last time and you alternate, that is also problematic, for a different reason. It doesn't scale well to more than two PCs on the same network.

The standard protocol is memoryless; it doesn't require keeping track of past history. This makes it simple, scalable, and reasonably efficient in many scenarios.

  • $\begingroup$ Thanks, that was what I was confused about. It seemed only fair for both to back off, but for some reason our professor implied by the scenario he gave us to work on that only the losing party would back off $\endgroup$ – Sudix Jun 18 '18 at 12:13
  • $\begingroup$ @Sudix, your comment prompted me to take another look, and I was confused, and you were right. My fault. I'm sorry. I've corrected my answer. $\endgroup$ – D.W. Jun 18 '18 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.