## 4 Cache-Supported ICN Router
### Implementation
#### 4.2.3 Cache Element  
In the cache element, we employed a small but fast DRAM (Layer 1) combined with multiple large but slow SSDs (Layer 2) to construct a hierarchical cache structure that has been proven to be an effective method to extend the cache capacity of an ICN router to the terabyte scale [27]. Dual Queue Management of DRAM  
We implemented a chunk assemble submodule in the assemble core. In addition to assembling chunks, it also serves as the L1 cache of the router and manages the L1 and L2 cache indexes. Considering the inevitable delay of assembling chunk, we employed dual queues of first input first output (FIFO) and LRU to manage chunks for leveraging the L1 cache space and efficiently assembling space (as shown in Figure 1). The FIFO queue manages the chunks being assembled, and the LRU queue manages the chunks that have assembled and evicted from the FIFO queue. When the FIFO queue is full, the chunk that started assembling first are deleted, no matter whether they were successfully assembled or not, because we believe that the time an incomplete chunk lives in FIFO is sufficient for assembling. Optimal Chunk Assembling  
The same chunk may be simultaneously transmitted by multiple sources on same path in the network. Hence, packets of the same chunk may reach the router out of order, and the length of each payload packet is not uniform due to the different MTU size settings. To reduce the delay of chunk assembling, we built an optimal scheme in which packets with the same name are put into the same memory area for chunk assembling. In other word, the same chunk from different sources can be assembled at the same time. To settle the performance problem caused by the frequent dynamic memory allocation, we allocated a large amount of assembling space that is equal to the chunk size in advance. The Assemble cores decapsulate the payload from the primitive packet and put it in assembling space based on payload size and start-offset field in the ICN header, which is a necessary field we should add in ICN header. This process is managed by a double linked list. When a linked list is created, an initial node that records the starting and ending addresses of the assembling memory space is created. A new node is created when the payload of the received packet is filled into the assembling space. Immediately, both nodes are updated to record the starting and ending addresses of two memory spaces separated by payload. Figure 5 shows four situations that will be encountered during assembling in a pre-malloc memory space. The shaded portion indicates that this space has been filled with data. Figure 5: The four situations in process of assembling. Situation 1: Some part of this space that the payload should fill is occupied. Situation 2: The space that the payload should fill has already been occupied completely. Situation 3: Both the space that the payload should fill and the adjacent space are free. Situation 4: The space that the payload should fill is after an ending, before the starting of occupied data, or in the middle exactly. Algorithm 1 shows the details how an optimal algorithm of the chunk assembling works. Only if there is only one node left in the linked list and the starting and ending addresses of this node are equal to the addresses of the assembling memory space, a chunk has been assembled completely. This method can improve router memory utilization and the success probability of chunk assembling, especially for popular contents. ```
1. Offset \(\leftarrow\) ReturnPacketOffset(Packet)
2. Len \(\leftarrow\) ReturnPayloadLen(Packet)
3. EID \(\leftarrow\) ReturnChunkED(Packet)
4. ifEID not in the ITthen
5. Create Double linked list
6. Copy packet payload from Offset to Offset + Len
7. Node_count \(\leftarrow\) 1
8. endif
9. ifEID in the ITthen
10. ifChunkAssemblingDone(EID)then
11. Drop Packet
12. else
13. fori = 0 to Node_count do
14. ifsituation 1 then
15. Copy packet payload from EndingAddress(Node[i]) to Offset + Len
16. UpdateNode(Node[i],Offset + Len)
17. endif
18. ifsituation 2 then
19.