Subject: Re: [alto] Multiple Cost Types in an ALTO Cost Map

From: "RANDRIAMASY, SABINE (SABINE)" <[email-masked]>
Date: Wed, 1 Jun 2011 22:30:31 +0200

Hi Rich, Robert and all,
Thanks a lot for bringing the discussion on this topic. Please see my comments inline.
Best regards
Sabine

-----Message d'origine-----
De : [email-masked] [mailto:[email-masked]] De la part de Richard Alimi
Envoyé : vendredi 27 mai 2011 20:26
À : Robert Varga
Cc : [email-masked]
Objet : Re: [alto] Multiple Cost Types in an ALTO Cost Map

Hi Robert,

Thanks for the feedback. A couple of short responses inline.

On Fri, May 27, 2011 at 11:04 AM, Robert Varga <[email-masked]> wrote:
> On 05/27/11 18:21, Richard Alimi wrote:
>> Hi All,
>
> Hi,
>
> please see inline comments.
>
>> Now that we have posted the -08 version of the protocol draft, it
>> would be good to get opinions on a couple of remaining issues. This
>> thread is about allowing multiple Cost Types to appear in a single
>> Cost Map.
>>
>> Background:
>>
>> Sabine has proposed draft-randriamasy-alto-multi-cost-02, in which one
>> suggested extension was to support multiple costs in a single Cost
>> Map.  If an ALTO Client is indeed interested in multiple costs
>> simultaneously from an ALTO Server, this seems like a very natural
>> extension, and in a couple of offline discussions, it appears to have
>> traction.
>>
>> Main Question: are there any objections to providing support for this?
>>
A central use case is also to support multiple cost types in requests and answers for the individual Endpoint Cost Service.
>> Proposed changes (along with some questions for discussion):
>>
>> + Allow an ALTO Server to indicate that it supports multiple costs.
>> ++ Is it worth allowing an ALTO Server to explicitly indicate how many
>> costs types may be requested simultaneously? (see next for an
>> alternative)
>>
>> + Add an error code for requesting too many ALTO Cost Types (to catch
>> requests from ALTO Clients that are beyond the capabilities of the
>> receiving ALTO Server).  This could perhaps be used instead of an
>> explicit limit advertised by an ALTO Server; an ALTO Client can just
>> try what it wishes, and then either split it into multiple queries if
>> it doesn't work. My preference would be this approach since it keeps
>> the "capabilities" processing cleaner, but I don't feel strongly.
>
> I think exposing this information in capabilities is better, because the
> client has to check them anyway and it gives the client the ability to
> match the server's limits exactly, without incurring guessing and error
> round trips. We also need to document what the server should do if a
> client attempts to exceed the advertised limit.
>
>> + Allow an ALTO Client to indicate multiple Cost Types in a request to
>> the Map Filtering Service (but still indicate a single Cost Mode).
>> This should be straightforward.
>> ++ Note that an alternative is to allow an ALTO Client to indicate a
>> vector of (Cost Type, Cost Mode) tuples. I can't quite get my head
>> around use cases for this. Should this be supported?
Indeed, we need to figure out a use case. Let's say a client may want cost type 1 in ordinal mode and type 2 and 3 in numerical. Cost type 1 would be used separately for a given application1 where as type 2 and 3 would be used jointly to rank the EPs for another application2. However, I suggest that only one mode should be requested for each Cost Type, say by default the "numerical" mode, as ordering the values from the numerical is straightforward. This also saves transport resources.
>
> I think we should defer to HTTP request pipelining to support this kind
> of beast. A typical implementation would split such a request into two
> processing units anyway.
>
- Could you explain what these 2 units correspond would correspond to ?
- How can we make sure that pipelining is activated?

>> ++ draft-randriamasy-alto-multi-cost-02 also mentions the requirement
>> that this mode should be supported only for "numerical" and not
>> "ordinal".  Though I would imagine "numerical" to be the common case
>> for something like this, I'm not sure there is a technical reason for
>> the limitation.  Any reasons to restrict this to a particular Cost
>> Mode in the specification?
>
> I cannot think of any. Obviously, the ordinal rankings will need to be
> done on a per-cost-type basis.

Yes, ordinal would be per-cost-type.

