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

["Y. Richard Yang" <[e-mail]>]

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:
>>
>> - (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.
>
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, ....

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