Coordinated Forwarding and Caching in Information-Centric Networks
draft-xie-icnrg-coordinated-caching-forwarding-00

Abstract

Content caching plays an important role in Information-Centric Networking (ICN). Many of current ICN designs adopt a limited, en-route hierarchical caching mechanism; additionally, caching and forwarding are largely uncoordinated in these designs. This draft describes a coordinated caching and forwarding design to improve content access cost and cache miss rate of ICN.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on October 13, 2013.

Copyright Notice

Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Table of Contents

• 1. Introduction
• 2. Coordinated Forwarding and Caching
• 3. Popularity Ranking Based Coordination
• 3.1. Popularity Ranking
• 3.2. Cost-Based Optimal Content Caching
• 3.3. An Example of Cost-based Optimal Coordination
• 4. Dealing with Inconsistent Popularity Ranking
• 4.1. Inconsistent Popularity Ranking
• 4.2. Dual-Segment Content Caching
• 4.3. Adaptive Content Store Division
• 4.4. Example: Dual-Segment Content Store Division
• 5. Conclusions
• 6. Contributors
• 7. Security Considerations
• 8. IANA Considerations
• 9. Informative References
• Authors' Addresses

1. Introduction

The concept of Information-Centric Networking (ICN) has emerged and become a significant part of the world-wide research efforts on Future Internet architectures. The principal paradigm of ICN is significantly different from the host-to-host communication model in the current Internet architecture. Instead, ICN focuses on information objects, their properties, and receiver interest in the network to achieve efficient and reliable distribution of such objects. In ICN, content caching is becoming an inherent capability of network elements such as routers. With routers being able to cache contents in ICN, it is likely that not only the content distribution costs incurred to the network but also the quality of service experienced by end users are significantly improved.

Without specifying the details of content caching, the existing ICN architectures are designed to allow flexible design and implementation of new caching schemes. However, they also pose new challenges to caching schemes; in particular, it remains unclear how content caching should be provisioned (independently or collaboratively), and how it should be implemented efficiently.

Many of current ICN designs adopt a hierarchical caching mechanism allowing only limited collaboration in content caching. More specifically, for a given content, caching in many ICN designs takes place only at en-route routers (i.e., routers on the paths between a requesting host and one or multiple content origins), and thus forms a hierarchical caching mechanism. An en-route router that has the requested content should directly respond with the content from its local content cache and suppress further forwarding the request to the next router in the routing hierarchy. For instance, Content-Centric Network (CCN) is an example of ICN; CCN adopts a name-based routing architecture, advocating a ``host-to-content'' communication model which differs from the ``host-to-host'' model in Internet. In CCN, where content comes from is no longer important to the requesting host. Additionally, not only en-route routers but also routers in the same administrative domain (particularly those nearby en-route routers) could have possibly cached a requested content. These observations suggest that collaborative caching beyond the current limited hierarchical mechanism is feasible and could be beneficial.

Collaborative caching has drawn much attention and some have become commercially successful since more than a decade ago. This leads us to believe that collaborative caching in ICN is a key to success in that the network performance could be significantly improved by letting routers collaborate with each other.

However, collaborative caching in ICN, if not well designed, could significantly increase the communication overhead. For instance, control messages exchanged among routers, as an example of such overhead, are necessary to enable collaborations. Such messages normally contain information about what contents are stored in a particular router; due to the enormously large number of distinct contents, such messages could consume a significant portion of the network bandwidth. Additionally, the extra latency of exchanging such messages may further slow down the collaborative decision making process and thus reduce the effectiveness. A naive approach to collaborative caching is to adopt a broadcast mechanism, i.e., each request is forwarded to all routers and only those with the requested content respond with the data. However, such an approach is too costly and inefficient.

A key challenge to collaborative caching in ICN is how to make routers know what contents are available from other collaborative routers in an economic and efficient manner. Furthermore, since routers have knowledge about such availability information, routers should leverage it when making forwarding decisions; namely, forwarding and caching could be coordinated and collaborative to further optimize the network performance.

We will go beyond the en-route caching model and propose a novel name-based distributed coordinated forwarding and caching design for ICN in this draft.

