Subject: Re: [alto] ALTO Extension: A document defining multi-metrics filtering?

From: "Y. Richard Yang" <[email-masked]>
Date: Sun, 13 Oct 2013 22:42:17 -0400

Let me add on: although a filtering service can be a very useful service,
it can also be quite involved, and hence the WG may need to think through
the issues when designing this service. For example, there are two types of
use cases:

- end-to-end: given src set {s1, s2, s3, ..., sn} and dst set {d1, d2, d3,
..., dm}, return all pairs (si, dj), where si in {s1, ..., sn} and dj in
{d1, ..., dm} such that (si, dj) satisfies the constraints;

- relay: given src s, dst d, and a relay candidate set {r1, r2, ..., rk},
return all of the ri such that s -> ri -> d satisfies the constraints.

Note that with relay, we will then need to worry about the "composition"
semantics of metrics. For example, delay might be additive, loss rate
(unless small and independent) may not be.

The relay could be even fancier (e.g., one-hop server detour such as Akamai
one-hop detour and hence may involved two relay servers), but it may or may
not be a good idea to go too complex, depending on if the WG can define a
clean API (e.g., SQL select/where grammar comes to mind quickly).

Thanks!

Richard

On Sun, Oct 13, 2013 at 7:57 PM, Y. Richard Yang <[email-masked]> wrote:

> Dear all,
>
> The base ALTO protocol (
> http://www.ietf.org/id/draft-ietf-alto-protocol-20.txt) is mostly a
> single-cost-metric centric:
>
> - The Cost Map filtering service uses only one cost-type (Sec. 11.3.2.3):
>
>      object {
>      CostType   cost-type;
>      [JSONString constraints<0..*>;]
>      [PIDFilter  pids;]
>    } ReqFilteredCostMap;
>
>    object {
>      PIDName srcs<0..*>;
>      PIDName dsts<0..*>;
>    } PIDFilter;
>
> ...
>  constraints  Defines a list of additional constraints on which
>       elements of the Cost Map are returned.  This parameter MUST NOT be
>       specified if this resource's capabilities (Section 11.3.2.4)
>       indicate that constraint support is not available.  A constraint
>       contains two entities separated by whitespace: (1) an operator,
>       'gt' for greater than, 'lt' for less than, 'ge' for greater than
>       or equal to, 'le' for less than or equal to, or 'eq' for equal to;
>       (2) a target cost value.
>
> - The Endpoint Cost service allows filtering (Sec. 11.5.1.3) as well, and
> is similar to Cost Map Filtering:
>
>    object {
>      CostType          cost-type;
>      [JSONString       constraints<0..*>;]
>      EndpointFilter    endpoints;
>    } ReqEndpointCostMap;
>
>    object {
>      [TypedEndpointAddr srcs<0..*>;]
>      [TypedEndpointAddr dsts<0..*>;]
>    } EndpointFilter;
>
>    constraints  Defined equivalently to the "constraints" input
>       parameter of a Filtered Cost Map (see Section 11.3.2).
>
> In other words, in the base protocol, the filtering condition and the
> output are based on the same Cost Metric. It is natural that the filtering
> and the output are based on different Cost metrics. For example, a Client
> asks for routingcost for only pairs whose latency is below a threshold (see
> use cases in
> http://tools.ietf.org/html/draft-randriamasy-alto-multi-cost-07).
>
> One may argue that the filter-metric-no-equal-to-output-metric function
> can be implemented on top of the filter-and-output-using-one-metric
> function:
>
> In particular, suppose the filtering is based on metrics M1 and M2, and
> the output is M3, for a set src to a set dsts. The Client can use the
> following three queries:
>
> - Q1: Use single metric <M1, filter on M1, srcs, dsts> and obtains <srcs1,
> dsts1> in return;
> - Q2: Use single metric <M2, filter on M2, srcs1, dsts1> and obtains
> <srcs2, dsts2> in return;
> - Q3: Use single metric <M3, no filter, srcs2, dsts2> to get the final
> result.
>
> Although this is not too bad, it is inconvenient. Note that preceding is
> first discussed by Sabine, Wendy, Nico in:
> http://tools.ietf.org/html/draft-randriamasy-alto-multi-cost-07
>
> I saw that this is also the issue discussed in
> - http://tools.ietf.org/html/draft-wu-alto-json-te-01
> - http://tools.ietf.org/html/draft-lee-alto-app-net-info-exchange-02
>
> Hence, I propose that the WG extends the base protocol with this
> capability, as I see that it is quite useful. One issue is that I see three
> designs, and I am wondering if the authors are preparing on discussing
> their designs at the coming IETF, and if there is a possibility for a
> single, unified document, focusing on this issue.
>
> Thanks a lot!
>
> Richard
>

---

From: Qin Wu <[email-masked]>
Date: Mon, 14 Oct 2013 03:27:31 +0000

Richard took words out of my mouth,:)
Yes, in some cases, from source to destination, there is only one hop away, or we only care about source endpoint address and destination endpoint address, we don't care about which intermediary it traverses in the path from src to destination, I think base protocol strong support such case.

However when we put more constraints on the path, e.g.,we need to compute an end to end path with these constraints. These constraints can be latency, packet loss, jitter.
However latency, packet loss, jitter are usually gathered from routing protocol, and put as per link metrics, so we need to do some aggregation when we apply these per link metrics
to the end to end path, e.g., per link latency, if we choose a path that traverses link A, link B, link C, then we can get end to end latency by choosing the sum of per link latency of link A, link B and link C.

Regards!
-Qin

From: [email-masked] [mailto:[email-masked]] On Behalf Of Y. Richard Yang
Sent: Monday, October 14, 2013 10:42 AM
To: IETF ALTO
Cc: Wendy Roome; [email-masked]; Qin Wu
Subject: Re: [alto] ALTO Extension: A document defining multi-metrics filtering?

Let me add on: although a filtering service can be a very useful service, it can also be quite involved, and hence the WG may need to think through the issues when designing this service. For example, there are two types of use cases:

- end-to-end: given src set {s1, s2, s3, ..., sn} and dst set {d1, d2, d3, ..., dm}, return all pairs (si, dj), where si in {s1, ..., sn} and dj in {d1, ..., dm} such that (si, dj) satisfies the constraints;

- relay: given src s, dst d, and a relay candidate set {r1, r2, ..., rk}, return all of the ri such that s -> ri -> d satisfies the constraints.

Note that with relay, we will then need to worry about the "composition" semantics of metrics. For example, delay might be additive, loss rate (unless small and independent) may not be.

The relay could be even fancier (e.g., one-hop server detour such as Akamai one-hop detour and hence may involved two relay servers), but it may or may not be a good idea to go too complex, depending on if the WG can define a clean API (e.g., SQL select/where grammar comes to mind quickly).

Thanks!

Richard
On Sun, Oct 13, 2013 at 7:57 PM, Y. Richard Yang <[email-masked]<mailto:[email-masked]>> wrote:
Dear all,

The base ALTO protocol (http://www.ietf.org/id/draft-ietf-alto-protocol-20.txt) is mostly a single-cost-metric centric:

     object {
     CostType   cost-type;

   object {
     PIDName srcs<0..*>;
     PIDName dsts<0..*>;
   } PIDFilter;

...

- The Endpoint Cost service allows filtering (Sec. 11.5.1.3) as well, and is similar to Cost Map Filtering:

   object {
     CostType          cost-type;

   object {

In other words, in the base protocol, the filtering condition and the output are based on the same Cost Metric. It is natural that the filtering and the output are based on different Cost metrics. For example, a Client asks for routingcost for only pairs whose latency is below a threshold (see use cases in http://tools.ietf.org/html/draft-randriamasy-alto-multi-cost-07).

One may argue that the filter-metric-no-equal-to-output-metric function can be implemented on top of the filter-and-output-using-one-metric function:

In particular, suppose the filtering is based on metrics M1 and M2, and the output is M3, for a set src to a set dsts. The Client can use the following three queries:

- Q1: Use single metric <M1, filter on M1, srcs, dsts> and obtains <srcs1, dsts1> in return;
- Q2: Use single metric <M2, filter on M2, srcs1, dsts1> and obtains <srcs2, dsts2> in return;
- Q3: Use single metric <M3, no filter, srcs2, dsts2> to get the final result.

Although this is not too bad, it is inconvenient. Note that preceding is first discussed by Sabine, Wendy, Nico in:
http://tools.ietf.org/html/draft-randriamasy-alto-multi-cost-07

Hence, I propose that the WG extends the base protocol with this capability, as I see that it is quite useful. One issue is that I see three designs, and I am wondering if the authors are preparing on discussing their designs at the coming IETF, and if there is a possibility for a single, unified document, focusing on this issue.

Thanks a lot!

Richard

---

From: "RANDRIAMASY, SABINE (SABINE)" <[email-masked]>
Date: Thu, 17 Oct 2013 17:40:26 +0000

A few questions and comments inline to make sure I understood. If we are to document proposed filtering services, should we put separate sections, one on filtering services for the basic protocol and the other one, more prospective for protocol extensions on topologies?
Thanks
Sabine

De : [email-masked] [mailto:[email-masked]] De la part de Y. Richard Yang
Envoyé : lundi 14 octobre 2013 04:42
À : IETF ALTO
Cc : RANDRIAMASY, SABINE (SABINE); ROOME, Wendy D (Wendy); [email-masked]; Qin Wu; Young Lee; Greg Bernstein; [email-masked]; dhruv.dhody
Objet : Re: ALTO Extension: A document defining multi-metrics filtering?

- end-to-end: given src set {s1, s2, s3, ..., sn} and dst set {d1, d2, d3, ..., dm}, return all pairs (si, dj), where si in {s1, ..., sn} and dj in {d1, ..., dm} such that (si, dj) satisfies the constraints;
[     ] This use case corresponds to the base protocol. The requested service is the ALTO Cost Map Filtering Service w.r.t metric values. It seems easy to extend this service by extending the set of constraints with additional constraints metrics and additional logical operators.

- relay: given src s, dst d, and a relay candidate set {r1, r2, ..., rk}, return all of the ri such that s -> ri -> d satisfies the constraints.
[     ] This use case relates to a proposed ALTO extension on topologies providing cost maps where there may be several paths between an (S,D) pair. Is the ALTO Service here the ALTO Cost Map Filtering Service w.r.t metric values adapted to a multi-path topology?  The cost map here would need to include some index on the cost value w.r.t. the relay ID and the service would only return cost values on the indexed (S,D, idx) triples satisfying the constraints. If this is correct, then such a use case would well fit into filtering services for topology based ALTO  extensions.

Note that with relay, we will then need to worry about the "composition" semantics of metrics. For example, delay might be additive, loss rate (unless small and independent) may not be.
[     ] I think the composition and optimization operators should be documented in any case (I think in the "use and application" field of the RFC6390 template). Indeed, the OPTIMUM-COMPOSITION attributes may be MIN-SUM, MAX-MIN, MIN-PROD etc...

In the base protocol an e2e cost value provided by the server is already composed and abstracted. But if we have a protocol extension that details paths per sections,  then indeed e2e path cost composition may have to be done at  the ALTO Client side.

Thanks!

Richard

     object {
     CostType   cost-type;

   object {
     PIDName srcs<0..*>;
     PIDName dsts<0..*>;
   } PIDFilter;

...

   object {
     CostType          cost-type;

   object {

Thanks a lot!

Richard

---

From: "Y. Richard Yang" <[email-masked]>
Date: Fri, 18 Oct 2013 02:14:21 -0400

Hi Sabine,

Good comments. Please see below.

On Thu, Oct 17, 2013 at 1:40 PM, RANDRIAMASY, SABINE (SABINE) <
[email-masked] <javascript:_e({}, 'cvml',
[email-masked]');>> wrote:

>  A few questions and comments inline to make sure I understood. If we are
> to document proposed filtering services, should we put separate sections,
> one on filtering services for the basic protocol and the other one, more
> prospective for protocol extensions on topologies?
>
Following the guideline of modular design, how about using different
documents whenever possible?

Here is some thinking on organization. A main design feature of the
ALTO base protocol is its single-switch abstraction. Hence, how about we
first focus on filtering on this base abstraction, and not beyond?

Specifically, in this base abstraction model, a network map and a cost map
based on the network map defines an abstract, single switch. Each PID in
the network map defines a PoP (i.e., the set of endhosts, which can be
either servers or clients in an application context, attached to this PoP),
and the cost map of each cost metric defines the pair-wise values of the
given cost metric. Let V be the set of n PIDs (nodes), and E the set of n^2
edges. Filtering is to help an application to narrow down its choices when
building an application overlay based on this single-switch model. Hence,
we need to define the following components:

- how to filter the set of nodes?
- how to filter the set of candidate overlay paths (one hop or multiple
hops in extreme e.g., origin -> edge server -> consumer)?

Richard

>  ****
>
> Thanks****
>
> Sabine****
>
> ** **
>
> ** **
>
> *De :* [email-masked] <javascript:_e({}, 'cvml',
> [email-masked]');> [mailto:[email-masked]<javascript:_e({}, 'cvml', [email-masked]');>]
> *De la part de* Y. Richard Yang
> *Envoyé :* lundi 14 octobre 2013 04:42
> *À :* IETF ALTO
> *Cc :* RANDRIAMASY, SABINE (SABINE); ROOME, Wendy D (Wendy);
> [email-masked] <javascript:_e({}, 'cvml', [email-masked]');>;
> Qin Wu; Young Lee; Greg Bernstein; [email-masked] <javascript:_e({},
> 'cvml', [email-masked]');>; dhruv.dhody
> *Objet :* Re: ALTO Extension: A document defining multi-metrics filtering?
> ****
>
> ** **
>
> use cases:****
> ** **
> {d1, ..., dm} such that (si, dj) satisfies the constraints;****
>
> *[     ] This use case corresponds to the base protocol. The requested
> service is the ALTO Cost Map Filtering Service w.r.t metric values. It
> seems easy to extend this service by extending the set of constraints with
> additional constraints metrics and additional logical operators. *****
>
> ** **
>
> return all of the ri such that s -> ri -> d satisfies the constraints. ***
> *
>
> *[     ] This use case relates to a proposed ALTO extension on topologies
> providing cost maps where there may be several paths between an (S,D) pair.
> Is the ALTO Service here the ALTO Cost Map Filtering Service w.r.t metric
> values adapted to a multi-path topology?  The cost map here would need to
> include some index on the cost value w.r.t. the relay ID and the service
> would only return cost values on the indexed (S,D, idx) triples satisfying
> the constraints. If this is correct, then such a use case would well fit
> into filtering services for topology based ALTO  extensions. *****
>
> ** **
>
> (unless small and independent) may not be.****
>
> *[     ] I think the composition and optimization operators should be
> documented in any case (I think in the “use and application” field of the
> RFC6390 template). Indeed, the OPTIMUM-COMPOSITION attributes may be
> MIN-SUM, MAX-MIN, MIN-PROD etc… *
>
> * *
>
> *In the base protocol an e2e cost value provided by the server is already
> composed and abstracted. But if we have a protocol extension that details
> paths per sections,  then indeed e2e path cost composition may have to be
> done at  the ALTO Client side. *
>
> ** **
>
> The relay could be even fancier (e.g., one-hop server detour such as
> Akamai one-hop detour and hence may involved two relay servers), but it may
> or may not be a good idea to go too complex, depending on if the WG can
> define a clean API (e.g., SQL select/where grammar comes to mind quickly).
> ****
>
> ** **
>
> Thanks!****
>
> ** **
>
> Richard****
>
> On Sun, Oct 13, 2013 at 7:57 PM, Y. Richard Yang <[email-masked]<javascript:_e({}, 'cvml', [email-masked]');>>
> wrote:****
>
> Dear all,****
>
> ** **
>
> The base ALTO protocol (
> single-cost-metric centric:****
>
> ** **
>
> - The Cost Map filtering service uses only one cost-type (Sec. 11.3.2.3):*
> ***
>
> ** **
>
>      object {****
>
>      CostType   cost-type;****
>
>      [JSONString constraints<0..*>;]****
>
>      [PIDFilter  pids;]****
>
>    } ReqFilteredCostMap;****
>
> ** **
>
>    object {****
>
>      PIDName srcs<0..*>;****
>
>      PIDName dsts<0..*>;****
>
>    } PIDFilter;****
>
> ** **
>
> ...****
>
>  constraints  Defines a list of additional constraints on which****
>
>       elements of the Cost Map are returned.  This parameter MUST NOT be**
> **
>
>       specified if this resource's capabilities (Section 11.3.2.4)****
>
>       indicate that constraint support is not available.  A constraint****
>
>       contains two entities separated by whitespace: (1) an operator,****
>
>       'gt' for greater than, 'lt' for less than, 'ge' for greater than****
>
>       or equal to, 'le' for less than or equal to, or 'eq' for equal to;**
> **
>
>       (2) a target cost value. ****
>
> ** **
>
> is similar to Cost Map Filtering:****
>
> ** **
>
>    object {****
>
>      CostType          cost-type;****
>
>      [JSONString       constraints<0..*>;]****
>
>      EndpointFilter    endpoints;****
>
>    } ReqEndpointCostMap;****
>
> ** **
>
>    object {****
>
>      [TypedEndpointAddr srcs<0..*>;]****
>
>      [TypedEndpointAddr dsts<0..*>;]****
>
>    } EndpointFilter;****
>
> ** **
>
>    constraints  Defined equivalently to the "constraints" input****
>
>       parameter of a Filtered Cost Map (see Section 11.3.2).****
>
> ** **
>
> http://tools.ietf.org/html/draft-randriamasy-alto-multi-cost-07). ****
>
> ** **
>
> function:****
> ** **
> following three queries:****
>
> ** **
>
> dsts1> in return;****
> <srcs2, dsts2> in return;****
>
> result.****
> ** **
> http://tools.ietf.org/html/draft-randriamasy-alto-multi-cost-07****
>
> ** **
>
> I saw that this is also the issue discussed in  ****
>
> - http://tools.ietf.org/html/draft-wu-alto-json-te-01****
>
> - http://tools.ietf.org/html/draft-lee-alto-app-net-info-exchange-02****
>
> ** **
>
> single, unified document, focusing on this issue.****
>
> ** **
>
> Thanks a lot!****
>
> ** **
>
> Richard****
>
> ** **
>

---

From: "RANDRIAMASY, SABINE (SABINE)" <[email-masked]>
Date: Fri, 18 Oct 2013 17:50:20 +0000

Hi Richard,

Please see inline
Sabine

De : [email-masked] [mailto:[email-masked]] De la part de Y. Richard Yang
Envoyé : vendredi 18 octobre 2013 08:14
À : RANDRIAMASY, SABINE (SABINE)
Cc : IETF ALTO; ROOME, Wendy D (Wendy); [email-masked]; Qin Wu; Young Lee; Greg Bernstein; [email-masked]; dhruv.dhody
Objet : ALTO Extension: A document defining multi-metrics filtering?

Hi Sabine,

On Thu, Oct 17, 2013 at 1:40 PM, RANDRIAMASY, SABINE (SABINE) <[email-masked]<javascript:_e(%7b%7d,%20'cvml',[email-masked]');>> wrote:
A few questions and comments inline to make sure I understood. If we are to document proposed filtering services, should we put separate sections, one on filtering services for the basic protocol and the other one, more prospective for protocol extensions on topologies?
Following the guideline of modular design, how about using different documents whenever possible?
[     ] agree

Here is some thinking on organization. A main design feature of the ALTO base protocol is its single-switch abstraction. Hence, how about we first focus on filtering on this base abstraction, and not beyond?
[     ] Ok then I will start on my side and document the set of filtering services for the base protocol, based on the Multi-Cost 07 proposal, the proposals of Young et al. and Qin et al.  ,  list what I see as possible harmonization items to have a discussion basis.

Specifically, in this base abstraction model, a network map and a cost map based on the network map defines an abstract, single switch. Each PID in the network map defines a PoP (i.e., the set of endhosts, which can be either servers or clients in an application context, attached to this PoP), and the cost map of each cost metric defines the pair-wise values of the given cost metric. Let V be the set of n PIDs (nodes), and E the set of n^2 edges. Filtering is to help an application to narrow down its choices when building an application overlay based on this single-switch model. Hence, we need to define the following components:

- how to filter the set of nodes?
- how to filter the set of candidate overlay paths (one hop or multiple hops in extreme e.g., origin -> edge server -> consumer)?
[     ] Ok

Richard

Thanks
Sabine

De : [email-masked]<javascript:_e(%7b%7d,%20'cvml',[email-masked]');> [mailto:[email-masked]<javascript:_e(%7b%7d,%20'cvml',[email-masked]');>] De la part de Y. Richard Yang
Envoyé : lundi 14 octobre 2013 04:42
À : IETF ALTO
Cc : RANDRIAMASY, SABINE (SABINE); ROOME, Wendy D (Wendy); [email-masked]<javascript:_e(%7b%7d,%20'cvml',[email-masked]');>; Qin Wu; Young Lee; Greg Bernstein; [email-masked]<javascript:_e(%7b%7d,%20'cvml',[email-masked]');>; dhruv.dhody
Objet : Re: ALTO Extension: A document defining multi-metrics filtering?

Thanks!

Richard
On Sun, Oct 13, 2013 at 7:57 PM, Y. Richard Yang <[email-masked]<javascript:_e(%7b%7d,%20'cvml',[email-masked]');>> wrote:
Dear all,

     object {
     CostType   cost-type;

   object {
     PIDName srcs<0..*>;
     PIDName dsts<0..*>;
   } PIDFilter;

...

   object {
     CostType          cost-type;

   object {

Thanks a lot!

Richard