CN100496019C - A Method for Rapid Search and Update of IPv6 Routing Table - Google Patents

Abstract

The invention relates to the technical field of computer networks and provides a method for quickly searching and updating an IPv6 routing table. The method of fast lookup of the routing table includes using a first-level linear index table and a second-level set of hash tables organized by a binary search tree to perform a two-stage lookup; the method of fast update of the routing table includes using BMP-tree to reorganize the data structure The relationship between each prefix improves the update efficiency; in order to reduce the storage space, two binary search tree construction methods are designed; compared with the traditional multiple lookup table and the binary search method based on the length of the address prefix, the present invention is more suitable for IPv6 Network, faster search and update efficiency and other advantages.

Description

A Method for Rapid Search and Update of IPv6 Routing Table

technical field

The invention relates to the technical field of computer networks, in particular to a method for realizing fast routing table lookup and update based on IPv6 addresses.

Background technique

The routing table lookup method is the key technology in the router forwarding system, and the lookup efficiency affects the forwarding efficiency of the router to a great extent. The basic idea of routing table lookup is that, given an address keyword, it is necessary to find the longest address prefix matching the address keyword in the routing table, and perform subsequent processing according to the next-hop port number of the address prefix. Compared with the traditional search that can only complete the exact match of keywords, the difficulty and complexity of routing table search are greatly increased.

At present, there are many routing search methods for IPv4 routers. The most widely used methods include two types of search methods, namely the method based on the trie tree and the binary search method based on the length of the address prefix. However, with the further popularization of IPv6 networks, these routing table lookup methods have encountered their own limitations.

The search method based on the trie tree is like this. The trie is a tree structure that uses the value of each bit in the address prefix to construct the branches of the tree. An optimization method of the trie is a multi-branch trie tree, which uses multiple bits in the address prefix to construct each node of the tree, which can reduce the search depth, but also has a negative impact. Its main problem is focused on the choice of step width, the step width is large, the method efficiency is high, and the memory usage is large; the step width is small, the method efficiency is low, and the memory usage is small. Although people have used various compression methods to try to solve this problem, in the IPv4 network, due to the small number of address bits and the limited selection range of the step width, this problem is not particularly prominent. The 128-bit network address of IPv6 makes its The problem is highlighted, resulting in a serious decline in the search performance of this method.

In comparison, the binary search method based on the length of the address prefix is a search method with better performance and efficiency in the IPv6 network. This method is developed on the basis of the linear search method based on the hash table. Its basic idea is to classify the routing table according to different prefix lengths, and form a hash table with prefixes of the same length, so that the entire routing table will be composed of multiple hash tables. Then perform a binary search on these hash tables according to the length of the address key, and then directly locate the longest matching prefix according to the hash search method. During the implementation of this method, some details will be encountered. For example, for the prefix table 1 ^* , 00 ^* , 111 ^* , if the address key to be searched is 111, first binary search 11 ^* , in the 2-bit hash table There is only 00 ^* in , and there is no 11 ^* . At this time, a mechanism needs to be introduced to add a marker 11 ^* to the 2-bit hash table. This marker is not the actual address prefix, but only for the needs of the search process. After finding 11 ^* , continue to search behind the prefix table, and you can find 111 ^* at this time. Although the increase of IPv6 address length has little effect on this method, the update efficiency of this method is poor. Due to the large dependency between prefixes and between prefixes and markers, when a prefix encounters addition, deletion, When updating and other operations, it is necessary to change the information of multiple prefixes or markers. How to find these prefixes or markers that need to be changed is very difficult. In addition, these update operations, even through optimization, require reconstruction of the entire set of hash tables after a period of time.

Contents of the invention

The technical problem to be solved by the present invention is to propose a routing table search and update method suitable for IPv6 network routers, especially to effectively improve the routing table update efficiency while ensuring the routing table search efficiency. The method can be used for searching and updating the routing table in the router forwarding system of the IPv6 network.

The present invention is achieved like this: a kind of method based on IPv6 address realizes fast routing table lookup and update, is characterized in that:

