Subject: Re: [alto] JSON Patch vs. custom representation for incremental updates

From: Wendy Roome <[email-masked]>
Date: Wed, 09 Jul 2014 15:14:56 -0400

Here's why I think we need a representation for incremental updates that's
tailored to the ALTO data model, rather than using the general JSON Patch
representation.

As I understand it, JSON is a standardized way for a computer to create a
serialized, machine-independent representation of a data structure, send
that serialization over a stream to another computer, and have the other
computer recreate that data structure. This is a simplification, of
course, but I believe that's the goal.

JSON Patch is a standard way to represent the changes to a data structure,
ship them to another computer, and have a JSON Patch library on the other
computer automatically update the remote data structure, with little
additional work for either computer.

That's a wonderful goal. Unfortunately that has three problems when we
apply it to ALTO: (1) JSON does not have data representations that
directly correspond to the ALTO data structures, so JSON cannot capture
the semantics of the ALTO data. (2) As a result, JSON Patch is an
inefficient representation of the legal changes. (3) For the clients who
need incremental update, that inefficiency is a deal breaker.

Let's take the last first. What clients need incremental update? Clients
who keep full cost and network maps. But what clients would do that? After
all, clients care about costs between endpoints. Clients don't really care
about PIDs. PIDs are just an abstraction to make the space of endpoints
more manageable. For most ALTO clients, the Endpoint Cost Service (ECS) is
exactly what they want, and they'd much rather use that than go though the
hassle of downloading the maps, searching them, and keeping them
up-to-date.

So why would a client use full maps? Because the client needs to lookup
costs very quickly, and cannot tolerate the delay of querying the ALTO
Server. For example, a P2P tracker must select, out of 5,000 peers, the 50
with the lowest cost to a given peer. And a tracker might do that 10 times
a second.

As for the second point, incremental update is only necessary for large
maps. If a map only has 25 PIDs, why bother? Just download a new version.
What do I mean by "large"? A Network Map with 5,000 PIDs, 250,000
prefixes, and up to 25,000,000 cost points.

Yes, that seems huge. Will anyone ever build that large an ALTO server? I
don't know. But I think a lot of us remember when the ipv4 address space
seemed infinite. Or when a 100 meg disk was big.

Now consider point 1: JSON does not do a good job of representing the ALTO
data. Take Cost Maps. A Cost Map is a square sparse matrix of numbers
indexed by strings. JSON has no such data structure, so in JSON we
represent that as a lookup table of lookup tables of costs. But that
consumes a lot more space than necessary. Furthermore, at least for most
cost metrics, the values are low precision (do you really think that a
routingcost of 49.99999 is any better than a cost of 50?), and the string
indexes -- the PID names -- don't change very often.

So if a client needs to handle a 5,000 x 5,000 Cost Map, and lookup costs
in microseconds, the client convert the PID names to numbers from 0 to
N-1, so it can use a sparse numerically indexed array, and it stores the
costs single-precision floats, not double-precision, to save 100 megs of
RAM.

The mismatch is even worse for Network Maps. A Network Map is a lookup
table from PID names to sets of prefixes. ALTO has lookup tables, but
doesn't have sets, so we represent the sets by arrays. But this confounds
JSON Patch, because order matters in arrays. Furthermore, the JSON
representation does not capture the semantics that a prefix can only be in
one PID. So if the server moves 1.2.3.4 from PID1 to PID2, JSON Patch
would need the following update commands:

     add 1.2.3.4 at index 17 in the array for PID1
     delete index 6 from the array for PID2

But if we know the real semantics of ALTO Network Maps, we can represent
that update as:

     add 1.2.3.4 to PID1

The delete from PID2 is implicit.

Here's the bottom line: Clients who need incremental update will NOT store
data in a format that looks like JSON data model. Such a client will read
the JSON data, convert it in a totally different form, and then discard
the original JSON. If we use JSON Patch to represent deltas, a client
would NEVER be able to use a standard JSON library to automatically apply
the patches. Instead, the client would need custom code that understands
every possible JSON Patch update command, and figures out how to apply
them to the client's representation of the data. And the client may be
forced to use a suboptimal data structure to allow that (e.g., store
prefixes as arrays rather than sets).

This does not simplify anything; it just makes more work for the client.

    - Wendy Roome

---

From: Jan Seedorf <[email-masked]>
Date: Thu, 10 Jul 2014 14:26:08 +0000

Hi Wendy,

