2 INTERNET-DRAFT D. Boreham, Bozeman Pass
3 LDAPext Working Group J. Sermersheim, Novell
4 Category: Standards Track A. Anantha, Microsoft
5 <draft-ietf-ldapext-ldapv3-vlv-05.txt> M. Armijo, Microsoft
6 Expires: May 2002 A. Kashi, Microsoft
11 LDAP Extensions for Scrolling View Browsing of Search Results
15 1. Status of this Memo
17 This document is an Internet-Draft and is in full conformance with
18 all provisions of Section 10 of RFC2026.
20 Internet-Drafts are working documents of the Internet Engineering
21 Task Force (IETF), its areas, and its working groups. Note that
22 other groups may also distribute working documents as Internet-
25 Internet-Drafts are draft documents valid for a maximum of six
26 months and may be updated, replaced, or obsoleted by other documents
27 at any time. It is inappropriate to use Internet-Drafts as
28 reference material or to cite them other than as "work in progress."
30 The list of current Internet-Drafts can be accessed at
31 http://www.ietf.org/ietf/1id-abstracts.txt
33 The list of Internet-Draft Shadow Directories can be accessed at
34 http://www.ietf.org/shadow.html.
36 This document is intended to be submitted, after review and
37 revision, as a Standards Track document. Distribution of this memo
38 is unlimited. It is filed as <draft-ietf-ldapext-ldapv3-vlv-
39 05.txt>, and expires May, 2002.
41 Please send comments to the authors.
46 This document describes a Virtual List View control extension for
47 the Lightweight Directory Access Protocol (LDAP) Search operation.
48 This control is designed to allow the "virtual list box" feature,
49 common in existing commercial e-mail address book applications, to
50 be supported efficiently by LDAP servers. LDAP servers' inability to
51 support this client feature is a significant impediment to LDAP
52 replacing proprietary protocols in commercial e-mail systems.
55 Boreham et al Standards Track 1
\f
56 LDAP Extensions for Scrolling View November 2001
57 Browsing of Search Results
59 The control allows a client to specify that the server return, for a
60 given LDAP search with associated sort keys, a contiguous subset of
61 the search result set. This subset is specified in terms of offsets
62 into the ordered list, or in terms of a greater than or equal
65 3. Conventions used in this document
66 The key words ``MUST'', ``MUST NOT'', ``REQUIRED'', ``SHALL'',
67 ``SHALL NOT'', ``SHOULD'', ``SHOULD NOT'', ``RECOMMENDED'', and
68 ``MAY'' in this document are to be interpreted as described in RFC
74 A Virtual List is a graphical user interface technique employed
75 where ordered lists containing a large number of entries need to be
76 displayed. A window containing a small number of visible list
77 entries is drawn. The visible portion of the list may be relocated
78 to different points within the list by means of user input. This
79 input can be to a scroll bar slider; from cursor keys; from page
80 up/down keys; from alphanumeric keys for "typedown". The user is
81 given the impression that they may browse the complete list at will,
82 even though it may contain millions of entries. It is the fact that
83 the complete list contents are never required at any one time that
84 characterizes Virtual List View. Rather than fetch the complete
85 list from wherever it is stored (typically from disk or a remote
86 server), only that information which is required to display the part
87 of the list currently in view is fetched. The subject of this
88 document is the interaction between client and server required to
89 implement this functionality in the context of the results from a
90 sorted LDAP search request.
92 For example, suppose an e-mail address book application displays a
93 list view onto the list containing the names of all the holders of
94 e-mail accounts at a large university. The list is sorted
95 alphabetically. While there may be tens of thousands of entries in
96 this list, the address book list view displays only 20 such accounts
97 at any one time. The list has an accompanying scroll bar and text
98 input window for type-down. When first displayed, the list view
99 shows the first 20 entries in the list, and the scroll bar slider is
100 positioned at the top of its range. Should the user drag the slider
101 to the bottom of its range, the displayed contents of the list view
102 should be updated to show the last 20 entries in the list.
103 Similarly, if the slider is positioned somewhere in the middle of
104 its travel, the displayed contents of the list view should be
105 updated to contain the 20 entries located at that relative position
106 within the complete list. Starting from any display point, if the
107 user uses the cursor keys or clicks on the scroll bar to request
108 that the list be scrolled up or down by one entry, the displayed
109 contents should be updated to reflect this. Similarly the list
110 should be displayed correctly when the user requests a page scroll
112 Boreham et al Standards Track 2
\f
113 LDAP Extensions for Scrolling View November 2001
114 Browsing of Search Results
116 up or down. Finally, when the user types characters in the type-
117 down window, the displayed contents of the list should "jump" or
118 "seek" to the appropriate point within the list. For example, if
119 the user types "B", the displayed list could center around the first
120 user with a name beginning with the letter "B". When this happens,
121 the scroll bar slider should also be updated to reflect the new
122 relative location within the list.
124 This document defines a request control which extends the LDAP
125 search operation. Always used in conjunction with the server side
126 sorting control [SSS], this allows a client to retrieve selected
127 portions of large search result set in a fashion suitable for the
128 implementation of a virtual list view.
131 5. Client-Server Interaction
133 The Virtual List View control extends a regular LDAP Search
134 operation which must also include a server-side sorting control
135 [SSS]. Rather than returning the complete set of appropriate
136 SearchResultEntry messages, the server is instructed to return a
137 contiguous subset of those entries, taken from the sorted result
138 set, centered around a particular target entry. Henceforth, in the
139 interests of brevity, the sorted search result set will be referred
142 The sort control MAY contain any sort specification valid for the
143 server. The attributeType field in the first SortKeyList sequence
144 element has special significance for "typedown".
146 The desired target entry and the number of entries to be returned,
147 both before and after that target entry in the list, are determined
148 by the client's VirtualListViewRequest control.
150 When the server returns the set of entries to the client, it
151 attaches a VirtualListViewResponse control to the SearchResultDone
152 message. The server returns in this control: its current estimate
153 for the list content count, the location within the list
154 corresponding to the target entry, and any error codes.
156 The target entry is specified in the VirtualListViewRequest control
157 by one of two methods. The first method is for the client to
158 indicate the target entry's offset within the list. The second way
159 is for the client to supply an attribute assertion value. The value
160 is compared against the values of the attribute specified as the
161 primary sort key in the sort control attached to the search
162 operation. The first sort key in the SortKeyList is the primary
163 sort key. The target entry is the first entry in the list with
164 value greater than or equal to (in the primary sort order), the
165 presented value. The order is determined by rules defined in [SSS].
166 Selection of the target entry by this means is designed to implement
167 "typedown". Note that it is possible that no entry satisfies these
169 Boreham et al Standards Track 3
\f
170 LDAP Extensions for Scrolling View November 2001
171 Browsing of Search Results
173 conditions, in which case there is no target entry. This condition
174 is indicated by the server returning the special value contentCount
175 + 1 in the target position field.
177 Because the server may not have an accurate estimate of the number
178 of entries in the list, and to take account of cases where the list
179 size is changing during the time the user browses the list, and
180 because the client needs a way to indicate specific list
181 targets "beginning" and "end", offsets within the list are
182 transmitted between client and server as ratios---offset to
183 content count. The server sends its latest estimate as to the number
184 of entries in the list (content count) to the client in every
185 response control. The client sends its assumed value for the
186 content count in every request control. The server examines the
187 content count and offsets presented by the client and computes the
188 corresponding offsets within the list, based on its own idea of the
194 Si is the actual list offset used by the server
195 Sc is the server's estimate for content count
196 Ci is the client's submitted offset
197 Cc is the client's submitted content count
198 The result is rounded to the nearest integer.
200 If the content count is stable, and the client returns to the server
201 the content count most recently received, Cc = Sc and the offsets
202 transmitted become the actual server list offsets.
204 The following special cases are allowed: a client sending a
205 content count of zero (Cc = 0) means "client has no idea what the
206 content count is, server MUST use its own content count estimate
207 in place of the client's". An offset value of one (Ci = 1)
208 always means that the target is the first entry in the list. Client
209 specifying an offset which equals the content count specified in the
210 same request control (Ci = Cc) means that the target is the last
211 entry in the list. Ci may only equal zero when Cc is also zero.
212 This signifies the last entry in the list.
214 Because the server always returns contentCount and targetPosition,
215 the client can always determine which of the returned entries is the
216 target entry. Where the number of entries returned is the same as
217 the number requested, the client is able to identify the target by
218 simple arithmetic. Where the number of entries returned is not the
219 same as the number requested (because the requested range crosses
220 the beginning or end of the list, or both), the client must use the
221 target position and content count values returned by the server to
222 identify the target entry. For example, suppose that 10 entries
223 before and 10 after the target were requested, but the server
224 returns 13 entries, a content count of 100 and a target position of
226 Boreham et al Standards Track 4
\f
227 LDAP Extensions for Scrolling View November 2001
228 Browsing of Search Results
230 3. The client can determine that the first entry must be entry
231 number 1 in the list, therefore the 13 entries returned are the
232 first 13 entries in the list, and the target is the third one.
234 A server-generated context identifier MAY be returned to clients. A
235 client receiving a context identifier SHOULD return it unchanged in
236 a subsequent request which relates to the same list. The purpose of
237 this interaction is to enhance the performance and effectiveness of
238 servers which employ approximate positioning.
243 Support for the virtual list view control extension is indicated by
244 the presence of the OID "2.16.840.1.113730.3.4.9" in the
245 supportedControl attribute of a server's root DSE.
249 This control is included in the SearchRequest message as part of the
250 controls field of the LDAPMessage, as defined in Section 4.1.12 of
251 [LDAPv3]. The controlType is set to "2.16.840.1.113730.3.4.9". The
252 criticality SHOULD be set to TRUE. If this control is included in a
253 SearchRequest message, a Server Side Sorting request control [SSS]
254 MUST also be present in the message. The controlValue is an OCTET
255 STRING whose value is the BER-encoding of the following SEQUENCE:
257 VirtualListViewRequest ::= SEQUENCE {
258 beforeCount INTEGER (0..maxInt),
259 afterCount INTEGER (0..maxInt),
261 byoffset [0] SEQUENCE {
262 offset INTEGER (0 .. maxInt),
263 contentCount INTEGER (0 .. maxInt) },
264 greaterThanOrEqual [1] AssertionValue },
265 contextID OCTET STRING OPTIONAL }
267 beforeCount indicates how many entries before the target entry the
268 client wants the server to send. afterCount indicates the number of
269 entries after the target entry the client wants the server to send.
270 offset and contentCount identify the target entry as detailed in
271 section 4. greaterThanOrEqual is an attribute assertion value
272 defined in [LDAPv3]. If present, the value supplied in
273 greaterThanOrEqual is used to determine the target entry by
274 comparison with the values of the attribute specified as the primary
275 sort key. The first list entry who's value is no less than (less
276 than or equal to when the sort order is reversed) the supplied value
277 is the target entry. If present, the contextID field contains the
278 value of the most recently received contextID field from a
279 VirtualListViewResponse control. The type AssertionValue and value
280 maxInt are defined in [LDAPv3]. contextID values have no validity
281 outwith the connection on which they were received. That is, a
283 Boreham et al Standards Track 5
\f
284 LDAP Extensions for Scrolling View November 2001
285 Browsing of Search Results
287 client should not submit a contextID which it received from another
288 connection, a connection now closed, or a different server.
291 6.2. Response Control
293 This control is included in the SearchResultDone message as part of
294 the controls field of the LDAPMessage, as defined in Section 4.1.12
297 The controlType is set to "2.16.840.1.113730.3.4.10". The
298 criticality is FALSE (MAY be absent). The controlValue is an OCTET
299 STRING, whose value is the BER encoding of a value of the following
302 VirtualListViewResponse ::= SEQUENCE {
303 targetPosition INTEGER (0 .. maxInt),
304 contentCount INTEGER (0 .. maxInt),
305 virtualListViewResult ENUMERATED {
308 unwillingToPerform (53),
309 insufficientAccessRights (50),
311 timeLimitExceeded (3),
312 adminLimitExceeded (11),
313 sortControlMissing (60),
314 offsetRangeError (61),
316 contextID OCTET STRING OPTIONAL }
318 targetPosition gives the list offset for the target entry.
319 contentCount gives the server's estimate of the current number of
320 entries in the list. Together these give sufficient information for
321 the client to update a list box slider position to match the newly
322 retrieved entries and identify the target entry. The contentCount
323 value returned SHOULD be used in a subsequent VirtualListViewRequest
324 control. contextID is a server-defined octet string. If present,
325 the contents of the contextID field SHOULD be returned to the server
326 by a client in a subsequent VirtualListViewRequest control.
328 The virtualListViewResult codes which are common to the LDAP
329 searchResponse (adminLimitExceeded, timeLimitExceeded, busy,
330 operationsError, unwillingToPerform, insufficientAccessRights) have
331 the same meanings as defined in [LDAPv3], but they pertain
332 specifically to the VLV operation. For example, the server could
333 exceed an administration limit processing a SearchRequest with a
334 VirtualListViewRequest control. However, the same administration
335 limit would not be exceeded should the same SearchRequest be
336 submitted by the client without the VirtualListViewRequest control.
337 In this case, the client can determine that an administration limit
338 has been exceeded in servicing the VLV request, and can if it
340 Boreham et al Standards Track 6
\f
341 LDAP Extensions for Scrolling View November 2001
342 Browsing of Search Results
344 chooses resubmit the SearchRequest without the
345 VirtualListViewRequest control.
347 insufficientAccessRights means that the server denied the client
348 permission to perform the VLV operation.
350 If the server determines that the results of the search presented
351 exceed the range provided by the 32-bit offset values, it MUST
352 return offsetRangeError.
354 If the server returns any code other then success (0) for
355 virtualListViewResult, then the server MUST return controlError (76)
356 as the resultCode of the SearchResultDone message. [ctrlErr]
361 Here we walk through the client-server interaction for a specific
362 virtual list view example: The task is to display a list of all
363 78564 people in the US company "Ace Industry". This will be done by
364 creating a graphical user interface object to display the list
365 contents, and by repeatedly sending different versions of the same
366 virtual list view search request to the server. The list view
367 displays 20 entries on the screen at a time.
369 We form a search with baseDN "o=Ace Industry, c=us"; search scope
370 subtree; filter "objectClass=inetOrgPerson". We attach a server sort
371 order control to the search, specifying ascending sort on attribute
372 "cn". To this base search, we attach a virtual list view request
373 control with contents determined by the user activity and send the
374 search to the server. We display the results from each search in
375 the list window and update the slider position.
377 When the list view is first displayed, we want to initialize the
378 contents showing the beginning of the list. Therefore, we set
379 beforeCount = 0, afterCount = 19, contentCount = 0, offset = 1 and
380 send the request to the server. The server duly returns the first
381 20 entries in the list, plus the content count = 78564 and
382 targetPosition = 1. We therefore leave the scroll bar slider at its
383 current location (the top of its range).
385 Say that next the user drags the scroll bar slider down to the
386 bottom of its range. We now wish to display the last 20 entries in
387 the list, so we set beforeCount = 19, afterCount = 0, contentCount =
388 78564, offset = 78564 and send the request to the server. The server
389 returns the last 20 entries in the list, plus the content count =
390 78564 and targetPosition = 78564.
392 Next the user presses a page up key. Our page size is 20, so we
393 set beforeCount = 0, afterCount = 19, contentCount = 78564,
394 offset = 78564-19-20 and send the request to the server. The server
396 Boreham et al Standards Track 7
\f
397 LDAP Extensions for Scrolling View November 2001
398 Browsing of Search Results
400 returns the preceding 20 entries in the list, plus the content count
401 = 78564 and targetPosition = 78525.
403 Now the user grabs the scroll bar slider and drags it to 68% of the
404 way down its travel. 68% of 78564 is 53424 so we set beforeCount =
405 9, afterCount = 10, contentCount = 78564, offset = 53424 and send
406 the request to the server. The server returns the preceding 20
407 entries in the list, plus the content count = 78564 and
408 targetPosition = 53424.
410 Lastly, the user types the letter "B". We set beforeCount = 9,
411 afterCount = 10 and greaterThanOrEqual = "B". The server finds the
412 first entry in the list not less than "B", let's say "Babs Jensen",
413 and returns the nine preceding entries, the target entry, and the
414 proceeding 10 entries. The server returns content count = 78564 and
415 targetPosition = 5234 and so the client updates its scroll bar
416 slider to 6.7% of full scale.
419 8. Notes for Implementers
421 While the feature is expected to be generally useful for arbitrary
422 search and sort specifications, it is specifically designed for
423 those cases where the result set is very large. The intention is
424 that this feature be implemented efficiently by means of pre-
425 computed indices pertaining to a set of specific cases. For
426 example, an offset relating to "all the employees in the local
427 organization, sorted by surname" would be a common case.
429 The intention for client software is that the feature should fit
430 easily with the host platform's graphical user interface facilities
431 for the display of scrolling lists. Thus the task of the client
432 implementers should be one of reformatting up the requests for
433 information received from the list view code to match the format of
434 the virtual list view request and response controls.
436 Client implementers should note that any offset value returned by
437 the server may be approximate. Do not design clients > which only
438 operate correctly when offsets are exact.
440 Server implementers using indexing technology which features
441 approximate positioning should consider returning context
442 identifiers to clients. The use of a context identifier will allow
443 the server to distinguish between client requests which relate to
444 different displayed lists on the client. Consequently the server can
445 decide more intelligently whether to reposition an existing database
446 cursor accurately to within a short distance of its current
447 position, or to reposition to an approximate position. Thus the
448 client will see precise offsets for "short" repositioning (e.g.
449 paging up or down), but approximate offsets for a "long" reposition
450 (e.g. a slider movement).
453 Boreham et al Standards Track 8
\f
454 LDAP Extensions for Scrolling View November 2001
455 Browsing of Search Results
457 Server implementers are free to return status code
458 unwillingToPerform should their server be unable to service any
459 particular VLV search. This might be because the resolution of the
460 search is computationally infeasible, or because excessive server
461 resources would be required to service the search.
463 Client implementers should note that this control is only defined on
464 a client interaction with a single server. If a server returns
465 referrals as a part of its response to the search request, the
466 client is responsible for deciding when and how to apply this
467 control to the referred-to servers, and how to collate the results
468 from multiple servers.
471 9. Relationship to "Simple Paged Results"
473 These controls are designed to support the virtual list view, which
474 has proved hard to implement with the Simple Paged Results mechanism
475 [SPaged]. However, the controls described here support any operation
476 possible with the Simple Paged Results mechanism. The two mechanisms
477 are not complementary; rather one has a superset of the other's
478 features. One area where the mechanism presented here is not a
479 strict superset of the Simple Paged Results scheme is that here we
480 require a sort order to be specified. No such requirement is made
484 10. Security Considerations
486 Server implementers may wish to consider whether clients are able to
487 consume excessive server resources in requesting virtual list
488 operations. Access control to the feature itself; configuration
489 options limiting the featureÆs use to certain predetermined search
490 base DNs and filters; throttling mechanisms designed to limit the
491 ability for one client to soak up server resources, may be
494 Consideration should be given as to whether a client will be able to
495 retrieve the complete contents, or a significant subset of the
496 complete contents of the directory using this feature. This may be
497 undesirable in some circumstances and consequently it may be
498 necessary to enforce some access control.
500 Clients can, using this control, determine how many entries are
501 contained within a portion of the DIT. This may constitute a
502 security hazard. Again, access controls may be appropriate.
504 Server implementers SHOULD exercise caution concerning the content
505 of the contextID. Should the contextID contain internal server
506 state, it may be possible for a malicious client to use that
507 information to gain unauthorized access to information.
510 Boreham et al Standards Track 9
\f
511 LDAP Extensions for Scrolling View November 2001
512 Browsing of Search Results
517 Chris Weider of Microsoft co-authored a previous version of this
524 [LDAPv3] Wahl, M., Kille, S. and T. Howes, "Lightweight Directory
525 Access Protocol (v3)", Internet Standard, RFC 2251,
528 [SPaged] Weider, C., Herron, A., Anantha, A. and T. Howes, "LDAP
529 Control Extension for Simple Paged Results
530 Manipulation", RFC2696, September 1999.
532 [SSS] Wahl, M., Herron, A. and T. Howes, "LDAP Control
533 Extension for Server Side Sorting of Search Results",
534 RFC 2891, August, 2000.
536 [Bradner97] Bradner, S., "Key Words for use in RFCs to Indicate
537 Requirement Levels", BCP 14, RFC 2119, March 1997.
539 [ctrlErr] Armijo, M. and A. Kashi, ôResult Code for LDAP
540 Controlsö, Internet-Draft, September, 2001.
541 Work in progress published as:
542 <draft-armijo-ldap-control-error-02.txt>
545 13. Authors' Addresses
550 david@bozemanpass.com
555 Provo, Utah 84606, USA
559 Microsoft Corporation
561 Redmond, WA 98052, USA
567 Boreham et al Standards Track 10
\f
568 LDAP Extensions for Scrolling View November 2001
569 Browsing of Search Results
571 Microsoft Corporation
573 Redmond, WA 98052, USA
575 micharm@microsoft.com
578 Microsoft Corporation
580 Redmond, WA 98052, USA
585 14. Full Copyright Statement
587 Copyright (C) The Internet Society (2001). All Rights Reserved.
588 This document and translations of it may be copied and furnished to
589 others, and derivative works that comment on or otherwise explain it
590 or assist in its implementation may be prepared, copied, published
591 and distributed, in whole or in part, without restriction of any
592 kind, provided that the above copyright notice and this paragraph
593 are included on all such copies and derivative works. However, this
594 document itself may not be modified in any way, such as by removing
595 the copyright notice or references to the Internet Society or other
596 Internet organizations, except as needed for the purpose of
597 developing Internet standards in which case the procedures for
598 copyrights defined in the Internet Standards process must be
599 followed, or as required to translate it into languages other than
600 English. The limited permissions granted above are perpetual and
601 will not be revoked by the Internet Society or its successors or
602 assigns. This document and the information contained herein is
603 provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE
604 INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR
605 IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
606 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
607 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."
613 Boreham et al Standards Track 11
\f