IP routing search
AssigneeNew H3C Technologies Co., Ltd.
InventorsKai Ren, Changzhong Ge, Shaoliang An
Life of this patent
Estimating the term…
Abstract
A Multibit Trie is created for routing distribution of IP prefixes in each Virtual Private Network (VPN). Routing of IP prefixes in the highest level 1˜m of the Multibit Trie is expanded to IP prefixes in level m+1 according to a prefix expansion method, wherein m is an integer larger than 1. Each branch of the IP prefixes in the level m+1 of the Multibit Trie is taken as a Branch_Tree, and data structure information of each Branch_Tree is saved. When routing of an IP address in a VPN is to be searched, a Branch_Tree is searched in a Multibit Trie corresponding to the VPN according to the highest m+1 bits of the IP address, and the routing of the IP address is searched in the Branch_Tree.
Claims16
An Internet Protocol (IP) routing search method, comprising:
- creating a Multibit Trie for routing distribution of IP prefixes in each Virtual Private Network (VPN);
- expanding routing of IP prefixes in the highest level 1 to m of the Multibit Trie to IP prefixes in level m+1 according to a prefix expansion method, wherein m is an integer larger than 1;
- taking each branch of the IP prefixes in the level m+1 of the Multibit Trie as a BranchTree, and saving data structure information of each Branch_Tree;
- and
- in process of routing of an IP address in a VPN to be searched, searching for a BranchTree in a Multibit Trie corresponding to the VPN according to the highest m+1 bits of the IP address, and searching for the routing of the IP address in the BranchTree.
An Internet Protocol (IP) routing search apparatus, comprising:
- a Multibit Trie creating module, to create a Multibit Trie for routing distribution of IP prefixes in each VPN, expand routing of IP prefixes in the highest level 1 to m of the Multibit Trie to IP prefixes in level m+1 according to a prefix expansion method, wherein m is an integer larger than 1, take each branch of the IP prefixes in the level m+1 of the Multibit Trie as a Branch_Tree, and save data structure information of each Branch_Tree;
- and
- a routing search module, when routing of an IP address in a VPN is to be searched, to search for a Branch_Tree in a Multibit Trie corresponding to the VPN according to the highest m+1 bits of the IP address, and search for the routing of the IP address in the Branch_Tree.
Dependencies are inferred from the claim text.