Subject: Re: [alto] Interop test

From: Wendy Roome <[email-masked]>
Date: Fri, 29 May 2015 10:24:30 -0400

Folks,

Rather than simply update the last test, I suggest a new approach,
outlined below.

**** General ****

The interop test defines two network maps: the default network map and an
alternate network map. We specify the PIDs and CIDRs for each map. For
each network map, the interop test defines the numerical-mode values for
the routingcost and hopcount cost-metrics. The interop test does not
define ordinal values for those metrics. Instead, each ALTO server may
assign ordinal values however it wants, as long as the ordinal values
preserve the numerical values.

The interop test also defines a custom endpoint property, say
"priv:ietf-type", and specifies the values.

**** Approach & Philosophy ****

Rather than specifying every detail, as in the previous interop test, this
iteration only specifies what is absolutely necessary. That is, the PIDs
in the network maps, the costs between PIDs, and the enpdoint property
values. Everything else -- resource ids, uris, cost-type names, etc. -- is
up to the server. Thus each server is completely characterized by two
parameters:

* The URI of its IRD.
* The resource id of its alternate map (if provided).

When a client is paired with a server, the client is given those two
parameters. The client is expected to determine everything else it needs
(e.g., the URIs of the default network map and the numerical routingcost
cost map) from the IRD.

Client-writers are encouraged to script their client so that it validates
the server's responses. That is, rather than just printing a cost map, the
client is encouraged to verify that it has the expected values. The
interop test will specify the maps in enough detail that clients will know
exactly what the server should return for any request.

Server-writers are encouraged to configure their server (especially the
IRD) so as to stress-test clients. That is, do things which are legal, but
unusual. For example, instead of having all resources in one IRD, the
server might have several linked (cascaded) IRDs. Or instead of offering
one filtered cost map, which handles all four combinations of cost metrics
& modes, plus constraints, the server might offer four separate filtered
cost map resources: one which handles numerical mode routingcost &
hopcount, but does not accept constraints, a second that handles the same
cost types, but which does accept constraints, and two more for ordinal
mode costs. This would verify that a client is able to select the correct
resource for a given request.

**** Server Requirements ****

Each server MUST offer the following resources:
* A full network map for the default network.
* Four full cost maps for the default network map: the routingcost &
hopcount metrics, in both numerical & ordinal modes.
* An endpoint property service for the pid property for the default
network map.

Each server MAY offer the following optional services:
* A filtered network map for the default network.
* A filtered cost map for the default network, optionally allowing cost
constraints.
* An endpoint cost service, covering the 4 cost metric/mode combinations,
optionally allowing cost constraints. The values must be derived from the
default network & cost maps.
* The filtered cost map & endpoint cost services may support constraints.
* An alternate network map plus the 4 associated full cost maps.
* An endpoint property service for the alternate network's pid property.
This may be the same EPS resource as for the default network, or a
different resource.
* A filtered network map for the alternate network.
* A filtered cost map for the alternate network map.

If offered, the filtered cost map & endpoint cost resources MUST cover all
four metric/mode combinations.

If offered, the costs for the endpoint cost service MUST must be derived
from the default network map.

**** Client Requirements ****

When a client is paired with a server, the client is given the URI of the
server's IRD, and the resource id of its alternate map (if the server &
client support alternate maps). The client must be able to extract all
other information from the IRD -- full map resources, their URIs, etc.

Each client MUST:

* Fetch the IRD.
* Locate & fetch the default network map and its four associated full cost
maps.
* Locate the EPS for the default network map's pid resource, and determine
the pid for a set of endpoints specified by the interop test.

Note that clients are not required to fetch the alternate network map (if
present). But every client must be able to parse an IRD with an alternate
network map, and distinguish the default network map, and its associate
resources, from the alternate map.

Optional client requirements:
* Use the filtered network map for the default network map to fetch PIDs
specified by the interop test.
* Use the filtered cost map for the default network map to fetch the costs
for several combinations of source pids, destination pids, metrics/modes,
and optional constraints, as specified by the interop test.
* Use the endpoint cost service to fetch the costs for several
combinations of source addresses, destination addresses, metrics/modes,
and optional constraints, as specified by the interop test.
* Locate & fetch the alternate map and its four full cost maps.
* Use the filtered network map for the alternate network map to fetch PIDs
specified by the interop test.
* Use the filtered cost map for the alternate network map to fetch the
costs for several combinations of source pids, destination pids,
metrics/modes, and optional constraints, as specified by the interop test.
* Fetch the custom endpoint property for a set of endpoints defined by the
interop test.

