Cache-Aware Routing

Sustained growth in e-commerce, digital media, social networking and smartphone applications has led to the dominant use of the Internet as a distribution network. To meet the growing demand on content distribution in a fundamental way, a handful of innovative Information Centric Networking (ICN) architectures have been proposed. One common and distinctive feature of these architectures is to leverage built-in network caches to improve the transmission efficiency of content dissemination, which is known as in-network caching. As a building block of ICN architectures, in-network caching also brings about a series of problems. The default in-network caching policy is that each router caches any data packet passing by. It results in cache redundancy and unnecessarily frequent cache replacement on the path from the content source to the requester. Moreover, an ICN router is unaware of content cached in off-path routers. And thus such off-path cached content cannot be used and the caching in neighboring routers is not coordinated. Then in-network storage is utilized in an inefficient way. And therefore in-network caching policy in improving caching performance has recently received much attention from the ICN community.Although caching theories and techniques to optimize traditional Web caching and CDN caching have already been well-studied, new characteristics of in-network caching - transparency, ubiquity, and fine-granularity, have made such caching theories and optimization techniques unable to be directly and seamlessly ported into in-network caching. Existing works on in-network caching are almost about content placement without consideration of cached content location. To utilize in-network caches in an efficient way, it is crucial to make temporarily cached content to be visible in its vicinity. Reasonable cached content location improves the visibility of content in off-path routers, avoids redundant content placement and offers the opportunity for routers to cooperate in content placement. In consideration of the ubiquity of in-network caching and high volatility of cached content, this paper moderately introduces cache-awareness into routing to enable cached content location, and then designs low complexity in-network caching policies based on cache-aware routing to reduce cache redundancy, improve the availability of cached content and the efficiency of cache space usage and reduce users’ cost in content requests. Taking NDN (Named Data Networking), a large effort that exemplifies ICN, as the research background, the main research work and innovations are as follows:1. Existing on-path caching schemes lead to cache redundancy and unnecessary cache replacement. To address this issue, an opportunistic on-path caching policy is proposed (OPPORTUNISTIC). Without cache-aware routing, OPPORTUNISTIC enables on-path routers to selectively cache locally popular content and content that is far away to fetch. Such discriminate caching reduces unnecessary cache replacement. Meanwhile, due to request aggregation feature and cache filtering effect, each router has different views of content popularity distribution. Plus, each router is located differently in the network. And therefore, routers are likely to cache different content items and the reduce cache redundancy.2. If cached content is located merely by its resident router, routers cannot use content cached in off-path routers and may cache redundant content. To address this issue, an in-network caching policy that couples content placement, replacement and location is proposed (PRL). PRL supports cache-aware routing to enable routers to locate content temporarily cached in neighboring off-path routers, which improves the availability of cached content. With such awareness of cached content, content placement and replacement and the responses to users’requests in PRL take into account the availability of temporarily cached content in neighboring off-path routers. Then cache redundancy and unnecessary cache replacement is reduced, in-network storage resource is efficiently used and the performance of content dissemination is improved.3. The transparency, ubiquity, and fine-granularity of in-network caching invalidates the employ of traditional complex collaborative caching schemes in a centralized ways to in-network cooperative caching of relatively stable cached content. To address this issue, a distributed in-network cooperative caching scheme is proposed (DICC). DICC addresses the in-network cooperative caching in a distributed way. It first formalizes the in-network cooperative caching problem into a constrained optimization problem, and then applies the Lagrangian relaxation and primal-dual decomposition method to decompose the optimization problem into content placement subproblems and content locating subproblems, each of which can be solved in a distributed manner at each router. Cache-aware routing offers the solution for content placement subproblems to all routers so that they each can solve local object locating subproblems. DICC enables routers to share cached content and coordinate in caching relatively stable cached content with moderate communication cost.4. ICN ASes (Autonomous Systems) are enabled with in-network caching capability and each AS aims at its own access cost reduction by fetching data from its local cache or from neighboring ASes. Cooperative in-network caching among ASes is difficult to achieve. To address this issue, ASes are abstracted into autonomous caches and a caching scheme for cooperative in-network caching among autonomous caches is developed (NSCC). NSCC addresses the problem in a game theory way. It defines an Iterative Best Response (IBR) for autonomous caches to identify a global content object placement that benefits each cache as compared to that when they operate in isolation. During an iteration of IBR, each cache decides its best response to its caching based on its local request rate information, its access costs to other caches and the residual content placement at other caches. NSCC promotes autonomous caches to join such cooperation in in-network caching.5. A technical implementation model of NSCC in NDN is proposed. This model offers the system design of the five functions that are required for implementing NSCC, the collecting of request rate information, the synchronization among NSCC nodes, determining content placement, content caching and error event detection. The correctness of system design is validated by CCNx library that implements the basic idea of NDN.