IETF LDAPEXT Working Group David Watts INTERNET-DRAFT Data Connection Ltd. Steve Orbell Data Connection Ltd. April 1998 Efficient Referral Chasing in LDAP Directories 1. Status of this Memo This document is an Internet-Draft. Internet-Drafts are working docu- ments of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as ``work in progress.'' To view the entire list of current Internet-Drafts, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). Distribution of this memo is unlimited. Editorial comments should be sent to the authors. Technical discussion should take place on the IETF IETF LDAP Extension Working Group mailing list . 2. Abstract This document defines an extension to the LDAP URL format and a control on a LDAP search operation which, together, permit LDAP clients to chase LDAP referrals in a more efficient and more X.500-like manner. Watts & Orbell IETF LDAPEXT Working Group [Page 1] INTERNET-DRAFT Efficient LDAP Referrals April 1998 3. Contents of this Document The remaining sections in this document are as follows. - Section 4 gives some background on distributed directories and referrals. - Section 5 describes the limitations of LDAP referrals and explains why these limitations are unacceptable. - Sections 6 and 7 formally define the new URL extension and the new search control. - Sections 8 and 9 give the formal rules governing client and server behaviour with respect to the new extension and control. - Sections 10 to 12 cover security, references and authors' addresses. The key words "MUST", "MUST NOT", "SHOULD", and "MAY" used in this document are to be interpreted as described in [BRADNER97]. 4. Background - Distributed Directories and Referrals 4.1 Centralised and Distributed Directories In the LDAP/X.500 model, a directory may be centralised in a single server or distributed over several servers. 4.1.1 Centralised Directories In the centralised model, the single server performs all operations, returning either results or errors. There is no requirement to communicate with other servers, because they are outside the scope of the model. Watts & Orbell IETF LDAPEXT Working Group [Page 2] INTERNET-DRAFT Efficient LDAP Referrals April 1998 4.1.2 Distributed Directories In the distributed model, when a server receives an operation which it cannot satisfy (or can only satisfy partially), it can do one of two things. - It can chain the request to a second server which can satisfy the request. This second server performs the operation and passes the results back to the first server. The first server merges those results with any which have been produced locally or returned from other chained requests, and passes the combined result back to the client. The client has no further work to perform. - It can pass a continuation reference (i.e. a referral) back to the requestor, along with any results which have been produced locally. The client may then use the information in the referral to contact other servers and continue processing the operation. This requires the client, not only to contact the other servers, but also to perform server functions such as merging results, discarding any duplicates, referral loop detection, and managing size and time limits. The latter behaviour is typical of unmanaged directories and of low-end servers which do not implement chaining. The former behaviour is preferable in managed directories. It allows truly lightweight clients to be deployed and avoids the network and processing overhead of clients connecting to, and authenticating with, multiple servers. Watts & Orbell IETF LDAPEXT Working Group [Page 3] INTERNET-DRAFT Efficient LDAP Referrals April 1998 4.2 LDAPv2 LDAPv2 [LDAPv2] defines a simplified version of the X.500 Directory Access Protocol (DAP). It permits access to a directory using a restricted set of ASN.1 encodings, and without requiring an OSI stack. LDAPv2 thus circumvents some of the overhead associated with DAP and allows more lightweight directory access clients to be deployed. Like DAP, LDAPv2 defines abstract operations for accessing a directory. LDAPv2 does not define either: - a chaining mechanism (because LDAP is an access protocol) - a referral mechanism (for simplicity, because LDAP is lightweight). 4.3 The Requirement for Referrals Referrals are required in a distributed directory when the servers are incapable of chaining. Even when servers are capable of chaining, referrals may still be useful. If a server tries to chain to a second server, but the second server is busy or unavailable, the first server should return a referral to the client to indicate that the operation could not be completed. In the case where the server is capable of chaining, the client will not generally chase the returned referrals, since the server will already have tried to contact the referred-to server. The information in the referral may still be of use, for example to: - indicate the partial nature of the results to the human user - chase the referral later (by which time the referred-to server might no longer be unavailable/busy). 4.4 LDAPv3 One of the ways in which LDAPv3 [LDAPv3] extends LDAPv2 is by defining a referral mechanism. Referrals are LDAP URLs, defined in [URL] to contain the following fields. All fields are optional. - name/address/port of the referred-to server - DN of the base object of Search (or other operation) - attributes to be returned from Search - scope of Search (base-object/one-level/whole-subtree) - filter for Search - extensions Watts & Orbell IETF LDAPEXT Working Group [Page 4] INTERNET-DRAFT Efficient LDAP Referrals April 1998 5. Limitations of LDAPv3 Referrals LDAP URLs as defined in [URL] suffer from the following limitations. - They can be inefficient. - They are incompatible with X.500 referrals. 5.1 Inefficient Referrals A common topology for managing a distributed directory is to divide the naming contexts amongst the cooperating servers in a strictly hierarchical manner. Example - Distributed Directory for ACME Corp level 1 c=US | | | level 2 o=ACME | ---------------|---------------- | | | level 3 ou=Sales ou=Marketing ou=Research | | | ... ... ... level 4 2 servers hold the directory for ACME Corp: - server A contains levels 1 and 2 (i.e. US, ACME) - server B contains level 3 (Sales, Marketing, Research) and subordinate levels Servers A and B hold knowledge of the sections of the DIT held by each other. Watts & Orbell IETF LDAPEXT Working Group [Page 5] INTERNET-DRAFT Efficient LDAP Referrals April 1998 If server A is unable to chain to server B, then a LDAPv3 whole-subtree Search from o=ACME,c=US will return: - an entry for ACME (if it matches the filter) - a referral to server B, to search from ou=Sales,o=ACME,c=US - a referral to server B, to search from ou=Marketing,o=ACME,c=US - a referral to server B, to search from ou=Research,o=ACME,c=US Thus when the client chases the referrals to continue the search in server B, it has to chase 3 different referrals, even though they are referrals to the same server at sibling nodes. It would be far more efficient to have a single referral to server B, with semantic "search from all the sibling nodes just below o=ACME,c=US" Chasing three referrals instead of one is not terribly inefficient, but in real-life directory deployments, the number of subordinates at each level may be much larger - perhaps several thousand. 5.2 Incompatibility with X.500 referrals X.500 referrals are defined in X.518 [X518]. In addition to the information contained in a LDAP URL, they contain a field nameResolutionPhase. - nameResolutionPhase 'not completed' indicates that the referral contains the DN of entry from which to continue the search. - nameResolutionPhase 'completed' indicates that the referral contains the DN of PARENT of the entry from which to continue the search. In the ACMECorp example in 5.1, if server A is unable to chain to server B, then it will return: - an entry for ACME (if it matches the filter) - a single referral to server B, to search from all the naming contexts which are immediately subordinate to o=ACME,c=US (i.e. with nameResolutionPhase = 'completed') If this X.500 referral is converted to a LDAP referral ldap://serverb/o=ACME,c=US and the client converts this to a search operation to be passed to server B, then the nameResolutionPhase = 'completed' information will be lost. Watts & Orbell IETF LDAPEXT Working Group [Page 6] INTERNET-DRAFT Efficient LDAP Referrals April 1998 Server B will therefore attempt to continue the search from o=ACME,c=US (rather than each of its subordinates). Server B, when it follows the Find DSE procedure in [X518] section 18, will either chain or refer back to server A. This will then lead to a referral loop between servers A and B. Note that this problem cannot be overcome by 'munging' the X.500 referral when it comes to convert it to LDAP. The information which would be required to produce usable LDAP referrals: ldap://serverb/ou=Sales,o=ACME,c=US ldap://serverb/ou=Marketing,o=ACME,c=US ldap://serverb/ou=Research,o=ACME,c=US (i.e. the RDNs) is not contained in the X.500 referral. This information may not even be available to the server which is converting from the X.500 referral to the LDAP referral. - The X.500 referral may have been produced by a different server. - The knowledge of server B may be contained in an NSSR, rather than in 3 subordinate references. Thus LDAP referrals are incompatible with X.500 referrals. This means that LDAPv3 cannot be mapped to a strict subset of the X.500 Directory Abstract Service, and thus fails to meet one of its principal design goals ([LDAPv3] section 3.1). 5.3 Summary LDAP referrals are inefficient in certain distributed configurations, and are incompatible with X.500 referrals. These limitations are related because, as shown above, the extra information contained in X.500 referrals overcomes the inefficiency inherent in LDAP referrals. Watts & Orbell IETF LDAPEXT Working Group [Page 7] INTERNET-DRAFT Efficient LDAP Referrals April 1998 6. The subcontexts URL Extension This section defines a LDAP URL extension. The extension indicates that the URL does not refer to the entry named in the URL, but instead refers to all the context prefix entries which are immediately subordinate to the entry named in the URL. The extension type is "subcontexts". The extension value is absent. The extension is critical. eg: ldap://serverb/o=ACME,c=US????!subcontexts The subcontexts URL extension is returned within a LDAP URL which is part of a SearchResultReference, as defined in section 4.5.2 of [LDAPv3]. 7. The Subordinate Contexts Control A client may specify the following control when issuing a search request. This control is included in the searchRequest message as part of the controls field of the LDAPMessage, as defined in Section 4.1.12 of [LDAPv3]. The control type is 1.2.826.0.1.1578918.2.1.2.1. The control SHOULD be marked as critical. There is no value - the controlValue field is absent. The ASN.1 production for Control defined in [LDAPv3] is: Control ::= SEQUENCE { controlType LDAPOID, criticality BOOLEAN DEFAULT FALSE, controlValue OCTET STRING OPTIONAL } The Subordinate Contexts Control is therefore encoded as follows: 3020 041B 312E322E3832362E302E312E313537383931382E322E312E322E31 0101 FF Watts & Orbell IETF LDAPEXT Working Group [Page 8] INTERNET-DRAFT Efficient LDAP Referrals April 1998 8. Client Behaviour The subcontexts URL extension is critical. Therefore, if a client does not support the subcontexts extension, it MUST NOT process the URL. Clients which support the subcontexts extension MAY choose to process the URL or MAY choose not to process it. If the client chooses to process the URL, the search operation which is passed to the referred-to server MUST include the Subordinate Contexts Control. 9. Server Behaviour There are two aspects to the Server behaviour: - Returning the subcontexts URL extension - Processing the Subordinate Contexts Control. 9.1 Returning the subcontexts URL extension If a server is processing a Search and has found the base object, but does not hold the entire search area and is unable to chain, then each of the LDAP URLs which it returns may take one of the following forms. - The DN refers to the entry from which to continue the search, and the subcontexts URL extension is absent. (This is the format defined in [URL].) - The DN refers to the parent of all the context prefix entries from which to continue the search, and the subcontexts URL extension is present. Watts & Orbell IETF LDAPEXT Working Group [Page 9] INTERNET-DRAFT Efficient LDAP Referrals April 1998 The formal rules governing the presence of the subcontexts URL extension are as follows. - The subcontexts URL extension MUST NOT be returned in a URL which is returned from a non-Search operation, or in a URL for a Search operation where the server has been unable to find the base object. i.e. the subcontexts URL extension MUST NOT be present in a URL which is contained in a referral error. - The subcontexts URL extension MAY be returned in a URL for a Search operation where the server has found the base object. i.e. the subcontexts URL extension MAY be returned in a URL which is contained in a SearchResultReference. - If a server is unable to complete a search, and the search needs to be continued at many sibling context prefix nodes, all of which are stored in the same server, then the server SHOULD return a single URL with the subcontexts extension (in preference to many URLs without the subcontexts extension). This allows clients to chase the referrals more efficiently. 9.2 Processing the Subordinate Contexts Control The Subordinate Contexts Control is critical. Therefore, if a server does not support it, it MUST NOT perform the operation, and MUST instead return the resultCode unsupportedCriticalExtension. Servers which support the Subordinate Contexts Control MUST continue the Search from all of the entries which are context prefix subordinates of the baseObject. If there are no context prefix entries which are immediately subordinate to the baseObject, then the server MUST return the result code invalidReference. 10. Security Considerations The server decision to return a referral containing the DN of the parent, rather than the DN of the entry itself, involves disclosing less, rather than more, information to the client. There are therefore no security considerations over and above those involved in the decision to return a LDAP URL as considered in [URL]. Watts & Orbell IETF LDAPEXT Working Group [Page 10] INTERNET-DRAFT Efficient LDAP Referrals April 1998 11. References [BRADNER97] S. Bradner, "Key Words for use in RFCs to Indicate Requirement Lev- els", Internet Draft, draft-bradner-key-words-03.txt, January 1997. [LDAPv2] W . Yeong, T. Howes, S. Kille, "Lightweight Directory Access Protocol", RFC 1777, March, 1995. [LDAPv3] M. Wahl, T. Howes, S. Kille, "Lightweight Directory Access Protocol (v3)", Internet Draft draft-ietf-asid-ldapv3-protocol-09.txt, November, 1997. [URL] T. Howes, "The LDAP URL Format", Internet draft draft-ietf-asid- ldapv3-url-04.txt, August 1997. [X518] ITU-T Rec. X.518, "The Directory: Procedures for Distributed Operation", 1993. 12. Authors' Addresses David Watts Data Connection Ltd. 100 Church Street Enfield Middlesex England EN2 6BQ EMail: djw@datcon.co.uk Steve Orbell Data Connection Ltd. 100 Church Street Enfield Middlesex England EN2 6BQ EMail: so@datcon.co.uk Watts & Orbell IETF LDAPEXT Working Group [Page 11]