CN108173965A - Community-aware ICN caching method - Google Patents

Abstract

A community-aware ICN caching method belongs to the technical field of computers and relates to storing, transmitting and processing digital information. As new applications continue to emerge, the way traffic is generated and delivered will fundamentally change, with the majority of traffic coming from user-driven content acquisition applications. The invention is a community-aware ICN caching strategy (SCCNC). Nodes with different node community importance adopt different caching decisions and caching replacement strategies, so that the caching content is more reasonable in terms of time and space distribution. Introduce network coding into cache decision-making and cache replacement strategy to improve cache hit rate and cache diversity without increasing cache space. The SCCNC strategy was simulated and verified under various experimental conditions, and the results showed that compared with the other three cache strategies, this strategy can better improve the network including cache hit rate, hop reduction rate, average download time, etc. Cache performance.

Description

Community-aware ICN caching method

technical field

The invention belongs to the technical field of computers, and in particular relates to a method used in storing, transmitting and processing digital information.

Background technique

In recent years, with the continuous emergence of new applications, the way traffic is generated and transmitted will also undergo a fundamental change. Most of the traffic comes from user-driven content acquisition applications. Content distribution and acquisition have become the main applications of the Internet, which makes the current TCP/IP network architecture based on end-to-end communication encounter unprecedented challenges. In order to meet the needs of users and applications and enhance the mobility, security and scalability of the Internet architecture, domestic and foreign researchers have proposed a series of new network architectures centered on information or content.

Content-centric networking (Content Centric Networking, abbreviated as CCN) is recognized as the most promising ICN network architecture. In CCN, there are two types of data packets: Interest packets and Data packets. The user requests a certain content by sending an Interest, and any node that receives the Interest and has the content can respond to the Interest by sending a Data packet carrying the content. The nodes along the way record the forwarding path of the Interest, so that the Data packet can return to the user along the forwarding path of the Interest. When the intermediate node receives the Data packet, it caches the content in the local cache so as to respond to subsequent requests.

In order to alleviate the huge pressure on the network bandwidth caused by the rapid growth of network traffic, ICN adds a cache function to the nodes of the entire network to make content closer to users and reduce network traffic. The caching strategy determines the spatiotemporal distribution of content in the network and affects the traffic behavior of the network. The original cache strategy in ICN is LCE (Leave Copy Everywhere), that is, each node in the network caches the received content, which will cause great cache redundancy. For this reason, researchers at home and abroad have proposed a variety of caching mechanisms. The existing caching mechanism mainly has the following problems: (1) Most of the cache locations are from a global perspective, while the purpose of caching is to meet the needs of local users; (2) In terms of replacement strategies, each node uses the same Replacement strategy, resulting in homogenization of cached content. For this reason, the present invention proposes a community-aware caching and caching replacement strategy (SCCNC), so that content with different popularity can be more reasonably distributed in the network.

In recent years, many scholars believe that introducing network coding into ICN can improve network performance. However, due to ICN's in-network caching mechanism, the same encoded block may be cached by multiple nodes on the forwarding path. The same or linearly related coded blocks may respond to the same user, causing the user to receive linearly related coded blocks that cannot be decoded. In order to avoid responding to the same user with the same or linearly related coded blocks, the nodes on the way only cache the original blocks, and the received coded blocks can only be used once, and cannot be cached by the node to respond to subsequent requests.

Some studies have shown that the Internet network topology presents community characteristics, that is, the nodes within a community are relatively closely connected, and the nodes between communities are relatively sparsely connected. In the same community, nodes with high importance of the node community are not only easily accessed by nodes within the community, but also easily accessed by nodes outside the community. Therefore, in SCCNC, the original content block is cached at the node with the highest node community importance in each community it passes through, and the coded block is cached at the node with lower node community importance. Doing so can not only improve the cache efficiency of the network, save the cache space of the network, but also make the distribution of content with different popularity more even and reasonable in the network space. When the cache space is exhausted, in each community, different nodes adopt different cache replacement strategies to replace the cache content with a certain probability. The replacement probability depends on the node community importance of the node and the popularity of the cache content to achieve Reasonable distribution of cached content over time. At the same time, the present invention proposes a cache replacement strategy that uses encoding instead of removal to improve cache content diversity and cache hit rate without increasing node cache space.

Related job introduction

