Chapter 4

Overview of the distributed Directory


The Directory can be viewed from three levels of abstraction. At the First Level we regard the Directory system as a black box (an object, to use object oriented terminology), with a defined interface, called the Directory Abstract Service, to components that act on behalf of users of the Directory. The components that act on behalf of the users are called Directory User Agents, or DUAs for short. What happens inside the Directory black box is of no direct concern to the users, as long as the correct answers are given to their queries. At a more detailed level of abstraction, we can look inside the Directory black box, to see what is happening in there. We see that the Directory system is made up of individual components - called Directory System Agents, or DSAs for short - that co-operate to provide the service that the user has requested. The service that DSAs provide to each other, is called the DSA Abstract Service.

A third even more detailed abstract view looks inside a DSA to see how it functions. Both the internal processes and the data stored by the DSA are modelled. The DSA's data store, which contains part of the global DIT, is modelled as a DSA information tree. Each node in this tree is called a DSA Specific Entry, or DSE for short, as described in § 2.13. A DSA's internal processes, such as name resolution and operation evaluation, are described in terms of their interaction with the DSA's information tree. How this abstract DSA behaves, depends upon the service requested by the user (or by another DSA acting on behalf of a user) and also upon the contents of its own DSA information tree. However, the Standard stresses that how an actual DSA is implemented need bear no resemblance at all to this abstract model, as long as the externally visible behaviour, i.e. the abstract service, is identical to that of the abstract DSA. The Standard says nothing about the actual software components that will make up a real DSA. The building and design of a DSA are left entirely up to individual implementors, and this is how competition is introduced into standard conformant products. Some DSAs will be built using existing relational databases, others with existing hierarchical databases, and yet others with purpose built databases. Some DSA designs will outperform others, other designs may be more scalable, and yet other designs may be more flexible in the configuration tools that they give to administrators. The scope for DSA product differentiation is vast!

4.1.1 Directory User Agent (DUA)

At the First Level of abstraction, the Standard has defined an object, called a Directory User Agent, which interacts with the Directory system black box. The nature of this interaction is standardised. It consists of a set of operations that can be performed on the Directory by the user. For each operation the Standard defines the result or error that can be returned. Collectively these operations, along with the results and errors, are termed the Directory Abstract Service. The abstract service is turned into an actual protocol, called the Directory Access Protocol, or DAP for short, by combining it with the elements of two other OSI standard services: the Remote Operations Service (ROSE) [4.5], and the Association Control Service (ACSE) [4.6] (§ 5.1).

Implementors are free to design a DUA in any way that they please, and are guaranteed that it will interwork with the Directory system as long as it conforms to the DAP (Fig. 4.1).
Note. The Internet community has defined a Lightweight Directory Access Protocol (LDAP) (Yeong et al., 1993) for DUAs, that is now widely supported by implementations. For more details see § 10.3.1.

Fig. 4.1 Model of the Directory.

The Standard does not define the way that a DUA interacts with a user. Remember that the user can be either a human or a computer application, and so implementors are free to choose whichever design is most suitable for the anticipated user. Some may choose a programmable interface, others a command line interface, and others a windows, icons, mice and pointers (WIMP) type interface. All of these currently exist, and the user must choose the most appropriate one for their circumstances.
Note. Two programmable interfaces, using the C language, exist. One has been defined by the X/Open group [9.1]. This interface, known as XDS, provides a standard way of accessing a DUA implementation, but is very complex. The other, defined by the Internet community is the LDAP API, which is much easier to use.
It is very important to note that the user interface could bear very little resemblance to the abstract service. Several interfaces currently exist (Paradise International Report, 1991) in which a user enters a simple request, which bears no resemblance to a distinguished name or any other parameters of an abstract service request, and this is mapped into several sequential abstract service requests (usually comprising of Searches, Lists and Reads) before an answer is returned to the user. The average Directory user may therefore need to understand very little about the Directory Abstract Service or information models.

One thing that the Standard is very clear about, although this has caused a lot of confusion, is that there is precisely one DUA per user. A DUA is really a piece of software that conforms to the standardised interface between a user and the Directory system, i.e. the DAP. This does not mean, however, that each user must have their own personal DUA software. A piece of software on a computer, when invoked by one user, is acting as the DUA for that user. The same software, when invoked by another user, is acting as the DUA for that second user. So what, you may say. This distinction is important to bear in mind when one considers a topic such as caching and access controls. Data cached by shared DUA software on behalf of one user, cannot be given to a different user without potentially violating the access controls on the data. This is because the second user may not have access to the data, but since the DUA does not have a copy of the access control information, it cannot tell. However, data cached by a DUA can be returned to the user when the user requests it again. (The same is true of data cached by DSAs.) DUA and DSA designers need to be aware of this.

4.1.2 Directory System Agent (DSA)

At the second level of abstraction, we have Directory System Agents (DSAs) interacting with one another to provide the service requested by the user. The nature of the interaction between the DSAs is standardised - it is the DSA Abstract Service. This is mapped into the Directory System Protocol, the DSP, again by combination with ACSE and ROSE. The DSP consists of the operations, result and errors defined for the DAP, so that the user's requested operation, and the appropriate result or error, can be passed between him and the DSAs. In addition, however, DSAs add additional state information to the user's request, in order to notify each other how much of the operation has been progressed so far. This is so that undesirable effects such as duplication of results, and looping, do not result. This state information (§ 9.13) is added by the first DSA, modified by subsequent DSAs, and removed from the result (or error) by the first DSA before returning the result to the user. The path taken by the outgoing user request is always retraced by the returned result. The Directory has not opted for a scheme whereby the last DSA to get the request may return the result directly to the user, but rather each DSA passes on the request, and waits for the result (or error) to be returned to it, before passing a (possibly modified) result to the DUA or DSA that sent it the initial request. This process is known as chaining (Fig. 4.2).

