# Efficient Coded-Block Delivery and Caching in Information-Centric Networking

Authors: Yan Liu; Jun Cai; Huimin Zhao; Shunzheng Yu; JianLiang Ruan; Hua Lu
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

Information-centric networking (ICN) provides request aggregation and caching strategies that can improve network performance by reducing content server loads and network traffic. Incorporating network coding into ICN can offer several benefits, but a consumer may receive the same coded block from multiple content routers since the coded block may be cached by any of the content routers on its forwarding path. In this paper, we introduce a request-specific coded-block scheme to avoid linear dependency of blocks that are utilizing in-network caching. Additionally, a non-cooperative coded caching and replacement strategy is designed to guarantee that the cached blocks can be reused. Our experimental results show that the proposed scheme has superior performance to conventional CCN and two network coding-based ICN schemes.


---

## Body

## 1. Introduction

Trends in recent years have shown that Internet users care more aboutwhat the content is rather than where the content is. Information-centric networking (ICN) [1] is a novel design for a future networking architecture that has been proposed as a promising alternative to the current Internet. In ICN, IP addresses are replaced by content names and content routers (CRs) are equipped with storage capabilities to cache the content passing through each router. Content is requested by Interest packets that are sent by the consumer. With in-network caching [2, 3], the content can be cached by multiple CRs, and any content router (CR) that contains the content that is being requested by the Interest can respond with a data packet, where both the Interest and the data are identified by the content name. Content-centric networking (CCN) has been shown to be a promising ICN architecture [4].Network coding proposed by Ahlswede et al. [5] has been proven to be helpful in several different network scenarios, including peer-to-peer (P2P) [6], content distribution networks (CDNs) [7], and wireless networks [8, 9]. Recently, several studies have shown that network coding can also offer benefits to ICN [10–21], as network coding can be employed in ICN to effectively utilize multiple paths and reduce the complexity of the cache coordination. However, due to the ICN caching strategy, the same coded block may be cached by multiple CRs on its forwarding path and provided to the same consumer at a later time in response to their multicast requests [22].In this case, the consumer will not be able to recover the content from the received coded blocks. Several solutions have been proposed to guarantee that all the coded blocks that are provided to the consumer are linearly independent of each other. In some centralized schemes [11, 15], central routers are used to ensure that content caching and routing strategies can provide independent blocks. In some distributed schemes [20, 21], information on the coded blocks which have already been received by the consumer must be carried by the Interest to retrieve linearly independent blocks. The CR can decide whether to respond to the Interest according to the information carried by the Interest. Therefore, several round trips will be required to obtain sufficient linearly independent coded blocks. In our previous work [23], the CRs only cached the original received blocks to guarantee that all the coded blocks provided to consumers were linearly independent. Any coded blocks generated and transferred were wasted.To increase the caching efficiency and reduce the cost of computation and communication induced by centralized schemes, we propose a request-specific coded-block (RSCB) scheme to reduce the transmission volume and download delay and ensure that only a single round trip is required for the consumer to retrieve sufficient linearly independent blocks. A non-cooperative coded caching and replacing strategy is then proposed to guarantee that any two coded blocks that are cached in a network will be linearly independent. It is assumed that chunk-based routing and traffic control schemes are in place. The contributions of this paper are as follows:(i)
We propose a special content delivery strategy to retrieve blocks from multiple CRs simultaneously. Each CR on the forwarding path will aggregate Interests received from multiple consumers for chunks of the same content, to eliminate duplicates. Interests received by a CR will be separated again and forwarded in different directions. A mechanism is proposed for the aggregation and separation of Interests for the chunks of content to guarantee that the minimum number of coded blocks will be requested and will be linearly independent.(ii)
An on-path non-cooperative coded caching mechanism is designed to guarantee that the cached blocks can be reused. Blocks received by a CR can be encoded and cached depending on pending Interests and the proposed caching strategy.(iii)
In our model, only chunks (i.e., original blocks) and coded-from-original blocks can be cached. One coded-from-original block can satisfy multiple Interests sent by different consumers requesting a set of its component chunks. A chunk-level coding-instead-of-evicting cache replacement scheme is designed to effectively increase the caching efficiency and optimize cache capacity.(iv)
Our strategy is evaluated by comparison with conventional CCN and two network coding-based ICN strategies. Our experimental results demonstrate that the proposed strategy achieves the highest performance in terms of parameters such as average download time, server hit reduction rate, and cache hit rate.


## 2. Related Works

Network coding techniques have received much attention in a variety of network scenarios including P2P networks [6], CDNs [7], and wireless networks [9]. Recently, several works have been proposed that apply network coding in ICN. There are two categories of solutions that can be used to ensure consumers are provided with sufficient linearly independent coded blocks: centralized strategies and distributed strategies.Wang et al. [24] proposed a novel SDN-based framework to implement content caching and routing in ICN with linear network coding. The SDN controllers determine how to cache and route based on the information collected by the CR. Thus, a near-optimal caching and routing strategy can be obtained. Sadjadpour [11] proposed an architecture based on index coding for ICN, which groups the nodes into several clusters. The central router of each cluster maintains information on which content is cached by each node. Coded blocks generated by the central router are used to satisfy Interests for different content sent by different nodes. However, this strategy does not reduce traffic the first time content is requested. Llorca et al. [14] presented a multicast scheme based on network coding to achieve maximum network efficiency. However, the proposal does not mention a solution to deploy the proposed strategy in ICN. Talebifard et al. [15] proposed a method based on network coding that reduces the costs of coding and decoding by breaking the network into several clusters, with network coding only performed by selected nodes or clusters.As well as centralized strategies based on network coding, some works have obtained enough linearly independent coded blocks by sending Interests repeatedly. Zhang and Xu [21] proposed two checking strategies to guarantee that the consumer will receive sufficient linearly independent coded blocks, which were called precise matching and RB matching. In precise matching, each Interest carries the global coefficients X of the coded blocks that have already been received by the consumer. Each CR performs Gaussian elimination to check linear dependencies. Precise matching is an efficient approach to guarantee that all blocks received by consumers will be linearly independent. However, it has very high communication and computation overheads. Therefore, RB matching was proposed as a more lightweight approach, where the Interest only carries the rank of the global coefficients X of the coded blocks already received by the consumer. If the number of coded blocks cached by the CR is larger than the rank of the global coefficients X, the CR can respond to the Interest with a coded block. The larger the value of X is, the more difficult it is to serve the Interest. Wu et al. [16] proposed a network coding and random forwarding-based caching strategy, CodingCache, to enhance the caching efficiency. To guarantee all the blocks provided to consumer are linearly independent, each Interest carries the global coefficients of the coded blocks already received to retrieve the next block, similar to precise matching. Therefore, N rounds will be required in order to retrieve N blocks. Nguyen et al. [20] proposed a lightweight caching and Interest aggregation strategy to ensure that all the coded blocks received by the consumer are independent. Like RB matching, the rank of the global coefficients of the coded blocks already received by the consumer is carried by the Interest packet. Saltarin et al. [19] proposed a protocol named NetCodCCN to permit Interest aggregation and pipelining. Each node responds to an Interest once it has received enough coded blocks to recover the content or X is larger than the number of coded blocks already sent out over face i previously, where X is the rank of the global coefficients X of the coded blocks cached in ContentStore. However, NetCodCCN has a weakness also shared by RB matching in that it may provide false negative decisions, i.e., a node may falsely decide it cannot provide an innovative coded block for the consumer while actually the block is available. Montpetit et al. [17] proposed an architecture based on network coding, NC3N, where each Interest retrieves one coded block. However, there method does not include a strategy to ensure all the received blocks are independent. Liu et al. [18] proposed an ICN-NC method to guarantee that all the blocks received are provided by different CRs to increase the probability of obtaining linearly independent blocks. Each Interest packet contains a record of the Interest exploration range of the previous round. Only CRs within a new exploration area are permitted to respond to these Interests. Several rounds are required to retrieve enough independent coded blocks, and the Interest may retrieve linearly dependent coded blocks. The authors in [25] proposed a framework based on network coding for cache management in ICNs. Saltarin et al. [26] proposed a distributed caching strategy for ICNs enabled for network coding, which gives CRs the responsibility of estimating the popularity of contents and ensuring that the most popular content is cached near the network edge.Most of the existing schemes require several round trips to obtain sufficient linearly independent coded blocks to recover the content. In this paper, we propose a novel content delivery strategy to ensure enough blocks can be retrieved within a single round. An on-path non-cooperative caching and replacing strategy based on network coding is proposed to guarantee that all blocks received by consumers are linearly independent. Moreover, in our scheme, coded blocks are generated only if the traffic can be saved instead of generated at the server and all CRs on the forwarding path in order to reduce the cost of coding and decoding.


## 3. Method of Interest Aggregation and Separation

