Method and apparatus for moving subtrees in a distributed network directory

Abstract

A method and apparatus for reorganizing a distributed directory is disclosed. A source logical group, such as a partition, is identified for reorganization. A destination object is selected to which the source logical group will become subordinate. Multiple simultaneous reorganizations of the distributed directory can be handled.

Claims

We claim:

1. A method in a computer system for reorganizing a distributed directory having a hierarchy of objects, comprising the steps of:

a) identifying a non-root source object within a first logical group, said source having one or more subordinate objects, said source object being directly subordinate to a parent object;

b) identifying a destination object;

c) requesting to change the direct subordination of the source object to the destination object;

d) checking if the requested change is permitted;

e) if the requested change is permitted, splitting the first logical group at the source object whereby the source object becomes a root object for a second logical group;

f) if first logical group was successfully split, reorganizing the hierarchy of objects in the distributed directory such that the source object is directly subordinate to the destination object.

2. A method as recited in claim 1, wherein the checking step comprises one or more of the following steps:

(a) enforcing access control;

(b) enforcing directory schema rules; or (c) checking whether a software version can support the requested change.

3. A method as recited in claim 1, further comprising the step of joining the second logical group with the first logical group after the step of reorganizing if the destination object is within the first logical group.

4. A method as recited in claim 1 wherein the step of reorganizing is achieved by one or more of the following steps:

a) for each computer having at least one of the following:

(i) a replica of the second logical group and a replica of the destination logical group,

(ii) a replica of the second logical group and a reference to the root object of the destination logical group,

(iii) a replica of the second logical group and neither a replica of the destination logical group nor a reference to the root object of the destination logical group, or

(iv) a reference to the root object of the second logical group and a reference to the root object of the destination logical group, changing in each such computer the parent of the source object from the parent object to the destination object;

b) for each computer having at least one of the following:

(i) a reference to the source object and a replica of the destination logical group, or

(ii) neither a replica of the second logical group nor a reference to source object, and a replica of the destination logical group, creating in each such computer a reference to the second logical group; and

c) for each computer having a reference to the source object and neither a replica of the destination logical group nor a reference to the root object of the destination logical group, creating in each such computer a reference to the destination object.

5. A computer readable medium, comprising software capable of performing the method of claim 1.

6. A computer system capable of performing the method of claim 1.

7. A method as recited in claim 1, wherein the one or more of the logical groups is a partition in the distributed directory.

8. A method, in a computer system accessing a distributed directory having a hierarchy of logical groups of objects, for simultaneously reorganizing the hierarchy of one or more logical groups, comprising the steps of:

a) identifying a plurality of source logical groups each having a root object, one or more of the objects in the plurality of source logical groups having a distinguished name representing the hierarchal sequence of the object in the distributed directory;

b) identifying a destination object for each of the plurality of source logical groups;

c) requesting a reorganization of the hierarchy that the root object for each of the source logical groups will be directly subordinate to the respective destination object;

d) reorganizing the hierarchy of logical groups in accordance with the request; and

e) referring to objects in the source logical groups by the variations of the distinguished names in view of the requested reorganizations.

9. A method as recited in claim 8, wherein at least one of the source logical groups is a non-leaf partition.

10. A method as recited in claim 9, wherein at least one of the source logical groups is subordinate to another of the source logical groups.

11. A method as recited in claim 8, wherein one or more of the logical groups is a partition in the distributed directory.

12. A computer readable medium, comprising software capable of performing the method of claim 8.

13. A computer system capable of performing the method of claim 8.

14. A method as recited in claim 8, wherein the step of recognizing involves modifying the pointers in one or more computers such that the parent objects of the root object for the plurality of source logical groups is changed to the corresponding destination object.

15. A method as recited in claim 8, further comprising the step of referring to objects subordinate to the source logical groups by the variations of the distinguished names in view of the requested reorganizations.

16. A computer system, comprising:

a) a plurality of computers capable of sending information to and from one another;

b) a distributed directory accessed by the plurality of computers, said distributed directory having a hierarchy of objects;

c) a source logical group in the distributed directory, said source logical group comprising one or more objects having a distinguished name representing the hierarchal sequence of the object in the distributed directory, said source logical group further comprising a root object directly subordinate to a parent object;

