Practical computational cost

Let $i$ be the number of interior (non-leaf) nodes in the tree (1594 in our study). Let $H$ be the height of the tree, the maximum number of AS-hops for any path (15 in our study). Let $m$ be the maximum number of proxy caches placed (50 in our study).

Each AS is visited exactly once to compute his cost matrix. The total number of cost matrices computed is $i$.

Each cost matrix has $K$ rows. The total number of cost rows computed is $i * K$.

Each of those rows is a combination of the contributions from all of the children of the node. Let $\delta$ be the number of children of node $v$. As previously noted, there will be $K$ rows at node $v$. Each of those rows will have $m+1$ items representing values from 0 to $m$ pebbles. The initial local cost matrix of the parent will be combined $\delta$ times with other matrices (once for each child).

After several simple optimizations, our test run with a tree of 21 backbone nodes totaling 6395 nodes had 69,486 row combinations in the 6395 matrix combinations.