A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. CLASSICAL CONTENT CHARACTERISTICS <s> The notion of self-similarity has been shown to apply to wide-area and local-area network traffic. We show evidence that the subset of network traffic that is due to World Wide Web (WWW) transfers can show characteristics that are consistent with self-similarity, and we present a hypothesized explanation for that self-similarity. Using a set of traces of actual user executions of NCSA Mosaic, we examine the dependence structure of WWW traffic. First, we show evidence that WWW traffic exhibits behavior that is consistent with self-similar traffic models. Then we show that the self-similarity in such traffic can be explained based on the underlying distributions of WWW document sizes, the effects of caching and user preference in file transfer, the effect of user "think time", and the superimposition of many such transfers in a local-area network. To do this, we rely on empirically measured distributions both from client traces and from data independently collected at WWW servers. <s> BIB001 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. CLASSICAL CONTENT CHARACTERISTICS <s> This paper addresses two unresolved issues about Web caching. The first issue is whether Web requests from a fixed user community are distributed according to Zipf's (1929) law. The second issue relates to a number of studies on the characteristics of Web proxy traces, which have shown that the hit-ratios and temporal locality of the traces exhibit certain asymptotic properties that are uniform across the different sets of the traces. In particular, the question is whether these properties are inherent to Web accesses or whether they are simply an artifact of the traces. An answer to these unresolved issues will facilitate both Web cache resource planning and cache hierarchy design. We show that the answers to the two questions are related. We first investigate the page request distribution seen by Web proxy caches using traces from a variety of sources. We find that the distribution does not follow Zipf's law precisely, but instead follows a Zipf-like distribution with the exponent varying from trace to trace. Furthermore, we find that there is only (i) a weak correlation between the access frequency of a Web page and its size and (ii) a weak correlation between access frequency and its rate of change. We then consider a simple model where the Web accesses are independent and the reference probability of the documents follows a Zipf-like distribution. We find that the model yields asymptotic behaviour that are consistent with the experimental observations, suggesting that the various observed properties of hit-ratios and temporal locality are indeed inherent to Web accesses observed by proxies. Finally, we revisit Web cache replacement algorithms and show that the algorithm that is suggested by this simple model performs best on real trace data. The results indicate that while page requests do indeed reveal short-term correlations and other structures, a simple model for an independent request stream following a Zipf-like distribution is sufficient to capture certain asymptotic properties observed at Web proxies. <s> BIB002 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. CLASSICAL CONTENT CHARACTERISTICS <s> In this paper, we study the dynamics of the MSNBC news site, one of the busiest Web sites in the Internet today. Unlike many other efforts that have analyzed client accesses as seen by proxies, we focus on the server end. We analyze the dynamics of both the server content and client accesses made to the server. The former considers the content creation and modification process while the latter considers page popularity and locality in client accesses. Some of our key results are: (a) files tend to change little when they are modified, (b) a small set of files tends to get modified repeatedly, (c) file popularity follows a Zipf-like distribution with a parameter &agr that is much larger than reported in previous, proxy-based studies, and (d) there is significant temporal stability in file popularity but not much stability in the domains from which clients access the popular content. We discuss the implications of these findings for techniques such as Web caching (including cache consistency algorithms), and prefetching or server-based ``push'' of Web content. <s> BIB003 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. CLASSICAL CONTENT CHARACTERISTICS <s> Requests for dynamic and personalized content increasingly dominate current-day Internet traffic; however, traditional caching architectures are not well-suited to cache such content. Several recently proposed techniques, which exploit reuse at the sub-document level, promise to address this shortcoming, but require a better understanding of the workloads seen on web sites that serve such content. In this paper, we study the characteristics of a medium-sized personalized web site, NYUHome, which is a customizable portal used by approximately 44,000 users from the New York University community. Our study leverages detailed server-side traces of client activity over a two-week period in February 2002, obtained by instrumenting the NYUHome server. The paper presents statistics on document composition, personalization behavior, server-side overheads, and client-perceived request latencies. We then use these statistics to derive general implications for efficient caching and edge generation of dynamic content in the context of our ongoing CONCA project. Our study verifies both the need for and likely benefit from caching content at sub-document granularity, and points to additional opportunities for reducing client-perceived latency using prefetching, access prediction, and content transcoding. <s> BIB004 </s> A Survey on Content Placement Algorithms for Cloud-Based Content Delivery Networks <s> A. CLASSICAL CONTENT CHARACTERISTICS <s> Requests for dynamic and personalized content have increasingly become a significant part of Internet traffic, driven both by a growth in dynamic Web services and a "trickle-down" effect stemming from the effectiveness of caches and content-distribution networks at serving static content. To efficiently serve this trend, several server-side and cache-side techniques have recently been proposed. Although such techniques, which exploit different forms of reuse at the sub-document level, appear promising, a significant impediment to their widespread deployment is (1) the absence of good models describing characteristics of dynamic Web content and (2) the lack of effective synthetic content generators, which reduce the effort involved in verifying the effectiveness of a proposed solution.This paper addresses both of these shortcomings. Its primary contribution is a set of models that capture the characteristics of dynamic content both in terms of independent parameters such as the distributions of object sizes and their freshness, times, as well as derived parameters such as content reusability across time and linked documents. These models are derived from an analysis of the content from six representative news and e-commerce sites, using both size-based and level-based splitting techniques to infer document objects. A secondary contribution is a Java-based dynamic content emulator, which uses these models to generate edgeside include-based dynamic content and serve requests for whole documents as well as separate objects. <s> BIB005
An extensive analysis of static and dynamic content indicates that, though there are various content characteristics that are dependent on end-user behavior in the long-term, there are some that are independent of end-user behavior. There are two independent content characteristics required for describing content, size and freshness. The content size comprises of the size of metadata and encoded media stored on the surrogate servers. Content freshness is the interval between updates for content. Other characteristics of content that are typically dependent on end-user behavior include popularity, age, transmission times and spatial and temporal correlation. Fig. 7 illustrates a classification of content based on independent content characteristics. The size of static content is best captured by Pareto, a heavy tailed power law distribution  . Power law functions have shape parameters that can measure the skew in the data. They have heavy tails and large values along the x-axis that allows analysts VOLUME 6, 2018 to quantitatively study the data points, that otherwise would have been written off as outliers. In contrast, Gaussian normal distributions capture populations, which have 99.7% of the data within 3 times the standard deviation and the data outside these ranges is typically written off as outliers. The interval between updates of static content is modeled by Weibull, a variant of Exponential functions  , to capture very short time intervals (within few minutes to a day) between content updates BIB003 . Similarly, dynamic content is decomposed into coarse documents and finer objects. At the document level, the content sizes are best captured by Weibull distribution BIB004 , whereas Exponential functions best characterize the interval between updates  . The size of the objects in a document are found to be exponentially distributed BIB005 . The freshness time of these objects are best modeled by Weibull Distribution BIB005 . However, some objects in dynamic documents also exhibit bimodal characteristics BIB005 , requiring either no updates or continuous updates. Heavy-tailed distributions have been also shown to capture other independent content characteristics, such as the number of end-user requests  , transmission times  , idle times BIB001 and age of content  . Though transmission times are vulnerable to the underlying network traffic, it has been shown that they also follow a heavy-tailed distribution. Popularity is a major characteristic of content to be placed efficiently -i.e. it is popularity that ranks content. The rank is based on the number of end-user requests for content access. The popularity of content closely follows the discrete Zipf distribution such that static content that is not ranked highly can still generate end-user requests. The estimated time for the end-user requests to arrive is assumed to follow a Poisson process to capture the randomness and independence of the arrival of end-user requests. As a result, the interval time between end-user requests follows the Exponential distribution BIB004 . Though various characteristics of content are dependent on the end-user behavior, very few are correlated. For instance, there is negligible correlation between popularity, the content size and the update rate for static content BIB002 . The popularity of static content is uniformly distributed across hot servers BIB002 . However, objects in dynamic content exhibit temporal and spatial correlation BIB005 . This implies that there is a high probability of predicting future object requests based on the current object requests. And similarly, objects stored on the same physical server are more likely to be reused in a linked dynamic document than those stored on physically different servers.