2.4 Tree Walking

When a client agent submits a request to eDirectory, the request is not always received by a name server that is qualified to fulfill the request. The name server receiving the request must find a name server that can fulfill the request. Several name servers may need to be contacted before a qualified server is located.

To find the information, a name server initiates a search until a replica is found that contains the desired information. This process is called tree walking.

All eDirectory requests can be broken down to one or more names identifying objects for which information is needed. In pursuing each name component in a request, the name server searches for a partition that contains some part of the name path associated with the request. Once a partition is found, the search moves from that partition to the partition that actually contains the item. Until a relevant partition is found, the search proceeds toward the eDirectory directory [root], since any request can be pursued successfully by beginning at the [root].

If a name server can find no other information, it can at least provide a name server that has a partition with information about objects that are closer to the [root] than itself.

The tree walking process relies on subordinate references to connect the tree. The subordinate reference is an entry in a superior partition that points to a subordinate partition. There is a subordinate reference for each partition that is subordinate to a given partition. When walking the tree, a name server is given the name of an object. From there, the name server decides which server to attempt to access next in order to locate the object.

The following illustration shows an example eDirectory tree. It shows the total tree structure with no partition designations, and does not give any indication as to which servers the partitions and/or replicas are stored on.

This tree has three partitions. WimpleMakers, Kalamazoo, and Tucumcari were the objects selected as the partition roots, and NS1, NS2, and NS3, respectively, were chosen to store the partitions.

Suppose a client (user U2) has a connection with the name server NS2 and makes a request to update the Marketing object. It specifies the name Marketing.Tucumcari.Wimplemakers in the request. NS2 has no information about Tucumcari or Marketing, so it must begin a tree walking process. NS2 passes the request up the tree to NS1, because it knows it is closer to the [root] because of its superior reference. This short walk up the tree is the only upward walk that must occur for this particular request, as the following figure shows.

After locating Tucumcari, which is part of Marketing’s distinguished name, eDirectory begins the walk down the tree toward the desired object. NS3 then completes the tree walk when it successfully identifies Marketing as part of its partition. In this arrangement, each of these partitions is a master partition and can be written to, so NS3 is able to fulfill any request allowed by the eDirectory security access control lists.

If other servers were added to this tree, they could be designated as replica holders of any one or all of the partitions. If more replicas existed, server NS1 would have to determine which server to send the request to.

The referral gives the requesting server a new list of name servers to try if the name server cannot satisfy a request.

A referral contains the following fields:

Server List

This field is a list of name servers. The servers initially set this field based on currently connected servers and SAP.

Class Definition Cache

This cache holds the expanded class definition of each eDirectory class.