NDS Tree Walking Issues and Recommendations
Articles and Tips: article
Novell Consultant, MCNE, MCNI
Novell Consulting, Ohio
stanselle@novell.com
01 Oct 2000
The purpose of this AppNote is to discuss how various Novell products make use of "tree walking" in Novell Directory Services (NDS). It will also discuss what can be done from within each of these products to reduce the amount of unnecssary tree walking that occurs. This material is based on various white papers, Novell Technical Documents, and other information gathered on the subject. It is assumed that the reader is familiar with basic NDS concepts and terminology.
What Is Tree Walking?
Tree walking is a normal function of NDS. When a client agent submits a request to NDS, the request is not always received by a name server that is qualified to fulfill the request. It is therefore the responsibility of the name server receiving the request to 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 this information, another name server initiates a search of the NDS tree until a replica is found that contains the desired information. This process is called tree walking.
All NDS tree searches contain one or more names that identify 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 such a partition is found, the search moves from that partition to another partition that contains the next name component, until the partition that actually contains the desired item is reached. The search proceeds towards the [Root] of the NDS tree.
Any name resolution 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 parts of the NDS tree. A 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.
Tree Walking Example
Figure 1 shows an example of an NDS tree. It shows only the tree structure without partition designations, and does not give any indication as to which servers the partitions and replicas are stored on.
This tree has three partitions. Wimplemakers, Kalamazoo, and Tucumcari are the objects selected as the partition roots. NS1, NS2, and NS3, respectively, are the servers chosen to store the partitions.
Figure 1: Sample NDS tree structure.
To illustrate how tree walking works, suppose a client (user U2) with a connection to name server NS2 makes a request to update the Marketing object. The request specifies the name "Marketing.Tucumcari.Wimplemakers" for the object.
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 NS1 is closer to the [Root] because of its superior reference. Since NS1 knows about Wimplemakers, this short walk up the tree is the only upward walk that must occur for this particular request.
NS1 also knows about Tucumcari, which is part of the Marketing object's distinguished name, because of the subordinate reference its partition holds. After locating Tucumcari, NDS begins the walk down the tree toward the desired object. NS3 completes the tree walk when it successfully identifies Marketing as part of its partition.
This entire tree-walking scenario is illustrated in Figure 2. In this example, each of the partitions is a Master replica which can be written to. NS3 is thus able to fulfill any request that is allowed by the NDS security access control lists.
Figure 2: An example of how NDS walks the tree to resolve the object name specified in a request.
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. This is accomplished through the use of NDS referrals.
Referrals
During the tree-walking process, when a server receives a request and discovers information about how to get closer to the desired partition and server, this information is sent back to the server that sent the request. This "progress report" is called a referral.
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 (Service Advertising Protocol) information.
Class Definition Cache. This cache holds the expanded class definition of each NDS class.
We'll learn more about referrals later in this AppNote.
When Is Tree Walking Bad?
As mentioned previously, tree walking is a normal part of NDS operations. It is the means by which NDS locates objects that reside in a partition on a different server. However, one of the principles of good NDS design is to place replicas close to the users who will be accessing the objects within the replica. A server without a replica cannot service NDS authentication requests, or handle just about any other NDS-related process. If users connect to servers without replicas, tree walking will be involved, which slows things down. Performance can be affected even more when requests from workstations or servers must travel across slow WAN links in order to resolve object names.
To find out how much of a difference replica placement makes in your particular network environment, you could do timing tests with and without replicas that contain the User, Printer, and ZENworks for Desktops objects that the users of the server will need to access.
Another thing to keep in mind is that NDS uses the dynamic Access Control List (ACL) inheritance model, which economizes on replication traffic. However, the downside to dynamic inheritance is that it can cause tree walking when ACL information needs to be referenced. Even so, Novell believes this method to be optimal over static inheritance. With proper tree design, the impact of tree walking may be alleviated.
Product-Specific Tree Walking Issues
The previous discussion has outlined the main uses of tree walking in NDS-enabled versions of NetWare (4.x and above). This section covers tree walking issues and concerns in the following Novell products:
ZENworks for Desktops 2.x
Novell Licensing Services (NLS)
Novell Client 32
BorderManager 3.5
GroupWise 5.5 with the Enhancement Pack
NDS (removing the [Public] trustee)
This is not intended to be a comprehensive list of products in which tree walking issues may be of concern. While you may not have all of the products listed above, this discussion should give you a good general understanding of the tree walking issues that may arise in other products.
ZENworks for Desktops 2.x
Three main features of ZENworks for Desktops are the Novell Application Launcher (NAL), the Workstation Manager, and the Remote Control function. We will discuss the use of tree walking by each of these separately.
Tree Walking by NAL. NAL can be configured so that users or workstations can inherit applications from a number of container levels. This is a great feature when you need to assign a single application to multiple users throughout the NDS tree. However, when incorrectly used, this feature can degrade performance, especially if NAL has to tree walk across WAN links to locate an Application object located in a replica on a faraway server.
There are three mechanisms to control the tree walking behavior of NAL:
Set a suitable container as the "top" of the inheritance tree to ensure that NAL will not tree walk past this point. The container may be the user's immediate container or the container that represents the partition root object, thus preventing the need to connect to the parent partition to resolve an association. This is set in NWAdmin via the Launcher Configuration page for a user, workstation, or container.
Set NAL to inherit from only the number of levels that exist between the User object and the top of the inheritance tree. You can change this in NWAdmin through the "Set Application Inheritance Level" setting on the Launcher Configuration page for a user or workstation.
Set NAL to ignore group association if groups are not used to associate users with applications. This is done via the "Read Groups For Applications" setting on the Launcher Configuration page for a user or workstation.
Tree Walking by Workstation Manager. A new feature of ZENworks for Desktops 2.x is the Policy Package object allowing user-, workstation-, and container-based policies to be applied to the desktop. Like global group membership and NAL object association, policy searches can hurt performance if inappropriately configured.
A search policy can be effectively used to ensure that policy searches do not proceed past some logical point. By default, the search behavior of Workstation Manager includes going all the way to the [Root], unless a container policy package is encountered that includes a search policy. When a user authenticates to an NDS tree with Workstation Manager enabled, the following things happen:
The User object is searched for an associated policy package.
Groups that the user is a member of are searched for any associated policy packages.
The client walks the tree, checking each parent container for group associations until it reaches [Root].
While the tree walking is taking place, only policy packages that are associated to that user, or to a group which that users is associated with, will be applied. If the user is associated with two policy packages, the first policy setting found will be used.
This has the potential of creating some problems. For example, if [Root] or any other parent container is located across a WAN link, traffic across that link will be necessary for the user to authenticate. This could cause slow authentication, or errors if the connection is down.
To avoid the tree walking, use a Container Search Policy. This policy has one setting with two configurable tabs: Search Level and Search Order. These are accessible in NWAdmin by right-clicking a container, selecting Details, viewing the Associated Policy Packages, selecting the Container Package and clicking on Details, and then selecting Search Policy and clicking on Details (see Figure 3).
Figure 3: The Search Policy configuration window in NWAdmin, showing the Search Level page.
Search Level
This setting allows you to set a rule (or a policy) about how many levels the system will search in the tree for an associated policy package. There are several selections to choose from.
Search For Policies Up To. The default is [Root]. You can specify any other container below the root using the following choices:
Object Container = Search to the parent of the User or Workstation object
Partition = Search to the Partition Root
Selected Container = Search to the selected container
[Root] = Search to the Root of the tree
Selected Container. If you chose "Selected Container" in the Search For Policies Up To field, you can browse and select a starting point for the search.
Search Level. The default is 0, which means the program will search for policies up to whatever level you specify in the Search For Policies Up To field. You can choose to limit the search here, either up or down the tree. For example:
0 = Limits search to the current level (as set in the Search For Policies Up To field)
1 = Limits search to one level above the current level (as set in the Search For Policies Up To field)
-1 = Limits search up to, but not including, the current level (as set in the Search For Policies Up To field)
Search Order
From the Search Order page (see Figure 4), you can set rules (or a policy) on how the system will search in the tree for associated policy packages. The default search order is Object, Group, Container, where:
Object = User or Workstation
Group = Group or Workstation Group
Container = Container of a User or Workstation object
The arrows below the list are used to move the selected item up or down the list, which will change the search order. You can also add or remove items in the list.
Figure 4: The Search Order window in NWAdmin.
Depending on how you set the search order, you can configure the program in several ways, including:
Don't search past the user's container.
Don't search past a selected container.
Don't search past the end of the partition (wherever that is).
The last option is a useful catch-all if no firm strategy of policy location is in place. It prevents the search going up to the parent partition, which might possibly reside on a remote server.
Remember that once you set a search policy, any policy associated outside that search domain will not be effective. Check the Effective Policies tab in NWAdmin for a user to confirm the desired policy outcome.
You can check the settings of the Search Policy in the Novell Client by going to the Registry entry HKEY_LOCAL_MACHINE | Software | Novell | Workstation Manager | Search Policy. The String Value "Workstation Context Ceiling" should show the distinguished path to the context set in the Search Policy. If not, change it to minimize the amount of tree walking that must take place.
Tree Walking by the Remote Control Feature. The Remote Control agent must contact the Master replica in order to properly control (and lock access) to the workstation. As a result, when you start a remote control session with a workstation, some tree walking may occur to find the workstation and the Master Replica.
Novell Licensing Services
Here are some tips for reducing tree walking when dealing with licensing.
If you license a server and then immediately try to log in, you might get messages stating that the server is not properly licensed. This happens because the licensing object's attributes are especially large and take a while to synchronize. Wait a few minutes and try again.
To reduce tree walking at Novell, we have installed an MLA license in every container that contains (or might contain in the future) Server objects. That reduces the amount of tree walking required to find a valid license since the license object is always right there in the same container as the server.
If a container has both NetWare 4.11 servers and NetWare 5 servers, and the NetWare 5 servers hold no replicas, load NLS on a NetWare 4.11 server that holds a replica in that partition.
With MLA/CLA node licensing in NetWare 5, you can place one node- based license in the tree and have all of the servers use that one license. However, this might require the servers to walk the tree to find the license container. This will only occur until an external reference is built, as the server will use this reference for future requests to the license file.
NLS Search Type Parameter. There is a SET parameter that deals with licensing: Set NLS Search Type = n. The valid settings for this parameter are 0 (the default), which stops upward searches for a license certificate at the tree root, and 1, which stops upward searches at the partition root.
Licensing Issues. Here are a few additional issues to be aware of regarding licensing.
All recent versions of Novell Client 32 have NLS functionality built-in. The Client will search for a license certificate until it hits the root of an NDS replica partition. If you have several partitions in your NDS tree, the Client may have to tree walk to locate a Local Certificates object if it doesn't find one within the current partition. Client searches always go up the tree, not down. To avoid search traffic over slow links, place at least one NLS license certificate in the local partition if possible. Also, place the certificate object just below the top Organization (O) or Organizational Unit (OU) object.
NLSLSP.NLM is a service provider, which acts like a mediator to intercept client license requests to NDS. It requires at least one copy of the NDS partition database installed on the same server where NLSLSP.NLM is running.
To avoid extra NDS traffic between sites, at least one NetWare server should have NLSLSP.NLM running to intercept any license request for the local clients. You may not gain any benefit from installing NLSLSP.NLM on all of the NetWare servers in the tree.
Never assign an MLA certificate to either a User or a Server object using the Details option on the certificate object in NWAdmin. This will turn the unlimited connection license into a limited license.
Novell Client 32
Improper configuration of the Novell Client 32 software can cause unnecessary tree walking. To more clearly explore this issue, an explanation of the login process is in order.
When a workstation is turned on and an attempt is made to log in to a Novell server, the following sequence of events occurs:
If a preferred server (the server that is specified to handle the initial contact with NDS) is not specified, a connection is made to whatever server first responds to the Client's Get Nearest Directory Server request.
If a Preferred Server is configured, the Client will send out a request trying to locate that server. When the server is found, the Client creates a connection which is maintained at least until the login program is run.
Once this initial connection is made, the Client runs the login executable.
After receiving a credential set (user name, context, and password) from the Client, the server attempts to authenticate the user. In this sense, authentication means verifying that the User object exists in the specified context and that the supplied password is correct.
If the authentication is successful, the Client creates an unlicensed, authenticated connection to the server, and then attempts to read the "Default Server" field from the User object.
If this field is populated, the Client issues a Destroy Service Connection request to the server it is currently attached to, and then issues a Create Service Connection request to the Default Server (even if it is the same server).
If the "Default Server" field in the User object is blank, the Client uses the current server connection (if possible) to complete the login process for the user.
After the default/current server connection has been made, the login process is completed for the user and the connection to the server is changed from an unlicensed to a licensed connection.
If the default/current server does not hold a replica of the User object, this server will walk the tree or use server-to-server communication to obtain the necessary user information.
Contextless Login. Contextless Login is another feature that requires tree walking. If you are not currently using this feature, you should check your Client settings to verify that it is disabled. To do this, click on the Network icon in the Windows Control Panel, and examine the properties of the Novell NetWare Client. If the Enable box is checked under the Contextless Login tab, tree walking will occur even if you are not currently using this feature. As long as this is enabled, the Client will walk the tree looking for an NDS catalog object. This tree walking does not stop at [Root]; it continues looking all the way through the tree. The way to stop this is to disable Contextless Login if you are not using it.
BorderManager 3.5
When a user authenticates to BorderManager, the server must find the User object. Hence, tree walking could take place.
Another function where tree walking will occur is when you set up the access rules. If you list a group in a rule, ACLCHECK must read the membership list of the group. It then rechecks the members every time ACLCHECK refreshes. It should use an external reference to find the group, once one has been created on the BorderManager server.
When BorderManager reads the rules, it looks first at the rule list assigned at the server. Next it looks at the rule lists for its parent container, and so on through each container up to the Organization. If these containers are in different partitions (and replica rings), BorderManager will have to tree walk to find the appropriate replica. To reduce this tree walking, place a blanket rule (such as Deny All To Everyone) at the server or immediate parent container. BorderManager will stop reading rules on the first successful rule hit.
Note: Although BorderManager stops at the first hit, remember that if you click on the Effective Policies button in NWAdmin, it will look all the way up the tree because it is looking for any rule that could be applied.
GroupWise 5.5 Enhancement Pack
During normal GroupWise operations (users reading e-mail and such), there is no access from the client (or the server) to NDS. The only possibility for GroupWise to be reading NDS (and therefore potentially walking the tree) is if the Message Transfer Agent (MTA) has been set up to do NDS synchronization. This is turned off by default, but it can be enabled by the administrator. If one MTA is doing all the synchronization between NDS and GroupWise, this agent could be walking the tree because it needs to access a part of the tree that it doesn't have on the server where it is running.
This synchronization is optional. If a customer is doing all NDS user administration in the NetWare Administrator with the GroupWise snap-ins loaded, synchronization is done at that point and it is not necessary for the MTA to do NDS synchronization.
The [Public] Trustee
By default, [Public] is given Browse object rights at the root of every NDS tree. This gives all objects (including users) the ability to walk the tree in search of additional resources. There is no rule that requires you to maintain the [Public] trustee assignment at the Root of your tree. However, removing it may have the following implications:
User objects may have problems reading login scripts.
Users may not be able to find Application objects associated to them as the Novell Application Launcher searches up the tree for those applications.
Users may not be able to find Policy Packages associated to them as ZENworks for Desktop searches up the tree for those policies.
Users may not be able to set up printers through NDS. Only bindery-based queues will be visible.
Users will not be able to browse for their context upon login.
Any other operation that requires searching for objects may also fail.
How to Trace Tree Walking
To determine the reason for tree walking, a packet trace may be of assistance. To acquire the trace, you will need a tool such as LANalzyer for Windows, Sniffer Pro, or some other protocol analysis tool.
The workstation running the network capture (packet trace) must be on the same collision domain as the workstation you are using to demonstrate the tree walking. In some instances they may be the same workstation, but not when testing initial workstation login since the desktop is unavailable before login time on Win32 systems. Symptoms of a connection being made to a server across the WAN may include poor performance on NDS queries as well as unwanted server connections in the NetWare Connections window. (To check these, right-click on the red "N" in the workstation's system tray and then select NetWare Connections.)
Identifying an NDS Referral
When a referral occurs, the network trace shows the workstation performing a "Resolve Name" sequence for a particular NDS object. This sequence is identifiable in the packet data. For example, when a remote connection is being established due to the NAL configuration or ZENworks Policy searches, the clue that this is happening is that there is a "Resolve Name" request for the object at the [Root] of the tree. The server responds to this request with a list of sever addresses instead of an EntryID. You can see at a glance if this is happening by examining the packet trace data for recurring sequences of bytes which correspond to the port numbers NetWare uses for NetWare Core Protocol (NCP) communication.
In examining traces, keep in mind that an IPX (type "C") network address consists of four bytes denoting the IPX network number (which is unique for every server at a site), followed by "00 00 00 00 00 01" for the node number on that network, followed by "04 51" for the port number. A TCP/IP (type "6") network address consists of "02 0C" as the port number, followed by a four-byte TCP/IP host number. (IPv6 addresses will differ from this.)
As an example, here is a reproduction of the data segment from a referral packet.
06 00 00 00 00 00 00 00 9c 00 00 01 04 00 00 00 01 00 00 00 00 00 00 00 0c 00 00 00 11
11 11 12 00 00 00 00 00 01 04 51 01 00 00 00 00 00 00 00 0C 00 00 00 22 22 22 23 00 00
00 00 00 01 04 51 01 00 00 00 00 00 00 00 0c 00 00 00 33 33 33 34 00 00 00 00 00 01 04
51 01 00 00 00 00 00 00 00 0C 00 00 00 44 44 44 45 00 00 00 00 00 01 04 51
Note the byte sequence "00 00 00 00 00 01 04 51" which appears several times in the data. This sequence includes the node number "00 00 00 00 00 01" denoting a server on an internal network segment, and port number "04 51" which is the IPX port for server NCP communication. Preceding this byte sequence are four IPX internal network numbers being returned as an NDS referral:
11111112
22222223
33333334
44444445
Analyzing a Network Trace
Here is a simple technique you can use when examining a network trace to quickly identify what is going on.
Use the network trace to identify the servers that the workstation has authenticated to. As shown above, the addresses identified in the network trace can assist in identifying particular servers.
Also look for Get File Server Info packets. The server name appears as an explicit text string in the subsequent packet.
Try to discover why the workstation has authenticated to the servers you have an interest in. Remember that a "Resolve Name" request can be responded to with a referral list (as explained above) or an EntryID. The EntryID is a four-byte hex value that will be used as shorthand for the object in other workstation requests further on in the network trace.
The first DS request after the workstation authenticates to the server typically gives a clue as to why that server was contacted in the first place. Look for the "Finish Authentication" packet from the server, then look at the data in the subsequent packet originating from the workstation (it should be an "Open Stream" or "Read" packet). Look at the EntryID to determine what object is being referenced. If the EntryID doesn't match an object already identified in a "Resolve Name" request/response pair you have already seen, look back through all other pairs of packets to identify the Common Name of the object that the EntryID belongs to. Alternatively, you can use DSVIEW on the server to look for an object in the database which has the required EntryID. The attribute being accessed will suggest the process that has caused the access.
Troubleshooting Example
As an example, suppose workstation Melbourne has a server named SYDNEY in its NetWare connection list. This connection is undesirable, as it is being made across the WAN. You have collected a network trace of the packets being exchanged when the workstation logs in.
You identify the point at which this server is contacted by looking through the "C Get File Server Infor"/"R OK" pairs until you find the server name "SYDNEY". (Alternatively, you could identify the server by its address, if that is known.)
Moving backwards through the trace through the "Resolve Name" requests, you see an "NDS: C Verb=0x01 (Resolve Name)"?"NDS: R OK. Verb=0x01 (Resolve Name)" pair immediately preceding the RIPS and NCP traffic found in Step 1. The data in the "NDS: C Verb=0x01 (Resolve Name)" request shows the object being referenced is the top-level O=Company object. The response packet shows referrals and an EntryID of 0100009C.
You next examine the first request after the authentication following the traffic identified in Step 1:
SYDNEY => MELBOURNE: NDS: R OK, Verb=0x3C (Finish Authen)MELBOURNE => SYDNEY: NDS: C Verb=0x1B (Open Stream)SYDNEY => MELBOURNE: R Err (No such value), Verb=0x1B (Open Stream)
The second packet in this series contains the attribute name that is being requested, as well as the EntryID of the object found in Step 2. The attribute is "App: Launcher Config".
From this data analysis, you have discovered that the workstation is connecting to server SYNDEY because the workstation uses NAL, which is configured to walk the tree to the [Root] for configuration information. The remote server is contacted because the local server does not have a copy of the [Root] replica. The solution in this example is to implement an appropriate "Top of Inheritance Tree" setting for NAL to restrict this tree walking.
Other Troubleshooting Tips
As we have seen, connections to remote servers result in tree walking. If a workstation is attempting to read the properties of an object that is not held on a Master, Read/Write, or Read-Only replica on a server that the workstation is currently directing NDS queries to, the workstation will contact another server to locate the object, based on the referral information that the original server was able to provide.
Once a workstation has directed NDS queries to a server, it will continue to direct subsequent queries at the same server until encounters a referral to a different server. Problems can occur when a workstation has tree-walked across the WAN to [Root] due to a misconfigured NAL setting or a poorly configured ZENworks policy implementation. Once the workstation has connected to a remote [Root] server, it will keep communicating with that server for NDS information until that server is unable to satisfy a request. For sites which have placed all replicas on a master DS server, workstations at remote sites which tree-walk to [Root] may converge on this server, creating performance problems on this server and slow login times for the workstations.
Following are some final suggestions for troubleshooting tree-walking issues.
Problems with network configuration or service advertising can have a negative impact at login time when the workstation initially attaches to a server for the purpose of issuing NDS requests for information about objects in the tree. The server might appear to be local to the workstation, but it may not be.
To Do: Check to see whether the workstation is receiving correct information about the network topology from network devices such as routers. Using a network trace, identify the responses to the "Find Nearest File Server" request. Confirm that the MAC addresses in any response packets correspond to servers on the same segment. Or, if there is a router responding on behalf of a remote server, confirm that this is the behavior you expect based on your network configuration.
After the initial connection, the workstation is typically configured to establish a Preferred Server connection.
To Do: Check to see if the Preferred Server setting is to a server across the WAN.
The Preferred Server will be used by the workstation whenever it needs information from NDS. If that server is unable to satisfy a request made by the workstation, it provides the workstation with a list of network addresses (referrals) for other servers that do hold the required information. The workstation will then connect to a server from the list and will re-issue the request.
To Do: Check that replicas required for local use are placed on the sites where they will be used. Verify that all replica rings in the tree are consistent by ensuring that each ring has a Master replica and no servers are receiving -672 errors. You can use the NDS Manager "Partition Continuity" tool to gather this information.
Conclusion
I hope that this AppNote has given you a better understanding of NDS tree walking issues and concerns. Keep in mind that NDS tree walking is a normal function of NDS, as it helps NDS locate objects that reside in a partition on a different server. However, you should minimize the amount of tree walking that must occur over WAN links. When dealing with tree walking issues in NDS and other Novell products, remember that most of these issues take care of themselves if you have implemented a well though-out NDS design.
* Originally published in Novell AppNotes
Disclaimer
The origin of this information may be internal or external to Novell. While Novell makes all reasonable efforts to verify this information, Novell does not make explicit or implied claims to its validity.