What about future, new ALTO services (e.g. as proposed in http://tools.ietf.org/html/draft-seedorf-cdni-request-routing-alto-07)?

I am not a fan of JSON patch, but a solution for incremental updates based on JSON patch should be much more future-proof with respect to new, future ALTO services that convey JSON objects other than network/cost maps, right?

 - Jan

> -----Original Message-----
> From: alto [mailto:[email-masked]] On Behalf Of Wendy Roome
> Sent: Wednesday, July 09, 2014 9:15 PM
> To: IETF ALTO
> Subject: Re: [alto] JSON Patch vs. custom representation for incremental
> updates
> 
> _______________________________________________
> alto mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/alto

---

From: Sebastian Kiesel <[email-masked]>
Date: Thu, 10 Jul 2014 21:23:36 +0200

Jan,

Wendy's arguments seem very well thought-out to me.  
Why not define a specific solution for incremental updates of network
and cost maps (i.e., the stuff we have in the base protocol) and then,
each time we specify an extension, define either a specific update
mechanism for it or specify that json patch is to be used for it?!

Sebastian

---

From: Sebastian Kiesel <[email-masked]>
Date: Thu, 10 Jul 2014 21:36:22 +0200

Dear all,

> prefixes, and up to 25,000,000 cost points.

A full 5000x5000 cost map would be in the order of 130 MB gzipped json
(see "The size of the cost map" thread on the ALTO list Fri, 22 Mar 2013).

do we have any idea whether 5000 PIDs is a realistic assumption for
foreseeable deployments?

Thanks
Sebastian

---

From: Wendy Roome <[email-masked]>
Date: Thu, 10 Jul 2014 16:20:50 -0400

I respectfully disagree that using JSON Patch for cost & network map
incremental updates would make it any easier to provide incremental update
for future services.

You¹d have a point if JSON Patch solved the whole incremental update
problem without any additional protocol specification. E.g., if we could
just say, ³For incremental update, use JSON Patch [RFC 6902]², and Shazam!
we have incremental update.

Unfortunately it¹s not that easy. The format used to represent the deltas
‹ JSON Patch vs service-specific update commands ‹ is only a small part of
the incremental update mechanism. For an incremental update service to a
map, we have to specify how the client locates the service (e.g., its
media type), how the client tells the server what version the client has
now, etc, etc. 

Of course, if it turns out that JSON Patch is a good way to represent the
deltas for the CDN services you mentioned, then the associated incremental
update service an use JSON Patch. But we still need to define that
service. And that would require a new RFC, or at least a section in a new
RFC.

BTW, one of the problems I see with JSON Patch is that JSON does not
define a ³set² type, so everyone uses arrays instead. Your CDN service
example has several arrays that I believe are really sets. Arrays are fine
for exchanging sets, but they make it difficult for any JSON library to
automatically create an efficient JSON Patch for the changes between
versions. For example, if the values are permuted into a different order,
the set hasn¹t changed ‹ but the array is totally different. So JSON Patch
would have to update the whole thing, as opposed to saying ³no change."

	- Wendy

On 07/10/2014, 10:26, "Jan Seedorf" <[email-masked]> wrote:

>Hi Wendy,
>
>What about future, new ALTO services (e.g. as proposed in
>http://tools.ietf.org/html/draft-seedorf-cdni-request-routing-alto-07)?
>
>I am not a fan of JSON patch, but a solution for incremental updates
>based on JSON patch should be much more future-proof with respect to new,
>future ALTO services that convey JSON objects other than network/cost
>maps, right?
>
>- Jan
>

---

From: Wendy Roome <[email-masked]>
Date: Thu, 10 Jul 2014 16:37:32 -0400

If an ALTO Server were to provide a global view of the whole internet,
wouldn¹t its PIDs be on the scale of Autonomous Systems ‹ AS¹s? Granted
not all AS¹s are public, and some could be combined. But aren¹t there
close to 60k AS¹s?

That¹s where I got the idea of 5,000 PIDs.

And what seems realistic now may not be realistic 10 years from now. How
long did it take to realize that ASNs had to be 32 bits, not 16?

And for that matter, I remember in the early days of defining domain
names, after we defined the important TLDs like .edu, .org, .net, .gov and
.mil, somebody suggested adding ³.com² just in case some commercial
enterprise wanted a domain name. Of course, we never expected more than a
handful of companies would take us up on that.

	- Wendy

---

From: Sebastian Kiesel <[email-masked]>
Date: Thu, 10 Jul 2014 22:58:03 +0200

> That¹s where I got the idea of 5,000 PIDs.

I doubt that "one ALTO PID := one AS number" is a reasonable scheme
for an ALTO server providing a global view on the internet.

On the one hand, the number of AS is quite high, on the other hand,
there are major carriers that have their residential DSL, 3G wireless,
corporate customers, and data centers in the same AS.

Maybe something like  
"100 geograpic locations on the world" X "10 classes of access link"
= 1000 PIDs would be more realistic?  Not sure.
Anyone planning to deploy an Internet-wide ALTO service who wants to
share her or his plans wrt. network map layout with us?

> long did it take to realize that ASNs had to be 32 bits, not 16?

I am tempted to say that in 10 years, downloading a 130 MB file every
some seconds will probably not be considered a significant burden or
waste of ressources, at least for a large P2P tracker, CDN control node,
etc. :)

Thanks
Sebastian

---

From: Jan Seedorf <[email-masked]>
Date: Fri, 11 Jul 2014 08:50:05 +0000

Wendy, Sebastian,

I see your points. The thing that worries me is that one of the arguments _not_ to use ALTO for CDNI-FCI in the CDNI WG has been that it will take some time for incremental updates to be available for ALTO. We have always argued that incremental updates for ALTO are "on the way" (which indeed is/was the case). Now, from that perspective, if the "default" ALTO solution for incremental updates would only work for classic network/cost maps, and would not work for our ALTO CDNI FCI service, that is not desirable.

On the other hand, there are some differences when using ALTO for CDNI compared to P2P that have implications on incremental updates: CDNI-FCI is CDN service provider to CDN service provider (so you can expect a high capacity link between the two); the number of PIDs in a CDNI FCI network map footprint is likely much smaller than 5000; the overall size of a CDNI FCI object-format-map is likely much, much smaller than a cost map for a large ISP. All of these differences actually imply that incremental updates are not so crucial for the CDNI case than for e.g. the P2P case: if a uCDN has e.g. 4 dCDNs, the overall amount of data being sent over the network is much smaller than if an ISP has 200.000 P2P users, so fetching the complete JSON object each time may be ok for CDNI-FCI.

So we may have good arguments for saying ALTO network/cost map service has a specific incr. update solution, and ALTO CDNI FCI service uses JSON patch.

I guess I would like to hear other opinions ...

 - Jan

> From: Wendy Roome [mailto:[email-masked]]
> Sent: Thursday, July 10, 2014 10:21 PM
> To: Jan Seedorf; IETF ALTO
> < JSON Patch vs service-specific update commands < is only a small part of
> the set hasn¹t changed < but the array is totally different. So JSON Patch

---

From: "Scharf, Michael (Michael)" <[email-masked]>
Date: Fri, 11 Jul 2014 09:24:21 +0000

> do we have any idea whether 5000 PIDs is a realistic assumption for

Indeed, 5000 seems like an extreme case. Yet, I think one could really end up there, depending on how ALTO is used.

For instance, let's assume an ALTO use case like draft-scharf-alto-vpn-service for a large enterprise with many branches. As argued in the draft, only could possibly use one PID for each VPN endpoint. 

In that case, 5000 is not entirely unrealistic. As a random data point, Bank of America is reported to have 5,377 branches in the US. Other large organizations (e.g., retailers) may have a similar order of magnitude of branches. A L2VPN or L3VPN could be used to interconnect such branches.

Obviously, there are certain ways to reduce the network/cost size in such a scenario, e.g., by introducing a hierarchy, or by topology encoding (for cost map). Also, I doubt that an application would really require an accurate cost map entry for any given combination of PIDs. Thus, 5000 looks like a kind of worst-case scenario.

Michael

---

From: Sebastian Kiesel <[email-masked]>
Date: Fri, 11 Jul 2014 11:30:15 +0200

On Fri, Jul 11, 2014 at 09:24:21AM +0000, Scharf, Michael (Michael) wrote:
> Indeed, 5000 seems like an extreme case. Yet, I think one could really
> end up there, depending on how ALTO is used.
> 
> For instance, let's assume an ALTO use case like
> draft-scharf-alto-vpn-service for a large enterprise with many
> branches. As argued in the draft, only could possibly use one PID for
> each VPN endpoint. 
> 
> In that case, 5000 is not entirely unrealistic. As a random data
> point, Bank of America is reported to have 5,377 branches in the US.
> Other large organizations (e.g., retailers) may have a similar order
> of magnitude of branches. A L2VPN or L3VPN could be used to
> interconnect such branches.
> 
> Obviously, there are certain ways to reduce the network/cost size in
> such a scenario, e.g., by introducing a hierarchy, or by topology
> encoding (for cost map). Also, I doubt that an application would
> really require an accurate cost map entry for any given combination of
> PIDs. Thus, 5000 looks like a kind of worst-case scenario.

In this use case, would you really have a full(!) 5000x5000 matrix?
Or would it be more like a sparse matrix, defining cost only for 
5000 branch offices X 100 data centers, 
while most (all?) other costs (i.e., branch office to branch office) are
"default"?

Thanks,
Sebastian

---

From: "Scharf, Michael (Michael)" <[email-masked]>
Date: Fri, 11 Jul 2014 09:49:44 +0000

> while most (all?) other costs (i.e., branch office to branch office)

Sure, the non-default-entries in such a matrix could be sparse (and topology encoding could help). And, indeed, as already mentioned, I'd guess that one would mainly be interested in a small subset of the cost map. As a result, 5000x100 may be more realistic than 5000x5000. But we still have O(5000) PIDs.

Michael

---

From: Sebastian Kiesel <[email-masked]>
Date: Fri, 11 Jul 2014 12:05:49 +0200

On Fri, Jul 11, 2014 at 09:49:44AM +0000, Scharf, Michael (Michael) wrote:
> Sure, the non-default-entries in such a matrix could be sparse (and
> topology encoding could help). And, indeed, as already mentioned, I'd
> guess that one would mainly be interested in a small subset of the
> cost map. As a result, 5000x100 may be more realistic than 5000x5000.
> But we still have O(5000) PIDs.

Basically, it is not the number of PIDs that makes the map big, it is
the number of non-default values.  In our JSON encoding, 
a full 5000x5000 matrix is 50 times bigger on the wire 
than a 5000x5000 matrix that only defines 500000 values and leaves all
others as "default".

Sebastian

---

From: Sebastian Kiesel <[email-masked]>
Date: Fri, 11 Jul 2014 14:16:22 +0200

Jan,

after quickly reading over draft-seedorf-cdni-request-routing-alto-07
I was scratching my head and asking myself: why do you call this an ALTO
service?  I mean, it is json-over-http and it deals with IP prefixes and
an optimization task, sure, but it does not seem to rely heavily on
mechanisms of the ALTO base protocol, such as the PID concept or the
network map.  I don't want to start a fruitless discussion on how much
ALTO needs to be in a proposal to call it an ALTO extension, but to me
your proposal seems to be rather loosely coupled to the base protocol.

I think it would be worth re-thinking whether your problem really needs
a new map type.  If it could be solved using network map, cost map,
endpoint properties, and maybe PID properties
(draft-roome-alto-pid-properties) in conjunction with some new cost
metrics and/or endpoint propertiy types, you could benefit from the
generic incremental update mechanism, no matter how it will look like.

Just my $0.02
Sebastian

On Fri, Jul 11, 2014 at 08:50:05AM +0000, Jan Seedorf wrote:
> Wendy, Sebastian,
> 
> I see your points. The thing that worries me is that one of the
> arguments _not_ to use ALTO for CDNI-FCI in the CDNI WG has been that
> it will take some time for incremental updates to be available for
> ALTO. We have always argued that incremental updates for ALTO are "on
> the way" (which indeed is/was the case). Now, from that perspective,
> if the "default" ALTO solution for incremental updates would only work
> for classic network/cost maps, and would not work for our ALTO CDNI
> FCI service, that is not desirable.
> 
> On the other hand, there are some differences when using ALTO for CDNI
> compared to P2P that have implications on incremental updates:
> CDNI-FCI is CDN service provider to CDN service provider (so you can
> expect a high capacity link between the two); the number of PIDs in a
> CDNI FCI network map footprint is likely much smaller than 5000; the
> overall size of a CDNI FCI object-format-map is likely much, much
> smaller than a cost map for a large ISP. All of these differences
> actually imply that incremental updates are not so crucial for the
> CDNI case than for e.g. the P2P case: if a uCDN has e.g. 4 dCDNs, the
> overall amount of data being sent over the network is much smaller
> than if an ISP has 200.000 P2P users, so fetching the complete JSON
> object each time may be ok for CDNI-FCI.
> 
> So we may have good arguments for saying ALTO network/cost map service
> has a specific incr. update solution, and ALTO CDNI FCI service uses
> JSON patch.
>

---

From: Wendy Roome <[email-masked]>
Date: Fri, 11 Jul 2014 13:18:49 -0400

Jan,

I think it is misleading to wait for ³incremental updates to be available
in ALTO². Incremental updates will never be available in ALTO as a whole.
Instead, incremental updates will be available for the various ALTO
services separately. Just the various ALTO services are independent (more
or less), incremental updates for those services will also be independent.
Providing incremental update for one ALTO service will not automatically
provide it for the others. Notice that in
https://datatracker.ietf.org/doc/draft-roome-alto-incr-updates/ the
incremental update mechanisms for network and cost maps are completely
separate, and an ALTO server can implement one without the other.

Put it another way: If incremental update for network & cost maps were
available right  now, they would not provide incremental update for the
new ALTO services you proposed. You would still have to define incremental
update yourself.

And while I didn¹t look over the CDNI-FCI data in detail, it seemed like
it was a relatively small amount of data. 5kbytes, maybe 10k tops. After
all, the service just provides information for a few local servers, not
for the entire internet, doesn¹t it? And I suspect the
mean-time-between-changes is on the the order of minutes, not seconds. So
my guess is that downloading the full map whenever it changes costs (say)
5kbytes/5min. Incremental update might cut that to (say) 1kbytes/5min. But
is the hassle of incremental update really worth saving 4kb every 5
minutes?

	- Wendy 

On 07/11/2014, 04:50, "Jan Seedorf" <[email-masked]> wrote:

>Wendy, Sebastian,
>
>I see your points. The thing that worries me is that one of the arguments
>_not_ to use ALTO for CDNI-FCI in the CDNI WG has been that it will take
>some time for incremental updates to be available for ALTO. We have
>always argued that incremental updates for ALTO are "on the way" (which
>indeed is/was the case). Now, from that perspective, if the "default"
>ALTO solution for incremental updates would only work for classic
>network/cost maps, and would not work for our ALTO CDNI FCI service, that
>is not desirable.
>
>compared to P2P that have implications on incremental updates: CDNI-FCI
>is CDN service provider to CDN service provider (so you can expect a high
>capacity link between the two); the number of PIDs in a CDNI FCI network
>map footprint is likely much smaller than 5000; the overall size of a
>CDNI FCI object-format-map is likely much, much smaller than a cost map
>for a large ISP. All of these differences actually imply that incremental
>updates are not so crucial for the CDNI case than for e.g. the P2P case:
>if a uCDN has e.g. 4 dCDNs, the overall amount of data being sent over
>the network is much smaller than if an ISP has 200.000 P2P users, so
>fetching the complete JSON object each time may be ok for CDNI-FCI.
>
>has a specific incr. update solution, and ALTO CDNI FCI service uses JSON
>patch.
>

---

From: Wendy Roome <[email-masked]>
Date: Fri, 11 Jul 2014 13:44:54 -0400

I don¹t know whether any ALTO server could maintain a full 5000x5000 cost
matrix, but I can give you a very reasonable example of a client who like
one.

Consider a large P2P tracker. It has thousands of peers for each file,
scattered over the planet. It gets lots of requests from peers, who are
also scattered all over the planet. When a peer in New York asks for
peers, the tracker needs the costs from New York to every other peer. And
the tracker needs detailed local costs for the New York area: for a New
York peer, Boston is better than Chicago, and Chicago is better than San
Francisco. But to a New York peer, Tokyo & Kyoto are the same.

But when the tracker gets a request from a Tokyo peer, the tracker needs
detailed local cost data for Tokyo & Japan. For that peer, Tokyo is better
than Kyoto ‹ and Boston and New York are the same.

So a large P2P tracker love to have a fully populated 5k x 5k cost matrix.

	- Wendy

---

From: Sebastian Kiesel <[email-masked]>
Date: Fri, 11 Jul 2014 19:56:31 +0200

Hi Wendy,

this is very true!  But the question is, from where does the tracker get
the 5000x5000 matrix, if there is no single ALTO server that provides it?

One answer may be that the tracker will have to query multiple ALTO
servers and assemble the map on its own. (That's why I am working on and
lobbying for cross-domain discovery alias 3pdisc for quite a long
time...)  But in this case the maps pulled from the individual ALTO
servers would be smaller, and the tracker could control the update 
intervals individually.

Sebastian

---

From: Wendy Roome <[email-masked]>
Date: Fri, 11 Jul 2014 14:27:40 -0400

Sebastian,

How would you see the tracker doing that? Would it really merge maps from
N separate ALTO servers into one master map? Given that each ALTO server
can define PIDs however it wants, is that even possible?

Or do you see the tracker as maintaining copies of each of the N ALTO cost
maps separately, and using the one that is closest to the requesting peer?
Eg, when a New York peer asks for peers, the tracker uses the cost map
from the ALTO server nearest New York. For a Tokyo peer, the tracker uses
the cost map from the ALTO server nearest Tokyo. Then the individual maps
wouldn¡¯t be as large. But there would be a lot of them. And the tracker
would have to decide which map to use. Perhaps it could use the network
map which has the finest detail around the requesting peer¡¯s address?
Whatever that means?

Yet another approach would be for the tracker to require each peer to
provide the uri for its local ALTO server. The tracker would send an ECS
to that ALTO server to evaluate the costs of the other peers. Of course,
then the tracker must make an ALTO query for every peer request, which
will add a lot of latency to each request.

Although ... heh heh ... that could be one way for a tracker to do
cross-domain ALTO server discovery!

	- Wendy

On 07/11/2014, 13:56, "Sebastian Kiesel" <[email-masked]> wrote:

>>I don©öt know whether any ALTO server could maintain a full 5000x5000 cost

---

From: Sebastian Kiesel <[email-masked]>
Date: Mon, 14 Jul 2014 14:02:33 +0200

Hi Wendy,

> can define PIDs however it wants, is that even possible?

Non-aligned PIDs is a problem, but I think that could be solved if it
were the only problem.  The tracker could create a local PID for every
prefix learned from any remote network map, and then distribute the
incoming cost maps on these local PIDs. In the extreme case, it could
create a 2^32 x 2^32 map and store the cost for every pair of IP
adresses (with some sort of compression, 2^64 or even 2^256 is quite a
number of cells).  

The more interesting question is how to handle contradictory entries for
the same normalized (src,dst)-pair if received from different ALTO
servers.

So ...

> maps separately, and using the one that is closest to the requesting peer?

... yes.  And the total information contained in these many small maps would
probably be equivalent to a, say, 5000x5000 matrix.

> wouldn??t be as large. But there would be a lot of them. And the tracker
> map which has the finest detail around the requesting peer??s address?
> Whatever that means?

Basically yes, but I am a bit sceptical that your example thinks too
much in terms of geographical location instead of network topology and
administrative domains.
Who would be the operator of the "New York City Area ALTO Server"?

My vision of a deployment scenario with distributed ALTO knowledge is:

Every operator of an access network can publish (e.g., via the DNS) for
each of their prefixes, which ALTO Server (i.e. IRD URI) is in charge.
These ALTO servers will deliver very sparse cost maps, which are
de-facto only a "cost from us to anywhere"-vector.

If I am a network operator in, say Europe, I know the costs from my
access networks to the rest of the Internet (both in terms of routing
protocol costs and other traffic engineering parameters as well as
monetary costs for network interconnections).  But from where would I
know the cost from, say, Tokyo to New York City (or, to be more precise,
from a sepecific access network in Tokyo to a specific access network in
New York City)?  And even if I knew, why should I bother publishing it?
I might even run into legal liabilities if I gave bad advice?! That's
why I would only publish a "from us to anywhere"-vector (or a sparse
"from our prefixes to anywhere"-matrix).   This vector would
be rather detailed about possible destinations in my vicinity and less
detailed about other continents or difficult-to-reach networks.

And then, when a peer asks the tracker, it would be the task of the
ALTO client in the tracker to do a "back-connect" to the ALTO server
that is in charge for the peer's prefix, to get the appropriate cost
vector.

> cross-domain ALTO server discovery!

Yeah, I know.  We've been discussing this back in 2009
(http://tools.ietf.org/id/draft-kiesel-alto-3pdisc-00.txt , Approach #5).
This approach requires changes to all existing (P2P) application
protocols that want to benefit from ALTO.

Thanks
Sebastian

---

From: Wendy Roome <[email-masked]>
Date: Mon, 14 Jul 2014 11:25:27 -0400

On 07/14/2014, 08:02, "Sebastian Kiesel" <[email-masked]> wrote:

>>Š...

I agree. I just used geographic distance as a simple metaphor for
topological or administrative distance.

But the question then becomes given a set of N Network Maps, how would you
decide which one is best for costs relative to (say) 1.0.0.0? One
possibility is pick the map with the longest CIDR that matches 1.0.0.0.
However that favors sloppy maps that haven¹t aggregated adjacent CIDRs.
And of course that map might not be unique.

One way to filter out sloppy maps is to start with the set of all map(s)
with the longest CIDR that covers 1.0.0.0. Then add any maps with CIDRs
that cover 1.0.0.0 but are only slightly shorter than the longest one. Eg,
if the longest CIDR is 1.0.0.0/24, include maps with 1.0.0.0/22 and
1.0.0.0/23, but not 1.0.0.0/16. Then for each of those network maps,
estimate the size of the PID containing 1.0.0.0 -- that is, estimate the
maximum number of endpoints in the PID. Then pick the map with the
smallest PID containing 1.0.0.0. If that¹s not unique ... I dunno.
Randomize??

Estimating PID size might work for ipv4, because by this time, I think
assigned ipv4 addresses are uniformly dense. But I don¹t think it would
work as well for ipv6.

	- Wendy Roome

---

From: Wendy Roome <[email-masked]>
Date: Mon, 14 Jul 2014 12:04:05 -0400

Sebastian,

I agree with that 100%. I think that¹s the only practical deployment
scenario, for precisely the reasons you outlined.

However, over the last year, a number of folks have asked me, ³I¹ve heard
you¹re working on something called ALTO that¹s supposed to help me select
the best server. How does that work?² While learning about their
application, I¹ve discovered that almost every newbie expects an ALTO
server will have detailed cost information between any pair of endpoints
anywhere in the world. I¹ve tried to gently explain that your scenario is
more likely -- there won¹t be one global ALTO server. Instead there will
be a bunch of ALTO servers, each with local knowledge, and their
application will have to select the right ALTO server.

Of course, I haven¹t pushed that point too hard. I don¹t want to
discourage them from using ALTO!

But I am afraid that our customers may expect more from ALTO than ALTO can
deliver.

	- Wendy

---

From: Sebastian Kiesel <[email-masked]>
Date: Mon, 14 Jul 2014 18:10:19 +0200

On Mon, Jul 14, 2014 at 11:25:27AM -0400, Wendy Roome wrote:
> decide which one is best for costs relative to (say) 1.0.0.0? 

I would use the xdom-disc (formerly called 3pdisc) algorithm and perform
some DNS queries in order to find out whether the "owner" of 1.0.0.0
(i.e., the ISP, IT department, or whoever controls reverse DNS for that
address) has configured an ALTO server to be used for the optimization
of traffic from/to this IP address.

If no such specific ALTO server can be discovered, maybe there is a
fallback server with some (coarse grained) global knowledge. This would
have to be discovered by some other means.  If that fails, too, I'd give
up and go on without ALTO guidance.

> One

I think I need some more time to think about what could happen (and
possibly go wrong) when using this strategy.  The possible results are
probably too unforeseeable to write this down as a standard.

So far, my idea was that we have basically two different deployment
scenarios for ALTO servers (in an Internet-wide context, others may
apply for the CDN use case, etc.):

1.) An "altruistic and objective organization" (e.g., the same guys that
run large P2P trackers) operates a single ALTO server (of course
replicated for availability and load balancing) with more or less
coarse grained global knowledge.  Just discover it and ask...

2.) The ISPs publish "vectors" (see my mail from earlier today) to be
used for optimization of traffic from/to their customers. Use xdom-disc
to find the "right" ALTO server providing the "right" map/vector for
a given resource consumer.

