CN102868779B - A kind of IPv6 data partition and fast searching method - Google Patents
A kind of IPv6 data partition and fast searching method Download PDFInfo
- Publication number
- CN102868779B CN102868779B CN201210353161.XA CN201210353161A CN102868779B CN 102868779 B CN102868779 B CN 102868779B CN 201210353161 A CN201210353161 A CN 201210353161A CN 102868779 B CN102868779 B CN 102868779B
- Authority
- CN
- China
- Prior art keywords
- layer
- subregion
- leaf node
- ipv6 address
- ipv6
- 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.)
- Active
Links
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The present invention proposes a kind of IPv6 data partition and fast searching method, the different subregion of scale can be divided according to IPv6 address practical situations, carry out Multilayer partition storage to IPv6 address, make when no matter IP partition data is in what area, data can comparatively be evenly distributed in each subregion; And realize IPv6 address segmentation parallel search on this basis, the method for quick position, store to adapt to IPv6 address space and search.In addition, the present invention also sets discrete threshold values, can be polymerized scattered subregion.The present invention the storage of magnanimity partition data and in searching comparatively prior art speed significantly improve, good compatibility is also possessed to the IPv4 address of 24 simultaneously.
Description
Technical field
The present invention relates to the fast searching method of the storage of IPv6 data partition and correspondence, belong to areas of information technology.
Background technology
Mass data adopts partitioning technique to store usually, the rule of subregion will show greatly to be split as multiple little table by certain rule, data are stored into different regions, make the data in logic on a table, be stored in multiple little table according to rule, and different physical location can be stored, thus realize mass data storage.When carrying out data search, according to zoning ordinance, data place subregion can be determined, being directly targeted to corresponding table, making only to relate to specific little table during visit data, thus realize using specific subregion directly to inquire about.Owing to only relating to specific part data in inquiry, can greatly improve data search efficiency.The subregion of mass data stores and fast finding is widely used in mass data, simplifies the management of database, improves the ease for use of data.
At present, the partition method of corresponding IPv4 address date is normally interval at each by the uniform distribution of IPv4 address, determining interval, carrying out quick position and searching when searching according to subregion scope.This method applicability under IPv4 environment that the uniform distribution of IPv4 address is stored in each interval and searched is relatively good.Under but the method cannot be applicable to IPv6 addressing context, this is because IPv4 address has 2
32(4,294,967,295) individual IP address, if by IP uniform distribution in 4096 subregions, each subregion exists 2 at most
20(1,048,576) individual IP address, that is when taking IP as subregion benchmark, each partitioned storage is ten thousand IP more than 100, and the time creating the table of the information of network service in a storage somewhere is less than 1 minute under IPv4 environment; And the method cannot be adopted to carry out subregion and search, because IPv6 address comprises 2 altogether for IPv6 address
128(about 3.4*10
38) individual IP address, create the information of network service table that stores somewhere or certain operator, required storage area is infeasible under existing resource prerequisite, storage time cannot estimate, searching for the IPv6 address date of magnanimity will be time disaster simultaneously, therefore the subregion of IPv4 is stored and lookup method apply to IPv6 addressing context under be in the time or be all spatially infeasible.Clear and definite feature (allocation address block be usually less than/16d) is had in the world for IPv6 address assignment, and according to certain area or for operator, in most data partitions, data volume is less or substantially do not have data, and most of data centralization is in the subregion of only a few.
Summary of the invention
For above-mentioned technical problem, the present invention proposes a kind of foundation IPv6 address practical situations, carries out Multilayer partition storage, the method for fast finding location to IPv6 address.The IPv6 address that data partition method intelligence division scale according to the present invention is different, make when no matter IP partition data is in what area, data can comparatively be evenly distributed in each subregion.And realize IPv6 address segmentation parallel search on this basis, the method for quick position, store to adapt to IPv6 address space and search.The present invention is divided into two parts: Multilayer partition stores and parallel computation quick position.
Multilayer partition stores and adopts the method for partition tree to realize the storage of IPv6 address partition.Layering is a concept in logic, except leaf node needs to store except IPv6 address, other subregion of every layer needs two numeral partition size, one is subregion initial value, one is subregion end value, can use and represent that the data structure of number represents, as array, chained list, hash chained list etc., the present invention does not limit concrete data structure, and the information transmission between them can be transmitted by tree structure.Also namely the step of the building method of partition tree is as follows for partition method:
1) tectonic reverse tree: according to IPv6 address assignment and actual service condition, IPv6 address is divided into n layer, n-th layer sectional is leaf node, and the mapping relations from the 1st layer to n-th layer are 1:2
c1: 2
c2: ...: 2
cn, wherein C1+C2+ ... + Cn=128.Mapping relations formula refers to the mapping of next ATM layer relationsATM of last layer and next-door neighbour, such as, for the mapping of layers 2 and 3: each block of the 2nd layer, corresponding 2
c2the range systems of individual 3rd layer of block.For ease of understanding, dividing 15 layers by IPv6 below, is 1:2 from the mapping relations of the 1st layer to the 15th layer
16: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
16for example is described, but the present invention is not as limit.
A () the 1st layer is global IPv 6 address space, that is the 1st layer is global IPv 6 address realm, in order to comprise all data, consider the possibility of the network address, 1st layer of mapping block covers whole IPv6 scopes, mapping block address realm is:: to the root of FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF as partition tree, wherein subregion scope is as following table:
Each subregion is logical construction, and except the leaf node of partition tree is in order to store IPv6 address, other layer only it may be noted that the size of subregion.
B () the 2nd layer of blockette is 2
16, as the ground floor tree branch of partition tree, have 2 at this layer
16individual subregion, has 65536 subregions, and each partition size is 2
(128-16), wherein subregion scope is as following table:
C () the 3rd layer, under the 2nd layer, has 2 under each 2nd layer of branch
8each subregion, each partition size 2
(128-16-8); 4th under the 3rd layer, has 2 under each 3rd layer of branch
8each subregion, each partition size 2
(128-16-8-8), by that analogy;
D (), at the 15th layer, as the leaf node of partition tree, each partition size is 2
16.
D () be construction complete partition tree thus, the subregion height of tree 15 layers, and wherein the 1st layer is tree root, and the 2nd layer is branch to the 14th layer, and the 15th layer is leaf node, according to subregion scope, is stored IPv6 address on ownership leaf node.
2) according to the IPv6 partition tree constructed above, parallel calculating method determination partition tree leaf node (specific algorithm describes after the present invention) is adopted for given IPv6 address, IPv6 address is stored in given leaf node.
3) leaf node (the 15th layer) discrete threshold values D is set
s, in order to prevent the subregion scope of the polymerization process of leaf node to each branch from having an impact, participate in below polymerization leaf node demand fulfillment two conditions: under the leaf node 1) participating in being polymerized belongs to the 14th layer of same branch; 2) leaf node dispersion D under same branch is calculated.Polymerization is as follows:
A () calculates leaf node dispersion D
i=[N
i]/2
16, wherein D
i∈ D, D=[D
0..., D
n], n=2
(128-16), [N
i] be leaf node IPv6 number of addresses, add up the value that each subregion dispersion is non-vanishing.
B () is to meeting D
i>D
sor D
i+1>D
s, ([N
i]+[N
i-1]) <2
16, merge two adjacent subregion D
iand D
i+1be a subregion D
i.
4) repeat step (3), until leaf node does not meet polymerizing condition, polymerization terminates.
The present invention stores IPv6 subregion, by building partition tree, carries out subregion, be polymerized according to dispersion, ensure the efficiency of subregion, make each leaf node store enough IPv6 number of addresses, prevent a leaf node and only store several or minute quantity IPv6 address situation.
To the storage of magnanimity partition data with search, carry out parallel computation according to partition tree, the leaf node at the place, IPv6 address that quick position is given, its method is as accompanying drawing, and wherein step is as follows:
1) parallel computation:
A (), according to IPv6 address feature, splits 128 according to 16,8,8,8,8,8,8,8,8,8,8,8,8,16.Specifically, be exactly the 1-16 position in distinguishing 128,17-24 position, 24-32 position, 3340,41-48 position, 49-56 position, 57-64 position, 65-72 position, 72-80 is, 81-88 position, 89-96 position, 97-104 position, 105-112 position, 112-128 position.
B the IPv6 address of () computed segmentation, as the 2nd layer 2409, belongs to 9225 subregions (the 2nd layer 16, hexadecimal 2409 are converted to the decimal system obtains 9225,2409(the hexadecimal)=9225(decimal system)); 3rd layer of 80,128 subregion; 4th layer of AF, 175 subregions; The like; 14th layer of AA, 170 subregions.
2) quick position is searched:
The each layer position of IPv6 address attribution, location.Because IPv6 address bit value from left to right determines from root node successively to the path that lower floor extends, and each path of partition tree just represents the leaf node address of depositing IPv6 address.Find from the root node set to the storing information of leaf node according to IPv6 address, finally find this IPv6 address record in leaf node, i.e. IPv6 address in leaf node.In practice, leaf node IPv6 can enclose other attributes, different application in address, and additional attribute is different.Step is as follows:
A each layer subregion scope leaves in an array or many hash linked list data structure by ().
B each layer point zones values that () obtains according to parallel computation, from top to down is searched by level.
C (), when path reaches leaf node, completes positioning searching.
Good effect of the present invention is as follows;
1. scoping rules of the present invention is according to IPv6 address assignment rule, according to the actual conditions that IPV6 distributes, adopting multilayered structure to concentrate operator and regional IPv6 by dividing, taking partition tree mode data to be evenly distributed in as far as possible each different subregion.
2. IP is divided into multi-layer by the present invention, can the IPv4 address of compatible 24.
3. the present invention is to the leaf node IPv6 address of partition tree, is polymerized, about subtracts the subregion of sparse data according to dispersion, ensures that each subregion comprises valid data as much as possible, reduces total subregion number, decreases the time of building table, thus improves subregion efficiency.
4. the partition tree set up according to subregion scope of the present invention, parallel computation, according to partition tree storage and search, quick position.
Accompanying drawing explanation
Fig. 1 is IPv6 partition tree structure chart;
Fig. 2 is parallel computation schematic diagram;
Fig. 3 searches schematic diagram based on the quick position of partition tree.
Embodiment
In order to make those skilled in the art person better understand the present invention, the present invention is described in further detail to provide specific embodiment below.
IP number of levels illustrates the IP number comprised in carrying data partition, embody the degree of refinement of subregion, the subregion scope of each layer is larger, represents that the IP number that this subregion comprises is more, each subregion can logging data amount larger, but total total score section quantity reduces relatively; Subregion scope is less, represents that the IP number that each subregion comprises is fewer, and data are just few, but the just corresponding increase of total sectional quantity.IPv6 address attribution address block can divide IPv6 address according to layered approach, thus can determine certain layer of partition address scope, thus realizes the efficient lookup to IPv6 address.
In the present invention, global IPv 6 to be distributed and the scope of application is at different levels successively divides, the several distribution principle according to IPv6 of partition level (at present, IPv6 address division largest block is/20), IPv6 address covering the whole world.For convenience of explanation, below to be divided into 15 layers to be described IPv6 address, each layer mapping relations are 1:16:8:8:8:8:8:8:8:8:8:8:8:8:16, namely from the mapping relations of the 1st layer to the 15th layer be 1:2
16: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
16.The 15th layer of leaf node being defined as IPv6, the IPv6 address realm of storage is determined by mapping relations.Partition tree structure of the present invention as shown in Figure 1.
As global IPv 6 address realm be from:: be 1 grade to FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF, at ground floor; 2 grades of set (IPv6/16) are the subsets in global IPv 6 storehouse, and at the second layer, each 2nd layer of set is the 1st grade 1/216; 3 grades of set are subsets of the 2nd grade of set, and be positioned at third layer, each 3 layers of set are the 2nd layer 1/28; Each block of the 2nd layer, corresponding 28 the 3rd layer of blocks, namely, for a 2nd layer of block scope, with the range systems of the 3rd layer of block of 28 under it.According to above-mentioned division parameter the like.The IPv6 partition tree structure finally obtained as shown in Figure 1.Except the leaf node at partition tree stores except IPv6 address, other the 1st layer to 14 layers is all the scope of the subregion deposited.
(end in July, 2012, the IPv6 address block that China Mobile obtains has two: be 2409:8000: respectively :/20 and 2001:e80: :/32) for IPv6 address block for China Mobile 2409:8000: :/20.
As can be known from the above table, first search for the blockette of the 2nd layer, find 2409:: the subregion at place is the 9225th subregion; Then the 3rd layer of 2409:8000: is searched at this subregion:, belong to the 128th subregion of the 3rd layer; The 4th layer is searched again in the 128th subregion of the 3rd layer, the like; Find the subregion at the 14th layer of place, finally navigate to leaf node, look for corresponding IPv6 address.
Each subregion scope divides two effects: effect is the address assignment principle according to IPv6, and make Ipv6 to follow distribution principle, all ownership China Mobile IPv6 addresses are divided into same branch, do not occur across branch's situation; Another effect is when needing to search existing IPv6 address, can parallel computation IPv6 address block, and quick position stores the leaf node of this IPv6 address.Change as divided scope, then parallel computation positioning searching algorithm respective change.
In order to prevent the dispersion of IPv6 address, form the situation of leaf node fragment, after IPv6 address has stored, carry out leaf node and combine by arranging Ds and to prevent in certain IP scope IP quantity much smaller than prescribed condition, if adjacent leaf node is less than defined threshold Ds, and after polymerization, IP number of addresses is no more than leaf node capacity, is polymerized.Arranging of threshold value Ds need consider two factors: one is that leaf node can not be too discrete, and two is in polymerization process, and upper strata can not be caused to occur adjustment, and threshold value Ds is traditionally arranged to be 50%.Such as, 5 the IP sections existed in same branch are supposed: { [IP
1, IP
2], [IP
3, IP
4], [IP
5, IP
6], [IP
7, IP
8], [IP
9, IP
10], when the dispersion D of above 5 IP sections is for the threshold value Ds set, adjacent segment is aggregated into a sectional, by [IP in this example
1, IP
2] and [IP
3, IP
4] be polymerized, form 4 IP section { [IP
1, IP
4], [IP
5, IP
6], [IP
7, IP
8], [IP
9, IP
10].But the IP quantity of this polymeric segment can not exceed leaf node quantity, if exceeded, be not just polymerized.The present invention is only set to 50% with threshold value Ds and is illustrated, and can set according to the experience of real data situation and developer when concrete setting, the present invention is not as limit.
Experiment proves, adopts partition method of the present invention, and at certain District Universities IPv6 try net of practical application, finally this table the leaf node of logging data can reach 2195, and result aggregator leaf node reduces to 1863.It is 2 minutes for 100,000 IPv6 address location times of searching.
Although disclose specific embodiments of the invention and accompanying drawing for the purpose of illustration, its object is to help understand content of the present invention and implement according to this, but it will be appreciated by those skilled in the art that: without departing from the spirit and scope of the invention and the appended claims, various replacement, change and amendment are all possible.The present invention should not be limited to the content disclosed in this specification most preferred embodiment and accompanying drawing, and the scope that the scope of protection of present invention defines with claims is as the criterion.
Claims (8)
1. an IPv6 data partition method, is characterized in that, adopt the mode of partition tree to carry out Multilayer partition storage to IPv6 address, step comprises:
1) tectonic reverse tree, according to IPv6 address assignment and actual service condition, IPv6 address is divided into n layer, the mapping relations from the 1st layer to n-th layer are 1:2
c1: 2
c2: ...: 2
cn-1, wherein, C1, C2 ..., Cn-1 is the index of 2, C1+C2+ ... + Cn-1=128,2
cn-1for n-th layer maps, each block of i-th layer, corresponding 2
cithe range systems of individual the i-th+1 layer block, i=2,3 ..., n-1; According to mapping relations, subregion is carried out to IPv6 address: the 1st layer is tree root, and mapping block covers whole IPv6 scopes; 2nd layer is branch to Cn-1 layer, and i-th layer of each partition size is 2
(128-C1-...-Ci-1), n-th layer sectional is leaf node, for storing IPv6 address;
2) according to the partition tree of structure, partition tree leaf node is determined for given IPv6 address, IPv6 address is stored in given leaf node;
3) set the discrete threshold values Ds of leaf node, calculate ownership with the leaf node dispersion D in layer branch, if dispersion D is greater than threshold value Ds, adjacent sectors section is polymerized;
4) step 3 is repeated), until leaf node does not meet polymerizing condition, polymerization terminates, and completes the storage of IPv6 address.
2. the method for claim 1, is characterized in that, subregion two numeral partition size of every layer, and one is subregion initial value, and one is subregion end value.
3. the method for claim 1, is characterized in that, n=15, is 1:2 from the mapping relations of the 1st layer to the 15th layer
16: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
8: 2
16.
4. method as claimed in claim 3, is characterized in that, adopt the method determination leaf node of parallel computation, step is:
1) according to 16,8,8,8,8,8,8,8,8,8,8,8,8,16 segmentations 128;
2) the IPv6 address of computed segmentation, determines the layer belonging to this address and subregion.
5. the method for claim 1, is characterized in that, step 3) in polymerization be:
1) leaf node dispersion D is calculated
i=[N
i]/2
16, add up the value that each subregion dispersion is non-vanishing; Wherein D
i∈ D, D=[D
0..., D
n], n=2
(128-16), [N
i] be leaf node IPv6 number of addresses;
2) to meeting D
i>D
sor D
i+1>D
ssubregion, ([N
i]+[N
i-1]) <2
16, merge two adjacent subregion D
iand D
i+1be a subregion D
i.
6. the method for claim 1, is characterized in that, described discrete threshold values Ds is set to 50%.
7. the method for claim 1, is characterized in that, step 3) described sectional IP quantity is when exceeding leaf node quantity, is not polymerized.
8. carry out an IPv6 data search method according to IPv6 data partition method according to claim 1, it is characterized in that, carry out the positioning searching of leaf node according to given IPv6 address, the step of described positioning searching is:
1) each layer subregion scope is left in an array or many hash linked list data structure;
2) divide zones values according to parallel computation each layer out, from top to down is searched by level;
3) when path reaches leaf node, positioning searching is completed.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201210353161.XA CN102868779B (en) | 2012-09-20 | 2012-09-20 | A kind of IPv6 data partition and fast searching method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201210353161.XA CN102868779B (en) | 2012-09-20 | 2012-09-20 | A kind of IPv6 data partition and fast searching method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN102868779A CN102868779A (en) | 2013-01-09 |
| CN102868779B true CN102868779B (en) | 2016-01-20 |
Family
ID=47447364
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201210353161.XA Active CN102868779B (en) | 2012-09-20 | 2012-09-20 | A kind of IPv6 data partition and fast searching method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN102868779B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115460146B (en) * | 2022-08-19 | 2024-04-23 | 北京连星科技有限公司 | IPv6 address based visual management method, system and storage medium |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101350771A (en) * | 2008-07-07 | 2009-01-21 | 中国人民解放军国防科学技术大学 | Method and system for storing elements of tri-state content addressable memory without ordering |
| CN101577662A (en) * | 2008-05-05 | 2009-11-11 | 华为技术有限公司 | Method and device for matching longest prefix based on tree form data structure |
| CN102045412A (en) * | 2010-12-28 | 2011-05-04 | 赛尔网络有限公司 | Method and equipment for carrying out compressed storage on internet protocol version (IPv)6 address prefix |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7743214B2 (en) * | 2005-08-16 | 2010-06-22 | Mark Adams | Generating storage system commands |
-
2012
- 2012-09-20 CN CN201210353161.XA patent/CN102868779B/en active Active
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101577662A (en) * | 2008-05-05 | 2009-11-11 | 华为技术有限公司 | Method and device for matching longest prefix based on tree form data structure |
| CN101350771A (en) * | 2008-07-07 | 2009-01-21 | 中国人民解放军国防科学技术大学 | Method and system for storing elements of tri-state content addressable memory without ordering |
| CN102045412A (en) * | 2010-12-28 | 2011-05-04 | 赛尔网络有限公司 | Method and equipment for carrying out compressed storage on internet protocol version (IPv)6 address prefix |
Also Published As
| Publication number | Publication date |
|---|---|
| CN102868779A (en) | 2013-01-09 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN104199986B (en) | Vector data space index method based on hbase and geohash | |
| CN109583799B (en) | Region division method and device and electronic equipment | |
| CN110519090B (en) | Method and system for allocating accelerator cards of FPGA cloud platform and related components | |
| CN111756828B (en) | Data storage method, device and equipment | |
| CN105117171A (en) | Energy SCADA massive data distributed processing system and method thereof | |
| CN110287197A (en) | A kind of date storage method, moving method and device | |
| CN106873919A (en) | A kind of date storage method and device based on cloud storage system | |
| CN102868779B (en) | A kind of IPv6 data partition and fast searching method | |
| CN106897409A (en) | Data point library storage method and device | |
| CN103858125A (en) | Repeating data processing methods, devices, storage controller and storage node | |
| CN105227618A (en) | A kind of communication site's position information processing method and system | |
| CN106100964A (en) | The method and apparatus that a kind of virtual network maps | |
| CN108647771A (en) | The layout method of research-on-research flow data under a kind of mixing cloud environment | |
| CN107798018A (en) | A kind of method to set up and device of point of interest display information | |
| CN112561700B (en) | Verification method of transaction data in blockchain and blockchain system | |
| CN104239965A (en) | Large-scale road network double-layer routing method based on overlap community partitioning | |
| CN102378407B (en) | Object name resolution system and method in internet of things | |
| CN108920105A (en) | Diagram data distributed storage method and device based on community structure | |
| CN105302838A (en) | Classification method as well as search method and device | |
| CN103036796B (en) | Route information update method and device | |
| CN102110139A (en) | Analytic algorithm for geographic grid in telecommunication field | |
| CN109684588B (en) | Asset management system and method | |
| CN107656980A (en) | Applied to the method and distributed data base system in distributed data base system | |
| CN104331484B (en) | Node inquiring method and device based on maximizing influence | |
| Tsiftsis et al. | Identifying areas of high importance for orchid conservation in east Macedonia (NE Greece) |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant |