CN110851658B - Tree index data structure, content storage pool, router and tree index method - Google Patents

Abstract

The invention discloses a tree-shaped index data structure, each node of which contains a right pointer pointing to the node of the same layer and a sub-pointer pointing to the node of the next layer; each data node stores the complete name of real data, Real data refers to the name data that goes directly to the route. The invention also discloses a content storage pool, which includes an on-chip storage unit and an off-chip storage unit, the on-chip storage unit is provided with a neural network model for storing mapping data and a bitmap for storing data information; the off-chip storage unit There are multiple above-mentioned tree index data structures. The invention also discloses a router, which is provided with the above-mentioned content storage pool. The invention also discloses a tree index method using the above content storage pool, that is, real data is inserted into the tree index data structure as the best matching data package, and the best matching data package is dynamically selected and updated. The content storage pool and the router of the present invention can be used for the data cache of the forwarding plane of the named data network.

Description

Tree index data structure, content storage pool, router and tree index method

technical field

The invention relates to the field of high-performance router structure design, in particular to a tree index data structure, a content storage pool, a router and a tree index method.

Background technique

At present, with the explosive growth of the scale of the Internet, the continuous emergence of innovative technologies and computing models has accelerated the transformation of the role of the Internet from a "communication channel" to a "data processing platform". In order to meet the future business needs of Internet content, personalization, ultra-high mobility, "zero" delay, ultra-high traffic density, etc., and completely solve many problems brought about by the current Internet IP architecture, a content cache is featured , Naming Data Network applications for communication content.

NDN can not only realize the content-oriented communication mode of the Internet through the use of name data; it can also shorten the response time for users to access cached data by deploying buffer memory in routing nodes, realize content sharing in the true sense, and greatly reduce network traffic. load, effectively increasing the network data transmission rate. Therefore, it is considered to be one of the most promising development directions in the field of Internet architecture in the future.

However, the NDN also faces a series of problems and challenges to be solved [1], especially the content store memory storage and wire-speed processing support in the routing data plane [2]. On the one hand, the entry data of the routing table in the named data network is usually composed of numbers and characters, and is named by a character string with variable length and borderless characteristics. As a result, the Content Store needs to be able to store millions of data storage volumes. . On the other hand, every data packet forwarded from the forwarding route (PendingInterest Table, PIT) and every interest packet incoming to the route must visit the Content Store, and frequent memory accesses occur in the Content Store. Considering that the Content Store is part of the NDN router's operational flow, wire-speed operations should be satisfied, including name lookup and cache replacement. In order to return the data packet for the requested Interest packet as much as possible, the Content Store needs to be able to support all subname matching mechanisms, and in order to accurately judge the arriving data packets, the Content Store needs to be able to support the exact matching mechanism [2]. In addition, as a temporary content cache, its capacity is limited, so the Content Store needs to be able to efficiently compress and store data to reduce storage consumption, and replace the cache in time to clean up space for newly inserted data packets.

references:

1. L. Zhang et al., "Named Data Networking," ACM SIGCOMM Computer Communication Review, vol.44, no.3, pp.66-73, 2014.

2. Z.Li, Y.Xu, B, Zhang, L.Yan, and K.Liu, "Packet Forwarding in Named DataNetworking Requirements and Survey of Solutions," IEEE Communications Surveys&Tutorials, DOI: 10.1109/COMST.2018.2880444, 2018.

Contents of the invention

The invention provides a tree index data structure, a content storage pool, a router and a tree index method for improving the network data transmission rate in order to solve the technical problems in the known technology.

The technical solution adopted by the present invention to solve the technical problems in the known technology is: a tree index data structure, each node in the tree index data structure contains a right pointer pointing to the same layer node and pointing to The child pointer of the next layer node; each data node stores the complete name of the real data, and the real data refers to the name data directly reaching the route.

Further, the tree index data structure dynamically allocates pointers for inserting data nodes according to the number of components of real data and the insertion order.

The present invention also provides a content storage pool, which includes: an on-chip storage unit and an off-chip storage unit, the on-chip storage unit is provided with a bitmap for storing information; the off-chip storage unit is provided with a plurality of The above-mentioned tree index data structure is used for storing position information of data names in the off-chip storage unit and relationship information between data names.

Further, the on-chip storage unit adopts a high-speed memory, and a neural network model for realizing uniform mapping of data names is deployed in the high-speed memory.

The present invention also provides a router, which is provided with the above-mentioned content storage pool.

The present invention also provides a tree-shaped index method using the above-mentioned content storage pool, inserting real data as the best matching data package into the tree-shaped index data structure, automatically storing the logical relationship between name data, and dynamically The best matching packets are selected and updated.

