CN115801736A - IP address library construction loading method and device and IP address query method and device - Google Patents
IP address library construction loading method and device and IP address query method and device Download PDFInfo
- Publication number
- CN115801736A CN115801736A CN202310024056.XA CN202310024056A CN115801736A CN 115801736 A CN115801736 A CN 115801736A CN 202310024056 A CN202310024056 A CN 202310024056A CN 115801736 A CN115801736 A CN 115801736A
- Authority
- CN
- China
- Prior art keywords
- node
- executing
- address
- mask
- black tree
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000000034 method Methods 0.000 title claims abstract description 53
- 238000011068 loading method Methods 0.000 title claims abstract description 45
- 238000010276 construction Methods 0.000 title claims description 13
- 230000011218 segmentation Effects 0.000 claims description 18
- 238000004590 computer program Methods 0.000 claims description 12
- 230000009286 beneficial effect Effects 0.000 description 3
- 238000006243 chemical reaction Methods 0.000 description 2
- 230000007547 defect Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 238000000926 separation method Methods 0.000 description 1
- 238000006467 substitution reaction Methods 0.000 description 1
Images
Classifications
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The invention provides a method and a device for constructing and loading an IP address library and a method and a device for inquiring an IP address, and relates to the technical field of IP address inquiry. Compared with the prior art, the method has the advantages that the memory consumption of the IP address library constructed and loaded through the multi-level red-black tree and bit operation is low, and the advantage of memory consumption is more obvious in the address library with larger data volume. And the IP address is inquired based on the constructed IP address library, the time consumption is also obviously reduced, and the inquiry speed is higher if the IP mask or the IP section is contained in the address library.
Description
Technical Field
The invention relates to the technical field of IP address query, in particular to a method and a device for constructing and loading an IP address library and a method and a device for querying an IP address.
Background
With the characteristics of the internet, each interconnected terminal or device is assigned an IP address, and how to efficiently and quickly view the performance of an IP from a massive IP address library is particularly important.
At present, IP address query is mainly realized by using HaHill (Hill-Shake)Whether the IP address to be searched exists or not is inquired from the massive IP addresses. However, the existing method has the problems of large memory consumption and slow query speed when the address base is constructed and loaded.
In order to solve the above problems, a method with low memory consumption and fast query speed is needed.
Disclosure of Invention
Technical problem to be solved
Aiming at the defects of the prior art, the invention provides a method and a device for constructing and loading an IP address library, and a method and a device for inquiring an IP address, and solves the problem of large memory consumption in constructing the address library in the prior art.
(II) technical scheme
In order to realize the purpose, the invention is realized by the following technical scheme:
in a first aspect, a method for constructing and loading an IP address library is provided, where the method includes:
s101, acquiring first IP data, and segmenting the first IP data according to a segmentation rule to obtain second IP data; the segmentation rule is that 8-bit masks are used as units and the minimum mask bit principle is used for segmentation;
s102, inquiring the node A corresponding to the second IP data in the first-level red-black tree, if the node A does not exist, inserting the node A into the first-level red-black tree, and then executing S103; otherwise, directly executing S103;
s103, judging whether the node A is marked as a full mask, if so, loading the second IP data till then, and returning to S101; otherwise, executing S104;
s104, judging whether the corresponding mask is 8, if so, marking the node A as a full mask, and returning to S101; otherwise, setting the B position as 1 on the node A corresponding to the first-level redblack tree, and then executing S105;
s105, inquiring a node B corresponding to the second IP data on the secondary red-black tree pointed by the node A, if the node B does not exist, inserting the node B into the secondary red-black tree, and then executing S106; otherwise, directly executing S106;
s106, judging whether the corresponding mask is 16, if so, marking the node B as a full mask, and returning to S101; otherwise, setting the C position to be 1 on the B node corresponding to the second-level red-black tree, and then executing S107;
s107, inquiring a C node on the three-level red-black tree pointed by the B node, if the C node does not exist, inserting the C node into the three-level red-black tree, and then executing S108; otherwise, directly executing S108;
s108, judging whether the corresponding mask is 24, if so, marking the C node as a full mask, and returning to S101; otherwise, setting the D position as 1 on the C node of the three-level red-black tree.
Further, the first IP data is in any form of IP/mask, IP segment or single IP; the second IP data is in any form of IP/mask or single IP.
In a second aspect, an IP address library building and loading apparatus is provided, where the apparatus includes:
the first IP data splitting module is used for executing the S101, obtaining first IP data and splitting the first IP data according to a splitting rule to obtain second IP data; the segmentation rule is that 8-bit masks are used as units and the minimum principle of mask bits is used for segmentation;
the building and loading module is used for building and loading an IP address library based on the second IP data, and the steps comprise:
s102, inquiring the node A corresponding to the second IP data in the first-level red-black tree, if the node A does not exist, inserting the node A into the first-level red-black tree, and then executing S103; otherwise, directly executing S103;
s103, judging whether the node A is marked as a full mask, if so, loading the second IP data till then, and returning to S101; otherwise, executing S104;
s104, judging whether the corresponding mask is 8, if so, marking the node A as a full mask, and returning to S101; otherwise, setting the B position as 1 on the node A corresponding to the first-level redblack tree, and then executing S105;
s105, inquiring a node B corresponding to the second IP data on the secondary red-black tree pointed by the node A, if the node B does not exist, inserting the node B into the secondary red-black tree, and then executing S106; otherwise, directly executing S106;
s106, judging whether the corresponding mask is 16, if so, marking the node B as a full mask, and returning to S101; otherwise, setting the C position to be 1 on the B node corresponding to the second-level red-black tree, and then executing S107;
s107, inquiring a C node on the three-level red-black tree pointed by the B node, if the C node does not exist, inserting the C node into the three-level red-black tree, and then executing S108; otherwise, directly executing S108;
s108, judging whether the corresponding mask is 24, if so, marking the C node as a full mask, and returning to S101; otherwise, setting the D position as 1 on the C node of the three-level red-black tree.
In a third aspect, an IP address query method is provided, where the method includes a step of constructing a load IP address library, and further includes the following steps:
s201, acquiring an IP address to be inquired;
s202, inquiring the node A in the first-level red-black tree, and if the node A exists, executing S203; otherwise, obtaining a first query result; the first query result is used for indicating that the IP address is not queried;
s203, judging whether the node A is marked as a full mask or not, and if so, obtaining a second query result; otherwise, executing S204; the second query result is used for indicating that the IP address is queried;
s204, judging whether the B position of the node A is set; if yes, go to S205; otherwise, obtaining a first query result;
s205, inquiring whether the node B is marked with a full mask in the secondary red-black tree pointed by the node A, and if so, obtaining a second inquiry result; otherwise, executing S206;
s206, judging whether the C bit of the node B is set; if yes, go to S207; otherwise, obtaining a first query result;
s207, inquiring whether the node C is marked with the full mask in the three-level red-black tree pointed by the node B, and if so, obtaining a second inquiry result; otherwise, executing S208;
s208, judging whether the D position of the C node is set or not, and if so, obtaining a second query result; otherwise, a first query result is obtained.
In a fourth aspect, an IP address querying device is provided, including: the IP address library construction loading apparatus further includes:
a query module for performing the steps of:
s201, acquiring an IP address to be inquired;
s202, inquiring the node A in the first-level red-black tree, and if the node A exists, executing S203; otherwise, obtaining a first query result; the first query result is used for indicating that the IP address is not queried;
s203, judging whether the node A is marked as a full mask, and if so, obtaining a second query result; otherwise, executing S204; the second query result is used for indicating that the IP address is queried;
s204, judging whether the B position of the node A is set; if yes, go to S205; otherwise, obtaining a first query result;
s205, inquiring whether the node B is marked with a full mask in the secondary red-black tree pointed by the node A, and if so, obtaining a second inquiry result; otherwise, executing S206;
s206, judging whether the C position of the node B is set; if yes, go to S207; otherwise, obtaining a first query result;
s207, inquiring whether the node C is marked with a full mask in the three-level red-black tree pointed by the node B, and if so, obtaining a second inquiry result; otherwise, executing S208;
s208, judging whether the D position of the C node is set or not, and if so, obtaining a second query result; otherwise, a first query result is obtained.
In a fifth aspect, there is provided a computer-readable storage medium,
the system comprises a storage unit, a loading unit, a processing unit and a control unit, wherein the storage unit stores a computer program for constructing and loading an IP address library, and the computer program enables a computer to execute the IP address library constructing and loading method;
or it stores a computer program for IP address query, wherein the computer program causes a computer to execute the above-described IP address query method.
In a sixth aspect, an electronic device is provided, comprising:
one or more processors;
a memory; and
one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the programs comprising instructions for performing the above-described IP address library build load method or the above-described IP address query method.
(III) advantageous effects
The invention provides a method and a device for constructing and loading an IP address library and a method and a device for inquiring an IP address. Compared with the prior art, the method has the following beneficial effects:
(1) Compared with the prior art, the method has the advantages that the memory consumption of the IP address library constructed and loaded is low, and the memory consumption of the address library with larger data volume is more obvious. Loading all single IPv4 addresses (2 ^32= 4294967296), for example, consumes 1.129G of memory and, if there is an IP mask and an IP segment, less memory.
(2) Compared with the prior art, the method has the advantages that the time consumption is obviously reduced when the IP address is inquired based on the constructed IP address base, the time consumption for inquiring one IP is microsecond grade, about 490 microseconds, when 2049 address bases are loaded and the same equipment environment is used, and the inquiry speed is higher if the address base contains an IP mask or an IP section. Whereas the prior art requires 2 ten thousand microseconds to match an IP address in the same scenario.
Drawings
In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings used in the description of the embodiments or the prior art will be briefly described below, it is obvious that the drawings in the following description are only some embodiments of the present invention, and for those skilled in the art, other drawings can be obtained according to the drawings without creative efforts.
FIG. 1 is a flow chart of the embodiment of the present invention for constructing a load IP address library;
fig. 2 is a flowchart of an embodiment of performing an IP query using a built-up IP address library.
Detailed Description
In order to make the objects, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention are clearly and completely described, and it is obvious that the described embodiments are a part of the embodiments of the present invention, but not all of the embodiments. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present invention.
The embodiment of the application solves the problem that an existing address library consumes a large amount of memory by providing a method and a device for constructing and loading the IP address library and a method and a device for inquiring the IP address.
In order to solve the technical problems, the general idea of the embodiment of the application is as follows:
the invention relates to a method for quickly searching an IP in an IP address library, wherein the IP address library can comprise three forms of an IP mask, an IP section, a single IP and the like, and the specified IP is quickly inquired through multi-level red and black trees and bit operation.
In order to better understand the technical solution, the technical solution will be described in detail with reference to the drawings and the specific embodiments.
Example 1:
as shown in fig. 1, the present invention provides a method for building and loading an IP address library, where the method is executed by a computer, and the method includes:
s101, acquiring first IP data, and segmenting the first IP data according to a segmentation rule to obtain second IP data; the segmentation rule is that 8-bit masks are used as units and the minimum principle of mask bits is used for segmentation;
s102, inquiring the node A corresponding to the second IP data in the first-level red-black tree, if the node A does not exist, inserting the node A into the first-level red-black tree, and then executing S103; otherwise, directly executing S103;
s103, judging whether the node A is marked as a full mask, if so, loading the second IP data till then, and returning to S101; otherwise, executing S104;
s104, judging whether the corresponding mask is 8, if so, marking the node A as a full mask, and returning to S101; otherwise, setting the B position to be 1 on the node A corresponding to the first-level red-black tree, and then executing S105;
s105, inquiring a node B corresponding to the second IP data on the secondary red-black tree pointed by the node A, if the node B does not exist, inserting the node B into the secondary red-black tree, and then executing S106; otherwise, directly executing S106;
s106, judging whether the corresponding mask is 16, if so, marking the node B as a full mask, and returning to S101; otherwise, setting the C position as 1 on the B node corresponding to the secondary red-black tree, and then executing S107;
s107, inquiring a C node on the three-level red-black tree pointed by the B node, if the C node does not exist, inserting the C node into the three-level red-black tree, and then executing S108; otherwise, directly executing S108;
s108, judging whether the corresponding mask is 24, if so, marking the C node as a full mask, and returning to S101; otherwise, setting the D position as 1 on the C node of the three-level red-black tree.
The following describes the implementation process of the embodiment of the present invention in detail:
the IP address is a 32-bit binary number, which is usually divided into 4 "8-bit binary numbers" (i.e. 4 bytes), and is usually expressed in the form of a.b.c.d "decimal system, where a.b.c.d is a decimal integer between 0 and 255, and a.b.c.d is also referred to as a segment a to D of the IP address.
For example: the dotted decimal represents an IP address of 100.4.5.6, corresponding to an IP address of 100A, 4B, 5C, and 6D.
The embodiment of the invention comprises two parts: the first is the construction and loading of an IP address library; second is the query of the IP address.
In this embodiment, the node a represents a node corresponding to a in the second IP data, and is data having 255 bits; the node B represents a node corresponding to B in the second IP data, and is data having 255 bits; the C node represents a node corresponding to C in the second IP data, and is data having 255 bits; and the node A in the first-level red-black tree points to the root node of the second-level red-black tree corresponding to the node B, and the node B points to the root node of the third-level red-black tree corresponding to the node C.
In specific implementation, the method comprises the following steps:
s101, acquiring first IP data, and segmenting the first IP data according to a segmentation rule to obtain second IP data; the segmentation rule is to perform segmentation by using an 8-bit mask as a unit and using a mask bit minimum principle.
In the specific implementation: the specific form of the first IP data is not limited herein, and may be, for example, IP/mask, IP segment, single IP (mask is 32), or the like.
(1) The following description takes the first IP data in the form of an IP/mask as an example:
example 1: the IP/mask is 192.0.0.0/6, and the minimum mask bit is 8;
expressing the IP address as 11000000.00000000.00000000.00000000.00000000 in binary;
the mask is represented in binary as 11111100.00000000.00000000.00000000;
the AND operation obtains a network address of 11000000.00000000.00000000.00000000, namely 192.0.0.0;
the main machine position (positions 7 to 8) in the first 8 positions is set to be 1, namely 11000011, and after the main machine position is converted into a decimal system, the decimal system is 195.0.0.0.0, so that the main machine position is finally split into 192.0.0.0/8, 193.0.0.0/8, 194.0.0/8 and 195.0.0.0/8.
Example 2: the IP/mask is 172.22.0.0/13, and the minimum mask bit is 16;
the IP address is represented as 10101100.00010110.00000000.00000000 in binary;
the mask is represented in binary as 11111111.11111000.00000000.00000000;
the and operation results in a network address of 10101100.00010000.00000000.00000000, i.e. 172.16.0.0.
Setting 1 in the host positions (14 th to 16 th positions) in the first 16 positions, namely 10101100.00010111, to be 172.23.0.0 after decimal conversion, and finally splitting to be 172.16.0.0/16;172.17.0.0/16;172.18.0.0/16;172.19.0.0/16;172.20.0.0/16;172.21.0.0/16;172.22.0.0/16;172.23.0.0/16.
The same holds true for the splitting of the mask 24.
Example 3: for a split of mask 32, for example 192.120.22.0/28, where the mask is 28, split at 32:
the IP address is expressed as 11000000.01111000.00010110.00000000 in binary;
the mask is represented in binary as 11111111.11111111111.11111111111.11110000;
the network address obtained after the AND operation is 11000000.01111000.00010110.00000000, namely 192.120.22.0; the last 4 bits (i.e., host position) are set to 1, resulting in:
11000000.01111000.00010110.00001111, after conversion to decimal, 192.120.22.15.
Thus, the final resolution can be: 192.120.22.0 to 192.120.22.15, and the corresponding masks are all 32.
(2) The following description takes the first IP data in the form of IP segments as an example:
example 1: the IP section is 20.229.1.1-20.235.221.20, and the difference of the bits in the 17 th to 24 th ranges can be found by taking an 8-bit mask as a unit, and the range is 229 to 235.
According to the principle of mask bit minimum, the method can be finally split to obtain:
the mask is 24:20.229.2.0/24, 20.229.3.0/24, \ 8230 \ 8230;, 20.229.255.0/24, 20.235.0.0/24, 20.235.1.0/24, \ 8230; \ 8230;, 20.235.220.0/24;
the mask is 16:20.230.0.0/16, 20.231.0.0/16, 20.232.0.0/16, 20.233.0.0/16, 20.234.0.0/16;
the mask is 32:20.229.1.1 is not 20.229.0.0/16 of the initial IP nor 20.229.0.0/24 of the initial IP, so that the initial IP needs to be separated separately, namely 20.229.1 to 20.229.1.255 are obtained by separation, and corresponding masks are all 32. Similarly, the product can be split into 20.235.221.0 to 20.235.221.20.
It can be seen that the second IP data can also be in the form of IP/mask or single IP (mask is 32) according to the split result.
S102, inquiring the node A corresponding to the second IP data in the primary red-black tree, if the node A does not exist, inserting the node A into the primary red-black tree, and then executing S103; otherwise, directly executing S103;
s103, judging whether the node A is marked as a full mask (namely, the positions from 1 to 255 of the node A are all set to 1), if so, loading the second IP data till the second IP data is loaded, and returning to S101 without traversing and loading the subsequent sub red-black trees; otherwise, executing S104;
s104, judging whether the corresponding mask is 8, if so, marking the node A as a full mask, and returning to S101; otherwise, setting the B position to be 1 on the node A corresponding to the first-level red-black tree, and then executing S105; for example, assuming that the second IP data is 192.168.0.0 and there are 1 to 255 bits of data in the a node, 1 is set in the 168 th bit.
S105, inquiring a node B corresponding to the second IP data on the secondary red-black tree pointed by the node A, if the node B does not exist, inserting the node B into the secondary red-black tree, and then executing S106; otherwise, directly executing S106;
s106, judging whether the corresponding mask is 16, if so, indicating that the second IP data only exists on the first-level red-black tree and the second-level red-black tree, marking the node B as a full mask, and returning to S101; otherwise, setting the C position as 1 on the B node corresponding to the secondary red-black tree, and then executing S107;
s107, inquiring a node C on the three-level red-black tree pointed by the node B, if the node C does not exist, inserting the node C into the three-level red-black tree, and then executing S108; otherwise, directly executing S108;
s108, judging whether the corresponding mask is 24, if so, marking the C node as a full mask, and returning to S101; otherwise, setting the D position as 1 on the C node of the three-level red-black tree for identifying D.
Through the steps, the construction and loading of the whole IP address base can be completed, the embodiment is particularly suitable for large address bases, and the advantage of memory consumption is more obvious, for example, the memory consumption can reach 96G when all single IPv4 addresses (2 ^32= 4294967296) are loaded in the prior art, while the embodiment only consumes 1.129G of the memory, and if an IP mask and an IP segment exist, the memory consumption is less.
Example 2:
after the IP address library of the loading embodiment 1 is constructed, in order to further solve the problem of slow query speed in the prior art, this embodiment further provides an IP address query method as shown in fig. 2 on the basis of the IP address library of the loading embodiment 1, and specifically includes the following steps:
s201, acquiring an IP address to be inquired;
s202, inquiring the node A in the first-level red-black tree, and if the node A exists, executing S203; otherwise, obtaining a first query result; the first query result is used for indicating that the IP address is not queried;
s203, judging whether the node A is marked as a full mask or not, and if so, obtaining a second query result; otherwise, executing S204; the second query result is used for indicating that the IP address is queried;
s204, judging whether the B bit of the node A is set; if yes, go to S205; otherwise, obtaining a first query result;
s205, inquiring whether the node B is marked with a full mask in the secondary red-black tree pointed by the node A, and if so, obtaining a second inquiry result; otherwise, executing S206;
s206, judging whether the C position of the node B is set; if yes, go to S207; otherwise, obtaining a first query result;
s207, inquiring whether the node C is marked with a full mask in the three-level red-black tree pointed by the node B, and if so, obtaining a second inquiry result; otherwise, executing S208;
s208, judging whether the D position of the C node is set or not, and if so, obtaining a second query result; otherwise, a first query result is obtained.
By the method, when 2049 address libraries are loaded and under the same equipment environment, the time consumption for inquiring one IP is microsecond, about 490 microseconds, and if the address libraries contain IP masks or IP sections, the inquiring speed is higher. Whereas the prior art requires 2 tens of thousands of microseconds to match one IP address in the same scenario.
Example 3:
the embodiment provides an IP address library constructing and loading device, which includes:
the first IP data splitting module is used for executing S101, acquiring first IP data and splitting the first IP data according to a splitting rule to obtain second IP data; the segmentation rule is that 8-bit masks are used as units and the minimum principle of mask bits is used for segmentation;
the building and loading module is used for building and loading an IP address library based on the second IP data, and the steps comprise:
s102, inquiring the node A corresponding to the second IP data in the first-level red-black tree, if the node A does not exist, inserting the node A into the first-level red-black tree, and then executing S103; otherwise, directly executing S103;
s103, judging whether the node A is marked as a full mask, if so, loading the second IP data till then, and returning to S101; otherwise, executing S104;
s104, judging whether the corresponding mask is 8, if so, marking the node A as a full mask, and returning to S101; otherwise, setting the B position to be 1 on the node A corresponding to the first-level red-black tree, and then executing S105;
s105, inquiring a node B corresponding to the second IP data on the secondary red-black tree pointed by the node A, if the node B does not exist, inserting the node B into the secondary red-black tree, and then executing S106; otherwise, directly executing S106;
s106, judging whether the corresponding mask is 16, if so, marking the node B as a full mask, and returning to S101; otherwise, setting the C position as 1 on the B node corresponding to the secondary red-black tree, and then executing S107;
s107, inquiring a C node on the three-level red-black tree pointed by the B node, if the C node does not exist, inserting the C node into the three-level red-black tree, and then executing S108; otherwise, directly executing S108;
s108, judging whether the corresponding mask is 24, if so, marking the node C as a full mask, and returning to S101; otherwise, setting the D position as 1 on the C node of the three-level red-black tree.
It can be understood that the IP address library construction and loading device provided in the embodiment of the present invention corresponds to the IP address library construction and loading method described above, and the explanation, examples, and beneficial effects of the relevant contents thereof may refer to the corresponding contents in the IP address library construction and loading method, which are not described herein again.
Example 4:
the embodiment provides an IP address query apparatus, including: the IP address library building and loading apparatus according to claim 4, further comprising:
a query module for performing the steps of:
s201, acquiring an IP address to be inquired;
s202, inquiring the node A in the first-level red-black tree, and if the node A exists, executing S203; otherwise, obtaining a first query result; the first query result is used for indicating that the IP address is not queried;
s203, judging whether the node A is marked as a full mask or not, and if so, obtaining a second query result; otherwise, executing S204; the second query result is used for indicating that the IP address is queried;
s204, judging whether the B bit of the node A is set; if yes, go to S205; otherwise, obtaining a first query result;
s205, inquiring whether the node B is marked with a full mask in the secondary red-black tree pointed by the node A, and if so, obtaining a second inquiry result; otherwise, executing S206;
s206, judging whether the C position of the node B is set; if yes, go to S207; otherwise, obtaining a first query result;
s207, inquiring whether the node C is marked with a full mask in the three-level red-black tree pointed by the node B, and if so, obtaining a second inquiry result; otherwise, executing S208;
s208, judging whether the D position of the C node is set or not, and if so, obtaining a second query result; otherwise, a first query result is obtained.
Example 5:
a computer-readable storage medium storing a computer program for IP address library construction loading, wherein the computer program causes a computer to execute the IP address library construction loading method of embodiment 1;
or it stores a computer program for IP address query, wherein the computer program causes a computer to execute the IP address query method described in embodiment 3.
Example 6:
an electronic device, comprising:
one or more processors;
a memory; and
one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the programs comprising instructions for performing the IP address library build load method of embodiment 1 or the IP address query method of embodiment 2.
In summary, compared with the prior art, the invention has the following beneficial effects:
1) Compared with the prior art, the method has the advantages that the memory consumption of the IP address library constructed and loaded is low, and the memory consumption of the address library with larger data volume is more obvious. Loading all single IPv4 addresses (2 ^32= 4294967296), for example, consumes 1.129G of memory and, if there is an IP mask and an IP segment, less memory.
2) Compared with the prior art, the method has the advantages that the time consumption is obviously reduced when the IP address is inquired based on the constructed IP address library, for example, when 2049 address libraries are loaded and under the same equipment environment, the time consumption for inquiring one IP is microsecond, about 490 microseconds, and if the address libraries contain IP masks or IP sections, the inquiry speed is higher. Whereas the prior art requires 2 ten thousand microseconds to match an IP address in the same scenario.
It should be noted that, through the above description of the embodiments, those skilled in the art can clearly understand that each embodiment can be implemented by means of software plus a necessary general hardware platform. With this understanding in mind, the above-described technical solutions may be embodied in the form of a software product, which can be stored in a computer-readable storage medium such as ROM/RAM, magnetic disk, optical disk, etc., and includes instructions for causing a computer device (which may be a personal computer, a server, or a network device, etc.) to execute the methods described in the embodiments or some parts of the embodiments. In this document, relational terms such as first and second, and the like may be used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. Also, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, an element defined by the phrases "comprising a," "8230," "8230," or "comprising" does not exclude the presence of additional like elements in a process, method, article, or apparatus that comprises the element.
The above examples are only intended to illustrate the technical solution of the present invention, but not to limit it; although the present invention has been described in detail with reference to the foregoing embodiments, it will be understood by those of ordinary skill in the art that: the technical solutions described in the foregoing embodiments may still be modified, or some technical features may be equivalently replaced; and such modifications or substitutions do not depart from the spirit and scope of the corresponding technical solutions of the embodiments of the present invention.
Claims (7)
1. An IP address library construction loading method is characterized by comprising the following steps:
s101, acquiring first IP data, and segmenting the first IP data according to a segmentation rule to obtain second IP data; the segmentation rule is that 8-bit masks are used as units and the minimum principle of mask bits is used for segmentation;
s102, inquiring the node A corresponding to the second IP data in the primary red-black tree, if the node A does not exist, inserting the node A into the primary red-black tree, and then executing S103; otherwise, directly executing S103;
s103, judging whether the node A is marked as a full mask, if so, loading the second IP data till then, and returning to S101; otherwise, executing S104;
s104, judging whether the corresponding mask is 8, if so, marking the node A as a full mask, and returning to S101; otherwise, setting the B position to be 1 on the node A corresponding to the first-level red-black tree, and then executing S105;
s105, inquiring a node B corresponding to the second IP data on the secondary red-black tree pointed by the node A, if the node B does not exist, inserting the node B into the secondary red-black tree, and then executing S106; otherwise, directly executing S106;
s106, judging whether the corresponding mask is 16, if so, marking the node B as a full mask, and returning to S101; otherwise, setting the C position to be 1 on the B node corresponding to the second-level red-black tree, and then executing S107;
s107, inquiring a node C on the three-level red-black tree pointed by the node B, if the node C does not exist, inserting the node C into the three-level red-black tree, and then executing S108; otherwise, directly executing S108;
s108, judging whether the corresponding mask is 24, if so, marking the C node as a full mask, and returning to S101; otherwise, setting the D position as 1 on the C node of the three-level red-black tree.
2. The method for constructing and loading the IP address library according to claim 1, wherein the first IP data is in any form of IP/mask, IP section or single IP; the second IP data is in any form of IP/mask or single IP.
3. An IP address library construction loading apparatus, comprising:
the first IP data splitting module is used for executing the S101, obtaining first IP data and splitting the first IP data according to a splitting rule to obtain second IP data; the segmentation rule is that 8-bit masks are used as units and the minimum principle of mask bits is used for segmentation;
the building and loading module is used for building and loading an IP address library based on the second IP data, and the steps comprise:
s102, inquiring the node A corresponding to the second IP data in the first-level red-black tree, if the node A does not exist, inserting the node A into the first-level red-black tree, and then executing S103; otherwise, directly executing S103;
s103, judging whether the node A is marked as a full mask, if so, loading the second IP data till then, and returning to S101; otherwise, executing S104;
s104, judging whether the corresponding mask is 8, if so, marking the node A as a full mask, and returning to S101; otherwise, setting the B position to be 1 on the node A corresponding to the first-level red-black tree, and then executing S105;
s105, inquiring a node B corresponding to the second IP data on the secondary red-black tree pointed by the node A, if the node B does not exist, inserting the node B into the secondary red-black tree, and then executing S106; otherwise, directly executing S106;
s106, judging whether the corresponding mask is 16, if so, marking the node B as a full mask, and returning to S101; otherwise, setting the C position as 1 on the B node corresponding to the secondary red-black tree, and then executing S107;
s107, inquiring a C node on the three-level red-black tree pointed by the B node, if the C node does not exist, inserting the C node into the three-level red-black tree, and then executing S108; otherwise, directly executing S108;
s108, judging whether the corresponding mask is 24, if so, marking the C node as a full mask, and returning to S101; otherwise, setting the D position as 1 on the C node of the three-level red-black tree.
4. A method of IP address lookup comprising the method of claim 1, further comprising the steps of:
s201, acquiring an IP address to be inquired;
s202, inquiring the node A in the first-level red-black tree, and if the node A exists, executing S203; otherwise, obtaining a first query result; the first query result is used for indicating that the IP address is not queried;
s203, judging whether the node A is marked as a full mask or not, and if so, obtaining a second query result; otherwise, executing S204; the second query result is used for indicating that the IP address is queried;
s204, judging whether the B position of the node A is set; if yes, go to S205; otherwise, obtaining a first query result;
s205, inquiring whether the node B is marked with a full mask in the secondary red-black tree pointed by the node A, and if so, obtaining a second inquiry result; otherwise, executing S206;
s206, judging whether the C position of the node B is set; if yes, go to S207; otherwise, obtaining a first query result;
s207, inquiring whether the node C is marked with a full mask in the three-level red-black tree pointed by the node B, and if so, obtaining a second inquiry result; otherwise, executing S208;
s208, judging whether the D position of the C node is set or not, and if so, obtaining a second query result; otherwise, a first query result is obtained.
5. An IP address querying apparatus, comprising: the IP address querying method for implementing claim 4, further comprising:
a query module for performing the steps of:
s201, acquiring an IP address to be inquired;
s202, inquiring the node A in the first-level red-black tree, and if the node A exists, executing S203; otherwise, obtaining a first query result; the first query result is used for indicating that the IP address is not queried;
s203, judging whether the node A is marked as a full mask or not, and if so, obtaining a second query result; otherwise, executing S204; the second query result is used for indicating that the IP address is queried;
s204, judging whether the B position of the node A is set; if yes, go to S205; otherwise, obtaining a first query result;
s205, inquiring whether the node B is marked with a full mask in the secondary red-black tree pointed by the node A, and if so, obtaining a second inquiry result; otherwise, executing S206;
s206, judging whether the C position of the node B is set; if yes, go to S207; otherwise, obtaining a first query result;
s207, inquiring whether the node C is marked with a full mask in the three-level red-black tree pointed by the node B, and if so, obtaining a second inquiry result; otherwise, executing S208;
s208, judging whether the D position of the C node is set or not, and if so, obtaining a second query result; otherwise, a first query result is obtained.
6. A computer-readable storage medium, comprising,
which stores a computer program for an IP address repository build load, wherein the computer program causes a computer to execute the IP address repository build load method according to any one of claims 1-2;
or which stores a computer program for IP address query, wherein the computer program causes a computer to execute the IP address query method according to claim 4.
7. An electronic device, comprising:
one or more processors;
a memory; and
one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the programs comprising instructions for performing the IP address repository construction loading method of any of claims 1-2 or the IP address querying method of claim 4.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310024056.XA CN115801736B (en) | 2023-01-09 | 2023-01-09 | IP address library construction loading method and device and IP address query method and device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310024056.XA CN115801736B (en) | 2023-01-09 | 2023-01-09 | IP address library construction loading method and device and IP address query method and device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN115801736A true CN115801736A (en) | 2023-03-14 |
| CN115801736B CN115801736B (en) | 2023-04-18 |
Family
ID=85428790
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202310024056.XA Active CN115801736B (en) | 2023-01-09 | 2023-01-09 | IP address library construction loading method and device and IP address query method and device |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN115801736B (en) |
Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103902700A (en) * | 2014-04-01 | 2014-07-02 | 浙江大学 | Tree structure data processing method |
| CN104486387A (en) * | 2014-12-02 | 2015-04-01 | 浪潮(北京)电子信息产业有限公司 | Data synchronization processing method and system |
| US20150213150A1 (en) * | 2014-01-24 | 2015-07-30 | King Fahd University Of Petroleum And Minerals | Xml node labeling and querying using logical operators |
| CN106162930A (en) * | 2015-04-07 | 2016-11-23 | 中兴通讯股份有限公司 | The management method carried in equipment direct communication system and device |
| CN106162512A (en) * | 2015-04-09 | 2016-11-23 | 中兴通讯股份有限公司 | A kind of relaying bear control method and device |
| CN106777163A (en) * | 2016-12-20 | 2017-05-31 | 携程旅游网络技术（上海）有限公司 | IP address institute possession querying method and system based on RBTree |
| CN112417227A (en) * | 2021-01-21 | 2021-02-26 | 国能信控互联技术有限公司 | Real-time data storage and query method based on hash table and red-black tree |
-
2023
- 2023-01-09 CN CN202310024056.XA patent/CN115801736B/en active Active
Patent Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20150213150A1 (en) * | 2014-01-24 | 2015-07-30 | King Fahd University Of Petroleum And Minerals | Xml node labeling and querying using logical operators |
| CN103902700A (en) * | 2014-04-01 | 2014-07-02 | 浙江大学 | Tree structure data processing method |
| CN104486387A (en) * | 2014-12-02 | 2015-04-01 | 浪潮(北京)电子信息产业有限公司 | Data synchronization processing method and system |
| CN106162930A (en) * | 2015-04-07 | 2016-11-23 | 中兴通讯股份有限公司 | The management method carried in equipment direct communication system and device |
| CN106162512A (en) * | 2015-04-09 | 2016-11-23 | 中兴通讯股份有限公司 | A kind of relaying bear control method and device |
| CN106777163A (en) * | 2016-12-20 | 2017-05-31 | 携程旅游网络技术（上海）有限公司 | IP address institute possession querying method and system based on RBTree |
| CN112417227A (en) * | 2021-01-21 | 2021-02-26 | 国能信控互联技术有限公司 | Real-time data storage and query method based on hash table and red-black tree |
Also Published As
| Publication number | Publication date |
|---|---|
| CN115801736B (en) | 2023-04-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP2750053B1 (en) | Data storage program, data retrieval program, data retrieval apparatus, data storage method and data retrieval method | |
| CN112817538B (en) | Data processing method, device, equipment and storage medium | |
| CN109460404A (en) | A kind of efficient Hbase paging query method based on redis | |
| CN112131218A (en) | Hash table look-up method, device and equipment for gene comparison and storage medium | |
| CN109858025B (en) | Word segmentation method and system for address standardized corpus | |
| CN111107181B (en) | NAT rule matching method and device, electronic equipment and storage medium | |
| CN115801736B (en) | IP address library construction loading method and device and IP address query method and device | |
| CN114398315A (en) | Data storage method, system, storage medium and electronic equipment | |
| CN111310076B (en) | Geographic position query method, geographic position query device, geographic position query medium and electronic equipment | |
| US20030084031A1 (en) | System and method for searching a signature set for a target signature | |
| US9201982B2 (en) | Priority search trees | |
| CN114268608B (en) | Address segment retrieval method and device, electronic equipment and storage medium | |
| CN114880523A (en) | Character string processing method and device, electronic equipment and storage medium | |
| CN112506651B (en) | Method and equipment for data operation in large-data-volume environment | |
| KR100598341B1 (en) | Method of IP subnet information management on database using binary string | |
| CN113158640A (en) | Code similarity detection method and device, storage medium and electronic equipment | |
| CN112417179A (en) | Address processing method and device | |
| CN111538651A (en) | Interface testing method, device, server and storage medium | |
| CN113268987B (en) | Entity name recognition method and device, electronic equipment and storage medium | |
| US8001533B2 (en) | Maintaining object referential integrity for abstract objects | |
| CN110825846A (en) | Data processing method and device | |
| CN117978780B (en) | IP address storage method, device, equipment, medium and program product | |
| CN113050977B (en) | Data processing method and system | |
| CN114676289A (en) | Processing method, device, terminal and storage medium of prefix tree | |
| CN114036350A (en) | Website query method and device, electronic equipment and storage medium |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant | ||
| PE01 | Entry into force of the registration of the contract for pledge of patent right | ||
| PE01 | Entry into force of the registration of the contract for pledge of patent right |
Denomination of invention: Construction and loading method and device for IP address library, IP address query method and device Granted publication date: 20230418 Pledgee: Industrial Bank Co.,Ltd. Beijing Dongwai Branch Pledgor: Beijing Tianji Youmeng Information Technology Co.,Ltd. Registration number: Y2024980034085 |