Subject: [Simple] Partial Notifies?

From: "Avshalom Houri" <[email-masked]>
Date: Fri, 31 Aug 2001 13:37:53 +0200

[Sending from a different email due to mailing list DNS problems]

Will it be possible to get partial updates to presence info? It is of course
an optimization

but it seems to be an important one as presence info can become very big.

avshalom

Sametime/Lotus/IBM

---

From: Jonathan Rosenberg <[email-masked]>
Date: Wed, 5 Sep 2001 02:53:13 -0400

> -----Original Message-----
> From: Avshalom Houri [mailto:[email-masked]]
> Sent: Friday, August 31, 2001 7:38 AM
> To: [email-masked]
> Subject: [Simple] Partial Notifies?
> 
> 

I was actually debating this issue when doing the update of the presence
spec. Its not specified right now, all through the events framework allows
each package to define how its done. 

One model to do this is something I have proposed for other packages:

1. the notify triggered by a subscribe contains the full state
2. subsequent notifies contain only the piece thats changed (i.e., the
contact address that is different)
3. the subscriber keeps track of the cseq to see if it may have missed a
notify. If there are no gaps in Cseq, nothing was missed. If there is a gap,
something may have been missed, or else there was an intermediate challenge
or something like that. So, the subscriber re-subscribes to get a triggered
notify with full state.

A better way to handle the ordering is for the presence document itself to
contain version numbers, but that would require changes in the pidf spec. 

Since the initial SUBSCRIBE has to trigger full state anyway, idempotency of
SUBSCRIBE would argue for having full state triggered notify for refreshes
too.

-Jonathan R.

---
Jonathan D. Rosenberg, Ph.D.                72 Eagle Rock Ave.
Chief Scientist                             First Floor
dynamicsoft                                 East Hanover, NJ 07936
[email-masked]                     FAX:   (973) 952-5050
http://www.jdrosen.net                      PHONE: (973) 952-5000
http://www.dynamicsoft.com

---

From: [email-masked]
Date: Wed, 5 Sep 2001 10:33:45 +0200

Actually, there's also an approach to allow the SUBSCRIBE-triggered 
notification to be partial: 
The subscribe may include a "digest" (or checksum) of the data currently 
known to the client. The server may respond with "not modified", if the 
same digest matches the information on the server.
Only if there is some difference between the client's view of the data and 
the server's view of the data, a full trigger is returned.
Also, the digest should be returned with every "partial" update, and thus 
the client does not have to rely on CSeg numbers for data integrity (That 
is, even if the CSeq numbers are not sequential, the client may recognize 
that there's no need for full update, as in the case that it missed a 
sequence of changes to the same entity, and received only the last change 
of it).

----------------------------------------------------------------
Dror Tirosh <[email-masked]>
VocalTec Communications, Ltd
--------------------------------------------------------------

Jonathan Rosenberg <[email-masked]>
Sent by: [email-masked]
05/09/2001 08:53

        To:     "'Avshalom Houri'" <[email-masked]>, [email-masked]
        cc: 
        Subject:        RE: [Simple] Partial Notifies?

1. the notify triggered by a subscribe contains the full state
2. subsequent notifies contain only the piece thats changed (i.e., the
contact address that is different)
3. the subscriber keeps track of the cseq to see if it may have missed a
notify. If there are no gaps in Cseq, nothing was missed. If there is a 
gap,
something may have been missed, or else there was an intermediate 
challenge
or something like that. So, the subscriber re-subscribes to get a 
triggered
notify with full state.

Since the initial SUBSCRIBE has to trigger full state anyway, idempotency 
of
SUBSCRIBE would argue for having full state triggered notify for refreshes
too.

-Jonathan R.

---
Jonathan D. Rosenberg, Ph.D.                72 Eagle Rock Ave.
Chief Scientist                             First Floor
dynamicsoft                                 East Hanover, NJ 07936
[email-masked]                     FAX:   (973) 952-5050
http://www.jdrosen.net                      PHONE: (973) 952-5000
http://www.dynamicsoft.com
_______________________________________________
simple mailing list
[email-masked]
http://mailman.dynamicsoft.com/mailman/listinfo/simple