First create three data structures:

(1) A linear index table, where each entry corresponds to zero, one or more address prefixes whose length is equal to or less than 16;

(2) Hash Table List (Hash Table List, HTL), all the prefixes in the routing table whose length is less than or equal to 16 are stored in different hash tables according to the length classification, and the collection of these hash tables constitutes the HTL;

(3) Based on the hash table list (Binary tree—Hash Table List, B-HTL) organized by the binary search tree, all the prefixes in the routing table with a length greater than 16 are stored in different hash tables according to the length classification. These hash tables Organized to form B-HTL through binary search tree;

When a data packet of the IPv6 protocol enters the router, the upper 16 bits of the destination address are taken out and used as an index value to locate the corresponding entry in the linear index table. If the flag bit of the entry is 0, the next entry in the entry is directly taken out The jump port is used as the forwarding port; otherwise, according to the information stored in the entry, use the binary search tree to search in the corresponding B-HTL;

Use the data stored in HTL to update the linear index table.

In the method for realizing fast routing table lookup and update based on IPv6 addresses, the linear index table is fixed at 64k entries, each entry is 3 bytes in length, and is divided into 3 parts, wherein the high 16bit is the first One part is used to indicate the prefix length or a pointer to B-HTL; the next bit is a flag bit, which is used to indicate the meaning of the content stored in the first part; the third part is the last 7 bits, indicating the next corresponding to the entry Jump routing port; each entry in the linear index table uniquely corresponds to a B-HTL.

When the first part of the linear index entry is used to indicate the prefix length, each bit of the 16-bit length is set to 1 or 0; when an address prefix with a length of n corresponds to a certain linear index entry, The nth bit of the first part of the entry is set to 1, otherwise it is set to 0.

When performing an update operation in the linear index table, if the prefix length L to be updated is less than or equal to 16, first set the L-th position in the first part of the entry to 1, and then judge whether there is a bit that is 1 among the bits higher than L , if it does not exist, rewrite the third part of the linear index table entry as the port number to update the prefix according to the flag bit;

When performing a deletion operation in the linear index table, if the prefix length L to be deleted is less than or equal to 16, first set the L-th position in the first part of the entry to 0, and then determine whether there is a bit of 1 among the bits higher than L , if it exists, delete the prefix in the hash table corresponding to the length of the prefix in HTL; if it does not exist, look for the bit with the highest value of 1 among those bits lower than L, and look it up in HTL according to the position of the bit For the corresponding prefix, the third part of the linear index table entry is rewritten as the port number of the found prefix.

The method for realizing fast routing table search and update based on IPv6 address, the operation of performing routing table search includes the following steps:

5A, taking out the first 16 bits of the IPv6 packet destination address as an index value, and searching the corresponding entry in the linear index table;

5B. If the flag bit of the entry is 1, execute 5D;

5C. Obtain the output port corresponding to the entry, and execute 5F;

5D. Take out the last 112 bits of the IPv6 packet destination address;

5E. Obtain the B-HTL pointer in the entry of the linear index table, and obtain the B-HTL pointer in the corresponding B-HTL

Use the last 112bit address to perform a binary search to obtain the corresponding output port;

5F, end.

Each node of the binary search tree of the B-HTL points to a hash table; each entry in the hash table includes the following parts:

(1) An IPv6 address with a length of 16 bytes;

(2) the next hop port number with a length of 7 bits;

(3) A flag bit with a length of 1 bit, which is used to indicate whether the entry corresponds to an address prefix with a length greater than 16;

(4) A marker bit with a length of 1 bit, used to indicate whether the entry corresponds to a marker;

(5) The longest matching prefix (Best Matched Prefix, BMP) with a length of 8 bits is used to indicate the length of the longest address prefix corresponding to the entry;

(6) A marker counter with a length of 16 bits, which is used to count the number of markers superimposed on the entry;

(7) expand pointer, pointing to the root node of a longest matching address prefix tree (BMP_tree);

(8) The next_level pointer points to the lower-level node in the BMP_tree;

