Design space of ICN caching
Authors believe that the design space of ICN caching can be divided into 2 orthotropic parts:
- Caching strategy: how to properly place each content item in each router’s Content Store.
- Content discovery: for a router, how to know that there is a content item in the nearby routers.
Since caching strategy is a well-known topic, authors focus on Content discovery in this paper.
Current content discovery methods:
- Basic NDN/ICN: opportunistic content discovery.
content is searched opportunistically along the shortest path (or a designated path) towards a content origin. This approach has a very limited search scope (only the nodes along a path) and thus limited gain, but does not require coordination or communication among the nodes.
Drawbacks: Little gain but low overhead.
- off-path resolution-based routing.
The resolution table can be maintained either in a distributed manner, in which case a signaling protocol is required, or in a centralized manner as in a Name Resolution Service (NRS), in which case a registration/update communication is required.
Drawbacks: Much gain but high overhead (communication or storage overhead)
- coordinated content discovery.
- Flooding request to nearby routers.
Drawbacks: Much gain but high overhead (communication or storage overhead)
- Hashing based content discovery. Each router in the network is assigned a part of the hash space and caches the content items whose hashed identifiers fall within that space. This way, hash-routing avoids all the complex request-to-cache resolution steps of similar proposals and minimizes the corresponding signaling overhead.
Drawbacks: None. (Authors believes it is a good method)
- Breadcrumbs liked content discovery
Form a trace towards the end user. Interests can follow the trace to find the content item. (Previous works of the authors)
Conclusion:
Methods with low overhead has little gain, while methods with much gain cause high overhead.
So in this paper, authors present a content discovery mechanism with low overhead but has much gain. This work can be considered as an improvement of Breadcrumbs liked content discovery.
Main idea of this work:
Form a trace towards the router who decide to cache the content item. (Traces are recorded in EFIB, a data structure similar to FIB) So when receiving a request, a router can forward the request according the entry in FIB or EFIB.
Forwarding strategy:
- Multicast: suppose an content name matches N entries in FIB and EFIB, sending N requests simultaneously and forward to these N destinations.
- Stop and wait: suppose an content name matches N entries in FIB and EFIB, sending N requests one by one. If router send a request to the ith destination and does not receive the data packet in t time, the router send the next request to the (i+1)th destination.
- Budget based forwarding strategy: when the request is generated, it is given a budget. Forwarding request by one hop need some cost. Generating an off-path request also need some cost. So the bandwidth resources for a single data content retrieval process has a upper limitation.
Objective function:
Max{\sum {Alpha*Discovery_rate + beta * latency + gama * overhead}}
Discovery_rate = 1 – server load
Latency is calculated by hops.
Overhead is calculated by interest hops. (different from latency because this paper presents a multicast method, so interest hops can be much greater than latency)
Cache size and caching strategy are given (constants).
Some thoughts about this paper:
- Although this paper focus on a well-studied topic and has limited contribution, it is well-written and many detailed issues are considered.