Subject: Re: [alto] Are ALTO costs always End to End?

From: Richard Alimi <[email-masked]>
Date: Wed, 1 Feb 2012 00:04:04 -0800

I guess I'm a bit late to the party, so I can keep this simple and say
how the draft was currently intended:
(1) The choice of the term "endpoint" (those thingy's that are
contained in PIDs) was not an accident :)
(2) As such, each entry of the Cost Map is the *end-to-end* cost from
the source to the destination (I think this is what Ben meant by
"mesh").  That is, the ALTO Server has already added up the costs on
the physical links along the path for you.
(3) If there is an entry missing from the Cost Map, it means the ALTO
Server doesn't know the cost from that source to destination (or isn't
willing to tell you). I guess you could generate a path, but the point
about whether a packet can actually traverse that path is a good one
-- ALTO doesn't make any claims on routing capabilities offered by
endpoints.

Given that particular meaning, you could imagine doing overlay routing
on that (e.g., in a P2P swarm). In that sense, each endpoint is a node
on a graph, and you could imagine doing shortest path on that.
However, that's quite different than doing shortest path on the actual
network topology.  This was the reason for my comments a few times (I
guess not on the list, it was probably at the mic during a WG session)
that if we were to ever expose raw network topology via ALTO, then we
need to explicitly denote that it would be a different interpretation
of the Cost Map than we have today (an adjacency matrix seems like a
reasonable model here).

Along those lines, I'm a little bit hesitant of the proposal to add a
"transit" attribute to a PID, since that seems to conflate the two
possible interpretations of the cost map (end-to-end costs vs.
adjacency matrix).  If we wanted to convey the actual graph, how about
have an attribute for the entire cost map that indicates explicitly
that it is to be interpreted as an adjacency matrix (and obviously,
ordinal costs would not make sense there).

Given this discussion and the confusion it caused, we'll have to go
back and ensure this is explicitly stated in the draft.

Thoughts?
Rich

On Mon, Jan 30, 2012 at 9:03 AM, Ben Niven-Jenkins
<[email-masked]> wrote:
> Colleagues,
>
> In the current specification of ALTO, are costs always End to End?
>
> What I mean by that is when looking at ALTO cost maps is it possible to safely assume that of there is a cost between PIDX & PID Y and a cost between PIDY & PIDZ then the cost between PIDX & PIDZ can be calculated as cost(PIDX,PIDY)+cost(PIDY,PIDZ)? [If this assumption does hold, it is obviously not applicable to ordinal cost types].
>
> I suspect the answer is no, but I wanted to check what the definitive answer is.
>
>
> For example if a cost map contains:
>
>   "map" : {
>     "PID1": { "PID2": 1 },
>     "PID2": { "PID1": 1, "PID3": 2 },
>     "PID3": { "PID2": 2 }
>
> Can one assume that the cost between PID1 & PID3 is 3 (PID1->PID2 + PID2->PID3)?
>
> How about if the cost map contains:
>
>   "map" : {
>     "PID1": { "PID2": 1, "PID3": 3 },
>     "PID2": { "PID1": 1, "PID3": 2 },
>     "PID3": { "PID2": 2, "PID1": 3 }
>
> Can one assume PID2 is on a path between PID1 & PID3?
>
> Thanks
> Ben
>
> _______________________________________________
> alto mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/alto

---

From: Jan Medved <[email-masked]>
Date: Wed, 1 Feb 2012 00:08:07 -0800

On Jan 31, 2012, at 7:29 AM, stefano previdi wrote:

> 
> On Jan 31, 2012, at 4:08 PM, Vijay K. Gurbani wrote:
> 
>> On 01/31/2012 05:14 AM, stefano previdi wrote:
>> ben> This might be a case where we'd need a PID property to distinguish
>> ben> "transit" PIDs from "End Host" PIDs.
>> ben>
>> stefano> sounds pretty reasonable to me.
>> 
>> Ben: I suspect that your question had a foundation of some sort
>> and was not simply a fishing expedition ;-)
>> 
>> Let me ask you this: is the PID property that you would like to put
>> in useful for CDN-usage in ALTO?
> 
> 
> there are a variety of cases where this would be useful. When 
> you distribute a link-state topology you know you're talking 
> about routers and links and semantic is well-known. Same when 
> you advertise BGP routes or VPNv4 routes or whatever... the 
> protocol has the semantic you need to consider.
> 
> In ALTO you have the necessary bits to tell if cost is based on 
> routing or air miles or others but you don't really know what a 
> PID is (other than a bunch of addresses).
> 
Right, but the costs (and cost types) are associated with cost maps, not network maps. I still think a "transit" PID does not make sense (while thinking that PID attributes are a good thing). 

A while back we did model link-state topology in ALTO, and the only sensible way we could figure out was to assign a PID to each router interface and to model a router as a set of PID where costs between the "interface" PIDs were 0. Links were modeled in the the Cost Map, where the link cost mapped directly into the cost between two "interface" PIDs. It did work, but then BGP-LS came along, which was a much cleaner way to convert topology. 

If we want to convey topology to apps via ALTO, we have to come up with a convention, so that the receiving app can properly interpret it. Stefano, Rich W, Jon and I proposed such convention a couple of IETFs ago, but there was lot of resistance to it at that time. Maybe the time is right for it this time…

/Jan

---

From: stefano previdi <[email-masked]>
Date: Wed, 1 Feb 2012 09:57:07 +0100

Hi Rich,

> the physical links along the path for you.

do you intend that a cost map is supposed to be a full mesh of leaf 
nodes (as per analogy to SPF algorithm) ? IOW: you're not expected to 
transit across PIDs ?

> of the Cost Map than we have today (an adjacency matrix seems like a

I believe we have two orthogonal elements:

1. Information that can be leveraged by traditional SPF/Dijktra 
   algorithm so to compute a topology using same algorithm/paradigms 
   than the ones used in the network. This can be a cost map, I don't 
   mind, as long as the semantic of the information is compatible with 
   what we want to do with it. In this respect, Ben asked a valid 
   question.

2. The ability, for an ALTO server, to deliver a partial or aggregated 
   or virtual topology that would NOT represent the reality of the 
   network infrastructure but rather the topology that the application 
   needs in order to optimize its business.

Implementors have worked quite a bit on the latter.

> ordinal costs would not make sense there).

FYI: routing protocols do have such node attribute. In ISIS we call 
it "overload-bit" and allows an operator to define a router as a 
non-transit device. Having the same capability in ALTO doesn't look 
unreasonable to me.

I'd go a bit further and I believe having PID Capabilities TLV would
probably help.

s.

---

From: Richard Alimi <[email-masked]>
Date: Wed, 1 Feb 2012 02:16:57 -0800

> nodes (as per analogy to SPF algorithm) ? IOW: you're not expected to

Correct.  Transiting across PIDs would be an application-level concern
(e.g., constructing a P2P overlay) and outside of the scope of ALTO.
Since we're dealing with applications endpoints who are sending
resources back and forth (at least thats what ALTO was chartered for
:) ), the cost map indicates the cost of sending that resource from
one endpoint to another endpoint.

