CN103561133B - A kind of IP address attribution information index method and method for quickly querying - Google Patents

Abstract

The invention discloses a kind of IP address attribution information index and method for quickly querying.The method include the steps that 1) choose or set up an attaching information configuration file；2) the cidr block record in configuration file is read；Each record is created as a new node of query tree；If this block belongs to IPV4 address block or IPV6 address block, and the head node of correspondence IPV4 or IPV6 query sub tree is empty, then using this new node as head node, otherwise select corresponding head node traversal queries subtree, until meeting condition (to have traveled through arrival leaf node, or present node compares position and more than new node and comprises cidr block information), calculate the network prefix length L that present node is common with this new node；If L is more than the comparison position of present node, then it return back to father node and be set to present node；Determine the on position of this new node according to L-value and present node, and its attaching information is associated with this new node.The present invention has higher search efficiency.

Description

An IP address attribution information indexing method and fast query method

technical field

The invention relates to the field of computer network and communication field, in particular to a fast query method of IP address attribution information based on Patricia query tree.

Background technique

At present, IP address-based services (such as weather forecast, etc.), network management systems and security software provided on the Internet all need to use IP address attribution information, such as country information, city information, organization information, AS information, latitude and longitude information, etc. By querying the attribution information corresponding to an IP address, the weather forecast service can return the weather information of the city corresponding to the IP host; the network management system can monitor the traffic and other related information of a given monitoring object (country, institution, etc.); Security software can also specify corresponding security policies to clean specified traffic, such as filtering traffic from a certain country and so on.

There are already mature technologies and products for IP attribution information query. For example, MaxMind’s GeoIP database is specially used for IP geographic information query. It also provides a free version and a commercial version with higher accuracy. The GeoIP database has two forms, one is binary version of the library, and provide API interfaces in various languages, one is a file in csv format; the domestic QQ pure IP database is also a widely used free IP database, and the QQ IP database also provides two versions in binary format and non-binary format kind. The above two IP databases and other similar products associate their attribution information (including country information, city information, institution information, AS information, longitude and latitude) based on known IP CIDR address blocks assigned to each country, region or operator information, etc.) and organized into an IP database. For an IP address whose attribution information is unknown, by querying the IP database to find the CIDR to which it belongs, the corresponding attribution information can be queried.

CIDR classless inter-domain routing technology is to solve the problem that IP addresses cannot be used rationally caused by IP address subnetting. CIDR uses variable-length network prefixes to replace network numbers and subnet numbers in classified addresses, and multiple networks can be assigned to each other. IP addresses with the same prefix part form a CIDR address block. Each CIDR address block is composed of a start address and a suffix indicating the length of the network prefix, separated by '/', for example, 192.168.0.0/16 indicates the CIDR block address Starting from 192.168.0.0, the first 16 bits are network addresses, and there are a total of 216 consecutive addresses. CIDR address blocks can be further aggregated. For example, 16 original Class C (/24) networks can be aggregated together and displayed as a /20 network (if the first 20 bits of the addresses of these networks are all the same). Two aligned /20 networks can be further aggregated into a /19, and so on. CIDR technology brings great convenience to network management, so both IPV4 and IPV6 currently use CIDR technology.

There are two ways to query the GeoIP database and QQ pure IP database. One way is to query through the interface of the binary library, and the other way is to import the IP attribution information file data in csv format or text format into the database (such as MySQL database), and then query through the database, but these two query methods have some shortcomings. For the IP database in binary form, in order to improve the query speed and save resources, optimization measures have been taken when organizing IP attribution information records, such as indexing and attribution information redirection, and can be resident in memory. The query algorithm uses dichotomy, etc. for comparison Fast algorithm, so the query speed is relatively fast, but its shortcomings and limitations are that the flexibility is not good enough to meet some special applications. For example, for an organization A, there are smaller custom organizations inside, but GeoIP and QQIP There may be only records of A in the database but no records of the custom organization under A, so related operations cannot be performed on the sub-organizations of A, even if the attribution information of a custom form is added to the binary library, due to the black box of the binary library organization form In addition, in some application scenarios, one IP address corresponds to multiple attribution information (for example, one IP address corresponds to organization A, and organization A belongs to organization B, so the IP address also belongs to Institution B), it is required to return all attribution information for each query, but the query binary library method cannot be realized; in some application scenarios, only a part of the IP address attribution information fields defined in the GeoIP and QQIP databases may be used. Therefore, using GeoIP and QQIP will generate additional waste of resources. In short, the attribution information of the IP address should be customized according to the actual situation, so as to facilitate actual query. The second query method is highly flexible. Developers can extract the required relevant information from GeoIP or QQ IP database files in csv format (or text format) according to their own needs, organize them into IP CIDR block attribution information, and can Add custom IP CIDR attribution information, and then import it into the database (such as MySQL database), but this query method needs to access the database every time and execute SQL query statement operations, so it will increase the query time and affect the query speed. Currently the most widely used IPV4 address is 32 bits, and the number of its CIDR blocks is relatively small. This method of querying the database can also meet the requirements of real-time query. However, with the widespread use of IPV6 addresses, it is necessary to provide corresponding attribution information query services for more and more IPV6 addresses. Since IPV6 addresses have an address space of ²¹²⁸ , the number of CIDR blocks corresponding to IPV6 addresses will also increase. , and with further refinement, the number of CIDR blocks of IPV6 will be even more enormous, so this method of querying the database will have a large delay in querying IPV6 addresses with an astonishing number of CIDR blocks, especially for the backbone of operators Network, the network traffic monitoring system they use often requires millisecond-level real-time network flow processing delay, which cannot be met. In short, how to organize such a huge IPCIDR block address, establish an efficient index and be able to effectively provide address attribution query in real time is a very important task.

