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.
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.
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.
* Incremental updates
May want to update resource status of nodes or links separately.
Keeping node and link definitions separate promotes this.
* 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.
* Ports on Nodes
These should be supported but not required, similar to what is done
in GraphML.
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.
* 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.
* Many graph models support hyper-edges which can be used to model
some LANs and such.
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.
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]
> 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