**** Error Testing ****

We will develop "torture test" scripts of bad client requests, and feed
them to each server to make sure the server gives reasonable error
responses. Participants are encouraged to contribute bad client requests
up to the time of the test. We will not specify the error tests in
advance, but will publish them after the interop is complete.

Note that the emphasis in on verifying that servers survive client errors.
It does not seem important to verify that clients survive server errors.
If you disagree, speak now or forever hold your peace.

    - Wendy Roome

---

From: "Y. Richard Yang" <[email-masked]>
Date: Fri, 29 May 2015 11:40:22 -0400

Wendy,

Good proposal! Two comments:

1. I liked that the interop is for a setting that is close to real-life
deployment. In particular, my understanding of the proposal is that the
interop should leave as much unspecified as possible. A first reaction then
is how to validate the correctness. For example, the response of
resource-id is not known ahead of time. I assume that then the interop
participants will need a second channel (e.g., human in the loop) to verify
that a client c1 gets the correct response from a server s1. Is this the
intended setting?

2. A second comment is that it will be interesting if the interop design
will also become a starting point of ALTO compliance tests. We partition
the tests into MUST and optional so that a test case is a MUST case if and
only if (iff) it is a MUST in RFC7285. In the current proposal below, I see
some mix (e.g., some services in the interop is not a MUST in RFC7285).
Make sense?

Richard

On Fri, May 29, 2015 at 10:24 AM, Wendy Roome <[email-masked]>
wrote:

> _______________________________________________
> alto mailing list
> [email-masked]
>
> https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_alto&d=AwICAg&c=-dg2m7zWuuDZ0MUcV7Sdqw&r=4G36iiEVb2m_v-0RnP2gx9KZJjYQgfvrOCE3789JGIA&m=kXIGnWFHVmEKkrU-3jzE_hUpglOe7Bj7H4Ys164dZBE&s=eXl0C-Yj1ZVYLA6lRFfpWyP1zKA5InHCoayBzITypGQ&e=

---

From: Wendy Roome <[email-masked]>
Date: Fri, 29 May 2015 12:11:22 -0400

I was assuming the interop test would specify the network & cost maps. E.g.,
the pid names, their CIDRs, and the costs between PIDs. Given that, and
given the IRD entry for a resource (e.g., its media-type, accepts, uses and
capabilities), a validating client should know exactly what that resource
will return.

Okay, there are a few exceptions, such as the tag for a network map and the
values of an ordinal cost map. But a client can verify that the network map
vtag in a cost map matches the vtag in the network map, and it can verify
that ordinal cost values are consistent with the order of the known
numerical values.

Operationally, the ideal validating client would print the results from the
server, followed by a polite "C'est bon" or a big "I DISAGREE!!!"

- Wendy

From:  "Y. Richard Yang" <[email-masked]>
Date:  Fri, May 29, 2015 at 11:40
To:  Wendy Roome <[email-masked]>
Cc:  "[email-masked]" <[email-masked]>, "Bertz, Lyle T [CTO]"
<[email-masked]>, Hans Seidel <[email-masked]>,
"[email-masked]" <[email-masked]>
Subject:  Re: [alto] Interop test

1. I liked that the interop is for a setting that is close to real-life
deployment. In particular, my understanding of the proposal is that the
interop should leave as much unspecified as possible. A first reaction then
is how to validate the correctness. For example, the response of resource-id
is not known ahead of time. I assume that then the interop participants will
need a second channel (e.g., human in the loop) to verify that a client c1
gets the correct response from a server s1. Is this the intended setting?

---

From: "Y. Richard Yang" <[email-masked]>
Date: Fri, 29 May 2015 12:24:48 -0400

Wendy,

On Fri, May 29, 2015 at 12:11 PM, Wendy Roome <[email-masked]>
wrote:

