It is great to open email and see these discussions! First, answer to Lyle's P.S. question: We are looking at an interop in the July IETF meeting. Does this work for you? We sure hope that your team can participate.
I agree that denoting some metrics to be a formal metric is a great idea. An immediate benefit coming to mind is that it allows compression, for example, only half of the cost matrix need to transmitted. I particularly liked the idea of defining the (network) graph metrics. Your suggestion appear to me to have two directions: (1) still use the cost map framework and defining graph metrics between pairs of PIDs (i.e., metrics between a pair of nodes in a graph); (2) provide overall network (graph) properties; that is, provide summary properties of the overall network topology (periphery comes to mind). I can see a unifying framework such as there is a hierarchy of network graphs, and at each level, one can define properties on a network node or a pair of nodes. Assume the highest level is a single node representing the overall topology, and then such a compound node can have properties such as center/periphery). Am I too off in understanding your ideas? Thanks! Richard On 5/29/15, Bertz, Lyle T [CTO] <[email protected]> wrote: > Wendy, > > > > I worked on asymmetric distance theory in graphs - specifically max distance > and sum distance so I can definitely say the asymmetry is not an issue and > you should assume that asymmetric metrics exist in a digraph. In fact, > distance is defined at the minimum value of the directed distance from u to > v or v to u. > > > > wrt to your statement d(x,x)=0 is correct because of granularity (that x is > actually a new set where and x1 and x2 are actually involved). Such > summarization would be better described as common subgraph such as a > periphery, center, status or median. For example, if x1 and x2 are in the > center or periphery we would expect status measurements to be similar. In > general we would not measure distance between x1 and x2 but but merely talk > about periphery elements as 'x'. Precision is a whole other matter as > well. > > > > I think identifying metrics that follow formal metric definition is > definitely a great idea. For clients and servers we can identify other > graph metrics. The two that come to mind are center and periphery of a > graph. Where asymmetry is present we can apply max and sum distance to > yield the center and periphery versions for max and sum distance. > > > > These metrics and definitions are used quite often in computing edge of > networks, how to merge two networks together, Steiner cut selections, etc. > Periphery is the most interesting as it tells a lot about the status of node > traffic and hints for placement, e.g. nfv instance selection in MANO when > implementing a VNF FG - I could see that being useful for both client and > servers. > > > > Lyle > > > > ________________________________ > From: Wendy Roome <[email protected]> > Sent: Friday, May 29, 2015 4:06 PM > To: Bertz, Lyle T [CTO]; Y. Richard Yang > Cc: [email protected]; Hans Seidel; [email protected] > Subject: Re: [alto] Interop test > > Lyle, > > I haven't used metric spaces since the days of keypunches, so it took a > while to blow the cobwebs out of that memory bank. :-) > > I don't think ALTO cost metrics could ever meet the requirements for a > metric space. The problems: > > * A true metric d(x,y) must be defined for all x & y. ALTO does not require > that the cost be defined for all pairs. > > * For a metric, d(x,y) = d(y,x) for all x,y. ALTO costs represent > communication links, and are potentially asymmetric. Eg, the download > bandwidth can be higher than the upload bandwidth. > > * For a metric, d(x,x) = 0 for all x. For ALTO, the cost within a PID > frequently is greater than 0. > > * For a metric, d(x,y) = 0 means x = y. We *might* be able to define ALTO > costs so that is possible, but I have my doubts. > > * For a metric, d(x,z) <= d(x,y) + d(y,z) for all y. For ALTO, that is > tempting requirement, and I cannot think of an obvious counter example. But > I doubt that would help without the other requirements. > > So we could not require *every* ALTO cost metric to qualify as a > mathematical metric. But we could define a particular cost as satisfying > those rules, and (say) identify it in the IRD. Can you explain how that > would benefit clients or servers? One obvious advantage is that the cost > matrix could be smaller, because its symmetric and the center diagonal is > 0. > > - Wendy Roome > > From: "Bertz, Lyle T [CTO]" > <[email protected]<mailto:[email protected]>> > Date: Fri, May 29, 2015 at 16:03 > To: Wendy Roome > <[email protected]<mailto:[email protected]>>, "Y. Richard > Yang" <[email protected]<mailto:[email protected]>> > Cc: "[email protected]<mailto:[email protected]>" > <[email protected]<mailto:[email protected]>>, Hans Seidel > <[email protected]<mailto:[email protected]>>, > "[email protected]<mailto:[email protected]>" > <[email protected]<mailto:[email protected]>> > Subject: RE: [alto] Interop test > > I had not put together the comparison applying to the same requests. That > makes matters convenient as the included data only applies to the response. > > Without formal metric compliance though there are a lot of algorithms that > could not be reliably applied. I think we should consider this as we move > forward in developing ALTO. It may be worthwhile to clarify matters in a > future update. > > From: Wendy Roome [mailto:[email protected]] > Sent: Friday, May 29, 2015 2:45 PM > To: Bertz, Lyle T [CTO]; Y. Richard Yang > Cc: [email protected]<mailto:[email protected]>; Hans Seidel; > [email protected]<mailto:[email protected]> > Subject: Re: [alto] Interop test > > Interesting point! RFC 7285 does NOT require cost metrics -- numerical or > ordinal -- to follow the requirements for a formal metric. Other than the > values must be non-negative. > > In particular, there is no requirement that d(x,x) = 0, or that d(x,y) = 0 > iff x = y. > > Costs are directed, so symmetry isn't even appropriate. > > I guess I would expect a numeric metric to follow the triangle inequality, > more or less, but there is no formal requirement for it do so. > > Incidentally, for ordinal mode costs, the values are only comparable to > other costs in the same request. In other words, if an ordinal cost in a > filtered cost map is 0, that just means it is the lowest cost for the set of > sources & destinations you requested. It is NOT the lowest cost for the full > map. > > - Wendy Roome > > > From: "Bertz, Lyle T [CTO]" > <[email protected]<mailto:[email protected]>> > Date: Fri, May 29, 2015 at 15:21 > To: Wendy Roome > <[email protected]<mailto:[email protected]>>, "Y. Richard > Yang" <[email protected]<mailto:[email protected]>> > Cc: "[email protected]<mailto:[email protected]>" > <[email protected]<mailto:[email protected]>>, Hans Seidel > <[email protected]<mailto:[email protected]>>, > "[email protected]<mailto:[email protected]>" > <[email protected]<mailto:[email protected]>> > Subject: RE: [alto] Interop test > > I have a much larger question about ordinal rank in 7285, is it the > expectation that ordinal ranks are true metrics in practice. In other words > are they or even the original metrics true mathematical metrics, i.e. > non-negative, have symmetry, coincidence axiom and the triangle inequality. > Further are they formally ultrametrics or intrinsic? > > I only ask because depending on the answer we can add services for max > distance, sum distance and the like that apply graph theory to the resulting > maps. Who know, I may even be able to apply my only graph theories to them > but I will keep such aspirations low at the moment. > > > > ________________________________ > > This e-mail may contain Sprint proprietary information intended for the sole > use of the recipient(s). Any use by others is prohibited. If you are not the > intended recipient, please contact the sender and delete all copies of the > message. > > ________________________________ > > This e-mail may contain Sprint proprietary information intended for the sole > use of the recipient(s). Any use by others is prohibited. If you are not the > intended recipient, please contact the sender and delete all copies of the > message. > -- Richard _______________________________________________ alto mailing list [email protected] https://www.ietf.org/mailman/listinfo/alto