Caching technology has been widely used in Web, P2P and CDN. However, traditional caching mechanisms are designed for specific network scenarios and cannot be directly transplanted into ICN. It is an important feature of ICN to increase the cache in the nodes of the whole network. The cache strategy and cache replacement strategy determine the temporal and spatial distribution of content in the network and affect network performance. Most of the current research focuses on caching strategies, which determine cache objects and cache locations. In the original ICN proposal, the LCE (LeaveCopy Everywhere) strategy is adopted, that is, the content is cached by all nodes on the forwarding path, which will cause great cache redundancy. Current caching strategies can be divided into two categories: explicit cooperative caching and implicit cooperative caching. An explicit cooperative caching strategy computes cache nodes based on content access patterns, cache network topology, and state information for each cache. In the literature, a hash function-based collaborative caching strategy (CINC) is introduced, in which each node exchanges information with its neighbors within two hops and assigns labels to itself and its neighbors. When the node receives the Data packet, it uses the hash function to determine the cache location of the content, which can reduce the cache redundancy in the network. SainoL et al. proposed three hash routing and caching mechanisms in ICN, namely symmetric, asymmetric, and multicast hash routing. The main idea is: use the hash function to calculate the cache node, and only cache the content on this node. When a user requests content, Interest is routed directly to the cache node instead of the content server. Combining content space partitioning with hash routing, WANG et al. proposed a cooperative intra-network caching strategy to achieve efficient cooperative caching, but it would bring high communication overhead.

In an implicit cooperative caching strategy, each node independently decides whether to cache received content. In the literature, each node on the content forwarding path caches the content with a certain probability. The caching probability is related to the location of the node. The closer the node is to the user, the higher the probability of caching the content, so that the content can be quickly pushed to the edge of the network. CHAI and others proposed a selective caching mechanism based on betweenness, which caches content at the node with the largest betweenness on the forwarding path of Interest, so as to improve the cache hit rate and reduce the number of replacements. In the literature, the author proposes a caching strategy based on the popularity of content blocks, which caches content blocks with high popularity in edge routers. WAVE is a caching mechanism based on content popularity, which adjusts the number of content blocks cached by each node according to content popularity. As the number of requests increases, the number of content block caches grows exponentially.

Random network coding is proved to be a technique suitable for multicast networks and can save transmission bandwidth. However, there are very few researches on the application of ICN, and the urgent problem to be solved is "how to ensure that the user receives enough linearly independent coding blocks to decode the original content". Wang et al. proposed a network coding and content caching scheme to realize ICN on software-defined network. As the central controller, the SDN controller determines how to optimally cache the requested content block to a node close to the user according to the statistical data about the request obtained by each switch, so that the total amount of data transmission is as small as possible. The literature considers how to perform network-wide optimal caching and transmission of requested content blocks and coded blocks according to ICN network topology, cache capacity, and link capacity. However, it does not specify how to implement the scheme in the ICN network, but only theoretically discusses how to optimize and how to reduce the amount of calculation required. WU et al. proposed CodingCache to improve CCN caching efficiency through network coding and random forwarding. The process of CodingCache obtaining coding blocks is actually obtained in a block-by-block manner, because it must put the coefficient vectors of the obtained coding blocks in the request, so that the node receiving the request can provide the next linearly independent code block. Its limitation is that if a user wants to obtain N coding blocks, N round-trip delays are required, and the interests of different users cannot be combined.

In order to realize the reasonable distribution of content with different popularity in the network, the present invention proposes a caching strategy and caching replacement strategy (SCCNC) based on node community importance, which uses network coding to save cache space and improve cache efficiency. In SCCNC, the community is used as the unit, the node with high community importance caches the original block, and other nodes cache the coded block. In the cache replacement mechanism, for different nodes, different cache replacement strategies are adopted to make the content more reasonable in time and space distribution.

Contents of the invention

Technical scheme of the present invention:

1. Definition of node community importance

The present invention will determine the cache position of the content in the ICN network based on the local importance of the node-the importance of the node community. The eigenspectrum of the network adjacency matrix can clearly reflect the number of communities in the network, for example, a network composed of c communities, then the adjacency matrix of the network will have c eigenvalues that are much larger than other eigenvalues, and these eigenvalues can be used as quantitative network An important indicator of community structure. Therefore, the network community strength is defined as: Among them, λ ₁ , λ ₂ ,..., λ _c represent the first c eigenvalues in descending order in the adjacency matrix eigenvalues. When node k leaves the network, the community structure and the eigenvalues of the adjacency matrix of the entire network will change accordingly, namely Therefore, the importance of node k to the characteristics of the network community is P _k =PP'. The approximate solution of node community importance can be obtained by using the perturbation theory, such as formula (1).