> I was assuming the interop test would specify the network & cost maps.
> E.g., the pid names, their CIDRs, and the costs between PIDs. Given that,
> and given the IRD entry for a resource (e.g., its media-type, accepts, uses
> and capabilities), a validating client should know exactly what that
> resource will return.
>
> Okay, there are a few exceptions, such as the tag for a network map and
> the values of an ordinal cost map. But a client can verify that the network
> map vtag in a cost map matches the vtag in the network map,
>

This makes sense. We can specify the validation condition for the interop:

- For network map, the only unspecified value then is the "vtag" field, and
the interop specifies the assert, which is based on consistency between
data and IRD.

- For cost map, the only unspecified is the exact "dependent-vtags", and
your validation makes sense.

> and it can verify that ordinal cost values are consistent with the order
> of the known numerical values.
>

This is a reasonable validation. An issue is that RFC7285 specifies only
that "An ALTO server MUST support at least one of the following modes:
 numerical and ordinal." I believe that RFC7285 chose to not specify the
consistency between the two modes. Hence, this is beyond compliance, right?
Hence, I feel that separating RFC7285-conforming and beyond can be helpful.

Richard

>
> Operationally, the ideal validating client would print the results from
> the server, followed by a polite "C'est bon" or a big "I DISAGREE!!!"
>
> - Wendy
>
> Cc: "[email-masked]" <[email-masked]>, "Bertz, Lyle T [CTO]" <
> [email-masked]>, Hans Seidel <[email-masked]>, "
> [email-masked]" <[email-masked]>

---

From: Wendy Roome <[email-masked]>
Date: Fri, 29 May 2015 12:26:26 -0400

I already have a start for compliance tests -- see
http://alto.alcatel-lucent.com:8000/validate-server and
http://alto.alcatel-lucent.com:8000/validate-msg.

But I have not seen IETF compliance tests for other protocols. Does the IETF
officially sponsor/endorse them? Or must they be done outside of the IETF?

- Wendy Roome

2. A second comment is that it will be interesting if the interop design
will also become a starting point of ALTO compliance tests. We partition the
tests into MUST and optional so that a test case is a MUST case if and only
if (iff) it is a MUST in RFC7285. In the current proposal below, I see some
mix (e.g., some services in the interop is not a MUST in RFC7285). Make
sense?

---

From: "Y. Richard Yang" <[email-masked]>
Date: Fri, 29 May 2015 12:37:20 -0400

On Fri, May 29, 2015 at 12:26 PM, Wendy Roome <[email-masked]>
wrote:

> http://alto.alcatel-lucent.com:8000/validate-server
> <https://urldefense.proofpoint.com/v2/url?u=http-3A__alto.alcatel-2Dlucent.com-3A8000_validate-2Dserver&d=AwMFAg&c=-dg2m7zWuuDZ0MUcV7Sdqw&r=4G36iiEVb2m_v-0RnP2gx9KZJjYQgfvrOCE3789JGIA&m=2gSz8abdwCKA46ZzfuuqmROwpNENiQclUBd8YSzYsJY&s=5xb-YmFczOwf1JBuCV_hT51YMEzXdzHFdg2owONrrBY&e=> and
> http://alto.alcatel-lucent.com:8000/validate-msg
> <https://urldefense.proofpoint.com/v2/url?u=http-3A__alto.alcatel-2Dlucent.com-3A8000_validate-2Dmsg&d=AwMFAg&c=-dg2m7zWuuDZ0MUcV7Sdqw&r=4G36iiEVb2m_v-0RnP2gx9KZJjYQgfvrOCE3789JGIA&m=2gSz8abdwCKA46ZzfuuqmROwpNENiQclUBd8YSzYsJY&s=ZdWHyChFBK081zYck6jCEnHphdbxSmYDcCNcLdYPfJE&e=>
> .
>
>
Super cool!

> But I have not seen IETF compliance tests for other protocols. Does the
> IETF officially sponsor/endorse them? Or must they be done outside of the
> IETF?
>
>
I guess this is a question that the chairs/AD can provide the guidance :-)

Richard

---

From: Wendy Roome <[email-masked]>
Date: Fri, 29 May 2015 13:05:46 -0400

