Gregory's ServerTo recover from a collision, each computer waits a random time and tries again. If there's another collision, they double the wait time and keep trying. (Kind of like two people talking at the same time, pausing, and trying again.) This is " exponential backoff". 4/14
|
13 comments
 Each bit is implemented with a "dynamic latch". When the clock is high, the pass transistor turns on, connecting the two transistors in a stable loop, holding the bit. When the clock is low, the transistor capacitance holds the value (like DRAM)A or a new value can be input. 6/14 Adding a few more transistors makes a circuit that can be toggled, flipping its value. Ten of these toggle latches makes the counter. But each bit needs a circuit to decide when to toggle. 7/14 To count, a bit is toggled when all the lower bits are 1 (just like a carry in decimal addition). So the counter has a bunch of logic gates to generate the ten toggle signals. 8/14 Here's how the 10-bit counter looks on the die. I removed the chip's metal layer so you can see the transistors underneath, constructed from silicon and polysilicon. 9/14 The 10-bit mask register grows exponentially: binary 1, 11, 111, 1111, etc. It can be initialized with 1-8 bits set, or shift left to grow by one bit. 10/14 Here's the circuitry for the mask register. Three input lines select how many bits for the mask, decoded by a bunch of gates. 11/14 So that's how exponential backoff was implemented on the Intel 82586 Ethernet chip. Also my previous tweets on the Intel 82586: A bonus photo of the 82586 die with the metal layer removed, showing the underlying circuitry. I stopped dissolving the oxide layer a bit too soon, so it's a bit ugly. There are some random colored areas due to thin-film interference. The bond wires are around the edges. 14/14  Have you come across any errata where the 82586 ring handling has a bug and the part goes deaf until you reset it? I know it had a bug like that but now I cant find the errata for the part. @bitsavers Robert Garner is trying to track down the errata sheet for the 82586; he might know more.  @kenshirriff I recall the story of an ethernet card which performed much better than all of its competitors in a bake-off. It turned out that they purposely ignored "exponential backoff" and re-blasted their packets much sooner than other cards, so they naturally performed better than all the rest once collision rates went up. Worst for the LAN as a whole of course, but better for them. |
On the 82586 chip, exponential backoff is implemented with three circuits: a 10-bit counter to generate a pseudorandom number, a 10-bit mask register to select an (exponentially scaled) part of the counter, and a delay counter to loop that many times before trying again. 5/14