CN108900570B - A Cache Replacement Method Based on Content Value - Google Patents

Abstract

The invention discloses a cache replacement method based on content value, which includes statistics of the popularity of the content, calculation of the cache cost of each content, calculation of the time interval between the time when the content was last accessed and the current time, and the calculation of each content in the cache space. the value of each content and replace the minimum value of the value. The invention can not only cache the content with high popularity in advance, but also have a good response to the content with high cache cost, thereby effectively improving the accuracy of node data replacement, and helping to improve the data transmission efficiency of the content center network. Improve the user's online experience.

Description

A Cache Replacement Method Based on Content Value

technical field

The invention relates to a cache replacement method, in particular to a content value-based cache replacement method, and belongs to the technical field of communications.

Background technique

With the rapid development of Internet technology, the number of network information and users accessing the Internet has increased dramatically, resulting in an exponential increase in network traffic. , IP) network architecture brings great challenges and pressures. In order to solve the impact of huge data traffic in mobile networks, researchers have proposed a new content-centric network architecture—Content-Centric Networking (CCN). In the content-centric network, each node has a caching function. By caching popular content on nodes closer to the user for a long time, it can effectively relieve the pressure on the bandwidth of the backhaul link, reduce the network delay and improve the user experience. quality of experience.

However, the cache capacity of each node is limited. When the cache space is full, the less valuable content in the cache must be cleaned up according to a certain replacement strategy, and new meaningful data must be stored to improve the cache space. Request hit rate, it can be seen that reasonable management and replacement of cached content is the key to affecting the overall performance of the network.

Traditional cache replacement algorithms include first in first out (FIFO), least recently used (LFU), least recently used (LRU), and content size replacement ( SIZE) etc. Among them, FIFO replaces the data that first enters the cache space according to the first-in-first-out rule of the queue. This algorithm has low complexity and is easy to implement, but the request hit rate is low. The LRU algorithm always replaces the resources that have not been accessed for the longest time out of the cache, and considers that the recently accessed data has a higher probability of being accessed in the near future. The algorithm only considers the replacement data from the latest request time. When the content is popular and distributed When changes occur, adaptive performance decreases. By counting the access frequency of the cached content in the past period of time, the LFU replacement strategy considers that the resource with high frequency has a higher use value. Therefore, when the cache space is insufficient, the content with the lowest access frequency is always replaced. This algorithm also has cache pollution. The problem is that the content with high access frequency in the past still occupies the cache space even if it is no longer accessed now, resulting in a decrease in the utilization of the cache space. The SIZE algorithm replaces data according to the size of the content, and preferentially replaces data with a large number of bytes. However, this algorithm does not consider factors such as the access time interval and the number of cache hits, which may keep low-value small-byte objects for a long time. in the cache space, thereby reducing the hit rate.

The design of the above algorithms is slightly one-sided, and a single objective function is used to determine that the cache replacement object can no longer meet the diverse network data requirements. The LRU and LFU algorithms are combined with the least recently used and longest unused replacement algorithm (least frequently recently used, LFRU), which comprehensively considers the request frequency of the content and the time of recent access, but does not consider the global popularity of the content. The size-based Greedy-Dual Size (GDS) algorithm comprehensively considers the object size, the cache cost and the age factor of the content, sets a weight for each file in the cache space, and replaces the object with the smallest weight each time. Consider the number of times the cached object has been accessed in the past. MaT et al. proposed an improved weighted greedy dual size frequency (WGDSF) cache replacement strategy based on size frequency, which adds time-based weighted frequency parameters and weighted file type parameters to the GDS algorithm. , although the performance is improved, it also greatly increases the algorithm complexity. The Ant Colony Algorithm based Cache Replacement Algorithm (ACACRA) algorithm uses the size of the data object to represent the weight of the backpack, and the average number of times the object is requested to represent the storage value. Algorithm to determine the replacement content, but the algorithm has high complexity and is suitable for the application layer of the computer.