2. Coordinated Forwarding and Caching

A content router with coordinated forwarding and caching is illustrated in the following figure. A new component called the Availability Info Base (AIB for short), is introduced to coordinate forwarding and caching in content routers. AIB keeps track of content availability information. More specifically, AIB can be thought of as a table, where each entry has two columns, Name and RouterID, suggesting that a given named content is available from a router. Note that we require that each router in the network should have a name and routers' names are propagated through the network via intradomain routing protocol such as OSPF. As a result, routers' names are treated in the same way as content names and put in FIB.

For instance, the following figure shows an example of CCN content router architecture with coordinated forwarding and caching. The outbound face to reach Router R3 is face 3, and content /c/d is available from R3, as shown in the following figure.

+--------------------------------------------------------------------+
|         Content Store                 Forwarding Info Base         |
|          Name    Data              Name  Destination List   Face 0 |
|    +-->+-----+----+        +---> +-------+---------------+  +---+  |
|    |   |...  |... |        |     |  ...  |      ...      |  |   |---->  
|    |   |-----+----|        |     |-------+---------------|  |   |  |
|    |   |/a/b |    |        |     |  /e/f |       2       |  |   |〈----  
|    |   |-----+----|        |     |-------+---------------|  |   |  |
|    |   |...  |... |        |     |  ...  |      ...      |  +---+  |
|    |   +-----+----+        |     |-------+---------------|         |
|    |                       |     |   R3  |       3       |  Face 1 |
|    |                       |     |-------+---------------|  +---+  |
|    |                       |     |  ...  |      ...      |  |   |---->  
|    |                       |     +-------+---------------+  |   |  |
|    |           Index       |                                |   |〈----  
|    |          Ptr Type     |                                |   |  |
|    |        +---+-----+    |                                +---+  |
|    +--------| * |  CS |    |                                       |
|             |---+-----|    |                                       |
|    +--------| * | PIT |    |                                Face 2 |
|    |        |---+-----|    |                                +---+  |
|    |      +-| * | AIB |    |                                |   |---->  
|    |      | |---+-----|    |                                |   |  |
|    |      | | * | FIB |----+                                |   |〈----  
|    |      | +---+-----+                                     |   |  |
|    |      +------------------+                              +---+  |
|    |  Pending Interest Table |      Availability Info Base         |
|    |   Name  Requesting Faces|       Name      Router ID    Face 3 |
|    |   +----+-------------+  +--->+-------+---------------+ +---+  |
|    +-->|... |      ...    |       |  ...  |      ...      | |   |---->  
|        |----+-------------|       |-------+---------------| |   |  |
|        |/e/f|      0,1    |       |  /c/d |       R3      | |   |〈----  
|        |----+-------------|       |-------+---------------| |   |  |
|        |... |      ...    |       |  ...  |      ...      | +---+  |
|        +----+-------------+       +-------+---------------+        |
+--------------------------------------------------------------------+
Figure 1: Content router with coordinated forwarding and caching
			

Each content router periodically announces the pairwise link cost and coordinated forwarding/caching related metrics via OSPF or ISIS intradomain routing protocols. Each router also measures the ranking of incoming Interests, namely, examine the received Interests from the users, and generates its local ranking sequence of the most popular contents. Each router implements the coordinated forwarding and caching mechanism, namely, a distributed mechanism to make joint decisions for forwarding and caching. Additionally, each router measures the miss rate of the interests in order to further improve the caching/forwarding efficiency.

Upon receiving an Interest, a router first checks whether the content is available and fresh in its local CS.

• If yes, the router responds with the locally cached content.
• Otherwise, it looks up the Pending Interest Table (PIT), and either this Interest should not be forwarded if it is already pending in PIT, or it should be forwarded and PIT be updated accordingly. In the latter case, the router looks up AIB to check whether the content is available from other collaborative routers. If not, the Interest should be forwarded using the default policy in information-centric networks (e.g., look up the outbound face in FIB and forward to the designated face; if FIB lookup fails, use a broadcast-like approach to forward the Interest). Otherwise, the Interest should be forwarded to the designated collaborative router. In order to do so, the router needs to look up FIB to determine the outbound face to reach the designated router. Note that most likely retrieving contents from collaborative routers within an autonomous system saves a noticeable time than getting it from the origin, as the latter typically requires traversing multiple autonomous systems and multiple interdomain links.

