IEEE INFOCOM 20021Cache Placement Methods Based on Client DemandClusteringPaul Barford , Jin-Yi Cai, Jim GastAbstract— One of the principal motivations for content delivery net-works, such as those that have been deployed over the past three years,is to improve performance from the perspective of the client. Ideally, this isachieved by placing caches close to groups of clients and then routing clientrequests to the nearest cache. In the first part of this paper we present anew method for identifying regions of client demand. Our method uses bestpath information from Border Gateway Protocol (BGP) routing tables tocreate a hierarchical clustering of autonomous systems (AS’s). The methoditeratively adds small clusters to larger clusters based on minimizing theHamming distance between the neighbor sets of the clusters. This methodresults in a forest of AS trees where we define each tree root as an Internetbackbone node. This forest representation of AS connectivity is an ideal-ization of the Internet’s true structure. We test for fidelity by comparingAS hop distances to the Internet backbone. One of the strengths of ourAS clustering method is that it naturally lends itself to the cache placementproblem. In the second part of this paper, we present two cache placementalgorithms based on a tree graph of demand. The algorithms address theproblems of placing single caches and multiple caches so as to minimizeinter-AS traffic and client response time. We evaluate the effectiveness ofour cache placement algorithms using Web server logs and show that theycan greatly improve performance over random cache placement.Keywords—Cache Placement, Hierarchical Clustering, Demand Analy-sisI. INTRODUCTIONContent Delivery Networks (CDNs) distribute caches in theInternet as a means for reducing load on Web servers, reducingnetwork load for Internet Service Providers (ISPs) and improv-ing performance for clients. In order to effectively deploy andmanage cache and network resources, CDNs must be able to ac-curately identify areas of client demand. One means for doingthis is by clustering clients that are topologically close to eachother, and then placing caches in the areas where demandis typ-ically large. This raises two immediate questions: how can clus-ters of clients be generated and once identified, how can cachesbe placed among the clusters so as to maximize their impact?In this paper, we address the question of client clustering bypresenting a new method that generates a hierarchy of clientclusters. As opposed to recent work on IP client clustering de-scribed in [1], our method uses autonomous systems (AS’s) asthe basic cluster unit. We argue that clustering at the IP levelresults in cluster units which are too detailed, and too numerousandthusdonotreadilylendthemselvestohigherlevelsofaggre-gation. In contrast, clustering at the AS level provides a naturalmeans for not only identifying clients which should experiencesimilar performancefrom a given cache but also for aggregatingAS’s into larger groups which should experience similar perfor-mance.Our interest in the ability to aggregate AS’s stems from thePaul Barford, University of Wisconsin - Madison. E-mail:pb@cs.wisc.eduJin-Yi Cai, University of Wisconsin - Madison. E-Mail:jyc@cs.wisc.edu. Re-search supported in part by NSF CCR9820806 and a Guggenheim FellowshipJim Gast, University of Wisconsin - Madison. E-Mail: jgast@cs.wisc.edu.Research supported by the Anthony C. Klug fellowship in Computer Sciencedesire to clearly understand demandand to effectivelydistributecaches. Our clustering method enables groups of AS’s to becoalesced into larger groups based on best path connectivity ex-tracted from BGP routing tables. We use best paths becausethese are typically the preferred route between an AS and itsimmediate neighbors. The difficulty is that best paths do not in-dicate anythingabout quality of a connectionbeyondimmediateneighbors.We address this problem by introducing notion of Hammingdistance between a pair of connected AS’s.tance was introduced in [2] as the minimum number of ele-ments which must be changed to move from one string to an-other. For example, the Hamming distance between {1,3,5,7}and {1,2,3,4} is four because {2,4,5,7} appear in one but notboth of the sets. In our context, Hamming distance is appliedas a measure of similarity of AS connectivity. Specifically, twonodes with a short Hamming distance indicate that they havemany neighborsin commonand are thus candidates formerginginto a cluster.Our clustering algorithm removes edges from the AS graphuntil all that remains in a forest of trees. The benefits of mak-ing a forest are: (1) objectively identifying a small number ofvertices that can be treated as the backbone of the Internet and(2) assigning each AS to one and only one tree so that tractablealgorithms can be used to predict the paths packets will take go-ing to or coming from the backbone. It is implicitly assumedthat the backbone vertices are tightly interconnected (ideally, aclique) and that packet transfers between backbone vertices arevery fast.Our algorithm starts by coalescing nodes whose path to thebackboneis uncontested,formingsmall clusters of nodes whoseonly known path to the bulk of the Internet passes through acommon parent. In the BGP tables we examined, clusters wereseldom that obvious. In order to form larger clusters, the algo-rithm successively relaxes the Hamming distance requirementsfor clustering. If we relax the Hamming distance requirementstoo far we would eventually collapse the entire network to a treewith a single root node. Our intention, however, is to only col-lapse the topology to a size which readily enables evaluation ofdemand and facilitates our cache placement algorithms. The re-sult ofourclusteringalgorithmpresentedin this paperis a forestof 21 root AS trees. These root AS’s consist of many of the ma-jor ISPs such as BBNPlanet and AT&T, but also some smallerISPs such as LINX due to the nature of the algorithm. The rootAS’s connect on average with 7.29 other root AS’s indicatinga high level of connectivity between these nodes. The averageout-degree of the root AS’s (i.e.. the number of AS with whomthey peer) is 198 with a median of 97 indicating that the rootAS’s facilitate Internet access to a large number of other AS’s.It is also important that the forest minimizes that amount byHamming dis-