Contents of the invention

For the technical problems existing in the prior art, the purpose of the present invention is to provide a kind of IP address attribution information indexing method and fast query method based on Patricia search tree, can be used for IPV4 address, IPV6 address (especially IPV6 address) in real time and efficiently ) query of custom form attribution information.

The Patricia tree is a compressed binary query tree based on the idea of a Trie tree. All single-branch nodes are merged with their parent nodes to achieve the effect of compression. The nodes of the Patricia tree are divided into two types, one is called external nodes, that is, leaf nodes; the other is called internal nodes, that is, non-leaf nodes. In the Patricia tree, the specific information of the keyword is stored on the leaf node in the form of a binary string, and the internal node of the Patricia tree is used to record the path of the keyword. It has three basic data items: comparison bit, left pointer, right Pointers, where the left pointer and right pointer point to the left and right subtrees of the node respectively, and the comparison bit records the number of digits that need to be skipped before the next comparison, and the bit string passing through the node will choose a different subsequent path. When the comparison bit value is 0, the bit string turns to the left subtree, when the comparison bit value is 1, the bit string turns to the right subtree, each internal node has left and right child nodes, and its root node is a special internal node . The time complexity of Patricia tree search is related to the depth of the tree, and the depth of the Patricia tree is related to the length N of the binary string of keywords, the number of records n, the distribution of 0 and 1 on different bits, and the compression situation. In the best case It is a balanced binary tree structure. In the worst case, the tree formed by its internal nodes is a single branch tree, so the time complexity is optimally O(log N), and worst is O(N). When there are n keywords in the Patricia tree, that is, n leaf nodes, there are n-1 internal nodes, and the total number of nodes is 2n-1, so its space complexity is O(n).

Technical scheme of the present invention is:

A method for indexing IP address attribution information, the steps of which are:

1) Select or create an IP CIDR address block attribution information configuration file; initialize the IP address attribution information query tree and its subtrees, which are respectively the IPV4 query subtree and the IPV6 query subtree;

2) Read the CIDR block record in the configuration file; for each CIDR block record, use the CIDR address block as the key value, and use its network prefix length as the comparison bit to create a new node of the query tree;

21) If the CIDR block belongs to the IPV4 address block, and the head node of the current IPV4 query subtree is empty, use the new node as the head node of the IPV4 query subtree, and associate its attribution information to the new node, if the head node If the node is not empty, select the head node of the IPV4 query subtree and proceed to step 22); if the CIDR block belongs to the IPV6 address block, and the head node of the current IPV6 query subtree is empty, then use this new node as the IPV6 query subtree and associate its attribution information with the new node, if the head node is not empty, select the head node of the IPV6 query subtree and proceed to step 22);

22) Traverse the corresponding query subtree from the selected head node until condition 1 or condition 2 is met, and calculate the network prefix length L common to the current node traversed in the query subtree and the new node; if the value of L is greater than For the comparison bit of the current node, roll back to the parent node of the current node, and set the parent node as the current node until the value of L is less than or equal to the comparison bit of the current node in the query subtree;

23) Determine the insertion position of the new node according to the L value and the current node determined in step 22), insert the new node into the query subtree, and associate its attribution information with the new node;

Among them, condition one: the leaf node in the query tree has been traversed; condition two: the current node traversed is an internal node whose comparison bit is greater than that of the new node and contains CIDR block information.

Further, the method of traversing the corresponding query subtree is as follows: set the comparison bit of the current node traversed in the query subtree to be n, if the n+1th bit of the key value of the new node is 0, then traverse the current node in the query subtree The left child node of the node, if the n+1th bit of the key value of the new node is 1, traverse the right child node of the current node in the query subtree.

Further, the method for determining the insertion position of the new node is:

a) If L is equal to the comparison bit of the current node and the comparison bit of the new node, and the current node is an internal node that does not contain CIDR block information, replace the internal node with the new node;

b) If L is equal to the comparison bit of the current node and L is smaller than the comparison bit of the new node, then the new node will be regarded as a child node of the current node, if the L+1th bit of the binary string of the CIDR block of the new node is 0 , as the left child node of the current node, if the L+1th bit is 1, it is used as the right child node of the current node;

c) If L is equal to the comparison bit of the new node and L is smaller than the comparison bit of the current node, then the new node is taken as the parent node of the current node, if the L+1th bit of the binary string of the CIDR block of the current node is 0, then As the left subtree of the new node, if the L+1th bit is 1, it is used as the right subtree of the new node;

d) If L is less than the comparison bit of the new node and L is less than the comparison bit of the current node, create a new internal node, set its keyword to be empty, and set the comparison bit to L to replace the position of the current node. If the new node’s CIDR block If bit L+1 of the binary string is 0, then the new node is taken as the left child node of the newly created internal node, and the current node and its subtree are taken as the right subtree of the newly created internal node. If the binary string of the CIDR block of the new node If the L+1th bit is 1, the new node is used as the right child node of the newly created internal node, and the current node and its subtree are used as the left subtree of the newly created internal node.

Further, the establishment method of the configuration file is:

41) Set the format of the attribution information record. The attribution information record is composed of the corresponding IP CIDR block field and several attribution information fields. The format is such as: IP CIDR information (xxx.xxx.xxx.xxx/xx, consisting of subnet address and network prefix length part), country/region information, city information, organization information, AS information, longitude, latitude information, etc.; the IP CIDR field value cannot be empty, and other field values can be empty;

