Subject: [altoext] General Applicability of a Cost Graph?

From: Greg Bernstein <[email-masked]>
Date: Mon, 16 Apr 2012 11:13:22 -0700

Hi all, I wanted to see what the intersection between the "high 
bandwidth use cases", "Data Center", and "CDN uses" might be.
In particular we (high bandwidth folks) are interested in "Cost Graph" 
type of information and given a bit more formally at the end of this 
e-mail. Starting from the ALTO protocol document and looking at 
extensions we have:

 1. ALTO provides for "path cost", endpoint properties, and endpoint
    costs. Registry allows for new costs types in addition to 'exp:' and
    'priv:' prefixed cost identifiers.
 2. In draft-randriamasy-alto-multi-cost-06, Multi-Cost ALTO, bandwidth
    was brought up as a possible cost type. This seems to have wide
    applicability in the controlled and partially controlled cases. They
    call this "*/path bandwidth/*". --> We'd like standard latency and
    bandwidth cost types if possible.
 3. However "path bandwidth" would typically be used with some type of
    "routing cost", and perhaps a "latency cost". This leads to a
    "*/multi-cos//t/*" scenario. --> We'd like multiple costs at once
    (e.g., bandwidth, routing, latency)
 4. Bandwidth is much different from a hop count or distance based
    "routing cost". We have illustrated in our high bandwidth use case
    draft how "bottleneck" links can lead to erroneous assumptions on
    network capacity and we introduced a "*/cost graph/*" representation
    to more accurately model the network. --> We really need graph
    representation for high bandwidth situation. We gave examples in our
    high bandwidth draft and BoF presentation.

