IP routing search

An Internet Protocol (IP) routing search apparatus, comprising:

• a Multibit Trie creating and dividing module, to create a Multibit Trie for routing distribution of IP prefixes in each Virtual Private Network (VPN);
• and divide each Multibit Trie into multiple layers according to a predefined search step size;
• a routing search module, when routing search is performed for an IP address of a VPN, to generate an input key for each layer respectively, the input key of the layer comprising a VPN identifier of the VPN and bits to be searched, according to the predefined search step size, for all of at least one upper layer in the IP address;
• perform a calculation for the generated input key of each layer by using a Hash function of the layer;
• search for routing according to a data structure information pointer of a Sub_Trie node corresponding to a longest Hash hit result:
• and
• a Hash mapping module, to preconfigure multiple Hash functions for each layer;
• and each Hash function corresponding to a Hash table;
• each location in the Hash table uniquely representing a Hash calculation result;
• and each location being used to store an input key corresponding to the Hash calculation result represented by the location and a data structure information pointer of a Sub_Trie node corresponding to the input key;
• wherein when performing the calculation for the generated input key of each layer by using the Hash function of the layer, the routing search module is to perform a process of:
• performing the calculation for the generated input key of each layer by using the multiple Hash functions of the layer, and obtaining multiple Hash calculation results;
• for each Hash calculation result corresponding to the Hash function, searching the Hash table corresponding to the Hash function for a location corresponding to the Hash calculation result;
• if the location is found, comparing an input key stored at the location with the generated input key;
• if the input key stored at the location is identical with the generated input key, determining the Hash calculation result as a Hash hit result;
• if the input key stored at the location is different from the generated input key, searching the removed key list of the layer for the generated input key;
• if the removed key list comprising an input key identical with the generated input key, determining the Hash calculation result as the Hash hit result.