42) To create attribution information, first, according to the field format of the IP address attribution record, take out the required fields from the IP address attribution information database (if there is no relevant field in the IP address attribution information database, you can customize it), and organize it into a record; Secondly, create a custom IP CIDR address attribution information record (its IP CIDR block does not exist in the IP address library);

43) Save the IP address attribution information record described in 42) in a configuration file, and generate the configuration file, wherein each record occupies one line; the configuration file generally saves the IP address attribution information record in the form of a text file.

Further, in the configuration file, IP CIDR blocks of different attribution information are allowed to contain the same IP address.

Further, the method for updating the query tree is:

61) Read the CIDR record in the attribution information update configuration file, use the CIDR address block as the key value, and use its network prefix length as the comparison bit to create a new node a; if the update operation is insertion, proceed to step 62); if it is delete, proceed to step 63;

62) According to the IP address category in node a, select the head node of the corresponding query subtree, perform steps 22) and 23), and insert the new node a and its attribution information into the query subtree;

63) According to the IP address category in node a, select the head node of the corresponding query subtree, perform step 22), locate the node CIDR of the CIDR node to be deleted in the query subtree, if the node CIDR is consistent with the CIDR to be deleted , proceed to step 64), otherwise return an error message;

64) According to the rules (i)-(k), delete the CIDR block information at the corresponding position from the query subtree, and adjust the query tree;

(i) If the node to be deleted in the query subtree is a leaf node, delete the entire node information, if the leaf node is the left child node of its parent node, mark the left child node of its parent node as empty, and vice versa ;

(j) If the node to be deleted in the query subtree is an internal node and has only one child node, then delete the internal node and its attribution information, and replace its position in the tree with its child node;

(k) If the node to be deleted in the query subtree is an internal node and has two child nodes, only the CIDR information of the internal node is deleted, and the internal node and its comparison bits are retained.

A method for quickly inquiring about IP address attribution information, the steps of which are:

71) Select an IPV4 head node or an IPV6 head node in the query tree according to the type of IP address to be queried, and traverse the query tree in a depth-first manner from the selected head node until it reaches the leaf node of the query tree, and in the process of traversing the All nodes in the query tree containing CIDR block attribution information are pushed into the set stack;

72) Traverse each node in the stack, find all nodes matching the IP address to be queried, and proceed to step 73), if there is no node matching the IP address to be queried, return a null value or not found;

73) Determine the configuration status of the IP address attribution information. If multi-homing information is configured, return the attribution information of all nodes in the stack. If only unique attribution information is configured, only return the attribution information of the top node in the stack.

Further, the method of traversing the query tree is: set the comparison bit of the current node traversed in the query tree to be n, if the n+1th bit of the binary string corresponding to the IP address to be queried is 0, then traverse the left child node of the current node , if the n+1th bit is 1, then traverse the right child node of the current node.

Further, the nodes in the stack include: all internal nodes containing CIDR block attribution information and the last arrived leaf node in the process of traversing the query tree.

According to embodiments of the present invention, technical characterictic of the present invention has:

1. According to the embodiment of the present invention, the present invention supports self-defining IP CIDR block address attribution information and sets up configuration file, first sets attribution information record format, and attribution information record is made up of corresponding IP CIDR block field and some attribution information fields, and format is as follows : IP CIDR information (xxx.xxx.xxx.xxx/xx, composed of subnet address and network prefix length), country/region information, city information, organization information, AS information, longitude, latitude information, etc.; where IP CIDR Field values cannot be empty, and other field values can be empty; then create attribution information, firstly, according to the field format of the IP address attribution record, take out the required fields from the IP address attribution information database (if there is no relevant field in the IP address attribution information database) field, which can be customized), and organize it into a record; secondly, create a custom IP CIDR address attribution information record (its IP CIDR block does not exist in the IP address library); finally, save the IP address attribution information record in The configuration file is to generate the configuration file, wherein each record occupies one line; the configuration file generally saves the IP address attribution information record in the form of a text file.

2. The present invention proposes a kind of IP address attribution information query tree based on the Patricia query tree thought. According to one embodiment of the present invention, the IP address attribution information query tree of the present invention uses the IP CIDR block address binary string recorded in the configuration file as a keyword , the length of the CIDR block network prefix is used as a comparison bit, and the attribution information corresponding to the IP CIDR block in the configuration file is associated with the corresponding node as a value field. According to an embodiment, the IP address attribution information query tree constructed by the present invention is a special Patricia query tree, and its characteristics are as follows:

The information of the keyword of common Patricia tree is all stored in leaf node (being external node), and internal node only records the position of comparison bit and stores left and right sub-nodes, and the IP address attribution information inquiry tree of structure among the present invention is in order to adapt to IP CIDR address The particularity of , its internal nodes can also store keyword information. As in one embodiment of the present invention, there are the following CIDR block addresses A, B, and C, where B address block and C address block belong to the sub-blocks of A address block, that is, the network prefix of A address block and the addresses of B and C The network prefix of the block has a common part, so in the IP address attribution information query tree, A is the parent node of B and C, and A is no longer a leaf node. As an internal node, A also stores keyword information.

