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

Versions: 00 01 02 03 04 05 06 07 08 09                                 
INTERNET-DRAFT                                   David Boreham, Netscape
ldapext Working Group                                  20 November, 1997

     LDAP Extensions for Scrolling View Browsing of Search Results
                  This document expires on 23 May 1998

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 learn the current status of  any  Internet-Draft,  please  check  the
``1id-abstracts.txt''  listing  contained in the Internet- Drafts Shadow
Directories on ds.internic.net (US East Coast), nic.nordu.net  (Europe),
ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific Rim).

2.  Abstract

This document describes a Virtual List View control  extension  for  the
LDAP  Search  operation.  This control is designed to allow the ''virtual
list box'' feature, common in existing  commercial  e-mail  address  book
applications, to be supported efficiently by LDAP servers. LDAP servers'
inability to support this client feature is a significant impediment  to
LDAP replacing proprietary protocols in commercial e-mail systems.

The control allows a client to specify that the  server  return,  for  a
given  LDAP search with associated sort keys, a contiguous subset of the
search result set. This subset is specified in terms of indices into the
ordered list, or in terms of a greater than or equal comparison value.

3.  Background

A Virtual List is a graphical user interface  technique  employed  where
ordered lists containing a large number of entries need to be displayed.
A window containing a small number of visible list entries is drawn. The
visible  portion of the list may be relocated to different points within
the list by means of user input. This input  can  be  to  a  scroll  bar
slider; from cursor keys; from page up/down keys; from alphanumeric keys
for "typedown".  The user is given the impression that they  may  browse

Boreham                                                         [Page 1]

RFC DRAFT                                                  November 1997

the  complete  list  at  will,  even  though  it may contain millions of
entries. It is the fact  that  the  complete  list  contents  are  never
required  at  any one time that characterizes Virtual List View.  Rather
than fetch the complete list from wherever it is stored (typically  from
disk  or  a  remote  server), only that information which is required to
display the part of the list currently in view is fetched.  The  subject
of  this  document is the interaction between client and server required
to implement this functionality in the context of  the  results  from  a
sorted LDAP search request.

For example, suppose an e-mail address book application displays a  list
view  onto  the  list  containing the names of all the holders of e-mail
accounts at a large  university.  The  list  is  sorted  alphabetically.
While  there  may  be  tens  of  thousands  of entries in this list, the
address book list view displays only 20 such accounts at any  one  time.
The  list has an accompanying scroll bar and text input window for type-
down.  When first displayed, the list view shows the first 20 entries in
the  list,  and  the  scroll  bar slider is positioned at the top of its
range. Should the user drag the slider to the bottom of its  range,  the
displayed  contents  of the list view should be updated to show the last
20 entries in the list. Similarly, if the slider is positioned somewhere
in  the  middle  of  its travel, the displayed contents of the list view
should be updated to contain the 20 entries  located  at  that  relative
position  within the complete list.  Starting from any display point, if
the user uses the cursor keys or clicks on the  scroll  bar  to  request
that  the  list  be scrolled up or down by one entry, the displayed con-
tents should be updated to reflect this. Similarly the  list  should  be
displayed  correctly  when  the  user requests a page scroll up or down.
Finally, when the user types characters in  the  type-down  window,  the
displayed  contents of the list should "jump" or "seek" to the appropri-
ate point within the list.  For example, if  the  user  types  "B",  the
displayed  list could center around the first user with a name beginning
with the letter "B".  When this happens, the scroll  bar  slider  should
also be updated to reflect the new relative location within the list.

This document defines a request control which extends  the  LDAP  search
operation. When used in conjunction with the server results sorting con-
trol, this allows a client to retrieve selected portions of large search
result  set  in  a  fashion suitable for the implementation of a virtual
list view.

The key words "MUST", "SHOULD", and "MAY" used in this document  are  to
be interpreted as described in [Bradner97].

4.  Client-Server Interaction

The Virtual List View control extends a regular  LDAP  Search  operation
with  mandatory server-side sorting control[SSS].  Rather than returning

Boreham                                                         [Page 2]