To sum up, how to reasonably replace the cached content under the condition of limited cache space is an urgent problem to be solved by those skilled in the art.

SUMMARY OF THE INVENTION

The purpose of the present invention is to solve the above-mentioned defects of the prior art, and provide a cache replacement method based on content value. The storage value of the object, when the cache space is insufficient, the data with the least value is replaced. This solution can effectively improve the cache hit rate and reduce the average number of hops for users to obtain data.

The technical solution of the present invention is:

A content value-based cache replacement method, characterized in that it comprises the following steps:

S1: Statistically update the popularity of the content in each cycle, and calculate the popularity of the content in the current cycle according to the popularity of the content in the previous cycle and the hit rate of the content in this cycle;

S2: Calculate the cache cost of each content according to the node, the cache cost includes the transmission cost and the cache cost, and the content transmission cost is greater than the cache cost; the calculation formula of the cache cost is:

表示内容r单跳的传输成本，

表示内容r的缓存成本；Among them, Hop _r represents the number of hops of content r from the origin server,

represents the single-hop transmission cost of content r,

represents the caching cost of content r;

S3: Design a time label in the cache space, and use the time label to record the time when the content was last accessed, and then calculate the time interval between the time when the content was last accessed and the current time;

S4: Calculate the value of each content in the cache space according to the popularity in step S1, the cache cost in step S2 and the latest access time interval in step S3, when the cache space is insufficient, the node will replace the minimum value of the value .

Preferably, the calculation formula of the popularity in the step S1 is:

p _r (t)= _αpr (t-1)+(1-α)h _r (t)

Among them, r is the number of the content in the cache space, _pr (t) represents the popularity of the content _r in the current cycle, pr (t-1) represents the popularity of the content r in the previous cycle, and α is the decay factor , is the proportion of the popularity of the previous cycle in the current cycle, 0<α<1, h _r (t) represents the hit rate of the content r in the current cycle, N _r (t) represents the content r in the current cycle The number of hits, N _Q (t) represents the total number of requests received by the node in the current cycle.

Preferably, the calculation formula of the time interval in the step S3 is:

t _inter =t _cur -t _old

Among them, t _inter represents the time interval between the time when the content was last accessed and the current time, t _cur represents the current time, and t _old represents the time when the content was last requested.

Preferably, the calculation formula of the value in the step S4 is:

其中value_r(t)为价值。

where value _r (t) is the value.

Preferably, the data packet types of the content in the step S1, the step S2, the step S3 and the step S4 include an interest packet and a data packet.

Preferably, the interest packet includes the name of the requested content, is sent by the requesting client, is transmitted to an adjacent node or source server with the requested resource, and generates a corresponding data packet;

The data packet includes the data object, the content name and the publisher's signature information, and is transmitted to the user along the reverse path of the interest packet.

Preferably, the nodes in step S2 and step S4 include a content storage, a forwarding information base and a pending request table.

Preferably, the content storage stores data on the arriving node, and the cached content satisfies future requests for the data; the target field of the forwarding information base is the prefix of the content name; the pending request table records the routing state information being transmitted.

The invention provides a cache replacement method based on content value, which can dynamically update the popularity of content according to the user's access behavior, and adjust the popularity of the content and the cache cost in real time by using the content request time interval in the value function. It can not only cache high-popularity content in advance, but also respond well to content with high cache cost, which effectively improves the accuracy of node data replacement and is conducive to improving the data transmission of content-centric networks. efficiency and improve the user's online experience.

The specific embodiments of the present invention will be further described in detail below in conjunction with the accompanying drawings of the embodiments, so as to make the technical solutions of the present invention easier to understand and grasp.

Description of drawings

1 is a flowchart of an embodiment of the present invention;

Fig. 2 is the processing flow chart of interest packet in the present invention;

FIG. 3 is a flow chart of the processing of data packets in the present invention.

Detailed ways

A cache replacement method based on content value, comprising the following steps:

S1: Statistically update the popularity of the content in each cycle, and calculate the popularity of the content in the current cycle according to the popularity of the content in the previous cycle and the hit rate of the cached content in this cycle;

The calculation formula of the popularity is: pr (t)= _αpr (t-1)+(1-α)h _r ( _t )

Among them, r is the number of the content in the cache space, _pr (t) is the popularity of the content _r in the current cycle, pr (t-1) is the popularity of the content r in the previous cycle, and α is the decay factor , is the proportion of the popularity of the previous cycle in the current cycle, 0<α<1, h _r (t) represents the hit rate of the content r in the current cycle, N _r (t) represents the content r in the current cycle The number of hits, N _Q (t) represents the total number of requests received by the node in the current cycle.

S2: Calculate the cache cost of each content according to the node; the cache cost includes the transmission cost and the cache cost, and the content transmission cost is greater than the cache cost; the calculation formula of the cache cost is:

表示内容r单跳的传输成本，

表示内容r的缓存成本。Among them, Hop _r represents the number of hops from the content r to the source server. The larger the Hop _r , the higher the transmission cost and the greater the storage value of the content.

represents the single-hop transmission cost of content r,

represents the caching cost of content r.

S3: Design a time label in the cache space, and use the time label to record the time when the content was last accessed, and then calculate the time interval between the time when the content was last accessed and the current time; the calculation formula of the time interval is: t _inter = t _cur - t _old , where t _inter represents the time interval between the time when the content was last accessed and the current time, t _cur represents the current time, and t _old represents the time when the content was last requested.

S4: Calculate the value of each content in the cache space according to the popularity in step S1, the cache cost in step S2 and the latest access time interval in step S3, when the cache space is insufficient, the node will replace the minimum value of the value . The formula for calculating the value is:

其中value_r(t)为价值。

where value _r (t) is the value.

In the technical solution of the present invention, the data packet types of the content in the step S1, the step S2, the step S3 and the step S4 include an interest packet (interest packet) and a data packet (data packet). The package includes the name of the requested content, is sent by the requesting client, is transmitted to the adjacent node or source server with the requested resource, and generates a corresponding data package; the data package includes the data object, the content name and the publisher's signature information, And along the reverse path of the Interest packet to the user.

The nodes in the step S2 and step S4 include a content store (Content Store, CS), a forwarding information base (Forwarding Information Base, FIB) and a pending request table (Pending Interest Table, PIT), and the content store stores the arrival node. The cached content satisfies future requests for the data; the target field of the forwarding information base is the prefix of the content name; the pending request table records the routing state information being transmitted.

In order to better illustrate the technical solutions of the present invention, the specific embodiments of the present invention are described in detail below with reference to the accompanying drawings.

CCN no longer cares where the content is stored, but only the data itself. The data packets in this structure are identified by the content name instead of the traditional IP address. CCN includes two types of data packets: interest packets and data packets. The interest packet is sent by the requesting client, which carries the name of the requested content, but does not include the destination address. After the interest packet is routed to the adjacent node or source server with the requested resource, a corresponding data packet is generated. The data packet carries the data object, The content name and the publisher's signature information, which is sent to the user along the reverse path of the Interest.

The nodes of CCN include CS, FIB and PIT. The CS stores the data objects that arrive at the node, and the cached content can be used to satisfy future requests for the data, thereby reducing the repeated transmission of content. The FIB is similar to the IP routing table in the traditional Transmission Control Protocol/Internet Protocol (TCP/IP) network architecture, but the target field is the prefix of the content name. PIT records routing state information that is being transmitted. As shown in Figure 1, when an interest packet arrives on the node, it will first check whether the content corresponding to the interest packet is stored in the CS. If so, the content will be sent directly to the requester along the arrival path of the interest packet, and discarded at the same time. the interest package. If there is no such content in the cache, the node will continue to check whether there is an entry corresponding to the content name in the PIT, if there is, add the request interface to the corresponding interface list, and then discard the request interest packet, otherwise create a new PIT Enter the entry and query the FIB, and forward the Interest packet to the adjacent CCN node according to the matching port. If there is no matching entry in the FIB, the Interest packet is discarded or forwarded to the default port.

