Analysis of Similarity Caching on General Cache Networks

Analysis of Similarity Caching on General Cache Networks

... ABSTRACT Nowadays, content caching is essential to serve contents to users quickly and efficiently. In recent years, a technique to improve content caching, similarity caching, which focuses on the similarity among contents, has emerged. The feature of similarity caching is that a cache provides any content similar to a user's request even though the cache does not have the request itself, i.e., cache miss. In the literature, the effectiveness of similarity caching is investigated mainly through system-level metrics such as the cache hit ratio. However, its effectiveness from the point of view of users remains hardly understood despite its importance. Therefore, we try to quantify the user-level performance of similarity caching while focusing on a general cache network comprised of multiple cache nodes. To this aim, we introduce a user-oriented metric called similar-content delivery delay and analytically derive that; we also analyze the relation between the delivery delay observed by a user and the utility of the content similarity through several numerical evaluation. Our key findings are summarized as follows; (i) the effectiveness of similarity caching is dominated by the similarity which is acceptable to users; (ii) the effectiveness is also dependent on the location of users, i.e., distance to a contents server.

... INDEX TERMS Content distribution networks, information-centric networking, mathematical analysis, quality of service.

I. INTRODUCTION

WITH the continuous growth of content space, a way to flexibly resolve user's content requests, similarity searching, is expected to be one of promising approaches. Similarity searching is a technique to, from the large-scale content space, find contents that have similarity which is defined according to a given criteria. Its effectiveness stems from the fact that if a user can retrieve similar content instead of what the user actually wants, the user can gain a certain level of satisfaction.

At the same time, to efficiently deliver content to users, we have devoted significant effort to design cache networks which utilize content caching. Prominent architectures of the cache network are CDN (Content Delivery Network), MEC (Mobile Edge Computing), and CCN (Content-Centric Networking)/NDN (Named Data Networking). As we know, CDN distributes content from cache servers scattered around the world. MEC utilizes caches located at the edge of a network, e.g., access points; thus, users can acquire content from nearby caches. In contrast, CCN/NDN is a cache network comprised of routers equipped with a cache, which enables us to retrieve content from everywhere. Although CCN/NDN is a future network architecture, effort has been made. The benefit gained by these cache networks are, for instance, to reduce traffic transferred through a network and to shorten the content delivery delay.

Alongside such developments, a caching technique which applies the concept of similarity searching to content caching, similarity caching, has been attracting attention in recent years. The fundamental difference of similarity caching from conventional content caching called exact caching is that a cache can provide content similar to a requested one. To explain this difference more specifically, we briefly describe the mechanisms of exact caching and similarity caching. In exact caching, when a request from a user arrives at a cache node, i.e., a node with a cache, this cache node performs as follows; (i) it checks whether to store the requested content or not; (ii) if so, i.e., cache hit, it immediately returns the content; otherwise, i.e., cache miss, it forwards the request to other nodes, e.g., a node which stores the original content. In contrast, similarity caching differs from exact caching in terms of the operation at cache miss; namely, when the cache node does not store a content exactly-matching the user's request, it looks up similar content within its own cache and responds with that instead of discovering the exact content. A representative application of similarity caching is, for instance, video streaming. In this context, videos with different bit rates can be thought of as similar contents. Hence, in a scene where a user requests video content, similarity caching allows a cache node to server a video with a bit rate different from what the user actually wants, as similar content. As a result, the user can more quickly start watching it.

Similarity caching offers flexibility for content caching, but it involves a trade-off between the communication quality observed by users and the content similarity. For a user who values the communication quality, it is preferable that similar content is quickly delivered from a nearby cache even if this content differs from what the user wants. On the other hand, for a user who prefers the exactness of content, it is attractive that the requested content itself is returned from a node such as an origin server rather than a nearby cache, even if it sacrifices the communication quality.

Therefore, the purpose of this paper is theoretical understanding of similarity caching, in particular, to clarify the relationship between communication quality and content similarity while focusing on a general cache network. From our viewpoint, the situation in which such a quantitative evaluation of similarity caching has hardly performed comes up in the complexity of cache networks. In fact, the communication quality and content similarity as observed by the user are affected by various factors, for instance, which caches in the network serve content and what similar content they serve. This motivates us to reveal this complicated interaction on the general network with similarity caching.

To this end, we introduce a user-oriented metric for similarity caching, similar-content delivery delay and analytically derive that on a general cache network. The definition of similar-content delivery delay is the time taken from when a user sends a content request to a network until when it initially retrieves any content satisfying a given threshold. Here, the threshold is corresponding to the minimum of content similarity that the user can accept. Through several numerical examples, we also analyze the property of similarity caching in a multi-stage cache network from the perspective of the similar-content delivery delay.

Among several applications of similarity caching such as recommender system and contextual advertising, our paper focuses on multi-media retrieval, especially, query-based retrieval. Namely, a user retrieves content by issuing a query. In this scenario, similarity caching becomes effective when a nearby cache stores similar content, even if it does not store the exact requested content, and when the user is satisfied with similar content provided in a short delay. This effectiveness arises from cases where, if a user requests a particular song, they might be satisfied with an arranged version of the song, as similar content, instead of the original.

The contributions of the present paper is summarized as follows.

· We introduce the similar-content delivery delay as a user-oriented metric for similarity caching and algebraically derive it on a general cache network.

· We provide an analytical framework for similarity caching. This enables us to optimize control parameters of similarity caching. For instance, our analysis can derive the similarity acceptable to a user if the user's allowable delay is given.

· We reveal the effectiveness of similarity caching from the perspective of similarity-content delivery delay. As a consequence, a summary our insights is that (i) the effectiveness of similarity caching is dominated by several factors, in particular, the similarity which is acceptable to users, and (ii) the location of users, i.e., distance to contents server, is also an important factor.

The remainder of this paper is organized as follows. Section two introduces previous works related to this paper. Section three describes our analytic model used in this paper and explains the derivation of similar-content delivery delay. Section four analyzes the property of similarity caching in a multi-stage cache network through numerical evaluation. Finally, Section five presents the summary of this paper and addresses future works.