Do we have more realistic scenarios, that need different discovery
mechanisms?

Thanks
Sebastian

---

From: "Y. Richard Yang" <[email-masked]>
Date: Fri, 18 Jul 2014 12:04:03 -0400

> new ALTO services you proposed. You would still have to define incremental
Catching up on the discussions...

My understanding is that Wendy and Jan are making the same conclusion.

Jan: "So we may have good arguments for saying ALTO network/cost map service
has a specific incr. update solution, and ALTO CDNI FCI service uses JSON
patch."

>From an OO design point of view, I see JSON as a base type, and JSON Patch
as a base function on the base type. Network/Cost maps are derived types
that may also override the patch method to be more efficient. I can see
another design that for the same type, one instance Network/Cost map can be
patched using JSON Patch, for example, when it is small, while another
instance of the same type can use the more efficient encoding.  Hence, we
have the effect of prototype (JS) based derivation system. The exact method
can be announced, easily, in IRD.

Richard

-- 
-- 
 =====================================
| Y. Richard Yang <[email-masked]>   |
| Professor of Computer Science       |
| http://www.cs.yale.edu/~yry/        |
 =====================================

---

From: "Y. Richard Yang" <[email-masked]>
Date: Fri, 18 Jul 2014 12:55:49 -0400

Hi Wendy,