Fig. 4.2 The distributed Directory, showing chaining.


From the First Level of abstraction, one might assume that the Directory would implement distribution and location transparency i.e. the user is unaware that the data is distributed between different systems, and is also unaware of whereabouts in the Directory the data is stored. The data's distribution and location are transparent to them. This would have been the case if chaining had been the only mode of interaction between DSAs. However, very early on in the standardisation process it was decided that chaining should not be mandatory for DSAs. Some DSAs may not implement this feature, and others, whilst implementing the feature, under certain circumstances may not be able to chain a particular operation. So another mode of interaction was defined for DSAs, known as referrals. When operating in referral mode, a DSA returns to its requestor (a DSA or a DUA) the name(s) and address(es) of the DSA(s) that it would have chained the request to, had it been operating in chaining mode (Fig. 4.3). The name and address of a DSA is called its Access Point. Along with the Access Point(s), the DSA also returns (most of) the state information that would have been added to the chained request, had it been sent (§ 9.13.1). The requestor is thus able to recreate the chained request that would have been sent, and the processing of the operation can continue as before (but see w/w 4.1). It is not mandatory for a DSA to act on a returned referral. It can, if it wishes, return the referral to its requestor. The referral is then passed back down the chain of DSAs, until either one of the DSAs decides to act upon it, or it arrives back at the DUA (Fig. 4.4). The DUA will have to then either spontaneously act on the referral, or ask the user what to do next, or return an error diagnostic to the user. All three actions occur in various DUA designs.

Fig. 4.3 Referral passed back to a DSA and acted upon.

Fig. 4.4 Referral passed back to DUA and acted upon.

The major consequence of referrals is that distribution and location transparency are no longer possible. DUAs become aware that the DIT is distributed between different systems. They also become aware of the actual location of the information. Referrals tell them what information is likely to be stored where. This does have major benefits however. Firstly, it can be much more efficient for DUAs to directly contact the DSA where the data is actually held, rather than always going via its home DSA (§ 4.3). Secondly, under some security regimes, administrators may require DUAs to directly Bind (§ 4.6.1) to their DSAs rather than sending them information which will be chained via several, possibly untrustworthy, DSAs. Note however that both of these advantages require configurable DUA software, that allows new DSA Access Points to be configured in and selected by the user.


Whilst the Directory does in principle allow DUAs to Bind to any DSA in existence, there probably will be operational and security reasons why this is not achievable on a global basis. The most likely scenario is that DUAs will have a local (or home) DSA, to which they usually, or even always, initially Bind to. This home DSA will then chain the user's request to other DSAs in the Directory that it knows about. DUAs often will not be configured with a choice of DSAs, and even if they are, users will not want the hassle of binding to different DSAs for different requests. Unless the home DSA operates in a totally insecure environment, it will be responsible for authenticating the user (DUA). Furthermore, it is unlikely that many remote DSAs will know the credentials of more than a handful of remote users, and so will expect the home DSAs to have authenticated the user on their behalf. (Note that this is not the case with the current pilot projects, which generally allow any DUA to connect to any DSA, and do not bother with authentication at all.) A fuller discussion of user authentication is presented in Chapter 7.


So how does a DSA know which other DSA to chain or refer a request to, when it cannot fully answer a user's request itself? To answer this, we must first look at the way in which the DIT is partitioned or distributed, and then look at the distribution meta-information that a DSA needs to store.

Fig. 4.5 Part of a hypothetical DIT, showing allowed naming contexts.

The way that the DIT is actually distributed amongst DSAs is very simple in concept. The global DIT is partitioned into subtrees, as decided by local administrators. A subtree can be of arbitrary size, ranging from a single entry, to the entire DIT. The important thing to note though, is that every partition must be a true subtree, and cannot be portions of the DIT with holes in it, i.e. entries missing from the middle of a large subtree. (Figs 4.5 and 4.6 show the partitioning of a hypothetical DIT into allowable and disallowable subtrees.) Each subtree must reside within one DSA. It cannot be distributed between two or more DSAs, without first splitting it into two or more subtrees. Each DSA can hold any number of subtrees. (In this way it is possible for a DSA to hold whatever parts of the DIT that it wishes, including the disallowed subtrees shown in Fig. 4.6. All that is needed to be done is to split the disallowed subtrees into several true subtrees.) Subtrees must always be maximal. In other words, a DSA may not hold two subtrees which are vertically adjacent to each other in the DIT, but rather it must hold one maximal subtree.

Fig. 4.6 Part of a hypothetical DIT, showing illegal naming contexts.

Each of these subtree partitions has an entry at its root, and the distinguished name of this entry is called the context prefix of the subtree. Obviously, all the entries in a subtree will have the context prefix as the initial part of their distinguished names.

