Electrical computers and digital processing systems: multicomput – Computer network managing – Network resource allocating
Reexamination Certificate
2000-10-06
2004-06-15
Eng, David Y. (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer network managing
Network resource allocating
C708S250000
Reexamination Certificate
active
06751667
ABSTRACT:
BACKGROUND OF THE INVENTION
Technical Field
The present invention relates generally to the identification of components in a computer network and more particularly, to a system for generating universally unique identifiers (UUIDs) for software objects and other components in a network in which a large number of components may exist simultaneously and/or over a period of time.
STATEMENT OF THE PROBLEM
Structured computer information depends heavily upon unique identification of data objects. Generation of unique identifiers for these data objects, as well as other computer network components, is a challenging problem. Because of the wide deployment and redeployment of computer systems and data, it is necessary for these identifiers to be unique over time and space. Such an identifier is generally termed a Universally Unique Identifier, or ‘UUID’. In addition to the uniqueness requirement, which can be achieved by assigning identifiers through a central authority, it is also desirable to be able to generate new UUIDs rapidly via software, while still preserving the uniqueness of each object.
Solutions to this problem exist that create UUIDs based upon the IEEE 24-bit ‘company ID values’ that can be obtained from the IEEE Registration Authority. In addition, UUIDs may be created by using the various NAA (Network Address Authority) formats described in the
Fibre Channel Physical and Signaling Interface—
3 (
FC
-
PH
-3)
Rev
9.4, Nov. 5, 1997.
There are usually three components to a UUID. The first component is the IEEE company ID assigned by the IEEE Registration Authority. This component is complex and slow to assign, as the registration process takes place via mail. The second component is the NAA format, consisting of additional bit combinations assigned to particular products under the control of the company owning the IEEE company ID. The third component is typically assigned by software managed by a particular product, such as a disk storage array controller. This third component consists of the bit combinations remaining in the UUID which are assigned (usually sequentially) to produce the complete UUIDs as needed.
There are two subclasses of these solutions. The first subclass is created with the assumption that there is a statistical improbability of generating duplicate UUIDs using timestamps and certain hashing techniques. The second subclass of solution utilizes persistent storage of previously generated UUIDs to prevent re-generation of duplicate UUIDs. The first solution is generally deemed to be unacceptable due to the unbounded behavior of duplicate UUIDs, which are inevitably created using that technique. Implementation of the second solution is challenging due to the expense of high speed persistent storage (e.g., reliable battery backed up RAM) and the low speed of inexpensive persistent storage (e.g., flash memory).
SOLUTION TO THE PROBLEM
The present invention overcomes the aforementioned problems of the prior art and achieves an advance in the field by providing a method which combines the high speed of volatile RAM (without a requirement for battery backup) and the low cost of non-volatile memory such as flash memory (without the requirement for high speed) to generate identifiers that are consistently unique.
In accordance with the method of the present invention, the third component of the UUID (discussed above) generated by a particular product is further divided into two sub-fields. One (sub-) field is stored in (relatively slow) non-volatile memory, and incremented infrequently. The other (sub-) field is stored in relatively fast, volatile RAM, that can be incremented quickly. During normal operation, the product creating the UUIDs generates new UUIDs by incrementing the field stored in RAM. When overflow of the RAM field occurs, the field stored in non-volatile memory is incremented. The size of the field stored in RAM is selected to cause the more expensive incrementing of non-volatile memory to occur sufficiently infrequently to minimize the impact of slow access, while maintaining a reasonable lifetime. If the product generating the UUIDs should lose the contents of RAM (due to reboot, power failure, or malfunction) it merely increments the field in non-volatile memory and resets the RAM field to zero.
When using flash memory, which has a limited number of erase/write cycles, the present invention takes advantage of the fact that multiple writes can be performed between erase cycles, as long as they only change bits from ones (1) to zeros (0), and not vice-versa. The present invention operates by initializing a block of flash memory to all ones, and then sequentially clearing (zeroing) the bits to generate each subsequent unique identifier. This method provides the equivalent of a counter that can count up to the number of available bits in the non-volatile memory block while reducing the number of flash memory erase cycles to one cycle for each time all the bits are cleared. Reducing the number of flash erase cycles is of critical importance, since flash memory is limited in the number of erase operations that can be performed over the lifetime of the memory.
REFERENCES:
patent: 4819818 (1989-04-01), Simkus et al.
patent: 5541996 (1996-07-01), Ridenour
patent: 5778069 (1998-07-01), Thomlinson et al.
patent: 6243738 (2001-06-01), Hayles et al.
patent: 6324558 (2001-11-01), Wilber
patent: 6490637 (2002-12-01), Shih
patent: 6532497 (2003-03-01), Cromer et al.
patent: 6533664 (2003-03-01), Crumby
patent: 6628786 (2003-09-01), Dole
LandOfFree
System for generating unique identifiers in a computer network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for generating unique identifiers in a computer network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for generating unique identifiers in a computer network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3349492