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

From: Ben Niven-Jenkins <[email-masked]>
Date: Mon, 30 Jan 2012 17:03:05 +0000

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

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Mon, 30 Jan 2012 17:06:16 -0600

As individual.

Ben: Please see inline.

On 01/30/2012 11:03 AM, Ben Niven-Jenkins wrote:
> 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
> definitiveanswer is.

It will be interesting to hear from the authors, but here is my
two cents.

If I take the cost map and create a graph from it, and if the graph is
connected and I simply run Dijkstra's shortest path algorithm on it,
then I suspect the answer is yes.

More below.

>       "PID2": { "PID1": 1, "PID3": 2 },

If one were to construct a graph from the above cost map --- omitting
edges emanating and terminating at the same vertex and assuming
bi-directional links --- one would get:

           PID-2
            /\
          1/  \2
          /    \
       PID-1  PID-3

> Can one assume that the cost between PID1& PID3 is 3 (PID1->PID2 +
> PID2->PID3)?

Clearly, PID-3 is reachable from PID-1 via PID-2 at a cost of 3.

>       "PID3": { "PID2": 2, "PID1": 3 }

           PID-2
            /\
          1/  \2
          /    \
     PID-1------PID-3
             3

> Can one assume PID2 is on a path between PID1&  PID3?

PID-2 may be on a path, but it may not be the *shortest* path.
Although in the above example, it really does not matter since the cost
to reach PID-3 from PID-1 is 3 regardless of whether we go through
PID-2 or directly from PID-1 to PID-3.  Now, if the shortest path
computation algorithm was optimizing other metrics besides cost of the
edges (say, the hop count), then the best path from PID-1 to PID-3 would
be the direct path.

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: Ben Niven-Jenkins <[email-masked]>
Date: Mon, 30 Jan 2012 23:51:16 +0000

Vijay,

> then I suspect the answer is yes.

I guess my question is really whether an ALTO cost map is a graph or a mesh? I always assumed it was a mesh but then I got wondering...

> Clearly, PID-3 is reachable from PID-1 via PID-2 at a cost of 3.

I started considering that case but then wondered how to tell the difference between PID3 being reachable from PID1 via PID2 and PID2, for example, being a dual homed host/site that isn't capable/configured of routing between its WAN interfaces?

This might be a case where we'd need a PID property to distinguish "transit" PIDs from "End Host" PIDs.

Ben

---

From: Jan Medved <[email-masked]>
Date: Mon, 30 Jan 2012 22:22:30 -0800

> I started considering that case but then wondered how to tell the difference between PID3 being reachable from PID1 via PID2 and PID2, for example, being a dual homed host/site that isn't capable/c…

It's not clear what you mean. Can you perhaps draw a diagram that would explain the topology you have in mind?

> This might be a case where we'd need a PID property to distinguish "transit" PIDs from "End Host" PIDs.

A "transit" PID does not make sense. As Vijay explained below, you can not infer any topology from ALTO costs. If you need topology, it's best to get it directly from IGP/BGP routing protocols, or to use something like BGP-LS which helps to avoid peering with IGP speakers.

> Ben

/Jan

> _______________________________________________
> alto mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/alto

---

From: stefano previdi <[email-masked]>
Date: Tue, 31 Jan 2012 12:14:48 +0100

Ben, Vijay,

> I guess my question is really whether an ALTO cost map is a graph or a mesh? I always assumed it was a mesh but then I got wondering...

Well, you raised a pretty valid (and tricky) point here. I don't think 
we ever put much attention on the topology representation an alto map 
could/should/must have. It could be a graph, it could be an instance of 
a pre-calculated shortest path (i.e.: you won't see all paths but only 
the shortest one).

Note that the construction of the alto maps doesn't have to follow any 
specific rules as it is out of scope. IOW: you get what  alto server 
decides to give you.

>> Clearly, PID-3 is reachable from PID-1 via PID-2 at a cost of 3.

keep in mind that asymmetric routing is very common so you better 
compute your paths according to the direction the traffic is going 
to take.

In your example it doesn't make much different but in case you have a 
more meshed topology, it really DOES make the difference. 

You MUST have all mechanisms in order to match what your routers/network
will do at the end of the day (i.e.: packets are forwarded according to 
your ospf/isis shortest path and BGP selection, not your alto magic).

> I started considering that case but then wondered how to tell the difference between PID3 being reachable from PID1 via PID2 and PID2, for example, being a dual homed host/site that isn't capable/c…

Good point.

I suppose that by default all PIDs will have similar capabilities. IOW: 
in the picture Vijay drawn I expect all :IDs having "routing/transit" 
capabilities.

SPF-Dijsktra computation will give you the exact picture of your topology. 
And if you apply some extensions (like reverse-spf, multi-root-spf, etc 
etc) you can sort out most cases.

> This might be a case where we'd need a PID property to distinguish "transit" PIDs from "End Host" PIDs.

sounds pretty reasonable to me.

s.

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Tue, 31 Jan 2012 09:08:23 -0600

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?  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.

Thanks,

- vijay

---

From: stefano previdi <[email-masked]>
Date: Tue, 31 Jan 2012 16:29:43 +0100

On Jan 31, 2012, at 4:08 PM, Vijay K. Gurbani wrote:

> 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).

>  If so, and since others

yes, I _tend_ to agree... until we find disagreement of course ;-)

s.

---

From: "Vijay K. Gurbani" <[email-masked]>
Date: Tue, 31 Jan 2012 13:21:51 -0600

On 01/31/2012 09:29 AM, stefano previdi wrote:
> 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.

Stefano: True.

> routing or air miles or others but you don't really know what a PID
> is (other than a bunch of addresses).

That was a strategic design decision, as far as I can recall.
A PID abstracted a collection of some hosts, the collection
being defined by the entity populating such a collection in
a network map and cost map for the consumption of the ALTO
server.

Now, there is nothing that stops us from having a singleton
host --- a router --- be in its own PID and then show that
PID as being reachable from other PIDs.  This affects the
case that Ben may be thinking about ... Ben?

> yes, I _tend_ to agree... until we find disagreement of course ;-)

Of course.  To be sure, I am not disagreeing with you; just
trying to add to the discussion.

Ciao,

- vijay