CN100531102C - Route table adjustment method, route query method and device and route table storage device - Google Patents

Abstract

The present invention relates to a routing table adjustment method, a routing query method and device, and a routing table storage device. The routing table adjustment method includes: receiving a routing prefix; The capacity of the subtable establishes the augmented Bloom filter of the routing subtable and the augmenting routing subtable. The routing query method includes: obtaining an IP address to be queried; according to the IP address to be queried, by querying in a Bloom filter and an accretive Bloom filter, obtaining the length of the routing prefix corresponding to the IP address to be queried; Length, obtain the routing path of the IP address to be queried in the corresponding routing subtable. The routing table adjustment device and the routing query device respectively include functional modules for executing the above method, and the routing table storage device includes a module for storing routing sub-tables and Bloom filters. The technical scheme of the invention can realize the quick adjustment of the routing table with a small cost.

Description

Routing table adjustment method, routing query method and device, and routing table storage device

technical field

The invention belongs to the technical field of communication, and in particular relates to a routing table adjustment method, a routing query method and device, and a routing table storage device in the communication field.

Background technique

Among the existing communication network technologies, the routing technology is undoubtedly one of the most concerned technologies. Many developments in the field of communication require a corresponding increase in the requirements for routing technology. For example, in recent years, with the trend of corporate globalization, many companies have developed more branch structures in different parts of the world, so many companies tend to use the Internet to replace their private data networks. The logical network formed by the information is called a virtual private network (Virtual Private Network, hereinafter referred to as VPN). At present, the application of VPN is more and more extensive, and people's demand for safe and convenient data communication means is also increasing day by day. With the wide application of VPN, in the past, only the routing and forwarding equipment at the access end needed to support VPN routing, but now, many middle and high-end routing and forwarding equipment directly connected to end users also need to support VPN routing. Therefore, the requirements for routing technology are getting higher and higher. On the other hand, the transmission rate of the transmission medium is increasing rapidly, and the number of packets processed by the routing equipment is increasing rapidly. For example, the routing and forwarding equipment supporting 100G Routing and forwarding devices usually need to look up 250M routing prefixes per second, which also requires routing devices to provide stronger query capabilities, that is, stronger maximum routing prefix lookup capabilities. High-speed lookup technology is one of the challenges facing the industry.

Two key factors in high-speed lookup technology are: lookup rate and update rate. The search rate provides greater routing capacity, and the update rate provides a more stable network, that is, speeds up network convergence, which is exactly the technical problem to be solved by the present invention. Routing query technology is a common step in the process of transmitting data packets through the network. For each received IP data packet, the routing system must find the largest routing prefix of the destination address in the IP data packet in its routing table, and then follow the corresponding The corresponding routing path transmits the data packet. In order to improve factors such as query speed and query overhead of routing query operations, various routing lookup systems have been adopted, one of which is to use Bloom filter (hereinafter referred to as Bloom Filter) technology. Bloom Filter technology is a set of data set representation methods proposed by computer scientist "Burton Bloom" in 1970. This method can significantly and effectively compress the information of a data set, and is widely used in information retrieval. The Bloom Filter technology is applied in the routing technology. First, the routing table is divided into several routing subsets according to the length of the routing prefix matching value, and then a Bloom filter is established for each routing subset, that is, the Bloom Filter, and the filtering In the shared memory mode, each Bloom Filer corresponds to the start address of a memory respectively. The routing sub-table is actually a part of the original routing table, and is a logically formed routing sub-table. Figure 1A is a schematic diagram of a routing query based on Bloom filter technology, and Figure 1B is a schematic diagram of a related routing table architecture, and the basic steps are as follows:

Step a1, obtaining the IP address to be queried;

Step a2. According to the IP address to be queried, use Bloom Filter technology to query each filter, namely filter0, filter1, filter2 and filter3, etc., to obtain the length of the maximum routing prefix corresponding to the IP address to be queried. There may be many matches here. The length of the routing prefix, according to the principle of the longest match, select the length of the largest routing prefix;

Step a3, get the corresponding length byte in front of the IP address as the maximum routing prefix value, and this relative length is the maximum routing prefix length;