In ICN, chunk-based delivery strategies route chunks separately. Chunks may meet on an intermediate node during their forwarding paths to several consumers. Motivated by this, we propose a special request-specific coded-block (RSCB) scheme to encode chunks that meet during transport in order to reduce traffic.


### 3.1. Overview of RSNC

The definitions given in our previous study (referred to as RSNC) will be followed here. Each InterestS,N requests a specific set of chunks, where S=1,…,N is the set of chunk indices and N is number of independent coded blocks required to recover the content. Since chunks may be cached by different CRs, each CR can aggregate, separate, and forward Interests. If Interest 1 requests a set of chunks S1 and Interest 2 requests a set of chunks S2, then S,n satisfies both Interests, where S=S1∪S2 is the set of chunks used to generate n linearly independent coded blocks, n is the number of coded blocks to be sent by the upstream CR, and n=maxS1,S2. When n<S, the traffic required to deliver chunks from upstream will be reduced.Since an Interest sent by a consumer for multiple chunks will be copied and forwarded along a multicast tree, requests for different chunks sent from the same consumer will not meet again in a CR on the multicast tree. Therefore, the Interest aggregation operation “⊕” is defined to combine two Interests originating from at least two different consumers, i.e.,(1)S1,n1⊕S2,n2⇒defS,n,whereS=S1∪S2,n=maxn1,n2.Similarly, a separation operation “Div” is defined to split an Interest into several sub-Interests:(2)DivS,n⇒defS3,n3,S4,n4,whereS3,n3⊕S4,n4=S,n,S3∩S4=∅,S=S3∪S4,n3=minS3,n,n4=minS4,n.


### 3.2. Interest Aggregation and Separation in RSCB

In contrast with RSNC [23], RSCB includes information on S1,n1 and S2,n2 in the aggregated Interest S,n which guarantees that linearly independent coded blocks are provided to consumers and minimize the number of coded blocks transported in the network. To reduce the size of the Interest, the sub-Interest information is presented as a binary number, bSi. For example, if Interest S=1,2,3,4,bS,n=2 is an aggregated Interest of Interest 1 S1=1,3,n1=2 and Interest 2 S2=2,4,n2=2, the binary information of Interest 1 is bS1=1010, and the binary information of Interest 2 is bS2=0101, and thus bS=bS1∪bS2=1010,0101. Therefore, an Interest can be expressed as Ip,S,bS,n, where p is the name of the requested content, S is a set of chunks that match the name of the content p, bS is a set of binary numbers representing the sub-Interests (each sub-Interest is a subset of S), and n is the number of linearly independent coded blocks being requested. Therefore, any n linearly independent coded blocks that contain all chunks specified by S will satisfy the sub-Interests specified in bS.Equation (1) can thus be further modified as(3)S1,bS1,s1⊕S2,bS2,s2=defS,bS,s,whereS=S1∪S2,s=maxs1,s2,bS⊆bS1∪bS2,where s is the minimum number of linearly coded blocks satisfying both Interests S1,bS1,s1 and S2,bS2,s2.It should be noted that the binary numberbSi is used to represent the subset information, which is required to guarantee that the requested number of coded blocks is minimized. When s=1 or s=S, this subset information is not necessary, as shown in Figure 1(a). Moreover, if Si⊆Sj, the information on Si, i.e., bSi, will be deleted from bS.Figure 1
An example of RSCB. (a) Communication in RSCB. (b) Caching in RSCB.
(a)(b)For instance, Figure1(a) shows that CR1 receives two Interests for content Cp from different interfaces, Ip,S1=2,4,2 and Ip,S2=1,3,2. Before these two Interests are forwarded, CR1 aggregates the two requests into a single Interest Ip,S=1,2,3,4,bS=0101,1010,2 using equation (3). bS can then be used to reconstruct the subsets 2,4 and 1,3.Similarly, the separation operation used to split an InterestS,bS,s into several sub-Interests is modified, which is used to distribute the sub-Interests out over several interfaces of the CR towards different content sources:(4)DivS,bS,s=defS1,bS1,s1,S2,bS2,s2,whereS1∩S2=null,S=S1∪S2;s1=minS1,s,s2=minS2,s.If an InterestS,bS,s is formed by merging multiple Interests, the subsets Si,si should be reconstructed based on bS, and these subsets should then be separated into sub-subsets using equation (2). Then, new Interests, i.e., S1,bS1,s1 and S2,bS2,s2 in equation (4), are generated by aggregating the sub-subsets using equation (3). This procedure is described in Algorithm 1. The complexity of Algorithm 1 is On, where n is the number of subsets. According to Algorithm 1, Ip,1,2,3,4,bS,2 can be reconstructed into two subsets 2,4,2 and 1,3,2 for bS=0101,1010. These subsets can be further divided into sub-subsets: 2,1, 4,1, 1,1, 3,1 using equation (2), and then aggregated into Interest Ip,1,2,1 and Interest Ip,3,4,1 according to equation (3). If the original blocks ob1 and ob2 are located in the same direction and the original blocks ob3 and ob4 are located in another direction, the new Interests can be sent from two interfaces in two different directions, as shown in Figure 1(a). In this case, only two blocks will transmitted which is in contrast with RSNC [23], which requires four blocks to be transmitted.Algorithm 1: Separation.
Inputs(1)
Input Interest:Ip,S,bS,sSteps(1)
Reconstruct subsetsS1,s1,…and Sm,sm according to bS=bS1,…,bSm, where si=Si, for i=1,…,m;(2)
ifS≠∪iSi, i=1,…,mthen(3)
Determine subsetSm+1,sm+1, where Sm+1=S\∪iSi, sm+1=1;(4)
end if(5)
for each subset Si,sido(6)
Use equation (2) to divide subset Si,si into several sub-subsets Ti1,ti1,…,Tik,tik based on the forwarding interface of each chunk name (each and every sub-subset corresponds to an interface), where tij=minTij,si, for j=1,…,k;(7)
end for(8)
Use equation (3) to generate new Interests by aggregating the sub-subsets T1,t1,…,Tn,tn according to the forwarding interfaces.If Interest 2S2,n2 arrives after Interest 1 S1,n1 has already been sent upstream, then the aggregated pending Interest will be S,n=defS1,n1⊕S2,n2. Since S2,n2 may contain some chunks that have also been requested by Interest S1,n1, these chunks should be removed from Interest 2. Therefore, we define an operation to determine incremental Interest based on the separation operation:(5)ΔS2,Δn2=defS2,n2\S1,n1,whereΔS2=S2\ΔS1,Δn2=minΔS2,n2,ΔS1⊆S1∩S2,Δn1=minΔS1,n1.Since Interest 1 will return at mostn1 coded blocks, Δn1≤n1 is required. If S1∩S2>n1 and n2>n1, we let ΔS1⊂S1∩S2 and Δn1=ΔS1=n1. Similarly, if a CR has cached a subset W,w of blocks, only the remaining S′,n′ blocks need to be requested from the upstream CRs, where S′,n′=S,n\W,w. In RSCB, the coded blocks generated by the original blocks (referred to as coded-from-original block) are cached by the first node en route to consumers. The coded-from-original blocks are used as the original blocks to satisfy future Interests. For example, in Figure 1(b), the coded-from-original block, ocb1=α11ob1+α12ob2, can be presented as W=1,2,w=1. When Interest S=1,2,n=2 is received by CR2, the incremental Interest S′=2,n=1 is determined and sent to the next node.The benefits of RSCB are illustrated in Figures1 and 2. In Figure 1(a), two consumers connected to router CR5 and CR6 have requested content, which contains four original blocks, ob1,ob2,ob3, and ob4 at the same time. Each original block has a size of one unit, each CR has a two-unit cache capacity, and each link has a one-unit transmission cost. Figure 1 shows the communication and caching in RSCB. For RSCB, CR5 and CR6 receive two coded-from-original blocks generated by CR3 and CR4, respectively. Coded-from-original blocks ocb1 and ocb2 are received from CR1, where(6)ocb1=α11ob1+α12ob2,ocb2=α21ob3+α22ob4.Figure 2
Communication in ICN.The total transmission cost is eight units. Figure2 shows the conventional ICN communication. CR2 receives the four original blocks (ob1,ob2,ob3,ob4) from CR3 and CR4 and then forwards these original blocks to CR1. CR1 responds to Interest Ip:2,4,2 with two original blocks, ob2 and ob4, and Interest Ip,1,3,2 with two further original blocks, ob1 and ob3. The total transmission cost is 12 units. Therefore, our proposed solution saves 33% of the transmission cost compared with conventional ICN and 20% more than our previous work [23].


### 3.3. Caching in RSCB