Actually there is no technical problem to use ordinal modes in cost vectors (or arrays). The issue is more on the numerical validity and robustness of comparing vectors of ranks. Although it is the responsability of the Application Client and not the ALTO services & protocol, to use the ALTO information properly, here is my motivation: 

It seems attractive to order rank values, since they are normalised with any 2 conscutive values having a difference equal to 1. However the difference in rank values does not correspond to the difference in actual cost values. For instance, you may have 4 Endpoints (EPs) having respectively ranks 1, 2, 3, 4 where as their actual cost values are equal to 10, 11, 60, 65. Where as this can be acceptable when a single Cost Type is used, when N >= 2 are used, the results of rank-value based EP ranking can be misleading. And the error gets worse when the Costs have different importance weights. Not to talk about mixing ordinal and numerical values. This is why, processing the costs should be left to the Application client.

EXAMPLE: 
- suppose I use 2 Cost Types to rank EPs, I get the cost vectors (or arrays...) in numerical mode, then process and normalize the values. 
- Suppose I get: {EP1 : [ 1, 1.8], EP2 : [ 5, 2], EP3 : [6.5 , 1], EP4 : [1 , 2]}. 
- Some method, say normal averaging, extracts a scalar cost for each EP and gives: EP1 : 1.4, EP2 : 3.5, EP3 : 3.75, EP4 : 1.5
- The increasing EP "numerical" Ranking gives: R1: EP1 , R2: EP4 , R3: EP2 , R4: EP3. 

If I request the ordinal values 
- I get: {EP1 : [ 1, 2], EP2 : [ 2, 3], EP3 : [ 3, 1], EP4 : [1 , 3]}
- normal averaging gives: EP1 : 1.5, EP2 : 2.5, EP3 : 2, EP4 : 2 
- The increasing EP "ordinal" Ranking gives: R1: EP1 , R2: [EP3 , EP4] , R3: EP2. The ordering is different from the "numerical one" and besides, EP3 and EP4 which are equally ranked have very different values and EP2, the worst ranked is numerically the closest one to the "best values".

>
>> + Should we try to make Cost Maps with multiple Cost Types available
>> via the Map Service as well?  Note that you can still get some of the
>> caching benefits by issuing a redirect (to an alternate URI requested
>> via GET) in response to a request to the Map Filtering Service.
>
> I think we should keep the symmetry of Map and Map Filtering services,
> so yes, both should support multi costs. Another option would be to
> advertise the multi-cost capability explicitly so the client can avoid
> the round trip.
>
>> + Allow an ALTO Cost Map to have a vector of costs for each
>> (source,destination) entry, with one element of the vector per
>> requested Cost Type. The ordering of the vector can be the same as the
>> ordering of the vector of Cost Types echoed in the response from the
>> ALTO Server. This basically allows an entry of the Cost Map be a JSON
>> array instead of a number as it is today.
>
> I don't think vectors will work, because two different (S, D) entries
> can have different sets of Cost Types defined. Or we would need a
> special NaN (not present, etc.) marker.

I don't see what the problem is from the ALTO side. Especially if the non-availability for some destination pairs can be easily marked with a JSON null. The Application Client using the Cost Map is aware anyhow that Maps do not necessarily support all Cost Types. So it should also consider that some Cost Types are not necessarily available for all (S,D) pairs.

Sure - a 'null' would work too in JSON.  The idea was to make it more
compact than specifying a JSON object for each entry of the cost map
(it seemed wasteful in space and processing overhead).

Thanks,
Rich

Thanks,
Sabine

> Bye,
> Robert
>
> --
> Robert Varga
> Pantheon Technologies, s.r.o.
> Mlynske Nivy 56
> 831 05 Bratislava
>
> _______________________________________________
> alto mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/alto
>
_______________________________________________
alto mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/alto

---

From: Richard Alimi <[email-masked]>
Date: Wed, 1 Jun 2011 15:30:37 -0700

Hi Sabine,

> A central use case is also to support multiple cost types in requests and answers for the individual Endpoint Cost Service.

Yes - that can be done as well.

> Indeed, we need to figure out a use case. Let's say a client may want cost type 1 in ordinal mode and type 2 and 3 in numerical. Cost type 1 would be used separately for a given application1 where…