Step a4, perform a hash (hash) operation on the maximum routing prefix value to obtain the physical address of the corresponding routing table entry, so as to finally query the routing path, that is, query the index of the corresponding ip address in the corresponding prefix length table, in order to correctly , it is also necessary to compare the actual stored routing prefix value (key) with the query key, and use it as the query result when the verification is correct. If the verification is incorrect, return to step a2 and select a shorter routing prefix length. Then execute step a3 until the correct result is found.

In the above step a2, since there are many prefix configurations for the same route, an address is determined by hashing a value, and the corresponding route is stored at the address when configuring the routing table.

Rational storage and maintenance technology of routing data is an important prerequisite for efficient and reliable routing. When the above-mentioned Bloom filter technology is used, a vector table of a hash table occupying less memory, that is, a Bloom filter, can be established to correspond to the actual prefix entry occupying a large memory space.

However, the inventor finds that the routing table storage and maintenance technology based on Bloom filter technology has at least the following problems in the process of carrying out the research of the present invention: because it is difficult to estimate the size of each routing subset in advance, it can only be assumed in advance. Allocate a certain amount of storage space to the routing sub-table with a prefix of a certain length, but the number of routing table entries will frequently increase and decrease in the actual network. Release the old Bloom filter and the corresponding routing sub-table, and then rebuild a larger-capacity Bloom filter and the corresponding routing sub-table. Undoubtedly, this operation overhead is huge.

Contents of the invention

The embodiment of the present invention provides a routing table adjustment method and device, which overcomes the problems of complex routing table adjustment schemes and high adjustment costs in the existing Bloom filter-based routing technology, so as to increase or decrease the storage capacity of routing sub-tables When , the routing table is quickly maintained, and the routing table can be adjusted with a small operation cost.

The embodiment of the present invention also provides a routing query method and device, which is suitable for the routing table expanded by the routing table adjustment method of the present invention, so that a fast and low-cost routing table adjustment method can be used, and the routing query can be performed on smaller routes. Performing it in a sub-table can also increase the query speed accordingly.

The embodiment of the present invention further provides a routing table storage device, which is suitable for adjustment by adopting the embodiment of the routing table adjustment method of the present invention, which can adopt a routing table adjustment method that is fast and has low cost.

Some embodiments of the present invention provide a routing table adjustment method, including the following steps:

Receive route prefix matching value;

When it is detected that the storage amount of the routing sub-table corresponding to the length of the routing prefix matching value has reached the set threshold value, the routing sub-table is established according to the capacity of the routing sub-table and the length of the Bloom filter of the routing sub-table. The augmented Bloom filter of the routing sub-table, and the establishment of the augmented routing sub-table according to the capacity of the routing sub-table.

Still other embodiments of the present invention provide a routing table adjustment device, including:

A receiving module, configured to receive a routing prefix matching value;

Create a module for detecting that the storage amount of the routing sub-table corresponding to the length of the routing prefix matching value has reached the set threshold value, according to the capacity of the routing sub-table and the Bloom filter of the routing sub-table The length of the routing sub-table is used to establish the augmented Bloom filter of the routing sub-table, and the augmented routing sub-table is established according to the capacity of the routing sub-table.

It can be seen from the above technical solutions that in the embodiment of the routing table adjustment method and device of the present invention, when the storage capacity of the routing sub-table increases to the set value, the corresponding original Bloom filter and routing sub-table are used to establish the accretion Bloom filter and the accretion The technical means of the routing sub-table overcomes the technical problem in the prior art that the Bloom filter and the routing sub-table need to be rebuilt when the routing table is expanded, and the expansion cost is high. Therefore, the expansion cost of the routing table adjustment method and the adjustment device of the present invention is small, and the expansion operation is quick.

Still other embodiments of the present invention provide a routing query method, including:

Obtain the IP address to be queried;

According to the IP address to be queried, the routing prefix length corresponding to the IP address to be queried is obtained by querying in the Bloom filter and its accretive Bloom filter;

According to the queried length of the routing prefix, the routing path of the IP address to be queried is obtained in the corresponding routing sub-table.

Other embodiments of the present invention provide a routing query device, including:

Obtaining a module for obtaining an IP address to be queried;

The first query module is used to obtain the length of the maximum routing prefix corresponding to the IP address to be queried by querying in the Bloom filter and the proliferated Bloom filter according to the IP address to be queried;

The second query module is configured to obtain the routing path of the IP address to be queried in the corresponding routing sub-table according to the maximum routing prefix length.

