Routing table establishment method and device and routing table lookup method and device

Abstract

The embodiments of the present invention relate to a routing table establishment method and device and a routing table lookup, method and device. The routing table establishment method includes: partitioning a data structure of a routing table into a trunk and a TRIE sub-tree ( 101 ); adding entries of the routing table to the TRIE sub-tree ( 102 ); and storing an upgrade sub-node of the TRIE sub-tree's root in the trunk, where the height of the TRIE sub-tree is smaller than or equal to a set height threshold ( 103 ), and the upgrade sub-node of the TRIE sub-tree's root is a sub-root among prefix sub-nodes included in the TRIE sub-tree's root. Thereby ensuring the high compression ratio of the routing table; and the height of the TRIE sub-tree is controlled according to the height threshold, thereby reducing times for accessing a memory, improving lookup speed, and reducing lookup delay.

1 . A routing table establishment method, comprising:
 partitioning a data structure of a routing table into a trunk and a TRIE sub-tree;   adding entries of the routing table to the TRIE sub-tree; and   storing an upgrade sub-node of the TRIE sub-tree's root in the trunk, wherein a height of the TRIE sub-tree is smaller than or equal to a set height threshold, and the upgrade sub-node of the TRIE sub-tree's root is a sub-root among prefix sub-nodes comprised in the TRIE sub-tree's root.   
     
     
         2 . The routing table establishment method according to  claim 1 , further comprising:
 if the height of the TRIE sub-tree after adding the entries of the routing table is greater than the height threshold, splitting, from the TRIE sub-tree, a branch that is in the TRIE sub-tree and has the height greater than the height threshold, to obtain a new TRIE sub-tree; and   storing an upgrade sub-node of a root of the new TRIE sub-tree in the trunk, wherein the new TRIE sub-tree's root is anode connected between the branch that is in the TRIE sub-tree and has the height greater than the height threshold and the TRIE sub-tree's root.   
     
     
         3 . The routing table establishment method according to  claim 2 , further comprising:
 if the height of the TRIE sub-tree after the splitting, is smaller than the height threshold and the TRIE sub-tree has a parent TRIE sub-tree, combining the TRIE sub-tree's root to the parent TRIE sub-tree, and deleting, from the trunk, the upgrade sub-node of the TRIE sub-tree's root.   
     
     
         4 . The routing table establishment method according to  claim 1 , further comprising:
 if the height of the TRIE sub-tree after deleting the entries of the routing table is smaller than the height threshold and the TRIE sub-tree has a parent TRIE sub-tree, combining the TRIE sub-tree's root to the parent TRIE sub-tree, and deleting, from the trunk, the upgrade sub-node of the TRIE sub-tree's root.   
     
     
         5 . The routing table establishment method according to  claim 1 , further comprising:
 establishing the TRIE sub-tree by using a TRIE algorithm, and establishing the trunk by using range matching, B tree, or a ternary content addressable memory.   
     
     
         6 . A routing table lookup method, wherein a data structure of a routing table comprises a trunk and a TRIE sub-tree, and an upgrade sub-node of the TRIE sub-tree's root is stored in the trunk of the routing table, the method comprising:
 looking up, in the trunk of the routing table, an upgrade sub-node longest matching a key word;   obtaining a location of the TRIE sub-tree's root to which the upgrade sub-node longest matching the key word corresponds; and   according to the location of the TRIE sub-tree's root to which the upgrade sub-node longest matching the key word corresponds, looking up, in the TRIE sub-tree, a lookup result corresponding to the key word by using a TRIE algorithm.   
     
     
         7 . The routing table lookup method according to  claim 6 , wherein the looking up, in the trunk of the routing table, the upgrade sub-node longest matching the key word comprises:
 looking up, from upgrade sub-nodes of TRIE sub-trees stored in the trunk of the routing table, first prefixes matching the key word; and   selecting, from the first prefixes, a first prefix of a longest mask length to serve as the upgrade sub-node longest matching the key word.   
     
     
         8 . The routing table lookup method according to  claim 6 , wherein the according to the location of the TRIE sub-tree's root to which the upgrade sub-node longest matching the key word corresponds, looking up, in the TRIE sub-tree, the lookup result corresponding to the key word by using the TRIE algorithm, comprises:
 according to the location of the TRIE sub-tree's root to which the upgrade sub-node longest matching the key word corresponds, looking up, from prefix sub-nodes of nodes of the TRIE sub-tree to which the upgrade sub-node longest matching the key word corresponds, second prefixes matching the key word; and   selecting, from the second prefixes, a second prefix of a longest mask length to serve as the lookup result.   
     
     
         9 . A routing table establishment device, comprising:
 a partitioning module, configured to partition a data structure of a routing table into a trunk and a TRIE sub-tree;   an entry adding module, configured to add entries of the routing table to the TRIE sub-tree; and   a storing module, configured to store an upgrade sub-node of the TRIE sub-tree's root in the trunk, wherein the height of the TRIE sub-tree is smaller than or equal to a set height threshold, and the upgrade sub-node of the TRIE sub-tree's root is a sub-root among prefix sub-nodes comprised in the TRIE sub-tree's root.   
     
     
         10 . The routing table establishment device according to  claim 9 , further comprising:
 a splitting module, configured to, if the height of the TRIE sub-tree after the adding the entries of the routing table is greater than the height threshold, split, from the TRIE sub-tree, a branch that is in the TRIE sub-tree and has the height greater than the height threshold, to obtain a new TRIE sub-tree; and   the storing module, further configured to store an upgrade sub-node of a root of the new TRIE sub-tree in the trunk, wherein the new TRIE sub-tree's root is a node connected between the branch that is in the TRIE sub-tree and has the height greater than, the height threshold and the TRIE sub-tree's root;   or further comprising:   a combining and deleting module, configured to, if the height of the TRIE sub-tree after splitting is smaller than the height threshold and the TRIE sub-tree has a parent TRIE sub-tree, combine the TRIE sub-tree's root to the parent TRIE sub-tree, and delete, from the trunk, the upgrade sub-node of the TRIE sub-tree's root.   
     
     
         11 . The routing table establishment device according to  claim 10 , wherein the combining and deleting module is further configured to, if the height of the TRIE sub-tree after deleting the entries of the routing table is smaller than the height threshold and the TRIE sub-tree has a parent TRIE sub-tree, combine the TRIE sub-tree's root to the parent TRIE sub-tree, and delete, from the trunk, the upgrade sub-node of the TRIE sub-tree's root. 
     
     
         12 . A routing table lookup device, comprising:
 a trunk lookup module, configured to look up, in a trunk of a routing table, an upgrade sub-node longest matching a, key word, wherein a data structure of the routing table comprises the trunk and a TRIE sub-tree, and an upgrade sub-node of the TRIE sub-tree's root is stored in the trunk of the routing table;   a sub-tree location obtaining module, configured to obtain a location of the TRIE sub-tree's root to which the upgrade sub-node longest matching the key word corresponds; and   a sub-tree lookup module, configured to, according to the location of the TRIE sub-tree's root to which the upgrade sub-node longest matching the key word corresponds, look up, in the TRIE sub-tree, a lookup result corresponding to the key word by using a TRIE algorithm.   
     
     
         13 . The routing table lookup device according to  claim 12 , wherein the trunk lookup module comprises:
 a first prefix sub-module, configured to look up, from upgrade sub-nodes of TRIE sub-trees stored in the trunk of the routing table, first prefixes matching the key word; and   a longest matching sub-module, configured to select, from the first prefixes, a first prefix of a longest mask length to serve as the upgrade sub-node longest matching the key word.   
     
     
         14 . The routing table lookup device according to  claim 12 , wherein the sub-tree lookup module comprises:
 a second prefix sub-module, configured to, according to the location of the TRIE sub-tree's root which the upgrade sub-node longest matching the key word corresponds to, look up, from prefix sub-nodes of nodes of the TRIE sub-tree to which the upgrade sub-node longest matching the key word corresponds, second prefixes matching the key word; and   a lookup result sub-module, configured to select, from the second prefixes, a second prefix of a longest mask length to serve as the lookup result.   
     
     
         15 . The routing table lookup device according to  claim 13 , wherein the sub-tree lookup module comprises:
 a second prefix sub-module, configured to, according to the location of the TRIE sub-tree's root which the upgrade sub-node longest matching the key word corresponds to, look up, from prefix sub-nodes of nodes of the TRIE sub-tree to which the upgrade sub-node longest matching the key word corresponds, second prefixes matching the key word; and   a lookup result sub-module, configured to select, from the second prefixes, a second prefix of a longest mask length to serve as the lookup result.   
     
     
         16 . The routing table lookup method according to  claim 7 , wherein the according to the location of the TRIE sub-tree's root to which the upgrade sub-node longest matching the key word corresponds, looking up, in the TRIE sub-tree, the lookup result corresponding to the key word by using the TRIE algorithm, comprises:
 according to the location of the TRIE sub-tree's root to which the upgrade sub-node longest matching the key word corresponds, looking up, from prefix sub-nodes of nodes of the TRIE sub-tree to which the upgrade sub-node longest matching the key word corresponds, second prefixes matching the key word; and   selecting, from the second prefixes, a second prefix of a longest mask length to serve as the lookup result.   
     
     
         17 . The routing table establishment method according to  claim 2 , further comprising:
 establishing the TRIE sub-tree by using a TRIE algorithm, and establishing the trunk by using range matching, B tree, or a ternary content addressable memory.   
     
     
         18 . The routing table establishment method according to  claim 3 , further comprising:
 establishing the TRIE sub-tree by using a TRIE algorithm, and establishing the trunk by using range matching, B tree, or a ternary content addressable memory.   
     
     
         19 . The routing table establishment method according to  claim 4 , further comprising:
 establishing the TRIE sub-tree by using a TRIE algorithm, and establishing the trunk by using range matching, B tree, or a ternary content addressable memory.