Re: [altoext] General Applicability of a Cost Graph?
"Y. Richard Yang" <yry@cs.yale.edu> Tue, 17 April 2012 15:59 UTC
Return-Path: <yry@cs.yale.edu>
X-Original-To: altoext@ietfa.amsl.com
Delivered-To: altoext@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 44DD621F8566 for <altoext@ietfa.amsl.com>; Tue, 17 Apr 2012 08:59:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.302
X-Spam-Level: **
X-Spam-Status: No, score=2.302 tagged_above=-999 required=5 tests=[BAYES_50=0.001, HTML_MESSAGE=0.001, MANGLED_COST=2.3]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7Rk5xiugSuoh for <altoext@ietfa.amsl.com>; Tue, 17 Apr 2012 08:59:21 -0700 (PDT)
Received: from vm-emlprdomr-06.its.yale.edu (vm-emlprdomr-06.its.yale.edu [130.132.50.147]) by ietfa.amsl.com (Postfix) with ESMTP id CD87F21F8575 for <altoext@ietf.org>; Tue, 17 Apr 2012 08:59:20 -0700 (PDT)
Received: from dhcp-128-36-59-166.central.yale.edu (dhcp-128-36-59-166.central.yale.edu [128.36.59.166]) (authenticated bits=0) by vm-emlprdomr-06.its.yale.edu (8.14.4/8.14.4) with ESMTP id q3HFxFxT006184 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Tue, 17 Apr 2012 11:59:15 -0400
Message-ID: <4F8D9350.9030101@cs.yale.edu>
Date: Tue, 17 Apr 2012 11:59:12 -0400
From: "Y. Richard Yang" <yry@cs.yale.edu>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.7; rv:11.0) Gecko/20120327 Thunderbird/11.0.1
MIME-Version: 1.0
To: Greg Bernstein <gregb@grotto-networking.com>
References: <4F8C6142.5000202@grotto-networking.com> <4F8C7705.5070609@cs.yale.edu> <4F8D7F21.4020005@grotto-networking.com>
In-Reply-To: <4F8D7F21.4020005@grotto-networking.com>
Content-Type: multipart/alternative; boundary="------------000909010407030905080209"
X-Scanned-By: MIMEDefang 2.71 on 130.132.50.147
Cc: altoext@ietf.org
Subject: Re: [altoext] General Applicability of a Cost Graph?
X-BeenThere: altoext@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Non-WG list for discussions related to ALTO Protocol Extensions <altoext.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/altoext>, <mailto:altoext-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/altoext>
List-Post: <mailto:altoext@ietf.org>
List-Help: <mailto:altoext-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/altoext>, <mailto:altoext-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 17 Apr 2012 15:59:25 -0000
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 (510) 573-2237 >>> >>> >>> >>> _______________________________________________ >>> altoext mailing list >>> altoext@ietf.org >>> https://www.ietf.org/mailman/listinfo/altoext >> >> >> >> _______________________________________________ >> altoext mailing list >> altoext@ietf.org >> https://www.ietf.org/mailman/listinfo/altoext >
- [altoext] General Applicability of a Cost Graph? Greg Bernstein
- Re: [altoext] General Applicability of a Cost Gra… Y. Richard Yang
- Re: [altoext] General Applicability of a Cost Gra… Ben Niven-Jenkins
- Re: [altoext] General Applicability of a Cost Gra… Greg Bernstein
- Re: [altoext] General Applicability of a Cost Gra… Y. Richard Yang
- Re: [altoext] General Applicability of a Cost Gra… Greg Bernstein
- Re: [altoext] General Applicability of a Cost Gra… Greg Bernstein
- Re: [altoext] General Applicability of a Cost Gra… DIEGO LOPEZ GARCIA