d) a destination object in the distributed directory;

e) a reorganization mechanism capable of changing the subordination of the root object from being directly subordinate to the parent object to being directly subordinate to the destination object, wherein while the reorganization mechanism is changing the subordination of the root object the computers refer to one or more objects in the source logical group by one or more of the possible name states of the one or more objects.

17. A computer system as recited in claim 16, wherein the source logical group is a partition.

18. A computer system as recited in claim 16, wherein the variations of the distinguished name include changes in subordination of objects superior to the root source object.

19. A computer system as recited in claim 16, wherein the objects in the source logical groups may be accessed while the reorganization mechanism is changing the subordination of the source logical group.

20. A computer system as recited in claim 16, wherein the plurality of computers record references of the changing distinguished names of the objects in the source logical group.

21. A computer system as recited in claim 16, wherein at least one of the plurality of computers refers to the to one or more objects in the source logical group by one or more variations of the distinguished names known to the at least one computer.

Description

TECHNICAL FIELD

The present invention relates generally to distributed directories, and will be specifically disclosed as a method and apparatus for reorganizing objects within a distributed directory.

BACKGROUND

Technological advances in microelectronics and digital computing systems have resulted in the proliferation of digital computer networks, enabling the distribution of networking services across a wide range of computers participating in the network and over various communications media. Advances in distributing applications have also resulted in a client-server architecture for applications. Under the architecture, the portions of the application that interact with the user are typically separated from the portions of the application that fulfill client processing requests. Typically, the portions of an application that interact with the user are called a client applications or client software, whereas the portions of the application that service requests made by the client applications are called a server applications or server software. In a network environment, the client applications and server applications are generally executed on different computers.

Historically, digital networks in the form of local area networks, a physical collection of personal computers interconnected with network cabling and network interface cards, consisted of a single network server and multiple network clients. To manage which network clients could access the network server, as well as what files, printers, printer queues, and server applications were available to the network clients, the network server maintained information on each of the resources that were attached to the server and the identities of the network clients and users who could use the services of the network server and the scope and nature of the services available to the network clients and users.

As local area networks became more popular, networks grew in size requiring several servers to service the needs of users. With increased size and complexity of networks, came the need for easier management of network servers. Users required access to an increasing number of services that were located on an increasing number of network servers. Several vendors began offering networking servers. Each vendor implemented a different scheme of providing networking services information. In addition, each network server, because of the way the server maintained information about only its networking services still required management of its resources independently of other network servers.

This insular method of maintaining information of networking services fueled research and development of distributed networking directories, databases that spanned networking servers. Thus far, research has resulted in several potential solutions. Three technologies currently hold greater promise for replacing the large number of insular, idiosyncratic directories that now litter many an enterprise's numerous local-area networks and electronic-mail systems. One approach exploits the X.500 distributed network information directory services protocol developed as published by the CCIT and Open Systems Interconnect consortium.

However, while the X.500 protocol appears to hold the greatest promise to provide a robust, distributed directory, the X.500 protocol has been slow to gain acceptance. The X.500 protocol has been plagued from the start with management, interoperability and security problems. The X.500 protocol specification describes a technical framework, interoperability requirements and compliance criteria but does not describe specific implementations. Thus many of the details of implementation have been left up to systems providers.

The X.500 protocol specification describes a distributed directory. The directory provides information services to network clients. The information in the directory can be read as well as modified by users who have applicable access rights.

The information stored in the directory is a collection of objects with associated attributes or properties. FIG. 1 shows an object called "Computer" with some associated properties, such as owner, operator, status, etc. The values of the properties are not shown in the figure but an example of a value for "Owner" might be "Fred." Objects in the directory and their names correspond to things that humans relate to when dealing with computers, namely, users, printers, print queues, networks and information. Objects such as countries, organizations, networks, people and computers are objects you might find in the directory as well.

The directory provides information to users by giving users a hierarchical view of all of the information contained in the directory. The hierarchical view is generally in the form of a tree. FIG. 2 shows a directory. Each of the branches and terminating points or leaves represent objects in the directory. Generally, implementations of the directory organize objects in subtrees, partitions or domains. FIG. 2 also shows the directory organized into partitions or domains. Multiple copies of each partition may be stored in the directory. Software schemas define and determine the number and types of replicas of each partition.

