Subject: [alto] ALTO topology design issues

From: "Y. Richard Yang" <[email-masked]>
Date: Fri, 7 Nov 2014 15:28:34 -0500

Dear all,

As we are preparing for the slides on a potential ALTO topology extension
(node-link graph), we have a few design choices that can benefit from some
discussions in the WG list.

1. path vector vs flow

Starting from -03, the document introduced the concept of a path vector
mode as a generic mechanism to provide topology/routing information. Upon
writing the slides, however, we found that to handle multi-path routing
(e.g., ECMP), we will need a simple flow routing concept, where path vector
is a special case. Any comments on extending to this direction will be
appreciated.

2. property graph as a node-graph foundation

Another design choice, when introducing node-link graph, is
(1) adding network nodes in the network map, and hence we have a single
place for all network nodes, and PID properties can provide properties for
all such nodes; or
(2) separate PIDs (endpoint user groups) from network nodes. This may be
conceptually cleaner. Then it implies two types of links, which will be
captured by property graphs.

If you have any comments on this aspect, please share your opinions.

3. Subgraph selection API

How to provide a generic mechanism to allow an ALTO client to select a
subgraph is still not clear--it will depend on the use cases. So far, the
first selection service is the expander of a given set of src/dst PIDs: the
expander is the union of path vectors (or flows, if we consider
multi-path). If you have any opinions on this aspect, please let us know.

Cheers,

Richard

---------- Forwarded message ----------
From: <[email-masked]>
Date: Mon, Oct 27, 2014 at 7:41 PM
Subject: New Version Notification for draft-yang-alto-topology-05.txt
To: Greg Bernstein <[email-masked]>, Michael Scharf <
[email-masked]>, Wendy Roome <[email-masked]>,
Young Lee <[email-masked]>, "Y. Richard Yang" <[email-masked]>

A new version of I-D, draft-yang-alto-topology-05.txt
has been successfully submitted by Y. Richard Yang and posted to the
IETF repository.

Name:           draft-yang-alto-topology
Revision:       05
Title:          ALTO Topology Extensions
Document date:  2014-10-27
Group:          Individual Submission
Pages:          18
URL:
http://www.ietf.org/internet-drafts/draft-yang-alto-topology-05.txt
Status:         https://datatracker.ietf.org/doc/draft-yang-alto-topology/
Htmlized:       http://tools.ietf.org/html/draft-yang-alto-topology-05
Diff:           http://www.ietf.org/rfcdiff?url2=draft-yang-alto-topology-05

Abstract:
   The Application-Layer Traffic Optimization (ALTO) Service has defined
   network and cost maps to provide basic network information.  In this
   document, we discuss designs to provide abstracted graph
   representations of network topology.  We start with a basic
   application use case of multi-flow scheduling using ALTO.  We show
   that ALTO cost maps alone cannot provide sufficient information.  We
   then define one key, generic component to address the issues:
   introducing path vectors in cost maps.  We specify two approaches to
   complement path vectors and achieve a complete design: an approach
   using opaque network elements and another using a graph (node-link)
   representation.

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

The IETF Secretariat

---

From: Xiao SHI <[email-masked]>
Date: Fri, 7 Nov 2014 20:39:26 -0500

Hi Richard,

2. For the property graph foundation, I think separating PIDs from network
nodes is a cleaner design for the following reasons:
(1) The alto topology service will be able to hide unnecessary information
from clients who don't need it. e.g. if an alto client don't need topology
at all and simply requested the network map, the server would not need to
send all the network nodes as PIDs in the network map.
(2) One argument of unifying network nodes with PIDs is the homogeneity
when processing the topology map. However, the server or the client would
still need to distinguish whether a node is a PID or a network node because
PIDs don't relay.
(3) PID property service would indeed make encoding network node properties
convenient. In a property graph, one can use the node properties to encode
properties for network nodes, which is not too bad either.

3. by "subgraph selection API," I assume that you meant the transformation
and operations in Appendix A of the document?

There could be two options for the user input, depending on where the
majority of the computational burden falls (client side vs. server side.):
(1) if the client sends a set of (src, dst) PID pairs to the server,
indicating that those are the interested routes, the client will need to
provide a cost-metric calculation function (e.g. hopcount, avail-bandwidth,
etc), which might be hard to encode in the HTTP request/hard to define.
(2) The alternative is for the server to send a default high level topology
upon request, then the client further request on details that it's
interested in (i.e. zooming in). The computational burden falls on the
client side in this case. Remaining questions are how does the client know
where to "zoom in," perhaps on common vertices/edges between its interested
paths?