Always good comment. Please see below.

> This does not simplify anything; it just makes more work for the client.

After reading your discussion, I have the following picture of workflow in
mind:

Original Data Structure at ALTO Server (DSS) => (transformation T1)
  JSON at Server (JSONS) ----> (transmission/encoding)
     JSON at Client (JSONC) => (transformation T2)
        Data structure at Client (DSC)

Here are some points:

1. JSONS == JSONC, which can be defined as JSON.
2. It is possible that DSS != JSON != DSC.
3. Your key point is that DSC should be efficient (e.g., a trie), in memory
and/or lookup.
4. A related point is that T2 which implements 3 may need to be highly
customized, and hence is unlikely to be provided by a standard JSON
library, although many libraries provide auto conversion from JSON to a
specific data type (e.g., Java).

I like the arguments!

Before solving the preceding efficiency problem. I want to first solve the
automation problem. In other words, assume that we use JSON Patch. Is there
a library that provides automatic generation at server and application at
client of JSON Patch? I googled around and found the following:
http://stackoverflow.com/questions/7326532/delta-encoding-for-json-objects

The preceding is not complete, and I can imagine other approaches. For
example, I can define a wrapper data type, say Set', that wraps a generic
type such as Set, and user can modify an instance of Set' using only a set
of operations that Set' provides. Then, upon each invocation of a mutator
on Set', the type can produce the JSON patch automatically, before
delegating the real operation to Set. An issue of this approach, however,
is how to produce the XPATH when an instance of Set's might be a field of a
more complex data structure.