I thought RFC 7285 required order-consistency between numerical & ordinal
modes for the same metric. But I cannot find that requirement. Too bad! I
would have added that if I realized it wasn't there.

But if we take off our lawyer hats, and look at RFC 7285 as an agreement
between friends, rather than a formal contract between adversaries, then I
think it is reasonable to say that if the ordinal mode costs do not preserve
the order of the numerical costs, then that server is wrong.

Similarly, a router is allowed to drop packets, and I do not think there is
any formal requirement that it cannot drop *every* packet. So theoretically
you could glue eight jacks to a block of hardwood and market it as a router.
Maybe you could avoid getting charged for fraud. Just don't expect anyone to
buy more than one! :-)

And looking at it from a real-world perspective, the whole concept is
irrelevant. The only reason for defining ordinal mode is to allow a server
to hide the numerical costs. For example, if the numerical costs to three
PIDs are 10, 11 and 100, a client can deduce that the middle pid is close.
If the costs are 10, 99 and 100, a client can deduce that the middle pid is
distant. If the ordinal costs are 1,2,3, a client cannot deduce anything
other than 1 is better than 2 is better than 3.

So if a server offers numerical costs, there is no advantage for it to also
offer ordinal mode costs.

And if numerical costs are available, there is no advantage to a client to
use ordinal costs. Maybe if the client could assume the ordinal costs are
1,2,3,Š -- but the client cannot.

So in practice, no server will offer both numerical & ordinal mode for the
same metric.

That means a formal compliance test should only require one mode or the
other, but not both. However, keep the interop simple, unless someone
objects, I suggest we require both modes.

- Wendy

Date:  Fri, May 29, 2015 at 12:24

> and it can verify that ordinal cost values are consistent with the order of
> the known numerical values.

---

From: "Y. Richard Yang" <[email-masked]>
Date: Fri, 29 May 2015 14:24:59 -0400

> would have added that if I realized it wasn't there.

I remembered that the removal of the consistency requirement was a
conscious decision, not an omission, to reduce the load of consistency
checking. I buy your point below of a server supporting only one, in the
sense of providing the maximum allowed by the privacy concern.

Regarding supporting both in the interop, I will be happy to wait a bit to
hear others' opinions.

Richard