(9) The same_level pointer points to the same-level node in the BMP_tree.

The BMP_tree is composed of entries of the hash table in the B-HTL, and the expand pointer of each entry uniquely corresponds to a BMP_tree, and each node in the BMP_tree is prefixed with the entry, and the length of the prefix in the node is determined by Set the level of the node in the BMP_tree from low to high, and the nodes with the same prefix length are in the same level of the BMP_tree; when adding, deleting or updating the B-HTL, look for those hash table entries that need to be changed through the BMP_tree.

The method for realizing fast routing table lookup and update based on IPv6 address, when adding a prefix P2 to B-HTL, perform the following steps:

8A. Find the longest address prefix node P1 of P2 in B-HTL;

8B. In the BMP-tree of P1, traverse all prefix nodes whose levels are higher than P2, and execute 8C, 8D, and 8E respectively;

8C. If the traversal is not over, execute 8D; otherwise, execute 8F;

8D. If P2 is the prefix of the node, then execute 8E, otherwise traverse to the next node and execute 8C;

8E. Take out the node from the BMP-tree of P1, move to the BMP-tree of P2, traverse to the next node, and execute 8C;

8F, add marker in B-HTL for P2;

8G. Add P2 to the BMP-tree of P1;

8H, end.

The method for realizing fast routing table lookup and update based on IPv6 address, when deleting a prefix P2 to B-HTL, perform the following steps:

9A. Find the longest address prefix node P1 of P2 in B-HTL;

9B. In the BMP-tree of P1, traverse all prefix nodes whose levels are higher than P2, and execute 9C, 9D, and 9E respectively;

9C. If the traversal is not over, execute 9D; otherwise, execute 9F;

9D. If the node is the prefix of P2, then execute 9E, otherwise traverse to the next node and execute 9C;

9E. Modify the information stored in the data structure of the node, traverse to the next node, and execute 9C;

9F. Take out the BMP-tree of P2 and merge it into the BMP-tree of P1;

9G. Delete the prefix information of P2;

9H, end.

Each hash table in the B-HTL corresponds to a unique address prefix length, and all hash tables in the B-HTL correspond to an address prefix length interval; the binary search tree is constructed within this prefix length interval, and the binary search Each node of the tree covers a part of the address prefix length interval of B-HTL, the prefix length of the hash table corresponding to this node is also in this part of the address prefix length interval, and this part of the address prefix length interval is divided into two sub-intervals, the The two sub-intervals correspond to the left and right sub-nodes of the node; in the address prefix length interval corresponding to any node, a hash table with the largest number of entries is selected as the hash table corresponding to the arbitrary node.

Each hash table in the B-HTL corresponds to a unique address prefix length, and all hash tables in the B-HTL correspond to an address prefix length interval; the binary search tree is constructed within this prefix length interval, and the binary search Each node of the tree covers a part of the address prefix length interval of B-HTL, the prefix length of the hash table corresponding to this node is also in this part of the address prefix length interval, and this part of the address prefix length interval is divided into two sub-intervals, respectively Corresponding to the left and right sub-nodes of the node; in the address prefix length interval corresponding to any node, select a hash table, and use this hash table to divide the address prefix length interval into two sub-intervals, so that the hash table in the first sub-interval If the sum of entries is the closest to the sum of entries in the hash table in the second subinterval, then this hash table is used as the hash table corresponding to the node.

The present invention adopts two-level search and three data structure modes, and divides the entire address space into 64k parts through a first-level linear index. While ensuring the efficiency of the original binary search method based on address prefixes, each routing The update operation of the table only needs to be carried out in one of the 64k address spaces without changing the routing tables in other address spaces, which improves the efficiency of updating and reconstructing the routing table. At the same time, in the data structure B-HTL of the binary search method based on the address prefix, a data organization method called BMP_tree is added. Through this data organization method, the hash table that needs to be accessed in the routing table update operation is reduced. item, which further improves the efficiency of routing table update.

Description of drawings

Figure 1 is a schematic diagram of the IPv6 address format.

