One of the principal motivations for content delivery networks, such as
those that have been deployed over the past three years, is to improve
performance from the perspective of the client.  Ideally, this is achieved
by placing caches close to groups of clients and then routing client
requests  to the nearest cache.  In the first part of this paper we present
a new method for identifying regions of client demand.  Our method uses
best path information from Border Gateway Protocol (BGP) routing tables to
create a hierarchical clustering of  autonomous systems (AS's).  The method
iteratively adds small clusters to larger clusters based on minimizing the
Hamming distance between the  neighbor sets of the clusters.  This method 
results in a forest of AS trees where we define each tree root
as an Internet backbone node.  This  forest representation of AS
connectivity is an idealization of the  Internet's true structure.  We test
for fidelity by comparing AS hop distances to the Internet backbone.  One
of the strengths of  our AS clustering method is that it naturally lends
itself to the cache  placement problem.  In the second part of this paper,
we present two cache  placement algorithms based on a tree graph of demand.
The algorithms  address the problems of placing single caches and multiple
caches so as to  minimize inter-AS traffic and client response time.  We
evaluate the effectiveness of our cache  placement algorithms using Web
server logs and show that they can  greatly improve performance over random
cache placement.