Re: [alto] Interop test
Wendy Roome <w.roome@...>
toggle quoted messageShow quoted text
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]" <Lyle.T.Bertz@...>
Date: Fri, May 29, 2015 at 16:03
To: Wendy Roome <w.roome@...>, "Y. Richard Yang" <yry@...>
Cc: "alto@..." <alto@...>, Hans Seidel <hseidel@...>, "alto-dev@..." <alto-dev@...>
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:w.roome@...]
Sent: Friday, May 29, 2015 2:45 PM
To: Bertz, Lyle T [CTO]; Y. Richard Yang
Cc: alto@...; Hans Seidel; alto-dev@...
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
"Bertz, Lyle T [CTO]" <Lyle.T.Bertz@...>
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.