Random Number Generator for Back-off Algorithm (Ethernet)
Publication Date: 2003-Jul-29
The IP.com Prior Art Database
IEEE 802.3 specification requires the Media Access Controller (MAC) to meet the following four criterions for the Truncated Binary Exponential Back-off Algorithm (TBEB) in half duplex mode. This implementation uses two 10-bit controlled LFSRs. Since a 10-bit LFSR counts only up to 1023 counts.
Title : Random Number Generator for Back-off Algorithm (Ethernet)
IEEE 802.3 specification requires the Media Access Controller (MAC) to meet the following four criterions for the Truncated Binary Exponential Back-off Algorithm (TBEB) in half duplex mode.
1.The generated integer to calculate the back-off time (integer times the slot
time) on every collision should be uniformly distributed over the range
0 through 1023
2.The generated integer should be random
3.The generated integer should not be more aggressive than the specified limit
for each successive collision.
4.The generated integer should minimize the correlation between the numbers
generated by any two stations at any given time.
Most of the existing implementations use a free running 16-32 LFSRs to generate
pseudorandom number for the back-off algorithm implementation in Ethernet
(Half-duplex mode). Even though this implementation meets the randomness,
meeting uniform distribution over the range 0-1023 is not possible because of
the following reasons.
1.Selecting up to 10-bits (required for back-off algorithm) from a larger
counter might end up in repeating the same number more than once within
one full sequence.
2.The occurrence of collision (which is random) might end up in picking a
number that follows non-uniform distribution because of free-running nature.
Unlike most implementation, which uses larger free running counter for the
back-off algorithm, this implementation uses two 10-bit controlled LFSRs.
Since a 10-bit LFSR counts only up to 1023 counts (excluding the value
10'b0000000000), the missed count will be stuffed after the last count in
both the LFSRs. The LFSR1 counts on every collision seen on the Ethernet cable;
the LFSR2 counts once the LFSR1 reaches the last count. The XORing of the
outputs of the two LFSRs will generate 1024 unique pseudorandom count of 1024
The uniform distribution of the sequence can be verified by chi-square method.
The randomness of the sequence can be verified by the auto-correlation
function or the uniform distribution of a count following any count of the