Cache Placement

The result of our clustering algorithm is a hierarchical tree rooted at the backbone containing clusters of AS's in increasingly detailed groups. The fundamental assumption is that analysis of a load pattern against this model will yield a useful, objective measure of the value of placing caches into this tree. The problem is similar to that posed by Li, et al. [17], but we simplified it by setting the delivery cost to be the number of Autonomous Systems that the reply entered times the number of bytes in the reply.

To do this, we assign a weight to each leaf node equal to the number of bytes given to it in successful replies. Parent clusters of that leaf are responsible for finding the optimal use of $m$ proxy caches for each value of $\ell$ up to the total number of proxy caches we can afford to place. Each node can choose to distribute those $\ell$ caches in any amounts among its children and can choose to keep one for itself. We visualize this as pebbles placed onto the tree wherever a proxy cache is indicated. Our cache placement study assumes that any proxy cache will completely satisfy all requests sent to it. Assume that all requests are sent to web servers on the backbone. The cost of each reply is the number of AS's that see the reply (including the originating AS) multiplied by the size in bytes of the reply. The cost of the requests is ignored.

Figure 4: Tadpole Graph Example

Figure 4 shows a subtree near the bottom of a large tree. In the absence of caches, the 600 bytes of replies for AS 4 would be seen by $k+3$ systems as they traveled from the backbone. Placing a pebble at AS 4 will satisfy its own 600 byte demand locally. If that were the only pebble placed, the other 900 bytes of demand would escape and their cost would be $(500 (k+1) + 400 (k+3))$. So, the total cost of the AS 3 subtree given only a single pebble (and placing it at AS 4) is $600 + (1700 + 900 k)$.

For any vertex $v$ of the tree $T$, denote the subtree rooted at $v$ by $T_v$. For $k \ge 0$ we consider a tadpole graph $(T,k)$ defined as $T$ appended by a single path extending upwards from the root of $T$ with $k$ extra vertices. Traffic is said to escape if the request and reply need to traverse the $k$ vertices in the tail. The cost of a tadpole graph $(T,k)$ is the cost of the subtree traffic plus $k$ times the cost of the traffic that escapes.

From the point of view of AS 3, the cost of the traffic he represents will be different depending on how many pebbles he is allowed to use. We will use $\ell$ to represent the number of pebbles available. If $\ell = 0$, he can place 0 pebbles and his cost is $0 + (3500 + 1500 k)$. If he can place $\ell = 4$ pebbles, the cost of his subtree is $1500$, although in this case, the pebble placed at AS 5 is not valuable.

An interesting problem lies in comparing the options AS 3 has if we offer him only 1 pebble. At $k = 0, \ell = 1$, AS 3 should place the pebble at AS 4 for a total cost of $2300$. But at $k = 100$, AS 3 would choose to put his only pebble on AS 3 for a total cost of $3500$. Clearly, cost is not a simple function of $k$.

The reader may want to test his understanding by optimizing the cost of AS 3's subtree at $k=0$ if we offer him 2 pebbles. The node can choose to keep one for himself and let his children use one, or he can choose to let his children use both.

Proof: s s' x x' a