Emulab Experiment

Table II: Successful Queries for Emulab Experiment

	Completed queries
BW (MB/s)	No LB	k-Choices
.4	$4341$	5879 $(+35\%)$
1	$16672$	20217 $(+21\%)$
4	$24025$	29537 $(+23\%)$
40	$23331$	26224 $(+12\%)$
All	$68370$	81858 $(+20\%)$

To examine k-Choices's effect on a working system, we implemented it within Pastry and ran a query-and-download scenario. Our primary goal was to measure changes in throughput with k-Choices using a fairly large real topology. Our use of nearest-neighbor-based Pastry demonstrates that k-Choices generalizes beyond Chord semantics. We based our k-Choices implementation on FreePastry [15]. We ran k-Choices in passive mode with $\kappa=16$. We used 1 VS per node because FreePastry does not currently support multiple VSs. We were required to anticipate load based on namespace distances because low bandwidth nodes were unable to successfully join the network when queries were already taking place. For this same reason, queries were only for uniformly distributed destinations. If the destination responded, each node attempted to download an 8KB block. A query completed if both the query and download were successful.

We ran our experiment on Emulab, a testbed for networking research that supports precise bandwidth tuning [44]. The topology consisted of 256 nodes. There were 64 nodes of each bandwidth level; the levels were 40Mb/s, 4Mb/s, 1Mb/s, and $0.4$Mb/s. Although Emulab has been working on making their system more scalable to support larger experiments, at the time, this was the largest topology we could run. Table II shows the total number of queries completed by bandwidth type. Each value is averaged over two trials that consisted of one hour of queries. All nodes used one of the 40MB/s nodes as their bootstrap. As a result, they were frequently in other node's routing tables and had a higher message routing workload. This is why their completed queries are fewer than the 4MB/s nodes. As expected, the average number of hops was a just less than 2, with minimal variance. The main experimental result, however, is that a $20\%$ improvement in throughput confirms that k-Choices can have a substantial positive impact on performance in a heterogeneous topology while retaining the important security properties of verifiable IDs.