As Sebastian points out, sparse cost maps are allowed, and if the map is
sparse, it's reasonable to have a large number of PIDs.
But there's a gotcha. Remember clients must store the cost map, and lookup
costs as needed. If the client knows the matrix is sparse, the client can
store it as a hash table, where the key is the concatenation of the source
& dest PID names. That's simple & efficient.
Unfortunately, if the matrix ISN'T sparse, that technique is horribly
inefficient. If the matrix is full, the client should convert pid names to
index numbers (sort the PID names, use binary search to get the index),
and then store the costs in a conventional float[N][N] array.
And, of course, that technique is wasteful for a sparse cost matrix.
So the client has to guess how "sparse" the cost matrix really is.
- Wendy Roome
>Message: 2
>Date: Fri, 22 Mar 2013 08:30:14 +0100
>From: Sebastian Kiesel <[email protected]>
>To: [email protected]
>Subject: [alto] The size of the cost map
>Message-ID: <[email protected]>
>Content-Type: text/plain; charset=us-ascii
>
>Hi,
>
>lately we've been discussing linear vs. quadratic growth of the cost map,
>but at least I had no real feeling what this means in terms of bytes on
>the wire, using our JSON encoding. So I made a short experiment that I
>want to share:
>
_______________________________________________
alto mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/alto