Further, index all parent name data of the real data, and select the data packet with the smallest difference in the number of components and the earliest insertion time as the index address slot according to the number of name components and insertion order of the real data recorded in the index address slot The best matching data packet of the slot; and the index address corresponding to all parent name data is connected with the best matching data packet corresponding to the slot.

Further, when the lower layer node has multiple subname data with the smallest component difference from the real data, the earliest inserted subname data is selected as the next layer node according to the order of insertion into the tree index data structure, and the other subname data are selected as the next layer node. The name acts as a peer node.

Further, the steps of inserting data packets are as follows:

Step a1: input data packet: input data packet to the content storage pool;

Step a2: fixed-length processing: perform fixed-length processing on the name of the input data packet;

Step a3: Calculate the input vector: perform the XOR operation between the same bits on the result of the fixed-length processing to obtain the input vector of the data packet;

Step a4: Calculate the mapping label: the input vector of the data packet is calculated by the neural network model to obtain a value between 0 and 1, and this value is multiplied by the total number of slots in the bitmap to obtain the mapping label of the data packet mapped to the bitmap, namely mapping slot;

Step a5: Determine whether the data packet exists: if the current value in the mapping slot is 1, then the data packet exists, and perform step a10; if the current value in the mapping slot is 0, then the data packet does not exist, and perform step a6;

Step a6: Insert the tree index data structure: if the data packet is real data, when the mapping slot is empty, directly insert the data packet as the best data packet into the tree index data structure, and continue to execute step a8, When the mapping slot is not empty, the data packet is inserted into the tree index data structure as the best data packet, and the sub-pointer of the data packet points to the node pointed to by the pointer in the slot recorded in the mapping slot at this time, and continues Execute step a8; if the data packet is subname data, when the mapping slot is empty, the real data inserted last time is used as the best data packet, and continue to execute step a8, if the mapping slot is not empty, then proceed to step a7;

Step a7: Update the best data package: if the number of components of the data package is greater than the level recorded in the slot, point the class pointer of the name node pointed to by the pointer in the slot to the real data inserted last time, and the best data package will not be updated; Otherwise, the real data inserted last time is used as the new best data packet, and the class pointer of the best data packet points to the node pointed to by the pointer in the slot at this time;

Step a8: Update the bitmap slot: the pointer in the slot points to the actual storage address of the best data packet, and the level is updated to the number of component layers of the best data packet. When the data packet is real data, the current value changes from the default value 0 to 1 , otherwise the current value remains unchanged;

Step a9: Determine whether the name of the data package can be layered: if the level in the slot is > 1, then subtract one from the number of data package components of the name from the back to the front, perform layering processing to form a new name, and execute steps a2 to a9 in a loop; Otherwise, the data packet is not stratified, and continues to step a11;

Step a10: discarding the data packet directly;

Step a11: The data packet insertion ends.

Further, the steps of retrieving data packets are as follows:

Step b1: input data packet: input data packet to the content storage pool;

Step b2: fixed-length processing: perform fixed-length processing on the input data packet;

Step b3: Calculate the input vector: perform the XOR operation between the same bits on the result of the fixed-length processing to obtain the input vector of the data packet;

Step b4: The input vector of the data packet is calculated by the neural network model to obtain a value between 0 and 1, and this value is multiplied by the total number of slots of the bitmap to obtain the mapping number of the data packet mapped to the bitmap, that is, the mapping slot;

Step b5: Determine whether there is a best matching data packet: if the current value in the mapping slot is 1, then the best matching data packet exists, go to step b6; if the current value in the mapping slot is 0, then the best matching data packet does not exist , execute step b7;

Step b6: Discard data packets: learn the bitmap content storage pool to directly discard data packets, and continue to execute step b8;

Step b7: insert data packet: execute the data packet insertion process, and continue to execute step b8;

Step b8: The retrieval of the data packet in the learning bitmap content storage pool structure ends.

The advantages and positive effects that the present invention has are: each node in the tree-shaped index data structure of the present invention contains the right pointer pointing to the node of the same layer and the child pointer pointing to the node of the next layer; each data node Store the full name of the real data. During the establishment of the data structure, it automatically stores the logical relationship between the name data, and dynamically selects and updates the best matching data package. Therefore, after the name data is indexed by the tree-shaped index data structure, the actual address of the best matching data packet can be directly returned from the point in the index address, and the complex retrieval process of variable name data has been successfully moved forward to the table building process. . In this way, the name data retrieval process is moved forward, thereby simplifying the retrieval process and reducing the time complexity of the retrieval; by storing the logical relationship of the name data in the name data insertion process in the content storage pool to support variable-length name data search. A new type of content storage pool storage structure and router can be designed by using the neural network and combining with the tree index data structure in the present invention. The content storage pool and router reduce overall storage consumption by evenly mapping data. Wire-speed support for all subname matching, exact name matching, name data retrieval mechanisms, and data cache replacement by moving the complex name retrieval process forward to the table building process and storing the logical relationship between data in a tree index data structure Strategy. The content storage pool and the router of the present invention can be used for the data cache of the forwarding plane of the named data network.