Among them, c is the number of communities in the network, v _i represents the i-th eigenvector of the adjacency matrix constructed with the routers in the network as nodes and the physical links between routers as edges, and v _ik represents the i-th eigenvector in the eigenvector v _i k elements. The larger the value of _Pk , the more important node k is in the community it belongs to, that is, the easier it will be for other nodes inside and outside the community to visit this node. For a network with n nodes and c communities, there is In order to make the sum of the measured parameters equal to 1, define

I _k ＝P _k /c, satisfy Before applying I, the value of the community number c in the network needs to be known in advance. The invention utilizes the spectrum characteristic of the network to directly determine the number of network communities. If c is given, this method does not need to divide the network into communities, avoids the calculation of complex community divisions, and can directly describe the importance of nodes to communities. According to formula (1), to calculate the community importance of each node, only all the eigenvalues and eigenvectors of the adjacency matrix representing the connection relationship of network nodes are required. However, most networks in reality are sparse networks. Using Lanczos algorithm and QL algorithm, the time complexity of finding all eigenvalues and eigenvectors of sparse symmetric matrices is O(nm), where n and m represent the number of nodes and The number of sides is relatively low, which is suitable for practical applications.

2. Interest packet and Data packet forwarding mechanism

In SCCNC, Interest records the maximum value of the node community importance in each community on its forwarding path, namely {I _1max , I _2max ,…,I _imax }, where I _imax represents the i-th community on the Interest forwarding path The maximum value of node importance. When Data returns to the user along the Interest forwarding path, the intermediate node formulates a corresponding caching scheme by comparing its own node importance I _ij with the maximum value of the community's node importance carried by Data, I _imax . The present invention designs an Interest merging mechanism for merging multiple Interests received by nodes, with the purpose of reducing the communication overhead of Interest packets and Data packets. When the node N _j receives the Interest, it compares its own node importance I _ij with the maximum value I _imax of the current community importance carried in the Interest, and if I _ij >I _imax , then set I _imax =I _ij . When Interest is forwarded to a new community i, the first node N _i1 encountered (denoted as FN) records the maximum value of node importance in the downstream community, namely I _(i-1)max . In this way, Interest only needs to carry the maximum value of the node importance of the current community, so as to reduce the communication overhead of Interest. As shown in Figure 1, when node N ₂₁ in community 2 receives Interest(p,p ₁ ,I ₄ ), it replaces the maximum value of node community importance in Interest, I ₄ , with its own node community importance I ₂₁ , and then Forward the new Interest, namely Interest(p,p ₁ ,I ₂₁ ), to the upstream node, and create a new PIT entry record Interest(p,p ₁ ,I ₄ ).

When node Nj receives Interest from interface k, it first checks its PIT table. Each PIT entry is a quintuple, as shown in Table 1:

<ContentName,ChunkID,Faces,Iimax,I _(i-1)max >

Among them, "ContentName" is the name of the content, "ChunkID" is the name of the content block, "Faces" is the interface number that received the Interest, "Iimax" is the maximum value of the node importance of the current community ci on the forwarding path of the Interest, "I _(i-1)max ” is the maximum value of the node importance of the upstream and downstream community ci _-1 of the Interest forwarding path, only the FN record I _(i-1)max in the current community ci. If there is already a corresponding entry in the PIT, merge the newly arrived Interest with it and discard the Interest; otherwise, create a new PIT entry. Algorithm 1 describes the forwarding process of Interest.

Algorithm 1Interest forwarding process

Table 1 Extended PIT table

Table 1Extended PIT table

In SCCNC, the Data packet carries the node community importance information extracted from the Interest or PIT table, I _imax , and returns to the user along the Interest forwarding path. When the intermediate node receives the Data packet, it compares its own node community importance I _ik with the maximum node community importance I _imax carried by the Data packet, and formulates a corresponding caching strategy according to the comparison result. The pseudocode of the forwarding process of the Data packet is shown in Algorithm 2.

Algorithm 2Data forwarding process

3. Cache mechanism based on network coding