My two cents,
Xiao

On Fri, Nov 7, 2014 at 3:28 PM, Y. Richard Yang <[email-masked]> wrote:

> [email-masked]>, Wendy Roome <
> [email-masked]>, Young Lee <[email-masked]>, "Y. Richard
> Yang" <[email-masked]>
>
>
>
> Diff:
> http://www.ietf.org/rfcdiff?url2=draft-yang-alto-topology-05
>
> Abstract:
> _______________________________________________
> alto mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/alto
>
>

---

From: "Y. Richard Yang" <[email-masked]>
Date: Mon, 10 Nov 2014 09:47:02 -0500

Hi Xiao,

On Nov 7, 2014 8:39 PM, "Xiao SHI" <[email-masked]> wrote:
>
> Hi Richard,
>
> 2. For the property graph foundation, I think separating PIDs from
network nodes is a cleaner design for the following reasons:
> (1) The alto topology service will be able to hide unnecessary
information from clients who don't need it. e.g. if an alto client don't
need topology at all and simply requested the network map, the server would
not need to send all the network nodes as PIDs in the network map.

This is a reasonable argument that I buy.

> (3) PID property service would indeed make encoding network node
properties convenient. In a property graph, one can use the node properties
to encode properties for network nodes, which is not too bad either.

Right. Adding a point of reusing PID properties, different nodes will have
different sets of properties.

>
> 3. by "subgraph selection API," I assume that you meant the
transformation and operations in Appendix A of the document?

This is interesting. Gremlin has path function which could be sent. I was
thinking something simpler: fixed set of standard functions.

> (2) The alternative is for the server to send a default high level
topology upon request, then the client further request on details that it's
interested in (i.e. zooming in). The computational burden falls on the
client side in this case. Remaining questions are how does the client know
where to "zoom in," perhaps on common vertices/edges between its interested
paths?

I like zooming. Still not clear how a client can select pointa to zoom. Any
details?

Richard
>> As we are preparing for the slides on a potential ALTO topology
extension (node-link graph), we have a few design choices that can benefit
from some discussions in the WG list.
>> Status:
https://datatracker.ietf.org/doc/draft-yang-alto-topology/

---

From: Xiao SHI <[email-masked]>
Date: Tue, 11 Nov 2014 01:19:25 -0500

Hi Richard,

I don't have a fully formed idea of how a client would select nodes/edges
to zoom in, but here's a possible option:

Suppose the client knows that it's interested in paths p1: PID1->PID3 and
p2: PID2->PID4, and from the default topology the server initially sends
back (i.e. a bird's eye view of the PIDs and only a few switches), paths p1
and p2 has one common node/edge. Say p1 = {PID1->sw1->sw5->sw3->PID3} and
p2 = {PID2->sw2->sw5->sw3->PID3}, then the common node is sw5. Then the
client would know that it is possible that sw5 is a overlay node which may
become the bottleneck of its performance, and the client hereby knows to
request a more detailed topology on sw5 (i.e. zoom in on sw5).

To request the zoom in, the client sends the necessary meta info on the
topology map (e.g. resource-id, [tag,] dependent vtags), an operation field
that specifies "zoom-in", as well as a set of network elements
(nodes/edges) that the client is interested in zooming in on, in the above
example, {'sw5'}. The server would respond with a more fine-grained
topology map.

A crude example would be:
{
  "resource-id" : "my-default-topology-map",
  "dependent-vtags" : [...],
  "operation" : "zoom-in",
  "network-element-set" : {'sw5'}
}

Some other useful operations can be "zoom-out" (i.e. switch aggregation, O2
in Appendix A of the draft), "zoom-in-all" which requests for a more fine
grained topology across the board for all network elements.

Also, our topology extension need not specify how a client figures out
which elements to zoom in on, as that's up to the algorithm of the client
app.

Thoughts and comments?

Best,
Xiao

On Mon, Nov 10, 2014 at 9:47 AM, Y. Richard Yang <[email-masked]> wrote:

> I like zooming. Still not clear how a client can select pointa to zoom.
> Any details?
>
> Richard
>
> >
> > My two cents,
> > Xiao
> >
> >> (2) separate PIDs (endpoint user groups) from network nodes. This may
> be conceptually cleaner. Then it implies two types of links, which will be