3. According to an embodiment of the present invention, the present invention supports that an IP address belongs to one or more CIDR blocks, has one or more attribution information, and can return all CIDRs that match the IP address in the query tree when querying The attribution information of the block. According to the embodiment of the present invention, in some scenarios (such as network monitoring), some hosts or sub-organizations in a large organization need temporary or long-term independent monitoring (such as traffic monitoring, etc.), so it is necessary to provide these hosts or The IP addresses of sub-organizations are configured with corresponding CIDR blocks and their attribution information so that related operations can be performed. These IP addresses not only have the attribution information of large organizations, but also have nested and customized attribution information of small organizations.

4. Further, according to an embodiment of the present invention, the IP address attribution information query tree of the present invention also has the following characteristics: the IP address attribution information query tree of the present invention contains two subtrees, storing IPV4CIDR address attribution information and IPV6CIDR block address attribution information respectively . In the embodiments of the present invention, at first need to consider the time complexity of the IP address attribution information query tree, the search time complexity is related to the depth of the tree, and the depth of the query tree is mainly related to the number of bits of the IP address binary string (IPV4 has 32 bits, IPV6 has 128 bits) is related to the number of node records in the tree (the more the number of node records, the greater the depth of the tree), so in order to improve query efficiency and reduce query time (especially for 32-bit IPV4 addresses), it is best to use The IPV4CIDR address and the IPV6CIDR address construct the query tree separately; secondly, it is necessary to consider that the related operations of the constructed query tree should be relatively simplified, such as a unified query interface that can provide external IP address information, and a unified management interface for IP CIDR blocks. Therefore adopt in the embodiment of the present invention at first to construct whole IP address attribution information query tree, then construct corresponding query tree respectively for IPV4 and IPV6CIDR block address information and as the scheme of two sub-trees of whole query tree, thereby reach to improve query efficiency, It also simplifies the query interface and facilitates configuration management.

5. the present invention proposes a kind of query tree construction algorithm for the IP address attribution information query tree of the present invention, according to an embodiment of the present invention, the algorithm of constructing query tree among the present invention comprises the following steps:

The first step is to initialize the IP address attribution information query tree and its corresponding two subtrees, which are respectively the IPV4 query subtree and the IPv6 query subtree.

In the second step, if the IP CIDR attribution information record in the configuration file has been read, go to step six; otherwise, read the IP CIDR attribution information record from the configuration file, use the CIDR address block as the key value, and use the network prefix length as the comparison bit to create a new node, if the CIDR block belongs to the IPV4 address block then turn to (a); otherwise turn to (b).

(a) If the IPV4 head node is empty, then use this new node as the IPV4 head node, and associate its attribution information with this node, and turn to the second step; otherwise, select the IPV4 head node, and turn to the third step.

(b) If the IPV6 head node is empty, then use this new node as the IPV6 head node, and associate its attribution information with this node, and turn to the second step; otherwise, select the IPV6 head node, and turn to the third step.

The third step is to traverse the corresponding subtree (IPV4 or IPV6) from the head node, and set the comparison bit of the current node traversed in the query tree to be n, if the n+1th bit of the new node key value to be inserted is 0, then Traverse the left child node of the current node in the query tree, if the n+1th bit is 1, traverse the right child node of the current node in the query tree until any condition in (c) is encountered, and calculate the traversal in the query tree Find the common network prefix length L of the current node and the node to be inserted, and go to the fourth step.

(c) Condition 1: The leaf node in the query tree has been traversed; Condition 2: The current node traversed is an internal node whose comparison bit is greater than that of the new node to be inserted and contains CIDR block information.

In the fourth step, in the query tree, follow the rule in (d) to fall back to the position where the new node is inserted, and go to the fifth step.

(d) If L is greater than the comparison bit of the current node in the tree, roll back to the parent node of the current node, and reset the current node as its parent node (that is, set the parent node as the current node) until it rolls back to L less than Or equal to the comparison bit of the current node in the tree.

The fifth step is to insert a new node into the query tree according to the rules in (e-h), adjust the query tree according to the situation, and associate its attribution information to the node, and go to the second step.

(e) If it is satisfied that L is equal to the comparison bit of the current node in the query tree, and L is equal to the comparison bit of the new node to be inserted, if the current node is an internal node that does not contain CIDR block information, replace the internal node with the new node to be inserted , otherwise it is not processed (that is, if the current node is an internal node containing CIDR block information, it means that the CIDR block information already exists and does not need to be inserted into the tree again).

(f) If it is satisfied that L is equal to the comparison bit of the current node in the query tree and L is less than the comparison bit of the new node to be inserted, the new node is inserted into the tree as a child node of the current node in the tree. If the L+1th bit of the binary string of the CIDR block is 0, it is used as the left child node of the current node, and if the L+1th bit is 1, it is used as the right child node of the current node.

(g) If it is satisfied that L is equal to the comparison bit of the new node to be inserted and L is less than the comparison bit of the current node in the query tree, insert the new node into the tree as the parent node of the current node (replacing the position of the current node in the tree) , the current node and its subtree are used as the subtree of the new node. If the L+1th bit of the binary string of the CIDR block of the current node is 0, it is used as the left subtree of the new node. If the L+1th bit is 1, then as the right subtree of the new node.

(h) If it is satisfied that L is less than the comparison bit of the new node to be inserted and L is less than the comparison bit of the current node in the query tree, create a new internal node, set its keyword to empty, and set its comparison bit to L to replace the current node in the tree position, if the L+1th bit of the binary string of the CIDR block of the new node to be inserted is 0, then it will be the left child node of the new internal node, and the current node and its subtree will be the right subtree of the new internal node. The L+1th bit of the binary string of the new node CIDR block is 1, then it is used as the right sub-node of the newly-built internal node, and the current node and its subtree are used as the left sub-tree of the newly-built internal node.