Taking the community as the unit, in the same community, different caching strategies are formulated according to the community importance of each node on the Interest forwarding path: the node with the highest importance caches the original content block, because the node with high importance is more likely to be used by other nodes Access; nodes with low importance cache coded blocks to save cache space and improve cache diversity. When the node N _j receives the Data packet, and the Data packet carries the original content block D of the content p, it compares its own node importance I _ij with the current community importance I max carried in _Data , If I _ij =I _imax , store the content block in the local cache. Otherwise, check whether there is a content block D' of content p in the local cache CS, and if it exists, perform random network coding on D and D' to generate a new coded block D", and replace D' with D". Applying network coding to the cache, one coding block contains information of multiple content blocks, and can respond to requests for multiple content blocks. The caching mechanism realizes a reasonable distribution of caches in the network space, reduces network delays, and improves network transmission efficiency. The pseudocode of the caching mechanism is shown in Algorithm 3.

Algorithm 3 SCCNC cache strategy

When an Data(I _imax )arrived

4. Cache replacement strategy based on network coding

In SCCNC, the community is used as the unit, and different cache replacement strategies are implemented in the same community according to the importance of each node's community. Nodes with high importance in the node community have a high probability of replacing cached content with low popularity; while nodes with low importance in the node community have a high probability of replacing cached content with high popularity, which can realize caching in time and space reasonable distribution.

Suppose the node community importance of node N _j of community i is I _ij , and the average node importance in community i is When the cache is exhausted, first use LRU (Least Recently Used) to sort the cache content and build a cache sequence. The probability that the kth content is removed is

In the formula: α is the normalization factor, which satisfies the formula (3), and β is the probability adjustment coefficient.

When the cache replacement occurs, assuming that the content p is the content to be removed, if n original blocks are cached, random network coding is performed on the n original blocks to generate an encoded block, cache the encoded block, and remove n original block. The advantage of doing this is that the cache space of n-1 content blocks can be released, and at the same time, the information of n content blocks can be reserved to respond to subsequent requests.

Description of drawings

Fig. 1 is the example structural diagram of SCCNC of the present invention;

Fig. 2 is an average download time coordinate diagram of the present invention;

Fig. 3 is a cache hit rate coordinate diagram of the present invention;

Fig. 4 is a coordinate diagram of server hit reduction rate of the present invention;

Fig. 5 is a coordinate diagram of the hop reduction rate of the present invention;

Fig. 6 is a coordinate diagram of transmission flow in the present invention.

Detailed ways

Simulation experiment and analysis

The network topology in the simulation experiment comes from BRITE ^[25][26] , the network contains 100 nodes, the average node degree is 4, and the link bandwidth is 1Gbps. The present invention uses BRITE to generate various network topologies, performs multiple simulation experiments, and obtains similar simulation results. The network uses the Dijkstra algorithm as a routing mechanism. 4,000 pieces of content with a size of 1GB are randomly stored on 10 content servers, and each content is divided into 100 content blocks, of which 10 content blocks are one generation. We use intra-generation random linear network coding, and the encoding and decoding process only occurs in the between content blocks of the same generation. Content popularity obeys Zipf distribution, where α∈[0.7,1,1.5,2]. The user's request process for content follows a Poisson distribution. The present invention compares SCCNC with the following three mechanisms: NC-CCN ^[16] , CodingCache (CC) ^[17] and Leave Copy Down (LCD) ^[27] .

The present invention compares the performance of these four mechanisms from the following aspects:

●Average download time: The average download time refers to the average time required by each user from sending the first Interest to receiving the last content block.

●Cache hit rate: The cache hit rate is an important index to measure the performance of the cache, which is defined as the probability that the cache responds to the Interest instead of the content server. The higher the cache hit rate, the higher the cache efficiency of the network.

●Server hit reduction rate γ(t): If the request for content block i is responded by the cache, then ω _i (t)=0, otherwise ω _i (t)=1. N(t) represents the total amount of content blocks received by users in the time interval [t-Δ,t].

·Download hop reduction rate β(t): In the formula, h _i (t) is the number of hops actually experienced by the content block i from the cache hit node to the requester, and H _i (t) is the hop number of the content block i from the content server to the requester. If a request for content block i is responded to by a content server, then h _i (t) = H _i (t).

●Transmission traffic: Transmission traffic is defined as the data volume of Data packets transmitted by the network during the entire process from the first user sending Interest to the last user receiving the last content block.

From the experimental results, compared with the other three mechanisms, SCCNC can save the content download time, the amount of data transmitted over the network, improve the cache hit rate, and reduce the server load.

