wafsamba: use additional xml catalog file (bug #9512)
[Samba/bb.git] / source4 / ldap_server / devdocs / ldapext-ldapv3-vlv-04.txt
blobe7bb99ef8ad6b299758d18e43600bb9baab6cf7f
2 INTERNET-DRAFT                                   David Boreham, Netscape
3                                                  Jim Sermersheim, Novell
4                                                 Anoop Anantha, Microsoft
5                                                Michael Armijo, Microsoft
6 ldapext Working Group                                      6 April, 2000
9      LDAP Extensions for Scrolling View Browsing of Search Results
11                   draft-ietf-ldapext-ldapv3-vlv-04.txt
12                 This document expires on 5 October 2000
14 1.  Status of this Memo
16 This document is an Internet-Draft and is in full conformance  with  all
17 provisions  of Section 10 of RFC2026.  Internet-Drafts are working docu-
18 ments of the Internet Engineering Task Force (IETF), its areas, and  its
19 working  groups.   Note  that  other  groups may also distribute working
20 documents as Internet-Drafts.
22 Internet-Drafts are draft documents valid for a maximum  of  six  months
23 and  may  be  updated,  replaced, or obsoleted by other documents at any
24 time.  It is inappropriate to use Internet- Drafts as reference material
25 or to cite them other than as "work in progress."
27 The   list   of   current   Internet-Drafts   can   be    accessed    at
28 http://www.ietf.org/ietf/1id-abstracts.txt
30 The list  of  Internet-Draft  Shadow  Directories  can  be  accessed  at
31 http://www.ietf.org/shadow.html.
33 2.  Abstract
35 This document describes a Virtual List View control  extension  for  the
36 LDAP  Search  operation.  This control is designed to allow the "virtual
37 list box" feature, common in existing  commercial  e-mail  address  book
38 applications, to be supported efficiently by LDAP servers. LDAP servers'
39 inability to support this client feature is a significant impediment  to
40 LDAP replacing proprietary protocols in commercial e-mail systems.
42 The control allows a client to specify that the  server  return,  for  a
43 given  LDAP search with associated sort keys, a contiguous subset of the
44 search result set. This subset is specified in terms of offsets into the
45 ordered list, or in terms of a greater than or equal comparison value.
47 3.  Background
49 A Virtual List is a graphical user interface  technique  employed  where
53 Boreham et al                                                   [Page 1]
59 RFC DRAFT                                                     April 2000
62 ordered lists containing a large number of entries need to be displayed.
63 A window containing a small number of visible list entries is drawn. The
64 visible  portion of the list may be relocated to different points within
65 the list by means of user input. This input  can  be  to  a  scroll  bar
66 slider; from cursor keys; from page up/down keys; from alphanumeric keys
67 for "typedown".  The user is given the impression that they  may  browse
68 the  complete  list  at  will,  even  though  it may contain millions of
69 entries. It is the fact  that  the  complete  list  contents  are  never
70 required  at  any one time that characterizes Virtual List View.  Rather
71 than fetch the complete list from wherever it is stored (typically  from
72 disk  or  a  remote  server), only that information which is required to
73 display the part of the list currently in view is fetched.  The  subject
74 of  this  document is the interaction between client and server required
75 to implement this functionality in the context of  the  results  from  a
76 sorted LDAP search request.
78 For example, suppose an e-mail address book application displays a  list
79 view  onto  the  list  containing the names of all the holders of e-mail
80 accounts at a large  university.  The  list  is  sorted  alphabetically.
81 While  there  may  be  tens  of  thousands  of entries in this list, the
82 address book list view displays only 20 such accounts at any  one  time.
83 The  list has an accompanying scroll bar and text input window for type-
84 down.  When first displayed, the list view shows the first 20 entries in
85 the  list,  and  the  scroll  bar slider is positioned at the top of its
86 range. Should the user drag the slider to the bottom of its  range,  the
87 displayed  contents  of the list view should be updated to show the last
88 20 entries in the list. Similarly, if the slider is positioned somewhere
89 in  the  middle  of  its travel, the displayed contents of the list view
90 should be updated to contain the 20 entries  located  at  that  relative
91 position  within the complete list.  Starting from any display point, if
92 the user uses the cursor keys or clicks on the  scroll  bar  to  request
93 that  the  list  be scrolled up or down by one entry, the displayed con-
94 tents should be updated to reflect this. Similarly the  list  should  be
95 displayed  correctly  when  the  user requests a page scroll up or down.
96 Finally, when the user types characters in  the  type-down  window,  the
97 displayed  contents of the list should "jump" or "seek" to the appropri-
98 ate point within the list.  For example, if  the  user  types  "B",  the
99 displayed  list could center around the first user with a name beginning
100 with the letter "B".  When this happens, the scroll  bar  slider  should
101 also be updated to reflect the new relative location within the list.
103 This document defines a request control which extends  the  LDAP  search
104 operation.  Always  used  in  conjunction  with  the server side sorting
105 control[SSS], this allows a client  to  retrieve  selected  portions  of
106 large  search result set in a fashion suitable for the implementation of
107 a virtual list view.
109 The key words "MUST", "SHOULD", and "MAY" used in this document  are  to
113 Boreham et al                                                   [Page 2]
119 RFC DRAFT                                                     April 2000
122 be interpreted as described in [Bradner97].
124 4.  Client-Server Interaction
126 The Virtual List View control extends a regular  LDAP  Search  operation
127 which must also include a server-side sorting control[SSS].  Rather than
128 returning the complete set of  appropriate  SearchResultEntry  messages,
129 the server is instructed to return a contiguous subset of those entries,
130 taken from the sorted result set, centered around  a  particular  target
131 entry. Henceforth, in the interests of brevity, the sorted search result
132 set will be referred to as "the list".
134 The sort control MAY  contain  any  sort  specification  valid  for  the
135 server.  The  attributeType field in the first SortKeyList sequence ele-
136 ment has special significance for "typedown".
138 The desired target entry, and the number of entries to be returned  both
139 before,  and after, that target entry in the list, are determined by the
140 client's VirtualListViewRequest control.
142 When the server returns the set of entries to the client, it attaches  a
143 VirtualListViewResponse  control  to  the SearchResultDone message.  The
144 server returns in this control: its current estimate for the  list  con-
145 tent  count,  the  location  within the list corresponding to the target
146 entry, and any error codes.
148 The target entry is specified in the VirtualListViewRequest  control  by
149 one  of  two methods. The first method is for the client to indicate the
150 target entry's offset within the list.  The second way is for the client
151 to  supply  an  attribute assertion value. The value is compared against
152 the values of the attribute specified as the primary  sort  key  in  the
153 sort  control  attached  to the search operation.  The first sort key in
154 the SortKeyList is the primary sort key.  The target entry is the  first
155 entry  in  the  list with value greater than or equal to (in the primary
156 sort order), the presented value.  The  order  is  determined  by  rules
157 defined  in  [SSS].   Selection  of  the  target  entry by this means is
158 designed to implement "typedown".  Note that  it  is  possible  that  no
159 entry  satisfies  these  conditions,  in  which  case there is no target
160 entry. This condition is indicated by the server returning  the  special
161 value contentCount + 1 in the target position field.
163 Because the server may not have an accurate estimate of  the  number  of
164 entries in the list, and to take account of cases where the list size is
165 changing during the time the user browses  the  list,  and  because  the
166 client  needs  a  way  to indicate specific list targets "beginning" and
167 "end", offsets within the list are transmitted between client and server
168 as  ratios---offset  to content count. The server sends its latest esti-
169 mate as to the number of entries in the  list  (content  count)  to  the
173 Boreham et al                                                   [Page 3]
179 RFC DRAFT                                                     April 2000
182 client  in  every  response control.  The client sends its assumed value
183 for the content count in every request control.  The server examines the
184 content  count  and  offsets  presented  by  the client and computes the
185 corresponding offsets within the list, based on its own idea of the con-
186 tent count.
188      Si = Sc * (Ci / Cc)
190      Where:
191      Si is the actual list offset used by the server
192      Sc is the server's estimate for content count
193      Ci is the client's submitted offset
194      Cc is the client's submitted content count
195      The result is rounded to the nearest integer.
197 If the content count is stable, and the client returns to the server the
198 content  count most recently received, Cc = Sc and the offsets transmit-
199 ted become the actual server list offsets.
201 The following special cases are allowed:  a  client  sending  a  content
202 count  of zero (Cc = 0) means "client has no idea what the content count
203 is, server MUST use its own content  count  estimate  in  place  of  the
204 client's".  An offset value of one (Ci = 1) always means that the target
205 is the first entry in the list. Client specifying an offset which equals
206 the  content count specified in the same request control (Ci = Cc) means
207 that the target is the last entry in the list.  Ci may only  equal  zero
208 when Cc is also zero. This signifies the last entry in the list.
210 Because the server always returns contentCount and  targetPosition,  the
211 client  can always determine which of the returned entries is the target
212 entry. Where the number of entries returned is the same  as  the  number
213 requested,  the  client  is able to identify the target by simple arith-
214 metic. Where the number of entries returned  is  not  the  same  as  the
215 number  requested  (because the requested range crosses the beginning or
216 end of the list, or both), the client must use the target  position  and
217 content  count  values  returned  by  the  server to identify the target
218 entry. For example, suppose that 10 entries before and 10 after the tar-
219 get  were  requested, but the server returns 13 entries, a content count
220 of 100 and a target position of 3. The client  can  determine  that  the
221 first entry must be entry number 1 in the list, therefore the 13 entries
222 returned are the first 13 entries in the list, and  the  target  is  the
223 third one.
225 A server-generated context identifier MAY be  returned  to  clients.   A
226 client  receiving  a  context identifier SHOULD return it unchanged in a
227 subsequent request which relates to the same list.  The purpose of  this
228 interaction  is  to enhance the performance and effectiveness of servers
229 which employ approximate positioning.
233 Boreham et al                                                   [Page 4]
239 RFC DRAFT                                                     April 2000
242 5.  The Controls
244 Support for the virtual list view control extension is indicated by  the
245 presence  of  the  OID "2.16.840.1.113730.3.4.9" in the supportedControl
246 attribute of a server's root DSE.
248 5.1.  Request Control
250 This control is included in the SearchRequest message  as  part  of  the
251 controls  field  of  the  LDAPMessage,  as  defined in Section 4.1.12 of
252 [LDAPv3].  The controlType is set to "2.16.840.1.113730.3.4.9". The cri-
253 ticality   SHOULD be set to TRUE. If this control is included in a Sear-
254 chRequest message, a Server Side Sorting request control [SSS] MUST also
255 be  present  in  the  message. The controlValue is an OCTET STRING whose
256 value is the BER-encoding of the following SEQUENCE:
258           VirtualListViewRequest ::= SEQUENCE {
259                   beforeCount    INTEGER (0..maxInt),
260                   afterCount     INTEGER (0..maxInt),
261                   CHOICE {
262                           byoffset [0] SEQUENCE {
263                            offset          INTEGER (0 .. maxInt),
264                            contentCount    INTEGER (0 .. maxInt) },
265                           greaterThanOrEqual [1] AssertionValue },
266                   contextID     OCTET STRING OPTIONAL }
268 beforeCount indicates how many  entries  before  the  target  entry  the
269 client  wants  the  server  to  send. afterCount indicates the number of
270 entries after the target entry the client  wants  the  server  to  send.
271 offset and contentCount identify the target entry as detailed in section
272 4.  greaterThanOrEqual  is  an  attribute  assertion  value  defined  in
273 [LDAPv3].  If  present, the value supplied in greaterThanOrEqual is used
274 to determine the target entry by  comparison  with  the  values  of  the
275 attribute  specified as the primary sort key. The first list entry who's
276 value is no less than (less than or equal to  when  the  sort  order  is
277 reversed)  the  supplied value is the target entry. If present, the con-
278 textID field contains the value of the most recently received  contextID
279 field  from  a  VirtualListViewResponse control. The type AssertionValue
280 and value maxInt are defined in  [LDAPv3].   contextID  values  have  no
281 validity outwith the connection on which they were received.  That is, a
282 client should not submit a contextID which it received from another con-
283 nection, a connection now closed, or a different server.
286 5.2.  Response Control
288 This control is included in the SearchResultDone message as part of  the
289 controls   field  of the  LDAPMessage, as  defined in Section  4.1.12 of
293 Boreham et al                                                   [Page 5]
299 RFC DRAFT                                                     April 2000
302 [LDAPv3].
304 The controlType is set to "2.16.840.1.113730.3.4.10". The criticality is
305 FALSE (MAY be absent).  The controlValue is an OCTET STRING, whose value
306 is the BER encoding of a value of the following SEQUENCE:
308      VirtualListViewResponse ::= SEQUENCE {
309              targetPosition    INTEGER (0 .. maxInt),
310              contentCount     INTEGER (0 .. maxInt),
311              virtualListViewResult ENUMERATED {
312              success (0),
313              operationsError (1),
314              unwillingToPerform (53),
315              insufficientAccessRights (50),
316              busy (51),
317              timeLimitExceeded (3),
318              adminLimitExceeded (11),
319              sortControlMissing (60),
320              offsetRangeError (61),
321              other (80) },
322              contextID     OCTET STRING OPTIONAL }
324 targetPosition gives the list offset for the target entry.  contentCount
325 gives  the  server's  estimate  of  the current number of entries in the
326 list.  Together these give sufficient  information  for  the  client  to
327 update  a  list box slider position to match the newly retrieved entries
328 and identify the target entry. The contentCount value returned SHOULD be
329 used  in  a  subsequent  VirtualListViewRequest control.  contextID is a
330 server-defined octet string. If present, the contents of  the  contextID
331 field  SHOULD be returned to the server by a client in a subsequent Vir-
332 tualListViewRequest control.
334 The virtualListViewResult codes which  are  common  to  the  LDAP  sear-
335 chResponse  (adminLimitExceeded,  timeLimitExceeded, busy, operationsEr-
336 ror, unwillingToPerform, insufficientAccessRights) have the  same  mean-
337 ings  as  defined  in [LDAPv3], but they pertain specifically to the VLV
338 operation.  For example, the server could exceed an administration limit
339 processing  a  SearchRequest with a VirtualListViewRequest control. How-
340 ever, the same administration limit would not  be  exceeded  should  the
341 same  SearchRequest  be submitted by the client without the VirtualList-
342 ViewRequest control.  In this case, the client  can  determine  that  an
343 administration limit has been exceeded in servicing the VLV request, and
344 can if it chooses resubmit the SearchRequest  without  the  VirtualList-
345 ViewRequest control.
347 insufficientAccessRights means that the server denied the client permis-
348 sion to perform the VLV operation.
353 Boreham et al                                                   [Page 6]
359 RFC DRAFT                                                     April 2000
362 If the server determines that the results of the search presented exceed
363 the  range  provided  by  the  32-bit  offset  values,  it  MUST  return
364 offsetRangeError.
366 6.  Protocol Example
368 Here we walk through the client-server interaction for a  specific  vir-
369 tual list view example:  The task is to display a list of all 78564 peo-
370 ple in the US company "Ace Industry".  This will be done by  creating  a
371 graphical  user  interface  object  to display the list contents, and by
372 repeatedly sending different versions of  the  same  virtual  list  view
373 search  request  to the server. The list view displays 20 entries on the
374 screen at a time.
376 We form a search with baseDN "o=Ace Industry, c=us"; search  scope  sub-
377 tree;  filter "objectClass=inetOrgPerson". We attach a server sort order
378 control to the search, specifying ascending sort on attribute  "cn".  To
379 this  base  search,  we  attach a virtual list view request control with
380 contents determined by the user activity and  send  the  search  to  the
381 server.  We  display the results from each search in the list window and
382 update the slider position.
384 When the list view is first displayed, we want to  initialize  the  con-
385 tents showing the beginning of the list. Therefore, we set beforeCount =
386 0, afterCount = 19, contentCount = 0, offset = 1 and send the request to
387 the  server.  The  server duly returns the first 20 entries in the list,
388 plus the content count = 78564 and  targetPosition  =  1.  We  therefore
389 leave  the  scroll  bar  slider  at its current location (the top of its
390 range).
392 Say that next the user drags the scroll bar slider down to the bottom of
393 its  range.   We now wish to display the last 20 entries in the list, so
394 we set beforeCount = 19, afterCount = 0, contentCount = 78564, offset  =
395 78564 and send the request to the server. The server returns the last 20
396 entries in the list, plus the content count = 78564 and targetPosition =
397 78564.
399 Next the user presses a page up key. Our page size  is  20,  so  we  set
400 beforeCount  =  0,  afterCount  =  19,  contentCount  =  78564, offset =
401 78564-19-20 and send the request to the server. The server  returns  the
402 preceding  20  entries  in  the list, plus the content count = 78564 and
403 targetPosition = 78525.
405 Now the user grabs the scroll bar slider and drags it to 68% of the  way
406 down its travel. 68% of 78564 is 53424 so we set beforeCount = 9, after-
407 Count = 10, contentCount = 78564, offset = 53424 and send the request to
408 the  server.  The  server  returns the preceding 20 entries in the list,
409 plus the content count = 78564 and targetPosition = 53424.
413 Boreham et al                                                   [Page 7]
419 RFC DRAFT                                                     April 2000
422 Lastly, the user types the letter "B". We set beforeCount  =  9,  after-
423 Count  =  10  and  greaterThanOrEqual  = "B". The server finds the first
424 entry in the list not less  than  "B",  let's  say  "Babs  Jensen",  and
425 returns the nine preceding entries, the target entry, and the proceeding
426 10 entries.  The server returns content count = 78564 and targetPosition
427 =  5234  and so the client updates its scroll bar slider to 6.7% of full
428 scale.
430 7.  Notes for Implementers
432 While the feature is expected  to  be  generally  useful  for  arbitrary
433 search  and  sort  specifications, it is specifically designed for those
434 cases where the result set is very large.  The intention  is  that  this
435 feature be implemented efficiently by means of pre-computed indices per-
436 taining to a set of specific cases. For example, an offset  relating  to
437 "all  the  employees in the local organization, sorted by surname" would
438 be a common case.
440 The intention for client software is that the feature should fit  easily
441 with  the  host  platform's  graphical user interface facilities for the
442 display of scrolling lists. Thus the task  of  the  client  implementers
443 should  be  one of reformatting up the requests for information received
444 from the list view code to match the format of  the  virtual  list  view
445 request and response controls.
447 Client implementers should note that any offset value  returned  by  the
448 server  may  be  approximate. Do not design clients > which only operate
449 correctly when offsets are exact.
451 Server implementers using indexing technology which features approximate
452 positioning  should  consider  returning context identifiers to clients.
453 The use of a context identifier will allow  the  server  to  distinguish
454 between client requests which relate to different displayed lists on the
455 client. Consequently the server can decide more intelligently whether to
456 reposition an existing database cursor accurately to within a short dis-
457 tance of its current position, or to reposition to an approximate  posi-
458 tion. Thus the client will see precise offsets for "short" repositioning
459 (e.g. paging up or down), but approximate offsets for a  "long"  reposi-
460 tion (e.g. a slider movement).
462 Server implementers are free to return  status  code  unwillingToPerform
463 should  their  server  be  unable  to service any particular VLV search.
464 This might be because the resolution of the  search  is  computationally
465 infeasible,  or  because excessive server resources would be required to
466 service the search.
468 Client implementers should note that this control is only defined  on  a
469 client  interaction  with a single server. If a server returns referrals
473 Boreham et al                                                   [Page 8]
479 RFC DRAFT                                                     April 2000
482 as a part of its response to the search request, the client is responsi-
483 ble  for  deciding when and how to apply this control to the referred-to
484 servers, and how to collate the results from multiple servers.
487 8.  Relationship to "Simple Paged Results"
489 These controls are designed to support the virtual list view, which  has
490 proved  hard  to  implement  with  the  Simple  Paged  Results mechanism
491 [SPaged]. However, the controls described  here  support  any  operation
492 possible with the Simple Paged Results mechanism. The two mechanisms are
493 not complementary, rather one has a superset of  the  other's  features.
494 One  area where the mechanism presented here is not a strict superset of
495 the Simple Paged Results scheme is that here we require a sort order  to
496 be specified. No such requirement is made for paged results.
499 9.  Security Considerations
501 Server implementers may wish to consider whether  clients  are  able  to
502 consume  excessive  server  resources  in requesting virtual list opera-
503 tions. Access control to the feature itself; configuration options  lim-
504 iting  the  feature's  use  to certain predetermined search base DNs and
505 filters; throttling mechanisms designed to limit  the  ability  for  one
506 client to soak up server resources, may be appropriate.
508 Consideration should be given as to whether a client  will  be  able  to
509 retrieve  the complete contents, or a significant subset of the complete
510 contents of the directory using this feature. This may be undesirable in
511 some  circumstances and consequently it may be necessary to enforce some
512 access control.
514 Clients can, using this control, determine how  many  entries  are  con-
515 tained  within  a  portion  of  the  DIT. This may constitute a security
516 hazard. Again, access controls may be appropriate.
518 Server implementers SHOULD exercise caution concerning  the  content  of
519 the  contextID.   Should the contextID contain internal server state, it
520 may be possible for a malicious client to use that information  to  gain
521 unauthorized access to information.
523 10.  Acknowledgements
525 Chris Weider of Microsoft co-authored a previous version of  this  docu-
526 ment.
533 Boreham et al                                                   [Page 9]
539 RFC DRAFT                                                     April 2000
542 11.  References
544 [LDAPv3]
545      Wahl, M, S. Kille and T. Howes, "Lightweight Directory Access  Pro-
546      tocol (v3)", Internet Standard, December, 1997. RFC2251.
548 [SPaged]
549      Weider, C, A. Herron, A.  Anantha,  and  T.  Howes,  "LDAP  Control
550      Extension  for  Simple   Paged   Results   Manipulation", September
551      1999. RFC2696
553 [SSS]Wahl, M, A. Herron and T. Howes, "LDAP Control Extension for Server
554      Side  Sorting  of  Search  Results",  Internet  Draft, April, 1999.
555      Available as draft-ietf-asid-ldapv3-sorting-02.txt.
557 [Bradner97]
558      Bradner, S., "Key Words for use in  RFCs  to  Indicate  Requirement
559      Levels", BCP 14, RFC 2119, March 1997.
561 12.  Authors' Addresses
563    David Boreham
564    iPlanet e-commerce solutions
565    501 E. Middlefield Road
566    Mountain View, CA 94043, USA
567    +1 650 937-5206
568    dboreham@netscape.com
570    Jim Sermersheim
571    Novell
572    122 East 1700 South
573    Provo, Utah 84606, USA
574    jimse@novell.com
576    Anoop Anantha
577    Microsoft Corp.
578    1 Microsoft Way
579    Redmond, WA 98052, USA
580    +1 425 882-8080
581    anoopa@microsoft.com
583    Michael Armijo
584    Microsoft Corp.
585    1 Microsoft Way
586    Redmond, WA 98052, USA
587    +1 425 882-8080
588    micharm@microsoft.com
589    This document expires on 5 October 2000
593 Boreham et al                                                  [Page 10]
599 RFC DRAFT                                                     April 2000
653 Boreham et al                                                  [Page 11]