Now, in the CDN world, I agree those assumptions begin to change and
we start getting closer to an actual network topology (or aggregated
view of it)... hence this whole discussion.. :)

>   what we want to do with it. In this respect, Ben asked a valid

Yes - my only point is that if a cost map is to be interpreted this
way, it seems much cleaner/understandable to me if this mode is
explicitly indicated by the ALTO server.  More on this below...

>   needs in order to optimize its business.

Right - I agree that is orthogonal.

> I'd go a bit further and I believe having PID Capabilities TLV would

Okay, so let me try to put this all in perspective :) Imagine being an
application presented with a Cost Map from some ALTO Server.  Let's
assume for a minute that you don't have any pre-existing knowledge of
the ALTO Server and policies it uses to generate that information.  So
far on this thread we have discussed two possible ways to determine
the cost of sending some bytes from A -> B:
(1) Lookup (A, B) in the cost map [ this is what the protocol draft
currently prescribes ]
(2) Treat the cost map as an adjacency matrix, construct the
corresponding graph, compute the shortest path from A->B, and then
compute the cost based on that path (the particular mathematical
operation will depend on the cost type).

The application needs to know which algorithm to use.  What I'm
proposing is if an application is to interpret this as (2), then the
cost map returned by the ALTO Server be marked with an attribute
indicating that.

If when computing (2), certain PIDs were marked as non-transit, that
seems reasonable.  I would start to worry about scope-creep though.
There should be some dividing line to ensure we're not going to end up
building a generic data structure to carry what looks like a (perhaps
aggregated) link-state database.  In any case, thats probably a topic
for after (2) gets proposed/documented as an extension :)

The application of the non-transit PID attribute in (1) is less clear
to me, but I might imagine a few application-level heuristics that
could use that as input. For example, don't treat an endpoint in a
non-transit PID as a seed in a high-bandwidth peer in a P2P swarm.
However, it seems like those kinds of heuristics could equally be
gained by adjusting the costs in the Cost Map instead of introducing a
new attribute.

Thanks,
Rich

---

From: stefano previdi <[email-masked]>
Date: Wed, 1 Feb 2012 11:56:03 +0100

> one endpoint to another endpoint.

yes, well, this was the original context and therefore your point is 
right.

> view of it)... hence this whole discussion.. :)

exactly. And keep in mind that CDN is just another use case. Others 
are being addressed by existing alto application as well (e.g.: 
alto/topology guided DNS, Cloud Networking, ...).

> explicitly indicated by the ALTO server.  More on this below...

Agreed, hence the capability/characteristics TLV.

> the ALTO Server and policies it uses to generate that information.

which is the case most of the time.

> So

just for completion, there's a 3rd way: ECS which allows an app not 
to deal with mechanisms ALTO uses for building topology and doesn't
require the app to have any topology computational intelligence.

> cost map returned by the ALTO Server be marked with an attribute