The sixth step is to complete the construction of the IP address attribution information query tree.

6. The present invention proposes a real-time update algorithm for the IP address attribution information query tree of the present invention, which can insert new nodes into the query tree in time, or delete nodes from the tree to complete the update of the query tree. According to one embodiment of the present invention, the algorithm for updating the query tree in the present invention includes the following steps:

In the first step, if the attribution information update configuration file is read, go to step five; otherwise, read a CIDR attribution information record from the attribution information update configuration file, and judge the update operation, if it is insert, go to the second step; if For deletion, go to the third step.

In the second step, according to the IP address category of the read CIDR record, select the corresponding head node, use the CIDR address block as the key value, and use the network prefix length as the comparison bit to create a new node, and execute the operation of constructing the IP address attribution query tree The third, fourth, and fifth steps are to insert the corresponding node of the CIDR block record into the tree; go to the first step.

The third step is to select the corresponding head node according to the IP address category, perform the third and fourth steps of constructing the IP address attribution query tree, locate the node CIDR of the CIDR node to be deleted in the query subtree, and compare the nodes in the tree Whether the CIDR is consistent with the CIDR to be deleted, if they are consistent, go to step 4, otherwise return an error message.

The fourth step is to delete the given CIDR block information from the corresponding position in the query tree according to the rules in (i-k), and adjust the query tree according to the situation; go to the first step.

(i) If the node to be deleted in the tree is a leaf node, then delete the entire node information (including CIDR attribution information), if the leaf node is the left child node of its parent node, mark the left child node of its parent node as empty, otherwise The same is true.

(j) If the node to be deleted in the tree is an internal node and has only one child node, delete the entire node information (including CIDR attribution information), and replace its position in the tree with its child node.

(k) If the node to be deleted in the tree is an internal node and has two child nodes, only the CIDR information of the node is deleted, and the node and its comparison bit are retained, and the entire tree structure is not adjusted.

The fifth step is to complete the update of the IP address attribution information query tree.

7. The present invention proposes a fast IP address attribution information query algorithm for the IP address attribution information query tree of the present invention. According to an embodiment of the present invention, the IP address attribution information query of the present invention needs to quickly find the first one that satisfies the longest Matching CIDR blocks, and the CIDR blocks that satisfy the longest match are generally located at a certain leaf node or at an internal node close to the leaf node, so how to quickly reach these nodes is related to the query speed, the present invention The designed method of first finding leaves and then backtracking can solve this problem very well, avoiding the sequential matching and comparison of relevant nodes when traversing the query tree, so that the overall average query comparison times are greatly reduced, and the query speed is greatly improved. The fast query algorithm of the present invention comprises the following steps:

The first step is to complete the initialization work, including setting up the stack and so on.

The second step is to select an IPV4 head node or an IPV6 head node in the query tree according to the type of the IP address to be queried, and traverse the query tree in a depth-first manner from the head node; turn to the third step.

The third step is to perform the leaf-finding operation in (1) until the leaf node of the query tree is reached, and in the leaf-finding traversal process, all nodes containing CIDR block attribution information in the query tree (including all internal nodes and the last arrived leaf node) into the stack set by the first step operation; turn to the fourth step.

(l) Let the comparison bit of the current node traversed in the tree be n, if the n+1th bit of the binary string corresponding to the IP address to be queried is 0, then traverse the left child node of the current node, if the n+1th bit If it is 1, it traverses the right child node of the current node.

The fourth step is to traverse the stack containing the CIDR block address attribution information node until the stack is empty or the top node of the stack matches the IP address to be queried. If the top node of the stack does not match the IP address to be queried, the top node of the stack is popped (ie , discard the unmatched nodes); turn to step five.

The fifth step is to judge the state of the stack. If the stack is empty (that is, if all the nodes in the stack do not match, an empty stack will appear), return a null value or not found; if the stack is not empty, go to the sixth step.

The sixth step is to judge the configuration status of IP address attribution information. If multi-homing information is configured, the attribution information of all nodes in the stack will be returned. If only unique attribution information is configured, only the attribution information of the top node in the stack will be returned (due to The node is the CIDR block that satisfies the longest match, and as long as the top element of the stack satisfies the match, the rest of the nodes in the stack will also satisfy the match).

Compared with prior art, positive effect of the present invention is:

1. in the present invention, the IP address attribution information query method only needs to be initialized when the main body system (such as a network monitoring system, a security system) starts, and then resides in the internal memory. Only when it is found that there is an update operation in the corresponding configuration file, The entire tree will be updated again, the monitoring objects deleted in the configuration will be deleted from the tree, and the monitoring objects added in the configuration will be inserted into the tree, which is more efficient than database queries.

2. The tree index method of the IP CIDR attribution information in the present invention can effectively store the IP CIDR attribution information, and the IP CIDR blocks of different attribution information in the present invention are allowed to contain the same IP address, and one IP address belongs to one or more CIDR block has one or more attribution information, and can return the attribution information of all CIDR blocks matching the IP address in the query tree during query, and can update the attribution information of IP CIDR address blocks online according to real-time needs. Compared with existing Some Geo IP, QQ binary address library has higher flexibility.

3. The time complexity of the leaf-seeking and fallback steps of the IP address fast query algorithm in the present invention is related to the depth of the IP address attribution information query tree, and the time complexity is optimally O(log N), and worst is O(N ) (for IPV4 address N is 32, and for IPV6 address N is 128), since these two steps only need to do comparison operations of bit operations, the query speed is very fast even in the worst case, and the practice of first finding leaves has proved that It can minimize the expected value of the number of comparisons in the entire query, increase the average query speed, and can well meet the real-time requirements of the operator-level network traffic monitoring system in milliseconds; at the same time, its space complexity is O(n)(n is the number of CIDR block addresses), and the storage capacity provided by the current hardware fully meets its requirements.