3. Popularity Ranking Based Coordination

3.1. Popularity Ranking

To ease the description, we introduce the following notations. The network consists of N content routers. Each router i has a local Content Store (CS) that can cache up to Ci content objects (``contents'' for short). The maximum size of each content is u. It is a common practice that contents are chunked into pieces. Suppose that each piece fits one cache unit (i.e., the size of each piece is no greater than u). Then, the entire network can cache at most C*u of contents, where C = C1 + ... + CN. Users send requesting packets (e.g., Interest packets in CCN). We use a ranking sequence {r1, r2, ..., rC} to denote the most popular C contents, sorted in descending order of popularity. This ranking sequence can be measured in real time as routers receive Interests. All routers may not see the same distribution of content popularity, e.g., the ranking sequence {r1, r2, ..., rC} measured by different routers have a certain percentage of mismatches or shifts, refer to as the popularity inconsistency.

3.2. Cost-Based Optimal Content Caching

Each content router keeps track of the most popular C contents. The coordination should be provisioned in such a way that the contents should be optimally distributed (cached) by the N routers, whose sizes are C1, C2, ...,CN, so that the average content access cost can be minimized in the network. We denote by cost_i the cost of accessing a given content at router i. Without loss of generality, assume that after sorting, cost_1 ≤ cost_2 ≤ ... ≤ cost_N. Also, suppose the ranking sequence is {r1, r2, ...rC} in descending order of popularity. The optimal way to distributing (caching) contents (i.e., minimizes the average cost of accessing the most popular C contents in the network) is to let the more popular content be cached at a place that has a lower cost, i.e., router 1 caches r1, ..., rC1 , router 2 caches rC1+1, ..., rC1+C2, and so on (see Theorem 1 in [GXS12]).

An example of delay-based cost metric can be defined for CCN as follows. Let I_i denote the average number of interests received by router i and d_ij denotes the link cost of nodes i and j (d_ij becomes the cost of accessing content from the local Content Store when i = j). Such costs can correspond to either intradomain routing weights or other performance-related metrics such as distance and latency. Then, for any cache unit in router i, the average cost of accessing this content requested by users is cost_i = (I_1 * d_1i + ... + I_N * d_Ni) / (I_1 + ... + I_N).

There are many ways to obtain the cost information. For instance, with the help of intradomain routing protocol, topological information is generally available to each router; each router can calculate the average cost for all collaborative routers in the network and sort all routers using these values. For any cache unit in router, the average cost of accessing a content requested by users is the weighted sum of pair-wise access costs from all routers. Access costs can correspond to either intradomain routing weights or other performance-related metrics such as distance and latency. Then, the optimal solution that minimizes the average cost of accessing the most popular contents in the network is to let the more popular content be cached at a place that has a lower cost, and the less popular contents by the router with a larger cost. Therefore, for any top popular content, each router knows not only which contents it should keep in its local Content Store, but also which collaborative router it can request this content from, if not locally available. Such availability information for the top popular contents is stored in AIB.

3.3. An Example of Cost-based Optimal Coordination