Fig. 2 is an interrelationship diagram of data structures used in the present invention.

FIG. 3 is a schematic diagram of the structure of entries in the linear index table.

Fig. 4 is a flow chart of routing table search by applying the present invention.

Fig. 5 is a schematic diagram of the BMP-tree structure in the present invention.

Fig. 6(a) is a flow chart of adding prefix P2 in B-HTL.

Fig. 6(b) is a flow chart of deleting prefix P2 in B-HTL.

Fig. 7(a) is a statistical diagram of the distribution of address prefixes according to the length in the IPv4 routing table.

Fig. 7(b) is a statistical diagram of the distribution of address prefixes according to the length in the IPv6 routing table.

Detailed ways

Below in conjunction with accompanying drawing and embodiment, the present invention is described in further detail.

In RFC2373 and RFC2374, an aggregated global unicast address format scheme is proposed, which divides the IPv6 address into several segments, in which the first 64 bits are the network ID, and the last 64 bits are the interface ID. In the network ID, several network levels are divided, and different subnet addresses are assigned by different Internet organizations. Therefore, the present invention takes the first 16 bits of the address prefix of the routing table, that is, the range corresponding to the top-level aggregate identifier, as the index value of the first-level linear index, and constructs the HTL, and then forms the B-HTL according to the remaining 112-bit address, The dichotomy search is performed in it, and the schematic diagram of the data structure shown in FIG. 1 is shown in FIG. 2 . It is mainly divided into three data structures: linear index table, HTL and B-HTL. Wherein, the B-HTL is composed of a group of hash tables, and each B-HTL corresponds to an entry in the linear index table. B-HTL is derived from the data structure used by the binary search based on the address prefix space, except that the first 16 bits of the address prefix stored in its hash table are the same, which are the index values of the corresponding linear index table entries.

The structure of each entry in the linear index table is shown in Figure 3. It has two formats:

When the flag bit is 0, it means that there is no other address prefix starting with this 16-bit address prefix in the routing table and the length is greater than 16. At this time, the first 16 bits of the entry are used to indicate the mask length, that is, indicate How many prefixes of different lengths correspond to this entry; the last 7 bits of the entry are the output port, that is, the output port corresponding to the routing table prefix with the longest prefix length in the entry.

When the flag bit is 1, it means that there is an address prefix with a length greater than 16. At this time, the first 16 bits of the entry are used as a pointer to point to a B-HTL, so as to perform a binary search method based on the length of the address prefix to find the longest matching prefix. ;The last 7 bits of the entry are meaningless at this time and need to be set to 0.

Since the efficiency of linear index table lookup is far greater than that of hash lookup, and if the first-level index table can be placed in the cache, the lookup time can be ignored. The most important thing is that the linear index table divides the address prefix space into several subspaces, adding, deleting and reconstructing the data structure of the address prefix in each subspace will not affect the address prefixes of other subspaces.

After an IPv6 packet enters the router, the flow chart of the routing table lookup method is shown in FIG. 4 . Firstly, the first 16 bits of the destination address of the IPv6 packet are taken out, and the content of the 16 bits is used as an index value, assuming that this value is N, and directly located on the Nth entry of the linear index table. If the flag bit of the entry is 0, it means that in the routing table, there is no prefix with a length greater than 16 starting with the 16bit content. At this time, the third part of the output port of the entry is directly taken out as the forwarding port of the IPv6 packet. , to end a search; if the flag bit of the entry is 1, it means that there is a prefix whose length is greater than 16 and starts with the 16bit content in the routing table. In order to find this prefix, it is necessary to take out the first part of the entry, when the flag bit When it is 1, the first part stores the B-HTL pointer, and the corresponding B-HTL is located by this pointer, and the binary search is performed in the B-HTL according to the content of the last 112 bits of the IPv6 destination address. After that, it is similar to the binary search method based on the address prefix length, until the longest matching routing table prefix is found, the corresponding next-hop port number is taken out, and a search ends.

