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" <m...@mnot.net> wrote:
>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,
>
_______________________________________________
alto mailing list
alto@ietf.org
https://www.ietf.org/mailman/listinfo/alto