Description of drawings

Accompanying drawing 1 is the example figure that the present invention constructs IP address attribution information inquiry tree;

Accompanying drawing 2 is the IP query tree schematic diagram instantiated with the IPV4 intranet address block of structure of the present invention;

Accompanying drawing 3 is the algorithm flowchart of the structure IP address attribution information inquiry tree of the present invention;

Accompanying drawing 4 is the schematic diagram of the IP query tree after the update operation of the query tree of accompanying drawing 2 of the present invention;

Accompanying drawing 5 is the flow chart of IP address attribution information query tree search algorithm of the present invention.

detailed description

The technical solutions in the embodiments of the present invention will be fully described below in conjunction with the drawings in the embodiments of the present invention. Including the construction and update of the IP address attribution information query tree and the IP address attribution information query algorithm.

1. IP address attribution information query tree construction includes two steps:

First, define IP CIDR address block attribution information to form a configuration file.

The first step is to determine the required attribution information record format based on the requirements in practical applications, which consists of fields such as CIDR block and country name, among which the CIDR block field is an indispensable field, and other fields can be increased or decreased according to actual needs.

In the second step, according to the attribution information record format determined in the first step, the required IPCIDR blocks and attribution information fields are extracted from GeoIP csv and other files, and field values that do not exist in GeoIP csv and other files are added to form attribution information records ;At the same time, add a custom IP CIDR block (does not exist in GeoIP) attribution information record;

The third step is to save the IP CIDR attribution information record in the configuration file, as shown in Table 1.

Table 1 is a schematic representation of the IP CIDR address attribution information configuration file of the present invention:

CIDR block Country Name institution name Organization Type AS number *.*.*.*/twenty two CN 247 2 7497 *:*:*:*::0/48 CN 57 1 7497

Second, construct an IP address attribution information query tree.

As shown in Figure 1, it is the IP address attribution information query tree schematic diagram of the present invention structure, and wherein tree root node comprises two child nodes, and one is IPV4 head node, and the CIDR attribution information of IPV4 is stored in the tree taking this node as root; One is the IPV6 head node, and the CIDR attribution information of IPV6 is stored in a tree rooted at this node.

Figure 2 is a schematic diagram of a query tree with only IPV4 address blocks. In order to facilitate the description of the structure of the query tree, nodes in the tree are instantiated with IPV4 intranet address blocks.

FIG. 3 is a flowchart of an algorithm for constructing an IP address attribution information query tree according to an embodiment of the present invention. Below in conjunction with the configuration file shown in Table 1, Fig. 2 and Fig. 3, take the structure of IPV4 query tree in Fig. 2 as an example, describe in detail the structure of the IP address attribution information query tree in the embodiment of the present invention (the structure of the IPV6 tree and the structure of the IPV4 tree The process is the same and will not be described below):

The CIDR blocks in the configuration file are: 192.168.10.0/23, 192.168.12.0/23, 192.168.8.0/21, 192.168.4.0/22.

The first step is to initialize the root node of the IP address attribution information query tree and the IPV4 head node.

The second step is to read the 192.168.10.0/23 block record from the configuration file, use 192.168.10.0 as the key value, and use 23 as the comparison bit to create a new node, perform the following operations in (a), and insert it into the tree .

(a) At this time, the IPV4 head node is empty, and the 92.168.10.0/23 node is used as the IPV4 head node, and its attribution information is associated with this node.

The third step is to read the 192.168.12.0/23 block record from the configuration file, use 192.168.12.0 as the key value, and 23 as the comparison bit, create a new node, perform the following (b-e) operations, and insert it into the query tree , and associate its attribution information with this node.

(b) Start traversing the corresponding IPV4 query tree from the head node created in the first step. There is only one node 192.168.10.0/23 in the current tree, so it has traversed to reach the leaf node in the IPV4 query tree, terminate the traversal, and calculate the node to be inserted The common network prefix length with the current node in the tree is 21; since there is only one node in the tree, no fallback operation is performed.

(c) Create an internal node, set its CIDR block address to be empty, compare bit to 21, and serve as the parent node of 192.168.10.0/23 and 192.168.12.0/23.

(d) Using the comparison bit calculation of the internal node created in (c), it can be known that 192.168.10.0/23 is the left child node of the internal node, and 192.168.12.0/23 is its right child node.

(e) Readjust the internal node in (c) to be the head node of the IPV4 query tree.

The fourth step is to read the 192.168.8.0/21 block record from the configuration file, use 192.168.8.0 as the key value, and 21 as the comparison bit, create a new node, perform the following (f-h) operations, and insert it into the query tree , and associate its attribution information to this node.

(f) Start traversing the corresponding IPV4 query tree from the adjusted new head node in the third step, and use the current node comparison bit calculation in the tree to know that the next step is to choose to traverse its left subtree node 192.168.10.0/23, which is already The traversal reaches the leaf node in the IPV4 query tree, terminates the traversal, and calculates that the common network prefix length of the node to be inserted and the current node in the tree is 21.

(g) Perform a rollback operation, and roll back to the head node whose comparison bit is 21 according to the common network prefix length calculated in (f).

(h) Return to the IPV4 head node after executing (g), which is an internal node, and the internal node does not save the CIDR block address information, so replace the current node in the tree with the 192.168.8.0/21 block address node.

