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

[Greg Bernstein <[e-mail]>]

Good to hear from you Richard and good points. See comments below.
Greg
On 4/16/2012 12:46 PM, Y. Richard Yang wrote:
> 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).
-->  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?
>
> 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.
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?
>
> Thanks!
>
> Richard
>
> On 4/16/12 2:13 PM, 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:
>>
>>  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 [phone]
>>
>>
>>
>> _______________________________________________
>> altoext mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/altoext
>
>
>
> _______________________________________________
> altoext mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/altoext


-- 
===================================================
Dr Greg Bernstein, Grotto Networking [phone]