Figure 3 shows the experimental results of the average download time of the four caching schemes under different parameters. The average download time of the four mechanisms decreases with the increase of the Zipf parameter α, as shown in Fig. 3(a). This is because the larger the Zipf parameter α, the more concentrated the user's preference, and the request sent by the user is concentrated on a small part of the content, making this part of the content cached in the network more and more, and closer to the user. Similarly, the more user requests, the more cached content in the network, so the average download time of the four mechanisms decreases as the number of user requests increases, as shown in Figure 3(b). We can see that the SCCNC mechanism has always maintained a clear advantage, and this advantage is especially obvious in the case of a smaller Zipf parameter α and fewer user requests. This is because in SCCNC, original blocks are cached on nodes with high node community importance, which are more easily accessed by other nodes.

In SCCNC, nodes with low community importance cache code blocks, and one code block can be used as multiple content blocks to respond to requests from different users for different content blocks. For example, the coding block cb (cb=A⊕B) can satisfy different users' requests for content blocks A and B at the same time. Therefore, SCCNC can achieve higher cache hit ratio (as shown in Figure 4), lower server load reduction rate (as shown in Figure 5) and lower transmission traffic (as shown in Figure 7).

As shown in Figure 6, SCCNC has better performance than other caching schemes in terms of hop reduction rate. The reason is that each node in SCCNC makes different cache replacement decisions according to its node importance. When the cache is exhausted, encoding is used instead of removal to release cache space while retaining multiple content block information. The cache replacement strategy based on node community importance and network coding proposed by the present invention makes the distribution of content with different popularity more reasonable in time and space.

in conclusion

The present invention proposes a community-aware ICN cache strategy (SCCNC). Nodes with different node community importances adopt different cache decisions and cache replacement strategies to make cache content more reasonable in terms of time and space distribution. Introduce network coding into cache decision-making and cache replacement strategy to improve cache hit rate and cache diversity without increasing cache space. The present invention simulates and verifies the SCCNC strategy under various experimental conditions, and the results show that the strategy can better improve cache hit rate, hop reduction rate, average download time, etc. compared with other three cache strategies network cache performance.

Claims (4)

1. a kind of ICN caching methods that corporations perceive, it is characterized in that node part importance-node corporations importance will be based on Determining the cache location of content in ICN networks, the characteristic spectrum of network adjacent matrix can clearly reflect the number of corporations in network, Such as the network being made of c corporations, then the adjacency matrix of the network will have c characteristic value much larger than other feature value, these Characteristic value can as quantization network community structure important indicator, thus, network community strength definition is：Wherein λ₁,λ₂,…,λ_cRepresent the preceding c characteristic value arranged in descending order in adjacency matrix characteristic value.Work as section When point k leaves network, the community structure and adjacency matrix characteristic value of whole network will all change therewith, i.e.,So node k is P to the importance of network community characteristic_k=P-P ' can must be saved using perturbation theory The approximate solution of point corporations importance, such as formula (1)：

Wherein, c is corporations' number in network, v_iIt represents using the router in network as node, the physical link between router is The ith feature vector of the adjacency matrix of side structure, v_ikRepresent feature vector v_iIn k-th of element, P_kIt is worth bigger, node k More important in corporations belonging to it, i.e., the other node visits node inside and outside corporations will be easier, for n node, c The network of corporations, hasFor make measurement parameter and be 1, define I_k=P_k/ c meetsIt is applying Before I, the value of corporations' number c in network need to be known in advance, directly determine network community number using the spectral characteristic of network, such as Fruit c gives, and this method avoids the calculation amount that complicated corporations divide, can directly retouch without carrying out corporations' division to network State importance of the node to corporations.By formula (1), corporations' importance of each node is calculated, demand goes out to represent network node All characteristic values and feature vector of the adjacency matrix of connection relation, and most of network in reality is sparse network, is utilized Lanczos algorithms and QL algorithms, it is O (nm) to ask all characteristic values of sparse symmetrical matrix and the time complexity of feature vector, Wherein n and m represents the number of nodes and number of edges of network respectively, and calculation amount is suitable for practical application than relatively low.

