Hi Wendy, Mark, Good discussions. See below.
On Tue, Jul 29, 2014 at 3:59 PM, Wendy Roome <[email protected]> wrote: > 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. > > 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. > 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. > 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)? 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. > > 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? > 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. > > See above. Richard > - 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 protected]> 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, > > > > > -- -- ===================================== | Y. Richard Yang <[email protected]> | | Professor of Computer Science | | http://www.cs.yale.edu/~yry/ | =====================================
_______________________________________________ alto mailing list [email protected] https://www.ietf.org/mailman/listinfo/alto