A graph based model seems generally useful.  For example, it seems to me 
that this could be applicable to Data Center and possibly CDN 
situations. For example in the Data Center presentation 
(http://www.ietf.org/proceedings/83/slides/slides-83-i2aex-2.pdf) there 
was a use case on "Network Rack/Location Awareness" (slide 8). There 
seem to be a variety of data center network architectures (top of rack, 
end of row, fabric extenders, etc). It seems that that bandwidth 
constraints of such different designs could be well modeled via a cost 
graph, i.e., use a cost graph for VM placement and such... Similar 
comments apply to the "Use Case: Hybrid Cloud Bandwidth On Demand" on 
slide 9.  Data center and CDN folks any opinions on your needs/desires 
for potential extensions mention in items 2-4 above?

Cheers

Greg B.

A cost graph can be represented as a set of links with properties 
(costs). Possible cost graph JSON encoding:
// Simple Link object

object {

NIDName aend;// Node ids (NIDs) are similar to PIDs but

NIDName zend;// may not have endpoints, i.e., just a node for modeling.

JSONNumber wt; //A numerical routing cost

JSONNumber delay; //A numerical latency cost, optional

JSONNumber bw;//A numerical bandwidth "cost", optional

// Other costs private or experimental could be added

// for example stuff related to reliability or economic cost.

// Only one cost of each type would be permitted.

// Note a multi-cost like mechanism could be used.

} LinkData

// Collection of links each identified by link id (LID) name (LIDName).

object {

LinkData [lidname]<0..*>;    // Link id (LID) would be an identifier 
similar to

...                          // a PID or NID an identifies the link

} NetworkLinkData;

// The graph

object {

VersionTagmap-vtag;

NetworkLinkData graph;

} InfoResourceNetworkGraph;

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

---

From: "Y. Richard Yang" <[email-masked]>
Date: Mon, 16 Apr 2012 15:46:13 -0400

Hi Greg,

I agree that Cost Graph, in addition to Cost Map, is a good concept to 
add to ALTO. Conceptually:

- (E2E) Cost Map: "An ALTO Cost Map defines Path Costs pairwise amongst 
sets of source and destination Network Locations.  Each Path Cost is the 
end-to-end cost from the source to the destination." The key is that the 
information is end-to-end.

- (Link) Cost Graph (or Link-Cost Graph):  represents per-link info.

I see that we need a path-vector (E2E) Cost Map to connect the (E2E) 
Cost Map and the (Link) Cost Map, where the two maps need to be defined 
on the same set of network nodes (Network Map).

Do I understand you correctly?

I feel that we may need to understand the semantics first before we 
proceed to define the syntax representation: there are multiple data 
structures to represent a graph (e.g., adjacency matrix, collections of 
adjacency lists where each list is defined for one source node, or a set 
of links, as you defined in the email). The current (E2E) Cost Map is 
using mostly an adjacency matrix representation and can represent a 
graph as well, with different semantics though, and with different 
representation efficiency.

One additional (Link) info I see for (Link) Cost Graph as you defined at 
the end of your email is SRLG, for example, each Link includes a list of 
tags of shared risk link group.

Thanks!

Richard

On 4/16/12 2:13 PM, Greg Bernstein wrote:
>     costs. Registry allows for new costs types in addition to 'exp:'
>     and 'priv:' prefixed cost identifiers.
>  2. In draft-randriamasy-alto-multi-cost-06, Multi-Cost ALTO,
>     bandwidth was brought up as a possible cost type. This seems to
>     have wide applicability in the controlled and partially controlled
>     cases. They call this "*/path bandwidth/*". --> We'd like standard
>     latency and bandwidth cost types if possible.
>     network capacity and we introduced a "*/cost graph/*"
>     representation to more accurately model the network. --> We really
>     need graph representation for high bandwidth situation. We gave
>     examples in our high bandwidth draft and BoF presentation.
>
> A graph based model seems generally useful.  For example, it seems to 
> me that this could be applicable to Data Center and possibly CDN 
> (http://www.ietf.org/proceedings/83/slides/slides-83-i2aex-2.pdf) 
> there was a use case on "Network Rack/Location Awareness" (slide 8). 
> There seem to be a variety of data center network architectures (top 
> of rack, end of row, fabric extenders, etc). It seems that that 
> bandwidth constraints of such different designs could be well modeled 
> via a cost graph, i.e., use a cost graph for VM placement and such... 
> Similar comments apply to the "Use Case: Hybrid Cloud Bandwidth On 
> Demand" on slide 9.  Data center and CDN folks any opinions on your 
> needs/desires for potential extensions mention in items 2-4 above?
>
> Cheers
>
> Greg B.
>
> _______________________________________________
> altoext mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/altoext

---

From: Ben Niven-Jenkins <[email-masked]>
Date: Mon, 16 Apr 2012 21:44:04 +0100

Greg,

I wonder if splitting the topology from the costs (like it is in ALTO today) would be beneficial - i.e having a Network Graph & associated Cost Graph(s). Maybe because some clients might be interested in the network topology but be happy with E2E costs they don't need to compute?

I haven't really followed the large bandwidth use cases but one thing that strikes me between my CDN use cases and the large bandwidth use cases (and maybe also the DC ones) is the level of granularity of information required.

In the CDN use cases I have I need finer granularity of network topology than a peer to peer client[1] but I still only require an abstract view of the topology - i.e. I don't need to know about individual links/routers or about the topology between CDN locations etc. 

So a good part of the value of an ALTO server/solution is that it performs that abstraction for me. For the large bandwidth use cases I get the impression that knowing detailed topology is important and so ALTO is not really performing the role of an abstraction layer and is just performing the role of an API to obtain topology information.

Ben

[1] I have to model a PID per "clump" of end users and a PID per network location containing a CDN device rather than peer to peer that probably models something more akin to "my local peers", "peers on my ISPs network", "preferred transit peers", "everyone else".

On 16 Apr 2012, at 19:13, Greg Bernstein wrote:

> Hi all, I wanted to see what the intersection between the "high bandwidth use cases", "Data Center", and "CDN uses" might be.
> In particular we (high bandwidth folks) are interested in "Cost Graph" type of information and given a bit more formally at the end of this e-mail. Starting from the ALTO protocol document and looking at extensions we have:
> 	• ALTO provides for "path cost", endpoint properties, and endpoint costs. Registry allows for new costs types in addition to 'exp:' and 'priv:' prefixed cost identifiers.  
> 	• In draft-randriamasy-alto-multi-cost-06, Multi-Cost ALTO, bandwidth was brought up as a possible cost type. This seems to have wide applicability in the controlled and partially controlled cases. They call this "path bandwidth". --> We'd like standard latency and bandwidth cost types if possible.
> 	• However "path bandwidth" would typically be used with some type of "routing cost", and perhaps a "latency cost". This leads to a "multi-cost" scenario. --> We'd like multiple costs at once (e.g., bandwidth, routing, latency)
> 	• Bandwidth is much different from a hop count or distance based "routing cost". We have illustrated in our high bandwidth use case draft how "bottleneck" links can lead to erroneous assumptions on network capacity and we introduced a "cost graph" representation to more accurately model the network. --> We really need graph representation for high bandwidth situation. We gave examples in our high bandwidth draft and BoF presentation.
> A graph based model seems generally useful.  For example, it seems to me that this could be applicable to Data Center and possibly CDN situations. For example in the Data Center presentation (http://www.ietf.org/proceedings/83/slides/slides-83-i2aex-2.pdf) there was a use case on "Network Rack/Location Awareness" (slide 8). There seem to be a variety of data center network architectures (top of rack, end of row, fabric extenders, etc). It seems that that bandwidth constraints of such different designs could be well modeled via a cost graph, i.e., use a cost graph for VM placement and such... Similar comments apply to the "Use Case: Hybrid Cloud Bandwidth On Demand" on slide 9.  Data center and CDN folks any opinions on your needs/desires for potential extensions mention in items 2-4 above?
> 
> Cheers
> 
> Greg B.
> 
> A cost graph can be represented as a set of links with properties (costs). Possible cost graph JSON encoding:
> // Simple Link object
> object {
>       NIDName aend;     // Node ids (NIDs) are similar to PIDs but
>       NIDName zend;     // may not have endpoints, i.e., just a node for modeling.
>       JSONNumber bw;    //A numerical bandwidth "cost",       optional
>      LinkData [lidname]<0..*>;    // Link id (LID) would be an identifier similar to
>      VersionTag     map-vtag;

---

From: Greg Bernstein <[email-masked]>
Date: Tue, 17 Apr 2012 07:33:05 -0700

Good to hear from you Richard and good points. See comments below.
Greg
On 4/16/2012 12:46 PM, Y. Richard Yang wrote:
> - (E2E) Cost Map: "An ALTO Cost Map defines Path Costs pairwise 
> amongst sets of source and destination Network Locations.  Each Path 
> Cost is the end-to-end cost from the source to the destination." The 
> key is that the information is end-to-end.
>
> Cost Map and the (Link) Cost Map, where the two maps need to be 
> defined on the same set of network nodes (Network Map).
-->  I think your semantics comment below applies here.
I was imagining the leaf nodes in the "Cost Graph" being ALTO PIDs. 
Non-leaf nodes and links are abstractions for modeling network 
constraints and costs. Hence I figured that at a minimum I would need an 
ALTO Network map to map endpoints to PIDs and the Cost Graph.  In 
addition, I could use endpoint properties and costs to model the final 
"hop" from PID (node) to endpoint.

How would you see a path vector being used by an application?
> structures to represent a graph (e.g., adjacency matrix, collections 
> of adjacency lists where each list is defined for one source node, or 
> a set of links, as you defined in the email). The current (E2E) Cost 
> Map is using mostly an adjacency matrix representation and can 
> represent a graph as well, with different semantics though, and with 
> different representation efficiency.
Agree. I'll start my write up and pass it around (or post it somewhere) 
for folks to comment on. I'd like to find some common ground before 
publishing another draft to avoid multiplicity of drafts.
>
> One additional (Link) info I see for (Link) Cost Graph as you defined 
> at the end of your email is SRLG, for example, each Link includes a 
> list of tags of shared risk link group.
I'm fine with the SRLG concept since it can be done independent of layer 
and suitably abstracted.  I worked with the AT&T folks way back to get 
it into GMPLS.  Would you like this for your application?
>> In particular we (high bandwidth folks) are interested in "Cost 
>> Graph" type of information and given a bit more formally at the end 
>> of this e-mail. Starting from the ALTO protocol document and looking 
>> at extensions we have:
>>
>>     have wide applicability in the controlled and partially
>>     controlled cases. They call this "*/path bandwidth/*". --> We'd
>>     like standard latency and bandwidth cost types if possible.
>>  3. However "path bandwidth" would typically be used with some type
>>     of "routing cost", and perhaps a "latency cost". This leads to a
>>     "routing cost". We have illustrated in our high bandwidth use
>>     case draft how "bottleneck" links can lead to erroneous
>>     assumptions on network capacity and we introduced a "*/cost
>>     graph/*" representation to more accurately model the network. -->
>>     We really need graph representation for high bandwidth situation.
>>     We gave examples in our high bandwidth draft and BoF presentation.
>>

---

From: "Y. Richard Yang" <[email-masked]>
Date: Tue, 17 Apr 2012 11:59:12 -0400

Greg,

Good answers. Please see below.

On 4/17/12 10:33 AM, Greg Bernstein wrote:
>> I agree that Cost Graph, in addition to Cost Map, is a good concept 
>> to add to ALTO. Conceptually:
>>
> constraints and costs. Hence I figured that at a minimum I would need 
> an ALTO Network map to map endpoints to PIDs and the Cost Graph.  In 
This graph representation by introducing internal nodes to represent 
constraints and costs is quite interesting. I feel that for generality, 
the internal nodes may not be limited to virtual (abstract) nodes, but 
can be real PID nodes, representing, for example, loose source routing, 
locations/PE.

> How would you see a path vector being used by an application?
A use case of path vector, with each element being a node from the Cost 
Graph, is to convey the path(s) when there are multiple paths from a 
source PID to a destination PID on the Cost Graph, and the provider has 
chosen one or a few candidates. Application could use the path vector 
for reliability/availability selection (some examples in your 
presentation): suppose PID_client is a client site, and there are two 
sites PID_s1, PID_s2 hosting replicated servers. An application may 
check the path vector of PID_s1 -> PID_client  and that of PID_s2 -> 
PID_client when selecting paths: selecting disjoint paths for 
reliability, selecting maximum flow paths to maximize the downloading 
rate of the client, ....

> Agree. I'll start my write up and pass it around (or post it 
> somewhere) for folks to comment on. I'd like to find some common 
> ground before publishing another draft to avoid multiplicity of drafts.
>>
> I'm fine with the SRLG concept since it can be done independent of 
> layer and suitably abstracted.  I worked with the AT&T folks way back 
> to get it into GMPLS.  Would you like this for your application?
Yes. For some traffic engineering use cases, this is useful.  I feel 
that we may need to make the type general to be more extensible.

Thanks.

Richard
>>>     "*/multi-cos//t/*" scenario. --> We'd like multiple costs at
>>>     once (e.g., bandwidth, routing, latency)
>>>     graph/*" representation to more accurately model the network.
>>>     --> We really need graph representation for high bandwidth
>>>     situation. We gave examples in our high bandwidth draft and BoF
>>>     presentation.
>>>
>>> A graph based model seems generally useful.  For example, it seems 
>>> to me that this could be applicable to Data Center and possibly CDN 
>>> bandwidth constraints of such different designs could be well 
>>> modeled via a cost graph, i.e., use a cost graph for VM placement 
>>> and such... Similar comments apply to the "Use Case: Hybrid Cloud 
>>> Bandwidth On Demand" on slide 9.  Data center and CDN folks any 
>>> opinions on your needs/desires for potential extensions mention in 
>>> items 2-4 above?
>>>
>>> Cheers
>>>
>>> Greg B.
>>>

---

From: Greg Bernstein <[email-masked]>
Date: Wed, 18 Apr 2012 08:14:57 -0700

Hi Richard, I think we are in agreement. Just a few comments and 
questions below.
Cheers
Greg
On 4/17/2012 8:59 AM, Y. Richard Yang wrote:
>> addition, I could use endpoint properties and costs to model the 
>> final "hop" from PID (node) to endpoint.
>>
> constraints and costs is quite interesting. I feel that for 
> generality, the internal nodes may not be limited to virtual 
> (abstract) nodes, but can be real PID nodes, representing, for 
> example, loose source routing, locations/PE.
--> Agree. My statement above on"non-leaf" nodes isn't quite what I 
intended. Better "a node without any attached endpoints" is used for 
modeling purposes.
> A use case of path vector, with each element being a node from the 
> Cost Graph, is to convey the path(s) when there are multiple paths 
> from a source PID to a destination PID on the Cost Graph, and the 
> provider has chosen one or a few candidates. Application could use the 
> path vector for reliability/availability selection (some examples in 
> your presentation): suppose PID_client is a client site, and there are 
> two sites PID_s1, PID_s2 hosting replicated servers. An application 
> may check the path vector of PID_s1 -> PID_client  and that of PID_s2 
> -> PID_client when selecting paths: selecting disjoint paths for 
--> Makes sense. We would somewhere need a mechanism to allow the 
application to specify which path it intends to use. Right?
So this would be more commonality between the "Data Center" and "High 
bandwidth" uses cases?
> -- snip --

---

From: Greg Bernstein <[email-masked]>
Date: Wed, 18 Apr 2012 08:54:18 -0700

Hi Ben, good points. I think we have a fair amount in common. See 
comments and questions below.
Cheers
Greg
On 4/16/2012 1:44 PM, Ben Niven-Jenkins wrote:
> Greg,
>
> I wonder if splitting the topology from the costs (like it is in ALTO today) would be beneficial - i.e having a Network Graph&  associated Cost Graph(s). Maybe because some clients might be interested in the network topology but be happy with E2E costs they don't need to compute?
--> Sounds reasonable. I haven't evaluated all the options. First I'm 
trying to see how wide the applicability is for some type of graph 
representation. I think at the IP layer an abstract graph (tree 
structure) could show bottlenecks and help with multiple source and 
multiple destination ALTO, i.e., the "server selection problem".  No 
reservations (MPLS-TE, GMPLS, or OpenFlow) required.  Below IP 
particularly at the "optical" layer one cannot even probe for 
bandwidth... So an abstract graph can be very handy.
> In the CDN use cases I have I need finer granularity of network topology than a peer to peer client[1] but I still only require an abstract view of the topology - i.e. I don't need to know about in…
--> In the "high bandwidth" case. We also want to provide an abstract 
view. Though some carriers due display their fiber and other layer maps 
online, e.g., 
http://www.centurylink-business.com/demos/network-maps.html 
orhttp://maps.level3.com/default/#.T47ePdUcsTl, these are in abstract 
form. They are not showing individual routers, Ethernet switches, SONET 
or OTN switches, ROADMS, or OXCs. Network details are sensitive, in 
addition there is a question of how much does the application layer want 
to try and optimize the network.  Hence, we've been thinking of 
abstracting away all the messy multi-layer networking stuff into a 
single abstract network representation that the application layer can 
then use.
> So a good part of the value of an ALTO server/solution is that it performs that abstraction for me. For the large bandwidth use cases I get the impression that knowing detailed topology is importan…
---> Abstraction is crucial to the high bandwidth case too! We must hide 
the complexity of multi-layer networks to help applications to make 
effective use of underlying network resources.

> [1] I have to model a PID per "clump" of end users and a PID per network location containing a CDN device rather than peer to peer that probably models something more akin to "my local peers", "pee…
--> The PID concept is crucial for abstraction in the "high bandwidth 
case" too. We'd probably clump together users attached to OXC or ROADMs, 
or other types of switching gear abstract bandwidth capabilities, use 
endpoint properties/costs to represent last link, etc...

---

From: DIEGO LOPEZ GARCIA <[email-masked]>
Date: Mon, 23 Apr 2012 00:24:54 +0200

> So a good part of the value of an ALTO server/solution is that it performs that abstraction for me. For the large bandwidth use cases I get the impression that knowing detailed topology is importan…
Not necessarily. In the high bandwidth use case you'll probably be interested
in a more detailed view of certain aspects, but there is no need of being
aware of all the topology details.

In the scenarios under consideration a certain link may well model several
aggregated links, for which the server provides the necessary abstraction. In a
project I am currently involved we speak about "offers", which provide certain
values for cost functions, and each of these offers does not have to correspond
with a single link.

Be goode,

--
"Esta vez no fallaremos, Doctor Infierno"

Dr Diego R. Lopez
Telefonica I+D
http://people.tid.es/diego.lopez/

e-mail: [email-masked]
Tel:    +34 913 129 041
Mobile: +34 682 051 091
-----------------------------------------

Este mensaje se dirige exclusivamente a su destinatario. Puede consultar nuestra política de envío y recepción de correo electrónico en el enlace situado más abajo.
This message is intended exclusively for its addressee. We only send and receive email on the basis of the terms set out at
http://www.tid.es/ES/PAGINAS/disclaimer.aspx