Subject: [alto] ALTO topology/graph representation (Fwd: New Version Notification for draft-yang-alto-topology-03.txt)

From: "Y. Richard Yang" <[email-masked]>
Date: Wed, 2 Jul 2014 01:58:00 -0400

Dear all,

We have submitted an update of the net-graph draft below. The goal of the
draft is to study the graph representation WG item. Here is a quick summary
of some key components of the draft and related issues:

1. A parallel draft by Michael Scharf (who is a co-author of this draft) as
well will be posted soon. Michael's draft will emphasize more on the scope
of the work, to avoid conflict with the Routing Area.

2. The draft uses a simple multi-flow scheduling use case to argue that we
need an path-vector + X representation. We do not have a formal proof that
path-vector must be used, but we do not see an alternative without using
path-vectors to convey network policies. This is important given that ALTO
targets applications and hence needs to convey network policy constraints.
If you have a counter-argument (i.e., solution), or a more formal argument,
we are eager to listen to your point of view.

3. The draft gives two possibilities for the aforementioned X to complete
the design: (1) X is an unstructured hash from network element to element
properties, and (2) X is a node-edge graph representation. In (1), there is
actually no need to distinguish between nodes and edges. From the
multi-flow use case alone, we cannot make a convincing argument that we
need the more structured case of (2). To finish the argument for using X =
node-edge graph, we feel that we will have to need an application-layer
guided network-layer routing (e.g., SDN) use case. Any insightful
input/comments on this aspect will be highly interesting and appreciated!

Richard

---------- Forwarded message ----------
From: <[email-masked]>
Date: Wed, Jul 2, 2014 at 12:58 AM
Subject: New Version Notification for draft-yang-alto-topology-03.txt
To: Greg Bernstein <[email-masked]>, Michael Scharf <
[email-masked]>, "Y. Richard Yang" <[email-masked]>,
Young Lee <[email-masked]>, Wendy Roome <[email-masked]>

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

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

Abstract:
   The Application-Layer Traffic Optimization (ALTO) Service has defined
   Network and Cost maps to provide basic network information.  In this
   document, we discuss an initial design to provide abstracted graph
   representations of network topology, motivated by a basic application
   use case of multi-flow scheduling.  The design is based on the ALTO
   WG discussions at IETF 89.

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

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

---

From: "Scharf, Michael (Michael)" <[email-masked]>
Date: Wed, 2 Jul 2014 19:20:57 +0000

Hi all,

As mentioned by Richard, I happened to write some text as well. Having a second draft was actually not intended by me.

Anyway, I used slides 24 and 25 from the last meeting http://tools.ietf.org/agenda/89/slides/slides-89-alto-2.pdf as basis of a model, and since these slides were joint work with Richard, Young, and Greg, my model and wording is very similar to draft-yang-alto-topology.

You can now find my writeup in http://tools.ietf.org/html/draft-scharf-alto-topology-00

From a technical perspective, the model in draft-yang-alto-topology has a much better formal definition and it seems to me like a better starting point for moving forward this work in the ALTO WG.

Therefore, I suggest to focus the discussion on draft-yang-alto-topology instead of my specific model. I actually only post this document now given that it has been mentioned already. Perhaps some of the text on the scope could be re-used.

Thanks

Michael

From: alto [mailto:[email-masked]] On Behalf Of Y. Richard Yang
Sent: Wednesday, July 02, 2014 7:58 AM
To: IETF ALTO
Subject: [alto] ALTO topology/graph representation (Fwd: New Version Notification for draft-yang-alto-topology-03.txt)

Dear all,

We have submitted an update of the net-graph draft below. The goal of the draft is to study the graph representation WG item. Here is a quick summary of some key components of the draft and related issues:

1. A parallel draft by Michael Scharf (who is a co-author of this draft) as well will be posted soon. Michael's draft will emphasize more on the scope of the work, to avoid conflict with the Routing Area.

2. The draft uses a simple multi-flow scheduling use case to argue that we need an path-vector + X representation. We do not have a formal proof that path-vector must be used, but we do not see an alternative without using path-vectors to convey network policies. This is important given that ALTO targets applications and hence needs to convey network policy constraints. If you have a counter-argument (i.e., solution), or a more formal argument, we are eager to listen to your point of view.

3. The draft gives two possibilities for the aforementioned X to complete the design: (1) X is an unstructured hash from network element to element properties, and (2) X is a node-edge graph representation. In (1), there is actually no need to distinguish between nodes and edges. From the multi-flow use case alone, we cannot make a convincing argument that we need the more structured case of (2). To finish the argument for using X = node-edge graph, we feel that we will have to need an application-layer guided network-layer routing (e.g., SDN) use case. Any insightful input/comments on this aspect will be highly interesting and appreciated!

Richard

---------- Forwarded message ----------
From: <[email-masked]<mailto:[email-masked]>>
Date: Wed, Jul 2, 2014 at 12:58 AM
Subject: New Version Notification for draft-yang-alto-topology-03.txt
To: Greg Bernstein <[email-masked]<mailto:[email-masked]>>, Michael Scharf <[email-masked]<mailto:[email-masked]>>, "Y. Richard Yang" <[email-masked]<mailto:[email-masked]>>, Young Lee <[email-masked]<mailto:[email-masked]>>, Wendy Roome <[email-masked]<mailto:[email-masked]>>

