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.
_______________________________________________ alto mailing list [email protected] https://www.ietf.org/mailman/listinfo/alto