Description of drawings

FIG. 1 is a schematic diagram of a tree index data structure of the present invention.

FIG. 2 is a structural block diagram of nodes in a tree index data structure of the present invention.

FIG. 3 is a structural block diagram of a content storage pool according to the present invention.

FIG. 4 is a flow chart of a content storage pool supporting all subname matching operations in the present invention.

FIG. 5 is a flow chart of an operation for supporting exact matching in a content storage pool according to the present invention.

FIG. 6 is a flow chart of a data insertion operation of a content storage pool according to the present invention.

FIG. 7 is a flowchart of an operation for deleting data by a content storage pool according to the present invention.

Detailed ways

In order to further understand the invention content, characteristics and effects of the present invention, the following embodiments are enumerated hereby, and detailed descriptions are as follows in conjunction with the accompanying drawings:

The Chinese interpretation of English in this application is as follows:

NDN: Named Data Network;

Content Store: content storage pool;

Back Propagation Neural Networks, BPNN: reverse neural network;

Recent: current;

Point: the pointer in the slot;

Slot: slot;

Bitmap: bitmap;

Trie: word search tree;

Level: level;

Info: information;

next node: same layer node;

child node: the next layer of nodes;

next: right pointer;

child: child pointer;

Pending Interest Table, PIT: Forwarding routing;

URL: Uniform Resource Locator;

Back Propagation Neural Networks, BPNN: reverse neural network;

Forwarding Information Base, FIB: forward forwarding table.

Please refer to Figures 1 to 2, a tree index data structure, each node in the tree index data structure contains a right pointer pointing to the same layer node and a sub pointer pointing to the next layer node; each Each data node stores the complete name of the real data, which refers to the name data directly to the route. The name data obtained by layering the real data is defined as the subname of the real data, for example: /A, /A/B are the subname data of the real data A/B/C.

Preferably, the tree index data structure dynamically allocates pointers for inserting data nodes according to the number of components of real data and the insertion sequence.

In order to reduce the memory consumption of hierarchical names and reduce the depth of the tree, when we construct the tree index data structure, each data node stores the complete name of the real data instead of the component information of its name data. In order to store the logical relationship between data nodes, each node in the tree index data structure contains a right pointer (next) pointing to the same layer node (next node) and a child node pointing to the next layer node (child node). pointer (child).

In the tree index data structure, for the data packet whose content name is x, we define: x is the real data name, and the new data formed by continuously reducing the number of component layers of x is the parent name data of x, and x is its The child name data of the parent name data, such as when the data named /ICN/NDN/maps is input to the Content Store, /ICN/NDN/ and /ICN are the parent name data of the real data /ICN/NDN/maps, and vice versa ICN/NDN/maps are subname data for /ICN/NDN/ and /ICN. We also define child nodes as child name data with minimal component differences from the real data. When there are multiple qualified child name data, according to the order of inserting the tree index data structure, select the earliest inserted child name as the child node, and other child names as the next node, if there are three content names /ICN/NDN/ maps, /ICN/NDN/TJU and /ICN/NDN are entered in order, /ICN/NDN/maps and ICN/NDN/TJU are the child nodes of /ICN/NDN, and ICN/NDN/TJU is /ICN/NDN/maps The next node node.

The logical relationship of storing name data in the tree index data structure table building process is as follows: First, the tree index data structure indexes real data to obtain the exact index address. Then, the real data is inserted into the tree index data structure as the best matching packet. Finally, the tree index data structure indexes all the parent name data of the real data, and according to the number of name components and insertion order of the real data recorded in the index address slot, select the data packet with the smallest difference in the number of components and the earliest insertion time as the index The best matching packet for the address slot. At the same time, establish a connection between the index addresses corresponding to all parent name data and the best matching data packets corresponding to this slot.

The present invention also provides an embodiment of a content storage pool, which includes: an on-chip storage unit and an off-chip storage unit, the on-chip storage unit is provided with a bitmap for storing information; the off-chip storage unit is provided with A plurality of above-mentioned tree-shaped index data structures are used for storing position information of data names in the off-chip storage unit and relationship information between data names. The content storage pool can be used for the data cache of the NDN forwarding plane.