The update efficiency of the original binary search method based on the address prefix is very low, and the time complexity reaches O(N*logW). In the case of large routing tables, such efficiency is unacceptable due to the frequent occurrence of routing table updates in the network. The key factor affecting the update efficiency in the original search method is: how to find the markers that need to be updated.

The update of the marker includes the following situations.

●When replacing an address prefix, since it does not affect the marker of the prefix node, it only needs to be replaced simply.

●When inserting an address prefix, you need to add the marker required for the search to the prefix, and at the same time, you need to rewrite the BMPs of all markers with this prefix as BMP (Best Matched Prefix) to this prefix.

●When deleting a prefix, you need to delete the marker corresponding to the prefix. Note that if a marker is reused, it cannot be deleted. At the same time, you need to rewrite the BMP of all markers with this prefix as BMP to the BMP of this prefix .

Through the analysis, it can be known that when updating an address prefix record p/l (p is the prefix address, l is the prefix length), the original search method needs to update two types of markers, the first type is a marker whose length is less than l, and this type of marker is used for binary search used; the second type is a marker whose BMP is p/l, and the function of this type of marker is to avoid backtracking. The update of the first type of marker is relatively simple, because the address of p is known, and the corresponding first type of marker can be directly obtained by performing a hash lookup in the hash table of the corresponding length. The second type of marker represents the prefix extension of p/l. Since we don't know which prefix extensions p/l has in the routing table, it is necessary to traverse all hash tables with a length greater than l, or in all hashes with a length greater than l It is very inefficient to perform hash lookup on the complete set prefixed with p/l in the table.

A simple method is to link the second-type markers of each prefix entry through a linear linked list when building the data structure, which can greatly reduce the search scope. However, there is still room for improvement in the execution efficiency of such a search method. Therefore, the present invention uses a tree data structure, BMP-tree, to organize entries with the same BMP.

Not all markers have a longest matching prefix. For consistency, two pseudo-prefix hash entries are added to the hash table. In this embodiment, these two pseudo-prefix entries are added to the hash table with a length of 17. Assuming that all entries in this hash table list have a common prefix p/16, then the added two pseudo-prefix entries are {p, 0}/17 and {p, 1}/17 respectively.

Figure 5(a) is a schematic diagram of the BMP-tree data structure. Figure 5(a) is before the prefix P2 is deleted (or added), and Figure 5(b) is after the prefix P2 is deleted (or added). The binary search tree on the left shows the relationship between the hash tables. On the right is the list of hash tables and the BMP-tree composed of entries in the hash table, where p indicates that the entry is a pure prefix, m indicates that the entry is a pure marker, and b indicates that the entry is both a prefix and a marker. They use the same hash entry.

For a hash entry, if it represents a prefix, that is, it is marked as p or b, then it has a pointer to its corresponding BMP-tree, and each node in the BMP-tree uses this prefix as BMP (longest matching prefix) hash entry. For each parent node in the BMP-tree, the prefix length of its left child node is greater than the prefix length of the parent node, and the prefix length of its right child node is equal to the prefix length of the parent node. Starting from the root node, the only path composed of all left child nodes is called the backbone of the BMP-tree, and the path composed of all right nodes starting from a node on the trunk becomes the branch of the BMP-tree with a length of l , where l is the prefix length of all nodes on the branch.

The entry marked as P1 in the figure corresponds to a BMP-tree, which is represented by a light-colored node. The entry marked as P2 corresponds to another BMP-tree, represented by a dark node. It can be seen that the BMP of P2 is P1. When deleting entry P2, first update the first type of marker of P2, and if the marker needs to be deleted, search for those branches whose length is less than the prefix length of P2 in the BMP-tree of P1. Then update the second type of marker of P2. At this time, you only need to rewrite the BMP of all nodes in the BMP-tree of P2 to P1, and then merge the BMP-tree of P2 into the BMP-tree of P1. The merged The data structure is shown in Figure 5(b), and its flow chart is shown in Figure 6(a).

