Varying Outgoing Update Capacity

Our experiments thus far show that CUP outperforms PCX under conditions where all nodes have full outgoing update capacity. A node with full outgoing capacity is a node that can and does propagate all updates for which there are interested neighbors. In reality, an individual node's outgoing capacity will vary with its workload, network connectivity, and willingness to propagate updates. In this section we study the effect on CUP performance of reducing the outgoing update capacity of nodes.

We present an experiment run on a network of 1024 nodes. In this experiment, after a five minute warm up period, we randomly select twenty percent of the nodes and reduce their outgoing capacity to a fraction of their full capacity. These nodes operate at reduced capacity for ten minutes after which they return to full capacity. After another five minutes for stabilization, we randomly select another set of twenty percent of the nodes and reduce their capacity for ten minutes. We proceed this way for the entire 3000 seconds during which queries are posted, so capacity loss occurs three times during the simulation.

Figure 5 shows the ratio of CUP total cost to PCX total cost versus capacity $c$ for this experiment and for four different Poisson query rates $\lambda$. The capacity $c$ ranges from 0, implying that no updates are propagated, to 1, where nodes have full outgoing capacity. $c=.25$ means that a node is only capable/willing of pushing out one-fourth the updates it receives.

Note that even when one fifth of the nodes do not propagate any updates, the total cost incurred by CUP is about half that of PCX. As the outgoing capacity increases, the total cost decreases smoothly until $c = 1$ where CUP achieves its full potential. A key observation from these experiments is that CUP's performance degrades gracefully as the capacity $c$ decreases. This is because reduction in update propagation also results in reduction of its associated overhead. Therefore, the capacity reduction should be seen as a missed opportunity for higher returns rather than as an overall loss. Clearly though, CUP achieves its full potential when all nodes have maximum propagation capacity.

Figure 5: Total cost ratio vs. update propagation capacity

Table: Per-Key, Per-Query Rate Comparison of CUP with PCX for Pareto arrivals.

Average Rate (q/s)	1	1	10	10	100	100	1000	1000
Pareto rate (a)	1.25	1.1	1.25	1.1	1.25	1.1	1.25	1.1
CUP/PCX MissCost	0.24	0.14	0.08	0.07	0.07	0.09	0.08	0.08
PCX AvgLat ($\sigma$)	7.77 (9.28)	6.99 (9.43)	3.84 (8.41)	4.01 (8.75)	1.75 (5.88)	1.61 (5.53)	1.00 (4.02)	1.10 (4.16)
CUP AvgLat ($\sigma$)	3.16 (5.75)	1.71 (4.44)	0.42 (3.03)	0.37 (2.80)	0.13 (1.66)	0.15 (1.71)	0.08 (1.17)	0.09 (1.24)
IR/CUPOvhd Hop	6.41	7.49	13.09	16.03	43.25	53.57	223.97	293.30