The fifth step is to read the 192.168.4.0/22 block record from the configuration file, use 192.168.4.0 as the key value, and use 22 as the comparison bit, create a new node, perform the following (i-m) operations, and insert it into the tree .

(i) From the new head node 192.168.8.0/21 adjusted in the fourth step, start traversing the corresponding IPV4 query tree, and use the head node comparison bit calculation to know that the next step selects to traverse its left subtree node 192.168.10.0/23, At this time, the traversal has reached the leaf node in the IPV4 query tree, the traversal is terminated, and the length of the common network prefix between the node to be inserted and the current node in the tree is calculated to be 20.

(j) Perform a rollback operation, and roll back to the head node whose comparison bit is 21 according to the common network prefix length calculated in (i).

(k) Create an internal node, set its CIDR block address to be empty, compare bit to 20, and serve as the parent node of 192.168.8.0/21 and 192.168.4.0/22.

(l) Using the comparison bit calculation of the internal node created in (k), it can be seen that 192.168.4.0/22 is the left child node of the internal node, and 192.168.8.0/21 is the right child node.

(m) Readjust the internal node in (k) to be the head node of the IPV4 query tree.

The sixth step is to complete the construction of the IPV4 address attribution information query tree.

2. The IP address attribution information query tree update includes adding new CIDR block information and deleting existing CIDR block information. The new operation is the same as inserting a new node when constructing the tree, so the following will not be described in detail; Find the node that contains the specified CIDR in the tree, then delete the CIDR information of the node, and adjust the query tree according to the situation.

Figure 4 is a schematic diagram of the query tree after deleting the address block 192.168.8.0/21 in Figure 2. The following will combine Figure 2 and Figure 4 to delete the 192.168.8.0/21 address block in the query tree in Figure 2 as an example to describe this in detail. Invention embodiment IPV4 address attribution information query tree deletion CIDR update operation:

The first step is to read the 192.168.8.0/21 block record from the update tree configuration file and construct a new node.

The second step is to traverse the entire query tree from the IPV4 head node in Figure 2, and use the current node comparison bit calculation in the tree to know that the next step is to traverse the node 192.168.8.0/21, and then traverse 192.168.10.0/23. The traversal reaches the leaf node in the IPV4 query tree, terminates the traversal, and calculates that the common network prefix length of the node to be deleted and the current node in the tree is 21.

The third step is to perform a rollback operation. According to the common network prefix length calculated in the second step, roll back to the internal node 192.168.8.0/21 whose comparison bit is 21; the comparison finds that the CIDR block of the current internal node is also 192.168. 8.0/21, so it can be deleted correctly, perform the delete operation.

In the fourth step, according to the structure of the query tree, although the current node 192.168.8.0/21 in the query tree is an internal node, it has two child nodes, so there is no need to adjust the tree structure after deleting the 192.168.8.0/21 block information, so you only need to start from The current node in the tree deletes its CIDR block information and sets its comparison bit to 21.

The fifth step is to complete the update of the query tree and update the configuration file.

3. IP address attribution information query tree query algorithm

As shown in Figure 5, it is a flow chart of the IP address attribution information query tree search algorithm of the present invention. The following will combine the query tree in Figure 2 and the query tree search flow chart in Figure 5, taking the query 192.168.10.1 as an example to describe the implementation of the present invention in detail Example IP address attribution information query process:

The first step is to complete the initialization stack and so on.

The second step is to traverse the entire query tree from the IPV4 head node in Figure 2, and use the current node comparison bit calculation in the tree to know that the next step is to traverse the node 192.168.8.0/21, and then traverse 192.168.10.0/23. When the traversal reaches the leaf node in the IPV4 query tree, the traversal is terminated; and the CIDR information 192.168.8.0/21 and 192.168.10.0/23 encountered during the leaf-seeking traversal process are sequentially pushed into the stack set by the first step operation.

The third step is to traverse the stack that saves the CIDR block address information in the second step, first take out the top element of the stack 192.168.10.0/23, and compare the first 23 bits of 192.168.10.0 and 192.168.10.1, the result is the same, so query 192.168.10.1 belongs to the 192.168.10.0/23 block address.

The fourth step is to judge the configuration status of IP address attribution information. If multi-homing information is configured, the attribution information of 192.168.8.0/21 and 192.168.10.0/23 in the stack will be returned. If only unique attribution information is configured, only the attribution information will be returned to the stack Ownership information of the top node 192.168.10.0/23.

Claims (9)

1. an IP address attribution information index method, the steps include:

1) choose or set up an IP cidr address block attaching information configuration file；Initialize IP address attribution information inquiry tree and Its subtree, it is respectively IPV4 query sub tree and IPV6 query sub tree；

2) the cidr block record in described configuration file is read；For each cidr block record, using cidr address block as key Value, using its network prefix length as comparing position to create the new node of described query tree；

21) if this cidr block belongs to IPV4 address block, and the head node of current IPV4 query sub tree is empty, then with this New node is as the head node of IPV4 query sub tree, and its attaching information is associated with this new node, if cephalomere Point is not empty, then select the head node of IPV4 query sub tree to carry out step 22)；If this cidr block belongs to IPV6 Address block, and the head node of current IPV6 query sub tree be sky, then using this new node as IPV6 query sub tree Head node, and its attaching information is associated with this new node, if head node is not empty, then select IPV6 inquiry The head node of subtree carries out step 22)；