Associated with each subtree, are a set of knowledge references. These knowledge references point to the DSAs which hold the subtrees vertically adjacent to this one. Knowledge references are the distribution meta-information held by DSAs. For a subtree that does not start at the top of the DIT, there will be one immediate superior knowledge reference associated with it. This points to the DSA holding the subtree that is immediately above it in the DIT (w/w 4.2). Subtrees that start at the top of the DIT are special, and obviously cannot have an immediate superior reference. They are held in special DSAs called First Level DSAs, and these will be described later in § 9.7. For a subtree that is not at the bottom of the DIT i.e. it does not have only leaf entries at its lower extremities, there will be a set of subordinate knowledge references which point to the DSAs holding the subtrees immediately beneath it. Fig. 4.7 shows the subordinate and immediate superior knowledge references associated with the subtrees of Fig. 4.5. It can be seen that these are linked together in pairs, and point to each other's DSAs. This linkage is part of the hierarchical Operational Binding between the pair of DSAs (§ 4.8.1).

Fig. 4.7 Part of hypothetical DIT, showing hierarchical Operational Bindings.

The combination of a subtree of entries, a context prefix, a full set of subordinate references (which can be empty) and possibly an immediate superior reference, is called a naming context. Naming contexts, then, are the complete unit of distribution of the DIT amongst DSAs. They comprise of a subtree of DIT entries and its associated distribution meta-information.

4.4.1 Administrative Considerations

The Standard does not place any restrictions on which DSAs can hold which naming contexts, nor on how many naming contexts a DSA can hold. Thus a DSA may hold zero naming contexts (w/w 4.4), or dozens of them. The only limiting factor will be that of a particular implementation. The naming contexts held by a DSA can be completely unrelated, although in practice, for administrative reasons, they probably will not be. For example, a DSA could hold two naming contexts, with context prefixes of {C=US, O=Firestone Tyres} and {C=DE, O=BASF}, but it would be hard to see the rationale behind this. The physical location of a DSA is not restricted by the Standard, and it need bear no relationship to the naming context(s) that it holds. It would be quite feasible, though not very practical, for a DSA which holds the naming context for Stanford University (i.e. the context prefix is {C=US, O=Stanford University}) to be physically located in a DSA at the Rutherford Appleton Laboratory in Oxford, England. However, for administrative reasons, it will probably be the case that for most organisations that run their own Directory services, most of their DSAs will be physically located in close proximity to the objects represented in their naming contexts. When an organisation requests a service provider to run its X.500 service on its behalf, then the organisation's naming context will probably be held at a DSA located at the service provider's installation.

Organisations running their own directory service, might typically start off with one DSA. This will hold the naming context for the whole organisation i.e. a context prefix of {C=XX, O=OrgName}, with the naming context extending down to all of the leaves. As the organisation grows, it might split the naming context into several smaller ones, one for each functional unit of the organisation (sales, manufacturing, admin etc.), with each new naming context being placed in a new DSA physically located in each of the functional units. The naming context holding the organisation's entry, will now need to have subordinate references to each of the functional unit DSAs. Each of the functional unit DSAs will need to have an immediate superior reference to the DSA holding the organisation's naming context. Hierarchical Operational Bindings are the concept designed to keep these references synchronised.


In § 2.7 it was explained what name resolution is, and that every operation on the Directory requires to have firstly name resolution performed on the purported name, before the actual operation can be evaluated. Distributed name resolution is the process of performing name resolution in a distributed environment. Each DSA that participates in distributed name resolution will typically only perform a fraction of it, and either will get the operation, via chaining or referrals, nearer to the DSA which actually holds the entry named in the operation, or will be able to say definitively that the entry does not exist.

In order to facilitate distributed name resolution, each non First Level DSA must hold one superior reference. This reference points upwards in the DIT, effectively to the root of the DIT. (It actually points to any DSA that holds any naming context which is nearer to the root of the DIT than all of those that it holds.) In many cases superior references will point to First Level DSAs. In the DSA information tree, a superior reference is held in the root DSE (Fig. 9.2).

In the absence of cross references (§ 9.2.5), distributed name resolution proceeds up the DIT, via superior or immediate superior references, until either a First Level DSA, or a DSA holding a naming context with a context prefix that matches an initial part of the purported name, is encountered. At this point, distributed name resolution then proceeds down the DIT via subordinate (or non-specific subordinate - see § 9.2.3) references, until the DSA holding the required entry is encountered. Only after distributed name resolution starts to move down the DIT, is it possible to know if a purported name is erroneous. (From this you will deduce that First Level DSAs have to know about all the naming contexts that start immediately below the root, i.e. typically those with context prefixes of {C=XX}.)

Once a non First Level DSA knows the names and addresses of:

then it is possible for it to indirectly locate every entry in the DIT (providing of course, that all other non First Level DSAs hold this minimum amount of information as well). The Standard mandates that all non First Level DSAs should hold this minimum amount of knowledge information.

4.5.1 Distributed Name Resolution in the Presence of Replication

It can be seen that once subtrees/naming contexts are replicated, there may be several remote DSAs that hold copies of the same subtree. There could therefore be several alternative Access Points that a DSA could contact in order to access an entry. Due to the replication model that has been adopted (Chapter 6), not all copies of a subtree/entry are judged to be equal. One of the copies is said to be the master copy, the rest are said to be shadow copies. Therefore there will be two categories of Access Point (or knowledge reference). A master reference points to the DSA holding the master copy of a naming context i.e. the master Access Point, whilst a shadow reference points to a DSA holding a shadow copy of (possibly part of) the naming context (w/w 4.3) i.e. a shadow Access Point.