Before we draw the conclusion that JSON Patch mostly will add more work, I
still prefer that it is more rigorously "proven" that it is hard to develop
a good library for JSON Patch. I took the liberty of cc'ing the co-authors
of JSON Patch, hoping that they may provide additional pointers.

Thanks!

Richard

---

From: "Y. Richard Yang" <[email-masked]>
Date: Mon, 21 Jul 2014 00:17:42 -0400

Hi Mark,

Thanks a lot for the expert comment. Please see below.

On Sun, Jul 20, 2014 at 11:31 AM, Mark Nottingham <[email-masked]> wrote:

> Hi,
>
> It’s difficult to say without knowing more of the specifics, but generally
> - if you’re already using JSON, or considering it for expressing your data
> model (realising that a data model is separable from its serialisation onto
> the wire), JSON Patch may be useful to you. But it sounds like you need to
> figure out whether you want to use JSON.
>
> The ALTO Protocol is already based on JSON.  Please see
https://datatracker.ietf.org/doc/draft-ietf-alto-protocol/

Note that the PATCH method isn’t specific to JSON; you can come up with
> other PATCH formats.

Good comment. We are evaluating how good a match the particular JSON Patch
format in your RFC to our need.

> However, the more application-specific your patch format is, the less
> likely that it’ll “just work."
>
>
I am not sure I fully understand the context of it will "just-work." Here
are some issues in our application-specific context, as Wendy pointed out:

