NDS Name Resolution and Tree-Walking

     

NDS Name Resolution and Tree-Walking

NDS name resolution is the process of DS navigating through the different partitions in the tree ”using tree-walking ”until it finds the requested object. When DS finds the object, it retrieves the object ID and returns it to the caller. All DS information requests can be broken down into one or more names that identify the objects. In pursuing each name component in a request, DS searches for a partition that contains some part of the name path associated with the request. When a partition is found, the search moves from that partition to the partition that actually contains the object. Until a relevant partition is found, the search proceeds upward toward [Root] ; any request can be pursued successfully by beginning at [Root] and working downward.

Consider the sample tree shown in Figure 6.1. Let's assume that your currently context is at O=East_Coast . In order to locate the User object Dilbert , looking down the current tree branch does not find him. By moving upward to [Root] , you have two additional tree branches ( O=West_Coast and O=Central ) from which to pursue the object.

Figure 6.1. An example of a DS tree structure.

Tree-walking is the process of a NetWare Core Protocol (NCP) client, commonly referred to as the DS agent (DSA), walking through the NDS tree to locate a server hosting the partition that has a particular object. Each DS server (be it a NetWare server or Linux system running eDirectory) has a built-in client agent to facilitate DS name resolution and tree-walking.

NOTE

The name resolution process is initiated by the DS DSAResolveName "verb." ( DS verbs are predefined functions within the DS engine. Refer to Appendix B, "DS Verbs," for a complete list of DS verbs.)

An application may disable the tree-walking component of the name resolution process by setting the DCV_DISALLOW_REFERRALS flag to TRUE and calling the NWDSSetContext API . This is useful if the application wants to search only the database local to the server it is communicating with. When you set the DCV_DISALLOW_REFERRALS flag to TRUE , the DSA returns a failure (-601 error [object not found]) if the object being sought is not located in the local database.

The tree-walking process relies on Subordinate Reference (SubRef) partitions to connect the tree. If a server can provide no other DS information, the least it can offer is a reference to another server higher in the tree that has a partition with information about objects. When walking the tree, a server is given the object name of interest. Based on the name, the server decides whether it needs to move upward toward [Root] or downward away from [Root] in order to access the next partition in its efforts to locate the object.

NOTE

Tree-walking can go up or down a DS tree, depending on the location of the partition that holds the desired object.

NOTE

eDirectory 8.5 introduced a new feature called referral hints to help make tree-walking more efficient. Prior to eDirectory 8.5, NDS may have had to walk through a large portion of the tree, which could span slow WAN links, before locating the server holding a real replica of the desired object. This could consume a lot of time and overhead. With referral hints, the network addresses of servers that "should" have a real copy of the partition are kept on the External Reference (ExRef) partition root object. eDirectory simply walks to the partition root object and uses the referrals listed on that object to contact the servers directly and see whether they have real copies of the partition of interest. If this fails, the old way of walking the tree is then used to try to locate the desired partition.

The act of the workstation locating the server that holds the partition with the desired object constitutes half the name-resolution process. Up to this halfway point, the tree-walking process is solely carried out by the server on behalf of the workstation. The second half of name resolution is complete when the client retrieves the object ID from the server containing the partition. There are three ways in which this second half of the process is accomplished, depending on the DSA's request setting ( NWC_DS_PREFER_ONLY_REFERRALS , NWC_DS_PREFER_REFERRALS , or not set).

If the DSA has the resolve name request flag set to NWC_DS_PREFER_ONLY_REFERRALS (0x00004000) and the requested distinguished name (DN) is not in the local database, the agent returns to the caller a list of referrals of servers that will have real copies of the DN in question. If the DSA has the resolve name request flag set to NWC_DS_PREFER_REFERRALS (0x00002000) instead, the agent returns only one referral (the first entry in the list) instead of the entire list.

NOTE

When the resolve name request flag is set, the behavior of the DSAResolveName process is very similar to the LDAP referral process: The client is given a list of referrals, and it is up to the caller to decide what to do with that information.