As shown in Figure 2, when a data packet arrives, the node will query whether there is an entry corresponding to the content in the PIT, and if so, forward the data content from the interface list of the entry, delete the corresponding PIT entry, and then This data is stored in the CS according to the corresponding cache replacement policy.

In CCN, the popularity of content can well reflect the user's demand for content. Due to the time-varying data requests of users, the popularity of file content in the network always changes constantly. Over time, this part of the content is likely to become an object less visited by users, and its popularity declines. Therefore, affected by the user's access behavior, the popularity of the content stored on the nodes in the network changes dynamically, that is, the popularity of the content needs to be statistically updated in each cycle. In order to accurately predict its changes, this paper designs a counter for each content in the cache space in each router node to count the number of times the content is hit in each cycle, and design a total counter to count the number of nodes received of total requests. Then, based on the exponentially weighted moving average algorithm (EWMA), the popularity of the content in the current cycle is calculated according to the popularity of the content in the previous cycle and the hit rate of the content in the current cycle. The formula for calculating the popularity is: p _r (t)= αp _r (t-1)+(1-α)h _r (t)

Among them, r is the number of the content in the cache space, _pr (t) represents the popularity of the content _r in the current cycle, pr (t-1) represents the popularity of the content r in the previous cycle, and α is the decay factor , 0<α<1, it represents the proportion of the popularity of the previous cycle in the current cycle, hr (t) represents the hit rate of the content r in the current cycle, N _r (t) represents the content _r in the current cycle The number of hits, N _Q (t) represents the total number of requests received by the node in the current cycle.

The greater the number of hops between the node where the content is located and the content source server, the lower the number of hops for users to obtain the content. Therefore, during the cache replacement process, try to avoid replacing the content that is far away from the source server. The cache cost is mainly composed of two parts, the transmission cost and the cache cost. The calculation formula is:

表示内容r单跳的传输成本，

表示内容r的缓存成本，内容的传输成本远远大于其缓存成本。Among them, Hop _r represents the number of hops from the content r to the source server. The larger the Hop _r , the higher the transmission cost and the greater the storage value of the content.

represents the single-hop transmission cost of content r,

Represents the caching cost of the content r, and the transmission cost of the content is much greater than its caching cost.

The present invention designs a time label for each content in the node on the basis of the most recently unused replacement algorithm, which is used to record the time when the content was accessed most recently. Assuming that the current time is t _cur , the time when the content was last requested is t _old , then: t _inter =t _cur -t _old , the shorter the time interval t _inter , the higher the frequency of the content being requested in the current time period, the storage value of the content mainly depends on the popularity of the content, and When the interval t _inter is longer, the main factor that affects the value of content is the cache cost of the content, and the popularity of the content is a secondary factor. Based on the above analysis, the value formula of content is:

From the value formula of the content, it can be seen that if the data is frequently requested in a short period of time, then the time interval t _inter is very small, and the user's attention to the content is very high, indicating that the popularity of the data object is very high at this time. It is the main factor affecting the value of cached content. On the contrary, when the interval t _inter is large, it means that the content has been requested less recently and the popularity of the content has decreased. At this time, the cache cost of the content should be used as the main factor affecting the value function. factor, with content popularity as a secondary influencing factor. The cache replacement method uses the time interval when content is requested as a weight factor, and can adjust the proportion of data popularity and cache cost in the value function in real time, so that not only high popularity content can be cached in nodes, but also Data with high request cost also has a good response, making the data stored in the network more reasonable.