Name resolution usually is no more complex in the presence of replication, than without it - we just have in built redundancy.
Note. This is not always the case when non-specific subordinate references are present - see § 9.13.16.
If the first DSA contacted via its Access Point is not available, then another Access Point from the set can be chosen. What is more complex however, is the updating and distribution of these sets of Access Points between the referencing DSAs. Hierarchical and shadow Operational Bindings were designed partially with this in mind, and it is the Operational Binding management protocol that may be used to keep this information up to date. This will be described fully in § 6.4.2, § 9.5 and § 9.19ff.


Now that we have seen how the DIT is distributed, and how the DSAs co-operate to provide a user service, let's look briefly at the abstract service that is provided to the user. Chapter 5 is devoted to a full description of this service.

4.6.1 The Bind and Unbind Operations

The first protocol exchange that must take place between a DUA and a DSA is a Directory Bind operation. To date, all OSI applications operate in connection oriented mode, whereby a connection is first established between two parties, and then data exchange takes place.
Note. The other mode of interaction between application processes is the connectionless mode. With the connectionless mode of operation, each message contains the address of its destination, plus some data. A connection is never established between the sender and the receiver. The connectionless mode of operation is analogous to dropping letters in a mail box, and allowing the postmen to take them in their own time, and by their own route (which may be different for two letters going to the same address). The connection oriented mode of working is analogous to making a telephone call, whereby a call is first connected, and then the messages are exchanged. Each mode has its advantages and disadvantages.
The Directory Bind operation is the operation which establishes a connection (or an association, to give it the correct ISO term) between the DUA and the DSA. Conversely, the Directory Unbind operation is the operation which closes the connection between the DUA and the DSA.

In order to establish the connection, certain information is needed, such as: an identification of the protocol that is to be used (i.e. DISP, DAP, DSP or DOP, in this case it is the DAP), the names and addresses of the communicating parties, and security credentials that enable the parties to authenticate each other. These are all parameters of the Bind operation. Once the connection has been established, then the user may interrogate or modify the information stored in the Directory.

When the user has finished accessing the information in the Directory, the connection is closed with the Unbind operation. The Unbind message contains no parameters.

4.6.2 The Interrogation Operations

There are four Directory interrogation operations, and one operation to abandon them.

The Read Operation

The Read operation is used to read information from one specific directory entry. The input arguments are a purported name and an indication of which information is to be read. The latter argument enables the user to specify whether all the information is to be read, or just a subset of the attribute types and values held in the entry.

The result of the operation normally yields the distinguished name of the entry, plus the requested attribute types and values.

The Compare Operation

The Compare operation is used to compare a user presented attribute value with those actually existing in the entry. The input arguments are a purported name, and a purported attribute value. The operation result returns a True or False indication, signifying whether or not the attribute value is actually present in the target entry. Compare is usually used to check the value of the user password attribute (Chapter 7).

The List Operation

The List operation is used to list the immediate subordinates of an entry. The input argument is a purported name. The result of the operation returns the relative distinguished names of the subordinates. The List operation is used to browse through the DIT, and to discover which entries are below other entries in the DIT, for example, to find the names of all the people resident in an organisational unit.
Note. Under certain circumstances (§ 5.8), the list may be incomplete. In this case, embedded referrals to other DSAs will be returned in place of the names of the subordinates.

The Search Operation

The Search operation is used to search portions of the DIT, and to return selected information about selected entries. It is potentially a very powerful operation, and allows users to find entries that match a chosen set of criteria. The input arguments identify amongst other things: the base entry from which the search is to start, the portion of the DIT to be searched, the criteria (filter) for selecting entries, and what information should be returned from the selected entries.

The base entry argument is a purported name. The portion of DIT to be searched may be one of: the base entry only, or only the immediate subordinates of the base entry, or the base entry plus its entire subtree. The filter applies certain tests to an entry to determine if it is selected or not. The tests are applied to attributes within the entry, and test for such things as: if an attribute type is present, or if an attribute value lies within a given range. Finally, how much entry information should be returned is specified. This can be all the information, or just a specified subset of attribute types and values.

The result returns the name of every selected entry along with the requested entry information. Under certain circumstances (§ 5.10.3), the result may be incomplete. In this case, embedded referrals to other DSAs will be returned in place of the names of the entries.

The Abandon Operation

The Abandon operation allows the user to abandon any of the above interrogation operations, if they are no longer interested in obtaining the result. The abandon operation has just one argument, which identifies the operation to be abandoned. If the abandon operation succeeds, the operation that has been abandoned will return an error diagnostic instead of a normal result. However, the abandon operation is not guaranteed to always work, and the Directory may refuse (fail) the abandon request, e.g. a DSA may not wish, or be able, to abandon an operation which has already been chained to other DSAs. In this case the original operation will complete as normal, and the abandon operation will return an error.

4.6.3 The Modification Operations

These operations are designed to modify entries within the DIT. The operations as defined in the '88 Standard, have certain limitations, but most of these have been removed in the '93 edition of the Standard.

Successful modify operations return a null result.

The AddEntry Operation