---

From: [email-masked]
Date: Wed, 5 Sep 2001 13:14:55 +0300

> each package to define how its done.

I think that it should be included since NOTIFY can become big especially
given
detail/schema/human readable comment.

gap,
challenge
triggered
> notify with full state.

I assume that the granularity will be a single tuple of the presence, and
that
there will be an operator preceding the tuple for add/delete/update.

of
> SUBSCRIBE would argue for having full state triggered notify for
refreshes

It seems that Dror's suggestion ([email-masked]) can be helpful here.

avshalom
Sametime/Lotus/IBM

                    Jonathan                                                                                         
                    Rosenberg              To:     "'Avshalom Houri'" <[email-masked]>,                         
                    <jdrosen@dynami        [email-masked]                                            
                    csoft.com>             cc:                                                                       
                                           Subject:     RE: [Simple] Partial Notifies?                               
                    05/09/2001                                                                                       
                    09:53                                                                                            

-Jonathan R.

---

---

From: Jonathan Rosenberg <[email-masked]>
Date: Tue, 18 Sep 2001 07:58:38 -0400

This thread fell on the floor, but its a real important one and I want to
get it going again. Its probably the biggest open issue for the presence
spec, which is currently in wglc, so addressing it is really a higher
priority than the IM session discussion.

I think that partial updates is probably a really good thing. I'd like to
make sure it is adequately supported in the right way.

Now, the question is, where does such support belong? Is it a per-package
thing? Or is it something in the sip-events framework? I would argue that
each package be able to define whether it does or doesn't use partial
notifies, but that the mechanism for doing them be shared across all
packages. For example, if we add a header like Last-Data-Received: with a
hash of the body, as Dror had proposed, I think this header belongs in the
sip-events specification.

I believe the requirements for the partial notifications are the following:

1. the subscribe request have a way for the subscriber to indicate what
version they have, so that the notify only contain a delta from that version
(indeed, perhaps the notify isn't even sent if the version the subscriber
has is up to date)

2. the notify have a way to indicate what version of the document the
subscriber will have once the patch is applied

3. the notify have a way to indicate what version the of the document the
subscriber has to apply the patch against (i.e, the old version)

4. the "patch" be in a format that is independent of the format of the
presence document. 

Number 4 is important, I think, to avoid needing to specify updates and
partial notifies within every event document format. We just do it once, and
then each event package doesn't need to ever worry about it again. 

Anders Kristensen had pointed out to me that webdav has looked at a very
similar problem, and that there are specs for deltas within http. I haven't
looked at those in detail, but they might provide a solution for us that
would allow us to reuse existing work elsewhere in IETF.

So, the quesitons to be discussed, in order, are:

1. is there consensus that we should have a solution for partial notifies in
simple?

2. is there consensus that this should be done in a general fashion as part
of the sip events specification?

3. how should it be done?

Comments?

-Jonathan R.

> From: Robert Brown [mailto:[email-masked]]
> Sent: Wednesday, September 05, 2001 4:41 PM
> To: Avshalom Houri; [email-masked]
> Subject: Re: [Simple] Partial Notifies?
> 
> 
> Watcher info can become pretty big too.  It would be nice to receive
> partials that only contained new pending watchers.
> 
> ----- Original Message -----
> From: "Avshalom Houri" <[email-masked]>
> To: <[email-masked]>
> Sent: Wednesday, September 05, 2001 4:33 AM
> > > spec. Its not specified right now, all through the events 
> framework
> allows
> >
> > > A better way to handle the ordering is for the presence 
> document itself
> to
> >
> > > contain version numbers, but that would require changes 
> in the pidf
> spec.
> >
> > >
> >

---

From: "Sean Olson (EUS)" <[email-masked]>
Date: Tue, 18 Sep 2001 12:04:53 -0500

>then each event package doesn't need to ever worry about it again. 

There are a couple of obvious choices here:

1) Use a context or unified diff
   http://www.gnu.org/software/diffutils/diffutils.html

   This is appropriate for text (XML) but not binary
   payloads.

2) Use a binary diff format like gdiff
   http://www.w3.org/TR/NOTE-gdiff-19970825.html

In either case, for smaller payloads, the diff
format may actually be larger than the original
version. If message size is an issue, then we
should allow either format to be sent depending
on the size of the patch.

Sean Olson
Ericsson Inc.

---

From: [email-masked]
Date: Fri, 21 Sep 2001 18:00:15 +0300

Is the partial silence can be considered as a consensus given that the wglc
is today?

avshalom
Sametime/Lotus/IBM

                    Jonathan                                                                                         
                    Rosenberg              To:     "'Robert Brown'" <[email-masked]>, Avshalom Houri          
                    <jdrosen@dynami        <[email-masked]>, [email-masked]                     
                    csoft.com>             cc:     "Adam Roach (E-mail)" <[email-masked]>                   
                                           Subject:     RE: [Simple] Partial Notifies?                               
                    18/09/2001                                                                                       
                    14:58                                                                                            

1. the subscribe request have a way for the subscriber to indicate what
version they have, so that the notify only contain a delta from that
version
(indeed, perhaps the notify isn't even sent if the version the subscriber
has is up to date)

Number 4 is important, I think, to avoid needing to specify updates and
partial notifies within every event document format. We just do it once,
and
then each event package doesn't need to ever worry about it again.

1. is there consensus that we should have a solution for partial notifies
in
simple?

Comments?

-Jonathan R.

---

From: "Sean Olson (EUS)" <[email-masked]>
Date: Fri, 21 Sep 2001 10:05:38 -0500

I would like some clarification on how
this would be documented (separate I-D?) and
on whether or not this is mandatory to support
in the client / server. (I assume not)

Thanks,
Sean Olson
Ericsson Inc.

>From: [email-masked] [mailto:[email-masked]]
>Sent: Friday, September 21, 2001 10:00 AM
>To: Jonathan Rosenberg
>Cc: Adam Roach (E-mail); 'Robert Brown'; [email-masked]
>                    Rosenberg              To:     "'Robert 
>Brown'" <[email-masked]>, Avshalom Houri          
>                    <jdrosen@dynami        
><[email-masked]>, [email-masked]          
>

---

From: Robert Sparks <[email-masked]>
Date: Fri, 21 Sep 2001 11:21:06 -0400

To help me understand where the group thinking is on addressing partial
notifies,
comment on the following:
 
1) We have a full-state notification mechanism that works for the presence
and
    watcher-info events. For some environments, that will be sufficient. In
others
    it may be non-optimal.
 
2) We sense a need for partial-state notification of one or both of those
packages,
    and suspect that a general cross-package framework supporting the
partial-state
    concept would be better than having individual packages solve the
problem in
    different ways.
 
Proposal: We complete the full-state path we started on, so that we have a
concrete
solution in place. We work in SIP to develop the framework. We then return
and develop
packages in simple (partial-*) using that framework.
 
RjS

-----Original Message-----
From: Sean Olson (EUS) [mailto:[email-masked]]
Sent: Friday, September 21, 2001 10:06 AM
To: [email-masked]'; Jonathan Rosenberg
Cc: Adam Roach (E-mail); 'Robert Brown'; [email-masked]
Subject: RE: [Simple] Partial Notifies?

Thanks, 
Sean Olson 
Ericsson Inc. 

>From: [email-masked] [ mailto:[email-masked]
<mailto:[email-masked]> ] 
>> From: Robert Brown [ mailto:[email-masked]
<mailto:[email-masked]> ] 
>> > It seems that Dror's suggestion ([email-masked]) can be 
<http://mailman.dynamicsoft.com/mailman/listinfo/simple>

---

From: Jonathan Rosenberg <[email-masked]>
Date: Fri, 21 Sep 2001 11:26:38 -0400

I think we should proceed with the presence spec as is, and instead work on
the partial notifies as an extension. There is still a lot more work that
needs to happen for partial notifies, as there are lots of ways to do it,
and they require real investigation. I think we have some time until this
becomes a dire need as well. 

I will add some text to the presence spec, though, which mentions that
extensions or new sub-packages can support partial notifies, just as a
placeholder.

OK? Please speak up with a yea or nay so we can have a real decision and
move on.

-Jonathan R.

---

---

From: "Sean Olson (EUS)" <[email-masked]>
Date: Fri, 21 Sep 2001 11:13:11 -0500

Yea!
/sean

>From: Jonathan Rosenberg [mailto:[email-masked]]
>Sent: Friday, September 21, 2001 10:27 AM
>To: Sean Olson; [email-masked]'; Jonathan Rosenberg

---

From: "Ngo, Dai (c)" <[email-masked]>
Date: Fri, 21 Sep 2001 16:33:46 +0000

Yes, I agree.

-- Dai

-----Original Message-----
From: Jonathan Rosenberg [mailto:[email-masked]]
Sent: Friday, September 21, 2001 10:27 AM
To: Sean Olson; [email-masked]'; Jonathan Rosenberg
Cc: Adam Roach (E-mail); 'Robert Brown'; [email-masked]
Subject: RE: [Simple] Partial Notifies?

-Jonathan R.

---

---

From: [email-masked]
Date: Sat, 22 Sep 2001 20:17:27 +0300

Yes.

avshalom
Sametime/Lotus/IBM

                    Jonathan Rosenberg                                                                                          
                    <[email-masked]>         To:     Sean Olson <[email-masked]>, "[email-masked]'"     
                    Sent by:                          <[email-masked]>, Jonathan Rosenberg <[email-masked]>       
                    [email-masked]        cc:     "Adam Roach (E-mail)" <[email-masked]>, "'Robert Brown'" 
                    icsoft.com                        <[email-masked]>, [email-masked]                   
                                                      Subject:     RE: [Simple] Partial Notifies?                               
                                                                                                                                
                    21/09/2001 18:26                                                                                            

-Jonathan R.

---

---

From: "Robert Brown" <[email-masked]>
Date: Mon, 24 Sep 2001 11:55:08 -0700

Yea

-----Original Message-----
From: Jonathan Rosenberg [mailto:[email-masked]] 
Sent: Friday, September 21, 2001 8:27 AM
To: Sean Olson; [email-masked]'; Jonathan Rosenberg
Cc: Adam Roach (E-mail); Robert Brown; [email-masked]
Subject: RE: [Simple] Partial Notifies?

I think we should proceed with the presence spec as is, and instead work
on
the partial notifies as an extension. There is still a lot more work
that
needs to happen for partial notifies, as there are lots of ways to do
it,
and they require real investigation. I think we have some time until
this
becomes a dire need as well. 

-Jonathan R.

---

---

From: Jonathan Rosenberg <[email-masked]>
Date: Mon, 24 Sep 2001 16:49:59 -0400

I think we have rough consensus. I added the the sentence to Section 5.8 at
the end of the following paragraph:

The times at which the {\NOTIFY} is sent for a particular subscriber,
and the contents of the body within that notification, are subject to
any rules specified by the authorization policy that governs the
subscription. This protocol in no way limits the scope of such
policies. As a baseline, a reasonable policy is to generate
notifications when the state of any of the communications addresses
changes. These notifications contain the complete and current presence
state of the presentity as known to the presence agent. Future
extensions {\MAY} be defined that allow a subscriber to request that
the notifications contain changes in presence information only, rather
than complete state.

-Jonathan R.

---

> Sent: Monday, September 24, 2001 2:55 PM
> To: Jonathan Rosenberg; Sean Olson; [email-masked]
> Cc: Adam Roach (E-mail); [email-masked]

---

From: [email-masked]
Date: Thu, 4 Oct 2001 11:52:56 +0200

