It is important to highlight the role Content Distribution Networks (CDNs) play
in rapidly growing Internet topologies. They are responsible for serving the
lion's share of Internet content to the end users by replicating it from the
origin server and placing it to a caching server closer to them. Probably the
biggest issues CDNs have to deal with revolve around deciding which content
gets prefetched, in which surrogate/caching server it is placed and allocating
storage to each server in an efficient manner. We will focus on the content
selection/prefetching problem extending the work done by Sidiropoulos et al.
(World Wide Web Journal, vol. 11, 2008, pp. 39-70). Specifically, we are trying
to determine how their clustering algorithm can work in specific environments
in comparison with an approach used to solve the surveillance game in graphs as
discussed by Fomin et al(Proc. 6th Int’l Conf. on FUN with Algorithms, 2012,
pp.166-176)and Giroire et al. (Journal of Theoretical Computer Science, vol.
584, 2015, pp.131-143). Along the way, we provide another definition for
cluster cohesion that accounts for edge cases. Finally, we define an original
problem, which consists of partitioning a graph into a predefined amount of
disjoint clusters of optimal average cohesion.
surveillance number, densest subgraphs, Content Distribution Networks, graph partitioning, cluster cohesion