The AddEntry operation allows a leaf entry to be added to the DIT. The DIT is thus built up from the root of a naming context, downwards.
Note that this is the standardised method of building the DIT. Most Implementations add proprietary interfaces for bulk loading the DIT from other corporate databases.
Entries cannot be inserted into the middle of a branch, since this would affect the distinguished names of all of the subordinate entries. (Note however, that the ModifyDN operation affectively allows non-leaf insertions and deletions.)

The operation arguments contain the name of the new entry (distinguished name in '88 edition systems), plus its associated attributes. Any type of entry may be added: an object entry, an alias entry or a subentry.

The RemoveEntry Operation

The RemoveEntry operation allows a leaf entry to be deleted from the Directory. The operation argument contains the distinguished name of the entry to be removed. Any type of entry may be removed, but in order to remove a non-leaf entry, all its subordinates have to be removed first. In this way the tree is eaten away leaf by leaf.

The ModifyRDN Operation

This operation, which is only available to '88 edition systems, is used to change the relative distinguished name of a leaf entry. The operation arguments are the distinguished name of the entry, the new RDN, and an indication of whether or not the old RDN attribute values should be deleted from the entry. ModifyRDN provides no capability for restructuring the DIT. '88 edition DSAs will have to provide this facility via a proprietary mechanism.

The ModifyDN Operation

The ModifyRDN operation obviously has many restrictions, for example, how do you rename a non-leaf entry? Consequently, its scope has been considerably enhanced in the '93 Standard, and it has been given a new name to signify this difference. The ModifyDN operation is capable of renaming leaf and non-leaf entries, and of moving subtrees to new positions in the DIT. The operation can therefore help in restructuring the DIT to reflect new organisational structures.

The operation arguments comprise of the distinguished name of the entry to be renamed, the new RDN, and the distinguished name of the new superior entry in the DIT (optional). The standard places restrictions on the operation when it is used to move subtrees. In this case, all the affected entries must be in the same DSA (§ 5.16), otherwise proprietary mechanisms will still be needed.

The ModifyEntry Operation

This operation allows the contents of an entry to be modified, by adding new attributes and attribute values to, and by deleting existing attributes and attribute values from, the entry's contents. Any number of modifications may be specified in one operation, but all must succeed, or none will be made. In other words, the operation is atomic. Note that you are not allowed to modify the distinguished attribute values (i.e. the RDN) of the entry by this operation.

The operation arguments are the name of the entry to be modified, plus the sequence of modifications to be made.

4.6.4 The Errors

The Standard defines a comprehensive set of error messages which are used by the Directory to diagnose failures of a user's requested operation. The Standard details which error may be reported by which operation. Errors have been listed which cover every conceivable type of failure, from a DSA being temporarily busy, through to incorrectly specified user arguments, or a user having insufficient authorization or access rights.


This protocol is obviously very similar to the DAP, since it is used by cooperating DSAs to answer a user's DAP queries. The first step must be for the two co-operating DSAs to Bind together, and this is achieved via a DSA Bind operation. The parameters of this are identical to those of the Directory Bind. This time the protocol is identified as the DSP.

The operations that flow between the DSAs are termed chained operations. Each of the DAP operations has a corresponding DSP chained operation, and each result has a corresponding chained result.

The mapping of an operation to a chained operation is very simple - add some Chaining Arguments to the arguments of the DAP operation. The Chaining Arguments basically contain information about the progress of the evaluation of the operation (so-called state information) that is needed by the next DSA in the chain, in order for it to correctly process the request (w/w 4.1). Optional security and local information may also be passed in Chaining Arguments between a pair of DSAs. These Chaining Arguments are described more fully in Chapter 9.

The mapping of an operation result to a chained operation result is also very simple - add chaining results arguments to the arguments of the operation result. This information, which is minimal, and is often absent, may carry security or other local information between a pair of DSAs.

Finally, the mapping of chained errors to operation errors is even more simple - they are identical. Once a DSA returns an error to an operation, it is normally not manipulated in any way by any of the DSAs in the chain between the DSA signalling the error, and the DUA receiving it. The DSAs simply pass the error, unaltered, back to the DUA. The only exceptions to this are that certain soft errors (§ 9.12) may be ignored by a DSA, and that referral errors may be processed or manipulated. Certain soft errors - such as busy or unavailable - may be ignored by a DSA if it has another Access Point to contact instead of the one that failed - this may be the case when parts of the DIT are replicated. On the other hand, hard errors such as entry does not exist are never ignored. A referral has, quite anomalously, been classified as an error in the Standard, whereas it really is a result indicating partial progress of a request. As mentioned in §4.2, referrals may be processed by DSAs, so that they are not returned to the user. Also, as described in w/w 4.1, DSP referrals and DAP referrals are slightly different, in that referenceType is missing from '88 edition DAP referrals. An '88 home DSA therefore needs to alter a referral before passing it to the DUA.


We have seen that DSAs co-operate in the processing of directory operations. This is achieved by the use of chaining or referrals. However, before a DSA can chain or refer to another DSA, it needs to know something about the other DSA. It needs to have established some sort of operational relationship with the other DSA, the terms of which form the basis for how the two DSAs are to inter-operate. This operational relationship is termed an Operational Binding. Operational Bindings are typically long term relationships between pairs of DSAs, that outlive the duration of a single connection. It would not be unusual for an Operational Binding to last for several years. The '93 edition of the Standard currently standardises the two most important types of Operational Binding, although during the preparation of the Standard it was recognised that several other types of Operational Binding also exist. These may be standardised in subsequent editions of the Standard.

The '88 edition of the Standard did not mention Operational Bindings by name, although they were implicit since it was obvious that '88 DSAs had to co-operate. The only difference between the two editions of the Standard in this respect, is that the '93 Standard explicitly details, for the two standardised types of Operational Binding, the information that needs to be exchanged between the co-operating DSAs. It also defines an optional protocol - the Directory Operational Binding Management Protocol (DOP) - that may be used to create and maintain this information. On the other hand, the '88 Standard assumes that this information appears in a DSA as if by magic. From the perspective of the '93 Standard, '88 DSAs do have Operational Bindings with other DSAs, but the requisite information appears in the DSA via proprietary means. This probably means that phone calls or Email message are exchanged between the administrators of the two DSAs, and that configuration information is input into each DSA via a proprietary management interface. '93 DSAs that do not support the DOP will also have to resort to these proprietary means for inputting and updating their Operational Binding information.

Five operations make up the Operational Binding management protocol. The DSA Operational Binding Management Bind operation (DOP Bind for short) is used to open up an association (or connection) between two DSAs, so that they may establish or update an Operational Binding (Fig. 4.10). The Establish Operational Binding operation creates an Operational Binding between a pair of DSAs, and transfers the appropriate information between each DSA, so that they know how to cooperate. DSAs which do not have an Operational Binding between them, are in a non-co-operative state, and can quite properly refuse any operation that passes between them. DSAs that have an active Operational Binding are in a co-operative state, and should correctly process any operation that passes between them, providing of course that it is an operation that was expected under the terms of the relationship. Figure 4.8 shows the state transitions that occur in a DSA, as a result of receiving DOP operations from another DSA.

Fig. 4.8 Co-operative state transitions in a DSA y.

The Modify Operational Binding operation may be used by either DSA to update the operational information stored by the other DSA, and to thereby change the parameters of the relationship. Examples here include: a DSA is re-configured to a new address, or the context prefix of a naming context changes, or a shadowing DSA no longer requires a copy of certain attributes. The Terminate Operational Binding operation cancels the relationship between the pair of DSAs, and causes the stored operational information to be deleted.

Finally the DSA Operational Binding Management Unbind operation is used to close the connection after the two DSAs have finished updating their Operational Binding information. The Operational Binding will still be active after the Unbind operation, unless of course, a Terminate Operational Binding message was transferred.

4.8.1 Currently Standardised Operational Bindings

Two different types of Operational Binding are currently standardised. A Hierarchical Operational Binding, or HOB, governs the relationship between a pair of DSAs holding vertically adjacent naming contexts in the DIT. A Shadow Operational Binding governs the relationship between a pair of DSAs that are replicating (part of) a naming context.

Hierarchical Operational Bindings

We have seen that the DIT is distributed between DSAs and that each DSA holds some knowledge information that tells it where its portion of the DIT (naming context) fits into the global DIT. This immediate superior/subordinate reference pair forms part of the operational information of a Hierarchical Operational Binding, see Fig. 4.7. However, there are more to HOBs than simple knowledge reference synchronisation. Certain of the information in the global DIT, i.e. that associated with subentries, applies to subtrees of the DIT, irrespective of how the subtrees are distributed between DSAs. (This information is part of the Directory Operational and Administrative Information Model, described in Chapter 2.) If a DIT subtree is distributed between a pair of DSAs, i.e. a DIT subtree consists of two adjacent naming contexts held in different DSAs, then the subentry information held in the (superior) DSA holding the administrative entry, needs to be copied to the (subordinate) DSA holding the lower part of the subtree. For example, the collective telephone number attribute may be held in a subentry below the organisation's entry (the administrative entry), but it may apply to all the entries below the organisation's entry. Some of these entries may be held in other DSAs (e.g. see Fig. 5.3). The creation of an immediate superior knowledge reference and subentry information in the subordinate DSA, and a subordinate knowledge reference in the superior DSA, signifies the creation of the Hierarchical Operational Binding between the pair of DSAs. Each DSA now knows how to behave in respect of the other DSA, and knows how and when to chain or refer a user's request to the other one. The subordinate DSA also knows which access controls, schema information and collective attributes it has inherited from its immediate superior DSA.
Note.The Standard also defines a Non-specific Hierarchical Operational Binding (NHOB), which is established when the immediate superior DSA has a non-specific subordinate reference instead of a subordinate reference to the subordinate DSA. In most other respects, NHOBs are similar to HOBs.

Fig. 4.9 An example of DOP and DSP requests interleaved in time.

When a new non First Level DSA is created, in order for it to connect to the wider Directory, it first needs to establish a Hierarchical Operational Binding with its immediately superior DSA. This links it into the DIT, passes it down administrative information (if any) from its superior, gives it an immediate superior reference (which can also be used as a superior reference), and provides the superior with a subordinate reference (see § 9.9 for more details). DSP operations may then flow between the two DSAs. This is illustrated in Fig. 4.9. The subordinate DSA holds the naming context with context prefix {C=US, L=Florida, O=XYZ Inc, OU=Sales}. The immediate superior DSA holds the naming context with context prefix {C=US, L=Florida, O=XYZ Inc}. The subordinate DSA establishes a HOB with its superior, and both DSAs are then ready to co-operate.
Note.The superior DSA is also able to initiate the Establish Operational Binding operation. It does not matter which of the two DSAs actually initiates the request.
(Remember that this information could flow via a telephone call and be manually configured into both DSAs, instead of using the automated DOP.) Both DSAs then pass DSP requests between themselves as and when necessary e.g. the subordinate DSA asks to read an entry from Texas. The subordinate DSA is then due to be re-configured on the network, causing it to change addresses. It notifies the immediate superior DSA, via a Modify Operational Binding request, that as of 8 a.m. Monday morning it will have a new address. Both before and after the re-configuration, the superior DSA is able to contact its subordinate DSA, and user requests can still flow between them via the DSP e.g. the superior DSA wants to search for information from the sales unit. Management then decide to implement a tighter security policy, and place some mandatory access controls over the whole organisation. They do this by updating the prescriptive access controls in the organisation's administrative subentry. This information is automatically conveyed to the subordinate DSA via the DOP (Modify Operational Binding request). User requests may continue to flow undisturbed between the two DSAs, both before and after the Operational Binding update.

Fig. 4.10 Different associations for different protocols.

Note that whilst the DOP and DSP requests are interleaved in time, they do not flow down the same connection (or association). Both the DSP and DOP requests have to be superseded by an appropriate Bind operation. This establishes an association for the particular protocol (or application context). Figure 4.10 illustrates the fact that two separate logical communications links are established between the pair of DSAs, one for each protocol, with each link using the same set of DSA Access Points.

Shadow Operational Bindings

The second type of Operational Binding is concerned with replication. DSAs are able to copy DIT information to one another. This mechanism, known as shadowing, is described in more detail in Chapter 6. Before a DSA is able to participate in shadowing, it needs to establish the terms of the operational relationship with the other DSA. This information comprises of such things as: the portion of the DIT that is to be copied, and the frequency that updates should be transferred between the DSAs. Hence another type of Operational Binding is the Shadow Operational Binding (SOB). Before replication (shadowing) can take place, a Shadow Operational Binding needs to be established between two DSAs. One of the DSAs, called the shadow supplier, will provide the replicated information to the other DSA, called the shadow consumer. Once the Operational Binding has been established, either by proprietary means, or by using the DOP, shadowing proper can take place, using the Directory Information Shadowing Protocol (DISP) (§ 4.9).

The terms of the shadowing agreement may be updated at any time via the Modify Operational Binding message, and subsequent DISP messages will then abide by the terms of the new agreement. When shadowing is to cease, a Terminate Operational Binding message is sent, after which no more DISP messages are allowed. The sequencing of DISP and DOP messages is very similar to those of the DSP and DOP shown in Fig. 4.9. Two associations are also needed, one for the DOP and one for the DISP, similar to that shown in Fig. 4.10. If a pair of DSAs had a HOB and a SOB, then three associations would be needed, one each for the DOP, DISP and DSP.

One of the functions of the SOB is to update a supplier DSA with the list of DSAs that have been provided with copies of the naming context. (DSAs receiving copies may also act as suppliers, and pass the data onto other DSAs, see Fig. 6.1.) In this way the DSA holding the master copy of a naming context is able to obtain a complete list of the Access Points of all of the DSAs holding shadow copies of the naming context. This information can then be added to the set of knowledge references that point to a particular naming context, thereby building in redundancy to name resolution. A complete description of this mechanism is given in § 9.5.

4.8.2 Non Standardised Operational Bindings

Clearly there are other types of relationship that exist between DSAs. Some are quite definitive, such as: the relationship between a DSA that is to act as the superior of another DSA and is to be referenced by it via its superior reference, and the relationships that exist between the set of First Level DSAs. Others are much more ephemeral, such as the relationship between two DSAs that temporarily have cross references to each other, or the relationship between a DSA referenced in a referral and the DSA acting upon the referral. However, none of these relationships have yet been standardised, and so they must still be managed by proprietary means. In the case of referrals, the DSA referenced in a referral may refuse to process the request from the DSA acting upon the referral, precisely because no operational agreement has been established. The Standard currently gives no guidance in this area. Maybe the 1996 Standard might automate some of these other relationships, who knows?


The DISP is used to transfer the shadowed information from the shadow supplier to the shadow consumer. The DISP consists of three operations plus the DSA Shadow Bind and Unbind operations, which are used to open and close the connection. Either of two operations may be used to prepare both of the DSAs for sending and receiving the shadowed information. The third operation is used to actually transfer the shadowed data. Either the Coordinate Shadow Update operation, which is sent from the shadow supplier to the shadow consumer, or, alternatively, the Request Shadow Update operation, which is sent from the shadow consumer to the shadow supplier, may be used to synchronise the DSAs for the next batch of updates. Both serve the same purpose, and either may be used. The Update Shadow operation is used to actually transfer the batch of updates from the supplier to the consumer. Each batch of updates is timestamped by the supplier, so that they can be uniquely identified. This aids recovery, in the case of a failure.

The Coordinate Shadow Update operation tells the consumer which batch of updates it should have received last time round, and also what sort of update it will receive this time. The latter parameter, called the update strategy, takes one of three values:

Note. There is actually a fourth value allowed, but its definition is outside the scope of the Standard. It may be privately defined by individual implementors, to signal their proprietary update mechanism. This field is really here to allow '88 implementations which have already defined their own replication mechanisms, to gradually migrate towards the '92 Standard mechanism.

The shadow consumer can either reply OK to the operation, in which case it is prepared to receive the next batch of updates as specified, or it can send an error response with a diagnostic code such as: I am not ready to receive updates yet, or I already have that batch of updates safely stored.

The Request Shadow Update operation tells the supplier that the consumer is ready to receive a batch of updates. The parameters are the same as in the Coordinate Shadow Update operation, i.e., the timestamp of the last batch of updates that were successfully received, and the sort of update that it would like (obviously no updates is not allowed in this case!). If the shadow supplier is willing to send the next batch of updates by return, it will send an OK response to the operation, otherwise it will send an error response with a diagnostic code such as: I am not yet ready to send updates, or I do not support that sort of update strategy.

Assuming that the two DSAs have been successfully synchronised by either the Coordinate or Request Shadow Update operation, the shadow supplier will then send an Update Shadow operation to the consumer. This operation provides the latest batch timestamp, and either lists the changes that have been made to the replicated portion of the DIT since the last update, or sends a completely new copy of the data to the consumer, depending upon the update strategy. The shadow consumer securely stores the updates, and then replies OK to the supplier (Fig. 4.11). Alternatively, the consumer may indicate a problem with the received data, and may return an error code. Unfortunately the Standard gives few guidelines as to how to proceed if an error occurs during an Update Shadow operation (w/w 6.4).

Fig. 4.11 The sequencing of the DISP.

Once the shadowed data has been securely stored, it may be used to satisfy user queries in just the same way as other data mastered by the consumer DSA. The main difference is that user modify requests cannot be performed on the shadowed data. These must always be sent to the master DSA. Their effects on the shadowed data will be received some time later by the consumer DSA when it receives the next batch of shadow updates.


4.1 A consequence of referrals (which contain the state information that would have been inserted into a chained operation, had the DSA chained the request instead of sending a referral) being returned to DUAs, is that the DAP should in fact be virtually identical to the DSP! This is because the DSP is really only the DAP with DSA state information tagged onto it. When a DAP request is created from a returned referral, then it is logically the same as the DSP. Alignment of the DAP and DSP was strongly resisted in some quarters when the '88 Standard was being formulated. One consequence of this, was that '88 DSA referrals and DAP referrals were slightly different, in that one field (referenceType) present in the DSP referral, and used by DSAs to check the consistency of their knowledge references, was removed from the DAP referral. (It has been put back into the DAP referral in the '93 edition of the protocol see § 9.13.8!) Another consequence is that Chaining Arguments do not appear directly in the DAP, but have appeared, in a slightly different guise, in Common Arguments instead! (§ 5.4.) Some of the '88 Standard's makers may not have wanted the protocols to be the same, but they could not obviate the need for the state information to be carried somewhere in the DAP!
        One further decision that was made, was not to carry all of the state information in the referral. Only the absolutely essential information should be carried. One parameter that was removed was trace information (§ 9.13), since it was quite erroneously thought that looping could not occur by returning a referral. It has since been discovered that looping can occur. For example, DSA one returns a referral to a requestor, that points to DSA two. The requestor acts on this referral and contacts DSA two. DSA two, having not progressed the operation at all, returns a referral to DSA one. DSA one will again return a referral to DSA two! A similar scenario occurs if DSAs one and two each hold aliases that point to each other. This bug had to be fixed by a defect report on the '88 Standard, and by new text in the '93 Standard. If trace information had been included in referrals, the looping would have been immediately visible.

4.2 Naming contexts originally started out containing a reference, as well as a set of subordinate references. The superior reference points upwards in the DIT, to any DSA which is superior to it in terms of its DIT holdings. It was realised however, that if a DSA holds more than one naming context, then it will hold more than one superior reference. All of these except one, will be redundant in the process of name resolution, since all point upwards towards the root of the DIT. Only the one that points highest need be kept. (Subordinate references, on the other hand, are never redundant, because they all point to different subordinates.) It was thus decided in the '88 Standard to remove superior references from naming contexts, and to say that DSAs have only one superior reference, irrespective of the number of naming contexts held. This superior reference must point to a DSA which holds a naming context superior in the DIT to all of the naming contexts held by this DSA. When the '92 work was started, and hierarchical Operational Bindings were introduced, it was again realised that a superior reference was needed per naming context. So they were introduced again into naming contexts, only this time they were given the name immediate superior reference, to differentiate them from the one and only superior reference. Furthermore, an immediate superior reference does not point to the root of the DIT, but instead points to the DSA holding the immediately superior naming context.

4.3 The term actually used in the Standard for the information held by a DSA pointed to in a shadow reference, is commonly usable copy. This term is really a fudge to cover up a disagreement between the experts. Some experts suggested that shadow references should only be to DSAs that held complete copies of whole naming contexts, whilst others suggested that they could be to any DSA that held a copy of any useful part of a naming context. But with the latter position, if the shadow reference was to be of significant use to a wide audience, it would also need to hold an indication of precisely which part of the naming context was held in the remote DSA. No-one wanted to go down this path, and so the compromise was to say that shadow references point to commonly usable copies of a naming context. The precise definition of what commonly usable actually means is left to Directory administrators. The Standard only recommends that they should be copies of whole naming contexts.

4.4 It is possible to build a DSA that only holds a superior reference and that does not hold any naming contexts or shadowed information. Each DUA request to it would then be chained to the superior DSA. Such a DSA would really be a DUA that talks the DSP!