Multiple replicas of a partition are needed to reduce network storage and traffic requirements and speed up directory searches. Replicas are stored in name servers. A name server is a computer in the network, usually a network server. More than one partition can be stored in a name server. Partitions stored in a name server need not be contiguous.

The directory tree provides a logical means of searching for information. The tree is generally patterned after logical groupings such as organizations, organizational units, computers and users. These logical groupings, while extremely useful in helping users find relevant information also creates significant problems in managing the directory.

Each partition forms a major subtree of the directory. Taken together, the partitions form a hierarchical tree of partitions that leads back to a root partition containing the root directory. Where boundaries of two partitions meet, the partition closer to the root is considered superior, and the partition farther from the root is considered subordinate. Thus, FIG. 2, partitions E and C are subordinate to the other partitions.

The present invention solves one of those problems. As objects of the directory change, the directory must be changed as well. Organizations, organizational units, computers and users all move. Today, the legal department may be reporting through the finance department. Tomorrow, one of the employees of the finance department might be moved to marketing. Prior to the invention, systems administrators responsible for maintaining a directory had to move each object in the directory in response to a real change in the status of the object. Unfortunately, no facilities existed for moving course grain objects such as an entire department. If the legal department was to be moved to report to the finance department, each object in the legal subtree had to be moved separately.

SUMMARY OF THE INVENTION

With the present invention any portion of a directory tree provided that it is at the end of the tree may be moved either within a directory or to another directory. With the invention, ease of providing administration of distributed network directories increases. Accordingly, use of distributed network directories will also increase, making pervasive network computing possible.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention may be more fully understood by reference to the following Detailed Description in conjunction with the Drawings, in which:

FIG. 1 shows a typical directory object, a computer, with some of its associated attributes;

FIG. 2 shows a typical directory tree;

FIG. 3 shows a hypothetical scheme of replicas;

FIG. 4 shows how external references use back links;

FIG. 5 shows how the NDS protocol fits within the family of NetWare communications protocols;

FIG. 6 shows the packet structure of NDS packets;

FIG. 7 shows the sequences employed by the invention to move a leaf object;

FIG. 8 shows the movement of a subtree;

FIG. 9 shows an example of moving a leaf portion;

FIG. 10 shows an example of a multiple simultaneous moves of partitions;

FIG. 11 shows a move of a non-root logical grouping; and

FIG. 12 shows a move of a non-root logical grouping within a partition.

DETAILED DESCRIPTION OF THE INVENTION

The present embodiment of the invention, Novell's NetWare Directory Service or NDS, supports moving a terminal or leaf object or partition to allow reorganizing a subtree. Any portion of a directory tree provided that it is at the end of the tree may be moved either within a directory or to another directory.

NDS is based on the X.500 standard and implemented within Novell's NetWare network operating system. Novell implementation of NDS is based on the X.500 standard specification. The X.500 specification does not provide all of the details necessary to implement a distributed network directory.

NDS is implemented within the NetWare network operating system in terms of Novell's native NetWare protocols and a new native protocol called the NDS Protocol. The other components of the native protocols implemented in the NetWare network operating system are illustrated in FIG. 5. IPX is NetWare's native network layer protocol. It provides end-to-end, best-effort datagram delivery. It conveys traffic across a local area network (LAN), a wide area network (WAN), or any internetwork of connected WAN and LAN data-links of like or unlike kinds. An IPX internetwork address has three parts, a Network Number (four bytes) which identifies a network segment, a Node Number (six bytes) which identifies a computer on that segment, and a Socket Number (two bytes) which identifies a software entity within the computer. As an alternative to IPX, NetWare protocols can operate over IP.

The RIP (Routing Information Protocol) supports forwarding of IPX packets over an internetwork. Routers are the devices that connect network segments together. Traditionally, IPX routers exchange connectivity information with each other using RIP to determine proper paths for data packets to take. RIP uses a periodic broadcast mechanism.

The SAP (Service Advertising Protocol) is similar in concept to RIP, but the information exchanged describes services and their addresses (rather than network connectivity). Routers disseminate SAP information as they do with RIP. Through SAP, clients can rendezvous with servers of many kinds. SAP is used to bootstrap a client into the NDS world: a client uses SAP to locate its first NDS server when initializing.

