Greedy Placement

Figure 5 also shows the results of a greedy placement algorithm that incrementally places the each cache at the hottest remaining site in the tree. Two greedy algorithms were attempted with very similar results. Assume $p$ caches have already been placed. Incremental placement is accomplished for the $(p + 1)$ cache by pre-defining locations for the prior $p$ pebbles. The algorithm is then run with only one pebble allocated to the entire Internet. In fact, figure 5 shows an even simpler algorithm to determine the placement of a single, new cache. It chooses the uncached AS with the highest local demand. We were surprised to see how well the greedy algorithms performed and how closely their performance matched each other. The greedy algorithm reduced the total traffic below 7 Gigabyte-ASHops by using the 10 AS's with the highest local demand. In fact, the first 11 locations chosen by the greedy algorithm matched the first 11 locations chosen by the simultaneous placement algorithm (albeit in a different order).

Moreover, these incremental placement algorithms (random and greedy) more closely model the financial reality that moving a cache from one location to another is typically not economic.