22) begin stepping through the query sub tree of correspondence from selected head node, until meeting condition one or condition two, calculating is looked into Ask the network prefix length L that the present node traversed in subtree is common with this new node；If this L-value is more than current The comparison position of node, then return back to the father node of present node, and to arrange this father node be present node, until returning Fall back on this L-value less than or equal to the comparison position of present node in query sub tree till；

23) according to this L-value and step 22) determined by present node determine the on position of this new node, by this new node It is inserted in query sub tree, and its attaching information is associated with this new node；

Wherein, condition one: have stepped through arrival query tree leaf node；Condition two: the present node traversed is for comparing position More than the comparison position of this new node, and comprise the internal node of cidr block information.

2. the method for claim 1, it is characterised in that the method for the query sub tree that traversal is corresponding is: sets in query sub tree and travels through To present node to compare position be n, if the (n+1)th of this new node key assignments is 0, then in traversal queries subtree, present node is left Child node, if the (n+1)th of this new node key assignments is 1, then the right child node of present node in traversal queries subtree.

3. method as claimed in claim 1 or 2, it is characterised in that the method determining the on position of this new node is:

If a) L is equal to comparison position and the comparison position of this new node of present node, and present node is not for containing cidr block letter The internal node of breath, then replace this internal node by this new node；

If b) L equal to the comparison position of present node and L less than the comparison position of this new node, then using this new node as present node A child node, if the binary string L+1 position of the cidr block of this new node is 0, then as a left side for present node Child node, if L+1 position is 1, then as the right child node of present node；

If c) L equal to the comparison position of this new node and L less than the comparison position of present node, then using this new node as present node Father node, if the L+1 position of the binary string of present node cidr block is 0, then as the left subtree of this new node, If L+1 position is 1, then as the right subtree of this new node；

If d) L is less than the comparison position of this new node and L less than the comparison position of present node, the most newly-built internal node, it is set and closes Key word for empty, to compare position be L, replaces the position of present node, if the binary string L+1 of this new node cidr block Position is 0, then using this new node as the left child node of this newly-built internal node, present node and subtree thereof are new as this Build the right subtree of internal node, if the binary string L+1 position of this new node cidr block is 1, then this new node is made For the right child node of this newly-built internal node, present node and subtree thereof as the left subtree of this newly-built internal node.

4. method as claimed in claim 1 or 2, it is characterised in that the method for building up of described configuration file is:

41) arranging attaching information record format, IP address attribution information record is by corresponding IP cidr block field and some ownership Information field forms, and form is: IP CIDR information, country /region information, urban information, mechanism information, AS Information, longitude, latitude information；Wherein IP CIDR information word segment value is not empty；

42) create attaching information, first according to the field format of IP address attribution record, take out in secondary IP address attaching information storehouse Corresponding field；For there is not the cidr block of relevant attaching information record in IP address base, then create and make by oneself The IP cidr address attaching information record of justice；

43) IP cidr block address is preserved as a record with attaching information, generate described configuration file, wherein every record Occupy a line；Configuration file is usually and preserves IP address attribution information record in the way of text.

5. method as claimed in claim 1 or 2, it is characterised in that in described configuration file, the IP cidr block of different attaching informations Allow to comprise identical IP address.

6. the method for claim 1, it is characterised in that the method updating described query tree is:

61) the CIDR record in attaching information more new configuration file is read, using cidr address block as key assignments, before its network Sew length as comparing position to create new node a；If updating operation is to insert, then carry out step 62)；If deleting, then enter Row step 63)；

62) other according to the IP address class in node a, select the head node of respective queries subtree, perform step 22) and 23), This new node a and attaching information thereof are inserted in this query sub tree；

63) other according to the IP address class in node a, select the head node of respective queries subtree, perform step 22), navigate to The CIDR node to be deleted node CIDR in this query sub tree, if this node CIDR is consistent with CIDR to be deleted, then enters Row step 64), otherwise return error message；

64) according to rule (i)-(k), from this query sub tree, delete the cidr block information of relevant position, and adjust query tree；

If i node to be deleted is leaf node in () this query sub tree, then delete whole nodal information, if this leaf node is it The left child node of father node, then be labeled as sky by left for its father node child node, and vice versa；

If j in () this query sub tree, node to be deleted is internal node and only one of which child node, then delete this internal node and Attaching information, and replace its position in tree by its child node；

If k node to be deleted is internal node and has two child nodes in () this query sub tree, the most only delete this internal node CIDR information, retains this internal node and compares position.

7. an IP address attribution information method for quickly querying based on indexing means described in claim 1, the steps include:

71) in query tree, IPV4 head node or IPV6 head node are selected, from selected head according to the type of IP address to be checked Node starts depth first method traversal queries tree, until arriving the leaf node of query tree, and in ergodic process In the middle stack that node press-ins containing cidr block attaching information all in query tree are arranged；

72) travel through each node in this stack, search the node that IP address all and to be checked is mated, carry out step 73), if not having There is the node mated with IP address to be checked, then return null value or do not find；

73) IP address attribution information configuration state is judged, if being configured with many attaching informations, then the ownership of all nodes in return stack Information, if being only configured with unique Home information, then the attaching information of a return stack top node.

8. querying method as claimed in claim 7, it is characterised in that the method for traversal queries tree is: set query tree traverses ought The comparison position of front nodal point is n, if binary string (n+1)th corresponding to IP address to be checked is 0, then and traversal present node Left child node, if (n+1)th is 1, then travels through the right child node of present node.

9. querying method as claimed in claim 7, it is characterised in that the node in described stack includes: all during traversal queries tree Internal node containing cidr block attaching information and the last leaf node arrived.