Subject: Re: [alto] Work items for re-chartering

From: Wendy Roome <[email-masked]>
Date: Mon, 27 Jan 2014 15:38:35 -0500

As for your specific questions,

(1) Is this what¹s meant by the ³multiple switch model²?

I believe so, although this graph is a very simple example. My take is
that with the ³single switch² model, we think of every host on the planet
connected by a dedicated line to one central switch (with a LOT of ports).
That¹s the ³blob² model, where we show the net as a cloud with lots of
devices connected to it, and no idea about the blob¹s internal structure.

The ³multiple switch² model simply exposes some of the network blob¹s
internal structure.

(2) What sort of algebraic formulations do we expect Š.

That¹s messier, and I¹ll leave that to Richard Yang.

As for your pseudo-JSON description of the network, remember that nodes do
NOT have to be PIDs. I think all PIDs must be nodes, but not vice versa.

Also, I suggest using a separate ³node property service² for all but the
most essential attributes of nodes & links.

	- Wendy Roome

On 01/27/2014, 15:00, "[email-masked]" <[email-masked]>
wrote:

>Message: 2
>Date: Mon, 27 Jan 2014 10:46:04 -0600
>From: "Vijay K. Gurbani" <[email-masked]>
>To: "Y. Richard Yang" <[email-masked]>
>Cc: alto <[email-masked]>
>Subject: Re: [alto] Work items for re-chartering
>Message-ID: <[email-masked]>
>Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
>On 01/25/2014 10:45 PM, Y. Richard Yang wrote:
>>How about give different milestones to different items, with some later
>>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
>--
>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: QIN WU <[email-masked]>
Date: Wed, 29 Jan 2014 13:24:15 +0800

------------------------------

   - *From*: "Reinaldo Penno (repenno)" <repenno at cisco.com
<[email-masked]>>
   - *To*: "Peterson, Jon" <jon.peterson at neustar.biz
<[email-masked]>>, "Vijay K. Gurbani" <vkg at
bell-labs.com <[email-masked]>>, alto <alto at ietf.org
<[email-masked]>>
   - *Date*: Mon, 27 Jan 2014 22:26:23 +0000
   - *In-reply-to*: <[email-masked]
<http://www.ietf.org/mail-archive/web/alto/current/msg02360.html>>

------------------------------

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.

[Qin]:I fail and am confused to see first 4 items not extensions or
enhancements.

I see service orientated infrastructure has a lot of promising. Item 6
"ALTO Cost metrics extesion" does aim at that and provide various cost
metric for different application, e.g., latency sensitive
application,bandwidth sensitive application.
[I.D-ietf-idr-ls-distribution] and [I.d-ietf-idr-te-pm-bgp] have already
provided BGP extension to distribute TE information and network
performance information to ALTO server, see figure 3 of
[I.D-ietf-idr-ls-distribution] and figure 2 of
[I.d-ietf-idr-te-pm-bgp].

These information can be collected and aggregated by ALTO server using
routing protocol (see figure 1 of ALTO base protocol) and can be used
in the same way as routingcost metric.

This information doesn't need to disclosed as output to application
but as constraint based on policies and rules set by the operator and
allows application to connect better endpoint.

item 6 just adds a few addtional cost metric and is not a big work.

>From this  perspective, I could also say item 6 is more about a bug fixing.

Thanks,

Reinaldo

On 1/27/14, 9:35 AM, "Peterson, Jon" <jon.peterson at neustar.biz> wrote:

>
>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.
>
>On 1/23/14, 11:11 AM, "Vijay K. Gurbani" <vkg at bell-labs.com> wrote:
>
>>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.)

---

From: QIN WU <[email-masked]>
Date: Wed, 29 Jan 2014 13:57:17 +0800

- *From*: "Scharf, Michael (Michael)" <michael.scharf at
   alcatel-lucent.com <[email-masked]>>
   - *To*: "Gurbani, Vijay K (Vijay)" <vijay.gurbani at
alcatel-lucent.com<[email-masked]>>,
   "Y. Richard Yang" <yry at cs.yale.edu <[email-masked]>>
   - *Cc*: alto <alto at ietf.org <[email-masked]>>
   - *Date*: Tue, 28 Jan 2014 10:25:00 +0000
   - *In-reply-to*:
<[email-masked]<http://www.ietf.org/mail-archive/web/alto/current/msg02359.html>
   - *References*: <CANUuoLr69e3H3UzsYsQ=kfhwdi=
   [email-masked]>
<[email-masked]<http://www.ietf.org/mail-archive/web/alto/current/msg02349.html>>
   <[email-masked]<http://www.ietf.org/mail-archive/web/alto/current/msg02350.html>>
   <[email-masked]<http://www.ietf.org/mail-archive/web/alto/current/msg02359.html>

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

[Qin]: Good interpretation. I think in some cases, we may need to
establishtunnel between any two vertexs and stitching them together to
get end to end path. The end to end path is consisted of  a set of
edges. To achieve what you describe above, we need to introduce a lot
of vertext properties extension or endpoint properties extension and
even cost metric extension.

draft-wu-alto-endpoint-pid-properties-00

(http://tools.ietf.org/html/draft-wu-alto-endpoint-pid-properties-00)

provide an example for how these endpoint properties may look like.

However draft-wu-alto-endpoint-pid-properties-00 more focuses on
virtualized world.

> [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: QIN WU <[email-masked]>
Date: Wed, 29 Jan 2014 14:02:55 +0800

- *From*: Wendy Roome <w.roome at alcatel-lucent.com<[email-masked]>
   - *To*: <alto at ietf.org <[email-masked]>>
   - *Date*: Mon, 27 Jan 2014 15:38:35 -0500

[Qin]: I believe such network blob's internal structure is expressed
in the form PID properties extension or endpoint properties extension.