Cost Model

Consider a node N within spanning tree S(A,K) that is at distance $D$ from A. We define the cost per query for K at N as the number of hops in the peer-to-peer network that must be traversed to return an answer to N. When a query for K is posted at N for the first time, it travels toward A. If none of the nodes between N and A have a fresh response cached, the cost of the query at N is $2 D$: $D$ hops up and $D$ hops for the response to travel down. If a node on the query path has a fresh answer cached, the cost is less than $2 D$. Subsequent queries for K at N that occur within the lifetime of the entries now cached at N have a cost of zero. As a result, caching at intermediate nodes can significantly lower average query latency.

We can gauge the performance of CUP by calculating the percentage of updates CUP propagates that are ``justified'', i.e., those whose cost is recovered by a subsequent query. Updates for popular keys are likely to be justified more often than updates for less popular keys.

A refresh update is justified if a query arrives sometime between the previous expiration of the cached entry and the new expiration time supplied by the refresh update. An append update is justified if at least one query arrives between the time the append is performed and the time of its expiration. Finally, a deletion update is justified if at least one query arrives between the time the deletion is performed and the expiration time of the entry to be deleted.

For each update, let $T$ be the critical time interval described above during which a query must arrive in order for the update to be justified. Consider a node N at distance D from A in R(A,K). An update propagated down to N is justified if at least one query is posted within $T$ time units at any of the nodes of the spanning subtree S(N,K). For example, if we assume a Poisson query arrival rate $\lambda$ of one query per second at nodes in S(N,K) and $T=6$, then the probability that an update arriving at N is justified is $1 - e^{-\lambda T} = 1 - e^{-1*6} = .99$.

The benefit of a justified CUP update goes beyond just recovery of its cost. For each hop a justified update $u$ is pushed down to the root N of subtree S(N,K), exactly one hop is saved since without $u$'s propagation, entries in all nodes of S(N,K) will expire and the first subsequent query landing at a node $N_i$ in S(N,K) within $T$ time units will cause two hops, from N to its parent and back. This halves the number of hops traveled between N and its parent which in turn reduces query latency. In fact all subsequent queries posted somewhere in S(N,K) within $T$ time units will benefit from N receiving $u$. The cumulative benefit an update $u$ brings to subtree S(N,K) increases when N is closer to the authority node since there is a higher probability that queries will be posted within S(N,K). We define ``investment return'' as the cumulative savings in hops achieved by pushing a justified update to node N. The experiments show that the return is large even when CUP's reduction in latency is modest and is substantially large when the latency reduction is high.

Table: Total cost per key per query rate for varying cut-off policies.

Policy	1 q/s Total Cost	10 q/s Total Cost	100 q/s Total Cost	1000 q/s Total Cost
PCX	61568 (1.00)	154502 (1.00)	476420 (1.00)	2296869 (1.00)
Linear, $\alpha = 0.25$	55475 (0.90)	72022 (0.47)	49341 (0.10)	196650 (0.09)
Linear, $\alpha = 0.10$	41281 (0.67)	34311 (0.22)	47132 (0.10)	196650 (0.09)
Logarithmic, $\alpha = 0.5$	31658 (0.51)	27311 (0.18)	47785 (0.10)	196797 (0.09)
Logarithmic, $\alpha = 0.25$	30683 (0.50)	24695 (0.16)	48330 (0.10)	196797 (0.09)
Second-chance	16958 (0.28)	23702 (0.15)	48330 (0.10)	196797 (0.09)
Optimal push level	15746 (0.26)	23696 (0.15)	45325 (0.095)	153309 (0.07)