Electrical computers and digital processing systems: multicomput – Computer network managing – Network resource allocating
Reexamination Certificate
1998-09-21
2002-09-24
Geckil, Mehmet B. (Department: 2152)
Electrical computers and digital processing systems: multicomput
Computer network managing
Network resource allocating
C709S209000, C709S223000, C709S226000, C709S229000, C709S244000, C707S793000
Reexamination Certificate
active
06457053
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to distributed computer systems, and more particularly to a multiserver system for unique identifier allocation.
BACKGROUND OF THE INVENTION
Generally, in modern computing systems, unique identifiers (such as security identifiers or a relative identifier thereof) are associated with system generated objects to clearly identify an object to the system and distinguish any one object from others in the system. Users, groups of users, files, and hardware components such as servers and printers are all typically considered objects which have a unique identifier associated therewith. Unique identifiers are used by most systems to associate privileges with objects and in general to manipulate objects within the system. Those skilled in the art recognize that in a modern computing system, the generation and maintenance of unique identifiers plays a critical role in the successful operation of the system.
In existing distributed computer operating systems, where a limited number of unique identifiers exist in single group from which the identifiers may be allocated, the task of allocating the unique identifiers has traditionally been performed by a single “master server.” Thus, in existing systems, a single server has the capability to generate unique identifiers and all other computers in the system are configured to refer to the single server when a unique identifier is needed. In every instance where a new object needs to be generated, the single master server must be contacted.
There are of course limitations associated with single master server designs. In modern computing systems, very large numbers of unique identifiers may be requested, often in a very short time frame. Assigning a single server to service requests from throughout a network can place a significant burden on the processing capabilities of a single master server. As a consequence, requests may not be serviced quickly or, worse the master server may simply fail. If a master server responsible for generating unique identifiers crashes, the remaining network machines cannot obtain new unique system identifiers and therefore may be unable to generate new system objects. Further, even when a master server's absence from the network is scheduled, as in the case of system maintenance, a new master server needs to be promoted to master and the remaining servers on the network need to be re-configured, typically by manual means, to communicate with the new master.
Multi-server allocation designs have previously been proposed to relieve a single server from having to support an entire network. Several previous multi-server designs have employed globally unique identifiers (GUIDs). GUIDs are generally
128
bit long identifiers.
48
bits of a GUID's
128
bits identify the network card contained in the server that created the GUID. By agreement between network card vendors, each network card (across all vendors) is supposed to have a unique network card identifier associated therewith. This allows each server machine in a network to generate unique GUIDs independently of the other servers in a network simply by concatenating the network card's unique identifier with another string which the particular server knows it has not previously assigned. Because these systems can assume that the network identifiers for each card is unique, the further assumption is made that any unique string that is concatenated with a unique identifier will also be unique within the network.
Multi-server unique identifier systems which employ GUIDs have several limitations. First, the uniqueness of the identifiers is dependent upon prior human agreement, i.e. the agreement between network card vendors to assign unique identifiers to each network card. Error on the part of a network card vendor in assigning unique identifiers to network cards, say for example assigning the same identifier to two network cards, introduces error into the process of generating unique system identifiers. Also, systems relying on GUIDs operate on a probabilistic uniqueness model as opposed to a deterministic model. In probabilistic models which rely on generating large random numbers to create unique identifiers, uniqueness can not in fact be guaranteed although the chance of creating non-unique identifiers is made very small. In a deterministic model, uniqueness is guaranteed. Finally, GUID systems are restricted in the address space that can be used to create unique identifiers. GUIDs are typically constrained to 128 bits and their uniqueness is limited to the 48 bits used to identify the network card.
Thus, there is a need in the art for a system which provides the simplicity associated with a single master server but which also relieves the single master server from the burden associated with a single server fielding all requests for unique identifiers from the entire network. Further, there is a need for a multi-server unique identifier system which does not rely upon prior human agreement to insure uniqueness. Additionally, the system should not be restricted to an address space in which it can operate but rather should be adaptable for use in address spaces of varying sizes depending on the nature of the application.
SUMMARY OF THE INVENTION
Briefly, the present invention provides a system for multi-master unique identifier (e.g., RID) allocation. A single master server allocates “pools” of unique identifiers to network servers upon request. The network servers in turn allocate unique identifiers from the pool of identifiers which it received from the master server. When a network server's pool of unique identifiers is nearly depleted, the network server requests an additional pool of identifiers from the master server. The physical server machine which performs the role of master server may be transferred as needed to ensure that a master server is always available to allocate pools of identifiers to the other, non-master servers. The system includes protocols for gracefully restoring to the network servers, including the master server, which had temporarily been removed from the network. It should be noted that while the present invention is described with respect to am exemplary embodiment involving relative identifiers (RIDs), the invention applies more generally to any type of unique identifier and is in no way limited to the allocation of RIDs.
REFERENCES:
patent: 5768519 (1998-06-01), Swift et al.
patent: 5812773 (1998-09-01), Norin
patent: 5884322 (1999-03-01), Sidhu et al.
patent: 5987506 (1999-11-01), Carter et al.
patent: 5991279 (1999-11-01), Haugli et al.
patent: 6128654 (2000-10-01), Runaldue et al.
Steedman, D.,X.500 the directory standard and its application, Technology Appraisals, 1993, 1-165.
Brace Colin H.
Hacherl Donald J.
Mayhall Chris L.
Satagopan Murli D.
Straube Dave D.
Farahi Farzaneh
Geckil Mehmet B.
Microsoft Corporation
Woodcock & Washburn LLP
LandOfFree
Multi-master unique identifier allocation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-master unique identifier allocation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-master unique identifier allocation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2878045