It can be seen from the above technical solution that the routing query method and device of the present invention can query the proliferating Bloom filter at the same time when querying the original Bloom filter, which is suitable for the routing table expanded by the routing table adjustment method of the present invention, thus A fast and low-cost routing table adjustment method can be used, and the routing query is performed in a smaller routing sub-table, which can also increase the query speed accordingly.

Still other embodiments of the present invention provide a routing table storage device, including:

The routing table block is used to store the routing prefix matching value, including more than two routing sub-table units for storing the routing prefix matching value of the set length, and more than one routing sub-table unit for storing the same length as the routing prefix matching value in the routing sub-table unit The augmented routing subtable unit of the routing prefix matching value;

The segment address register is used to store the starting address of the routing subtable unit;

The third module includes more than two Bloom filters, which are connected to the routing sub-table unit in one-to-one correspondence, and are used to store the length information of the routing prefix matching value in the routing sub-table unit, and more than one accretive Bloom filter, and the accretion The routing sub-table units are connected in one-to-one correspondence, and are used to store the length information of the routing prefix matching value in the augmented routing sub-table unit.

It can be seen from the above technical solution that the routing table storage device includes a routing subtable unit and an augmented routing subtable unit for storing routing prefix matching values of the same length. The table unit and the proliferating routing sub-table unit correspond to each other, and can be adapted to adopt the technical scheme of the routing table adjustment method embodiment of the present invention. When the content of the routing sub-table unit expands, the routing sub-table unit and the Bloom filter do not need to be regenerated, thus The adjustment method is fast and the cost is small.

The present invention will be described in further detail below through specific embodiments and in conjunction with the accompanying drawings.

Description of drawings

Fig. 1A is the process flow of the route query method in the prior art;

FIG. 1B is a schematic flow diagram of a route query method in the prior art;

2 is a schematic structural diagram of the routing table in Embodiment 1 of the routing table adjustment method of the present invention;

FIG. 3 is a flow chart of Embodiment 1 of the routing table adjustment method of the present invention;

FIG. 4 is a flowchart of a second embodiment of the routing table adjustment method of the present invention;

FIG. 5 is a schematic structural diagram of Embodiment 1 of the routing table adjustment device of the present invention;

6 is a schematic structural diagram of Embodiment 2 of the routing table adjustment device of the present invention;

7 is a flowchart of a specific embodiment of the route query method of the present invention;

FIG. 8 is a schematic structural diagram of a specific embodiment of the routing query device of the present invention;

Fig. 9 is a schematic structural diagram of a specific embodiment of the routing table storage device of the present invention

Detailed ways

Embodiment 1 of Routing Table Adjustment Method

FIG. 3 is a flow chart of Embodiment 1 of the routing table adjustment method of the present invention. The routing table adjustment method of this embodiment is a method for adjusting the routing table in the routing technology based on Bloom filter technology. Based on the Bloom filter routing technology, it is divided into multiple disjoint sets of routing prefix matching values according to the length of the routing prefix matching value, and a space is allocated independently in the routing table for each set of routing prefix matching values. That is to say, the routing table is divided into multiple independent routing sub-tables, and each routing sub-table corresponds to a Bloom filter one by one. The routing prefix matching values in the routing sub-table are hashed, and the length information is written into Bloom In the filter, in order to query the length of the routing prefix to be found in a Bloom filter, and then further query the matching value of the routing prefix in the corresponding routing subtable, this is based on the routing technology of the Bloom filter Fundamental. The essence of the Bloom filter is a vector group, which is stored in a large array. When the Bloom filter is established, the matching value of the routing prefix will be hashed, and the address of the hash will be used to convert the corresponding bits in the Bloom filter. If the bit is set to 1, when several hash functions are used, a vector can be obtained by performing an operation on each routing prefix matching value, that is, several bits of the Bloom filter are all 1. The array of the Bloom filter needs to be large enough, otherwise there will be multiple router prefix matching value hash operations and the same bit will be 1, then when the ip routing prefix query is performed, a misjudgment will occur. Therefore, the length of the Bloom filter, that is, the number of bits of the Bloom filter, needs to be large enough. The length of the Bloom filter should correspond to the capacity of the routing subtable to minimize the possibility of misjudgment. The adjustment method for its routing table in this embodiment includes:

Step 101, receiving a routing prefix matching value;

Step 102, when it is detected that the storage capacity of the routing sub-table corresponding to the length of the routing prefix matching value has reached the set threshold value, an accretive Bloom filter of the routing sub-table is established according to the capacity of the routing sub-table And the augmented routing sub-table, the routing sub-table is marked as the original routing sub-table, and the Bloom filter of the routing sub-table is recorded as the original Bloom filter;

In the above-mentioned step 102, when the storage capacity of the original routing sub-table reaches the set threshold value, it may be that the storage space of the routing sub-table is full, or the maximum storage limit set for the routing sub-table storage capacity in order to ensure the query speed, It usually occurs when a routing subtable expands on a large scale; the adjusted routing table structure is shown in Figure 2, where the original routing subtable t0~t3 and the original Bloom filters bf0~bf3 can pass through the segment address register Seg ptr0 ~Seg ptr3 correspond one-to-one, segment address registers Seg ptr0~Segptr3 are respectively used to store the first address of each original routing subtable t0~t3 in memory. As shown in Figure 2, when the storage capacity of the original routing sub-table t2 reaches the set threshold value, an accretive Bloom filter bf2' is established according to the capacity of the original routing sub-table t2, and an accretive routing sub-table t2' is established , and, when using the segment address register to store the first address of the routing subtable, it is also necessary to save the first address of the augmented routing subtable bf2' in the segment address register Seg ptr4.

In the above step 102, according to the capacity of the original routing sub-table, the step of establishing the accretion Bloom filter of the original routing sub-table can be specifically: according to the capacity of the original routing sub-table, establishing the original Bloom filter whose length is the same as that of the original routing sub-table The filter lengths are equal, that is, the accretionary Bloom filter with the same number of bits. The length of the original Bloom filter corresponds to the capacity of the original routing subtable, which is generally proportional to the capacity of the routing subtable. In this technical solution, establishing an accretionary Bloom filter whose length is equal to that of the original Bloom filter can also facilitate the subsequent operation of merging the original Bloom filter and the accretionary Bloom filter. In step 102, the step of establishing the augmented routing sub-table according to the capacity of the original routing sub-table can be specifically: according to the capacity of the original routing sub-table, an augmented routing sub-table with a capacity equal to the capacity of the original routing sub-table is established, that is, in memory Allocate a storage space with the same size as the original routing sub-table as the augmented routing sub-table.

In step 102, after the augmented routing sub-table is established, the starting address of the augmented routing sub-table can be saved so as to find the location of the routing sub-table. In the routing table storage architecture targeted by this embodiment, as shown in Figure 2, when the memory is shared, the starting address of the routing sub-table can be further stored in the segment address register. When the random access memory (RAM) is embedded, the routing sub-table may correspond to the routing sub-table number, and the location of the routing sub-table can be found more conveniently by using the segment address register and the routing sub-table number. Therefore, the storage of the start address of the augmented routing sub-table may be specifically stored in a segment address register.

After the augmented routing sub-table is established, the following steps can be further performed, as shown in Figure 3:

Step 103, saving the received routing prefix matching value.

In the above step 103, the received route prefix matching value is stored in the routing sub-table, and the length information of the routing prefix matching value is written into the Bloom filter. In this embodiment, it is preferable to save the newly received routing prefix matching value into the newly-created augmented routing sub-table, and write its length information into the augmented Bloom filter to enrich the augmented routing sub-table Gradually make the storage capacity of the original routing sub-table and the augmented routing sub-table tend to be equal.

The technical solution of this embodiment has the advantage of realizing the method of expanding the dynamic routing table. Compared with the prior art, the expansion cost of the routing table is small, and the adjustment method is convenient.

Embodiment 2 of Routing Table Adjustment Method

As shown in Figure 4, it is the flow chart of the specific embodiment 2 of the routing table adjustment method of the present invention. This embodiment is based on the technical solution of the above-mentioned embodiment 1. In the above-mentioned step 102, a proliferating Bloom filter and a proliferating router are established. After the table, the shrinking step of the routing table can be further performed, which specifically includes the following steps:

Step 301, when it is detected that the storage capacity of the routing sub-table and/or the augmented routing sub-table of the routing sub-table is reduced to a set threshold value, step 302 is executed;

