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