It is possible to construct scenarios in which this might happen. We
are making a bit of a tradeoff for supporting an access pattern that
seems (to me, anyways) much less common. It is supported easily with
just 2 separate requests (as Robert pointed out). Where we stand on
the tradeoff curve is the part is less clear to me.

> - Could you explain what these 2 units correspond would correspond to ?

One request for "ordinal", and a second request for "numerical".

> - How can we make sure that pipelining is activated?

This is a concern of HTTP. My reading of Section 8.1.2.2 of RFC2616
says that servers need to support it if persistent connections are
supported.

> - The increasing EP "ordinal" Ranking gives: R1: EP1 , R2: [EP3 , EP4] , R3: EP2. The ordering is different from the "numerical one" and besides, EP3 and EP4 which are equally ranked have very diff…

Right. I don't think we are in any way recommending clients'
processing of the responses, beyond the definitions of Cost Mode that
is already in the protocol draft. Is there something above that gives
that impression? (If so, that needs to be fixed.)  If an application
wishes to treat something with an ordinal cost mode as you described
above, that would be (I think) a bug, but we don't care in the
protocol spec.

> I don't see what the problem is from the ALTO side. Especially if the non-availability for some destination pairs can be easily marked with a JSON null. The Application Client using the Cost Map is…

The ability to support 'missing' entries seems reasonable to me.

Thanks,
Rich

---

From: "RANDRIAMASY, SABINE (SABINE)" <[email-masked]>
Date: Thu, 2 Jun 2011 17:45:32 +0200

Hi Rich,

-----Message d'origine-----
De : [email-masked] [mailto:[email-masked]] De la part de Richard Alimi
Envoyé : jeudi 2 juin 2011 00:31
À : RANDRIAMASY, SABINE (SABINE)
Cc : Robert Varga; [email-masked]
Objet : Re: [alto] Multiple Cost Types in an ALTO Cost Map

Hi Sabine,

