> Issue 7 of the proposed rechartering effort [0] deals with a suitable > format for encoding graphs in ALTO. My impression is that there > are two distinct capabilities we are looking for: graph > representation and graph transformation. The representation part > appears easy enough (I think). > > Taking some liberties with the syntax, a coarse JSON GML encoding > can be approximated as follows: > > graph [ > node [ > id 0 > label "PID-1" > address-type "ipv4" > hosts ""192.0.2.0/24, 198.51.100.0/24" > ] > node [ > id 1 > label "PID-2" > address-type "ipv4" > hosts ""192.0.2.0/25, 192.0.2.128/25" > ] > node [ > id 2 > label "PID-3" > address-type "ipv4" > hosts "0.0.0.0/0" > ] > edge [ > source 0 > target 1 > value 2 > type "undirected" > ] > edge [ > source 0 > target 2 > value 3 > type "undirected" > ] > edge [ > source 1 > target 2 > value 6 > type "undirected" > ] > ] > > Two questions: > > 1) Is the encoding above close to what we have been calling the > "multiple-switch" model? Is something like this encoding one > possible > outcome of a work item related to Issue 7?
Yes, at least this is my understanding. GML is, as well as GraphML (XML), widely used on open source tools, but both are not JSON based. An example for a JSON format that available in the well-known tinkerpop open source graph processing tool suite would be GraphSON: https://github.com/tinkerpop/blueprints/wiki/GraphSON-Reader-and-Writer-Library While I have no preference regarding the specific JSON syntax, I think that we look for a "property graph" model. According to https://github.com/tinkerpop/blueprints/wiki/Property-Graph-Model, a property graph has these elements: a set of vertices each vertex has a unique identifier. each vertex has a set of outgoing edges. each vertex has a set of incoming edges. each vertex has a collection of properties defined by a map from key to value. a set of edges each edge has a unique identifier. each edge has an outgoing tail vertex. each edge has an incoming head vertex. each edge has a label that denotes the type of relationship between its two vertices. each edge has a collection of properties defined by a map from key to value. In your GML example, the key question is thus how to deal with the "value" property of the edges. Similar to the ALTO maps, I'd argue that an ALTO graph must support a default cost metric ("routingcost"), but extensions should be possible. > 2) The harder part is graph transformation. What sort of algebraic > formulations do we expect to turn into protocol primitives that will > allow us to transform graphs as is outlined in Section 4 of [1]? > > [0] http://www.ietf.org/mail-archive/web/alto/current/msg02345.html > [1] http://tools.ietf.org/html/draft-yang-alto-topology-00 Section 4 of [1] contains some pretty advanced concepts. I am not sure if in the current re-chartering we should aim at that level of complexity. In my opinion, a more low-hanging fruit - as a starting point for a discussion - would be the question whether ALTO would have protocol primitives to do SPF (and CSPF) queries on the graph. That would be an equivalent to the endpoint cost service. In my view, there are two alternatives: a) Corresponding ALTO primitives are specified along with the graph format b) As a first step, such queries would be left up to the ALTO client, i.e., the ALTO server only provides the maps (=graph), but it is up to the ALTO client to perform advanced logic using that data I personally think that b) might be an easier first step for the re-chartering, but if somebody comes up with a good ALTO API extension for a), I'd be interested in it as well. Michael _______________________________________________ alto mailing list [email protected] https://www.ietf.org/mailman/listinfo/alto