The operation of adding a route prefix is similar to the operation of deleting it. For example, to add the prefix P2 to the data structure shown in Figure 5(b), you must first add the first type of marker of P2. If the operation of adding an entry is involved, then you must add the P2 BMP, that is, the P1 BMP- Add nodes on the branches of the corresponding length in the tree. Then to construct the BMP-tree of P2, search linearly in the branch of the BMP-tree of P1 whose length is greater than the prefix length of P2, find those nodes prefixed with P2, rewrite its BMP to P2, and transfer them from P1 Cut it from the BMP-tree of the P2 and add it to the BMP-tree of P2. The flow chart of adding prefixes is shown in Figure 6(b).

By introducing BMP-tree, the deletion operation of the prefix entry becomes very fast. If a doubly linked list is used, the time complexity of the deletion operation can be controlled at O(kWlogW), where k is the number of memory accesses required for a single operation of the linked list, Compared with the original method that requires linear search, the efficiency is greatly improved. The operation efficiency of adding routing entries is not very good, but compared with the original method, after the introduction of BMP-tree, a large number of alternative entries can be excluded according to the length of the address prefix, which is also improved to a certain extent. efficiency.

Fig. 6(a) is a flow chart of adding prefix P2 in B-HTL. Figure 7(a) shows the statistical histogram of routing prefix distribution according to the length in IPv4 backbone network routers. It can be seen from the figure that the number of prefixes of different lengths in the routing table is different, and has specific distribution characteristics. If these features are fully utilized, the average efficiency of the search method can be effectively improved. Fig. 6(b) is a flow chart of deleting prefix P2 in B-HTL. Similarly, Figure 7(b) shows the statistical histogram of the distribution of routing prefixes of IPv6 backbone network routers according to their length (only the first 64 network addresses are shown).

In order to simplify the description, the IPv4 routing table is taken as an example to illustrate the impact of using different binary search trees on the search efficiency, as shown in Figure 7, Figure 7 (a) is a statistical diagram of the distribution of address prefixes in the IPv4 routing table according to their length.

Fig. 7(b) is a statistical diagram of the distribution of address prefixes according to the length in the IPv6 routing table. If you use a balanced binary search tree to search, although some hash tables have an advantage in the number of prefixes, they are located at a deeper level in the search tree. For most search tasks, more memory access is required to complete Find it once. However, if the binary search path is designed and the hash table with a large number of prefixes is placed at a higher level, although the maximum depth of the tree is increased, the maximum search depth is increased, but the average efficiency is improved.

In addition, the introduction of the traditional binary search method based on the address prefix length will inevitably lead to additional consumption of memory. Since some markers can reuse the same memory space as the real routing prefix information, the impact of markers on space efficiency can be controlled to a certain extent. For this reason, this embodiment uses two different search tree structure schemes to minimize the occupation of memory space by markers.

Solution 1 uses a hash table with a large number of prefixes to form the upper node of the search tree, which can make the marker have the greatest possibility of multiplexing the memory space with the real routing prefix information; solution 2 is based on this consideration, for the binary search tree For a node, the prefix information in its right subtree will generate a marker at this node. If the size of the right subtree can be reduced as much as possible, the number of markers will be greatly reduced. A limit case is that each node in the binary tree has only left child nodes, so no additional marker storage is required, but the binary tree degenerates to linear search. For this reason, Scheme 2 adopts the method of balancing the left and right subtrees. When selecting a parent node, the number of prefixes in the left and right subtrees should be as equal as possible. It is best that the number of prefixes in the left node is slightly greater than the number of prefixes in the right node.

The two schemes for constructing the search tree structure greatly improve the efficiency of the search method and reduce the storage of markers.

As can be seen from the above, on the basis of the binary search method based on the length of the address prefix, the present invention uses a two-level search mode, separates the address prefix space through the first-level linear index table, and reduces the update of address prefixes in different subspaces. The mutual influence of time also ensures the efficiency of the search; a data organization method BMP-tree is added to the data structure used in the binary search method based on the length of the address prefix, which further reduces the overhead of updating the routing table; finally, The present invention provides two different binary search tree organization modes, which reduces storage overhead.

