Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1995-05-26
2001-10-02
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S256000
Reexamination Certificate
active
06298360
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the generation of random numbers. More particularly, the invention relates to random number generation for a computer system on a computer network.
2. Description of the Related Art
A primary function of a computer networking protocol is to provide an efficient and reliable protocol for the transmission of network packets between computer systems on a computer network.
In a networking environment, a collision is an event in which two or more computer systems on the computer network attempt simultaneous packet transmissions. Computer networking protocols can be divided into two general classes with respect to their collision avoidance techniques; collision abstinence protocols and collision reduction protocols.
FIG. 1A
shows a computer network
100
which includes a plurality of computer systems
111
,
112
, . . .
119
coupled together by a computer networking medium
190
.
In collision abstinence protocols, collisions are effectively prevented by a token-passing scheme or equivalent in which only one computer system has possession of a token at an instance in time. The only computer system permitted to transmit on networking medium
190
at that instance is the owner of the token. One example of a token-passing scheme is a token ring network.
In contrast, collision reduction protocols require computer systems to listen on the networking medium
190
while transmitting a packet and to retransmit the packet whenever a collision is detected, e.g. Ethernet's collision sense multiple access/collision detect (CSMA/CD) protocol. Subsequently, in order to reduce the probability of another collision clue to simultaneous packet retransmissions, every computer system involved in the initial collision is responsible for backing off for a randomly distributed time interval before attempting another retransmission. In the case of the CSMA/CD protocol, the scheduling of retransmissions is determined by a process called “Truncated Binary Exponential Backoff” which provides a random integer “r”, in a range suitable for the transmission medium, for determining the back-off time interval before the retransmission.
Integer “r” must satisfy two main criteria in order to minimize packet collisions while ensuring fair access to the computer network. First, random integers (“r”) generated over a period of time should be uniformly distributed over a predetermined range of integers. Second, apparatus/methods for generating integer “r” should ensure that there is minimal correlation between the random integers generated for any two computer systems on the same network. Typically, a random number generator is used to select a suitable back-off time period for rescheduling the packet retransmission. Conventional random number generators include a free-running digital counter and an analog noise source coupled to an analog-to-digital converter, both of which have inherent disadvantages.
For example, digital counters of computer systems coupled to the computer network have a tendency to synchronize upon a network-wide reset caused by for example a network-wide power failure. Further, these counters will continue to increment at approximately the same rate and cause multiple collisions as the computer systems back off for similar time periods. In the case of partially analog solutions such as noise generators, analog circuitry is combined with digital circuitry. As such, a single integrated chip solution requires relatively complex hybrid semiconductor processes, e.g., BiCMOS process. In addition, analog-to-digital converters, occupy substantial semiconductor real estate.
Hence there is a need for a reliable random number generator that produce uniformly distributed numbers in a truly random manner, and is both inexpensive and easy to implement.
SUMMARY OF THE INVENTION
The present invention provides a random number generator, useful in association with a computer system on a computer network, for generating a randomly distributed back-off time interval between a collision and the retransmission of the packet, e.g. for Ethernet's collision sense multiple access/collision detect (CSMA/CD) protocol. The random number generator includes a data-based number generator, a timer-based number generator and a number combiner. The combiner accepts the output numbers from data-based and timer-based number generators, and in turn generates a random number.
In one embodiment, a user-selectable initialization number is provided as a seed number for the data-based number generator. In this implementation, the initialization number is a unique network address. Subsequently, the same initialization number or a different number can be loaded into data-base number generator. A cyclic redundancy check (CRC) generator provides numbers for data-based number generator on a continuous basis, after initialization has been completed.
A free-running timer provides numbers for the timer-based number generator. The user selectable initialization number is also provided as a seed number for the timer-base generator. Alternatively, a different initialization number can be provided to timer-based number generator. Subsequently, the same initialization number or a different number can be loaded into time-base number generator.
In this implementation, a feedback path is provided between the output node of the data-based number generator and an adder of the data-based number generator. In another implementation, a feedback path is provided between the output node of the random number generator and the adder of the data-based number generator.
In this embodiment, the number combiner includes an exclusive “OR” (“XOR”) circuit. However, other suitable logical and/or mathematical functions can be substituted in place of the “XOR” function, e.g., “OR”, “NAND”, addition, and multiplication.
Advantages of the present invention include a simple digital-only circuit that is easy to fabricate. In addition, the random number generator leverages off existing networking circuitry, e.g., the CRC generator.
Hence, by generating random numbers evenly distributed over a predetermined range, the random number generator of the present invention provides suitable random numbers for determining back-off time intervals between packet retransmissions of a computer system coupled to a computer network.
REFERENCES:
patent: 4769777 (1988-09-01), Bittle et al.
patent: 4771429 (1988-09-01), Davis et al.
patent: 4852023 (1989-07-01), Lee et al.
patent: 5153532 (1992-10-01), Albers et al.
patent: 5420928 (1995-05-01), Aiello et al.
patent: 5438622 (1995-08-01), Normile et al.
patent: 5515307 (1996-05-01), Aiello et al.
Lim, Esq. Kang S.
Mai Tan V.
Sun Microsystems Inc.
LandOfFree
Method and apparatus for generating a highly random number... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating a highly random number..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating a highly random number... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2573037