NLSP (NetWare Link Services Protocol) is a newer routing protocol designed to scale to larger environments than RIP and SAP. It plays the role of RIP and SAP for large internetworks. It conveys the same information as RIP and SAP, but instead of using periodic broadcast it sends updates when changes occur.

NCP (NetWare Core Protocol) implements NetWare services such as remote file access. As shown in FIG. 5, NDS packets ride inside NCP packets. While most of this description deals with NDS messages, implementing NDS also involves a few new NCP verbs.

FIG. 6 shows the structure of NDS packets with NCP packets. The data-link header and trailer are media-specific, and are documented in the standard for each LAN or WAN technology. The message formats in this description define an offset for each field. The offset is from the start of the NCP portion of the packet. The first byte of the NCP header is at offset zero. The request/reply fragmentation header is the means of conveying an NDS request and response in a series of NCP request/response exchanges. The arrangement of fields in the NDS data portion of the packet varies, depending on the verb field of the NDS header. Later sections of this document specify the packet formats in detail.

A Completion Code field exists for NCP replies and for NDS replies that ride (fragmented) within NCP. In both cases, Completion Code=0 means "success." Nonzero values report various error conditions.

Moving a Leaf Object

From a network client vantage point, moving a subtree looks the same as moving a single leaf object. From a server standpoint moving a subtree and moving a single leaf object are quite different. The details of moving a leaf object are provided below. The details of moving an entire subtree, and the move from the vantage point of a server, are considered below. See "Moving a Subtree" below.

When a NDS network client moves an NDS directory entry from one container object to another in the tree, it is possible that the source and the destination container objects are in different partitions. A container object is any object that can hold another object, such as a subtree. When a network client moves the NDS entry, there might not be any servers holding a writeable replica of both partitions.

Each partition can have replicas on several servers. Suppose there are three NDS servers for a name tree: servers S, T, and U. One possible deployment of replicas for FIG. 2 among the servers is illustrated in FIG. 3. There are no restrictions on the placement of replicas together on servers; for example, the replicas stored together on a server need not represent contiguous partitions.

Sometimes, a name server has to keep information about objects that can be outside the replicas it holds. The best examples are the objects superior to its replicas in the tree. Consider FIG. 4. The objects A and Root are not in a replica of a partition on server T. But to know the name of objects in Q, T needs the name of A. This information is kept in a data structure called an external reference. Since an external reference is not in a replica, it is not synchronized with other servers. However, it does have an entry identification valid on the server where it resides (T in this case). If A's name changes, the external reference has to be updated. To allow this, the object A has a back link attribute value pointing to each external reference to A. This is the dotted line in FIG. 4.

Because there might not be any servers holding a writeable replica of both partitions when a client attempts to move an NDS entry, moving an object involves two operations: "Begin Move Entry" and "Finish Move Entry."

The detailed steps of moving a leaf object are:

1. The client identifies two servers. The source server is the one holding the master replica of the object being moved. The destination server is the one holding the master replica of the container into which the object is being moved. Sometimes, the servers are the same, but the same procedure applies regardless.