Claims (11)

1, a kind of method based on IPv6 address realizes fast routing table lookup and update, is characterized in that: First create three data structures: (1) A linear index table, where each entry corresponds to zero, one or more address prefixes whose length is equal to or less than 16; (2) Hash table list HTL, all prefixes in the routing table whose length is less than or equal to 16 are stored in different hash tables according to the length classification, and the collection of these hash hash tables constitutes the HTL; (3) Based on the hash table list B-HTL organized by the binary search tree, all the prefixes in the routing table with a length greater than 16 are stored in different hash tables according to the length classification, and these hash tables are organized through the binary search tree to form B-HTL HTL; When a data packet of the IPv6 protocol enters the router, the upper 16 bits of the destination address are taken out and used as an index value to locate the corresponding entry in the linear index table. If the flag bit of the entry is 0, the next entry in the entry is directly taken out The jump port is used as the forwarding port; otherwise, according to the information stored in the entry, use the binary search tree to search in the corresponding B-HTL; Use the data stored in HTL to update the linear index table. 2. The method for realizing fast routing table lookup and update based on IPv6 address according to claim 1, characterized in that: the linear index table is fixed to 64k entries, and the length of each entry is 3 bytes, divided into It consists of 3 parts, of which the high 16bit is the first part, which is used to indicate the length of the prefix or the pointer to the B-HTL; the next bit is a flag bit, which is used to indicate the meaning of the content stored in the first part; the third part is the last 7bit, indicating the next-hop routing port corresponding to the entry; each entry in the linear index table uniquely corresponds to a B-HTL. 3. The method for realizing fast routing table lookup and update based on IPv6 address according to claim 2, characterized in that: the first part of the linear index table entry, when used to represent the prefix length, has a length of 16 bits each Bits are all set to 1 or 0; when an address prefix of length n corresponds to a certain linear index entry, the nth bit of the first part of the entry is set to 1, otherwise it is set to 0. 4. The method for realizing fast routing table search and update based on IPv6 address according to claim 3, characterized in that: When performing an update operation in the linear index table, if the prefix length L to be updated is less than or equal to 16, first set the L-th position in the first part of the entry to 1, and then judge whether there is a bit that is 1 among the bits higher than L , if it does not exist, rewrite the third part of the linear index table entry as the port number to update the prefix according to the flag bit; When performing a deletion operation in the linear index table, if the prefix length L to be deleted is less than or equal to 16, first set the L-th position in the first part of the entry to 0, and then determine whether there is a bit of 1 among the bits higher than L , if it exists, delete the prefix in the hash table corresponding to the length of the prefix in HTL; if it does not exist, look for the bit with the highest value of 1 among those bits lower than L, and look it up in HTL according to the position of the bit For the corresponding prefix, the third part of the linear index table entry is rewritten as the port number of the found prefix. 5. The method for realizing fast routing table search and update based on IPv6 address according to claim 2, characterized in that: the operation of performing routing table search comprises the steps of: 5A, taking out the first 16 bits of the IPv6 packet destination address as an index value, and searching the corresponding entry in the linear index table; 5B. If the flag bit of the entry is 1, execute 5D; 5C. Obtain the output port corresponding to the entry, and execute 5F; 5D. Take out the last 112 bits of the IPv6 packet destination address; 5E. Obtain the B-HTL pointer in the entry of the linear index table, use the last 112bit address in the corresponding B-HTL to perform binary search, and obtain the corresponding output port; 5F, end. 6. The method for realizing fast routing table lookup and update based on IPv6 address according to claim 1, characterized in that: each node of the binary search tree of the B-HTL points to a hash table; Table items include the following parts: (1) An IPv6 address with a length of 16 bytes; (2) the next hop port number with a length of 7 bits; (3) A flag bit with a length of 1 bit, which is used to indicate whether the entry corresponds to an address prefix with a length greater than 16; (4) A marker bit with a length of 1 bit, used to indicate whether the entry corresponds to a marker; (5) The longest matching prefix BMP with a length of 8 bits is used to indicate the maximum address prefix length corresponding to the entry; (6) A marker counter with a length of 16 bits, which is used to count the number of markers superimposed on the entry; (7) expand pointer, pointing to the root node of a longest matching address prefix tree BMP_tree; (8) The next_level pointer points to the lower-level node in the BMP_tree; (9) The same_level pointer points to the same-level node in the BMP_tree. 7. The method for realizing fast routing table search and update based on IPv6 address according to claim 6, characterized in that: said BMP_tree is composed of entries of hash table in B-HTL, and the expand pointer of each entry is uniquely corresponding A BMP_tree, each node in the BMP_tree is prefixed with this entry, and the level of the node in the BMP_tree is set from low to high according to the length of the prefix in the node, and nodes with the same prefix length are in the same layer of the BMP_tree; When adding, deleting or updating the B-HTL, look up those hash table entries that need to be changed through the BMP_tree. 8. The method for realizing fast routing table search and update based on IPv6 address according to claim 7, characterized in that: when adding a prefix P2 to B-HTL, perform the following steps: 8A. Find the longest address prefix node P1 of P2 in B-HTL; 8B. In the BMP-tree of P1, traverse all prefix nodes whose levels are higher than P2, and execute 8C, 8D, and 8E respectively; 8C. If the traversal is not over, execute 8D; otherwise, execute 8F; 8D. If P2 is the prefix of the node, then execute 8E, otherwise traverse to the next node and execute 8C; 8E. Take out the node from the BMP-tree of P1, move to the BMP-tree of P2, traverse to the next node, and execute 8C; 8F, add marker in B-HTL for P2; 8G. Add P2 to the BMP-tree of P1; 8H, end. 9. The method for realizing fast routing table lookup and update based on IPv6 address according to claim 7, characterized in that: when deleting a prefix P2 to B-HTL, perform the following steps: 9A. Find the longest address prefix node P1 of P2 in B-HTL; 9B. In the BMP-tree of P1, traverse all prefix nodes whose levels are higher than P2, and execute 9C, 9D, and 9E respectively; 9C. If the traversal is not over, execute 9D; otherwise, execute 9F; 9D. If the node is the prefix of P2, then execute 9E, otherwise traverse to the next node and execute 9C; 9E. Modify the information stored in the data structure of the node, traverse to the next node, and execute 9C; 9F. Take out the BMP-tree of P2 and merge it into the BMP-tree of P1; 9G. Delete the prefix information of P2; 9H, end. 10. The method for realizing fast routing table search and update based on IPv6 address according to claim 1 or 6, characterized in that: each hash table in the B-HTL corresponds to a unique address prefix length, and in the B-HTL All hash tables correspond to an address prefix length interval; the binary search tree is constructed within this prefix length interval, and each node of the binary search tree covers a part of the address prefix length interval of B-HTL, and the hash table corresponding to the node The prefix length of the address prefix length is also in this part of the address prefix length interval, and this part of the address prefix length interval is divided into two sub-intervals, and the two sub-intervals correspond to the left and right child nodes of the node; the address prefix length corresponding to any node In the interval, a hash table with the largest number of entries is selected as the hash table corresponding to the arbitrary node. 11. The method for searching and updating a fast routing table based on an IPv6 address according to claim 1 or 6, wherein each hash table in the B-HTL corresponds to a unique address prefix length, and in the B-HTL All hash tables correspond to an address prefix length interval; the binary search tree is constructed within this prefix length interval, and each node of the binary search tree covers a part of the address prefix length interval of B-HTL, and the hash table corresponding to the node The prefix length of the address prefix length is also in this part of the address prefix length interval, and this part of the address prefix length interval is divided into two sub-intervals, corresponding to the left and right child nodes of the node; in the address prefix length interval corresponding to any node, select A hash table, using this hash table to divide the address prefix length range into two sub-ranges, so that the sum of the number of hash table entries in the first sub-range is closest to the sum of the number of hash table entries in the second sub-range, then the hash table as the hash table corresponding to the node.

Images