When the referral information is returned to the call, it is up to the caller to make a new request to the new servers. If the caller (such as the Novell Client for Windows on a workstation) did not previously have a connection to the referred server, an authenticated-but-not-licensed connection is created in order to retrieve the (server-centric) object ID from the server.

NOTE

One of the steps in the DSAResolveName process in eDirectory 8.5 and higher checks whether the object has a global unique identifier ( GUID ). If a GUID value is not found, one will be created. eDirectory 8.7 requires that every object have a GUID . Therefore, DSAResolveName is a process that ensures that the objects have GUIDs because this routine is used often.

Many processes (such as file system trustee assignments on Novell Storage Service [NSS] version 3 volumes on NetWare 6 servers) are starting to use GUIDs instead of the server-centric IDs of the objects. To maintain backward compatibility with previous versions of NDS , however, the server-centric IDs are still being maintained and used.

If the DSA request flag did not specify referrals, a temporary external reference will be created on the local server (the one the workstation sent the initial request to), and its object ID will be returned to the caller. (If the server no longer needs an ExRef, background processes will have it removed after 192 hours [eight days]. See the section "The Backlink Process," later in this chapter.)

NOTE

If the object ID of the real object is desired, the calling application should set the request flags for one of the two referral options discussed previously.

The name resolution and tree-walking processes are best illustrated by the following login example. In this example, three different partitions in the DS tree are located on three separate servers (see Figure 6.2), and the replica placement is as follows :

Figure 6.2. A tree-walking example with three partitions.

	ACME_Inc Partition	OU_2 Partition	Testing Partition
Server FS1	”	”	Master
Server FS2	”	Master	SubRef
Server FS3	Master	SubRef	”

Suppose the workstation is initially attached to FS1. The user logs in as .peter.ou_1.acme_inc . Server FS1 does not contain information for this User object, nor does it have information about OU_1 or ACME_Inc . Rather than immediately returning an error message (indicating that the object is not found) to the workstation, however, FS1 passes the query up the tree ”using its internal DS client agent ”to FS2. (It knows FS2 is closer to [Root] because of the SubRef pointer.)

If FS2 does not contain information for the object (which it does not in this example), it passes the name of the server containing a parent partition of itself ”in this case, FS3 ”back to FS1. Then FS1 queries FS3 for the desired information; FS1 has "walked" up the DS tree structure, toward [Root] . In this instance, FS3 holds the partition that contains the User object. Therefore, FS1 redirects the workstation ( transparently to the user) to query server FS3 directly; if the workstation did not previously have a connection to FS3, an authenticated-but-not-licensed connection will be created in order to retrieve the information from the server. (The redirection here is a function of the Novell Client, and the behavior is hard-coded and cannot be changed.)

Tree-walking gives a DS client the ability to log in or authenticate without having to attach to the specific server holding the partition (or replica of the partition) that contains the User object. Tree-walking is also used to locate services ”such as servers and print queues ” anywhere within a DS tree. You might have noticed the similarities between DS's tree-walking and LDAP's chaining process. The main difference between the two is the DS's tree-walking does not require the requesting server to authenticate to the target server every time it connects, whereas LDAP's chaining process does.

NOTE

In an NDS /eDirectory environment, after a client is authenticated to a DS tree, that client can locate any ( DS -aware) service within the tree without the use of a SAP packet or an SLP packet. NetWare 2 and NetWare 3 services, such as print servers and database servers, must broadcast the services' availability (over IPX ) on a regular basis (the default is 60 seconds) so clients that can locate these services.

This feature is especially beneficial for networks that have many services. The use of DS to locate services significantly reduces the amount of network broadcast or multicast traffic due to SAP or SLP . This reduction in network traffic is also of importance to companies that have WAN links. It is one of the many reasons NDS /eDirectory works well in large networks where other DS failed to deliver the expected performance.