Implementation

Our simultaneous placement algorithm is a dynamic programming algorithm that visits each node exactly once to determine the best use of $m$ caches in its subtree. The algorithm discovers the optimal placement of all values of $\ell$ caches from $0$ to $m$ so as to minimize the total cost of traffic.

The result of running the evaluation on any node $v$ is a $k \times m$ matrix $f_v (k, \ell)$ containing the total costs of the subtree where $0 \le \ell \le m$ is the number of caches and $k$ is the distance to the nearest source of the data. For each element of the matrix, the node must choose how many pebbles to give to each of its children and whether or not to keep a pebble for itself.

Leaf nodes can compute their cost matrix $f_v (k, \ell)$ easily. If they are given one or more pebbles, their cost is simply the number of bytes of replies needed by that AS. Assume $t_v$ is that number of local traffic bytes at node $v$. If a leaf is given zero pebbles, his cost is $k * t_v$. In the implementation, we used a matrix that is 15 rows high, representing values of $k$ from 0 to 14. In our study, the maximum number of pebbles, $m$, is set to 50 but could be increased at the cost of running time and memory consumed by the algorithm.

Define $f_{v, d}^{b}(k, \ell)$ to be the cost of a daughter subtree of $T_v$, where $1 \le d \le \Delta$ is one of the $\Delta$ daughters of node $v$.

Each row $k$ of $f_v^0(k, \ell)$ is computed using row $k+1$ from the daughters. Start with the first daughter's $k+1$ row intact. Then for each subsequent daughter, test all distributions of $\ell' + \ell'' = \ell$ pebbles in which $\ell'$ pebbles are given to the prior daughters and $\ell''$ pebbles are given to the new child.

$$f_{v, d}^{0}(k, \ell) = \min_{\ell' + \ell'' = \ell} \{ f_{v, d-1}^{0}(k, \ell') + f_{v_d}(k+1, \ell'') \}.$$

When all $\Delta$ children have been combined, the resulting $f_{v,\Delta}^0(k, \ell)$ matrix is $f_v^0(k, \ell)$.

Now we construct $f_v^1(k, \ell)$. The first element, $f_v^1(0,0)$ is $\infty$, because no pebble is available. To find the rest of $f_v^1(k, \ell)$, take the first row of $f_v^0(k, \ell)$ and shift it down by 1 pebble because the children will only have $\ell -1$ pebbles to distribute. Note that all other rows of the matrix are copies of row $0$.

$$f_v^1(k, \ell) = f_v^0(0, \ell - 1)$$

Finally, each element $f_v (k, \ell)$ is the minimum of $f_v^1(k, \ell)$ and $f_v^0(k, \ell)$.

To compute the best placement for the whole tree, we compute the cost matrix of the root, $f_{root}(k, \ell)$. The row $k=0$ contains the minimum cost for the whole tree for values of $0 \le \ell \le m$.