RFC DRAFT                                                  November 1997

the complete set of appropriate SearchResultEntry messages,  the  server
is instructed to return a contiguous subset of those entries, taken from
the sorted result set, centered around a particular target  entry.  Hen-
ceforth,  in the interests of brevity, the sorted search result set will
be referred to as "the list".

The sort control MAY  contain  any  sort  specification  valid  for  the
server.  The  attributeType field in the first SortKeyList sequence ele-
ment has special significance for "typedown".

The desired target entry, and the  number  of  entries  to  be  returned
before  and  after  that target entry in the list, are determined by the
client's VirtualListViewRequest control.

When the server returns the set of entries to the client, it attaches  a
VirtualListViewResponse  control  to  the searchResultDone message.  The
server returns in this control: its current estimate for the  list  con-
tent  count,  the  location  within the list corresponding to the target
entry, and any error codes.

The target entry is specified in the VirtualListViewRequest  control  by
one  of  two methods. The first method is for the client to indicate the
target entry's index within the list.  The second way is for the  client
to  supply an attribute assertion value. This value is used to determine
the target entry as follows.  The value is compared against  the  values
of  the  attribute specified as the primary sort key in the sort control
attached to the search operation.  The target entry is  first  entry  in
the list having an attribute value for that attribute, but no value less
than (in the primary sort order), the presented value.  Selection of the
target  entry  by  this means is designed to implement "typedown".  Note
that it is possible that no entry satisfies these conditions,  in  which
case there is no target entry. This condition is indicated by the server
returning the special value contentCount +  1  in  the  target  position

Because the server may not have a completely accurate  estimate  of  the
number  of  entries  in the list, and to take account of cases where the
list size is changing during the time the user  browses  the  list,  and
because the client needs a way to indicate specific list targets "begin-
ning" and "end", indices within the list are transmitted between  client
and  server  as  ratios---index  to  content count. The server sends its
latest estimate as to the number of entries in the list (content  count)
to  the  client in every response control.  The client sends its assumed
value for the content count in every request control.  The server  exam-
ines  the content count and indices presented by the client and computes
the corresponding indices within the list, based on its own idea of  the
content count.

Boreham                                                         [Page 3]

RFC DRAFT                                                  November 1997

     Si = Sc * (Ci / Cc)

     Si is the actual list index used by the server
     Sc is the server's estimate for content count
     Ci is the client's submitted index
     Cc is the client's submitted content count
     The result is rounded to the nearest integer.

If the content count is stable, and the client returns to the server the
content  count most recently received, Cc = Sc and the indices transmit-
ted become the actual server list offsets.

The following special cases are allowed:  a  client  sending  a  content
count  of  zero  means  "client  has  no idea what the content count is,
server MUST  use  its  own  content  count  estimate  in  place  of  the
client's".  An  index value of one (Ci = 1) always means that the target
is the first entry in the list. Client specifying an index which  equals
the  content count specified in the same request control (Ci = Cc) means
that the target is the last entry in the list.

Because the server always returns contentCount and  targetPosition,  the
client  can always determine which of the returned entries is the target
entry. Where the number of entries returned is the same  as  the  number
requested,  the  client  is able to identify the target by simple arith-
metic. Where the number of entries returned  is  not  the  same  as  the
number  requested  (because the requested range crosses the beginning or
end of the list, or both), the client must use the target  position  and
content  count  values  returned  by  the  server to identify the target
entry. For example, suppose that 10 entries before and after the  target
were  requested, but the server returns five entries, a content count of
100 and a target position of 3. The client can determine that the  first
entry  must  be  entry  number 1 in the list, therefore the five entries
returned are the first five entries in the list, and the target  is  the
third one.

5.  The Controls

Support for the virtual list view extended operation is indicated by the
presence of the OID "2.16.840.1.113730.3.4.9" in the supportedExtensions
attribute of a server's root DSE.

5.1.  Request Control

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 controlType is set to "2.16.840.1.113730.3.4.9". The cri-
ticality   SHOULD  be  set  to  TRUE.  If  this control is included in a

Boreham                                                         [Page 4]

