VALUE X500 OPERATIONAL INTERWORKING FORUM AND PLATFORM TECHNICAL QUARTERLY REPORT INRIA 01-01-94 30-04-94 Version : 1.2 PLAN ==== 1. Introduction 2. Name Resolution / Distribution of operations 2.1 The targetObject and operationProgress components 2.2 The nextRDNToBeResolved component : an optional component ? 2.3 Distribution of subordinate entries in different DSAs 2.4 Operation resolution / optimization 3. Loops / Continuation references 4. Semantic of the limitProblem component / consequences 5. Copies 5.1 Copies and distribution of an operation 5.2 Copies and name resolution 5.3 Copy of a complete subtree / one-level search 5.4 Copies, general considerations 6. Search / indexed attributes 7. Just one comment on legal issues 8. Miscellaneous bugs 8.1 BaseObject / alias 8.2 The optional targetObject component 8.3 DUA / Stack of references 8.4 The dontusecopy option 8.5 Wrong DN 8.6 Incorrect Trace 8.7 Merging Results 8.8 Reference pointing to itself 8.9 Filters 9. Conclusion 1. INTRODUCTION ============== The Operational Interworking Forum and Platform (OIFP) is part of the VALUE PARADISE X500 Project which is an initiative of the European Commission to continue the provision of some essential X500 services. Initial experiences have demonstrated that different implementations, all conformant to the same standard may fail to provide acceptable operational interworking under specific data or knowledge distribution configurations. For this reason, it was decided to provide the DSA managers and the developers/suppliers of X500 Directory software with the OIFP service. The main goal is to identify and discuss interworking problems, not to give a label to implementations. Three different implementations have been connected. In order not to make any positive or negative publicity, the name of the implementations is not disclosed. Initially only interworking problems were to be addressed. Given that several conformance problems have been encountered so far, it has been decided to take them into account. Nevertheless the general approach has not been changed, we do not check each protocol data unit systematically but try to make interwork different implementations in various contexts. This technical report presents the problems that were encountered during the last period of the project (01-94 / 04-94). Twenty four reports were issued. If you require any further information regarding this report you can contact : Name : Paul-Andre Pays Bruno Koechlin Telephone: +33 1 39 63 54 58 +33 1 39 63 57 36 Email: oifp@pamir.inria.fr S=OIFP; OU=pamir; O=INRIA; P=INRIA; A=ATLAS; C=FR Address: INRIA Institut National de Recherche en Informatique et Automatique B.P. 105 / 78153 Le Chesnay Cedex / France Fax : +33 1 39 63 53 30 / Twx: 697033 F 2. NAME RESOLUTION / DISTRIBUTION OF OPERATIONS ================================================= Introduction : -------------- The standard has defined every directory operation as comprising three distinct phases : - the Name Resolution phase - the Evaluation phase - the Result Merging phase Name Resolution is the process of sequentially matching each RDN in a purported Name to an arc (or vertex) of the DIT, beginning logically at the Root and progressing downwards in the DIT. This phase can be distributed among several DSAs, at the end of this phase the targetObject must be located if it exists. The required operation is performed in the Evaluation Phase. The operation may involve a single entry or multiple entries. The latter case is much more complex since the multiple entries may be distributed in several DSAs. It is the case of the List and Search operations. The phase is then called the Multiple object evaluation phase. We have distributed DIT subtrees between different implementations. Depending on the subtree, an implementation is in the position of the superior or subordinate DSA. Problems had been identified in the Name Resolution and Evaluation phases during the previous period of the project. This period was dedicated to validating the new releases installed on the platform and focusing on the referral mode. 2.1 The targetObject and operationProgress components ------------------------------------------------------- Description of the problems ----------------------------- Parts of the DIT are not explored or explored several times. Causes of the problems ---------------------- We will describe this problem in detail because we encountered it twice and it has significant consequences : DIT : C=FR | O=OIFP held by DSA 1 | ------------------------------------- | | | OU=OIFP-1 OU=OIFP-2 OU=OIFP-3 distributed between DSAs | | | different from DSA 1 Operation : SEARCH -whole-subtree -baseObject= C=FR; O=OIFP Rule 1 : When DSA 1 distributes the operation between its subordinate DSAs (which hold OU=OIFP-i) it must not modify the targetObject (C=FR; O=OIFP), but only set the operationProgress.NameResolutionPhase to completed. Rule 2 : When a subordinate DSA of DSA 1 receives this chained operation, it must only deal with the subordinate entries of C=FR; O=OIFP that it holds and must not deal with the references that it holds regarding the other subordinates of C=FR; O=OIFP. We have identified the following two problems : - Rule 1 was not applied : the target object was changed from C=FR; O=OIFP; to C=FR; O=OIFP; OU=OIFP-i. When a subordinate DSA, DSA-i, applied rule 2, it only dealt with the subordinates of C=FR; O=OIFP; OU=OIFP-i that it held. Consequently, * the other subordinates of C=FR; O=OIFP that DSA-i held, * the subordinates of C=FR; O=OIFP; OU=OIFP-i that DSA-i did not hold, were not dealt with. - Rule 2 was not applied : a subordinate DSA followed the references that it held regarding the other subordinates of C=FR; O=OIFP which were dealt with more than once. We have encountered a few other bugs regarding the value of the operationProgress, nevertheless, with respect to this issue the quality of the implementations has been highly enhanced. 2.2 The nextRDNToBeResolved component : an optional component ? --------------------------------------------------------------- The nextRDNToBeResolved component is only used when the operation is in the "proceeding" state which means that at least the first RDN of the base object has been resolved but not all its RDNs. This component points to the first RDN which has not yet been resolved. The standard mentions that - it is optional - "it is only present if the nameResolutionPhase component has the value proceeding". The last sentence does not indicate clearly whether the nextRDNToBeResolved component is mandatory in this case. One implementation does not set the nameResolutionPhase component when the operation is in the "proceeding" state. If we look at the specification of the name resolution algorithm, the nextRDNToBeResolved component is used to : - control the progression of the name resolution - detect loops Given that these parts of the algorithm are crucial in an operational, wide scale context, we think that the nextRDNToBeResolved must always be set when the operation is in the "proceeding" state. The implementation has been modified. 2.3 Distribution of subordinate entries in different DSAs --------------------------------------------------------- Introduction ------------ One implementation did not make it possible to distribute the subordinate entries of an entry between different DSAs (see OIFP technical report, 01/09-93/93, paragraph 2.1). This results in having the same entry twice in the DIT. For instance in PARADISE the C=FR entry is doubled : root | -------------------------------- ------------ root | | | | FR DSA | ... C=GB ... C=DE ... C=FR | | C=FR | DSA | | | | | -------------------------------- -----|------ | --------------- | | | Description of the problem -------------------------- This organization has no consequences as long as the FR DSA does not control the name resolution which means that the FR DSA is not conformant to the standard. If the DSA software run on the FR DSA was replaced by a standard implementation, it would reject the operations chained by the root DSA. Cause of the problem --------------------- When the root DSA chains the operation, it considers that it has resolved the C=FR RDN. When the C=FR DSA receives the operation, it considers that it is an error to have sent it this operation, since it cannot resolve another RDN (C=FR has already been resolved). The operation should have been sent to the subordinate DSA of C=FR which holds the next RDN that has not yet been resolved. Modifications aimed at solving this problem have been experimented and will be used in the framework of PARADISE. 2.4 Operation resolution / optimization --------------------------------------- Introduction ------------ DIT : entry 1 held by DSA 1 | ----------------------- | | entry 2.1 entry 2.2 held by DSA 2.1 held by DSA 2.2 DUA : bound to DSA 2.1 Operation : SEARCH -wholesubtree -baseObject=entry 1 According to the standard, the evaluation phase can only start if the name resolution has been completed. If you apply the standard, the operation described above will follow these steps : 1 : the operation is sent by the DUA to DSA 2.1 2 : the operation is chained from DSA 2.1 to DSA 1 3a : DSA 1 chains the query to DSA 2.1 3b : DSA 1 chains the query to DSA 2.2 4a : DSA 2.1 returns a result (or an error) to DSA 1 4b : DSA 2.2 returns a result (or an error) to DSA 1 5 : DSA 1 returns the final result to DSA 2.1 6 : DSA 2.1 returns the final result to the DUA One implementation, we will call it implementation OPT, has tried to optimize the processing of this operation. Description of the problem -------------------------- If the type of DSA 1 is OPT and if the type of DSA 2.1 is not OPT the subtree, whose root is entry 2.1, is not explored. Cause of the problem -------------------- The designers of implementation OPT have considered that steps 3.a and 4.a are useless and that DSA 2.1 can start the operation evaluation in its own part of the DIT (subtree whose root is entry 2.1) just after step 1. Consequently if DSA 2.1 does this, DSA 1 does not need to perform step 3a since it considers that it has already been done by DSA 2.1 which it deduces from its knowledge information. The processing of the operation will be : 1 : the operation is sent by the DUA to DSA 2.1 2a : the operation is chained from DSA 2.1 to DSA 1 2b : DSA 2.1 deals with its local part of the DIT 3 : DSA 1 chains the query to DSA 2.2 4 : DSA 2.2 returns a result (or an error) to DSA 1 5 : DSA 1 returns the result to DSA 2.1 6 : DSA 2.1 merges the results and returns a final result to the DUA If - DSA 2.1 is not an OPT implementation and - DSA 1 is an OPT implementation The processing of the operation will be : 1 : the operation is sent by the DUA to DSA 2.1 2a : the operation is chained from DSA 2.1 to DSA 1 3 : DSA 1 chains the query to DSA 2.2 4 : DSA 2.2 returns a result (or an error) to DSA 1 5 : DSA 1 returns the result to DSA 2.1 6 : DSA 2.1 returns the result to the DUA step 2b is not performed and the part of the DIT, whose root is entry 2.1, is not explored. The behaviour of implementation OPT is not conformant to the standard since the evaluation phase can only start when the name resolution is completed. The designers of implementation OPT wish to keep this feature. In order to avoid interworking problems this implementation has been modified in the following way : - DSA 1 now returns, at step 5, a partial result containing : * the result returned by DSA 2.2 * a continuation reference related to entry 2.1 pointing to DSA 2.1 (this reference is intended for use by a non OPT implementation in order to explore the part of the DIT whose root is entry 2.1) - DSA 2.1 * still anticipates (performs step 2b) * ignores the continuation reference returned by DSA 1 3. LOOPS / CONTINUATION REFERENCES ================================== Introduction ------------ During the first period of the project, we focused on the chaining mode and found cases where loops were not detected. The implementations were modified and we have not identified undetected loops so far. During this last period we focused on the referral mode. Description of the problem -------------------------- When the referral mode was used, we did not identified new problems provided that only DSP was used. On the other hand, when DAP was used several undetected loops were encoutered. Causes of the problem --------------------- Once again the operationProgress is the cause of the problem : - DSAs do not take into account the value of the operationProgress when the operation comes from a DUA and consider that the name resolution has not yet started. They start it again inducing a loop. Since the value of the operationProgress is changed wrongly, it is difficult to detect a loop. - DUAs also have the same wrong behaviour : when they receive a continuation reference and follow it, they do not keep the value of the operationProgress returned in the continuation reference. The name resolution is restarted encouraging undetected loops. Undetected loops can easily break down a part of an X.500 infrastructure. New directory client software are being developed, using different technologies. We would like to stress the importance of the undetected loops issue so that the designers of new software supply products which deal with the operationProgress component properly. 4. SEMANTIC OF THE LIMITPROBLEM COMPONENT / CONSEQUENCES ======================================================== Introduction ------------- The standard defines two basic modes of DSA interaction to process the distributed operations, the "chaining" and the "referral" modes. The principle of the "referral" mode is the following : When a DSA considers that it cannot process a request and must forward it to another DSA (we will call it the target DSA) according to a knowledge reference, it does not forward the query to this target DSA but returns, to the originator of the request, the address of the target DSA with the status of the query in a continuation reference. A continuation reference can be returned in - a dsaReferral in DSP (or Referral in DAP) which is an Error PDU. This PDU can contain only one continuation reference or - a result which can contain in the partialOutComeQualifier component several continuation references. When references are returned in a partialOutComeQualifier they can be associated with the limitProblem which can take 3 different values : - timeLimitExceeded - sizeLimitExceeded - administrativeLimitExceeded The standard does not give operational guidelines related to the limitProblem component. Description of the problem -------------------------- In a heterogeneous environment (different DUA and DSA implementations), if a DSA returns a continuation reference in a partialOutcomeQualifier, the reference is seldom followed. Cause of the problem -------------------- We have identified two main causes (apart from bugs) : - product designers have considered that a given type of directory agent is not aimed at following this type of reference. This point has already been discussed in the 10/93-12/93 OIFP technical report, section 4. - there have been different interpretations of the partialOutcomeQualifier and its components. We can identify two main kinds of interpretation : interpretation 1 : A DSA returns a continuation reference if it considers that it can be followed and that the operation can be succesful, otherwise it will not return a reference. The limitProblem field is an informational field. interpretation 2 : A DSA always returns continuation references, even it is sure that they cannot be followed now. They can be used for caching purpose. It sets the limitProblem to indicate that it considers that it would be useless to follow the reference now, otherwise it does not set the limitProblem. Given all the possible situations : - the type of application - DSAs in the referral / chaining mode - DSAs setting internal limits (time ,number of entries returned) - Operations with time/size limits set or not - DUAs allowing users to set or not the time/size limits - and all the possible failures (network failure, access control, congestion ...) It would be too long to analyse the whole issue. We simply wish to - raise the problem - give a few recommendations in the framework of PARADISE We have to strike balance between : - not following references which would have been relevant to follow - following references uselessly Up to now, the first case has been the most frequent. - It has been discussed whether a DSA, using the referral mode, should set the limitProblem to administrativeLimitExceeded. We recommend not to set the limitProblem in this case in order to stress that the reference should be followed. - Being able to configure the DUAs so that, they follow the reference automatically, or return the information to the user, according to the value of the limitProblem, could be useful : If an operation must be chained several times, we can imagine that the time limit of the operation may be reached before having reached the target DSA. A reference will be returned with limitProblem set to timeLimitExceeded. If the reference is not followed, the user may try again and may get the same answer. If the reference is followed the operation will restart closer to the target DSA and may succeed before having reached its timeLimit. 5. COPIES ========== The X.500 standard allows a DSA to hold a copy of one or more entries whose originals are in other DSAs. 5.1 Copies and distribution of an operation ------------------------------------------- Introduction ------------ When the dontusecopy option is not set by the originator of the operation, DSAs must have the same behaviour to perform the operation, whether they use copied or original entries. Description of the problem -------------------------- DIT : - Data entry 1.1 copy held by DSA COP | | ----------------------------------- | | ... | | entry 2.1 entry 2.i entry2.n * entry 2.1 is an original entry held by DSA COP * entry 2.2 to entry 2.n are copies held by DSA COP - Knowledge * a reference for the original entry 1.1 pointing to the master DSA of this entry * a reference for each entry 2.i (with i different from 1) pointing to the DSA holding the original of entry 2.i Operation : READ (this entry does not exist) - copies allowed The READ operation is chained to the DSA which holdsthe original of entry 1.1. This DSA returns a "Service Error, invalid reference". The inconvenience is twofold : - From the user's point of view, an error meaning that the DIT is inconsistent, is returned when simply the base object of the operation does not exist. - From the operational point of view, holding a copy of an entry is aimed at performing the operation locally and avoiding chaining. A DSA must consider that it holds all the subordinate knowledge associated with entry 1.1. Chaining the operation to the master DSA of entry 1.1, each time it cannot resolve (or find a reference related to ) the RDN following entry 1.1 is useless : the master DSA must have the same subordinate knowledge, it would not be able to do futher processing and would return an error. Cause of the problem -------------------- The implementation considers that it holds only a copy of entry 1.1 but not all the knowledge associated with it. If it cannot find entry 2.unknown or a reference pointing to this entry it chains the query to the DSA which holds the original of entry 1.1 with the knowledge associated with it. The master DSA of entry 1.1 returns a "Service Error, invalid reference" because it considers that since DSA COP has resolved entry 1.1 and chained the operation to it, DSA COP has an invalid subordinate reference related to entry 2.unknown pointing to it. Given the X.500 model the copy of an entry must be considered as : - the copy of the data of the entry and - the copy of the subordinate knowledge associated with this entry 5.2 Copies and name resolution ------------------------------ Introduction ------------ It is imposssible to have a efficient and reliable directory service if entries cannot be duplicated in different servers : given the reliabilty of computers systems, directory software, network accesses, in order to enhance the reliability of a directory service, it is much more efficient to multiply the systems and the parts of the DIT they are responsible for than trying to have only one very reliable and secure system. Applied to X.500 this means that copied entries should be used like original entries provided that the originator of the operation authorizes copies. Description of the problem -------------------------- One implementation does not provide the minimum functionalities which would make it possible to duplicate parts of the DIT publicly. By publicly I mean that the copies are available to any directory agent to perform the basic X.500 functions. Cause of the problem -------------------- This implementation does not use the copies during the name resolution. This means that as long as the base object of an operation has not been resolved, the operation must cross the single master DSA of each RDN of the base object. The copies managed by this implementation have only a local scope which means that they can only be used by the DSA which holds the copy to perform the evaluation phase. This does not have interworking consequences provided that - DSA managers are aware that this kind of copies are not "public" - consequently they do not set references pointing to these copies from other DSAs 5.3 Copy of a complete subtree / one-level search ------------------------------------------------- Introduction ------------ We described in section 2.3 of the 01/93-09/93 technical OIFP report that one implementation did make it possible to have an efficient one-level copy. Description of the problem -------------------------- If one wants to have an efficient one-level search operation, the immediate subordinates of the base object must not be distributed in different DSAs or the DSA which holds the base object must hold a copy of the immediate subordinate entries. One implementation could not hold such copies. Cause of the problem -------------------- This is due to the internal knowledge organization of the implementation which considers that if it holds a copy of an entry it holds a copy of the complete subtree whose root is the copied entry. For instance, if the DSA responsible for C=FR held a copy of all the immediate subordinates of C=FR, this implementation would consider that it held a copy of the whole C=FR subtree which is impossible in practice. This implementation has been modified to be able to handle "one-level" copies : a DSA manager can register copies of the immediate subordinates of an entry and the DSA will consider that it only holds a copy of the subordinate entries and not the corresponding whole subtree. 5.4 Copies, general considerations ---------------------------------- None of the 3 implementations involved in the project has implemented all the mechanisms required to be able to register and manage a complete copy of an entry in any context : - One has implemented RFC 1276 - Another provides only * one-level local copies * whole subtree copy - The last one * local copies It would have been a heavy task and since the standard does not specify a replication protocol, the benefit would have been very low compared to the investment. Moreover the replication mechanism is not the only element lacking in the standard : - As we wrote above, the copy of an entry consists not only of the data of the entry (attributes) but also of the subordinate knowledge associated with it. Since the standard does not specify the representation of this knowledge, each product has its own representation which is not compatible with the others. The knowledge is not the only information whose representation has not been specified, it is the same for the access control information. In a heterogeneous environment, this makes very difficult to handle real copies, and prevent any replication mechanism from being used. - The standard does not make it possible : * to specify in a reference that it points to an original or copied entry * to return a reference pointing to the original entry and one or more references pointing to copies. - The operation resolution is described irrespective of the status (original / copy) of an entry The 1993 standard should fix these short comings. Given the state of the standard, and if we want to be realistic, a user can demand from an X.500-88 implementation : - the "one-level" copy to have an efficient one-level search operation - the "local" copy of subtrees which would be used at the bottom of the DIT in an organization to enhance the quality of service (response time / reliability) This is now the case for the three implementations involved in this project. 6. SEARCH / INDEXED ATTRIBUTES ============================== Introduction ------------ The X.500 search operation is based on filters using the values of the entries attributes. In order to enhance the performance of the search operation, implementations index attributes of the entries. In order to find an entry, directory clients use the one-level search to explore the top of the DIT and end with the whole-subtree search when they consider that they are deep enough in the DIT for the whole-subtree search to be used. Description of the problem -------------------------- DIT : | entry 1 | ----------------------------- | .... | .... | entry 2.1 entry 2.i entry 2.n Entries 2.i are leaf objects In one implementation, a one-level search, baseObject = entry 1 was much slower than a whole-subtree search. Cause of the problem -------------------- This implementation only used the attributes index tables with the whole-subtree search. It has been modified to use the index tables for one-level searches when this is likely to be faster, the DSA uses a heuristic to decide on the strategy. 7. JUST ONE COMMENT ON LEGAL ISSUES =================================== This section is not aimed at covering the legal issue, we just want to make one comment regarding the implementation features. Some countries already have strict legislation regarding directory services applied to personal data. The European legislation will be harmonized. From what we have seen so far, we can already forsee that DSAs will have to be able to forbid specific operations. We can already mention : - search which involves an attribute that has been declared "not searchable" from the legal point of view. [ for instance, each French person has a unique identifier delivered by the social services. It is "not searchable" except by a few services which have governamental authorization ] - list operations aimed at building listings The implementation must provide the necessary functions to allow DSA managers to configure their DSAs so as to reject these operations. For instance : - a list of not searchable attributes - a parameter which determines the maximum number of entries that a DSA can return in a result. must be available. This is not always the case. 8. MISCELLANEOUS BUGS ===================== The problems mentioned below are bugs rather than problems resulting from difficulties in interpreting or implementing the standard. This is why we will not go into detail. 8.1 BaseObject / alias ---------------------- The base object of an operation must never be modified. One implementation modified it when an alias was dereferenced. 8.2 The optional targetObject component --------------------------------------- When an operation is chained, if the target object is equal to the base object, it is optional. In this case an implementation does not set it, which is possible, and the implementation which received the operation (which always sets the target object), considered that the target object was empty and applied the operation to the root of the DIT instead of using the value of the base object. 8.3 DUA / Stack of references ----------------------------- When a DUA performs a query, if the DSAs contacted to resolve the baseObject use the referral mode, the DUA may have to send the query several times, each time it will get one (or more) reference, as the base object is resolved progressively. One DUA could not send the operation more than twice , the third time it broke the base object because of an internal memory error. 8.4 The dontusecopy option ----------------------------- Although the dontusecopy parameter was set, one implementation returned a copy instead of the original entry. 8.5 Wrong DN ------------ In a specific case one implementation broke a DN by doubling one RDN. 8.6 Incorrect Trace ------------------- One implementation did not trace properly when a reference was returned : it did not take into account the part of the name resolution made by the DSA which returned the reference. The protocol data unit may become inconsistent : the target object was resolved but according to the trace information nobody had done it. This could mislead loop detection algorithms and prevents DSAs from detecting loops. 8.7 Merging Results ------------------- When a DSA performs an operation, it may distribute it between several DSAs which will return a result. The DSA which distributed the operation must merge the results into a final result that it will return to the originator. Two problems were identified : - In some cases, when it receives a "Service Error, Invalid Reference", one implementation returned an empty result with a continuation reference pointing to the DSA which returned the service error. It should not do that but return an error to the originator. - When it receives a result with an empty PartialOutcomeQualifier, which means that the result is complete, an implementation sets the limitProblem field, making the result partial. 8.8 Reference pointing to itself -------------------------------- One implementation cannot follow a reference pointing to itself. This is due to the internal structure of the product and has serious consequences, specially if the DSA is a subordinate of a DSA which uses the referral mode. 8.9 Filters ----------- One implementation did not take into account filter items of a filter associated with a search operation if there were more than 3 filter items and if the filter items applied to indexed attributes 9. CONCLUSION =============== Once more we must conclude that the name resolution and the operation distribution are crucial issues. At the beginning of this project the interworking level was very low, at least two thirds of the reports are related to these issues. Much work has been done by the products suppliers and very significant progress has been made. If a few problems still remain when the knowledge models of the two implementations are very different, the quality of the implementations regarding these issues is now sufficient to provide a service in a heterogeneous context. Given the state of the X.500-88 standard, one cannot expect to really use full copies in a heterogeneous environment. Products may use proprietary mechanism and all have strong limitations. Interworking problems may happen if users are not aware of the limitations of their products and do not take them into account when they configure their DSAs and organize their parts of the DIT. We encourage users to ask their product supplier for an accurate description of the copy facility. The quality of the directory client software must be improved in three fields : - it should be possible to configure them so that they follow or not the references according to the context - they must use and update the operationProgress components to avoid loops as much as possible - their loop detection algorithms must be improved