Step 302, merging the Bloom filter of the routing sub-table and the augmented Bloom filter, and merging the routing sub-table and the augmented routing sub-table.

In the above step 301, the setting of the lower limit of the storage capacity of the routing sub-table or the augmented routing sub-table can be determined according to specific circumstances, and also needs to be determined according to the way of merging the routing sub-tables. For example, it is necessary to ensure that the space of an original routing sub-table can accommodate the routing prefix matching values stored in the original routing sub-table and the augmented routing sub-table.

In the above step 302, the step of merging the Bloom filter of the routing subtable and the accretionary Bloom filter may specifically be: perform "OR" on the routing subtable Bloom filter and the bit vector array of the accretionary Bloom filter operation, use the result as the original Bloom filter, and then release it, that is, delete the augmented Bloom filter; the steps of merging the routing subtable and the augmented routing subtable can be as follows: match the route prefixes in the augmented routing subtable The value is added to the subsequent storage space of the routing prefix matching value of the original routing subtable. Further, after merging the routing sub-table and the augmented routing sub-table, it may further include: deleting the start address of the augmented routing sub-table from the segment address register.

The advantage of the technical solution of this embodiment is that: when the number of routing prefix matching values in the augmented routing sub-table is reduced below the set threshold value, the shrinking operation can be further performed to maintain the routing table, so as to save storage space and improve routing performance. Query speed.

Embodiment 1 of routing table adjustment device

As shown in Figure 5, it is a schematic structural diagram of a specific embodiment 1 of the routing table adjustment device of the present invention, and the device includes:

The receiving module 1 is used to receive the routing prefix matching value; the creating module 2 is used to detect that when the storage capacity of the routing sub-table corresponding to the length of the routing prefix matching value has reached the set threshold value, according to the routing sub-table The capacity of the table establishes the augmented Bloom filter of the routing sub-table and the augmenting routing sub-table.

The routing table adjustment device of this embodiment can adopt the technical solution of the first embodiment of the routing table adjustment method of the present invention to realize the method of dynamic routing table expansion. Compared with the prior art, the expansion cost of the routing table is small and the adjustment is convenient.

Embodiment 2 of routing table adjustment device

As shown in Figure 6, it is a schematic structural diagram of a second embodiment of the routing table adjustment device of the present invention. This embodiment further includes:

The merging module 4 is used for merging the Bloom filter and the proliferation Bloom filter of the routing subtable when detecting that the storage capacity of the routing subtable and/or the accretion routing subtable of the routing subtable is reduced to a set threshold value, And merge the routing sub-table and the augmented routing sub-table.

The routing table adjustment device of this embodiment can adopt the technical solution of the second embodiment of the routing table adjustment method of the present invention, and when the number of routing prefix matching values in the augmented routing sub-table is reduced below the set threshold value, the shrinking operation can be further performed , to maintain the routing table to save storage space and improve routing query speed.

Example of routing query method

As shown in Figure 7, it is a flow chart of a specific embodiment of the routing query method of the present invention. The routing query method of the present embodiment performs routing query according to the routing table targeted in the routing table adjustment method of the present invention. The structure of the routing table is shown in Figure 2 shown, including the following steps:

Step 201, obtaining the IP address to be queried;

Step 202, according to the IP address to be queried, the length of the routing prefix corresponding to the IP address to be queried is obtained by querying in the Bloom filter and the accretive Bloom filter;

Step 203, according to the routing prefix length, obtain the routing path of the IP address to be queried in the corresponding routing sub-table.

During the execution of the above steps 202 and 203, according to the longest routing prefix matching principle, usually select the longest routing prefix length from the multiple routing prefix lengths corresponding to the obtained IP address, and then query Shorter routing prefix length, repeat steps 202 and 203 until the correct result is found

In the above step 203, according to the length of the routing prefix, obtaining the routing path of the IP address to be queried in the corresponding routing sub-table can specifically be achieved by performing the following steps:

Step 2031, according to the length of the obtained routing prefix, query the starting address of the corresponding routing subtable in the segment address register;

Step 2032, obtain the in-table address of the corresponding routing sub-table through hash operation;

Step 2033, obtain the corresponding physical address in the corresponding routing table according to the obtained initial address of the routing sub-table and the address in the table;

