[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
IETF LDAPEXT Working Group                                  David Watts
INTERNET-DRAFT                                     Data Connection Ltd.
                                                           Steve Orbell
                                                   Data Connection Ltd.
                                                             April 1998


                Efficient Referral Chasing in LDAP Directories
                 <draft-watts-ldapext-x500-referrals-00.txt>



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
<ietf-ldapext@netscape.com>.


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]