1. Ease-of-use: is there an easy-to-use library that just works: it
produces and applies JSON Patch based on existing JSON libraries? Do you
have any recommended pointers that we may check out?

2. The issue of Set: JSON does not have a concept of a Set (e.g., a set of
IP prefixes). Hence, one typically uses an array to represent what actually
is a set. In setting where patching a set is simple, e.g., indicating the
element to be deleted. But indicating the op using the array is cumbersome:
one has to remember the array index.

3. Batching a set of operations: moving a subset of elements in a set.

Any comment or pointers?

Richard

> Cheers,
>
>
> On 18 Jul 2014, at 12:55 pm, Y. Richard Yang <[email-masked]> wrote:
>
> > Hi Wendy,
> >
> > After reading your discussion, I have the following picture of workflow
> in mind:
> >
> > 3. Your key point is that DSC should be efficient (e.g., a trie), in
> memory and/or lookup.
> > Before solving the preceding efficiency problem. I want to first solve
> the automation problem. In other words, assume that we use JSON Patch. Is
> there a library that provides automatic generation at server and
> application at client of JSON Patch? I googled around and found the
> following:
> >
> > Before we draw the conclusion that JSON Patch mostly will add more work,
> I still prefer that it is more rigorously "proven" that it is hard to
> develop a good library for JSON Patch. I took the liberty of cc'ing the
> co-authors of JSON Patch, hoping that they may provide additional pointers.
> >
> > Thanks!
> >
> > Richard
> >
> >
> >     - Wendy Roome
> >
> >
> Mark Nottingham   http://www.mnot.net/
>

---

From: Mark Nottingham <[email-masked]>
Date: Sun, 20 Jul 2014 11:31:56 -0400

Hi,

It’s difficult to say without knowing more of the specifics, but generally - if you’re already using JSON, or considering it for expressing your data model (realising that a data model is separable from its serialisation onto the wire), JSON Patch may be useful to you. But it sounds like you need to figure out whether you want to use JSON.

Note that the PATCH method isn’t specific to JSON; you can come up with other PATCH formats. However, the more application-specific your patch format is, the less likely that it’ll “just work."

Cheers,

On 18 Jul 2014, at 12:55 pm, Y. Richard Yang <[email-masked]> wrote:

> On Wed, Jul 9, 2014 at 3:14 PM, Wendy Roome <[email-masked]> wrote:
> After reading your discussion, I have the following picture of workflow in mind:
> 
> 3. Your key point is that DSC should be efficient (e.g., a trie), in memory and/or lookup. 
> 4. A related point is that T2 which implements 3 may need to be highly customized, and hence is unlikely to be provided by a standard JSON library, although many libraries provide auto conversion from JSON to a specific data type (e.g., Java).
> 
> I like the arguments!
> 
> Before solving the preceding efficiency problem. I want to first solve the automation problem. In other words, assume that we use JSON Patch. Is there a library that provides automatic generation at server and application at client of JSON Patch? I googled around and found the following:
> The preceding is not complete, and I can imagine other approaches. For example, I can define a wrapper data type, say Set', that wraps a generic type such as Set, and user can modify an instance of Set' using only a set of operations that Set' provides. Then, upon each invocation of a mutator on Set', the type can produce the JSON patch automatically, before delegating the real operation to Set. An issue of this approach, however, is how to produce the XPATH when an instance of Set's might be a field of a more complex data structure.
> 
> Before we draw the conclusion that JSON Patch mostly will add more work, I still prefer that it is more rigorously "proven" that it is hard to develop a good library for JSON Patch. I took the liberty of cc'ing the co-authors of JSON Patch, hoping that they may provide additional pointers.
> 
> Thanks!
> 
> Richard
>  
> 
>     - Wendy Roome
> 
>

---

From: Mark Nottingham <[email-masked]>
Date: Mon, 28 Jul 2014 12:48:33 +1000