2. the ICN caching methods that corporations according to claim 1 perceive, it is characterized in that Interest packets and the forwarding of Data packets Mechanism, in SCCNC, Interest records the maximum value of each corporations' interior joint corporations importance on its forward-path, i.e., {I_1max,I_2max,…,I_imax, wherein I_imaxRepresent the maximum of i-th of corporations' interior joint importance on Interest forward-paths Value.When Data returns to user along Interest forward-paths, intermediate node is by comparing the pitch point importance I of oneself_ijAnd The pitch point importance maximum value for the corporations that Data is carried, I_imax, formulate corresponding buffering scheme.Present invention design is a kind of Interest merges mechanism, the multiple Interest received for merge node, it is therefore an objective to reduce Interest packets and Data packets Communication overhead, as node N_jWhen receiving Interest, by the pitch point importance I of oneself_ijIt is current with being carried in Interest The importance maximum value I of corporations_imaxIt is compared, if I_ij>I_imax, then I is enabled_imax=I_ij, when Interest is forwarded to one During a new corporations i, first node N encountering_i1(being denoted as FN) records the pitch point importance maximum value of downstream corporations, i.e., I_(i-1)max, such Interest need to only carry the pitch point importance maximum value of current corporations, be opened with the communication for reducing Interest Pin, as the node N in corporations 2₂₁Receive Interest (p, p₁,I₄) when, with the node corporations importance I of oneself₂₁It replaces Interest interior joints corporations importance maximum value, I₄, then by new Interest, i.e. Interest (p, p₁,I₂₁), forwarding To upstream node, while create PIT program recording Interest (p, a p₁,I₄)；

As node N_jWhen receiving Interest from interface k, its PIT table is first checked for.Each PIT list items are a five-tuple, such as table Shown in 1：

<ContentName,ChunkID,Faces,I_imax,I_(i-1)max>

Wherein, " ContentName " is content name, and " ChunkID " is the name of content blocks, and " Faces " is to receive Interest Interface number, " I_imax" it is current corporations c on Interest forward-paths_iPitch point importance maximum value, " I_(i-1)max" be Interest forward-path upstream and downstream corporations c_i-1Pitch point importance maximum value, only current corporations c_iIn FN record I_(i-1)maxIf having corresponding list item in PIT, the Interest newly arrived is merged with it, while abandon the Interest； Otherwise, a PIT list item is created, algorithm 1 describes the repeating process of Interest.

3. the ICN caching methods that corporations according to claim 1 perceive, it is characterized in that the caching machine based on network code System as unit of corporations, in same corporations, is formulated different according to corporations' importance of node each on Interest forward-paths Cache policy：The highest nodal cache original contents block of importance, this is because the high node of importance be easier it is other Node visit；The low nodal cache encoding block of importance to save spatial cache, improves caching diversity.As node N_jIt receives Data packets, and when that carried in Data packets is the original contents block D of content p, by the pitch point importance I of oneself_ijWith being taken in Data The importance maximum value I of the current corporations of band_imaxIt is compared, if I_ij=I_imax, by content blocks storage to local cache In, whether otherwise, checking in local cache CS has the content blocks D ' of content p, if in the presence of to D and D ' carry out random network volumes Code generates new encoding block D ", and replaces D ' with D ", and network code is applied in caching, and an encoding block is included in multiple Hold the information of block, the request of multiple content blocks can be responded, which, which realizes, is buffered in rationally dividing in cyberspace Cloth reduces network delay, improves the efficiency of transmission of network.

4. the ICN caching methods that corporations according to claim 1 perceive, it is characterized in that the caching based on network code is replaced Strategy, in SCCNC, as unit of corporations, the node corporations importance in same corporations according to each node is different, performs difference Cache replacement policy, the big node of node corporations importance, the probability that the low cache contents of popularity are replaced is big；And node The small node of corporations' importance, the probability that the high cache contents of popularity are replaced is big, can realize in this way be buffered in the time and Reasonable layout spatially, it is assumed that the node N of corporations i_jNode corporations importance be I_ij, the average nodal in corporations i is important It spends and isWhen caching exhausts, cache contents are ranked up first with LRU (Least Recently Used), structure is slow Sequence is deposited, the probability that k-th of content is removed is

In formula：α is normalization factor, meets formula (3), and β is probability adjustment factor.

When caching, which is replaced, to be occurred, it is assumed that content p is content to be removed, original to n if caching is n original block Block carries out random network code, generates an encoding block, caches the encoding block, removes n original block, the advantage of doing so is that, The spatial cache of n-1 content blocks can be discharged, while retains the information of n content blocks, to respond subsequent request.