Hi Greg, Some comments inline [MS].
Michael From: alto [mailto:[email protected]] On Behalf Of Greg Bernstein Sent: Tuesday, January 28, 2014 4:54 PM To: [email protected] Subject: Re: [alto] Work items for re-chartering Great points Michael. In our paper available at http://www.grotto-networking.com/files/BandwidthConstraintModeling.pdf in section III we give a number of reduction/transformation procedures. We looked at this from the point of view of lists of paths, most suitable when there are few path choices and a limited number of source-destination pairs of interest. And we looked at this from the point of view of a "service specific" graphs which were transformed from the original graph based on source-destination pairs of interest and limits on additive paths measures such as delay. [MS] I haven't digged through all the maths in the paper. I fully agree that there can be service specific graphs, similar to service specific ALTO maps, which are possible as of today. However, the key question to me is whether the ALTO protocol actually needs protocol primitives to deal with this. For instance, referring to the paper, if the ALTO server would expose the graph shown in Figure 6, the ALTO client could calculate the different "views" in Figure 7 without requiring ALTO functions for this (other than e.g. well-defined metrics, e.g., based on draft-wu-alto-te-metrics). As I already said, I am open to adding such functions to ALTO (as optional extensions), but we need something that is easy to understand as a starting point. I didn't know about tinkerpop. Thanks for the reference. Here are some of the design considerations I was thinking about and how they are supported in various graph formats. [MS] Yes, there are some good thoughts therein. More below. Cheers Greg B. Desirable "graph representation" properties: * Separation of nodes and links. Both nodes and links can have properties and resource restrictions, e.g., WDM nodes. Better not to embed node definitions in links. Give both nodes and links unique identifiers. This aids incremental updates and allows for parallel links without the use of ports. [MS] Yes * Incremental updates May want to update resource status of nodes or links separately. Keeping node and link definitions separate promotes this. [MS] I think incremental updates should be first solved for the existing maps, but we certainly look for a future-proof format. * Path definitions Standardize a format for paths in terms of nodes or links. This allows for path only topology sharing and abstraction. This is also useful/needed for multi-layer network descriptions. OGF NML has a "path" in terms of "links" in its "serial-compound link" notion. [MS] What is the difference between a path and a link? How would an application use such a path? * Ports on Nodes These should be supported but not required, similar to what is done in GraphML. [MS] I think I agree to that. Ports are useful in asymmetric switching nodes such as ROADMs. * Multi-Layer Modeling For this we need the adaptation concept. We can define this as an edge with properties if we are building on basic graph notions of vertices and edges. Note that OGF doesn't define layer networks, but just assigns "encodings" to links, ports, adaptations, and switching services. [MS] I don't understand this. What would be an ALTO-like example? * Need to separate graph notions from network notions. Graphs only have vertices and edges. Graph description languages or frameworks (e.g. NetworkX) do allow for these to have properties. Networks have nodes, links, and adaptations... Hence why OGF NML has a separate Adaptation/De-adaptation classes. [MS] Same here. * Many graph models support hyper-edges which can be used to model some LANs and such. [MS] Possibly useful, but an ALTO-like example for using such a feature would really help, too. GraphML OGF NML SNDlib NetworkX JSON Node ids Explicit, Required, Unique Explicit, Required, Unique Explicit, Required, Unique Implicit via ordering in nodes array. But can use "id" attribute when converting from JSON to python representation Link ids (these also allow parallel links without ports) Explicit, Required unique Explicit, Required, Unique Explicit, Required, Unique Implicit via ordering in links array. . Node properties Can contain a graph, ports, data, locator. Arbitrary data via a (key, data) mechanism. Can contain location, has "life time concept", name, ports. Not directly associated with links but only through ports. Can contain coordinates Arbitrary. Link properties Can contain a graph. Arbitrary data via (key, data) mechanism.S Not currently defined. Routing cost, setup cost, pre-installed and additional modules that have increments of capacity. Must include source/target node references. Arbitrary properties can be added. Paths No serial compound links/"ordered list of links" Yes No. Layers No, but could add a "property" for this. This seems to be implemented by assigning ports, links, adaptation, and switching service all have a "encoding" parameter. Nodes and Topologies do not. No No. Can add via a property. Nodes Can contain arbitrary data including graphs. In topology object. Contained in a "nodes" element. Contained in nodes list. Ports Yes. Contained within nodes. Yes. have "encoding" parameter, relationship to link. No. No. Could add as a node and link property. Adaptation concept No. Could add as link property Yes. No. Could add as a link property. [MS] Good table. But GraphML, OGF NML, and SDNlib are all not JSON. And I think that an implicit ordering like in NetworkX JSON is inferior to explicit identifiers for edges/vertices. On 1/28/2014 2:25 AM, Scharf, Michael (Michael) wrote: 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]<mailto:[email protected]> https://www.ietf.org/mailman/listinfo/alto -- =================================================== Dr Greg Bernstein, Grotto Networking (510) 573-2237
_______________________________________________ alto mailing list [email protected] https://www.ietf.org/mailman/listinfo/alto