On 21 Jul 2014, at 2:17 pm, Y. Richard Yang <[email-masked]> wrote:

> I am not sure I fully understand the context of it will "just-work."

Just that the PATCH method is defined for generic mechanisms, not application-specific ones; if your payload is application-specific, you might as well use POST.

> Here are some issues in our application-specific context, as Wendy pointed out:
> 
> 1. Ease-of-use: is there an easy-to-use library that just works: it produces and applies JSON Patch based on existing JSON libraries? Do you have any recommended pointers that we may check out?

We have a test suite at:
  https://github.com/json-patch/json-patch-tests

One of the community members keeps a list of implementations at:
  http://jsonpatch.com

> 2. The issue of Set: JSON does not have a concept of a Set (e.g., a set of IP prefixes). Hence, one typically uses an array to represent what actually is a set. In setting where patching a set is simple, e.g., indicating the element to be deleted. But indicating the op using the array is cumbersome: one has to remember the array index.
> 

Yes, I can see how these would be difficult -- but they are possible.

Note that we are starting to collect issues for a possible second version of json-patch:
  https://github.com/json-patch/json-patch2
... and I've noted your feedback at:
  https://github.com/json-patch/json-patch2/issues/8
Please feel free to expand upon your requirements in that issue (and thanks for the feedback!).

One approach you could take would be to use json-patch for now, and then use json-patch2 (or whatever it ends up being called) when it ships; that way, you avoid defining an application-specific patch format.

Cheers,

--
Mark Nottingham   https://www.mnot.net/

---

From: Mark Nottingham <[email-masked]>
Date: Mon, 28 Jul 2014 13:54:08 +1000

PATCH isn't idempotent.

Cheers,

On 28 Jul 2014, at 1:52 pm, Paul C. Bryan <[email-masked]> wrote:

> On Mon, 2014-07-28 at 12:48 +1000, Mark Nottingham wrote:
> 
> If the intent is for the operation to be idempotent, then I believe PATCH can still be more suitable for an application-specific payload.
> 
> Paul

---

From: Wendy Roome <[email-masked]>
Date: Mon, 28 Jul 2014 11:25:05 -0400

Thanks for the info. I took a quick look at one of the Java
implementations of json patch, and it was pretty much what I expected.

The good news: A library that supports JSON patch can provide incremental
update with relatively little additional work for the client or the
server. For clients, a patch(oldNode,patchText) method applies a json
patch to an existing json object. For servers, a diff(oldNode,newNode)
method calculates the json patch that represents the changes between two
versions.

The bad news: To achieve that ease of use, the client & server MUST store
the ALTO data in objects that the JSON library provides, and access the
data via methods provided by the JSON library. That is, the client &
server MUST use the DOM [Document Object Model] dictated by the JSON data.

So what's wrong with that? For small maps, nothing. For medium-sized maps,
it's probably okay.

But for small maps, why bother with incremental update? Just download the
new version already. Ditto for medium-sized maps. For heavens sake, look
at the number of commercial web sites with a footprint of a megabyte or
more!

Incremental update becomes vital for large maps. E.g., thousands of PIDs,
with cost maps that take hundreds of megabytes. And for those, alas, the
JSON data model breaks down. Example: I originally used a JSON java
library from json.org. Then I tried it on large cost maps. For a
fully-specified 1,000 PID cost map, the library did read the JSON and
create the necessary object tree, but it took almost minute. Then I tried
reading a fully-specified 5,000 PID cost map. The library failed. I told
the JVM to use four gigs of ram. It still failed.

So I wrote my own JSON library, with an "on the fly" parser instead of the
DOM model. That is, the parser scanned the incoming json, but instead of
building it's own model of the data, it called sub-class methods for each
event (enter/leave dictionary or array, found new string/number value,
etc). The sub-class methods stored the data in form optimized for the
application. For cost maps, I converted the PID names to numeric indexes,
on the assumption that the PID names don't change that often, and stored
the costs in a numerically-indexed square matrix of single-precision
floats.

It's hard to be sure with java, but my guess is that my optimized
representation takes about 105 megs of RAM, while the JSON data model (if
it succeeded) would have taken well over a gig.

In any case, my library can create a 5,000 PID cost map as fast as it can
read the JSON text.

So the problem I have with JSON patch is that the automatic, hassle-free
implementations may not scale up to the map sizes we would like to
support. I think that limitation is inherent in the requirement that
clients use a DOM dictated by the JSON library.

	- Wendy Roome

On 07/27/2014, 22:48, "Mark Nottingham" <[email-masked]> wrote:

>Just that the PATCH method is defined for generic mechanisms, not
>application-specific ones; if your payload is application-specific, you
>might as well use POST.
>
>
>> 2. The issue of Set: JSON does not have a concept of a Set (e.g., a set
>>of IP prefixes). Hence, one typically uses an array to represent what
>>actually is a set. In setting where patching a set is simple, e.g.,
>>indicating the element to be deleted. But indicating the op using the
>>array is cumbersome: one has to remember the array index.
>> 
>One approach you could take would be to use json-patch for now, and then
>use json-patch2 (or whatever it ends up being called) when it ships; that
>way, you avoid defining an application-specific patch format.
>
>Cheers,
>
>
>--

---

From: Mark Nottingham <[email-masked]>
Date: Tue, 29 Jul 2014 14:57:25 +1000

Interesting; I can totally see how that's a problem (especially with Java implementations).

It seems like ALTO has a choice here between:

a) using a standard format on the wire (json-patch) and encouraging / writing implementations that are more memory-efficient (perhaps supporting streaming), or

b) defining its own wire format, and still needing implementation work to take place.

I know which I'd choose; YMMV :)

Cheers,

---

From: Wendy Roome <[email-masked]>
Date: Tue, 29 Jul 2014 15:59:44 -0400

Yes, exactly. Let me add one more point. Cost maps may have millions of
cost points. During any (say) 5 minute interval, it is very likely that
some of those costs will change. But it is very unlikely that a lot of
them will change.

So for cost maps, incremental update is very important.

A cost map is a square, sparse matrix of numbers, indexed by strings (PID
names). Our JSON representation is a lookup table of lookup tables of
numbers. The table keys are PID names, and undefined cost points are
omitted from the table.

Turns out that our JSON cost-map representation is also perfect
representation of an incremental update. Just change the semantics
slightly:

* Start with the previous cost matrix, rather than an empty matrix.
* For a null-valued cost point, remove that point from the previous
version, if it existed.
* For a non-null cost point, add it to the matrix, either replacing the
previous value or creating a new one.

So for cost maps, efficient custom patch messages are "free². Or at least
"no additional work." :-)

For network maps, the case isn't as clear. The data structure that best
captures the semantics of a network map is a lookup table from CIDRs to
PID names. Alternatively, a network map is a lookup table from PID names
to sets of CIDRs, with the additional assertion that a CIDR is in only one
set. Our JSON representation is a lookup table from PID names to arrays of
CIDRs.

Our JSON network map message does not do a good job of representing
network map deltas such as "move 1.0.0.0/16 from PID1 to PID2".

On the other hand, JSON patch doesn't do a good job of representing
network map changes either, if only because we use an array to represent a
set, so JSON patch thinks the order matters.

On top of that, I claim that incremental update simply isn't that
important for network maps. A fundamental assumption behind the design of
ALTO is that network maps will not change very often. When a network map
changes, it completely invalidates all previously retrieved cost maps. Any
change to a network map, no matter how simple, is a flag day.

So how about this compromise: for cost maps, define incremental update
using our existing cost map message format. If the JSON group asks why
don't we use JSON patch, just say that our message format perfectly
captures the semantics of all legal cost map changes, and ALTO clients and
servers already support it, so we don't need any additional patch
mechanism.

For network maps, do not define incremental update at this time. Wait
until some ALTO servers actually implement incremental cost map update --
and clients use it! -- and then see if there is any demand for incremental
update for network maps.

	- Wendy Roome

 would be happy to define incremental update for cost maps using our
existing cost map messages

On 07/29/2014, 00:57, "Mark Nottingham" <[email-masked]> wrote:

>a) using a standard format on the wire (json-patch) and encouraging /
>writing implementations that are more memory-efficient (perhaps
>supporting streaming), or
>

---

From: "Y. Richard Yang" <[email-masked]>
Date: Thu, 31 Jul 2014 15:34:33 -0400

Hi Wendy, Mark,

Good discussions. See below.

> numbers. The table keys are PID names, and undefined cost points are
This data structure of lookup table of lookup tables (dict of dicts)
appears to be a good data structure. For example, see NetworkX (see
http://networkx.github.io/documentation/latest/reference/introduction.html
and search for dict-of-dicts for its argument on the benefits of using this
data structure to represent sparse graphs.

> previous value or creating a new one.

Two comments:

1. A small technical question: what is the JSON type for each element of
the cost matrix? It is a JSON number before. Now it is JSON number \union
null?

The more general, intended question is whether it will be beneficial to
introduce a generic data type to denote operations.

2. A more general question is: how widely applicable is your design (i.e.,
using the original data type plus some small annotation to convey updates?
Or more interestingly, where the design does not work (well)?

> servers already support it, so we don't need any additional patch
This compromise looks reasonable to me. To proceed, it will be great if the
overall update framework is laid out (e.g., indicate the default as well as
the patch mechanism(s) for each data type), so that we can claim that ALTO
has a complete patch mechanism?

> and clients use it! -- and then see if there is any demand for incremental
See above.

Richard

---

From: "Y. Richard Yang" <[email-masked]>
Date: Thu, 31 Jul 2014 16:50:03 -0400

To make progress, here is one straw-man proposal encoding that combines
JASON PATCH (RFC6902) and in-place edit. Specifically, JSON PATCH defines a
set of ops. How about we define a new op, as an extension of JSON PATCH,
that provides in-place override, as in Wendy's design. One possibility is
to name it "override", or another name you like. It still has "path", to
indicate the place of "override". Its "value" will be Wendy's encoding.

On Thu, Jul 31, 2014 at 3:34 PM, Y. Richard Yang <[email-masked]> wrote:

> This compromise looks reasonable to me. To proceed, it will be great if
> the overall update framework is laid out (e.g., indicate the default as
> well as the patch mechanism(s) for each data type), so that we can claim
> that ALTO has a complete patch mechanism?
>
>
>

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 1 Aug 2014 12:00:38 +1000

JSON PATCH doesn't allow extensions; you need to define a new media type to add operations.

I think the question is whether that's json-patch2 (as discussed previously), or something alto-specific.

Cheers,

On 1 Aug 2014, at 6:50 am, Y. Richard Yang <[email-masked]> wrote:

> To make progress, here is one straw-man proposal encoding that combines JASON PATCH (RFC6902) and in-place edit. Specifically, JSON PATCH defines a set of ops. How about we define a new op, as an extension of JSON PATCH, that provides in-place override, as in Wendy's design. One possibility is to name it "override", or another name you like. It still has "path", to indicate the place of "override". Its "value" will be Wendy's encoding. 
> 
> On Tue, Jul 29, 2014 at 3:59 PM, Wendy Roome <[email-masked]> wrote:
> This data structure of lookup table of lookup tables (dict of dicts) appears to be a good data structure. For example, see NetworkX (see http://networkx.github.io/documentation/latest/reference/introduction.html and search for dict-of-dicts for its argument on the benefits of using this data structure to represent sparse graphs. 
>  
> 1. A small technical question: what is the JSON type for each element of the cost matrix? It is a JSON number before. Now it is JSON number \union null?
> 
> The more general, intended question is whether it will be beneficial to introduce a generic data type to denote operations.
> 
> 2. A more general question is: how widely applicable is your design (i.e., using the original data type plus some small annotation to convey updates? Or more interestingly, where the design does not work (well)?
> 
> This compromise looks reasonable to me. To proceed, it will be great if the overall update framework is laid out (e.g., indicate the default as well as the patch mechanism(s) for each data type), so that we can claim that ALTO has a complete patch mechanism?
> 
>

---

From: "Y. Richard Yang" <[email-masked]>
Date: Thu, 31 Jul 2014 22:31:47 -0400

> previously), or something alto-specific.
I prefer more reusable design. Hence, it will be more along the line of
json-patch2... Make sense?

Richard

> > 2. A more general question is: how widely applicable is your design
> (i.e., using the original data type plus some small annotation to convey
> updates? Or more interestingly, where the design does not work (well)?
> >
> > >Interesting; I can totally see how that's a problem (especially with
> Java
> > >implementations).
> > >
> > >b) defining its own wire format, and still needing implementation work
> to
> > >take place.
> > >