Step 2034, obtain the routing path of the IP address to be queried according to the physical address in the routing table.

The technical solution of this embodiment can effectively perform routing query based on the routing table adjusted by the routing table adjustment method of the present invention, so a fast and low-cost routing table adjustment method can be used, and the routing query is performed in a smaller routing sub-table. It can also increase the query speed accordingly.

Embodiment of routing query device

As shown in Figure 8, it is a schematic structural diagram of a specific embodiment of the routing query device of the present invention, and the device includes:

The obtaining module 11 is used to obtain the IP address to be queried; the first query module 12 is used to obtain the IP address corresponding to the queried IP address by querying in the Bloom filter and the accretion Bloom filter according to the IP address to be queried. The length of the routing prefix; the second query module 13 is configured to obtain the routing path of the IP address to be queried in the corresponding routing sub-table according to the length of the routing prefix.

The routing query device of this embodiment can adopt the technical solution of any embodiment of the routing query method of the present invention, so a fast and low-cost routing table adjustment method can be used, and the routing query is carried out in a smaller routing sub-table, or through Other storage media are used to realize simultaneous query in the routing sub-table and the augmented routing sub-table, so the query speed can be correspondingly improved.

Embodiment of routing table storage device

FIG. 9 is a schematic structural diagram of a specific embodiment of the routing table storage device of the present invention, and the device includes:

The routing table module 100, namely the first module, is used to store the matching value of the routing prefix, including more than two routing sub-table units 1001 for storing the matching value of the routing prefix of the set length, namely the first unit, and more than one for storing The augmentation routing subtable unit 1002 of the routing prefix matching value equal to the routing prefix matching value length in the routing subtable unit 1001, i.e. the second unit; the segment address register 200, i.e. the second module, is used to store the routing subtable unit 1001 and The initial address of the augmented routing subtable unit 1002; the filter module 300 includes more than two Bloom filters 3001, i.e. the third unit, which is connected to the routing subtable unit 1001 in one-to-one correspondence, and is used to store the routing subtable unit 1001 The length information of the routing prefix matching value in the middle, and more than one augmentation Bloom filter 3002, that is, the fourth unit, is connected to the augmentation routing subtable unit 1002 in one-to-one correspondence, and is used to store the routing prefix matching value in the augmentation routing subtable unit 1002 length information.

This embodiment can be adapted to the embodiments of the routing table adjustment method and the routing query method of the present invention, and when the content is expanded, it can be adjusted quickly and with low cost.

Those of ordinary skill in the art can understand that all or part of the steps for realizing the above-mentioned method embodiments can be completed by hardware related to program instructions, and the aforementioned program can be stored in a computer-readable storage medium. When the program is executed, the It includes the steps of the above method embodiments; and the aforementioned storage medium includes: ROM, RAM, magnetic disk or optical disk and other various media that can store program codes.

Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present invention, rather than to limit them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: it can still be Modifications are made to the technical solutions described in the foregoing embodiments, or equivalent replacements are made to some of the technical features; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the spirit and scope of the technical solutions of the various embodiments of the present invention.

Claims (15)

1, a kind of route table adjustment method comprises:

Receive the route prefix matching value;

When the memory space that monitors the route sublist corresponding with the length of described route prefix matching value has reached the threshold value of setting, set up the hyperplasia Bloom filter of described route sublist according to the length of the Bloom filter of the capacity of described route sublist and described route sublist, and set up hyperplasia route sublist according to the capacity of described route sublist.

2, route table adjustment method according to claim 1, it is characterized in that, the hyperplasia Bloom filter of setting up described route sublist according to the length of the Bloom filter of the capacity of described route sublist and described route sublist is specially: according to the capacity of described route sublist, set up the hyperplasia Bloom filter of equal in length of the Bloom filter of length and described route sublist.

3, route table adjustment method according to claim 1, it is characterized in that, setting up hyperplasia route sublist according to the capacity of described route sublist is specially: according to the capacity of described route sublist, set up the hyperplasia route sublist that capacity equates with the capacity of described route sublist.

4, route table adjustment method according to claim 1 is characterized in that, after setting up described hyperplasia route sublist, also comprises: the initial address of described hyperplasia route sublist is kept in the segment address register.