2. The client sends a "Begin Move Entry" request to the destination server. At this point, the destination server enforces access control to permit or deny the operation. The "Begin Move Entry" NDS Protocol verb has the structure identified in Table 1.

                  TABLE 1
    ______________________________________
    Begin Move Entry Structure (42 (0x2A))
    Offset     Content           Type
    ______________________________________
    Request Format
    32         Version = 0       Int4
    36         Flags = 0         Int4
    40         Destination Parent Entry ID
                                 Int4
    36         New RDN           Ustring
    . . .      Align4
    . . .      Source Server's DN
                                 Ustring
    Reply Format
    16         Completion Code   Int4
    ______________________________________
     *Int4  a byte integer transmitted in LowHigh order
     *Ustring  a nullterminated Unicode string. Unicode is a fixedlength
     character encoding scheme, 16 bits per character. It defines encodings
     from all the world's languages. The representation was chosen to have
     fixed width to facilitate processing. In Unicode, the range from 0x0000
     through 0x007F is sevenbit ASCII (that is, ANSI X3.4).
     *Align4  is a pad field of zero to three bytes making the next field star
     on twobyte boundary.
     * . . .  When a variablelength field occurs, the subsequent fields are no
     at a fixed offset. Ellipses appear in the offset column to indicate this.
     *Completion Codes Success = 0
     *Distinguished Name or DN  is a representation of the sequence of
     hierarchical components. An NDS object is identified by its name and by
     the names of the objects in which it is contained, in a hierarchical tree
     structure. The object's own name is called its partial name, or RDN (for
     Relative Distinguished Name). Proceeding up the hierarchy, each containin
     object has its own RDN. For  # example, CN = Jan. O = Acme. C = US has
     three partial names (RDNs). The Common Name is "Jan." The Organization
     Name is "Acme." And, the Country Name "US.
     This request is addressed to the server holding the master replica of the
     destination container. The new parent of the NDS object is identified by
     Destination Parent Entry ID. Within that container, its relative
     distinguished name will be New RDN. The client also identifies the server
     holding the master replica of the existing entry, by sending the Source
     Server's DN.

                  TABLE 2
    ______________________________________
    Finish Move Entry (43(0x2B))
    Offset     Content           Type
    ______________________________________
    Request Format
    32         Version = 0       Int4
    36         Flags             Int4
    40         Source Entry ID   Int4
    44         Destination Parent Entry ID
                                 Int4
    48         New RDN           Ustring
    . . .      Align4
    . . .      Destination Server's DN
                                 Ustring
    Reply Format
    16         Completion Code   Int4
    ______________________________________
     Flags
     0x00000001 Remove Old Name Values
     Completion Codes Success = 0
     Remarks
     This request is addressed to the server holding the master replica of the
     object being moved. The Source Entry ID identifies the object on that
     server. The client identifies the server holding the master replica of th
     destination container by sending the Destination Server's DN. The
     Destination Parent Entry ID identifies the parent container itself The ne
     parent of the NDS object is identified by Destination Parent Entry ID.
     Within that container, its relative  # distinguished name will be New RDN
     If the Remove Old Name Values flag is set, old values of the naming
     attribute remain as multiple values of the attribute (but not as part of
     the RDN). This choice is unavailable if the naming attribute is
     singlevalued. If the flag is zero, all prior values of the naming
     attribute are deleted before New RDN is added.

                  TABLE 3
    ______________________________________
    Restore Entry (46 (0x2E))
    Offset    Content            Type
    ______________________________________
    Request Format
    32        Version = 0        Int4
    36        Request Flags      Int4
    40        Iteration Handle   Int4
    44        Parent Entry ID    Int4
    48        Relative Distinguished Name
                                 Int4
    . . .     Align4
    . . .     Source Distinguished Name|
                                 Ustring
    . . .     Align
    . . .     Data Size = N      Int4
    . . .     Entry Data         Byte ›N!
    Reply Format . . . Moving = 0
    16        Completion Code    Int4
    20        Iteration Handle   Int4
    Reply Format . . . Moving = 1 and More = 1
    16        Complete Code      Int4
    20        Iteration Handle   Int4
    24        Reserved Field = 0 Int4
    Reply Format . . . Moving = 1 and More = 0
    16        Completion Code    Int4
    20        Reply Flags = 0x00000400
                                 Int4
    24        New Distinguished Name
                                 Ustring
    . . .     Align4
    . . .     New Tuned Name     Tuned Name
    ______________________________________
     *Request Flags  0x00000001 More, 0x00000002 Moving
     *Reply Flags  0x00000400 Reply includes the New Tuned Name
     *Completion Codes Success = 0
     |Note: The Source Distinguished Name field is present if and only if the
     Moving request flag is set to one.
     Remarks
     This operation serves two purposes.
     (a) Restoring an entry previously backed up to an external medium.
     (b) Conveying an entry's information to its new location when moving an
     NDS leaf entry. The Moving flag indicates which case it is; zero for (b);
     one for (b). In case (b), collision with an existing name is considered a
     error.
     The Parent Entry ID indicates the immediate parent of the entry being
     restored.
     The Relative Distinguished Name identifies the entry itself.
     The Source Distinguished Name identifies the entry's former name, in case
     of a move operation.
     The Iteration Handle is used differently here from elsewhere. In other
     situations, the amount of data returned from the server is (potentially)
     larger than a single NDS message can accommodate. Here, the opposite
     holds. The request can be larger than the largest NDS message. When the
     More bit of the Request Flags field is set to one, the Restore Entry
     request is incomplete, and is to be continued in another Restore Entry
     request. If the bit is reset to zero, the client is indicating the  #
     completion of a series of Restore Entry requests. Only on completion does
     the server process the request. On the first NDS request of the series,
     the client sets the Iteration Handle to 0xFFFFFFFF; on subsequent
     requests, to the value returned by the server in the preceding reply. The
     reply format depends on the Request Flags, as indicated above. When movin
     an entry, the last reply conveys information about the entry in its new
     location; its new distinguished name (in  # typed form), and its new Tune
     Name.

                  TABLE 4
    ______________________________________
    Synch External Reference
    Offset    Content            Type
    ______________________________________
    Request Format
    32        Version = 0        Int4
    36        Flags = 0 or Purge obituary
                                 Int4
    40        Remote ID (hint)   Int4
    44        Entry Name         Ustring
    . . .     Align4
    . . .     Parent             Tuned Name
    . . .     Align4
    ______________________________________
    Obituary Information
    ______________________________________
    1)                  Restored
    2)                  Dead
    3)                  Moved
    4)                  New RDN
    Common Parameters
    Type           Int2
    Flags          Int2
    Unused         Int4
    Creation Time  Time Stamp
    Data Parameters
    Restored       Creation Time
                   Restored CTS
    Dead           NULL
    Moved          Moved Destination Name - Tuned
    New RND        RDN - Name
    ______________________________________

                  TABLE 5
    ______________________________________
    Control . . . Get Entry Move State
    Offset     Content           Type
    ______________________________________
    Request Details
    40         Verb = 2          Int4
    44         Entry ID          Int4
    Reply Details
    20         Parent Entry ID   Int4
    ______________________________________
     This operation reports if an entry is being moved or not. The entry is
     indicated by Entry ID. If the entry is being moved, the completion code
     "Move in Progress" is returned, and the Parent Entry ID reports the new
     parent of the object.

                  TABLE 6
    ______________________________________
    Start Move Tree
    Offset   Content        Type
    ______________________________________
    Request Details
    40       Version = 0    Int4
    44       Flags          Int4
    48       Revision       Int4
    52       Destination ID Int4 (on destination server)
    . . .    Source Name    Tuned Name
    . . .    Align4
    . . .    New RND        Ustring
    Reply Details
    20       Version        Int4
    24       Flags          Int4
    28       Source ID      Int4 (on destination server)
    32       Destination Root ID
                            Int4 (on destination server)
    ______________________________________


              TABLE 6
    ______________________________________
    Start Move Tree
    ______________________________________
    Flags -          Mt.sub.-- Created.sub.-- ExtRef
                     Mt-Partition.sub.-- Overlap
    ______________________________________

    ______________________________________
    Type Distinguished Name
    ______________________________________
    0    Identifies G (new parent object).
    1    Identifies B (old parent object).
    2    Empty string in the Partition overlap case; otherwise, identifies A
         (root object of partition immediately above C).
    ______________________________________

                  TABLE 7
    ______________________________________
    Move Tree
    Offset     Content           Type
    ______________________________________
    Request Details
    40         Version = 0       Int4
    44         Flags             Int4
    48         Parent Name       Tuned Name
    . . .      Align4
    . . .      Name              Ustring
    . . .      Align4
    . . .      Creation Time     Time Stamp
    . . .      Destination Parent
                                 Tuned Name
    . . .      Align4
               Name Flags        Int4
               New Name          Int4
    . . .      Align4
    . . .      Replica Pointer for Master
    Reply Details
    20         Version           Int4
    24         Flags             Int4
    28         Replica Root ID   Int4
    ______________________________________

    ______________________________________
    Case   1       2     3     4   5    6   7    8   9
    ______________________________________
    Partition C
           R       R     R     E   E    E   N    N   N
    Partition F
           R       E     N     R   E    N   R    E   N
    ______________________________________
    In Cases 1, 2, 3 and 5:
                 W locally switches its record of C's parent
                 from B to G.
    In Cases 4 and 7:
                 W locally creates a subordinate reference
                 for partition C. Its reply has the Created
                 Subordinate Reference flag set, informing
                 T to add the subordinate reference to C's
                 replica list.
    In Case 6:   W locally creates an external reference for
                 G. Its reply has the Created External
                 Reference flag set, informing T to create a
                 back link to W.
    In Cases 8 and 9:
                 These do not occur. Such servers would
                 not be on the Notification List.
    ______________________________________

                                      TABLE 8
    __________________________________________________________________________
    Transmitter (S1)
             Receiver (S2)
                       Comments
    __________________________________________________________________________
    Has seen new name
             Has seen new name
                       A local MapNameToID (LookForTunedRDN
                       or FineTuneRDN) can locate the object on
                       the receiver. This is the simplest scenario.
    Has seen new name
             Has NOT seen new
                       The transmitter sends New Name to the
             name      receiver. In this case C.Y.D.A. Since the
                       receiver has not seen the new name it creates
                       it as a reference object. When the MOVED
                       obituary is skulked to the receiver the old
                       object will be collapsed with this reference as
                       a part of the move.
    Has NOT seen New
             Has seen New Name
                       A local MapNameToID (LookForTunedRDN
    Name               or FineTuneRDN) can locate the object using
                       the forward reference placed at the old object
                       location. This case is similar to the first case
                       listed above. In both of these cases a
                       reference for the object is not created but the
                       actual object is found.
    __________________________________________________________________________

                  TABLE 9
    ______________________________________
    variations of name states
    D.C.B.A -> D.F.E.A
                    B.A -> B.H.A Name States
    ______________________________________
    No              No           D.C.B.A
    Yes             No           D.C.B.A
                                 D.F.E.A
    No              Yes          D.C.B.A
                                 D.C.B.H.A
    Yes             Yes          D.C.B.A
                                 D.F.E.A
                                 D.C.B.H.A
    ______________________________________

                  TABLE 10
    ______________________________________
    Name known as
               State of Moves on receiver
    ______________________________________
    D.C.B.A    None of the moves have occurred on the receiver
    D.F.E.A    D.C.B.A -> D.F.E.A
    D.C.B.H.A  B.A -> B.H.A
    D.F.E.A    D.C.B.A -> D.F.E.A
               B.A -> B.H.A
    ______________________________________

    ______________________________________
    BuildNameList(namelist, partialName)
    // Get the root most component of the partial name.
    entry = GetRootMostComponent(partialName);
    while (entry |= root)
    {
    fromEntry = GetMovingFromComponent(entry);
    if (fromEntry |= null)
    {
    partialName = RemoveComponent(partialName);
    partialName = AddComponent(partialName, fromEntry);
    BuildNameList(nameList, partialName);
    partialName = RemoveComponent(partialName);
    partialName = AddComponent(partialName, entry);
    }
    entry = GetParentOfEntry(entry);
    partialName = AddComponent(partialName, entry);
    }
    AddNameToList(nameList, partialName);
    }
    ______________________________________

    ______________________________________
            typedef struct PARTCNTL
            {
              uint32
                    type;
              uint32
                    function;
              uint32
                    state;
              uint32
                    partnerPartID;
            } PARTCNTL;
    ______________________________________


                                  TABLE 11
    __________________________________________________________________________
    Field  Length
               Values          Description
    __________________________________________________________________________
    type   4 Bytes
               a) Sequence Number (2 bytes)
                               The first two bytes contain the
               b) type (2 bytes) One of: PCT.sub.-- 0,
                               sequence number of the
               PCT.sub.-- 1, PCT.sub.-- 2, PCT.sub.-- 3, PCT.sub.-- 4
                               operation. For a multi-step
                               operation the operations will be
                               performed in sequence with the
                               numerically lowest one being
                               performed first. The second two
                               bytes contain operation specific
                               data.
    function
           4 Bytes
               One of following (4 bytes):
                               Specifies the partition
               PC.sub.-- IDLE, PC.sub.-- SPLITTING,
                               operation. Currently only the
               PC.sub.-- SPLITTING.sub.-- CHILD,
                               PC.sub.-- MOVE.sub.-- SUBTREE.sub.-- SRC is
               PC.sub.-- JOINING.sub.-- UP,
                               defined to be a multi step
               PC.sub.-- JOINING.sub.-- DOWN,
                               operation. It may involve the
               PC.sub.-- MOVE.sub.-- SUBTREE.sub.-- SRC,
                               following steps:
               PC.sub.-- MOVE.sub.-- SUBTREE.sub.-- DEST,
                               1. PC.sub.-- SPLITTING
               PC.sub.-- LOCKED,
                               2. PC.sub.-- MOVE.sub.-- SUBTREE.sub.-- SRC
               PC.sub.-- REPAIRING.sub.-- TIMESTAMPS,
                               3. PC.sub.-- JOINING.sub.-- UP
               PC.sub.-- CHANGING.sub.-- REPLICATYPE,
               etc.
    state  4 Bytes
               Operation Specific
                               Data is specific to the operation
    partnerPartID
           4 Bytes
               Operation Specific
                               Data is specific to the operation
    __________________________________________________________________________

                  TABLE 12
    ______________________________________
    Field        Type      Description
    ______________________________________
    Version      uint32    0.
    Flags        uint32    0.
    New Partition Root Entry
                 ID uint32 The new partition root entry is
                           Entry ID.
    ______________________________________

                  TABLE 13
    ______________________________________
    Field         Type      Description
    ______________________________________
    Version       uint32    2. DNs are Ustrings.
                            3. DNs are Tuned Names.
    Flags         uint32    0.
    Iteration Handle
                  uint32
    Parent Distinguished Name
                  Tuned Name
                            The Distinguished Name of
                            the parent partition of the
                            partition being split.
    Align4
    Child Distinguished Name
                  Tuned Name
                            The entry that will be the
                            partition root for the
                            new partition.
    ______________________________________

                                      TABLE 14
    __________________________________________________________________________
    Field  Length
               Values         Description
    __________________________________________________________________________
    type   4 Bytes
               a) Sequence Number (2)
                              The sequence number
               b) type (2) PCT.sub.-- 3
                              would be the number
                              corresponding to the Move
                              operation PCT.sub.-- 0 Partition
                              Control value.
    function
           4 Bytes
               PC.sub.-- MOVE.sub.-- SUBTREE.sub.-- SRC,
                              Specifies Move operation
    state  4 Bytes
               N.A.           N.A.
    partnerPartID
           4 Bytes
               class ID       Specifies the new base class
                              of the moved object
    __________________________________________________________________________

                  TABLE 15
    ______________________________________
    Field        Type    Description
    ______________________________________
    Version      uint32  0.
    Flags        uint32  0.
    Partition Root Entry ID
                 uint32  The Entry ID of the child partition's
                         root entry.
    ______________________________________

                  TABLE 16
    ______________________________________
    Field     Type      Description
    ______________________________________
    Version   uint32    2. DNs are returned as Ustrings.
                        3. DNs are returned as Tuned Names.
    Flags     uint32    0.
    Iteration Handle
              uint32
    Parent DN Tuned Name
                        The DN of the parent partition.
    Align4
    Child DN  Tuned Name
                        The DN of the child partition's root
                        entry.
    ______________________________________

                  TABLE 17
    ______________________________________
    Field     Type      Description
    ______________________________________
    Version   uint32    2. DNs are Ustrings.
                        3. DNs are Tuned Names.
    Flags     uint32    0.
    Iteration Handle
              uint32
    Parent DN Tuned Name
                        The Distinguished Name of the
                        parent partition.
    Align4
    Child DN  Tuned Name
                        The Distinguished Name of the
                        child partition's root entry.
    ______________________________________

• Inventors
  Prasad, Ranjan; Olds, Dale Robert;
• Assignee
  Novell, Inc. (Orem, UT)
• Published
  Sep-21-1999
• Current US Classes:
  707/10
  707/2
  707/201
  707/3
  709/203
  710/200
  713/201
• Application #
  810851
• International Classes
  G06F 017/30
• Field of Search
  707/2 707/3 707/10 707/103 707/201 395/187.01 395/200.33 395/726
• Examiner
  Black; Thomas G.
• Agent
  Dinsmore & Shohl LLP
• US Patent References:
  5001628
  5032979
  5113519
  5367698
  5369778
  5418966
  5634124