Subject: [alto] Work items for re-chartering

From: "Vijay K. Gurbani" <[email-masked]>
Date: Thu, 23 Jan 2014 13:11:14 -0600

Folks: Over the last few IETFs, Enrico and I have solicited feedback
during face-to-face meetings, WG sessions, hallway conversations, ALTO
mailing list and private conversations on how to move ahead with respect
to adopting new work items.

As we begin the charter discussions, we have identified seven
work items to propose as additions to the charter.  The first four of
these work items are fairly uncontroversial.  The last three are work
items that have a monumental mind share in the ALTO working group and
have been found to be extremely useful in controlled networks (e.g.,
VPNs).  However, we have to take some care in defining these such that
we do not duplicate the functionality available elsewhere (e.g., general
routing) in ALTO, nor do we take on an aspect that the working group
does not fully understand.

Here are the seven items up for discussion:

1. Anycast-based server discovery
    (Presented by Reinaldo Penno in IETF 86 and appears to have
    some support for adoption.)

2. Third-party server discovery
    (Sebastian Kiesel et al. have been driving this work and it
    also appears to have support.)

3. Incremental ALTO map updates
    (Side meeting held during IETF 86; two proposals have been
    studied.  One way forward is to use an ALTO-specific incremental
    update that may be more efficient, and the second approach is to
    simply use JSON patch.)

4. Server-initiated update notifications
    (Jan Seedorf and Enrico Marocco have suggested the use of
    Websockets; HTTP/2.0 may provide some mitigation as well.)

5. Extensions to annotate PIDs with properties (e.g., geographical
    locations).
    (Useful as an extension in controlled environments, e.g., VPNs
    where IP addresses are not the only form of identification.
    Some drafts, including draft-roome-alto-pid-properties
    has already started work in this direction.)

6. Extensions for cost metrics.
    (Some drafts, including draft-wu-alto-json-te, have started work
    in this direction.)

7. An ALTO format for encoding graphs.
    (draft-ietf-alto-protocol already recognizes the need to provide
    topology details that are useful in controlled environments.
    Richard Yang, Greg Bernstein and others have been working on the
    need and use cases for such an encoding.  draft-yang-alto-topology
    is a good start.  Projects like OpenDayLight and NetworkX (Python)
    have JSON models for graph representation.  Some concrete examples
    of how we envision encoding graphs will be useful during list
    discussion.)

We will like to understand whether the working group believe such
additional deliverables, if included in an updated charter proposal,
would allow people to do the extension work that has been repeatedly
proposed. (Clarification: we are explicitly asking whether people could
find such an update acceptable. We understand that anyone will have a
preferred flavor of the above.)

We are at a point where show of support by whoever is interested is
essential for moving forward. If it turns out to be positive, Enrico
and I will subsequently circulate actual text, including milestones, for
a rechartering request.

Thanks.

- vijay
-- 
Vijay K. Gurbani, Bell Laboratories, Alcatel-Lucent
1960 Lucent Lane, Rm. 9C-533, Naperville, Illinois 60563 (USA)
Email: vkg@{bell-labs.com,acm.org} / [email-masked]
Web: http://ect.bell-labs.com/who/vkg/  | Calendar: http://goo.gl/x3Ogq

---

From: Jan Seedorf <[email-masked]>
Date: Fri, 24 Jan 2014 14:08:57 +0000

Dear all,

I fully support the proposed work items below (1-7) for extending the ALTO charter. I believe the many discussions and several side meetings we had in 2013 (and before) have shown that a) there is significant interest from the community in working on these items, and b) that there are multiple important use cases that would benefit from these extensions.

Sidenote: Item #5 (PID properties) would be extremely useful for ALTO as a CDNI FCI protocol, which Richard Yang and I are proposing in the CDNI WG.

 - Jan

> -----Original Message-----
> From: alto [mailto:[email-masked]] On Behalf Of Vijay K. Gurbani
> Sent: Thursday, January 23, 2014 8:11 PM
> To: alto
> Subject: [alto] Work items for re-chartering
> 
> _______________________________________________
> alto mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/alto

---

From: "Y. Richard Yang" <[email-masked]>
Date: Fri, 24 Jan 2014 22:53:02 -0500

Dear all,

I support all of the 7 items. They provide key functions that together will
both fill some gaps in the base ALTO protocol and extend ALTO to be more
useful. As more networks open up to applications (e.g., some recent major
movement by ChinaTelecom), the new functionalities can be quite helpful to
allow ALTO to make a bigger impact!

