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