I'm reporting this here mostly for its curiosity value; also, it puts the (un)importance of the exponential random back-off algorithm into perspective, which is of interest from an academic point of view. (I teach this stuff for a living...)
Disclaimer: this page is not meant to attack the company Winbond or its products.
Ethernet is a network technology for connecting computers to each other. Its development started in the 1970s, and today almost every PC has an ethernet interface
The principle of ethernet is that any computer connected to the network may send a packet of data whenever it pleases (and no other computer is currently tranmitting a packet). If it is lucky, this computer is the only one that transmits a packet at that time, and the packet will reach the other computers unharmed. If it is unlucky however, another computer tries to transmit a packet at the same time. This is called a collision, and both computers detect this and stop their transmissions.
After a collision, the two colliding computers still have their packets ready for transmission. If they would both transmit them again after waiting for a fixed time, they obviously would collide again. In order to resolve this, the ethernet protocol states that both computers should pick a random number, and let that number determine how long they wait before trying again. Since it is unlikely that both computers pick the same random number, it is likely that the retransmissions will be done at different times, i.e., without colliding.
Actually, the ethernet specification (which can be found here) says not just that a random number must be chosen, it also specifies the range in which the number should lie. For the first retransmission, the number should be either 0 or 1; if this retransmission collides again, then the waiting time before the second retransmission should be chosen from 0, 1, 2 and 3; for the third attempt from 0, 1, ..., 7; and so on, until the tenth retransmission with a number in the range 0...1023. For the eleventh through sixteenth (and last) retransmission attempt, the range is not extended further. The actual waiting time should then be this random number times 51.2 microseconds. By extending the range of numbers at later retransmissions, the likelihood of the colliding computers choosing the same number becomes less and less likely.
This procedure is called exponential random back-off: random because of the random times between transmission attempts, and exponential because the average time between transmission attempts increases exponentially with the number of retransmissions.
Obviously, such a fixed back-off schedule goes against the principle of ethernet. If two cards with the same back-off schedule happen to do an initial transmission at the same time, resulting in a collision, then all retransmission attempts will also collide: the packet will never get through.
Now, actually, these fixed retransmission times in Winbond's chips are still a bit random: they seem to be chosen randomly at the moment the card is initialized (which typically happens only when the computer is booted, so typically only just after switching on). So, the back-off schedule is indeed chosen randomly, but this randomization happens only once. If you're unlucky, all computers with Winbond chips on your network choose the same back-off schedule and thus collisions will often not be resolved well.
A few more observations:
For driving the card, I used the Linux operating system, with the ping tool to generate a packet every second. (The arp command can be used to put fake entries in the ARP table, so the ping packets are actually transmitted, instead of ARP requests.) Running Linux does imply that I did not use the (Windows) driver supplied by the chip manufacturer. I don't expect this to make a difference though, since the back-off is normally handled in hardware.
Secondly: if you happen to be the engineer who designed these chips, I'd very much like to hear from you! Was this chip designed like this on purpose, and if so, why?
Thirdly, I'd like to thank Maarten Burghout (who has been using two Winbond cards on his home network for years, without problems), Eduard van Dijk and Olaf van Zandwijk for providing me with several extra ethernet cards with different types of Winbond chips for testing.
Finally, in case you're wondering why I connected an oscilloscope to my ethernet and ran into this phenomenon in the first place: well, that happened while developing the hardware for my software-defined radio project.
Comments are welcome at email@example.com.
Back to my "miscellaneous" webpage.