URL:            http://www.ietf.org/internet-drafts/draft-yang-alto-topology-03.txt

Abstract:

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<http://tools.ietf.org>.

The IETF Secretariat

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

---

From: Greg Bernstein <[email-masked]>
Date: Thu, 03 Jul 2014 11:08:49 -0700

Hi Richard and thanks for keeping this work moving.  I'd like to make a
few comments.

(a) Formal proof of the need for topology info?  I think this draft,
Michael's draft and previous drafts have essentially proven that to
support multiple-flow scenarios with resource constraints we must have
increased network information (some kind of topology info).  The current
draft illustrates this requirement with a bottleneck link example for a
multi-flow application.  Previous drafts have pointed out that resilient
(enhanced reliability) applications also require topology info.  If
needed we can get more formal than what is in the current draft.

(b) We have given two general approaches to conveying abstracted
topology information. (1) An abstract path-vector approach where
candidate (potential) paths are listed along with there properties and
dependencies, e.g., shared bottleneck (or risk) links. (2) An abstract
graph representation with pertinent costs and constraint attributes on
the abstracted network elements.  Note that we really mean "abstracted"
paths or network elements. The provider is not sharing details of there
network with the user, only enough information for the user/provider to
achieve their goals with "better than random efficiency". How to go from
an internal management or routing system network description to such an
abstract description is out of scope for this draft.  Some ideas on how
this can be done can be found in
http://grotto-networking.com/files/BandwidthConstraintModeling.pdf.

(c) Why two topology representations? The abstract path vector permits
the greatest abstraction, but can have scalability issues as mentioned
in the draft.  In modern formulations of network design/allocation
problems [1] the abstract path-vector would correspond to what is known
as a "link-path" formulation, and the graph representation to a
"node-link" formulation.  There are differences in what applications
(design/optimization problems) these two approaches are best suited
for[1]. I just finished teaching a graduate network design course using
[1] and have posted all my course slides and sample (Python) code
tohttp://grotto-networking.com/netDesignCourse.html
<http://grotto-networking.com/netDesignCourse.html> see the Lecture #7
slides for the basics.

 Reference [1]: Michal Pioro and Deepankar Medhi, /Routing, Flow, and
Capacity Design in Communication and Computer Networks/, Morgan
Kaufmann, 2004.

(d) As Richard mentioned there are some options on how to best complete
the JSON extensions to support topology extensions. We have from
previous drafts a number of test cases that we want to make sure are
supported but are very flexible in the details.  I the network design
course I just used the NetworkX JSON format for graphs and added
properties for convenience (see Lecture #8), however as previously
discussed on the list (or side discussions) it isn't quite optimal for
ALTO-topology.  However, JSON itself is very flexible and desirable.
With just a few added link/node properties we were able to model,
formulate and solve multi-layer network problems via JSON (see Lectures
16 and 17).

Best Regards
Greg B.

On 7/1/2014 10:58 PM, Y. Richard Yang wrote:
> Dear all,
>
> We have submitted an update of the net-graph draft below. The goal of
> the draft is to study the graph representation WG item. Here is a
> quick summary of some key components of the draft and related issues:
>
> 1. A parallel draft by Michael Scharf (who is a co-author of this
> draft) as well will be posted soon. Michael's draft will emphasize
> more on the scope of the work, to avoid conflict with the Routing Area.
>
> 2. The draft uses a simple multi-flow scheduling use case to argue
> that we need an path-vector + X representation. We do not have a
> formal proof that path-vector must be used, but we do not see an
> alternative without using path-vectors to convey network policies.
> This is important given that ALTO targets applications and hence needs
> to convey network policy constraints. If you have a counter-argument
> (i.e., solution), or a more formal argument, we are eager to listen to
> your point of view.
>
> 3. The draft gives two possibilities for the aforementioned X to
> complete the design: (1) X is an unstructured hash from network
> element to element properties, and (2) X is a node-edge graph
> representation. In (1), there is actually no need to distinguish
> between nodes and edges. From the multi-flow use case alone, we cannot
> make a convincing argument that we need the more structured case of
> (2). To finish the argument for using X = node-edge graph, we feel
> that we will have to need an application-layer guided network-layer
> routing (e.g., SDN) use case. Any insightful input/comments on this
> aspect will be highly interesting and appreciated!
>
> Richard
>
>
>
> From: <[email-masked] <mailto:[email-masked]>>
> To: Greg Bernstein <[email-masked]
> <mailto:[email-masked]>>, Michael Scharf
> <[email-masked]
> <mailto:[email-masked]>>, "Y. Richard Yang"
> <[email-masked] <mailto:[email-masked]>>, Young Lee
> <[email-masked] <mailto:[email-masked]>>, Wendy Roome
> <[email-masked] <mailto:[email-masked]>>
>
>
>
> Diff:          
> http://www.ietf.org/rfcdiff?url2=draft-yang-alto-topology-03
>
> Abstract:
> | Y. Richard Yang <[email-masked] <mailto:[email-masked]>>   |
> | http://www.cs.yale.edu/~yry/ <http://www.cs.yale.edu/%7Eyry/>        |
> _______________________________________________
> alto mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/alto

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