In RSCB, the original/coded-from-original blocks are cached by CRs to respond to future Interests. In order to provide consumers with sufficient linearly independent blocks in a single round, none of coded blocks that were encoded by coded blocks are cached in the network. The coded-from-original block only can be cached by a single CR, which is the immediate downstream neighbor of the CR that generated the block. Thus, the two coded-from-original blocks,ocb1 and ocb2, will be cached only by CR2 (Figure 1(b). The coded-from-original block ocb1 can be used as the original block ob1 or ob2 to respond to future Interests. When cache replacement happens, CR encodes several original blocks into one coded-from-original block to release the caching space. This ensures that all information contained in the original blocks is retained in the CR.


## 3.1. Overview of RSNC

The definitions given in our previous study (referred to as RSNC) will be followed here. Each InterestS,N requests a specific set of chunks, where S=1,…,N is the set of chunk indices and N is number of independent coded blocks required to recover the content. Since chunks may be cached by different CRs, each CR can aggregate, separate, and forward Interests. If Interest 1 requests a set of chunks S1 and Interest 2 requests a set of chunks S2, then S,n satisfies both Interests, where S=S1∪S2 is the set of chunks used to generate n linearly independent coded blocks, n is the number of coded blocks to be sent by the upstream CR, and n=maxS1,S2. When n<S, the traffic required to deliver chunks from upstream will be reduced.Since an Interest sent by a consumer for multiple chunks will be copied and forwarded along a multicast tree, requests for different chunks sent from the same consumer will not meet again in a CR on the multicast tree. Therefore, the Interest aggregation operation “⊕” is defined to combine two Interests originating from at least two different consumers, i.e.,(1)S1,n1⊕S2,n2⇒defS,n,whereS=S1∪S2,n=maxn1,n2.Similarly, a separation operation “Div” is defined to split an Interest into several sub-Interests:(2)DivS,n⇒defS3,n3,S4,n4,whereS3,n3⊕S4,n4=S,n,S3∩S4=∅,S=S3∪S4,n3=minS3,n,n4=minS4,n.


## 3.2. Interest Aggregation and Separation in RSCB

In contrast with RSNC [23], RSCB includes information on S1,n1 and S2,n2 in the aggregated Interest S,n which guarantees that linearly independent coded blocks are provided to consumers and minimize the number of coded blocks transported in the network. To reduce the size of the Interest, the sub-Interest information is presented as a binary number, bSi. For example, if Interest S=1,2,3,4,bS,n=2 is an aggregated Interest of Interest 1 S1=1,3,n1=2 and Interest 2 S2=2,4,n2=2, the binary information of Interest 1 is bS1=1010, and the binary information of Interest 2 is bS2=0101, and thus bS=bS1∪bS2=1010,0101. Therefore, an Interest can be expressed as Ip,S,bS,n, where p is the name of the requested content, S is a set of chunks that match the name of the content p, bS is a set of binary numbers representing the sub-Interests (each sub-Interest is a subset of S), and n is the number of linearly independent coded blocks being requested. Therefore, any n linearly independent coded blocks that contain all chunks specified by S will satisfy the sub-Interests specified in bS.Equation (1) can thus be further modified as(3)S1,bS1,s1⊕S2,bS2,s2=defS,bS,s,whereS=S1∪S2,s=maxs1,s2,bS⊆bS1∪bS2,where s is the minimum number of linearly coded blocks satisfying both Interests S1,bS1,s1 and S2,bS2,s2.It should be noted that the binary numberbSi is used to represent the subset information, which is required to guarantee that the requested number of coded blocks is minimized. When s=1 or s=S, this subset information is not necessary, as shown in Figure 1(a). Moreover, if Si⊆Sj, the information on Si, i.e., bSi, will be deleted from bS.Figure 1
An example of RSCB. (a) Communication in RSCB. (b) Caching in RSCB.
(a)(b)For instance, Figure1(a) shows that CR1 receives two Interests for content Cp from different interfaces, Ip,S1=2,4,2 and Ip,S2=1,3,2. Before these two Interests are forwarded, CR1 aggregates the two requests into a single Interest Ip,S=1,2,3,4,bS=0101,1010,2 using equation (3). bS can then be used to reconstruct the subsets 2,4 and 1,3.Similarly, the separation operation used to split an InterestS,bS,s into several sub-Interests is modified, which is used to distribute the sub-Interests out over several interfaces of the CR towards different content sources:(4)DivS,bS,s=defS1,bS1,s1,S2,bS2,s2,whereS1∩S2=null,S=S1∪S2;s1=minS1,s,s2=minS2,s.If an InterestS,bS,s is formed by merging multiple Interests, the subsets Si,si should be reconstructed based on bS, and these subsets should then be separated into sub-subsets using equation (2). Then, new Interests, i.e., S1,bS1,s1 and S2,bS2,s2 in equation (4), are generated by aggregating the sub-subsets using equation (3). This procedure is described in Algorithm 1. The complexity of Algorithm 1 is On, where n is the number of subsets. According to Algorithm 1, Ip,1,2,3,4,bS,2 can be reconstructed into two subsets 2,4,2 and 1,3,2 for bS=0101,1010. These subsets can be further divided into sub-subsets: 2,1, 4,1, 1,1, 3,1 using equation (2), and then aggregated into Interest Ip,1,2,1 and Interest Ip,3,4,1 according to equation (3). If the original blocks ob1 and ob2 are located in the same direction and the original blocks ob3 and ob4 are located in another direction, the new Interests can be sent from two interfaces in two different directions, as shown in Figure 1(a). In this case, only two blocks will transmitted which is in contrast with RSNC [23], which requires four blocks to be transmitted.Algorithm 1: Separation.
Inputs(1)
Input Interest:Ip,S,bS,sSteps(1)
Reconstruct subsetsS1,s1,…and Sm,sm according to bS=bS1,…,bSm, where si=Si, for i=1,…,m;(2)
ifS≠∪iSi, i=1,…,mthen(3)
Determine subsetSm+1,sm+1, where Sm+1=S\∪iSi, sm+1=1;(4)
end if(5)
for each subset Si,sido(6)
Use equation (2) to divide subset Si,si into several sub-subsets Ti1,ti1,…,Tik,tik based on the forwarding interface of each chunk name (each and every sub-subset corresponds to an interface), where tij=minTij,si, for j=1,…,k;(7)
end for(8)
Use equation (3) to generate new Interests by aggregating the sub-subsets T1,t1,…,Tn,tn according to the forwarding interfaces.If Interest 2S2,n2 arrives after Interest 1 S1,n1 has already been sent upstream, then the aggregated pending Interest will be S,n=defS1,n1⊕S2,n2. Since S2,n2 may contain some chunks that have also been requested by Interest S1,n1, these chunks should be removed from Interest 2. Therefore, we define an operation to determine incremental Interest based on the separation operation:(5)ΔS2,Δn2=defS2,n2\S1,n1,whereΔS2=S2\ΔS1,Δn2=minΔS2,n2,ΔS1⊆S1∩S2,Δn1=minΔS1,n1.Since Interest 1 will return at mostn1 coded blocks, Δn1≤n1 is required. If S1∩S2>n1 and n2>n1, we let ΔS1⊂S1∩S2 and Δn1=ΔS1=n1. Similarly, if a CR has cached a subset W,w of blocks, only the remaining S′,n′ blocks need to be requested from the upstream CRs, where S′,n′=S,n\W,w. In RSCB, the coded blocks generated by the original blocks (referred to as coded-from-original block) are cached by the first node en route to consumers. The coded-from-original blocks are used as the original blocks to satisfy future Interests. For example, in Figure 1(b), the coded-from-original block, ocb1=α11ob1+α12ob2, can be presented as W=1,2,w=1. When Interest S=1,2,n=2 is received by CR2, the incremental Interest S′=2,n=1 is determined and sent to the next node.The benefits of RSCB are illustrated in Figures1 and 2. In Figure 1(a), two consumers connected to router CR5 and CR6 have requested content, which contains four original blocks, ob1,ob2,ob3, and ob4 at the same time. Each original block has a size of one unit, each CR has a two-unit cache capacity, and each link has a one-unit transmission cost. Figure 1 shows the communication and caching in RSCB. For RSCB, CR5 and CR6 receive two coded-from-original blocks generated by CR3 and CR4, respectively. Coded-from-original blocks ocb1 and ocb2 are received from CR1, where(6)ocb1=α11ob1+α12ob2,ocb2=α21ob3+α22ob4.Figure 2
Communication in ICN.The total transmission cost is eight units. Figure2 shows the conventional ICN communication. CR2 receives the four original blocks (ob1,ob2,ob3,ob4) from CR3 and CR4 and then forwards these original blocks to CR1. CR1 responds to Interest Ip:2,4,2 with two original blocks, ob2 and ob4, and Interest Ip,1,3,2 with two further original blocks, ob1 and ob3. The total transmission cost is 12 units. Therefore, our proposed solution saves 33% of the transmission cost compared with conventional ICN and 20% more than our previous work [23].


## 3.3. Caching in RSCB

In RSCB, the original/coded-from-original blocks are cached by CRs to respond to future Interests. In order to provide consumers with sufficient linearly independent blocks in a single round, none of coded blocks that were encoded by coded blocks are cached in the network. The coded-from-original block only can be cached by a single CR, which is the immediate downstream neighbor of the CR that generated the block. Thus, the two coded-from-original blocks,ocb1 and ocb2, will be cached only by CR2 (Figure 1(b). The coded-from-original block ocb1 can be used as the original block ob1 or ob2 to respond to future Interests. When cache replacement happens, CR encodes several original blocks into one coded-from-original block to release the caching space. This ensures that all information contained in the original blocks is retained in the CR.


## 4. Architecture

CCN architecture is the most popular architecture of ICN, and we have selected this architecture to implement RSCB. To enable network coding in CCN, some changes are required.


### 4.1. Content Publishing and Requesting

In CCN, content is split into several smaller-sized chunks, with each chunk identified by a unique hierarchical name. In RSCB, content is firstly divided intoh generations and each generation is then divided into N chunks, i.e., original blocks. We denote content as Cp=cp,1,1,…,cp,1,N,…,cp,h,1,…,cp,h,N, where p is the name of the content, N is a design parameter, and h can be calculated based on the content size and N. The content name p should contain information on h and N. For instance, the name of chunk cp,2,1 is /sysu.edu.cn/largefile/h/N/2/1, where /sysu.edu.cn/largefile/h/N is the content name, p, 2 is the generation ID, and 1 is the chunk ID (referred to as the original block index).A consumer will generate a set of Interests,Ip,1,…,Ip,h, for each generation in order to request content Cp. Each Interest Ip,i requests a set of original blocks, cp,i,1,…,cp,i,N, where i is the number of generations. The number of Interests sent by the consumer depends on the flow control schemes which have been placed in the network. The consumer can send Interests either sequentially or simultaneously.Since the forwarding paths of requests for different chunks generated by the same consumer will form a multicast tree, these requests will not meet in any intermediate CR on the multicast tree. Interests are responded to with chunks or coded blocks which are linear combinations of chunks that have been specified by the Interest. Random linear network coding (RLNC) is used to generate the coded blocks within each generation. For convenience, in the remainder of this paper, we will not explicitly state which generation each chunk belongs to. Our model makes the assumption that a chunk-based routing and flow control scheme is in place.


### 4.2. Interest and Data

All communications are driven by consumers in CCN. Consumers can receive chunks of content from multiple sources, which may include the content provider and CRs. A consumer interested inCp will send a set of requests Ip=ip,1,…,ip,N with one request for each chunk. Before these requests are forwarded, the CR determines the forwarding interface of each chunk using the forwarding information base (FIB). Requests that have the same forwarding interface will be aggregated into a single Interest. Each Interest can contain multiple requests for a set of chunks, Si, where Si is the set of chunk names.There are two types of CCN packets, Interests and data. In our model, the network coding information is appended to the selector field of the Interest packet and includes the set of chunk namesS, the sub-Interests bS, and the number of required blocks n. The coefficient of the coded blocks, the caching flag Fq, is contained within the signed info field of the data packet. The data field of the data packet contains the original/coded block(s).The Interest and data packets used in our model are formulated using the following method:(i)
Ip,S,B,m defines an Interest for content Cp, where p is the content name, S=S1∪S2∪…∪Sn is the set of chunk names, and m=maxS1,S2,…,Sn≤S is the number of required blocks. B=bS1,bS2,…,bSn is used to represent the subsets S1,S2,…,Sn and Si⊈Sj, if i≠j. For convenience, we express the Interest as Ip,S,m.(ii)
Dp,S,block,Fq defines a data packet for content Cp containing block, which is either a chunk or a coded block (a linear combination of several chunks specified by set S). Fq is a caching flag which indicates whether the block is cacheable or not. If the block is a coded block, we obtain SD⊇SI, where SD is the set of chunk names carried by the data and SI is carried by the Interest.


### 4.3. Forwarding Module

The forwarding module of RSCB contains three components: the ContentStore (CS), the pending interest table (PIT), and the forwarding information base (FIB). The blocks received by the CRs are cached by the CS module. A CS entry can be formulated byCSp,W,w, which is defined as follows:(i)
p: content name.(ii)
IndexW,w: W is a set of chunk names and w is the number of cached blocks. Since both the original and the coded-from-original blocks can be cached, we obtain W≥w.(iii)
Data: the original or coded-from-original blocks.In contrast with CCN, each CR interface in RSCB maintains a PIT. The PIT can have two types of entry, PIT-OUT and PIT-IN, which record information on Interests already sent or received to the interface, respectively. PIT-OUT and PIT-IN can be defined as follows:(i)
PITout−ip,S,s,facelist: this is a PIT-OUT entry that indicates that p,S,s is an aggregated Interest generated by aggregating several Interests received from interface(s) of facelist. The aggregated Interest has already been sent out over the interface i but a response has not been received from the upstream CR.(ii)
PITin−ip,S,s: this is a PIT-IN entry that indicates that p,S,s is an aggregated Interest generated by aggregating several Interests received from interface i. A response has not yet been sent over interface i.The FIB is the same as for CCN. When an Interest is received by a CR, its CS is first consulted, followed by PIT and finally FIB. Data packets will be sent back to consumers using the same path that was created by the Interest, but in the opposite direction.


## 4.1. Content Publishing and Requesting

In CCN, content is split into several smaller-sized chunks, with each chunk identified by a unique hierarchical name. In RSCB, content is firstly divided intoh generations and each generation is then divided into N chunks, i.e., original blocks. We denote content as Cp=cp,1,1,…,cp,1,N,…,cp,h,1,…,cp,h,N, where p is the name of the content, N is a design parameter, and h can be calculated based on the content size and N. The content name p should contain information on h and N. For instance, the name of chunk cp,2,1 is /sysu.edu.cn/largefile/h/N/2/1, where /sysu.edu.cn/largefile/h/N is the content name, p, 2 is the generation ID, and 1 is the chunk ID (referred to as the original block index).A consumer will generate a set of Interests,Ip,1,…,Ip,h, for each generation in order to request content Cp. Each Interest Ip,i requests a set of original blocks, cp,i,1,…,cp,i,N, where i is the number of generations. The number of Interests sent by the consumer depends on the flow control schemes which have been placed in the network. The consumer can send Interests either sequentially or simultaneously.Since the forwarding paths of requests for different chunks generated by the same consumer will form a multicast tree, these requests will not meet in any intermediate CR on the multicast tree. Interests are responded to with chunks or coded blocks which are linear combinations of chunks that have been specified by the Interest. Random linear network coding (RLNC) is used to generate the coded blocks within each generation. For convenience, in the remainder of this paper, we will not explicitly state which generation each chunk belongs to. Our model makes the assumption that a chunk-based routing and flow control scheme is in place.


## 4.2. Interest and Data

All communications are driven by consumers in CCN. Consumers can receive chunks of content from multiple sources, which may include the content provider and CRs. A consumer interested inCp will send a set of requests Ip=ip,1,…,ip,N with one request for each chunk. Before these requests are forwarded, the CR determines the forwarding interface of each chunk using the forwarding information base (FIB). Requests that have the same forwarding interface will be aggregated into a single Interest. Each Interest can contain multiple requests for a set of chunks, Si, where Si is the set of chunk names.There are two types of CCN packets, Interests and data. In our model, the network coding information is appended to the selector field of the Interest packet and includes the set of chunk namesS, the sub-Interests bS, and the number of required blocks n. The coefficient of the coded blocks, the caching flag Fq, is contained within the signed info field of the data packet. The data field of the data packet contains the original/coded block(s).The Interest and data packets used in our model are formulated using the following method:(i)
Ip,S,B,m defines an Interest for content Cp, where p is the content name, S=S1∪S2∪…∪Sn is the set of chunk names, and m=maxS1,S2,…,Sn≤S is the number of required blocks. B=bS1,bS2,…,bSn is used to represent the subsets S1,S2,…,Sn and Si⊈Sj, if i≠j. For convenience, we express the Interest as Ip,S,m.(ii)
Dp,S,block,Fq defines a data packet for content Cp containing block, which is either a chunk or a coded block (a linear combination of several chunks specified by set S). Fq is a caching flag which indicates whether the block is cacheable or not. If the block is a coded block, we obtain SD⊇SI, where SD is the set of chunk names carried by the data and SI is carried by the Interest.


## 4.3. Forwarding Module

The forwarding module of RSCB contains three components: the ContentStore (CS), the pending interest table (PIT), and the forwarding information base (FIB). The blocks received by the CRs are cached by the CS module. A CS entry can be formulated byCSp,W,w, which is defined as follows:(i)
p: content name.(ii)
IndexW,w: W is a set of chunk names and w is the number of cached blocks. Since both the original and the coded-from-original blocks can be cached, we obtain W≥w.(iii)
Data: the original or coded-from-original blocks.In contrast with CCN, each CR interface in RSCB maintains a PIT. The PIT can have two types of entry, PIT-OUT and PIT-IN, which record information on Interests already sent or received to the interface, respectively. PIT-OUT and PIT-IN can be defined as follows:(i)
PITout−ip,S,s,facelist: this is a PIT-OUT entry that indicates that p,S,s is an aggregated Interest generated by aggregating several Interests received from interface(s) of facelist. The aggregated Interest has already been sent out over the interface i but a response has not been received from the upstream CR.(ii)
PITin−ip,S,s: this is a PIT-IN entry that indicates that p,S,s is an aggregated Interest generated by aggregating several Interests received from interface i. A response has not yet been sent over interface i.The FIB is the same as for CCN. When an Interest is received by a CR, its CS is first consulted, followed by PIT and finally FIB. Data packets will be sent back to consumers using the same path that was created by the Interest, but in the opposite direction.


## 5. Communication Scheme

### 5.1. Forwarding Interest

When a CR receives an InterestIp,X,x over interface f, the first step is to check its CS. If the CS contains all chunks or the coded-from-original blocks containing all the information in the Interested set X, the CR will respond to Interest Ip,X,x directly, as described in Algorithm 2. The complexity of Algorithm 2 is On, where n is the number of coded blocks. If X=x, the CR responds to Interest Ip,X,x with the x cached blocks (chunks or coded-from-original blocks) without coding; otherwise, the CR will respond with the x coded blocks generated from the blocks cached in the CS, which contain the chunk information specified by set X. The caching flag, Fq, will be turned on, i.e., Fq = 1 if the block used to respond to the Interest is an original block or a coded-from-original block encoded by that CR; otherwise, Fq = 0. In RSCB, the CR performs network coding only if it will save on the transmission costs. For instance, as shown in Figure 1(a), CR responds to Interest Ip,1,2,3,4:1010,0101,2 with two coded-from-original blocks, ocb1 and ocb2, which were received from CR3 and CR4, respectively, without further coding. In this case, there is a saving on the cost of coding.Algorithm 2: Responding Interest.
Input:Ip,X,x← Interest arriving on interface f,CSpW,w←W is the set of blocks specified by Ip,X,x and w is the number of blocks;(1)
ifX=x or x=wthen(2)
for each block csi in CSpdo(3)
ifcsi is an original block then(4)
Fq = 1;(5)
else(6)
Fq = 0;(7)
end if(8)
Create a data packetDp,Yi,csi,Fq and send over interface f;(9)
end for(10)
else(11)
Generatex coded blocks, ob1,…, and obx, using the blocks in CSp;(12)
if all the blocks in CSp are original blocks then(13)
Fq = 1;(14)
else(15)
Fq = 0;(16)
end if(17)
for each coded block cbido(18)
Generate a data packetDp,Yi,cbi,Fq and send over interface f;(19)
end for(20)
end ifIf the Interest cannot be satisfied by the CR, PIT-IN of the arrival interfacef will be checked. If there is a matched entry PITin−fp,Z,z, CR will aggregate the PIT-IN entry and the Interest using equation (3) and will then update the PIT-IN entry PITin−fp,Z′,z′, where Z′=X∪Z, z′=maxx,z. Therefore, the incremental Interest p,ΔX,Δx=p,X,x\p,W,w will be determined.The CR will split the incremental requests forp,ΔX,Δx into several Interests using Algorithm 1. If one of the Interests, e.g., p,Xj,xj, needs to be transmitted over the interface j, PIT-OUT of interface j will be obtained. If there is a matching PIT-OUT entry PITout−jp,V,v, a new incremental Interest for p,ΔXj,Δxj=p,Xj,xj\p,V,v will be generated using equation (5) and transmitted over interface j if ΔXj≠null. The PIT-OUT entry will then be updated to PITout−jp,V′,v′,facelist, where V′=V∪Xj and v′=maxv,xj, and interface f will be added to facelist. Algorithm 3 describes the process used to forward an Interest. The complexity of Algorithm 3 is On, where n is the number of sub-Interests.Algorithm 3: Forwarding Interest.
Input: InterestIp,X,x; interface f(1)
if CS matches then(2)
Respond to Interest according to Algorithm2;(3)
else(4)
if PIT-IN of interface f matches then(5)
Update PIT-IN;(6)
else(7)
Establish a new PIT-IN entry;(8)
end if(9)
Calculate the incremental InterestΔI;(10)
ifΔI≠nullthen(11)
Separate the incremental InterestΔI into several sub-Interests according to Algorithm 1;(12)
for each sub-Interest Ii which needs to be sent over interface ido(13)
if PIT-OUT of i matches then(14)
Update PIT-OUT;(15)
Calculate the incremental InterestΔIi;(16)
ifΔIi=nullthen(17)
return;(18)
end if(19)
else(20)
Establish a new PIT-OUT entry;(21)
end if(22)
Send InterestIi (or ΔIi) from interface i;(23)
end for(24)
end if(25)
end if


### 5.2. Forwarding Data

When data packetDp,Y,block,Fq is received by a CR over interface f, the PIT-OUT of interface f will be checked in the tables. If there is no PIT-OUT match, the data Dp,Y,block,Fq will be discarded directly since the CR has not requested the block; otherwise, the caching flag will be checked and the matching PIT-OUT entry will be updated according to Algorithm 4. If Fq=1, the block carried by data will be cached into CS; otherwise, it will be temporarily cached into CACHE. The CR will then check whether more chunks can be obtained by decoding the blocks cached in CS and CACHE. If the CR has already received enough blocks of content p to recover the content, the chunks decoded from the received blocks will be cached into CS and all of the blocks of content p that were cached in CACHE will be deleted. In this case, CR can satisfy any Interest of content p.Algorithm 4: Forwarding data.
Input: data packetDp,Y,block,Fq; interface f(1)
if PIT-OUT of interface f matches then(2)
ifFq=1then(3)
Cache data into CS;(4)
else(5)
Cache data into CACHE;(6)
end if(7)
for each interface i in the facelist of the matched PIT-OUT do(8)
Find the matched PIT-IN entry, i.e.PITin−ip,Z,z, where Y∩Z≠∅;(9)
if the matched PIT-IN entry of interface i is satisfied then(10)
Respond to the PIT-IN entryPITin−ip,Z,z, according to Algorithm 2;(11)
Delete the PIT-IN entry;(12)
else(13)
if the block carried by data is an original block and Z=zthen(14)
Send dataDp,Y,block,Fq over interface i;(15)
UpdatePITin−ip,Z,z to PITin−ip,Z′,z′, where Z′=Z\Y, z′=z−1;(16)
end if(17)
end if(18)
end for(19)
if the matched PIT-OUT of interface f is satisfied then(20)
Delete the PIT-OUT entry;(21)
end if(22)
else(23)
Discard dataDp,Y,block,Fq;(24)
end ifIf interfacei is included in the facelist of the matching PIT-OUT entry, the corresponding PIT-IN entry is PITin−ip,Z,z. If Y∩Z≠∅, CR checks whether the PITin−ip,Z,z can be satisfied using blocks cached in CS and CACHE. If it can be satisfied, CR will generate z linearly independent combinations of the blocks specified by the set Z and will send z data packets over interface i. Each data packet carries a coded block and PITin−ip,Z,z is then deleted. Once the PIT-IN entries of all interfaces in facelist of the matched PIT-OUT entry are satisfied, the coded blocks of content p that are cached in CACHE are deleted, as described by Algorithm 4. The complexity of Algorithm 4 is Onm, since the complexity of Algorithm 2 is Om, where n is the number of interfaces in the facelist of the matched PIT-OUT and m is the number of coded blocks.The network will try to deliver chunks without introducing extra traffic in order to increase the independence of the blocks cached in CRs. When the CR receives a data packetDp,Y,block,Fq carrying a chunk (i.e., Y=1), if z=Z, the data packet Dp,Y,block,Fq will be sent out over interface i without further processing or waiting for other data packets. The CR will then update PITin−ip,Z,z to PITin−ip,Z′,z′, where Z′=Z\Y, z′=z−1. If z=0, the CR will delete the PIT-IN entry. In this case, the time to download chunk Y will be reduced and the cost of coding and decoding is saved without introducing additional traffic.


### 5.3. Cache Policy

Network coding-enabled ICN (NC-ICN) will divide the content inton original blocks. For traditional NC-ICN, each coded block is a linear combination of the n original blocks. The n coded blocks will be cached by n′ (n′≥n) CRs along their forwarding paths to a group of consumers. Figure 3(a) shows that for traditional NC-ICN, network N1 will provide m coded blocks, cb1,…,cbm, to consumers in group G1 and network N2 will provide the remaining n−m coded blocks. During the process of responding to consumers in group G1, m′ (m′≥m) coded blocks generated by cb1,…,cbm will be cached by multiple CRs in network N1, while n′ (n′≥n−m) coded blocks will be cached by multiple CRs in network N2. At a later time, when the consumers in G2 multicast their Interests for n coded blocks of content p, these Interests will be received first by CRs in network N1. Each CR will respond to the Interest with its cached coded blocks independently, and thus tt>m coded blocks cached in network N1 may be provided to consumers in G2. However, the maximum number of independent coded blocks that a consumer can receive from network N1 is m. In this case, at least t−m blocks are not beneficial to the consumer and are a waste of resources. Therefore, the conventional in-network caching strategy is not suitable for NC-ICN.Figure 3
Caching. (a) Caching in ICN. (b) Caching in RSCB.
(a)(b)To address this issue, we propose to introduce a simple cache mechanism to guarantee that the blocks provided to consumers will be independent. In RSCB, only original blocks and coded-from-original blocks will be cached by CRs. None of coded blocks that were encoded by other coded blocks can be cached in the network. The received/decoded original blocks can be cached by any CR. The coded-from-original blocks can only be cached by a single CR, which is the immediate downstream neighbor of the CR that generated the block. Thus, anyn coded-from-original blocks cached in the network will be linearly independent, where n is the number of blocks required to recover the content. Fq in data packet Dp,S,block,Fq is a caching flag that indicates whether the block is cacheable or not.Since CRs have limited storage capacity, a cache replacement policy is required. When cache replacement occurs, the candidate contentp that is to be discarded is selected using the existing content-level cache replacement policy, e.g., least recently used (LRU). Assume t units of cache space are required to cache newly received/decoded blocks and the cache space used to cache the candidate content p is n units (one unit for each block). If t≥n, content p is deleted and t=t−n. The first step is repeated until only some of cached blocks of the candidate content pi need to be discarded to cache new blocks, i.e., t<ni. Chunk-level cache replacement is then introduced to discard blocks in content pi. Firstly, any original blocks that are contained in the cached coded-from-original blocks are discarded, i.e., the information contained in the original blocks ob1 and ob2 may also be contained in the coded-from-original blocks ocb1=α11ob1+α12ob2. Secondly, the remaining original blocks are coded into a single coded-from-original block. Finally, the received coded-from-original blocks are randomly discarded. These three steps are performed in turn until there is sufficient space for the newly received/decoded blocks, as described in Algorithm 5. The complexity of Algorithm 5 is On, where n is the number of evicted content. If content is rarely accessed, only the coded-from-original blocks will be cached to respond to future Interests. Since a single coded-from-original block can respond to an aggregated Interest containing multiple requests for different chunks sent by multiple consumers, our chunk-level cache replacement policy can effectively increase the cache efficiency.Algorithm 5: Cache replacement strategy.
Input:t newly received/decoded blocks(1)
Determine the candidate contentp with n blocks using LRU;(2)
ift≥nthen(3)
Lett=t−n;(4)
Discard contentp;(5)
ift>0then(6)
go to step 1;(7)
end if(8)
else(9)
Discard then1 original blocks which are contained in the coded-from-original blocks;(10)
LetΔt1=t−n1;(11)
ifΔt1>0then(12)
Encode the remainingn2 original blocks into a single coded blocks;(13)
LetΔt2=Δt1−n2+1;(14)
ifΔt2>0then(15)
Randomly discardΔt2 received coded-from-original blocks;(16)
end if(17)
end if(18)
end if(19)
Cache the newly received/decoded blocks into the CS;


## 5.1. Forwarding Interest

When a CR receives an InterestIp,X,x over interface f, the first step is to check its CS. If the CS contains all chunks or the coded-from-original blocks containing all the information in the Interested set X, the CR will respond to Interest Ip,X,x directly, as described in Algorithm 2. The complexity of Algorithm 2 is On, where n is the number of coded blocks. If X=x, the CR responds to Interest Ip,X,x with the x cached blocks (chunks or coded-from-original blocks) without coding; otherwise, the CR will respond with the x coded blocks generated from the blocks cached in the CS, which contain the chunk information specified by set X. The caching flag, Fq, will be turned on, i.e., Fq = 1 if the block used to respond to the Interest is an original block or a coded-from-original block encoded by that CR; otherwise, Fq = 0. In RSCB, the CR performs network coding only if it will save on the transmission costs. For instance, as shown in Figure 1(a), CR responds to Interest Ip,1,2,3,4:1010,0101,2 with two coded-from-original blocks, ocb1 and ocb2, which were received from CR3 and CR4, respectively, without further coding. In this case, there is a saving on the cost of coding.Algorithm 2: Responding Interest.
Input:Ip,X,x← Interest arriving on interface f,CSpW,w←W is the set of blocks specified by Ip,X,x and w is the number of blocks;(1)
ifX=x or x=wthen(2)
for each block csi in CSpdo(3)
ifcsi is an original block then(4)
Fq = 1;(5)
else(6)
Fq = 0;(7)
end if(8)
Create a data packetDp,Yi,csi,Fq and send over interface f;(9)
end for(10)
else(11)
Generatex coded blocks, ob1,…, and obx, using the blocks in CSp;(12)
if all the blocks in CSp are original blocks then(13)
Fq = 1;(14)
else(15)
Fq = 0;(16)
end if(17)
for each coded block cbido(18)
Generate a data packetDp,Yi,cbi,Fq and send over interface f;(19)
end for(20)
end ifIf the Interest cannot be satisfied by the CR, PIT-IN of the arrival interfacef will be checked. If there is a matched entry PITin−fp,Z,z, CR will aggregate the PIT-IN entry and the Interest using equation (3) and will then update the PIT-IN entry PITin−fp,Z′,z′, where Z′=X∪Z, z′=maxx,z. Therefore, the incremental Interest p,ΔX,Δx=p,X,x\p,W,w will be determined.The CR will split the incremental requests forp,ΔX,Δx into several Interests using Algorithm 1. If one of the Interests, e.g., p,Xj,xj, needs to be transmitted over the interface j, PIT-OUT of interface j will be obtained. If there is a matching PIT-OUT entry PITout−jp,V,v, a new incremental Interest for p,ΔXj,Δxj=p,Xj,xj\p,V,v will be generated using equation (5) and transmitted over interface j if ΔXj≠null. The PIT-OUT entry will then be updated to PITout−jp,V′,v′,facelist, where V′=V∪Xj and v′=maxv,xj, and interface f will be added to facelist. Algorithm 3 describes the process used to forward an Interest. The complexity of Algorithm 3 is On, where n is the number of sub-Interests.Algorithm 3: Forwarding Interest.
Input: InterestIp,X,x; interface f(1)
if CS matches then(2)
Respond to Interest according to Algorithm2;(3)
else(4)
if PIT-IN of interface f matches then(5)
Update PIT-IN;(6)
else(7)
Establish a new PIT-IN entry;(8)
end if(9)
Calculate the incremental InterestΔI;(10)
ifΔI≠nullthen(11)
Separate the incremental InterestΔI into several sub-Interests according to Algorithm 1;(12)
for each sub-Interest Ii which needs to be sent over interface ido(13)
if PIT-OUT of i matches then(14)
Update PIT-OUT;(15)
Calculate the incremental InterestΔIi;(16)
ifΔIi=nullthen(17)
return;(18)
end if(19)
else(20)
Establish a new PIT-OUT entry;(21)
end if(22)
Send InterestIi (or ΔIi) from interface i;(23)
end for(24)
end if(25)
end if


## 5.2. Forwarding Data

When data packetDp,Y,block,Fq is received by a CR over interface f, the PIT-OUT of interface f will be checked in the tables. If there is no PIT-OUT match, the data Dp,Y,block,Fq will be discarded directly since the CR has not requested the block; otherwise, the caching flag will be checked and the matching PIT-OUT entry will be updated according to Algorithm 4. If Fq=1, the block carried by data will be cached into CS; otherwise, it will be temporarily cached into CACHE. The CR will then check whether more chunks can be obtained by decoding the blocks cached in CS and CACHE. If the CR has already received enough blocks of content p to recover the content, the chunks decoded from the received blocks will be cached into CS and all of the blocks of content p that were cached in CACHE will be deleted. In this case, CR can satisfy any Interest of content p.Algorithm 4: Forwarding data.
Input: data packetDp,Y,block,Fq; interface f(1)
if PIT-OUT of interface f matches then(2)
ifFq=1then(3)
Cache data into CS;(4)
else(5)
Cache data into CACHE;(6)
end if(7)
for each interface i in the facelist of the matched PIT-OUT do(8)
Find the matched PIT-IN entry, i.e.PITin−ip,Z,z, where Y∩Z≠∅;(9)
if the matched PIT-IN entry of interface i is satisfied then(10)
Respond to the PIT-IN entryPITin−ip,Z,z, according to Algorithm 2;(11)
Delete the PIT-IN entry;(12)
else(13)
if the block carried by data is an original block and Z=zthen(14)
Send dataDp,Y,block,Fq over interface i;(15)
UpdatePITin−ip,Z,z to PITin−ip,Z′,z′, where Z′=Z\Y, z′=z−1;(16)
end if(17)
end if(18)
end for(19)
if the matched PIT-OUT of interface f is satisfied then(20)
Delete the PIT-OUT entry;(21)
end if(22)
else(23)
Discard dataDp,Y,block,Fq;(24)
end ifIf interfacei is included in the facelist of the matching PIT-OUT entry, the corresponding PIT-IN entry is PITin−ip,Z,z. If Y∩Z≠∅, CR checks whether the PITin−ip,Z,z can be satisfied using blocks cached in CS and CACHE. If it can be satisfied, CR will generate z linearly independent combinations of the blocks specified by the set Z and will send z data packets over interface i. Each data packet carries a coded block and PITin−ip,Z,z is then deleted. Once the PIT-IN entries of all interfaces in facelist of the matched PIT-OUT entry are satisfied, the coded blocks of content p that are cached in CACHE are deleted, as described by Algorithm 4. The complexity of Algorithm 4 is Onm, since the complexity of Algorithm 2 is Om, where n is the number of interfaces in the facelist of the matched PIT-OUT and m is the number of coded blocks.The network will try to deliver chunks without introducing extra traffic in order to increase the independence of the blocks cached in CRs. When the CR receives a data packetDp,Y,block,Fq carrying a chunk (i.e., Y=1), if z=Z, the data packet Dp,Y,block,Fq will be sent out over interface i without further processing or waiting for other data packets. The CR will then update PITin−ip,Z,z to PITin−ip,Z′,z′, where Z′=Z\Y, z′=z−1. If z=0, the CR will delete the PIT-IN entry. In this case, the time to download chunk Y will be reduced and the cost of coding and decoding is saved without introducing additional traffic.


## 5.3. Cache Policy

Network coding-enabled ICN (NC-ICN) will divide the content inton original blocks. For traditional NC-ICN, each coded block is a linear combination of the n original blocks. The n coded blocks will be cached by n′ (n′≥n) CRs along their forwarding paths to a group of consumers. Figure 3(a) shows that for traditional NC-ICN, network N1 will provide m coded blocks, cb1,…,cbm, to consumers in group G1 and network N2 will provide the remaining n−m coded blocks. During the process of responding to consumers in group G1, m′ (m′≥m) coded blocks generated by cb1,…,cbm will be cached by multiple CRs in network N1, while n′ (n′≥n−m) coded blocks will be cached by multiple CRs in network N2. At a later time, when the consumers in G2 multicast their Interests for n coded blocks of content p, these Interests will be received first by CRs in network N1. Each CR will respond to the Interest with its cached coded blocks independently, and thus tt>m coded blocks cached in network N1 may be provided to consumers in G2. However, the maximum number of independent coded blocks that a consumer can receive from network N1 is m. In this case, at least t−m blocks are not beneficial to the consumer and are a waste of resources. Therefore, the conventional in-network caching strategy is not suitable for NC-ICN.Figure 3
Caching. (a) Caching in ICN. (b) Caching in RSCB.
(a)(b)To address this issue, we propose to introduce a simple cache mechanism to guarantee that the blocks provided to consumers will be independent. In RSCB, only original blocks and coded-from-original blocks will be cached by CRs. None of coded blocks that were encoded by other coded blocks can be cached in the network. The received/decoded original blocks can be cached by any CR. The coded-from-original blocks can only be cached by a single CR, which is the immediate downstream neighbor of the CR that generated the block. Thus, anyn coded-from-original blocks cached in the network will be linearly independent, where n is the number of blocks required to recover the content. Fq in data packet Dp,S,block,Fq is a caching flag that indicates whether the block is cacheable or not.Since CRs have limited storage capacity, a cache replacement policy is required. When cache replacement occurs, the candidate contentp that is to be discarded is selected using the existing content-level cache replacement policy, e.g., least recently used (LRU). Assume t units of cache space are required to cache newly received/decoded blocks and the cache space used to cache the candidate content p is n units (one unit for each block). If t≥n, content p is deleted and t=t−n. The first step is repeated until only some of cached blocks of the candidate content pi need to be discarded to cache new blocks, i.e., t<ni. Chunk-level cache replacement is then introduced to discard blocks in content pi. Firstly, any original blocks that are contained in the cached coded-from-original blocks are discarded, i.e., the information contained in the original blocks ob1 and ob2 may also be contained in the coded-from-original blocks ocb1=α11ob1+α12ob2. Secondly, the remaining original blocks are coded into a single coded-from-original block. Finally, the received coded-from-original blocks are randomly discarded. These three steps are performed in turn until there is sufficient space for the newly received/decoded blocks, as described in Algorithm 5. The complexity of Algorithm 5 is On, where n is the number of evicted content. If content is rarely accessed, only the coded-from-original blocks will be cached to respond to future Interests. Since a single coded-from-original block can respond to an aggregated Interest containing multiple requests for different chunks sent by multiple consumers, our chunk-level cache replacement policy can effectively increase the cache efficiency.Algorithm 5: Cache replacement strategy.
Input:t newly received/decoded blocks(1)
Determine the candidate contentp with n blocks using LRU;(2)
ift≥nthen(3)
Lett=t−n;(4)
Discard contentp;(5)
ift>0then(6)
go to step 1;(7)
end if(8)
else(9)
Discard then1 original blocks which are contained in the coded-from-original blocks;(10)
LetΔt1=t−n1;(11)
ifΔt1>0then(12)
Encode the remainingn2 original blocks into a single coded blocks;(13)
LetΔt2=Δt1−n2+1;(14)
ifΔt2>0then(15)
Randomly discardΔt2 received coded-from-original blocks;(16)
end if(17)
end if(18)
end if(19)
Cache the newly received/decoded blocks into the CS;


## 6. Simulation

In this section, the performance of our model is investigated by comparison with other three schemes: chunk-level CCN strategy (CCN) [4], NC-CCN [21], and CodingCache (CC) [16]. The caching strategy leave copy everywhere (LCE) is incorporated into the above strategies. In LCE, each block or chunk is cached by all CRs on the forwarding path between the content provider and the consumer.


### 6.1. Simulation Model

BRITE [27, 28] was used to generate the network topology, since it can roughly reflect the actual Internet topology. The Dijkstra algorithm was used to generate the FIB tables. All links have a bandwidth of 1 Gbps. There were a total of 1000 end hosts that were connected to 100 CRs and 10 original content providers were randomly connected to the CRs. 10,000 files were equally partitioned into 400 classes. Each content packet was 1 GB and was divided into 10 generations with each generation containing 10 chunks; each chunk size was 10 MB. In our simulation, only chunks in the same generation could be encoded. The content popularity follows a Zipf distribution with α∈0.3,0.7,1,1.5,2. Interests sent by consumers follow a Poisson process. The request number was defined as the number of Interests sent by consumers during the processing period. In our simulations, each CR was equally configured to have a cache space of 0.1%, 0.25%, 0.5%, 1%, and 2% of the overall content catalog size. The default cache size of each CR was set to 10 GB for caching, i.e., 1% of the total content catalog size. Random linear network coding (RLNC) was used for coding. The size of a finite field was 28 [29]. The coefficient vector and the generation ID are contained within the signed info field of the data packet. The performance of all four strategies was evaluated under the same simulation environment.The following parameters were used for the evaluation:(i)
Average download time: the average time for consumers to download each successfully received content request response.(ii)
Average number of hops: the average number of hops for each successfully received chunk from the provider to the consumer.(iii)
Cache hit ratio: the ratio of the number of Interests that were satisfied by the caches to the number of Interests that were satisfied by either the caches or the server.(iv)
Server hit reduction ratioγt:(7)γt=∑i=1NtwitNt,wherewit=0 if the chunk i is sent from a cache or an aggregated Interest; otherwise, wit=1. Nt is the number of chunks received by all consumers. t indicates that the data were collected from time t−Δt to t [20].(v)
Traffic: the total traffic to deliver the data packets over the whole request process.(vi)
Average number of Interests: the average number of Interest packets that were handled by each CR for each chunk that was successfully received by the consumer, as in [21].


### 6.2. Simulation Results

Due to its network coding-based content delivery and caching strategies, our proposed RSCB always achieves the best performance in terms of having the shortest average download time, the highest cache hit ratio, the lowest server hit reduction ratio, and the lowest transmission volume. RSCB ensures that consumers will receive sufficient independent coded blocks within a single round and the coded blocks cached by the CRs can be used as multiple chunks.Figure4 plots the average download time of the four caching strategies for different system parameters. The average download time decreases as the Zipf parameter α is increased, as shown in Figure 4(a), since a larger Zipf parameter α indicates that the Interests sent by consumers are concentrated on a smaller set of contents. As the number of requests increases, chunks that have already been requested will be cached on more CRs and thus consumers can retrieve chunks directly from the CRs, which are much closer to the consumers. Therefore, the average download time will be reduced (Figure 4(b)). RSCB performs much better even for a small Zipf parameter and a low number of Interests, since it can retrieve chunks or coded blocks from multiple CRs simultaneously. Compared with other schemes, RSCB provides consumers with enough independent coded blocks in a single round.Figure 4
Average download time. (a) Zipf parameter VS average download time. (b) Request numbers VS average download time.
(a)(b)In RSCB, one coded-from-original block can be used to respond to an aggregated Interest for multiple chunks requested by different consumers. For instance, the coded-from-original block,ocb1=α11ob1+α12ob2, can satisfy the Interest for chunk ob1 from consumer 1 and the Interest for chunk ob2 from consumer 2, as shown in Figure 1(b). Thus, RSCB achieves the best caching performance, in terms of average download hops (Figure 5), cache hit ratio (Figure 6), and server hit reduction ratio (Figure 7).Figure 5
Average number of hops. (a) Zipf parameter VS average number of hops. (b) Request numbers VS average number of hops.
(a)(b)Figure 6
Cache hit ratio. (a) Zipf parameter VS cache hit ratio. (b) Cache size VS cache hit ratio.
(a)(b)Figure 7
Server hit reduction ratio.Figure8 shows the traffic for different caching schemes, and it can be seen that RSCB has the lowest transmission volume. Moreover, we can see that as the number of requests increases, RSCB has a higher traffic saving too due to its Interest aggregation scheme which saves on traffic required to deliver n−n1+n2 blocks, as per equation (3).Figure 8
Traffic. (a) Zipf parameter VS transmission amount. (b) Request numbers VS transmission amount.
(a)(b)RSCB can also aggregate Interests for different chunks into a single Interest. As shown in Figure9, the average number of Interests processed by the CR is much lower compared with other schemes. In ICN, a consumer requests content with N chunks by sending out N Interests, and thus the CR needs to process N Interests. However, in RSCB, only one aggregated Interest containing several Interests will be processed by the CR. This can reduce the cost of transmitting and processing the Interest.Figure 9
Average number of Interests. (a) Zipf parameter VS average number of Interests. (b) Request numbers VS average number of Interests.
(a)(b)


## 6.1. Simulation Model

BRITE [27, 28] was used to generate the network topology, since it can roughly reflect the actual Internet topology. The Dijkstra algorithm was used to generate the FIB tables. All links have a bandwidth of 1 Gbps. There were a total of 1000 end hosts that were connected to 100 CRs and 10 original content providers were randomly connected to the CRs. 10,000 files were equally partitioned into 400 classes. Each content packet was 1 GB and was divided into 10 generations with each generation containing 10 chunks; each chunk size was 10 MB. In our simulation, only chunks in the same generation could be encoded. The content popularity follows a Zipf distribution with α∈0.3,0.7,1,1.5,2. Interests sent by consumers follow a Poisson process. The request number was defined as the number of Interests sent by consumers during the processing period. In our simulations, each CR was equally configured to have a cache space of 0.1%, 0.25%, 0.5%, 1%, and 2% of the overall content catalog size. The default cache size of each CR was set to 10 GB for caching, i.e., 1% of the total content catalog size. Random linear network coding (RLNC) was used for coding. The size of a finite field was 28 [29]. The coefficient vector and the generation ID are contained within the signed info field of the data packet. The performance of all four strategies was evaluated under the same simulation environment.The following parameters were used for the evaluation:(i)
Average download time: the average time for consumers to download each successfully received content request response.(ii)
Average number of hops: the average number of hops for each successfully received chunk from the provider to the consumer.(iii)
Cache hit ratio: the ratio of the number of Interests that were satisfied by the caches to the number of Interests that were satisfied by either the caches or the server.(iv)
Server hit reduction ratioγt:(7)γt=∑i=1NtwitNt,wherewit=0 if the chunk i is sent from a cache or an aggregated Interest; otherwise, wit=1. Nt is the number of chunks received by all consumers. t indicates that the data were collected from time t−Δt to t [20].(v)
Traffic: the total traffic to deliver the data packets over the whole request process.(vi)
Average number of Interests: the average number of Interest packets that were handled by each CR for each chunk that was successfully received by the consumer, as in [21].


## 6.2. Simulation Results

Due to its network coding-based content delivery and caching strategies, our proposed RSCB always achieves the best performance in terms of having the shortest average download time, the highest cache hit ratio, the lowest server hit reduction ratio, and the lowest transmission volume. RSCB ensures that consumers will receive sufficient independent coded blocks within a single round and the coded blocks cached by the CRs can be used as multiple chunks.Figure4 plots the average download time of the four caching strategies for different system parameters. The average download time decreases as the Zipf parameter α is increased, as shown in Figure 4(a), since a larger Zipf parameter α indicates that the Interests sent by consumers are concentrated on a smaller set of contents. As the number of requests increases, chunks that have already been requested will be cached on more CRs and thus consumers can retrieve chunks directly from the CRs, which are much closer to the consumers. Therefore, the average download time will be reduced (Figure 4(b)). RSCB performs much better even for a small Zipf parameter and a low number of Interests, since it can retrieve chunks or coded blocks from multiple CRs simultaneously. Compared with other schemes, RSCB provides consumers with enough independent coded blocks in a single round.Figure 4
Average download time. (a) Zipf parameter VS average download time. (b) Request numbers VS average download time.
(a)(b)In RSCB, one coded-from-original block can be used to respond to an aggregated Interest for multiple chunks requested by different consumers. For instance, the coded-from-original block,ocb1=α11ob1+α12ob2, can satisfy the Interest for chunk ob1 from consumer 1 and the Interest for chunk ob2 from consumer 2, as shown in Figure 1(b). Thus, RSCB achieves the best caching performance, in terms of average download hops (Figure 5), cache hit ratio (Figure 6), and server hit reduction ratio (Figure 7).Figure 5
Average number of hops. (a) Zipf parameter VS average number of hops. (b) Request numbers VS average number of hops.
(a)(b)Figure 6
Cache hit ratio. (a) Zipf parameter VS cache hit ratio. (b) Cache size VS cache hit ratio.
(a)(b)Figure 7
Server hit reduction ratio.Figure8 shows the traffic for different caching schemes, and it can be seen that RSCB has the lowest transmission volume. Moreover, we can see that as the number of requests increases, RSCB has a higher traffic saving too due to its Interest aggregation scheme which saves on traffic required to deliver n−n1+n2 blocks, as per equation (3).Figure 8
Traffic. (a) Zipf parameter VS transmission amount. (b) Request numbers VS transmission amount.
(a)(b)RSCB can also aggregate Interests for different chunks into a single Interest. As shown in Figure9, the average number of Interests processed by the CR is much lower compared with other schemes. In ICN, a consumer requests content with N chunks by sending out N Interests, and thus the CR needs to process N Interests. However, in RSCB, only one aggregated Interest containing several Interests will be processed by the CR. This can reduce the cost of transmitting and processing the Interest.Figure 9
Average number of Interests. (a) Zipf parameter VS average number of Interests. (b) Request numbers VS average number of Interests.
(a)(b)


## 7. Conclusion and Discussion

In this paper, we have proposed a request-specific coded-block strategy to reduce the transmission volume. Additionally, a chunk-level on-path non-cooperative coded caching and replacing strategy has been proposed to improve the caching efficiency. Our method enables a consumer to multicast a set of Interests in order to obtain multiple content chunks simultaneously from multiple CRs. The traffic can be reduced by encoding chunks that meet in an intermediate CR and have been requested by different consumers. A novel Interest forwarding-responding strategy has been proposed to guarantee that the minimum number of coded blocks will be requested and that the blocks will be linearly independent. A network coding-based caching and replacing mechanism has been designed to guarantee that the cached blocks can be reused. A chunk-level coded cache replacement strategy has been proposed to discard blocks. Rather than discarding the original blocks, the CR will encode the original blocks into a single coded-from-original block to release cache space when cache replacement is required. A single coded-from-original block can satisfy multiple Interests from different consumers for a set of its component original blocks. Therefore, this will increase the caching diversity without requiring extra cache space. The simulation results have confirmed that the RSCB scheme outperforms the other three strategies.However, although there are many benefits in deploying network coding in ICN, it also introduces some additional costs for computation and communication. Some studies have already proven that RLNC is a practical method which has acceptable costs. Since ICN is a new architecture, there are still many issues that need to be resolved before ICN can be deployed, such as efficient operation of PIT and FIB at a chunk level [30, 31].



---

*Source: 3838547-2020-06-10.xml*