Ben, Vijay,
On Jan 31, 2012, at 12:51 AM, Ben Niven-Jenkins wrote:
> Vijay,
>
> On 30 Jan 2012, at 23:06, Vijay K. Gurbani wrote:
>
>> As individual.
>>
>> Ben: Please see inline.
>>
>> On 01/30/2012 11:03 AM, Ben Niven-Jenkins 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
>>> 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.
>
> 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.
>> More below.
>>
>>> For example if a cost map contains:
>>>
>>> "map" : {
>>> "PID1": { "PID2": 1 },
>>> "PID2": { "PID1": 1, "PID3": 2 },
>>> "PID3": { "PID2": 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.
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/configured of routing between its
> WAN interfaces?
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.
>
> Ben
>
>
>>
>> Now, for the second example I get a graph of the form:
>>
>>> How about if the cost map contains:
>>>
>>> "map" : {
>>> "PID1": { "PID2": 1, "PID3": 3 },
>>> "PID2": { "PID1": 1, "PID3": 2 },
>>> "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 protected]
>> Web: http://ect.bell-labs.com/who/vkg/
>
> _______________________________________________
> alto mailing list
> [email protected]
> https://www.ietf.org/mailman/listinfo/alto
>
_______________________________________________
alto mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/alto