RFC DRAFT                                                  November 1997

searchRequest message, a Server Side Sorting request control [SSS]  MUST
also  be  present  in  the  message. The controlValue is an OCTET STRING
whose value is the BER-encoding of the following SEQUENCE:

     VirtualListViewRequest ::= SEQUENCE {
             beforeCount    INTEGER (0 .. maxInt),
             afterCount     INTEGER (0 .. maxInt),
             CHOICE {
                     byIndex [0] SEQUENCE {
                     index           INTEGER (0 .. maxInt),
                     contentCount    INTEGER (0 .. maxInt) }
                     byValue [1] greaterThanOrEqual assertionValue }

beforeCount indicates how many  entries  before  the  target  entry  the
client  wants  the  server  to  send. afterCount indicates the number of
entries after the target entry the client  wants  the  server  to  send.
index  and contentCount identify the target entry as detailed in section
4.  greaterThanOrEqual  is  an  attribute  assertion  value  defined  in
[LDAPv3].  If  present, the value supplied in greaterThanOrEqual is used
to determine the target entry by  comparison  with  the  values  of  the
attribute  specified as the primary sort key. The first list entry who's
value is no less than the supplied value is the target entry.

5.2.  Response Control

This control is included in the searchResultDone message as part of  the
controls   field  of the  LDAPMessage, as  defined in Section  4.1.12 of

The controlType is set to "2.16.840.1.113730.3.4.10". The criticality is
FALSE (MAY be absent).  The controlValue is an OCTET STRING, whose value
is the BER encoding of a value of the following SEQUENCE:

     VirtualListViewResponse ::= SEQUENCE {
             targetPosition    INTEGER (0 .. maxInt),
             contentCount     INTEGER (0 .. maxInt),
             virtualListViewResult ENUMERATED {
                     success (0),
                     operatonsError (1),
                     unwillingToPerform (53),
                     insufficientAccessRights (50),
                     busy (51),
                     timeLimitExceeded (3),
                     adminLimitExceeded (11),
                     sortControlMissing (60),
                     indexRangeError (61),
                     other (80) }  }

Boreham                                                         [Page 5]

RFC DRAFT                                                  November 1997

targetPosition gives the list index for the target  entry.  contentCount
gives  the  server's  estimate  of  the current number of entries in the
list.  Together these give sufficient  information  for  the  client  to
update  a  list box slider position to match the newly retrieved entries
and identify the target entry. The contentCount value returned SHOULD be
used in a subsequent virtualListViewRequest control.

6.  Protocol Example

Here we walk through the client-server interaction for a  specific  vir-
tual list view example:  The task is to display a list of all 78564 peo-
ple in the US company "Ace Industry".  This will be done by  creating  a
graphical  user  interface  object  to display the list contents, and by
repeatedly sending different versions of  the  same  virtual  list  view
search  request  to the server. The list view displays 20 entries on the
screen at a time.

We form a search with baseDN "o=Ace Industry, c=us"; search  scope  sub-
tree;  filter "objectClass=inetOrgPerson". We attach a server sort order
control to the search, specifying ascending sort on attribute  "cn".  To
this  base  search,  we  attach a virtual list view request control with
contents determined by the user activity and  send  the  search  to  the
server.  We  display the results from each search in the list window and
update the slider position.

When the list view is first displayed, we want to  initialize  the  con-
tents showing the beginning of the list. Therefore, we set beforeCount =
0, afterCount = 19, contentCount = 0, index = 1 and send the request  to
the  server.  The  server duly returns the first 20 entries in the list,
plus the content count = 78564 and  targetPosition  =  1.  We  therefore
leave  the  scroll  bar  slider  at its current location (the top of its

Say that next the user drags the scroll bar slider down to the bottom of
its  range.   We now wish to display the last 20 entries in the list, so
we set beforeCount = 19, afterCount = 0, contentCount = 78564,  index  =
78564 and send the request to the server. The server returns the last 20
entries in the list, plus the content count = 78564 and targetPosition =

Next the user presses a page up key. Our page size  is  20,  so  we  set
beforeCount  =  0,  afterCount  =  19,  contentCount  =  78564,  index =
78564-19-20 and send the request to the server. The server  returns  the
preceeding  20  entries  in the list, plus the content count = 78564 and
targetPosition = 78524.

Now the user grabs the scroll bar slider and drags it to 68% of the  way
down  its  travel.  68%  of  78564  is  52424 so we set beforeCount = 9,

Boreham                                                         [Page 6]

RFC DRAFT                                                  November 1997

afterCount = 10, contentCount =  78564,  index  =  52424  and  send  the
request  to  the server. The server returns the preceeding 20 entries in
the list, plus the content count = 78564 and targetPosition = 78524.

Lastly, the user types the letter "B". We set beforeCount  =  9,  after-
Count  =  10  and  greaterThanOrEqual  = "B". The server finds the first
entry in the list not less  than  "B",  let's  say  "Babs  Jensen",  and
returns  the nine preceeding entries, the target entry, and the proceed-
ing 10 entries.  The server returns content count = 78564 and  targetPo-
sition = 5234 and so the client updates its scroll bar slider to 6.6% of
full scale.

7.  Notes for Implementers

While the feature is expected  to  be  generally  useful  for  arbitrary
search  and  sort  specifications, it is specifically designed for those
cases where the result set is very large.  The intention  is  that  this
feature be implemented efficiently by means of pre-computed indices per-
taining to a set of specific cases. For example, an  index  relating  to
"all  the  employees in the local organization, sorted by surname" would
be a common case.

The intention for client software is that the feature should fit  easily
with  the  host  platform's  graphical user interface facilities for the
display of scrolling lists. Thus the task  of  the  client  implementers
should  be  one of reformatting up the requests for information received
from the list view code to match the format of  the  virtual  list  view
request and response controls.

8.  Relationship to "Simple Paged Results"

These controls are designed to support the virtual list view, which  has
proved  hard  to  implement  with  the  Simple  Paged  Results mechanism
[SPaged]. However, the controls described  here  support  any  operation
possible with the Simple Paged Results mechanism. The two mechanisms are
not complementary, rather one has a superset of the other's features.

9.  Security Considerations

Server implementers may wish to consider whether  clients  are  able  to
consume  excessive  server  resources  in requesting virtual list opera-
tions. Access control to the feature itself; configuration options  lim-
iting  the  feature's  use  to certain predetermined search base DNs and
filters; throttling mechanisms designed to limit  the  ability  for  one
client to soak up server resources, may be appropriate.

Boreham                                                         [Page 7]

RFC DRAFT                                                  November 1997

Consideration should be given as to whether a client  will  be  able  to
retrieve  the complete contents, or a significant subset of the complete
contents of the directory using this feature. This may be undesirable in
some  circumstances and consequently it may be necessary to enforce some
access control.

Clients can, using this control, determine how  many  entries  are  con-
tained  within  a  portion  of  the  DIT. This may constitute a security
hazard. Again, access controls may be appropriate.

10.  References

     Wahl, M, S. Kille and T. Howes, "Lightweight Directory Access  Pro-
     tocol  (v3)",  Internet  Draft,  11 July, 1997. Available as draft-

     Weider, C, A. Herron and T. Howes, "LDAP Control Extension for Sim-
     ple  Paged  Results  Manipulation",  Internet  Draft,  March, 1997.
     Available as draft-ietf-asid-ldapv3-simple-paged-01.txt.

[SSS]Wahl, M, A. Herron and T. Howes, "LDAP Control Extension for Server
     Side  Sorting  of  Search  Results",  Internet  Draft, March, 1997.
     Available as draft-ietf-asid-ldapv3-sorting-00.txt.

     Bradner, Scott, "Key Words for use in RFCs to Indicate  Requirement
     Levels", Internet Draft, March, 1997. Available as RFC2119.

11.  Author's Address

   David Boreham
   Netscape Communications Corp.
   501 E. Middlefield Road
   Mountain View, CA 94043, USA
   +1 650 937-5206

   This document expires on 23 May 1998

Boreham                                                         [Page 8]