> think it is reasonable to say that if the ordinal mode costs do not
> preserve the order of the numerical costs, then that server is wrong.
>
> Similarly, a router is allowed to drop packets, and I do not think there
> is any formal requirement that it cannot drop *every* packet. So
> theoretically you could glue eight jacks to a block of hardwood and market
> it as a router. Maybe you could avoid getting charged for fraud. Just don't
> expect anyone to buy more than one! :-)
>
> So if a server offers numerical costs, there is no advantage for it to
> also offer ordinal mode costs.
>
> 1,2,3,… -- but the client cannot.
>
> From: "Y. Richard Yang" <[email-masked]
> <javascript:_e(%7B%7D,'cvml',[email-masked]');>>
> To: Wendy Roome <[email-masked]
> <javascript:_e(%7B%7D,'cvml',[email-masked]');>>
> Cc: "[email-masked] <javascript:_e(%7B%7D,'cvml',[email-masked]');>" <
> [email-masked] <javascript:_e(%7B%7D,'cvml',[email-masked]');>>, "Bertz,
> Lyle T [CTO]" <[email-masked]
> <javascript:_e(%7B%7D,'cvml',[email-masked]');>>, Hans Seidel <
> [email-masked] <javascript:_e(%7B%7D,'cvml',[email-masked]');>>,
> "[email-masked]
> <javascript:_e(%7B%7D,'cvml',[email-masked]');>" <
> [email-masked]
> <javascript:_e(%7B%7D,'cvml',[email-masked]');>>

-- 
Richard

---

From: "Bertz, Lyle T [CTO]" <[email-masked]>
Date: Fri, 29 May 2015 19:21:37 +0000

Wendy,

On Friday, May 29, 2015, Wendy Roome <[email-masked]<mailto:[email-masked]>> wrote:
"Similarly, a router is allowed to drop packets, and I do not think there is any formal requirement that it cannot drop *every* packet. So theoretically you could glue eight jacks to a block of hardwood and market it as a router. Maybe you could avoid getting charged for fraud. Just don't expect anyone to buy more than one! :-)"

I am pretty sure someone has actually tried to sell me one of these and can find it in the lab (but was not the purchaser).  To date its loss rate is close to 100%.  It is treated more like a very secure firewall than a router and is placed beside a tin pale that is a bit bucket someone purchased long ago. :D

On a serious note, I agree with you that only one mode would be supported on the server .   Please note that an ordinal ranking of a metric may exist if there are too many entries that have the same value in the original metric.  We do this quite often as an operator but we *always* give this metric a different name in order to emphasize the ranking aspect.

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.

Lyle

PS - Are we looking to perform an interop in July or the next meeting?

From: Wendy Roome [mailto:[email-masked]]
Sent: Friday, May 29, 2015 12:06 PM
To: Y. Richard Yang
Cc: [email-masked]; Bertz, Lyle T [CTO]; Hans Seidel; [email-masked]
Subject: Re: [alto] Interop test

I thought RFC 7285 required order-consistency between numerical & ordinal modes for the same metric. But I cannot find that requirement. Too bad! I would have added that if I realized it wasn't there.

But if we take off our lawyer hats, and look at RFC 7285 as an agreement between friends, rather than a formal contract between adversaries, then I think it is reasonable to say that if the ordinal mode costs do not preserve the order of the numerical costs, then that server is wrong.

Similarly, a router is allowed to drop packets, and I do not think there is any formal requirement that it cannot drop *every* packet. So theoretically you could glue eight jacks to a block of hardwood and market it as a router. Maybe you could avoid getting charged for fraud. Just don't expect anyone to buy more than one! :-)

And looking at it from a real-world perspective, the whole concept is irrelevant. The only reason for defining ordinal mode is to allow a server to hide the numerical costs. For example, if the numerical costs to three PIDs are 10, 11 and 100, a client can deduce that the middle pid is close. If the costs are 10, 99 and 100, a client can deduce that the middle pid is distant. If the ordinal costs are 1,2,3, a client cannot deduce anything other than 1 is better than 2 is better than 3.

So if a server offers numerical costs, there is no advantage for it to also offer ordinal mode costs.

And if numerical costs are available, there is no advantage to a client to use ordinal costs. Maybe if the client could assume the ordinal costs are 1,2,3,... -- but the client cannot.

So in practice, no server will offer both numerical & ordinal mode for the same metric.

That means a formal compliance test should only require one mode or the other, but not both. However, keep the interop simple, unless someone objects, I suggest we require both modes.

                - Wendy

From: "Y. Richard Yang" <[email-masked]<mailto:[email-masked]>>
Date: Fri, May 29, 2015 at 12:24
To: Wendy Roome <[email-masked]<mailto:[email-masked]>>
Cc: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, "Bertz, Lyle T [CTO]" <[email-masked]<mailto:[email-masked]>>, Hans Seidel <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [alto] Interop test

and it can verify that ordinal cost values are consistent with the order of the known numerical values.

This is a reasonable validation. An issue is that RFC7285 specifies only that "An ALTO server MUST support at least one of the following modes:  numerical and ordinal." I believe that RFC7285 chose to not specify the consistency between the two modes. Hence, this is beyond compliance, right? Hence, I feel that separating RFC7285-conforming and beyond can be helpful.

________________________________

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.

---

From: Wendy Roome <[email-masked]>
Date: Fri, 29 May 2015 15:45:20 -0400

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-masked]>
Date:  Fri, May 29, 2015 at 15:21
To:  Wendy Roome <[email-masked]>, "Y. Richard Yang"
<[email-masked]>
Cc:  "[email-masked]" <[email-masked]>, Hans Seidel <[email-masked]>,
"[email-masked]" <[email-masked]>
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.

---

From: "Bertz, Lyle T [CTO]" <[email-masked]>
Date: Fri, 29 May 2015 20:03:30 +0000

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-masked]]
Sent: Friday, May 29, 2015 2:45 PM
To: Bertz, Lyle T [CTO]; Y. Richard Yang
Cc: [email-masked]; Hans Seidel; [email-masked]
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.

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-masked]<mailto:[email-masked]>>
Date: Fri, May 29, 2015 at 15:21
To: Wendy Roome <[email-masked]<mailto:[email-masked]>>, "Y. Richard Yang" <[email-masked]<mailto:[email-masked]>>
Cc: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, Hans Seidel <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: RE: [alto] Interop test

---

From: Wendy Roome <[email-masked]>
Date: Fri, 29 May 2015 17:06:33 -0400

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

Date:  Fri, May 29, 2015 at 16:03

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.

               - Wendy Roome

From: "Bertz, Lyle T [CTO]" <[email-masked]
<mailto:[email-masked]> >
Date: Fri, May 29, 2015 at 15:21
To: Wendy Roome <[email-masked]
<mailto:[email-masked]> >, "Y. Richard Yang" <[email-masked]
<mailto:[email-masked]> >
Cc: "[email-masked] <mailto:[email-masked]> " <[email-masked]
<mailto:[email-masked]> >, Hans Seidel <[email-masked]
<mailto:[email-masked]> >, "[email-masked]
<mailto:[email-masked]> " <[email-masked]
<mailto:[email-masked]> >
Subject: RE: [alto] Interop test

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.

---

From: "Bertz, Lyle T [CTO]" <[email-masked]>
Date: Sat, 30 May 2015 03:13:33 +0000

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-masked]>
Sent: Friday, May 29, 2015 4:06 PM
To: Bertz, Lyle T [CTO]; Y. Richard Yang
Cc: [email-masked]; Hans Seidel; [email-masked]
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

Cc: [email-masked]<mailto:[email-masked]>; Hans Seidel; [email-masked]<mailto:[email-masked]>

                - Wendy Roome

---

From: "Y. Richard Yang" <[email-masked]>
Date: Sat, 30 May 2015 06:48:03 -0400

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-masked]> 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: "Bertz, Lyle T [CTO]"
> <[email-masked]<mailto:[email-masked]>>
> To: Wendy Roome
> <[email-masked]<mailto:[email-masked]>>, "Y. Richard
> Yang" <[email-masked]<mailto:[email-masked]>>
> Cc: "[email-masked]<mailto:[email-masked]>"
> <[email-masked]<mailto:[email-masked]>>, Hans Seidel
> <[email-masked]<mailto:[email-masked]>>,
> "[email-masked]<mailto:[email-masked]>"
> <[email-masked]<mailto:[email-masked]>>
> Cc: [email-masked]<mailto:[email-masked]>; Hans Seidel;
> [email-masked]<mailto:[email-masked]>
> From: "Bertz, Lyle T [CTO]"
> <[email-masked]<mailto:[email-masked]>>
> To: Wendy Roome
> <[email-masked]<mailto:[email-masked]>>, "Y. Richard
> Yang" <[email-masked]<mailto:[email-masked]>>
> Cc: "[email-masked]<mailto:[email-masked]>"
> <[email-masked]<mailto:[email-masked]>>, Hans Seidel
> <[email-masked]<mailto:[email-masked]>>,
> "[email-masked]<mailto:[email-masked]>"
> <[email-masked]<mailto:[email-masked]>>

-- 
Richard

---

From: "Bertz, Lyle T [CTO]" <[email-masked]>
Date: Mon, 1 Jun 2015 02:39:38 +0000

Richard,

You are not too far off at all.  We need to think about this carefully.  The team I work in is looking to set up topology information in such a way that NFV MANO and VIM decisions are simple while still providing some traditional transport optimization.

I also think we may need theorems for aggregation of metrics.  I'll have to dust off old work by various folks to see if it has not already been figured out.

Since cost maps are directed there is no reason why we can't compute max and sum distance.  This is practically an exercise left to the reader.  The symmetric case would be new though.

wrt the July question we may be able to do some work with the old code and there may be other code available as well but that will be quite new and full of bugs.   I hope to confirm this before the end of June.

Lyle

________________________________________
From: [email-masked] <[email-masked]> on behalf of Y. Richard Yang <[email-masked]>
Sent: Saturday, May 30, 2015 5:48 AM
To: Bertz, Lyle T [CTO]
Cc: Wendy Roome; [email-masked]; Hans Seidel
Subject: Re: [alto] Interop test

Thanks!

Richard

--
Richard