Richard

-- 
-- 
 =====================================
| Y. Richard Yang <[email-masked]>   |
| Professor of Computer Science       |
| http://www.cs.yale.edu/~yry/        |
 =====================================

---

From: Qin Wu <[email-masked]>
Date: Sun, 26 Jan 2014 03:58:09 +0000

Hi, all:
I support adding the below 7 items into updated charter.
The proposed work in 7 items can bring a big enhancement to
the existing ALTO protocol.

Regards!
-Qin
-----Original Message-----
From: alto [mailto:[email-masked]] On Behalf Of Vijay K. Gurbani
Sent: Friday, January 24, 2014 3:11 AM
To: alto
Subject: [alto] Work items for re-chartering

Thanks.

- vijay

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Sun, 26 Jan 2014 04:29:27 +0000

I do not support all 7. In my opinion it will be more we can deliver.

The original charter was around, say, 15 months and 4 documents and we are late by 2 years.

I think we need a charter with a small number of documents we can deliver in a short timeframe.  Nothing wrong to continue to work on other extensions in the meantime and including then in another recharter.

Thanks,

From: "Y. Yang" <[email-masked]<mailto:[email-masked]>>
Date: Friday, January 24, 2014 at 7:53 PM
To: Vijay Gurbani <[email-masked]<mailto:[email-masked]>>
Cc: alto <[email-masked]<mailto:[email-masked]>>
Subject: Re: [alto] Work items for re-chartering

Dear all,

I support all of the 7 items. They provide key functions that together will both fill some gaps in the base ALTO protocol and extend ALTO to be more useful. As more networks open up to applications (e.g., some recent major movement by ChinaTelecom), the new functionalities can be quite helpful to allow ALTO to make a bigger impact!

Richard

On Thu, Jan 23, 2014 at 2:11 PM, Vijay K. Gurbani <[email-masked]<mailto:[email-masked]>> wrote:

Thanks.