yes, I agree. 

> for after (2) gets proposed/documented as an extension :)

so if I understand your point, we could have:
1. an attribute describing the whole map (graph vs. tree vs. mesh)
2. a pid attribute describing pid characteristics/capabilities

if so, then we are in agreement.

> non-transit PID as a seed in a high-bandwidth peer in a P2P swarm.

again, there are many other non-p2p apps out there.

> gained by adjusting the costs in the Cost Map instead of introducing a

You _MAY_ handle some cases with costs but it can become VERY complex 
and also you MUST have a cost for each direction of the link/branch 
connecting two PIDs.

As an implementor, I'd discourage that way...

s.

---

From: Richard Alimi <[email-masked]>
Date: Wed, 1 Feb 2012 09:26:12 -0800

> if so, then we are in agreement.

Yes.  I believe we are in agreement.

> As an implementor, I'd discourage that way...

That's true.

Rich

---

From: Ben Niven-Jenkins <[email-masked]>
Date: Wed, 1 Feb 2012 20:18:42 +0000

Vijay,

> and was not simply a fishing expedition ;-)

The question does have a foundation :-) Partly I'm trying to understand precisely what I can & can not infer from an ALTO map and Bill & Rich's follow-up confirm a lot of that for me. We probably want to add some text to the protocol spec to clarify that because I suspect if I'm asking the question then someone else looking to use ALTO for a purpose that wasn't originally in scope and who hasn't been involved with ALTO from day 1 might have similar questions.

At the same time I'm trying to think through the applicability of ALTO to a number of CDN-related scenarios.

One scenario is whether I can get enough "resolution" out of an ALTO map to represent the network topology (as it pertains to a CDN) sufficiently. If I need to augment what I can get from ALTO with raw IGP/BGP routing to get a sufficient (for the CDN) topology then it negates a good chunk of the value provided by ALTO IMO. It's worth clarifying here that by "sufficient topology for a CDN" I don't mean being able to translate a network map back into the raw network topology, I only need enough topology to overlay a CDN topology on top of. After thinking a bit more about this I think ALTO as-is probably provides sufficient information for the purpose although not in the most efficient form (but that's not showstopper).

The other scenarios relate to using ALTO maps for more than just CDN cache selection and in those scenarios I'm thinking that ALTO is still probably OK and I can achieve a lot of what I need without needing ALTO to expose me a graph, provided there are some common constraints applied by the ALTO server (like not renaming PIDs) but I need to give those scenarios some more thought. I might have a couple of ideas for extensions once I'm done (like enabling entries in the IRD to be given a name/ID) but that's a separate topic. 
 
> in useful for CDN-usage in ALTO?  If so, and since others
> (Stefano) appear to agree, then it is worth a larger discussion on
> the need of such a property to support emerging usages of ALTO.

I'm starting to conclude I don't need the PID property to achieve what I want but I haven't 100% convinced myself of that yet. I think the idea of PID properties is interesting though so if there's a discussion on them I'll get involved. I might have some other use cases but I haven;t really given them any thought yet.

Ben

> 
> Thanks,
> 
> - vijay
> -- 
> Vijay K. Gurbani, Bell Laboratories, Alcatel-Lucent
> 1960 Lucent Lane, Rm. 9C-533, Naperville, Illinois 60566 (USA)
> Email: vkg@{bell-labs.com,acm.org} / [email-masked]
> Web:   http://ect.bell-labs.com/who/vkg/

---

From: Jan Medved <[email-masked]>
Date: Thu, 2 Feb 2012 22:55:06 -0800

On Feb 1, 2012, at 12:18 PM, Ben Niven-Jenkins wrote:

> One scenario is whether I can get enough "resolution" out of an ALTO map to represent the network topology (as it pertains to a CDN) sufficiently.

Yes you can. ALTO servers providing this functionality have been designed, implemented and some of them are in production.

> If I need to augment what I can get from ALTO with raw IGP/BGP routing to get a sufficient (for the CDN) topology then it negates a good chunk of the value provided by ALTO IMO.

You don't need to augment ALTO with IGP/BGP data. The ALTO data model has enough flexibility to convey sufficient topology information from IGP/BGP to a CDN. Again, ALTO servers that do this have been designed, implemented and some of them are in production. CDN Request Routers that utilize topology information from an ALTO Server have been designed, implemented and some of them are in production. 

> It's worth clarifying here that by "sufficient topology for a CDN" I don't mean being able to translate a network map back into the raw network topology, I only need enough topology to overlay a CDN topology on top of. After thinking a bit more about this I think ALTO as-is probably provides sufficient information for the purpose although not in the most efficient form (but that's not showstopper).
> 
We are in agreement here. Even the efficiency is good enough, especially if you use the Endpoint Cost Interface.

> I'm starting to conclude I don't need the PID property to achieve what I want but I haven't 100% convinced myself of that yet. I think the idea of PID properties is interesting though so if there's…
PID properties (a.k.a PID attributes) are a good idea. "Transit" PIDs are not.

/Jan