Preferably, the on-chip storage unit can use a high-speed memory, and a neural network model for realizing uniform mapping of data names can be deployed in the high-speed memory. The off-chip storage unit can be a low-speed memory.

The present invention also provides an embodiment of a router, which is provided with the above-mentioned content storage pool. The router can be used for data caching of the forwarding plane of the named data network.

The present invention also provides an embodiment of a tree index method using the above-mentioned content storage pool. The tree index method is: inserting real data as the best matching data packet into the tree index data structure, automatically Store the logical relationship between name data, and dynamically select and update the best matching data package.

Preferably, all parent name data of the real data can be indexed, and according to the number of name components and insertion order of the real data recorded in the index address slot, the data packet with the smallest difference in the number of components and the earliest insertion time can be selected as the The best matching data packet of the index address slot; and the index address corresponding to all parent name data can be connected with the best matching data packet corresponding to this slot.

Preferably, when the lower layer node has multiple subname data with the smallest component difference from the real data, the earliest inserted subname can be selected as the next layer node according to the order of insertion into the tree index data structure, Other subnames can be used as peer nodes.

Preferably, after being indexed by the tree index data structure, the name data can be directly returned to the actual address of the best matching data packet by the pointer in the slot (Point) in the index address slot.

Preferably, the steps of inserting a data packet may be as follows:

Step a1: input data packet: input data packet to the content storage pool;

Step a2: fixed-length processing: perform fixed-length processing on the name of the input data packet;

Step a3: Calculate the input vector: perform the XOR operation between the same bits on the result of the fixed-length processing to obtain the input vector of the data packet;

Step a4: Calculate the mapping label: the input vector of the data packet is calculated by the neural network model to obtain a value between 0 and 1, and this value is multiplied by the total number of slots in the bitmap to obtain the mapping label of the data packet mapped to the bitmap, namely mapping slot;

Step a5: Determine whether the data packet exists: if the current value in the mapping slot is 1, then the data packet exists, and perform step a10; if the current value in the mapping slot is 0, then the data packet does not exist, and perform step a6;

Step a6: Insert the tree index data structure: if the data packet is real data, when the mapping slot is empty, directly insert the data packet as the best data packet into the tree index data structure, and continue to execute step a8, When the mapping slot is not empty, the data packet is inserted into the tree index data structure as the best data packet, and the sub-pointer of the data packet points to the node pointed to by the pointer in the slot recorded in the mapping slot at this time, and continues Execute step a8; if the data packet is sub-name data, when the mapping slot is empty, the real data inserted last time is used as the best data packet, and continue to execute step a8, if the mapping slot is not empty, proceed to Step a7;

Step a7: Update the best data package: if the number of components of the data package is greater than the level recorded in the slot, point the class pointer of the name node pointed to by the pointer in the slot to the real data inserted last time, and the best data package will not be updated; Otherwise, the real data inserted last time is used as the new best data packet, and the class pointer of the best data packet points to the node pointed to by the pointer in the slot at this time;

Step a8: Update the bitmap slot: the pointer in the slot points to the actual storage address of the best data packet, and the level is updated to the number of component layers of the best data packet. When the data packet is real data, the current value changes from the default value 0 to 1 , otherwise the current value remains unchanged;

Step a9: Determine whether the name of the data package can be layered: if the level in the slot is > 1, then subtract one from the number of data package components of the name from the back to the front, perform layering processing to form a new name, and execute steps a2 to a9 in a loop; Otherwise, the data packet is not stratified, and continues to step a11;

Step a10: discarding the data packet directly;

Step a11: The data packet insertion ends.

Preferably, the steps of retrieving the data packet may be as follows:

Step b1: input data packet: input data packet to the content storage pool;

Step b2: fixed-length processing: perform fixed-length processing on the input data packet;

Step b3: Calculate the input vector: perform the XOR operation between the same bits on the result of the fixed-length processing to obtain the input vector of the data packet;

Step b4: The input vector of the data packet is calculated by the neural network model to obtain a value between 0 and 1, and this value is multiplied by the total number of slots of the bitmap to obtain the mapping number of the data packet mapped to the bitmap, that is, the mapping slot;

Step b5: Determine whether there is a best matching data packet: if the current value in the mapping slot is 1, then the best matching data packet exists, go to step b6; if the current value in the mapping slot is 0, then the best matching data packet does not exist , execute step b7;

Step b6: Discard data packets: learn the bitmap content storage pool to directly discard data packets, and continue to execute step b8;

Step b7: insert data packet: execute the data packet insertion process, and continue to execute step b8;