The coordinated forwarding and caching design is illustrated using a simple example shown in the following figure. In the example, there are three coordinated routers R1, R2 and R3. These routers can cache 10 contents in total (the size of these three caches are 3, 4, and 3, respectively). The most popular 10 contents measured by these routers are consistent. Suppose cost_i is the average cost of accessing this content requested by users for any cache unit in router i, and cost_1 >= cost_2 >= cost3. The most popular 3 contents should be cached in router R3, the next 4 contents should be cached in R2, and the next 3 contents should be cached in R1. As shown in the figure, for any incoming Interest requesting for the most popular contents, AIB tells where it should be forwarded to (the content is either available from the router's local CS or other collaborative routers).

			.-------------------------------------.
			|	   Availability Info Base     |	
			|         .-------------------.       |	
			|    Name |a|b|c|d|e|f|g|h|i|j|	      |	
			| RouterID|3|3|3|2|2|2|2|1|1|1|	      |	
			|	  .------|-|-|-|------.	      |	
			|		 | | | |	      |	
			|		 | | | |      CS      |	
			|		 | | | |    +---+     |	
			|		 | | | ---->| g |     |
			|		 | | |      |---|     |	
			|		 | | ------>| h |     |	
			|		 | |	    |---|     |	
			|		 | -------->| e |     |	
			|		 |  	    |---|     |	
		------->|		 ---------->| d |     |	
		|	|	R2		    +---+     |	
		|	.-------------------------------------.
		|				^	
		V				|
.-------------------------------------.		|
|	   Availability Info Base     |		|
|         +-------------------+       |		|
|    Name |a|b|c|d|e|f|g|h|i|j|	      |		|
| RouterID|3|3|3|2|2|2|2|1|1|1|	      |		|
|	  +--------------|-|-|+	      |		|
|		         | | |	      |		|
|		  CS     | | |        |		|
|		 +---+   | | |        |		|
|		 | h |〈--  | |        |		|
|		 |---|     | |	      |		|
|		 | i |〈----| |        |		|
|		 |---|       |	      |		|
|		 | j |〈------|        |		|
|                |---+                |		|
|	R1		              |		|
.-------------------------------------.		|
		^				|
		|				V
		|	.-------------------------------------.
		|------>|	   Availability Info Base     |	
			|         +-------------------+       |	
			|    Name |a|b|c|d|e|f|g|h|i|j|	      |	
			| RouterID|3|3|3|2|2|2|2|1|1|1|	      |	
			|	  +|-|-|--------------+	      |	
			|	   | | |	              |	
			|	   | | |      CS              |	
			|	   | | |    +---+             |	
			|	   | | ---->| c |             |
			|	   | |      |---|             |	
			|	   | ------>| b |   	      |	
			|	   |	    |---|             |	
			|	   -------->| a |    	      |	
			|		    +---+    	      |	
			|	R3			      |	
			.-------------------------------------.
Figure 2: A design for coordinated forwarding and caching

			

4. Dealing with Inconsistent Popularity Ranking

In practice, popularity rankings seen by different routers are more likely inconsistent. In such cases, the efficiency of content forwarding and caching will be degraded. We describe a solution that leverages the dual-segment caching design to address the inconsistent popularity ranking problem.

4.1. Inconsistent Popularity Ranking

Inconsistency in popularity ranking happens when the ranking sequences of routers are slightly different from each other. Therefore, the knowledge of routers about the distribution of contents in the caches may be inaccurate. In this situation, when any Interest requesting comes for a content, AIB may tell a wrong destination where it should be forwarded to, resulting in cache misses and efficiency degradation.

We illustrate inconsistency in popularity ranking through an example shown in the following figure. In this example, router R2's ranking sequence is slightly different from R1's and R3's. In R2's ranking sequence, the positions of content h and f are swapped and content k replaces j. As a result, router R2 caches contents {d, e, h, g}; however, routers R1 and R3 expect that R2 caches {d, e, f, g} instead. Whenever R1 and R3 forward Interests for content f to R2, such Interests have to be further forwarded towards the origin by R2 (not shown in the figure). Similarly, R2 always forwards Interests for content f and k to R1, resulting in cache misses and further forwarding.

			.-------------------------------------.
			|	   Availability Info Base     |	
			|         .-------------------.       |	
			|    Name |a|b|c|d|e|h|g|f|i|k|	      |	
			| RouterID|3|3|3|2|2|2|2|1|1|1|	      |	
			|	  .------|-|-|-|------.	      |	
			|		 | | | |	      |	
			|		 | | | |      CS      |	
			|		 | | | |    +---+     |	
			|		 | | | ---->| g |     |
			|		 | | |      |---|     |	
			|		 | | ------>| h |     |	
			|		 | |	    |---|     |	
			|		 | -------->| e |     |	
			|		 |  	    |---|     |	
		------->|		 ---------->| d |     |	
		|	|	R2		    +---+     |	
		|	.-------------------------------------.
		|				^	
		|				|
		V				|
.-------------------------------------.		|
|	   Availability Info Base     |		|
|         +-------------------+       |		|
|    Name |a|b|c|d|e|f|g|h|i|j|	      |		|
| RouterID|3|3|3|2|2|2|2|1|1|1|	      |		|
|	  +--------------|-|-|+	      |		|
|		         | | |	      |		|
|		         | | |        |		|
|		 +---+   | | |        |		|
|		 | h |〈--  | |        |		|
|		 |---|     | |	      |		|
|		 | i |〈----| |        |		|
|		 |---|       |	      |		|
|		 | j |〈------|        |		|
|                |---+                |		|
|	R1		              |		|
.-------------------------------------.		|
		^				|
		|				|
		|				V
		|	.-------------------------------------.
		|------>|	   Availability Info Base     |	
			|         +-------------------+       |	
			|    Name |a|b|c|d|e|f|g|h|i|j|	      |	
			| RouterID|3|3|3|2|2|2|2|1|1|1|	      |	
			|	  +|-|-|--------------+	      |	
			|	   | | |	              |	
			|	   | | |      CS              |	
			|	   | | |    +---+             |	
			|	   | | ---->| c |             |
			|	   | |      |---|             |	
			|	   | ------>| b |   	      |	
			|	   |	    |---|             |	
			|	   -------->| a |    	      |	
			|		    +---+    	      |	
			|	R3			      |	
			.-------------------------------------.
Figure 3: An example of inconsistent ranking sequences
			

4.2. Dual-Segment Content Caching

To address the above problem resulted by inconsistent popularity, a dual-segment cache design can be adopted, namely, divide a router's Content Store into two segments:

• the Advertised Content Store (ACS for short), which is the regular collaborative cache that is operated the same way as described in the preceding subsection assuming consistent popularity;
• the Complementary Content Store (CCS for short), which is the cache space used for adapting to the inconsistency of popularity distribution.

The rationale behind this dual-segment design is to leverage CCS to absorb contents that are supposed to be store at a router but are missing in its ACS due to inconsistent popularity. Upon receiving an Interest, if the requested content is available locally, the router directly responds with the data. Otherwise, if the Interest comes from another collaborative router, the router forwards the Interest towards the content origin and stores the returned data into its Complementary Content Store when the data comes back; if the Interest comes from a requesting host directly, the router applies its knowledge of popularity-ranking sequence and checks whether the ranking of the requesting content is less than the cache capacity; If yes, it forwards the Interest to the collaborative router designated by the sequence; otherwise, it forwards the Interest towards the origin.

4.3. Adaptive Content Store Division

The impact of the preceding dual-segment design on the performance of coordinated forwarding and caching in content-centric networks could be subtle. On the one hand, a sufficiently large CCS is more favorable to adapt to the popularity inconsistency; and on the other hand, when the total size of the Content Store is fixed, a smaller CCS is more favorable, as the ACS could be larger to store more frequently requested contents in the network. Clearly there exist trade-offs when determining their sizes.

A straightforward solution is fixed division of ACS and CCS, e.g., 90% dedicated to ACS and the remaining to CCS. However, the problem of fixed division is one size does not fit all, namely, routers may experience different levels of popularity inconsistency, and a fixed size may either over-estimate or underestimate the inconsistency level, thus resulting an inefficient use of the cache space.

A distributed, self-adaptive scheme can be designed to address the above division problem; specifically, the division of ACS and CCS is adjusted based on the dynamics experienced by the content routers. The scheme is designed based on cache miss rate as the cache miss rate plays an important role in the efficiency of dual-segment collaborative caching. On the one hand, when the miss rate is low, it implies a potentially oversized CCS and thus a waste of cache space. On the other hand, when the miss rate is high, then contents supposed to be stored in a designated collaborative router are actually not stored in it, resulting in additional costs to forward Interests to the designated router and then towards the origin.

Below we describe an example algorithm for adaptively adjust the cache division. Define the Locking Miss Rate (LMR for short) to characterize the maximum miss rate (corresponding to a maximum level of popularity inconsistency) that a router would like to tolerate. Every router distributively adjusts its size of CCS to make its miss rate closely approach to LMR. More specifically, a router starts with a pre-configured initial cache division, e.g., 90% for the Advertised and 10% for CCS. It then begins measuring the cache miss rate for all Interests received from other collaborative routers. We denote the measured cache miss rate by MR. The example algorithm is as follows:

• If MR〈=LMR, it is likely that the router experiences less popularity inconsistency than expected, we may have an oversized CCS, so the size of CCS is halved so that we increase the size of ACS to cache more contents in the network.
• If MR>LMR, the popularity inconsistency is likely under-estimated; therefore we should reduce the size of ACS to have a larger CCS in order for accommodating the inconsistency. Usually, it will be better to reduce the size of ACS linearly comparing with reducing the size aggressively. For example, the size of ACS can be reduced to 1/(1+MR) of the orginal ACS size.

4.4. Example: Dual-Segment Content Store Division

An example of this design for router R2 in the previous example is shown in the following figures. With the single-segment design, content f, which is supposed to be cached in R2, is always missing due to the inconsistency of R2's ranking statistics. However, with the dual-segment design, R2 only advertise 3 as its cache size. As a result, an extra cache unit can be used to store the missing content f. Therefore, future Interests requesting for f forwarded from routers R1 and R3 can be fulfilled by R2.

.-----------------------------------.
|	   Availability Info Base   |	
|         .-------------------.     |	
|    Name |a|b|c|d|e|h|g|f|i|k|	    |	
| RouterID|3|3|3|2|2|2|2|1|1|1|	    |	
|	  .------|-|-|-|------.	    |	
|		 | | | |	    |	
|		 | | | |    CS      |	
|		 | | | |  .---.     |	
|		 | | | -->| g |     |
|		 | | |    |---|     |	
|		 | | ---->| h |     |	
|		 | |	  |---|     |	
|		 | ------>| e |     |	
|		 |  	  |---|     |	
|		 -------->| d |     |	
|	R2		  .---.     |	
.-----------------------------------.
        (a)Single segment




.------------------------------------.
|	   Availability Info Base    |	
|         .-------------------.      |	
|    Name |a|b|c|d|e|h|g|f|i|k|	     |	
| RouterID|3|3|3|2|2|2|2|1|1|1|	     |	
|	  .------|-|-|--------.	     |	
|		 | | |	     CS      |			      
|		 | | | .-----------. |
|		 | | | |  ACS  CCS | |	
|		 | | | |  .-.  .-. | |	
|		 | | --|->|h|  |f| | |	
|		 | |   |  |-|  .-. | |	
|		 | ----|->|e|      | |	
|		 |     |  |-|      | |	
|    R2		 ------|->|d|      | |		
|		       .-----------. |	
.------------------------------------.
        (b)Dual segment

Figure 4: An example of Content Store Division
			

5. Conclusions

In this draft, we describe a distributed, popularity-guided coordinated forwarding and caching design for information-centric networks, where we introduce an Availability Information Base to allow coordination between forwarding and caching in content routers. In order to deal with popularity inconsistency in realistic networks, we also describe a self-adaptive dual-segment cache division scheme. Simulation-based evaluations demonstrate that by coordinating forwarding and caching in ICN, content access cost and cache miss rate can be significantly improved.

6. Contributors

Guoqiang Wang
2330 Central Expy
Santa Clara
US

Email: gq.wang AT (huawei.com)

Xinwen Zhang
2330 Central Expy
Santa Clara
US

Email: xinwen.zhang AT (huawei.com)

Shuo Guo
University of Minnesota
Minneapolis, Minnesota 55455
USA

Email: sguo AT (umn.edu)

Guangyu Shi
Central Research Institute, Huawei Technologies
Shenzhen
China

Email: shiguangyu AT (huawei.com)

7. Security Considerations

Security issues are not discussed in this memo.

8. IANA Considerations

This document makes no specific request of IANA.

9. Informative References

Authors' Addresses