Re: LDAP

pays@faugeres.inria.fr Tue, 01 June 1993 23:46 UTC

Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa18691; 1 Jun 93 19:46 EDT
Received: from CNRI.RESTON.VA.US by IETF.CNRI.Reston.VA.US id aa18687; 1 Jun 93 19:46 EDT
Received: from haig.cs.ucl.ac.uk by CNRI.Reston.VA.US id aa01296; 1 Jun 93 19:46 EDT
Received: from bells.cs.ucl.ac.uk by haig.cs.ucl.ac.uk with local SMTP id <g.10797-0@haig.cs.ucl.ac.uk>; Tue, 1 Jun 1993 23:27:19 +0100
Received: from faugeres.inria.fr by bells.cs.ucl.ac.uk with Internet SMTP id <g.13165-0@bells.cs.ucl.ac.uk>; Tue, 1 Jun 1993 23:27:12 +0100
X400-Received: by /PRMD=inria/ADMD=atlas/C=fr/; Relayed; 02 Jun 93 00:26:43+0200
Date: 02 Jun 93 00:26:43+0200
Sender: ietf-archive-request@IETF.CNRI.Reston.VA.US
From: pays@faugeres.inria.fr
To: pays@faugeres.inria.fr, tim@terminator.rs.itd.umich.edu
Subject: Re: LDAP
cc: osi-ds@cs.ucl.ac.uk
Message-ID: <738973603.7893.0-faugeres.inria.fr*@MHS>

> 
> PAP, can you post a more detailed description of your algorithm to
> the list, and explain in more detail why the change is needed?   -- Tim
> 

It's very late here, but let me try in a few words
(il it is unclear please drop a note and questions):

note: it is not my algorithm, if you want to put a name on it, it
could be seen  as the algorithm prposed by E3X for the
DUAs they are proposing with Pizarro. However this has been discussed
through email with plenty of people including in particular
Paul Barker from UCL.

The idea when a directory client has to look-up for an entry from
a set of values provided by the user to start with a read
(or search base-object) of the most "probable" DN that can be
constructed with the provided values.
   either a result is returned => OK look-up is over
   either a name error is returned which indicates
	how many RDN were matched.
	-> this enable to start the search based algorithm from
	this start point (instead of starting from the root
	as in what Steve name the 2nd generation DUA)

In many many cases this will enable to start the search
a few levels lower in the tree thus avoiding either performance
problems or administrative limits.


Let me give you a concrete example

when presented with the following
A:   FR INRIA DMI PAP
B:   FR INRIA siege PAP
C:   FR INRIA DMI "Paul-Andre Pays"
whereas my DN is : <C=fr; O=inria; OU=DMI; CN="Paul-Andre Pays";>

a DE type algorithm (from UCL/Paradise) 
  will do something like (simplified)

  for A:

     a search-one-level, base <>, filter C=FR
     a search-one-level, base C=FR; filter O=inria;
     a search-one-level, base O=inria; filter OU=dmi;
     from here <C=FR;O=inria;OU=DMI> look for an entry with PAP as CN or S

  for B: 

     a search-one-level, base <>, filter C=FR
     a search-one-level, base C=FR; filter O=inria;
     a search-one-level, base O=inria; filter OU=siege;
     a search-one-level, base O=inria; filter OU=siege;
	but substring or approximate match
     error thus
     from here <C=FR;O=inria> look for an entry with PAP as CN or S

  for C:

     a search-one-level, base <>, filter C=FR
     a search-one-level, base C=FR; filter O=inria;
     a search-one-level, base O=inria; filter OU=dmi;
     from here <C=FR;O=inria;OU=DMI> look for an entry with 
	"Paul-Andre Pays" as CN or S


whereas

an AFRO (E3X name for their algorithm) will perform

  for A:

     a read, base-object= <C=FR; O=inria; OU=DMI; CN=PAP>
     -> as name error is returned with the info that <C=FR; O=inria; OU=DMI>
      is OK, then 
     from here <C=FR;O=inria;OU=DMI> look for an entry with PAP as CN or S

  for B:

     a read, base-object= <C=FR; O=inria; OU=siege; CN=PAP>
     -> as name error is returned with the info that <C=FR; O=inria>
      is OK, then 
     from here <C=FR;O=inria> look for an entry with PAP as CN or S
      (why not by a search-one-level sequence as for DE but starting
      lower in the tree)

  for C:

     a read, base-object= <C=FR; O=inria; OU=DMI; CN="Paul-Andre Pays">
      => result obtained in one single operation

-----------------------------

This second kind of alorithm will be less costly than the DE type one
(except if the first token is not matched, in which case the AFRO
type algorithm will cost one additional read compared with the
DE type algorithm), and has the advantages in my mind of
being usable and efficient for simple look-ups as well
as for UFN type look-ups.

Moreover I imagine that the odds than someone looking for Tim Howes
entry are high that he/she will know that the first token is US,
and are not zero than he/she will provide the "University of Michigan"
second token.

To sum it up 
  once one algorithm has to really search, then the 2nd gneration 
    algorithm with a sequence of one-level-search is indeed
    the best solution
  BUT it is important and efficient to try to determine the search
    start-point as low in the DIT as possible by means of a READ
    (or nearly equivalent search base object) through the name error
    indication returned in case the read is not succesfull.
    performance gain: obvious as soon as a few tokens are correct
    important: it enables managers of DSA at national level
	or at Org level to enforce a restriction of searches
	at these levels (for whatever reason performance or privacy).
	The algorithm will still work as long as the first few
	components of the DN are provided correctly by the requestor
    drawbacks: nearly none  (I am ready to receive opposite opinions)

> 


-- PAP