Step b8: The retrieval of the data packet in the learning bitmap content storage pool structure ends.

The following takes two real data packets /ICN/NDN/maps and /ICN inputting the tree index data structure for the first time as an example to illustrate the table building process of the above tree index data structure. For the real data /ICN/NDN/maps, first, assuming that the name is mapped to the index address slot 2 by the tree index data structure, then, /ICN/NDN/maps is inserted into the tree as the best matching packet for slot 2 In the shape index data structure, and the Point pointer in slot 2 points to the best matching data packet of this slot. Finally, the subnames /ICN/NDN and /ICN of /ICN/NDN/maps are indexed through the tree index data structure in turn, assuming that they are indexed to slots 4 and 6 respectively, then Points in slots 4 and 6 (assuming the initial state , when it is empty) all point to the memory address of the /ICN/NDN/maps node in the tree index data structure. /ICN/NDN/maps data retrieval completed. For the real data /ICN, it is mapped to the index address slot 6 through the tree index data structure, compare the /ICN/NDN/maps data pointed to by Point and the component layers of /ICN, and select /ICN as the best match for slot 6 The data packet, therefore, /ICN is inserted into the tree index data structure, and slot 6 is connected with the off-chip /ICN node by Point.

The above-mentioned content storage pool and the router formed by it can be used for the forwarding plane of the named data network. It can achieve line speed by moving the complex name retrieval process to the table building process and storing the logical relationship between data in the tree index data structure. It supports all subname matching, exact name matching, name data retrieval mechanism and data Cache replacement strategy.

The following is a preferred embodiment of the content storage pool used for the forwarding plane of the named data network of the present invention to illustrate the workflow and working principle of the present invention:

A content storage pool of a NDN forwarding plane, as shown in FIG. 3 , has a structure comprising: an on-chip storage unit and an off-chip storage unit. Wherein, a high-speed memory is provided in the on-chip storage unit, and a neural network model is deployed on-chip to realize uniform mapping of data names and improve data storage utilization. In Fig. 3, a model is used to represent the neural network model; an improved model is also deployed. Bitmap (Bitmap), represented by bitmap in Fig. 3, is used to store the information of the best matching name data; The off-chip storage unit uses low-speed memory, deploys the slot (slot) of the index unit of multiple and improved bitmap on it ) corresponding to the tree-shaped index data structure to store the position information of the data name in the content storage pool and the relationship information between the names, and each tree-shaped index data structure node stores a class pointer pointing to a node of the same layer, and Child pointer to the next layer of nodes. In Figure 3, the neural network model and the improved bitmap are integrated and called a learning tree. A herringbone arrow is used to indicate the next pointer; a solid arrow is used to indicate the child pointer; a dotted arrow is used to indicate the slot of the index unit corresponding to the tree index data structure.

The content storage pool of the present invention can realize fast compression processing operations on data. The key is that in the ContentStore, the network mapping of the neural network is used to improve storage efficiency and support different name data retrieval algorithms, and the tree shape that meets the fast cache replacement strategy is designed. Index data structures and tree index data structures that can store logical relationships of name data. Its specific design and implementation plan are as follows:

(1) Neural network model to realize the uniform mapping process of the data name is as follows:

First, the neural network collects samples for training, and a large number of uniform resource locator URLs similar to the name data format of the named data network are used as sample data; secondly, the cumulative distribution function F(x) value of the sample data is calculated as the label; then, the training reverse Propagate the neural network to learn a neural network model that can reflect the distribution of index data. Finally, the name string of the data name is used as input to train the neural network model, and a real value between 0 and 1 is obtained. The value is multiplied by The total number of slots in the improved bitmap is used to obtain the mapping label, that is, to achieve uniform mapping of data names.

(2) The structure of the neural network model is designed as follows:

The neural network model is a model consisting of the following two layers: in 1-level BPNN and 1,000 BPNNs, each BPNN has 5 input neurons, 20 hidden neurons and 1 output neuron. Figure 1 shows that in each bitmap slot, there is a Recent indicating that the slot is occupied by the actual content name, and a point (Point) is used to return the actual memory address of the best matching name (in all subname matching operations In , the best matching name is defined as the data packet stored in the name Trie, whose name has the smallest component difference and starts with the name of the arriving Interest packet; in the exact matching operation, the best matching name is defined as the same as the arriving data packet Note that when one or more matching names have the smallest component, select the data packet inserted into the tree index data structure first as the best matching name). A level (Level) indicates the level of the best matching name (indicated by the number of components separated by "/" or "), and an information (Info) records the name data information required to satisfy the cache replacement. For example, the number of times the data is indexed or arrival time etc.

Through the efficient cooperation between the above data structures, the designed new storage structure content storage pool can quickly support all sub-name matching mechanisms of data, precise name matching mechanisms and cache replacement strategies, and realize Data insertion and deletion operations.

FIG. 4 is a flow chart of a content storage pool supporting all subname matching operations in the present invention.

Please refer to Figure 4. The content storage pool used for the forwarding plane of the named data network uses a subname matching mechanism in its storage structure to retrieve interest packets. The steps for each retrieval of interest packets are as follows:

Step 1-1: Input interest packet x: Input interest packet x into the content storage pool.

Step 1-2: Fixed-length processing: Perform fixed-length processing on the name of the input data packet x; to meet the characteristics that the reverse neural network (Back Propagation Neural Networks, BPNN) only supports fixed-length data processing, that is, every 5 of x The number of digits is one, and it is divided into five parts. If the number of digits is insufficient, 0 is added at the end.

Step 1-3: Calculate the input vector: perform an XOR operation between the same bits of the fixed-length processing result to obtain the 5-bit input value of x processed by the input stage.

Step 1-4: Calculate the mapping label: the input value is calculated by the neural network that has been trained to obtain a value between 0 and 1, and this value is multiplied by the total number of slots in the improved bitmap to obtain that the Interest packet is mapped to the improved bitmap The mapping label on the diagram.

Step 1-5: Determine whether there is a best matching data packet: if the pointer (Point) in the slot in the mapping label is not empty, it proves that there is a best matching data packet, and perform steps 1-6. Otherwise, it means that there is no best matching packet, and go to steps 1-7.

Step 1-6: return the best matching data packet: the content storage pool directly returns the actual data packet pointed to by the pointer (Point) in the slot and continues to execute steps 1-8.

Step 1-7: Forward the Interest packet x: The content storage pool forwards the Interest packet to the PIT and the Forwarding Information Base (FIB) for subsequent processing, and continue to execute steps 1-8.

Steps 1-8: The retrieval of the Interest packet in the content storage pool ends.

FIG. 5 is a flow chart of an operation for supporting exact matching in a content storage pool according to the present invention.

Please refer to Fig. 5, the content storage pool for the forwarding plane of the named data network uses an exact matching mechanism to retrieve data packets in its storage structure, and the steps for each retrieval of data packets are as follows:

Step 2-1: Input data package y: input data package y to the content storage pool;

Step 2-2: Fixed-length processing: Perform fixed-length processing on the name of the input data packet y; to meet the characteristics that the reverse neural network only supports fixed-length data processing, that is, every 5 bits of y are divided into 5 copies, if there are not enough digits, add 0 at the end.

Step 2-3: Calculate the input vector: Execute the XOR operation between the same bits of the result of the fixed-length processing to obtain the 5-bit input value of y processed by the input stage.

Step 2-4: Calculate the mapping label: the input value is calculated by the neural network that has been trained to obtain a value between 0 and 1, which is multiplied by the total number of slots in the improved bitmap, and the data packet y is mapped to the improved bitmap Mapping label on the bitmap.

Step 2-5: Determine whether there is a best matching data packet: if Recent in the slot in the mapping label is not 0, it proves that there is a best matching data packet, and perform steps 2-6. Otherwise, it means that there is no best matching data packet, and go to steps 2-7.

Step 2-6: discard data x: the content storage pool directly discards x, and proceed to step 2-8.

Step 2-7: Insert data x: The packet enters the insert phase, and proceeds to step 2-8.

Steps 2-8: The retrieval of the data packet in the content storage pool ends.

FIG. 6 is a flow chart of a data insertion operation of a content storage pool according to the present invention.

Please refer to Fig. 6, the data packet is inserted into the storage structure of the NDN forwarding flat content storage pool, and the steps of inserting each data packet are as follows:

Step 3-1: Input data package: input data package into the content storage pool.

Step 3-2: Fixed-length processing: Perform fixed-length processing on the name of the input data packet; to meet the characteristics that the reverse neural network only supports fixed-length data processing, that is, every 5 bits of the data packet are divided into 5 copies, if there are not enough digits, add 0 at the end.

Step 3-3: Calculate the input vector: perform the XOR operation between the same bits on the result of the fixed-length processing to obtain the input value of the data packet processed by the input stage.

Step 3-4: Calculate the mapping label: the input value is calculated by the neural network that has been trained to obtain a value between 0 and 1, and this value is multiplied by the total number of slots in the improved bitmap to obtain that the data packet is mapped to the improved bitmap Mapping labels on the diagram are mapping slots.

Step 3-5: Judging whether the data packet exists: if Recent=1 in the mapping slot, it proves that the data packet exists, and executes step 3-10. Otherwise, it means that the data package does not exist, go to steps 3-6.

Step 3-6: Insert the tree index data structure: If the data packet is real data, when the mapping slot is empty, insert the data packet directly into the tree index data structure as the best data packet, and continue to execute the steps 3-8, when the mapping slot is not empty, insert the data packet as the best data packet into the tree index data structure, and point the sub-pointer of the data packet to the node pointed to by the Point recorded in the mapping slot at this time, continue Execute steps 3-8; if the data packet is subname data, when the mapping slot is empty, the real data inserted last time will be used as the best data packet, continue to perform steps 3-8, if the mapping slot is not empty, proceed to Steps 3-7.

Step 3-7: Update the best data package: If the number of components of the data package is greater than the Level recorded in the slot, point the class pointer of the name node pointed to by Point in the slot to the real data inserted last time, and the best data package does not Update; otherwise, the real data inserted last time is used as the new best data packet, and the class pointer of the best data packet is pointed to the node pointed to by Point in the slot at this time.

Step 3-8: Update the Bitmap slot: Point points to the actual storage address of the best data packet, Level is updated to the number of component layers of the best data packet, and when the data packet is real data, Recent changes from the default value 0 to 1, otherwise Recent remains unchanged.

Step 3-9: Determine whether the name can be layered: if the Level in the slot is > 1, the number of components of the name data package will be reduced by one from the back to the front, and a new name will be formed by hierarchical processing (such as /A/B, divided into Layer is /A), execute steps 3-9 in a loop. Otherwise, the packet cannot be layered, continue to step 3-11.

Step 3-10: discard the packet directly.

Step 3-11: The insertion of the data packet in the content storage pool ends.

FIG. 7 is a flowchart of an operation for deleting data by a content storage pool according to the present invention.

Please refer to Fig. 7, which is used to delete data packets in the storage structure of the NDN forwarding plane content storage pool, and the steps for deleting a data packet are as follows:

Step 4-1: Input data package: input data package into the content storage pool.

Step 4-2: Fixed-length processing: Perform fixed-length processing on the name of the data packet to meet the characteristics that the reverse neural network only supports fixed-length data processing, that is, every 5 bits of the data packet are divided into 5 parts , if the number of digits is insufficient, add 0 at the end.

Step 4-3: Calculate the input vector: perform the XOR operation between the same bits on the result of the fixed-length processing to obtain the input value of the data packet processed by the input stage.

Step 4-4: Calculate the mapping label: the input value is calculated by the neural network that has been trained to obtain a value between 0 and 1, and this value is multiplied by the total number of slots in the improved bitmap to obtain that the data packet is mapped to the improved bitmap Mapping labels on the diagram are mapping slots.

Step 4-5: Determine whether the data packet exists: if Recent=1 in the mapping slot, it proves that the data packet exists, and proceed to step 4-6. Otherwise, it means that the data package does not exist, go to steps 4-9.

Step 4-6: Updating the pointer: If the subpointer and class pointer of the data packet node are not empty, point the subpointer originally pointing to the data packet node to the node pointed to by the data packet class pointer. The sub-pointer of the node pointed to by the data packet class pointer points to the pointed child node of the data packet node, and the node pointed to by the data packet node sub-pointer is taken as the optimal data packet. Otherwise, the best packet is empty.

Step 4-7: Update the Bitmap slot: Point points to the actual storage address of the best data packet at this time, Level is updated to the number of component layers of the best data packet, and Recent changes from 1 to 0.

Steps 4-8: Delete the packet directly.

Steps 4-9: The deletion of the data package in the content storage pool ends.

From the above process of inserting name data into the tree-shaped index data structure, it can be seen that during the establishment of the tree-shaped index data structure, the logical relationship between name data is automatically stored, and the best matching data package is dynamically selected and updated. Therefore, after the name data is indexed by the tree-shaped index data structure, the Point in the index address can directly return the actual address of the best matching data packet, successfully realizing the complex retrieval process of variable name data forward to the table building process.

The above-described embodiments are only used to illustrate the technical ideas and characteristics of the present invention, and its purpose is to enable those skilled in the art to understand the content of the present invention and implement it accordingly. The present invention cannot be limited only by this embodiment. The scope of the patent, that is, all equivalent changes or modifications made to the spirit disclosed in the present invention still fall within the scope of the patent of the present invention.

Claims (3)

1. A tree index method based on a content storage pool, characterized in that a content storage pool is set, and the content storage pool includes: an on-chip storage unit and an off-chip storage unit, and the on-chip storage unit is provided with a A bitmap for storing information; the off-chip storage unit is provided with multiple tree-shaped index data structures for storing position information of data names in the off-chip storage unit and relationship information between data names; Each node in the tree index data structure contains a right pointer pointing to the same layer node and a subpointer pointing to the next layer node; each data node stores the full name of the real data, and the real data Refers to the name data that goes directly to the route; The tree index data structure dynamically allocates pointers to insert data nodes according to the number of components of real data and the insertion order; The tree index method inserts real data as the best matching data package into the tree index data structure, automatically stores the logical relationship between name data, and dynamically selects and updates the best matching data package; Index all parent name data of the real data, and according to the number of name components and insertion order of the real data recorded in the index address slot, select the data packet with the smallest difference in the number of components and the earliest insertion time as the best package for the index address slot Match the data packet; and establish a connection between the index address corresponding to all the parent name data and the best matching data packet corresponding to the slot; When the next-level node has multiple sub-name data with the smallest component difference from the real data, select the earliest inserted sub-name as the next-level node according to the order of insertion into the tree index data structure, and other sub-names as the same layer node; The steps to retrieve a packet are as follows: Step b1: input data packet: input data packet to the content storage pool; Step b2: fixed-length processing: perform fixed-length processing on the input data packet; Step b3: Calculate the input vector: perform the XOR operation between the same bits on the result of the fixed-length processing to obtain the input vector of the data packet; Step b4: The input vector of the data packet is calculated by the neural network model to obtain a value between 0 and 1, and this value is multiplied by the total number of slots of the bitmap to obtain the mapping number of the data packet mapped to the bitmap, that is, the mapping slot; Step b5: Determine whether there is a best matching data packet: if the current value in the mapping slot is 1, then the best matching data packet exists, go to step b6; if the current value in the mapping slot is 0, then the best matching data packet does not exist , execute step b7; Step b6: Discard data packets: learn the bitmap content storage pool to directly discard data packets, and continue to execute step b8; Step b7: insert data packet: execute the data packet insertion process, and continue to execute step b8; Step b8: the retrieval of the data packet in the learning bitmap content storage pool structure ends; The steps to insert a packet are as follows: Step a1: input data packet: input data packet to the content storage pool; Step a2: fixed-length processing: perform fixed-length processing on the name of the input data packet; Step a3: Calculate the input vector: perform the XOR operation between the same bits on the result of the fixed-length processing to obtain the input vector of the data packet; Step a4: Calculate the mapping label: the input vector of the data packet is calculated by the neural network model to obtain a value between 0 and 1, and this value is multiplied by the total number of slots in the bitmap to obtain the mapping label of the data packet mapped to the bitmap, namely mapping slot; Step a5: Determine whether the data packet exists: if the current value in the mapping slot is 1, then the data packet exists, and perform step a10; if the current value in the mapping slot is 0, then the data packet does not exist, and perform step a6; Step a6: Insert the tree index data structure: if the data packet is real data, when the mapping slot is empty, directly insert the data packet as the best data packet into the tree index data structure, and continue to execute step a8, When the mapping slot is not empty, the data packet is inserted into the tree index data structure as the best data packet, and the sub-pointer of the data packet points to the node pointed to by the pointer in the slot recorded in the mapping slot at this time, and continues Execute step a8; if the data packet is subname data, when the mapping slot is empty, the real data inserted last time is used as the best data packet, and continue to execute step a8, if the mapping slot is not empty, then proceed to step a7; Step a7: Update the best data package: if the number of components of the data package is greater than the level recorded in the slot, point the class pointer of the name node pointed to by the pointer in the slot to the real data inserted last time, and the best data package will not be updated; Otherwise, the real data inserted last time is used as the new best data packet, and the class pointer of the best data packet points to the node pointed to by the pointer in the slot at this time; Step a8: Update the bitmap slot: the pointer in the slot points to the actual storage address of the best data packet, and the level is updated to the number of component layers of the best data packet. When the data packet is real data, the current value changes from the default value 0 to 1 , otherwise the current value remains unchanged; Step a9: Determine whether the name of the data package can be layered: if the level in the slot is > 1, then subtract one from the number of data package components of the name from the back to the front, perform layering processing to form a new name, and execute steps a2 to a9 in a loop; Otherwise, the data packet is not stratified, and continues to step a11; Step a10: discarding the data packet directly; Step a11: The data packet insertion ends. 2. The tree index method based on content storage pool according to claim 1, characterized in that, the on-chip storage unit adopts a high-speed memory, and the neural network model for realizing uniform mapping of data names is deployed in the high-speed memory . 3. A router, characterized in that the content storage pool according to claim 2 is arranged inside it.

Images