5, route table adjustment method according to claim 1, it is characterized in that, after setting up described hyperplasia route sublist, also comprise: the described route prefix matching value that receives is kept in the described hyperplasia route sublist, and the length information of the described route prefix matching value that receives is write in the described hyperplasia Bloom filter.

6, route table adjustment method according to claim 1 is characterized in that, after the hyperplasia Bloom filter of setting up described route sublist and hyperplasia route sublist, this method also comprises:

The memory space that monitors the hyperplasia route sublist of described route sublist and/or described route sublist reduces to when setting threshold value, merge the Bloom filter and the described hyperplasia Bloom filter of described route sublist, and merge described route sublist and described hyperplasia route sublist.

7, route table adjustment method according to claim 6, it is characterized in that, the Bloom filter and the described hyperplasia Bloom filter that merge described route sublist are specially: Bloom filter and described hyperplasia Bloom filter to described route sublist are carried out OR operation, with the Bloom filter of result, and delete described hyperplasia Bloom filter as described route sublist.

8, route table adjustment method according to claim 6, it is characterized in that, merge described route sublist and described hyperplasia route sublist is specially: the route prefix Configuration Values in the described hyperplasia route sublist is added in the follow-up memory space of the route prefix Configuration Values in the described route sublist.

9, route table adjustment method according to claim 8 is characterized in that, after merging described route sublist and described hyperplasia route sublist, also comprises: the initial address of the described hyperplasia route sublist of deletion from segment address register.

10, a kind of routing table adjusting device is characterized in that, comprising:

Receiver module is used to receive the route prefix matching value;

Creation module, when the memory space that is used to monitor the route sublist corresponding with the length of described route prefix matching value has reached the threshold value of setting, set up the hyperplasia Bloom filter of described route sublist according to the length of the Bloom filter of the capacity of described route sublist and described route sublist, and set up hyperplasia route sublist according to the capacity of described route sublist.

11, routing table adjusting device according to claim 10 is characterized in that, also comprises:

Merge module, the memory space that is used to monitor the hyperplasia route sublist of described route sublist and/or described route sublist reduces to when setting threshold value, merge the Bloom filter and the described hyperplasia Bloom filter of described route sublist, and merge described route sublist and described hyperplasia route sublist.

12, a kind of method for searching route according to the arbitrary described route table adjustment method of claim 1-9 is characterized in that, comprising:

Obtain IP address to be checked;

According to IP address to be checked,, obtain the route prefix length of IP to be checked address correspondence by in Bloom filter and hyperplasia Bloom filter, inquiring about;

According to the described route prefix length that inquires, in the route sublist of correspondence, obtain the routed path of IP to be checked address.

13, method for searching route according to claim 12 is characterized in that, according to route prefix length, the routed path that obtains IP to be checked address in the route sublist of correspondence is specially:

According to the route prefix length of obtaining, the initial address of the route sublist of inquiry correspondence in the segment address register of correspondence;

Obtain address in the table of corresponding route sublist by Hash operation;

Initial address and Biao Nei address according to the route sublist of obtaining obtain the corresponding physical address in routing table;

Obtain the routed path of IP to be checked address according to the physical address in the routing table.

14, a kind of routing inquiring device according to the arbitrary described route table adjustment method of claim 1-9 is characterized in that, comprising:

Acquisition module is used to obtain IP address to be checked;

First enquiry module is used for according to IP address to be checked, by inquiring about in the Bloom filter of Bloom filter and hyperplasia thereof, obtains the length of the route prefix of IP to be checked address correspondence;

Second enquiry module is used for according to route prefix length, obtains the routed path of IP to be checked address in the route sublist of correspondence.

15, a kind of route table storage device, it is characterized in that, comprise: router table means, be used to store the route prefix matching value, comprise the route sublist unit that is used to store preseting length route prefix matching value more than two, and be used for storing the hyperplasia route sublist unit with the route prefix matching value of described route sublist unit route prefix matching value equal in length more than one;

Segment address register, the initial address that is used to store described route sublist unit;

Filter module, comprise two above Bloom filters, link to each other with described route sublist unit is corresponding one by one, be used for storing the length information of described route sublist unit route prefix matching value, and above hyperplasia Bloom filter, link to each other with described hyperplasia route sublist unit is corresponding one by one, be used for storing the length information of described hyperplasia route sublist unit route prefix matching value.

Images