Subject: [alto] Fw: Incremental Update/SSE Key Design Issue 2: sending full resources at the beginning of stream

From: [email-masked]
Date: Fri, 24 Oct 2014 22:42:29 +0800 (GMT+08:00)

Hi Xiao,

My suggestion is that if we can adopt your window design into the most costly solution to make all version can be acceptable. We assume V0 is the first version and Vkn is the last version, and the server keeps V0->Vk, Vk->V2k,..., V(n-1)k->Vkn.

The problem here i think is the size of patch between Vi->Vj and the sum of Vi->V(i+1), V(i+1)->V(i+2),... V(j-1)->Vj. We set the first one is S1 and the second one is S2: 1. if each patch does not overlap with others, S1 = S2; 2. else, S1 < S2.

However, as versions change, the difference between Vi and Vj can be huge (the size of Vi->Vj is also huge correspondingly), which makes Vi->Vj is not suitable as a patch. So, i think if we can get the best value of k, we can make server not reject any request while maintaining high performance.

Is this right?

Thanks,
Xin 

From: [email-masked]
Date: Thu, 23 Oct 2014 06:37:12 -0400
To: [email-masked]
CC: [email-masked]
Subject: [alto] Incremental Update/SSE Key Design Issue 2: sending full resources at the beginning of stream

Hi folks,

Another design question is whether we should include the full resource (e.g. full network map/cost map) when the SSE stream is first initiated.

The advantage of doing so is that the server does not need to keep any old version of the resources. The full map the server first sends to the client will always be updated, and the updates come when they become available.

It also has the following disadvantage:
(1) Modularity: SSE streams are for incremental updates, it carries a different functionality than full resource requests;
(2) Space efficiency: to reduce the payload for the SSE stream, it would be nice not to do that. It is conceivable that the client fetches the full resource somewhere else and then ask for incremental updates via HTTP SSE stream.

If we do not send the full resource via SSE, the client needs to request for incremental updates with resource-id and version-tag. there are two possible extreme solutions:
(1) the laziest: The server accepts the request that have the most recent version-tag; if the version-tag is not the most update version, the server simply rejects this request.

(2) the most costly: The server remembers all history of all resources, when the client requests with a resource-id and vtag, the server accepts the connection, and immediately send out patches to "catch the client up."

Example:
Notate version tags as vi, e.g. v0, v1, v2, etc. And the patches that updates vi to vj as patch(vi->vj) where vi is the old tag and vj is the new tag.

Say the current network map is v3. Client 1 requests incr updates with {"resource-id":"my-networkmap", "tag":"v0"} and Client 2 requests incr updates with {"resource-id":"my-networkmap", "tag":"v3"}. The lazy server would reject the request from client 1 and accepts that from client 2. The costly server would accept both request and send patch(v0->v3)

Another possible solution is a hybrid of the two extremes. The server keeps a patch that can update the resource from vi to vj, and accepts requests that has vtag vk such that i<=k<=j.

Because of the JSON merge-patch replacement property, applying patch(vi->vj) would update vk to vj. No matter what vtag vk the request comes in with, the server accepts if i<=k<=j, and immediately sends patch(vi->vj) via the stream. This will update the client's resource to the most updated version. The subsequent updates will be pushed as they become available.The window of [i, j] can be determined by the server, according to time or storage constraints.

You comments would be much appreciated. Thank you!

Best,
Xiao

_______________________________________________ alto mailing list [email-masked] https://www.ietf.org/mailman/listinfo/alto

---

From: Wendy Roome <[email-masked]>
Date: Fri, 24 Oct 2014 15:40:35 -0400

That can work for Network Maps, but I don't think it is a good idea for
Cost Map updates. Here is why.

First, Network Maps already are versioned, and although the protocol does
not require it, the assumption is that Network Maps do not change very
often. So when a client requests an Update Stream, the client could give
the vtag of its current Network Map. If that is the latest version, the
server can omit sending the full Network Map.