Actually, I'm concerened about using generic diff algorithm. It requires 
the server to build the entire document, and perform a diff operation to 
create the partial document to send to the client.
However, the "document" returned which requires this partial update us 
actually a list of items, updated at different times.
Thus, in most cases, the server can create a list of changed items without 
rebuilding the entire list.
e.g.: generating a list of all updated items since date X can be much 
simpler than fetching the entire list
In some situations, an update counter might be easier to use than "date of 
updates".

My suggestion for partial list:
1. whenever a server returns the list to the client, it also returns an 
"update-cookie". This cookie is treated as an opaque string.
2. whenever the client wants to update its local list, it will send this 
"update-cookie" to the server.
3. the server will see whether the cookie makes sense, and will try to 
return partial update of changes since the time the cookie was generated.
4. if the cookie denotes an up-to-date list, the server will return 
nothing
5. if the server fails to parse the cookie, it will return a full update 
to the client.
6. in any case, the server returns a new "update-cookie" to the client.

Anders Kristensen <[email-masked]>
Sent by: [email-masked]
03/10/2001 02:24

        To:     "Sean Olson (EUS)" <[email-masked]>
        cc:     "'Jonathan Rosenberg'" <[email-masked]>, "'Robert Brown'" 
<[email-masked]>, Avshalom Houri <[email-masked]>, 
[email-masked], "Adam Roach (E-mail)" 
<[email-masked]>
        Subject:        Re: [Simple] Partial Notifies?

"Sean Olson (EUS)" wrote:
>
> I realize this has been pushed off to future work,
> but I thought I would throw my two cents in now.
> I think we could have a reasonable first draft
> of a partial NOTIFY mechanism completed in a
> couple of weeks.

Yup.

>
> >That sure sounds like way too much. The draft I had in mind was
> >http://www.ietf.org/internet-drafts/draft-mogul-http-delta-08.txt
> >
> >This details how various diff algorithms (textual or binary - the
> >mechanism works with either) can be used to reduce the message
> >size when
> >the client has an old version of some resource. It seems like it
> should
> >be fairly straightforward to apply the same ideas to SIP.
>
> I agree. This is much simpler. Can we make a baseline
> requirement for either vcdiff or gdiff? Both support
> binary data. gdiff seems simpler, but vcdiff supports
> compression. If I had to choose, I would mandate support
> for vcdiff.

I'd prefer a recommendation over a hard requirement for a particular
format/algorithm. I agree that vcdiff seems like the better choice.

>
> >So here's a sketch of how this might work in SIP.
> >
> >Clients would indicate support for one or more delta encoding
> >mechanisms
> >in SUBSCRIBEs by listing extension token 'delta' in a Supported
> header
> >and the actual "instance manipulations" supported in an A-IM header
> >(A-IM stands for Accept-Instance-Manipulations and is defined in the
> >http draft as is the IM header used in NOTIFYes):
> >
> >        SUBSCRIBE sip:[email-masked] SIP/2.0
> >        Supported: delta
> >        A-IM: diffe, vcdiff
> >        Event: presence
> >        ...
>
> Can we use the A-IM: header as an implicit indicator
> of support for delta encoding?

Sounds reasonable.

>
> >the server would make a note of supported alg's in the subscription
> >"record".
> >
> >The server then has to know what version of a particular subscription
>
> >doc a watcher has received, and when it sends a NOTIFY for a watcher
> it
> >may send only a delta if that guy has indicated support for it, e.g.:
>
> >
> >        NOTIFY sip:[email-masked] SIP/2.0
> >        Require: delta
> >        IM: diffe
> >        Delta-Base: "abc"
> >        Etag: "ghi"
> >        Event: presence
> >        Content-Type: application/cpim-pidf+xml
> >
> >        ...
> >
> >Unlike the http case there's no request in which a version number/tag
>
> >can be carried so presumably the server has to just know what
> >version of
> >the presence doc (or whatever) the client knows about, or else assume
>
> >that it knows about the previous version.  If for some reason
> >the client
> >doesn't, it would return some error response which would tell
> >the server
> >to send the whole resource/document. The error response would also
> list
> >the A-IM and Supported header as appropriate.
>
> I assume we can do something like:
> SUBSCRIBE sip:[email-masked]?Etag="ghi" SIP/2.0
> to at least indicate what version the client has at the
> time of subscription. The first NOTIFY could then include
> either the full state or the appropriate delta encoding to
> bring the client in sync with the server. Or use a
> "If-None-Match:" header as in HTTP/1.1.