- vijay
--
Vijay K. Gurbani, Bell Laboratories, Alcatel-Lucent
1960 Lucent Lane, Rm. 9C-533, Naperville, Illinois 60563 (USA)
Email: vkg@{bell-labs.com<http://bell-labs.com>,acm.org<http://acm.org>} / [email-masked]<mailto:[email-masked]>
Web: http://ect.bell-labs.com/who/vkg/  | Calendar: http://goo.gl/x3Ogq
_______________________________________________
alto mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/alto

--
--
 =====================================
| Y. Richard Yang <[email-masked]<mailto:[email-masked]>>   |
| Professor of Computer Science       |
| http://www.cs.yale.edu/~yry/        |
 =====================================

---

From: "Y. Richard Yang" <[email-masked]>
Date: Sat, 25 Jan 2014 23:45:32 -0500

How about give different milestones to different items, with some later
milestones? The chairs enforce more strictly the deadlines.

Thanks!

Richard

On Sat, Jan 25, 2014 at 11:29 PM, Reinaldo Penno (repenno) <
[email-masked]> wrote:

>  I think we need a charter with a small number of documents we can
> deliver in a short timeframe.  Nothing wrong to continue to work on other
> extensions in the meantime and including then in another recharter.
>
>  Thanks,
>
>
>   From: "Y. Yang" <[email-masked]>
> To: Vijay Gurbani <[email-masked]>
> Cc: alto <[email-masked]>
>  I support all of the 7 items. They provide key functions that together
> will both fill some gaps in the base ALTO protocol and extend ALTO to be
> more useful. As more networks open up to applications (e.g., some recent
> major movement by ChinaTelecom), the new functionalities can be quite
> helpful to allow ALTO to make a bigger impact!
>
>  Richard
>
>
> On Thu, Jan 23, 2014 at 2:11 PM, Vijay K. Gurbani <[email-masked]>wrote:
>

---

From: Dhruv Dhody <[email-masked]>
Date: Sun, 26 Jan 2014 10:43:36 +0530

Thanks Vijay and Enrico for preparing this list of possible work items.
I support all 7.

Regards,
Dhruv

---

From: "Songhaibin (A)" <[email-masked]>
Date: Mon, 27 Jan 2014 01:10:41 +0000

Hi Vijay,

I believe all these items are reasonable and there is enough energy from the group to finish the deliverables.

Best Regards!
-Haibin

> Folks: Over the last few IETFs, Enrico and I have solicited feedback during
> face-to-face meetings, WG sessions, hallway conversations, ALTO mailing list
> and private conversations on how to move ahead with respect to adopting new
> work items.
> 
> As we begin the charter discussions, we have identified seven work items to
> propose as additions to the charter.  The first four of these work items are
> fairly uncontroversial.  The last three are work items that have a monumental
> mind share in the ALTO working group and have been found to be extremely
> useful in controlled networks (e.g., VPNs).  However, we have to take some
> care in defining these such that we do not duplicate the functionality available
> elsewhere (e.g., general
> routing) in ALTO, nor do we take on an aspect that the working group does not
> fully understand.
> 
> We will like to understand whether the working group believe such additional
> deliverables, if included in an updated charter proposal, would allow people to
> do the extension work that has been repeatedly proposed. (Clarification: we
> are explicitly asking whether people could find such an update acceptable. We
> understand that anyone will have a preferred flavor of the above.)
> 
> We are at a point where show of support by whoever is interested is essential
> for moving forward. If it turns out to be positive, Enrico and I will subsequently
> circulate actual text, including milestones, for a rechartering request.
> 
> Thanks.
> 
> - vijay
> --

---

From: "Cao,Zhen" <[email-masked]>
Date: Mon, 27 Jan 2014 11:05:45 +0800

Dear all,

I support the above 7 items.

In addition, if the group could consider some deployment guide
document, it would be more than welcome.

thanks,
cz

---

From: Sebastian Kiesel <[email-masked]>
Date: Mon, 27 Jan 2014 09:38:55 +0100

Dear all,

I think that all 7 items are desirable and well-scoped goals.
I am willing to spend signficant energy on items 1. and 2.,
and I will comment on and contribute to all others.

Side note: for 3. and 4. the new work item description should really
make clear that we are going to evaluate general mechanisms (json patch,
http/2.0, etc.) first, before we start specifying ALTO-specific
mechanisms.

Thanks to Vijay and Enrico for putting this list together and starting
the discussion!

Sebastian

---

From: Sebastian Kiesel <[email-masked]>
Date: Mon, 27 Jan 2014 09:42:53 +0100

Dear Cao,Zhen,

> document, it would be more than welcome.

We are already working on a deployment considerations document:

http://datatracker.ietf.org/doc/draft-ietf-alto-deployments/

This document is currently being restructured.  If you think that
something is missing or if you want to contribute text please send an
email to the authors and/or the ALTO mailing list.

Thanks
Sebastian

---

From: "Scharf, Michael (Michael)" <[email-masked]>
Date: Mon, 27 Jan 2014 14:39:06 +0000

I think that all 7 items are important directions for ALTO, and they therefore should become charter items. In the WG there are already individual drafts for all items. 

My understanding is that re-chartering does not imply that a document has to be adopted by the WG immediately in every case. In particular, the milestone dates can take into account that some work has already been discussed extensively in the WG, whereas other items were mostly covered in side meetings only. 

Michael

---

From: "Scharf, Michael (Michael)" <[email-masked]>
Date: Mon, 27 Jan 2014 14:43:15 +0000

> From: alto [mailto:[email-masked]] On Behalf Of Sebastian Kiesel
> Sent: Monday, January 27, 2014 9:43 AM
> To: Cao,Zhen
> Cc: alto

Indeed, we currently update the deployment document. As usual in the IETF, text contributions would be very welcome.

Michael

---

From: "RANDRIAMASY, SABINE (SABINE)" <[email-masked]>
Date: Mon, 27 Jan 2014 16:08:33 +0000

Dear all,

I support all the listed 7 items as they significantly extend the capabilities of the ALTO Service and accordingly provide incentives to deploy it. I am willing to provide effort on topics relating to item 6 while providing help and feedback on the other ones.  

Like Richard and Michael, I figure that milestones may be set according to the work and discussions already done on the items.  

Thanks to Vijay and Enrico for starting the discussion,

Best regards,
Sabine

-----Message d'origine-----
De : alto [mailto:[email-masked]] De la part de Vijay K. Gurbani
Envoyé : jeudi 23 janvier 2014 20:11
À : alto
Objet : [alto] Work items for re-chartering

Folks: Over the last few IETFs, Enrico and I have solicited feedback during face-to-face meetings, WG sessions, hallway conversations, ALTO mailing list and private conversations on how to move ahead with respect to adopting new work items.

As we begin the charter discussions, we have identified seven work items to propose as additions to the charter.  The first four of these work items are fairly uncontroversial.  The last three are work items that have a monumental mind share in the ALTO working group and have been found to be extremely useful in controlled networks (e.g., VPNs).  However, we have to take some care in defining these such that we do not duplicate the functionality available elsewhere (e.g., general
routing) in ALTO, nor do we take on an aspect that the working group does not fully understand.

We will like to understand whether the working group believe such additional deliverables, if included in an updated charter proposal, would allow people to do the extension work that has been repeatedly proposed. (Clarification: we are explicitly asking whether people could find such an update acceptable. We understand that anyone will have a preferred flavor of the above.)

We are at a point where show of support by whoever is interested is essential for moving forward. If it turns out to be positive, Enrico and I will subsequently circulate actual text, including milestones, for a rechartering request.

Thanks.

- vijay
--
Vijay K. Gurbani, Bell Laboratories, Alcatel-Lucent 1960 Lucent Lane, Rm. 9C-533, Naperville, Illinois 60563 (USA)
Email: vkg@{bell-labs.com,acm.org} / [email-masked]
Web: http://ect.bell-labs.com/who/vkg/  | Calendar: http://goo.gl/x3Ogq _______________________________________________
alto mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/alto

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Mon, 27 Jan 2014 10:46:04 -0600

> milestones? The chairs enforce more strictly the deadlines.

For a recharter to be successful, we need to understand in sufficient
detail what we want to do.  The value proposition of the 7 items [0] is
not under dispute, as is evident by the rather strong show of support
thus far.  (Reinaldo's reticence duly noted and appreciated.)

Let's do a second order analysis on what we expect to have as an
outcome of the work item, "An ALTO format for encoding graphs."
Personally, I think that this is the most intriguing of the lot.

So, in order to ensure a common understanding such that we are
forearmed with answers to the questions we know we will get when
we recharter and assign milestones, let's do a bit of armchair
analysis on the encoding format for graphs.

Consider the following ALTO triangle:

                 PID-1
                 /   \
               2/     \ 3
               /       \
          PID-2--------PID-3
                   6

Today, ALTO knows the pair-wise cost (i.e., {PID-1,PID2}, {PID-2,PID-3}
and {PID-1,PID-3}) from the cost map.  So if a resource consumer is in
PID-2 and there are two resource producers, one in PID-1 and the second
in PID-3, ALTO will choose the producer in PID-1 because of the low
cost to get to PID-1.

The network map will be encoded as:

    "network-map" : {
      "PID3" : { "ipv4" : [ "0.0.0.0/0" ] },
      "PID1" : { "ipv4" : [ "192.0.2.0/24", "198.51.100.0/24" ] },
      "PID2" : { "ipv4" : [ "192.0.2.0/25", "192.0.2.128/25" ] }
    }

and a cost map as:

      "cost-map" : {
        "PID1": { "PID1": 1,  "PID2": 2,  "PID3": 3 },
        "PID2": { "PID1": 2,  "PID2": 1,  "PID3": 6 },
        "PID3": { "PID1": 3,  "PID2": 6  }
      }

Here, by design of the current ALTO protocol, the underlying network
(switches, links) are abstracted behind PIDs.

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?
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

Thanks!

- vijay

---

From: "Peterson, Jon" <[email-masked]>
Date: Mon, 27 Jan 2014 17:35:04 +0000

If ALTO doesn¹t take up some of these items, at least, I fear much of the
work to date may be for nought. We need 3, 4 and 5 for ALTO to be a
credible CDNi solution, for example. So yes, I would urge the group to
take up these work items. We can debate the priority among them, but let¹s
get them chartered and done.

Jon Peterson
Neustar, Inc.

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Mon, 27 Jan 2014 18:06:21 +0000

I would suggest looking at how RESTconf solved the server-side
notification issue. RESTconf and ALTO have a lot is common protocol wise.

http://tools.ietf.org/html/draft-bierman-netconf-restconf-03#page-41

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Mon, 27 Jan 2014 22:26:23 +0000

Agreed. I conveyed the same to the chairs offline but let me repeat here.

1 - ALTO as specified in draft-alto is something difficult to deploy in
production. 

2 - In other for ALTO to be a well-rounded, deployable, robust protocol we
need to do the first 4 items. In other words, I believe the first 4 items
are not extensions or enhancements, but the result of “bugs” that need
fixing.

3 - Item 5 is something I think has great potential. If we could choose
only one feature to include in the charter I would vote for number 5.

Thanks,

Reinaldo

---

From: "Scharf, Michael (Michael)" <[email-masked]>
Date: Tue, 28 Jan 2014 10:25:00 +0000

>   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.

> [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

---

From: Greg Bernstein <[email-masked]>
Date: Tue, 28 Jan 2014 07:35:44 -0800

Support all 7.
Greg

-- 
===================================================
Dr Greg Bernstein, Grotto Networking (510) 573-2237

---

From: Greg Bernstein <[email-masked]>
Date: Tue, 28 Jan 2014 07:53:40 -0800

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.

---

From: "Scharf, Michael (Michael)" <[email-masked]>
Date: Wed, 29 Jan 2014 10:49:29 +0000

Hi Greg,

Some comments inline [MS].

Michael

From: alto [mailto:[email-masked]] On Behalf Of Greg Bernstein
Sent: Tuesday, January 28, 2014 4:54 PM
To: [email-masked]
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.

  *   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.

  *   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.

graph [

   node [

      id 0

      label "PID-1"

      address-type "ipv4"

   ]

   node [

      id 1

      label "PID-2"

      address-type "ipv4"

   ]

   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:

  "multiple-switch" model?  Is something like this encoding one

possible

    a set of vertices

    a set of edges

Michael

alto mailing list

--

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Wed, 29 Jan 2014 17:04:17 -0600

Michael, Greg: Great dialogue.

I think as a general deliverable for "An ALTO format for encoding
graphs", this dialogue has shed some clarity on what could be the
outcome of such a deliverable.  The scope of what goes into encoding
the graph would be something that we should discuss as well.

It appears that normal attributes associated with graph representation
are in scope, and these include labels for vertices and edges, in-degree
and out-degree for vertices, the pair of vertices an edge connects,
and a set of properties associated with edges and vertices.  (This is
essentially the "property graph" model you outline in [1].)

I'd like to see what the thoughts are of you (and the working group)
on whether we end up using an existing format (and how that will
actually work with respect to the copyright holders, if any, of the
existing format) or do we come up with a new one?

Another question to consider is whether this new format will subsume
the existing topology map and cost map as well?  Or does this new
format only model individual hosts and the links connecting them
and stays away from representing the hosts in the aggregate (the PID
concept)?  Usages of ALTO that will benefit from existing concepts
(PIDs, pairwise costs) can continue to use the existing topologies and
cost maps.  Usages of ALTO that need more detailed knowledge of
individual hosts and link can use the new extension format for encoding
graphs.

Regarding the second sub-issue on the need for reductionist algebra for
graph transformations, I agree with you [1] that we leave that up to the
ALTO client.  I believe that such a strategy will allow Greg to derive
"service-specific" graphs that are transformed from an original graph.
Since the specific need for such "service-specific" graphs will be a
function of what the ALTO client wants, it seems reasonable to provide
building blocks in the form of an extension for encoding graphs that
can be coupled with the extensions for TE metrics
(draft-wu-alto-te-metrics).  It is up to the ALTO client to put these
together in some fashion that satisfies its constraints.

This will leave us with a reasonable and tractable problem to come up
with an extension to encode graphs, hopefully in a short time frame.

[1] http://www.ietf.org/mail-archive/web/alto/current/msg02365.html

Looking forward to your responses and insights.

Cheers,

- vijay

---

From: Greg Bernstein <[email-masked]>
Date: Fri, 31 Jan 2014 12:38:08 -0800

Hi Michael good conversation, see responses in line below.
Cheers
Greg
On 1/29/2014 2:49 AM, Scharf, Michael (Michael) wrote:
> *From:*alto [mailto:[email-masked]] *On Behalf Of *Greg Bernstein
> *Sent:* Tuesday, January 28, 2014 4:54 PM
> *To:* [email-masked]
> *Subject:* Re: [alto] Work items for re-chartering
>
>  
>
> 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.
>
--> The idea (in a VPN or other somewhat controlled context) is that the
network provider would take its internal graph representation such as
shown in figure 6 and reduce it based on such items as a limited
collection of potential source-destination pairs of interest to the
client, previously agreed on QoS measures or metrics.  Such a process
would not be subject to standardization. However, the paper was trying
to show that such "graph transformations" could be as simple or
complicated as the provider chose (but also that they were viable).
> ---snip---
>     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.
>
--> When we first presented the "high bandwidth use case" (summer of
2012) we did it in terms of lists of "abstract paths" (see section III.A
of the paper) and their mutual dependencies via share links. This is
particularly effective if the number of source-destination pair
candidates is limited, and the number of paths choices between a
source-destination pair is limited (e.g., IP with OSPF based routing as
the underlying technology).

I'm getting set to teach a graduate course on network design course and
have been surveying texts and the literature. Depending upon the
underlying technology and constraints two general approaches are
typically used: (a) link-path formulation, and (b) node-link
formulation. Our proposed extensions to ALTO to deal with bandwidth
constraints (capacitated design problem) can benefit from both
formulations depending on the context. However we want to keep the JSON
encoding as simple as possible.
> [MS] I don't understand this. What would be an ALTO-like example?
--> Once again I would use a VPN/private network example. For example
consider a campus of data centers with optical switches (WSON) used for
the inter-building network and SDN (OpenFlow) Ethernet switches for
intra building.  This would be a yet more sophisticated network
consumer, but not unreasonable given current networking trends. 
Although advanced I think we can allow for this type of extension via a
default single layer model with optional layer parameters as opposed to
required layer parameter  on very link, port, switching service as done
in the OGF.
>     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.
>
--> Just an idea not a requirement.
> Implicit via ordering in nodes array. But can use "id" attribute when
> converting from JSON to python representation
>
> Link ids
> Can contain location, has "life time concept", name, ports. Not
> directly associated with links but only through ports.
>
> 	
>
> Can contain coordinates
>
> 	
>
> Arbitrary.
>
> Link properties
>
> 	
>
> Routing cost, setup cost, pre-installed and additional modules that
> have increments of capacity. Must include source/target node references.
>
> 	
>
> This seems to be implemented by assigning ports, links, adaptation,
> and switching service all have a "encoding" parameter. Nodes and
> Topologies do not.
>
> 	
>
> No
>
> 	
>
> [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.
>
--> I was interested in their models structure and capability.  SNDlib
is used for conveying network design problems. OGF takes most of its
models from ITU. JSON seems to be able to accommodate all these modeling
situations.  I agree with you on NetworkX's drawback on implicit
ordering of the node array. Tinkerpop avoids this. But neither
NetworkX's JSON or Tinkerpop's are JSON formally defined.
--snip--

---

From: Greg Bernstein <[email-masked]>
Date: Fri, 31 Jan 2014 12:57:09 -0800

Hi Vijay, see comments below.
Cheers
Greg
> existing format) or do we come up with a new one?
--> NetworkX originated with a government research project is is open
sourced under BSD
(http://networkx.github.io/documentation/latest/overview.html#free-software). 
Hard to exactly say what the Tinkerpop open source license is
(https://github.com/tinkerpop/blueprints). However, neither of these is
formally defined at a sufficient level for standardization purposes,
i.e., not even close to the JSON standardized in the current ALTO spec.
As Michael pointed out the structure of a graph in JSON via node lists
and link lists with properties is a fairly generic notion. We'd need to
formalize it for interoperability sake. Note also that representing
paths as a list of links (link-path representation) is also fairly generic.
> individual hosts and link can use the new extension format for encoding
--> Not sure if this is possible. Was having related discussions with
Wendy and Richard, they may have more ideas on this.
> together in some fashion that satisfies its constraints.
--> Either the client or the server but not part of the standard. How a
network provider wants to represent
their network to a client is their business.  In the case of controlled
environments (VPN) the provider may
customize what they show to a particular client (based on pre-arranged
information that is out of our scope).

---

From: "Jan Medved (jmedved)" <[email-masked]>
Date: Fri, 31 Jan 2014 22:48:08 +0000

Network topology as a list of nodes and links is defined in
http://datatracker.ietf.org/doc/draft-clemm-netmod-yang-network-topo/.
This draft is implemented in the OpenDaylight controller as a part of the
Hydrogen Service Provider edition. OpenDaylight supports RESTconf v02
(http://datatracker.ietf.org/doc/draft-bierman-netconf-restconf) on its NB
interface and can provide data (including topology graphs) to clients in
both XML and JSON formats. OpenDaylight is open sourced under EPL.

Thanks,
/Jan