But Cost Maps don't have version tags, at least not yet, so that trick
doesn't work for them. And I do not think we should add version tags to
Cost Maps if we can avoid them. Why? Because vtags force changes to happen
in discrete quantum jumps. Right now, conceptually, anyway, cost map
changes trickle in as a continuous process. Cost PID1=>PID2 changes. Cost
PID47=>PI9 changes. Etc. But if we have to assign vtags to Cost Map
versions, then the server has to somehow hold updates until it has enough
to justify assigning a new tag.

Consider how this would work without Cost Map vtags. An update stream
would send updates for a Network Map and its associated Cost Maps (or
perhaps a subset of those Cost Maps). FThe ALTO server would have an
update buffer for each update stream. When a cost changes, a central
thread in the server appends the new cost to the buffer of every stream
that subscribes to that cost map. Each update stream has its own sender
thread (in case the tcp/wrote blocks). Each thread would batch up the
individual PID->PID cost updates into merge-patch messages and send them
to its client. Each sender thread would separately decide how many costs
to fold into one merge-patch update message; there is no "master clock².

I think that is much more modular than trying to assign versions to every
cost update and get every stream to operate in lock-step.

And yes, the downside is that if a stream terminates abnormally, the
server has to resend the full cost map. While that isn't esthetically
pleasing, it is simple. And unless we expect streams to fail frequently, I
vote for simplicity.

	- Wendy Roome

On 10/23/2014, 11:08, "[email-masked]" <[email-masked]>
wrote:

>From: Xiao SHI <[email-masked]>
>Subject: [alto] Incremental Update/SSE Key Design Issue 2: sending
>	full resources at the beginning of stream
>
>Hi folks,
>
>Another design question is whether we should include the full resource
>(e.g. full network map/cost map) when the SSE stream is first initiated.
>
>The advantage of doing so is that the server does not need to keep any old
>version of the resources. The full map the server first sends to the
>client
>will always be updated, and the updates come when they become available.
>
>(1) Modularity: SSE streams are for incremental updates, it carries a
>different functionality than full resource requests;
>(2) Space efficiency: to reduce the payload for the SSE stream, it would
>be
>nice not to do that. It is conceivable that the client fetches the full
>resource somewhere else and then ask for incremental updates via HTTP SSE
>stream.
>
>
>If we do not send the full resource via SSE, the client needs to request
>for incremental updates with resource-id and version-tag. there are two
>possible extreme solutions:
>(1) the laziest: The server accepts the request that have the most recent
>version-tag; if the version-tag is not the most update version, the server
>simply rejects this request.
>(2) the most costly: The server remembers all history of all resources,
>when the client requests with a resource-id and vtag, the server accepts
>the connection, and immediately send out patches to "catch the client up."
>
>
>*Example:*
>Notate version tags as vi, e.g. v0, v1, v2, etc. And the patches that
>updates vi to vj as patch(vi->vj) where vi is the old tag and vj is the
>new
>tag.
>
>Say the current network map is v3. Client 1 requests incr updates with
>{"resource-id":"my-networkmap", "tag":"v0"} and Client 2 requests incr
>updates with {"resource-id":"my-networkmap", "tag":"v3"}. The lazy server
>would reject the request from client 1 and accepts that from client 2. The
>costly server would accept both request and send patch(v0->v3)
>
>
>Another possible solution is a hybrid of the two extremes. The server
>keeps
>a patch that can update the resource from vi to vj, and accepts requests
>that has vtag vk such that i<=k<=j.
>
>Because of the JSON merge-patch replacement property, applying
>patch(*vi*->vj)
>would update vk to vj. No matter what vtag vk the request comes in with,
>the server accepts if i<=k<=j, and immediately sends patch(vi->vj) via the
>stream. This will update the client's resource to the most updated
>version.
>The subsequent updates will be pushed as they become available.The window
>of [i, j] can be determined by the server, according to time or storage
>constraints.
>