LCUP show stopper

To LCUP,

Let us try to describe what we consider to be the primary
show-stopping issue in the draft-ietf-ldup-lcup proposal.  For
convenience, we will refer to this below as LCUP.

LCUP expects server implementations to maintain sufficient history
so that they provide incremental refreshes of content instead of
full reloads on subsequent client requests.  For subsequent client
request, full reloads should be the exception not the norm.  We
argue that full reloads will actually be more of the norm, certainly
not limited to rare exceptions.
 
As you know, we think it is not reasonable to require servers
maintain history information in order to support LCUP.  That forces
a particular design choice which may be counter to other design
factors, such as scalability.  However, we will focus our
discussions on servers which choose to maintain some amount of
historical information. 

We think LCUP misjudges the completeness of history information
that would need to be maintained to avoid reloads in the general
case and the complexity of computing the clients state based upon
that history (in order to determine what "deletes" need to be sent).

Complete history implies that server can compute the client's state
and generate the smallest amount of traffic to converge the client's
state to server's state based upon the information contained in the
cookie.  Of course, if we were to assume complete history, we could
do much better than sending complete copies of entries.
 
Sufficient history implies that the server is able to determine
which entry update and delete messages need to be delivered to the
client to converge its state to that of the server.       
 
Determining which entries need updating requires no history, the
server can simply send all entries presently meeting the search
criteria that have been updated since the previous request (based
upon time stamps).  However, determining which delete messages to
send requires history.

Minimally, the server needs to
  a) maintain history about deleted entries and
  b) track the time each entry was modified and/or renamed,

and send a delete message for each entry deleted or modified since
the previous content was provided.  That is, without additional
history, the server has to assume that all deletes, modifications,
and renames affected entries to leave the result set.  This is 
problematic as the server has to force a reload as a result of
modifications which are not and were not ever of interest to the
application.  That is, when a client is interested in 100 entries
of a 1,000,000 entry context and 10,000 (1%) were modified since
the last refresh, the server would have to prove most of these
10,000 entries were not previously in the result set otherwise
return an error indicating a full reload was required.  This is
because 1 update (1% of 100) and 9,999 delete messages are likely
far more traffic than 100 full entry messages.

Now, a server could maintain additional information about entry
renaming.  Then it could prove which entries could not possibly be
in the search's scope and trim out those "deletes".  However, unless
it maintained history of entry modifications (and other changes in
entry visibility based upon other factors), the server would still
have to send deletes for all modified entries which are in scope
regardless of whether they currently match the search criteria.
 
That is, without entry modification history, if the scope was subtree
covering 10% of the context (as described above), then 9000 of the
deletes could be eliminated.  The server would still have to send
1 update + 999 deletes.  If we assume 1K entry size (common for 
many directories), that's about the same amount of traffic as 
required for a full reload.

As another example, let's look at two general history maintenance
mechanism common in existing servers, tombstones and changelogs.
LDAP servers supporting these mechanisms generally do not maintain
history of old attribute types and values of modified or deleted
entries and, hence, cannot compute after an update operation an
entry's previous state.  If the server cannot compute the entry's
previous state, it cannot generally compute whether that entry was
previously in the LCUP result set.  It must assume that it was.
Hence, even where no or few modified or deleted entries were
previously in the result set, the server is forced to either send
delete messages for all of these entries or cause a full reload.
LCUP does not provide a reasonably efficient solution for the
LDAP servers maintaining history information through common
practices.
 
The first example was intended to be illustrative of one of many
use scenarios.  As a general solution to the client update problem,
we believe LCUP needs to work well in a wide variety of use scenarios
having different characteristics in factors like total number of         
entries, the amount of changes, the percent of in-scope entries,      
the percent of entries in the result set and average entry size.          
The second example was intended to illustrate that history information         
currently maintained in today's LDAP servers is not "sufficient
history" for LCUP purposes.

Basically, LCUP requires vendors to maintain "sufficient history"               
(significantly more than servers currently maintain today for other
purposes) when in many use scenarios that history is ineffective           
in reducing traffic.  And in use scenarios where that history might         
be effective, the protocol doesn't allow the server to fully take           
advantage of that history (because it doesn't support entry change
deltas).
 
It is our opinion that LCUP is generally not more suitable than           
persistent search solutions it was intended to replace, while coming        
at a significantly higher implementation cost (the cost of
maintaining/using "sufficient history").  After 3 years of LCUP
engineering, we don't yet have "running code".  Our (Jong and Kurt's)    
own efforts to develop a LCUP prototype were stopped shortly after    
we concluded LCUP was unsuitable.  We are currently pursuing a            
technical alternative.

Kurt and Jong