Ethernet Operations: Random Generator
Back-off is an important feature of the Ethernet MAC protocol. After a collision is detected through the MII/RMII interface, ASH1 should stop transmitting (there are more specific details about when exactly to stop transmission) and then reschedule its retransmission by generating a period of time to wait before retransmission. The period of time is based on a random number chosen by ASH1 and used in its back-off calculations.
The amount of total back-off delay is calculated by multiplying the slot time by a randomly chosen integer. The range of integers used in the choice is generated according to the rules of the back-off algorithm, which create a range of integers that increases in size after each collision that occurs for a given frame transmission attempt. The interface then randomly chooses an integer from this range, and the product of this integer and the slot time creates a new back-off time.
The back-off algorithm uses the following formula for determining the integer r, which is used to multiply the slot time and generate a back-off delay: where k = min(n,10).
0 < r < 2^k
To translate into something closer to English:
• r is an integer randomly selected from a range of integers. The value of r may range from zero to one less than the value of two to the exponent, k.
• k is assigned a value that is equal to either the number of transmission attempts or the number 10, whichever is less.
This algorithm can be implemented by ASH1 by the following:
- Creating a 10-bit counter that is incremented on the rising edge of ASH1 clock. Thereby, we can have a random number generator.
- By keeping track of the number of collision happened so far, we can choose the random number range by ANDING the 10-bit counter with (no. of collisions -1).
- Keep in mind that after 10 collisions, the range will be the same. And after 16, ASH1 must report an error.
Now, how to implement this:
The main point is to come up with a random generator unit that will generate random integers based on the number of collisions taken place so far. so basically the random generator unit will have an 4-bit input ( top of stack) determining the range of the random number and the output will be a 10-bit number that can be pushed on the stack to make use of it for the back -off time.
Implementing the random generator can be done either by using a counter as we’re sampling this counter at an unknown random time, yet it might not be so random as it’s going up and rolls over again. A better way is to use some kind of linear feedback shift register.
After implementing the random generator, this is what I got (you can check with the range in the table at the bottom of the post):
I’ve generated a random light sequence of DE2 board using ASH1 here : Random_Generator_Light_Sequence