I like the idea of the client telling the server which version it has in
the SUBSCRIBE but I think it's preferable to put the version number in
an ETag header as in HTTP.

>
> I don't see a reason to return an error response to the server.
> Do a one-time SUBSCRIBE with no "A-IM" header instead. It costs
> two extra messages, but simplifies the life of the presence server.
>
> >
> >The Delta-Base header gives the version of the resource that the
> delta
> >should be applied to (and which the client is assumed to possess).
> The
> >ETag gives an identifier for the new resource.
>
> Sounds good.
>
> >
> >A presence server that doesn't know about the delta extension just
> >ignores the A-IM header and sends the full update every time.
>
> Sounds reasonable. Some things that need to be fleshed out include:
>
> 1) How would the server indicate in the initial NOTIFY that the
>    client state is already up-to-date? (HTTP 1.1 uses a
>    "304 Not Modified" response code. Do we want to do something
>    similar?) This would be particularly useful for a fetch operation.

It may be enough to send a NOTIFY with identical values in the ETag and
Delta-Base headers and an empty body (or whatever ).

>
> 2) Do we want to allow compression manipulations in addition to the
>    delta encoding? Or can we just apply Content-Encodings on top
>    of the delta encoding? I assume the later is fine.

I'm not sure why HTTP includes both but I see no reason for excluding
compressions. There's no requirement to support any, of course.

> /sean

Anders

---

From: "Sean Olson (EUS)" <[email-masked]>
Date: Thu, 4 Oct 2001 11:22:58 -0500

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
Sent: Thursday, October 04, 2001 4:53 AM

>Actually, I'm concerened about using generic diff algorithm. 
>It requires the server to build the entire document, and perform a diff
>operation to create the partial document to send to the client. 

Actually it doesn't. This depends on how the server decides
to implement diffs. It could keep a history ala RCS that makes
it easy to build diffs without having to build the entire document
for every NOTIFY. It builds it once (which it needs to do to satisfy
full updates anyways), then computes a diff with the previous version.
Successive partial NOTIFYs (against the last or earlier versions) can quickly
be built.

>rebuilding the entire list. e.g.: generating a list of all updated items 
>since date X can be much simpler than fetching the entire list
>In some situations, an update counter might be easier to use than "date of updates".

A timestamp is probably not a good idea as you mention. There are
a number of ways to compute a "ETag"-like value for versioning purposes
including virtual clocks. 

>3. the server will see whether the cookie makes sense, and will try to return
>   partial update of changes since the time the cookie was generated.

In what format will the server return the partial update? Will it be
XML? If XML, will it be WFF? Will it pass a validating parser? 
It can be difficult to do compact partial updates that satisfy these properties.
Since compactness is the goal of partial notifies, a generic diff algorithm
seemed more appropriate.
 
>4. if the cookie denotes an up-to-date list, the server will return nothing 
>5. if the server fails to parse the cookie, it will return a full update to the client. 

The "update-cookie" concept is fine. This is exactly what the ETag: header
provides. I think the issue you are raising is how we supply diffs.
Do we use a generic diff algorithm or a "diff" that is tailored to the
format of the information we are sending in the NOTIFY (e.g. application/cpim-pdif+xml)?

Arguments for a generic diff algorithm include:
1) Possible simplicity of implementation (easy to understand and debug)
2) Applicable across applications that use NOTIFY, i.e.
   it won't be tied to presence
3) Could even be applied by intermediate proxies that don't
   understand the content of the NOTIFY payload. Imagine a
   server farm where you have a master server handling full
   updates and a cluster of servers handling partial updates.

Regards,
Sean Olson
Ericsson Inc.