Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Random Number Generator for Back-off Algorithm (Ethernet)

IP.com Disclosure Number: IPCOM000018633D
Publication Date: 2003-Jul-29
Document File: 9 page(s) / 158K

Publishing Venue

The IP.com Prior Art Database

Abstract

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.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 58% of the total text.

Page 1 of 9

Title : Random Number Generator for Back-off Algorithm (Ethernet)

Problem:

Requirements

----------------

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.

Problem

--------

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.

Solution :

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

(1,048,576 counts).

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

sequence.

Th...