>>> costs types may be requested simultaneously? (see next for an

We may extend this to how many Cost Modes per Type when both modes are available. Unless it is considered obvious for the Application Client (AC) that it can convert Cost information in numerical mode in ordinal itself.   

I agree. Multi Cost transactions should be made as light as possible. I just tried to figure out a use case for needing both ordinal and numerical modes for a Cost Type. As for the related ALTO request, if the numerical mode is present and the ALTO Server explicitly indicates how many costs types/modes may be requested simultaneously the Application Client (AC) can organize its requests accordingly. 

Right. I don't think we are in any way recommending clients'
processing of the responses, beyond the definitions of Cost Mode that
is already in the protocol draft. Is there something above that gives
that impression? (If so, that needs to be fixed.)  

No, I didn't see any processing recommendations. It will be sufficient to provide in the Cost Type & Mode registry semantics to guide their usage by ALTO Clients. And some useful remarks such as in §5122 that says "It is important to note that the values in the Cost Map provided with the ordinal Cost Mode are not necessarily the actual cost known to the ALTO Server ". 

If an application

I agree, what the AC does is out of the protocol scope. 
My comment and draft focused on the case of *joint* usage of different Cost Types to evaluate EPs. Moreover, if they are evaluated on a per-cost-type basis as mentioned by you and Robert, any Cost Mode is acceptable.
So for the question on "any reasons to restrict to a particular Cost Mode in the specification", my answer now is: no, there is no reason. Especially if only the ordinal information is available for a Cost Type. 

Thanks,
Rich

Thanks,
Sabine

---

From: Ben Niven-Jenkins <[email-masked]>
Date: Mon, 6 Jun 2011 10:38:34 +0100

Rich,

Please see inline for my opinion.

> Main Question: are there any objections to providing support for this?

Not from me, it seems a reasonable extension to have.

> + Allow an ALTO Server to indicate that it supports multiple costs.

The existing Information Resource Directory in -08 already allows this. I guess the change would be changing the semantics from "I support all of these cost-modes/types and you may filter on one of them" to "I support all of these cost-modes/types and you may filter on any combination of them".
 
> costs types may be requested simultaneously? (see next for an

I'd assume that if an ALTO server is advertising via the Information Resource Directory that a particular URI supports multiple cost-types then it is capable of returning any combination of those, for example if I saw:

         "uri" : "http://alto.example.com/costmap/numerical",
         "media-types" : [ "application/alto-costmap+json" ],
         "accepts" : [ "application/alto-costmapfilter+json" ],
         "capabilities" : {
           "cost-modes" : [ "numerical" ],
           "cost-types" : [ "routingcost", "hopcount" ]
         }

I would assume a GET to http://alto.example.com/costmap/numerical would return me a cost map with both routingcosts & hopcounts.

Or, I could POST a alto-costmapfilter and request one or both of the supported costmaps.

If an ALTO Server wanted to restrict the combination of cost-modes/types it was willing to return it could do so by constructing the entries in the Resource Directory appropriately.

> the "capabilities" processing cleaner, but I don't feel strongly.

You may well need this anyway to handle cases where a server advertises that a particular URI supports a single cost-type and the client tries to request multiple cost-types by mistake.

> around use cases for this. Should this be supported?

You could support multiple modes with a dictionary of mode: types in the filter, something like:

   {
     "cost-filter" : {
       "numerical" : [ "routingcost" ],
       "ordinal" : [ "hopcount" ]
     }

     ...
   }

For ordinal costs I guess the order of the listed cost-types would need to indicate the priority order in which to apply the cost-types when ranking EndPoints/PIDs.

I'm not quite sure what the use case for mixing numerical & ordinal costs would be though.

> via GET) in response to a request to the Map Filtering Service.

Yes I can use cases for a client wanting the map (or some subset of it) and multiple costs. Doing it in a single request/response would have benefits Vs multiple requests if the map is large (assuming the encoding of the multiple cost-types in a single map is not too verbose).

> array instead of a number as it is today.

Seems reasonable (as others have noted some kind of NULL would need to be supported for cases where a (S, D) pair did not have a particular cost-type associated with it).

Ben

> 
> Beyond the overall question of whether there are any objections, any
> feedback on the proposed changes are welcome!
> 
> Thanks,
> Rich

---

From: Richard Alimi <[email-masked]>
Date: Wed, 8 Jun 2011 01:56:32 -0700

Hi Ben,

> The existing Information Resource Directory in -08 already allows this. I guess the change would be changing the semantics from "I support all of these cost-modes/types and you may filter on one of…

Yes, that is the distinction that must be made, except that this isn't
only the 'filtering' cast. It applies to getting the full cost map too
(I'm assuming that's what you meant?).

> If an ALTO Server wanted to restrict the combination of cost-modes/types it was willing to return it could do so by constructing the entries in the Resource Directory appropriately.

Yes, that is a possibility as well. However, if an ALTO Server does
not wish to support returning multiple cost types, then it must
provide a single entry in the resource directory for each cost type.
That seems a bit verbose?  Furthermore, if an ALTO Server wished to
only provide up to a fixed number (say, 3) of cost types in an effort
to limit the amount of work it needs to do per request, it would need
to construct resource directory entries for all (N choose 3)
combinations.

> You may well need this anyway to handle cases where a server advertises that a particular URI supports a single cost-type and the client tries to request multiple cost-types by mistake.

Sure.

>       "ordinal" : [ "hopcount" ]

Yeah - I wasn't worried about the encoding, but rather the use case
for it and whether that should be supported.

> For ordinal costs I guess the order of the listed cost-types would need to indicate the priority order in which to apply the cost-types when ranking EndPoints/PIDs.

Interesting question.  I'm not so sure that I agree with that -- this
seems more like the application's concern to make this tradeoff,
meaning the draft should stay silent about it (or at the most, say
that the order of cost types implies nothing about their importance).

> I'm not quite sure what the use case for mixing numerical & ordinal costs would be though.

Okay, that seems to be the consensus. Leaving it out sounds good to me.

> Yes I can use cases for a client wanting the map (or some subset of it) and multiple costs. Doing it in a single request/response would have benefits Vs multiple requests if the map is large (assum…

The question was whether we should force the client to use a POST in
this case, or structure the directory and protocol such that it can
use GET.  In either case, multiple cost types would come back in a
single response.

> Seems reasonable (as others have noted some kind of NULL would need to be supported for cases where a (S, D) pair did not have a particular cost-type associated with it).

Agree. Thanks!

Rich

---

From: Ben Niven-Jenkins <[email-masked]>
Date: Mon, 13 Jun 2011 23:08:55 +0100

Rich,

See inline.

> (I'm assuming that's what you meant?).

In my mind the full cost map is just a filtered cost map with an empty pids property (i.e. all PIDs). 

We may be saying the same thing in different ways but...

IMO a GET should return a resource will all the cost-modes/types specified in the Information Resource directory entry (as such a cost-map with multiple modes/types could still be supported by a static file if one so desired).

A POST is required to filter. A POST with multiple cost-modes/types but an empty pids property returns the full cost map for the requested (filtered) cost-modes/types. Additionally if pids is non-empty the cost map is filtered by both the specified cost-mode/types and the specified pids.

> That seems a bit verbose?

I guess it depends on how many cost-modes/types we think are going to be defined and supported by a single ALTO server in reality. Entries in a resource directory are cheap IMO so verbosity is not really that much of an issue and I suspect that the number of different cost-modes/types we define will be limited to "a handful".

>  Furthermore, if an ALTO Server wished to

Hmmm that is true but begs the question of how likely it is that an ALTO server will be prepared to support complex queries (i.e. multiple cost-mode/type filters) but then want to limit the complexity of the requests?

One thing this conversation has highlighted to me though is that we do need to be more explicit in the protocol document on the specification of the "capabilities" property and what the semantics are when there are multiple cost-mode/type entries in it.

> that the order of cost types implies nothing about their importance).

I'm not sure that the application can do that. The server is returning an ordinal ranking meaning where no two entries can have the same rank, correct?

In which case the application can't apply a second ranking to entries that are "equal" according to a first ranking criteria because the ALTO server will never return two entries with the same ordinal rank.

> use GET.  In either case, multiple cost types would come back in a

If we have the semantic that GET returns all listed cost-mode/types then we can do either with the tradeoff that if an ALTO server wants to support complex combinations of different cost-mode/type filters for the entire cost map via GET they have a more verbose resource directory.

IMO for filtered cost-modes/maps where only a subset of the cost map is required then only being able to POST is probably not an issue as the chance of two clients wanting exactly the same filter with the same set of PIDs is small, but the ALTO server can always make use of redirects if it wants to offer GET-able responses for subsequent cacheability.

Ben

---

From: Richard Alimi <[email-masked]>
Date: Tue, 14 Jun 2011 21:32:39 -0700

Hi Ben,

> A POST is required to filter. A POST with multiple cost-modes/types but an empty pids property returns the full cost map for the requested (filtered) cost-modes/types. Additionally if pids is non-e…

Yes - this was the later question in the email. It sounds like your
saying "Yes, we should try hard to support multiple costs via GET
requests"

> Hmmm that is true but begs the question of how likely it is that an ALTO server will be prepared to support complex queries (i.e. multiple cost-mode/type filters) but then want to limit the complex…

For the filtering queries, I'd agree the server is likely be be more
prepared to handle the more complex requests. However, it also sounds
like responders on this thread are in favor of also supporting
multiple cost types via GET, which are currently the requests that are
likely to be "cheaper" and more likely cachable.  In that case, it
seems very reasonable that the server should be able to bound the work
that its doing.

> One thing this conversation has highlighted to me though is that we do need to be more explicit in the protocol document on the specification of the "capabilities" property and what the semantics a…

We can certainly work on the text here.

> In which case the application can't apply a second ranking to entries that are "equal" according to a first ranking criteria because the ALTO server will never return two entries with the same ordi…

The proposed design would be that the client gets back an ordinal
ranking of each cost type independently. For example, if an
application requested ranking by routingcost and latency, a client
might wish to rank first by latency, but if two entries are close, it
might decide to switch the order if the routingcost is better.

This logic seems better placed in the client. The server may have no
idea what type of application is querying it.

> If we have the semantic that GET returns all listed cost-mode/types then we can do either with the tradeoff that if an ALTO server wants to support complex combinations of different cost-mode/type…

Yes - I'll avoid replying here since that is the discussion we're
having above :)

> IMO for filtered cost-modes/maps where only a subset of the cost map is required then only being able to POST is probably not an issue as the chance of two clients wanting exactly the same filter w…

That is the design in the current protocol document, yes?  The change
being discussed here shouldn't change that.

Rich