Figure 3 shows the specific algorithm flow in the present invention. When the node receives the user's request, it first determines whether the request object is in the CS. If it is in the content storage, the number of hits of the content and the total number of requests of the node are increased by 1. , update the request time of the content, and then send the content directly to the user. If the content is not cached on the node, the interest packet is forwarded, the content is obtained from the adjacent node or the origin server, and the content is sent to the user. Determine whether there is enough space on the node to cache the data object, if so, store the content in the CS, initialize the number of hits and request time of the content, and record the number of hops that the data packet takes to reach the node. If the cache space is insufficient, the value of each content is calculated according to the popularity of the content in the current cycle, the cache cost and the content request time interval, and the value is replaced from small to large until there is enough space to store the new content.

The invention provides a content value-based cache replacement method, which comprehensively considers the dynamic popularity of the content, the cache cost and the time recently requested, and constructs a more practical content value function, and according to the content value function, An effective content storage and replacement scheme is designed. Specifically, when the updated cached content does not match the existing content, the existing cached content is replaced according to the value from small to large. Compared with traditional algorithms, this method effectively improves the cache content hit rate of network nodes and reduces the average number of hops for users to obtain content.

It should be noted that the above-described embodiments illustrate rather than limit the invention, and that alternative embodiments may be devised by those skilled in the art without departing from the scope of the appended claims.

Claims (8)

1. A cache replacement method based on content value is characterized by comprising the following steps:

s1: counting and updating the popularity of the content in each period, and calculating the popularity of the content in the current period according to the popularity of the content in the last period and the hit rate of the content in the period;

s2: calculating the caching cost of each content according to the node, wherein the caching cost comprises transmission cost and caching cost, and the transmission cost of the content is greater than the caching cost; the calculation formula of the cache cost is as follows:

wherein, Hop_rRepresenting the number of hops the content r is from the origin server,

representing the transmission cost of a single hop of the content r,

represents the caching cost of the content r;

s3: designing a time tag in a cache space, recording the latest access time of the content by using the time tag, and then calculating the time interval between the latest access time of the content and the current time;

s4: according to the popularity in the step S1, the caching cost in the step S2 and the latest access time interval in the step S3, the value of each content in the caching space is calculated, and when the caching space is insufficient, the node replaces the minimum value of the value.

2. A content value-based cache replacement method according to claim 1, wherein: the calculation formula of the popularity in the step S1 is:

p_r(t)＝αp_r(t-1)+(1-α)h_r(t)

where r is the number of the content in the cache space, p_r(t) denotes the popularity of the content r in the current period, p_r(t-1) represents the popularity of the content r in the previous period, alpha is an attenuation factor, and is the proportion of the popularity of the previous period in the current period, 0 < alpha < 1, h_r(t) represents the hit rate of the content r in the current cycle, N_r(t) represents the number of hits on the content r in the current cycle, N_QAnd (t) represents the total number of requests received by the node in the current period.

3. A content value-based cache replacement method according to claim 1, wherein: the calculation formula of the time interval in step S3 is:

t_inter＝t_cur-t_old

wherein, t_interTime interval, t, representing the time at which the content was last accessed and the current time_curRepresenting the current time, t_oldIndicating the time at which the content was last requested.

4. A content value-based cache replacement method according to claim 1, wherein: the calculation formula of the value in step S4 is:

wherein value_r(t) is a value.

5. A content value-based cache replacement method according to claim 1, wherein: the packet types of the content in the step S1, the step S2, the step S3, and the step S4 include interest packets and data packets.

6. A content value-based cache replacement method according to claim 5, wherein: the interest packet comprises the name of the requested content, is sent by the requesting client, is transmitted to a neighboring node or an origin server with the requested resource, and generates a corresponding data packet;

the data package includes the data object, the content name, and the publisher's signature information and is transmitted to the user along the reverse path of the interest package.

7. A content value-based cache replacement method according to claim 1, wherein: the nodes in steps S2, S4 include a content store, a forwarding information base, and a pending request table.

8. A content value-based cache replacement method according to claim 7, wherein: the content memory stores data arriving at the node, and the cached content satisfies future requests for the data; the target field of the forwarding information base is a prefix of the content name; the pending request table records the routing state information being transmitted.

Images