[go: up one dir, main page]

WO2015192742A1 - Dispositif de recherche, procédé de recherche, et procédé de configuration - Google Patents

Dispositif de recherche, procédé de recherche, et procédé de configuration Download PDF

Info

Publication number
WO2015192742A1
WO2015192742A1 PCT/CN2015/081357 CN2015081357W WO2015192742A1 WO 2015192742 A1 WO2015192742 A1 WO 2015192742A1 CN 2015081357 W CN2015081357 W CN 2015081357W WO 2015192742 A1 WO2015192742 A1 WO 2015192742A1
Authority
WO
WIPO (PCT)
Prior art keywords
prefix
mbt
node
subtree
length
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/CN2015/081357
Other languages
English (en)
Chinese (zh)
Inventor
张文勇
崔秀梅
杨鸿志
汪自雄
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Huawei Technologies Co Ltd
Original Assignee
Huawei Technologies Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Huawei Technologies Co Ltd filed Critical Huawei Technologies Co Ltd
Publication of WO2015192742A1 publication Critical patent/WO2015192742A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Definitions

  • the present invention relates to the field of data communications, and in particular, to a search device, a search method, and a configuration method.
  • the main task of the router is to forward the Internet Protocol (IP) packet, that is, forward the packet to the router's input port to the correct output port according to the destination IP address in the packet header.
  • IP Internet Protocol
  • the route lookup process is to find the routing table in the router based on the destination IP address of the packet and obtain the next hop information of the packet.
  • Each route in the routing table is mainly composed of a prefix and corresponding next hop information, and the prefix can be represented by a three-valued bit string consisting of '0', '1' and '*'.
  • Route lookup uses the principle of longest prefix match (LPM). When multiple prefixes match the entered IP address, the next hop information corresponding to the longest prefix in the prefix matching the IP address is the final search result.
  • LPM longest prefix match
  • Trie tree also called a prefix tree
  • An algorithm based on a Trie tree builds a binary tree or a multi-tree based on a bit string in the prefix. If you consider one bit at a time, create a binary tree, also known as the unit Trie tree.
  • Figure 1 shows a unit Trie tree containing 11 prefixes, p0 to p10 on the left side in Figure 1, corresponding nodes in the unit Trie tree are indicated by black circles, and connection points are indicated by white circles. If you consider multiple bits each time, create a multi-bit Trie tree. In multiple Trie trees, the number of bits considered each time is generally fixed, called the step size of the Trie tree (English: stride).
  • the MBT (multi-bit trie) tree algorithm is a widely used route lookup algorithm.
  • MBT can be thought of as dividing a unit Trie tree into multiple subtrees by stride and creating a Trie node for each subtree.
  • Each Trie node has an associated prefix, and the associated prefix of a Trie node is the prefix value on the root node of the subtree corresponding to the Trie node.
  • the number of prefixes in a subtree is up to 2 stride -1. If a prefix is distributed in a subtree, a prefix (English: prefix) node is created for the subtree, and the prefixes in a subtree are saved. In the prefix node corresponding to the subtree.
  • Each prefix corresponds to one next hop information. Generally, only the next hop pointer, that is, the pointer to the next hop information, is stored in the MBT.
  • FIG. 2 shows an MBT tree with stride equal to 3 established based on the prefix in FIG. 1.
  • the MBT tree includes seven Trie nodes, such as the Trie Node T1 to Trie Node T7 shown in FIG. 2, and each Trie node is configured with a prefix node, such as the Prefix Node shown in FIG. 2.
  • Each of the Prefix Nodes stores a next hop pointer of each prefix in the Trie node corresponding to the Prefix Node.
  • the prefix node corresponding to the Trie Node T4 in FIG. 2 (the prefix node indicates a prefix node) stores the prefix p3.
  • One hop pointer "RE Index of P3" One hop pointer "RE Index of P3".
  • a longest prefix match (PLPM) is also stored.
  • the PLPM of a prefix node is the longest prefix that covers the subtree corresponding to the prefix node.
  • the "RE Index of PLPM" in the prefix node in Fig. 2 indicates the next hop pointer of the PLPM of the prefix node.
  • the prefixes located in a subtree are stored in the prefix node corresponding to the subtree.
  • a prefix node all prefixes in the subtree corresponding to the prefix node are usually saved, and the prefix stored in the prefix node is indicated by a bitmap, and the bitmap includes 2 stride - 1 bit.
  • the bitmap includes 2 stride - 1 bit.
  • the value of the step size is generally increased, for example, the value is 8.
  • the bitmap corresponding to the prefix node also occupies more bits. If the prefix distribution is sparse, the number of prefixes stored in the prefix node is small, but the corresponding bitmap still needs to occupy more bits, resulting in larger storage space overhead and lower utilization.
  • the embodiment of the invention provides a searching device, a searching method and a configuration method, which are used to improve the coding efficiency of the prefix node, thereby reducing the overhead of the storage space.
  • a search device comprising: a storage unit;
  • the storage unit is configured with N prefix nodes, N ⁇ 1, each prefix node includes a first data domain, and the first data domain includes M prefix sets, where M ⁇ 1, where:
  • the i-th prefix node corresponds to the first MBT sub-tree of the first step length
  • the j-th prefix set of the i-th prefix node corresponds to the second MBT sub-tree
  • the second MBT sub-tree is based on the second step
  • the second MBT subtree is divided by the first step length; wherein, 1 ⁇ i ⁇ N, 1 ⁇ j ⁇ M;
  • the first prefix information includes the associated prefix and the first location information of the second MBT subtree, where the first location information is used to sequentially indicate each prefix in the second MBT subtree in the first The location in the two MBT subtrees.
  • the ith prefix node further includes a second data domain, where the second data domain includes all the first MBT subtrees The next hop corresponding to each prefix.
  • the second data domain is disposed after the first data domain
  • the order of the next hops corresponding to the prefixes in the second data domain is the same as or opposite to the order of the prefix locations indicated by the first location information in each prefix set in the first data domain.
  • the ith prefix node further includes a third a data field, where the third data field includes the number of all prefix sets in the i-th prefix node, and header information of each of the prefix sets in all the prefix sets in the i-th prefix node, where The header information of the j prefix set includes the length of the associated prefix of the second MBT subtree.
  • the third data domain is disposed before the first data domain
  • the order of the header information of each prefix set in the third data domain is the same as or opposite to the order of each prefix set in the first data domain.
  • the M in the first data domain The prefix set includes the first to the Mth prefix sets in the search order, and the length of the associated prefix stored in the first prefix set in the M prefix sets is not less than the length of the associated prefix stored in the j+1 prefix set. 1 ⁇ j ⁇ M.
  • the ith prefix node includes first indication information, where Instructing the second MBT subtree corresponding to the jth prefix set to include a unique prefix, where the first location information in the jth prefix set is the node with the unique prefix in the second MBT subtree a location number, the length of the first location information is equal to the second step; or
  • the second i-prefix node includes second indication information, where the second MBT sub-tree corresponding to the j-th prefix set includes at least two prefixes, and the first location in the j-th prefix set
  • the information is a bitmap, and is used to indicate a position of the at least two prefixes in the second MBT subtree in the second MBT subtree, where the length of the first indication information is 2 stride -1, and the stride is The second step.
  • the storage unit is configured to perform a search process; or
  • the searching device further includes a searching unit, and the searching unit is configured to execute the searching process based on the storage unit;
  • the search process includes:
  • the first to the seventh possible implementation manners of the first aspect in an eighth possible implementation manner of the first aspect, further comprising a configuration unit, where the configuration unit is configured to configure the storage a prefix node in the unit.
  • the configuration unit is specifically configured to:
  • the prefix information to be configured, where the prefix includes at least one address prefix and a next hop corresponding to the address prefix;
  • a search method including:
  • each prefix node includes a first data domain
  • the first data domain includes M a prefix set, M ⁇ 1
  • the i-th prefix node corresponds to a first MBT sub-tree of the first step length
  • the j-th prefix set of the i-th prefix node corresponds to a second MBT sub-tree
  • the second MBT The subtree is obtained by dividing the first MBT subtree based on the second step, the second step is smaller than the first step length, 1 ⁇ i ⁇ N, 1 ⁇ j ⁇ M, the jth And the first location information is used to sequentially indicate each prefix in the second MBT subtree in the second MBT subtree.
  • the ith prefix node further includes a second data domain, where the second data domain includes all the first MBT subtrees The next hop corresponding to each prefix.
  • the second data domain is disposed after the first data domain
  • the order of the next hops corresponding to the prefixes in the second data domain is the same as or opposite to the order of the prefix locations indicated by the first location information in each prefix set in the first data domain.
  • the ith prefix node further includes a third a data field, where the third data field includes the number of all prefix sets in the i-th prefix node, and header information of each of the prefix sets in all the prefix sets in the i-th prefix node, where The header information of the j prefix set includes the length of the associated prefix of the second MBT subtree.
  • the third data domain is disposed before the first data domain
  • the order of the header information of each prefix set in the third data domain is the same as or opposite to the order of each prefix set in the first data domain.
  • the M in the first data domain The prefix set includes the first to the Mth prefix sets in the search order, and the length of the associated prefix stored in the jth prefix set in the M prefix sets is not less than the length of the associated prefix stored in the j+1 prefix set. , 1 ⁇ j ⁇ M.
  • the ith prefix node includes first indication information, where the second MBT subtree corresponding to the jth prefix set includes a unique prefix, and the first location information in the jth prefix set is Defining a node location number of the unique prefix in the second MBT subtree, the length of the first location information being equal to the second step size; or
  • the second i-prefix node includes second indication information, where the second MBT sub-tree corresponding to the j-th prefix set includes at least two prefixes, and the first location in the j-th prefix set
  • the information is a bitmap, and is used to indicate a position of the at least two prefixes in the second MBT subtree in the second MBT subtree, where the length of the first indication information is 2 stride -1, and the stride is The second step.
  • a configuration method including:
  • the prefix information to be configured, where the prefix includes at least one address prefix and a next hop corresponding to the address prefix;
  • each prefix node includes a first data domain, and the first data domain Including M prefix sets, M ⁇ 1, wherein: the i-th prefix node corresponds to the first MBT sub-tree of the first step length, and the j-th prefix set of the i-th prefix node corresponds to the second MBT sub-tree, where The second MBT subtree is obtained by dividing the first MBT subtree based on the second step, the second step is smaller than the first step length, 1 ⁇ i ⁇ N, 1 ⁇ j ⁇ M,
  • the first prefix information of the second MBT subtree includes the associated prefix and the first location information, where the first location information is used to sequentially indicate each prefix in the second MBT subtree in the second MBT The position in the subtree;
  • the ith prefix node further includes a second data domain, where the second data domain includes all the first MBT subtrees The next hop corresponding to each prefix.
  • the second data domain is disposed after the first data domain
  • the order of the next hops corresponding to the prefixes in the second data domain is the same as or opposite to the order of the prefix locations indicated by the first location information in each prefix set in the first data domain.
  • the ith prefix node further includes a third a data field, where the third data field includes the number of all prefix sets in the i-th prefix node, and header information of each of the prefix sets in all the prefix sets in the i-th prefix node, where The header information of the j prefix set includes the length of the associated prefix of the second MBT subtree.
  • the third data domain is disposed before the first data domain
  • the order of the header information of each prefix set in the third data domain is the same as or opposite to the order of each prefix set in the first data domain.
  • the M in the first data domain The prefix set includes the first to the Mth prefix sets in the search order, and the length of the associated prefix stored in the jth prefix set in the M prefix sets is not less than the length of the associated prefix stored in the j+1 prefix set. , 1 ⁇ j ⁇ M;
  • the associated prefix in the prefix set is used to match the prefix to be configured.
  • the found prefix set is determined as the longest matching prefix set of the prefix to be configured.
  • the ith prefix node includes first indication information, where the second MBT subtree corresponding to the jth prefix set includes a unique prefix, and the first location information in the jth prefix set is Defining a node location number of the unique prefix in the second MBT subtree, the length of the first location information being equal to the second step size; or
  • the second i-prefix node includes second indication information, where the second MBT sub-tree corresponding to the j-th prefix set includes at least two prefixes, and the first location in the j-th prefix set
  • the information is a bitmap, and is used to indicate a position of the at least two prefixes in the second MBT subtree in the second MBT subtree, where the length of the first indication information is 2 stride -1, and the stride is The second step.
  • a prefix set is introduced, and one prefix node may include M prefix sets, and M ⁇ 1.
  • the ith prefix node corresponds to the first MBT subtree of the first step length
  • the jth prefix set of the ith prefix node corresponds to the second MBT subtree
  • the second MBT subtree is based on the second step
  • the second step size is smaller than the first step length obtained by dividing the first MBT subtree
  • the jth prefix set includes an associated prefix and first location information of the second MBT subtree
  • the first location information is used to sequentially indicate the location of each prefix in the second MBT subtree in the second MBT subtree.
  • the data structure of the prefix node corresponding to the MBT subtree of the first step can be described by one or more prefix sets corresponding to the second step MBT subtree in the subtree. Since the second MBT subtree corresponding to one prefix set is smaller than the first MBT subtree, the number of bits used to describe the location information of the prefix on the second MBT subtree is less than that used to describe the prefix in the first MBT sub The number of bits of the location information on the tree, and considering the prefix distribution is relatively loose, the data structure of the prefix node provided by the embodiment of the present invention can improve the coding and reduce the overhead of the storage space.
  • FIG. 1 is a schematic diagram of a unit Trie tree in the background art
  • FIG. 2 is a schematic diagram of an MBT tree in the background art
  • 3a, 3b, 3c, and 3d are schematic structural views of a search device according to an embodiment of the present invention.
  • FIG. 4 is a schematic diagram of a data structure of a PCL according to an embodiment of the present invention.
  • FIG. 5 and FIG. 6 are respectively a data structure of a prefix node in an embodiment of the present invention.
  • FIG. 7 is a schematic diagram of MBT subtree division according to an embodiment of the present invention.
  • FIG. 8 is a schematic diagram showing a data structure of a prefix node based on the MBT subtree shown in FIG. 7;
  • FIG. 9 is a schematic flowchart of a search process according to an embodiment of the present invention.
  • FIG. 10 is a schematic diagram of a configuration process according to an embodiment of the present invention.
  • the embodiment of the present invention provides a search device, a search method, and a configuration method, and encodes the data structure of the prefix node by using an efficient coding manner, thereby improving the coding efficiency of the prefix node, thereby reducing The overhead of storage space.
  • the present invention will be described in detail in the following aspects: (1) the structure of the search device and the data structure of the prefix node, (2) the search process, and (3) the configuration flow.
  • the searching device may be a device located in a network device for implementing packet forwarding, such as a search module, a processor, or a hardware-implemented search engine; or a router or a switch.
  • a network device used to implement packet forwarding.
  • the prefix device stores a prefix prefix node.
  • a prefix node can be thought of as a container, that is, a prefix node corresponds to a data structure.
  • the prefix node is used to store information about the prefix.
  • the prefix node has a certain capacity limit.
  • the capacity of the prefix node refers to the size of the data structure of the prefix node, and its unit is a bit.
  • FIG. 3 is a schematic structural diagram of a search device according to an embodiment of the present invention.
  • a storage unit 31 may be included in the search device.
  • the storage unit 31 may refer to a chip implemented by a logic device, such as a ternary content addressable memory (TCAM), or a storage space in the memory.
  • TCAM ternary content addressable memory
  • the storage unit 31 is configured with N prefix nodes, N ⁇ 1, each prefix node includes a first data domain, and the first data domain includes M prefix sets, M ⁇ 1, where:
  • the i-th prefix node corresponds to the first MBT sub-tree of the first step length
  • the j-th prefix set of the i-th prefix node corresponds to the second MBT sub-tree
  • the second MBT sub-tree is based on the second step
  • the second MBT subtree is divided by the first step length; wherein, 1 ⁇ i ⁇ N, 1 ⁇ j ⁇ M;
  • the first prefix information includes the associated prefix and the first location information of the second MBT subtree, where the first location information is used to sequentially indicate each prefix in the second MBT subtree in the first The location in the two MBT subtrees.
  • the first MBT subtree is obtained according to the routing table, that is, the first MBT subtree is a subtree obtained by dividing the MBT tree corresponding to the routing table according to the first step length;
  • the subtree is a subtree obtained by dividing the "first MBT subtree" based on the second step.
  • the first MBT subtree has a smaller subtree coverage than the corresponding second MBT subtree.
  • the associated prefix of the second MBT subtree refers to the prefix corresponding to the root node of the second MBT subtree.
  • the prefix within a prefix set corresponds to the same association
  • the prefix, so a prefix set can be called prefix cluster, referred to as PCL.
  • PCL is used to represent the prefix set.
  • a larger step size is usually used for subtree partitioning, for example, the step size is 8.
  • the data structure of the prefix node in the embodiment of the present invention is sub-tree partitioned according to the step size of 8 and is again smaller than 8 in the subtree with each step size of 8 obtained by the partitioning.
  • the step size is divided into subtrees, for example, subtrees each having a step size of 8 are divided based on a step size of 3.
  • a subtree with a step size of 8 can be divided into multiple subtrees with a step size of 3. If a subtree with a step size of 3 contains a prefix, the subtree with a step size of 3 corresponds to a PCL.
  • the information about the prefix in the subtree with the step size of 3 is stored.
  • the related information may include an associated prefix corresponding to the subtree with the step size of 3, a bitmap for indicating the prefix position in the subtree, and may include the next hop information of the prefix and the like.
  • Fig. 4 exemplarily shows the data structure of one PCL. Among them, seg0 ⁇ segn saves the pre-segment of PCL, and the prefix bitmap is represented by PBM.
  • the ith prefix node further includes a second data domain, where the second data domain includes a next hop corresponding to each of the prefixes in the first MBT subtree.
  • next hop corresponding to the prefix can be set in the data structure of the prefix node as part of the PCL.
  • the second data field may be set in each PCL, so that the next hop corresponding to the prefix is placed in the corresponding PCL, or a second data field may be set in the prefix node, thereby including all the PCLs.
  • the next hop set corresponding to the prefix is placed in the data field.
  • the second data domain may be set after the first data domain; and the next hop corresponding to each prefix in the second data domain
  • the order is the same as or opposite to the order of the prefix locations indicated by the first location information in each prefix set in the first data domain.
  • the ith prefix node further includes a third data domain, where the third data domain includes the number of all prefix sets in the ith prefix node, and the ith Header information of each prefix set in all prefix sets in the prefix node, wherein the header information of the jth prefix set includes the length of the associated prefix of the second MBT subtree.
  • the length of the associated prefix may be represented by the number of pre-segments included in the associated prefix, ie, the length of the associated prefix is equal to the number of pre-segments included in the associated prefix multiplied by the second step.
  • the associated prefix corresponding to a prefix node may include one or more pre-segments, and the length of each pre-segment (ie, the number of bits) is the same as the value of the second step. For example, in the case where the second step is equal to 3, the associated prefix of a second MBT subtree is '001010*', the associated prefix contains 2 preambles, and the first preamble is '001'. The second pre-stage is '010'.
  • the number of PCLs in a prefix node is related to the first step length, the second step size, and the degree of rarity of the prefix distribution. For example, if the first step length is 8 and the second step is 3, a subtree with a step size of 8 is further divided according to the step size of 3 to obtain 21 subtrees, which requires 5 The bits represent the 21 subtrees, but considering that the prefix distribution is relatively loose, the number of PCLs in a prefix node does not exceed 16, so 4 bits can be used to represent the total number of PCLs.
  • the header information of each PCL is the same length.
  • the length of the header information of the PCL can be set to M bits.
  • IP_length represents the length of the IP address
  • stride represents the second step. Indicates rounding up. For example, if the length of the IPv6 address is 128 bits and the value of the second step is 3, the length of the header of the PCL can be set to 6 bits.
  • the third data domain is disposed before the first data domain; the order of the header information of each prefix set in the third data domain, and the order of each prefix set in the first data domain Same or opposite.
  • the total number of PCLs, the header information of the PCL, and the order of the PCLs may be: after all the PCL header information is set to the total number of PCLs, all PCLs are set to all. After the PCL header information.
  • the order in which the header information of the PCL is arranged It is in the same order as the PCL.
  • Fig. 5 exemplarily shows a data structure of a prefix node containing 6 PCLs.
  • the PCL Num field is used to store the number of PCLs, and the length is 4 bits.
  • the PCL Header field is used to store the header information of the PCL, and the length is 6 bits.
  • the PCL field is used to store the associated prefix and the first location information (such as a prefix). Bitmap), the length of a PCL is determined by the length of its associated prefix and the length of the first location information.
  • the M prefix sets in the first data domain include a first to an Mth prefix set in a search order, and a length of the associated prefix stored in the jth prefix set in the M prefix sets, Not less than the length of the associated prefix stored in the j+1 prefix set, 1 ⁇ j ⁇ M.
  • This can reduce the logical resources occupied by logical resolution. That is to say, in the data structure of a prefix node, all PCLs are arranged from front to back in descending order of the length of the associated prefix, that is, the longer PCL is always located before the shorter PCL. Accordingly, the header information of all PCLs is also arranged in descending order of the length of the associated prefix in the PCL.
  • the first location information may be a bitmap, that is, the location of the prefix in the second MBT subtree is indicated by a bitmap manner.
  • the number of the prefix in the second MBT subtree may be used as the first location information to identify the location of the prefix in the second MBT subtree.
  • the bitmap can be used as the first location information to identify the locations of these prefixes in the second MBT subtree.
  • the ith prefix node includes first indication information, where the second MBT subtree corresponding to the jth prefix set includes a unique prefix, and the first one of the jth prefix sets
  • the location information is a node location number of the unique prefix in the second MBT subtree, the length of the first location information is equal to the second step size; or the second i th prefix node includes a second
  • the indication information is used to indicate that the second MBT subtree corresponding to the jth prefix set includes at least two prefixes, and the first location information in the j th prefix set is a bitmap, and is used to indicate the The position of the at least two prefixes in the second MBT subtree in the second MBT subtree, the length of the first indication information is 2 stride -1, and the stride is the second step size.
  • the length of the first indication information and/or the second indication information is 1 bit.
  • an extra bit can be set in the header information of a PCL.
  • the value of the bit is equal to 1, it indicates that the first location information in the corresponding PCL indicates the node location number; when the value of the bit is equal to 0, indicating that the first location information in the corresponding PCL is in the form of a bitmap.
  • an extra 1 bit can be set in the data structure of the prefix node, for example, after the total number of PCLs.
  • the value of the bit is equal to 1, it indicates that the first location information in all PCLs in the prefix node indicates the node location number; when the value of the bit is equal to 0, it indicates the number of all PCLs in the prefix node.
  • a location information is in the form of a bitmap.
  • the prefix when there is only one prefix in a PCL, the prefix can be used to indicate the node position number in the 7-bit bitmap. If the node position number is used, only 3 bits are needed. So in this case, using the node location number to indicate that it will save more storage resources.
  • using the node location number to indicate that it will save more storage resources.
  • using the node location number to indicate the prefix location will significantly reduce the overhead of storage resources.
  • a subtree having a step size of 8 is divided into 7 subtrees based on a step size of 3, if one step is If there is only one prefix in the subtree of 3 and is located in the fifth node in the subtree, the node location number "110" may be used as the first location information to indicate the node location of the prefix in the subtree;
  • a subtree with a step size of 3 has two prefixes and is located in the first and fifth nodes in the subtree.
  • the bitmap "1000100" can be used to indicate that the two prefixes are in the subtree. Node location.
  • FIG. 6 exemplarily shows a data structure of a prefix node including a prefix next hop.
  • the longer PCL is always arranged before the shorter PCL.
  • the RE Index field is used to store the next hop of the prefix and is 20 bits in length. The order of the RE Index and the corresponding front The order of the suffixes is reversed.
  • an MBT tree shown in FIG. 7 is taken as an example to describe the data structure of the prefix node.
  • Figure 7 (1) shows the prefix of a distribution within an MBT subtree of step size 8;
  • Figure 7 (2) shows that the step size is 8 based on a smaller step size (3 in this example)
  • the MBT subtree is divided into smaller subtrees (T1, T2, T3, T4 as shown in the figure), and each smaller subtree corresponds to one PCL;
  • Figure 7 (3) shows each The prefix contained in the PCL;
  • Figure 7 (4) shows the data structure of each PCL.
  • PCL1 only contains 7-bit bitmap
  • PCL2 contains the associated prefix as "001 and *" 7-bit bitmap
  • PCL3 contains the associated prefix as "101*" and 7-bit bitmap, which is included in PCL4.
  • the association prefix is "001001*” and a 7-bit bitmap.
  • the corresponding prefix node structure is shown in Figure 8.
  • the associated prefix "001*" in PCL2 includes one pre-segment '001'
  • the associated prefix "101*” in PCL3 includes one pre-segment '101'
  • "001001*" contains 2 pre-segments, the first pre-segment is '001' and the second pre-segment is '001'.
  • PCL4 the longer PCL is placed in front, so the order of arrangement of the PCL is PCL4, PCL2, PCL3, and PCL1.
  • PCL2 and PCL3 are the same length and have no order requirements.
  • the length of the bitmap is fixed, so the bitmap can also be placed in the PCL header.
  • the advantage of putting a long PCL in front is to save logic resources.
  • the prefix length is 128 bits at the maximum and the MBT step size is 3
  • the operation length of the first PCL parser only needs to be set to 126 bits (a multiple of the step size, ie, ), in the latter PCL parser, the length of the operation can be decremented in turn.
  • the operation length of a PCL parser refers to the number of bits that a logical unit of a PCL parser can process in one clock cycle.
  • the operation length of the PCL parser can be successively decremented to save the logic unit.
  • the storage unit 31 may also perform a lookup process.
  • the search device may further include a lookup unit 32 for performing the search process based on the storage unit 31. The search process will be described in detail in the subsequent content.
  • the storage unit 31 may refer to a chip implemented by a logic device, such as a TCAM. In this case, the storage unit 31 may perform a lookup process.
  • the storage unit 31 may also refer to a storage space in the memory.
  • the search unit 32 may be implemented by software, such as a functional unit in the processor. In this case, the searching unit 32 is configured to perform the search based on the storage unit 31. Process.
  • the searching device may further include a configuration unit 33 for configuring a prefix node in the storage unit 31.
  • the configuration flow will be described in detail in the subsequent content.
  • the configuration unit 33 can be implemented by software, such as a functional unit in the processor.
  • the configuration unit 33 may be a functional unit in the processor, and the storage unit 31 may be a chip implemented by a logic device.
  • the configuration unit 33 is configured to configure a prefix node in the storage unit 31, a prefix node is configured in the storage unit 31, and a search process can be performed.
  • one prefix node may include M prefix sets, and M ⁇ 1.
  • the ith prefix node corresponds to the first MBT subtree of the first step
  • the jth prefix set of the ith prefix node corresponds to the second MBT.
  • the second MBT sub-tree is obtained by dividing the first MBT sub-tree based on a second step, where the second step size is smaller than the first step length; and the j-th prefix set is included
  • the associated prefix and the first location information of the second MBT subtree, the first location information is used to sequentially indicate the location of each prefix in the second MBT subtree in the second MBT subtree.
  • the data structure of the prefix node corresponding to the MBT subtree of the first step can be described by one or more prefix sets corresponding to the second step MBT subtree in the subtree.
  • the data structure of the prefix node can improve the coding and reduce the overhead of the storage space.
  • a bitmap of 128 bits is needed in a prefix node to describe the position of the prefix.
  • a subtree with a step size of 3 (hereinafter referred to as a small subtree) is obtained by using a step size of 3, each of which contains a prefix.
  • the tree is for a set of prefixes, such that a bitmap of only 8 bits is needed in a prefix set to describe the location of the prefix.
  • the traditional MBT algorithm is used, and the data structure of the prefix node includes at least a 128-bit bitmap (excluding the Re Index).
  • the data structure of the prefix node needs at most 68. Bit (does not include Re Index).
  • FIG. 9 shows the search flow.
  • the discovery process can include:
  • Step 91 Obtain a search keyword
  • Step 92 Search for the prefix node whose associated prefix matches the search key with the longest match among the configured N prefix nodes. This process can be performed in parallel.
  • the data structure of the prefix node is as described above and will not be described in detail herein.
  • Step 93 Perform the following steps for the discovered prefix node:
  • Step 94 Obtain a next hop according to a prefix that matches the search keyword, and obtain a search result of the search keyword.
  • the data structure of the prefix node may also include the total number of prefix sets in the prefix node, the header information of each prefix set, and the associated prefix of one prefix set may be one or more pre-segments.
  • the length of the associated prefix of a prefix set can be represented by the number of prefix segments included in the associated prefix, so in step 93, the preamble of the first PCL can be calculated based on the total number of PCLs. The starting position of the segment.
  • the total number of associated prefix fields of the PCL can be obtained by multiplying the number of prefix segments in the PCL header information by three. length.
  • the end position of the associated prefix field of the PCL and the prefix bitmap position can be calculated according to the starting position of the associated prefix field of the first PCL and the total length of the associated prefix field.
  • the starting position of the first PCL association prefix field is 255-4-6*PCL Num
  • the ending position is 255-4-6*PCL Num-3* PCL header+1
  • the location range of the prefix bitmap is [255-4-6*PCL Num-3*PCL header:255-4-6*PCL Num-3*PCL header-7+1]
  • the starting position of the associated prefix field of the PCL is the ending position of the prefix bitmap of the first PCL, and so on, the associated prefix field of all PCLs can be obtained.
  • the location of the prefix bitmap field is the starting position of the first PCL association prefix field.
  • the left position of the PCL associated prefix field is shifted by 1 bit to the left (ie, 1 bit is moved to the upper direction), and then moved to the right (ie, moved to the lower direction).
  • the associated prefix of the PCL is obtained. Then shift the 7 bits to the right to get the prefix bitmap field of the PCL.
  • step 93 the process of searching for a prefix set whose associated prefix matches the lookup keyword in all prefix sets is an iterative process.
  • all prefix sets can be arranged according to the length of the associated prefix.
  • the search prefix may be matched with the lookup key in the prefix set in the search order from front to back, and when the first associated prefix is found to match the search key
  • the set of prefixes is determined by the set of prefixes that are found to be the longest matching prefix of the lookup key.
  • the lookup engine is usually configured as a pipeline-level architecture, and the lookup process is performed in a pipeline-level order.
  • the corresponding PCL is configured in each level on the pipeline level, and the segmentation keyword corresponding to the search keyword of the current level is obtained according to the length of the PCL configured in the current level and the length that the search key has been matched. For example, first shifting the search key to the left by a corresponding number of lengths that have been matched in the previous stage pipeline, and then right shifting (256 - the PCL preamble length + 2) bits, the lower 2 bits indicate the The prefix bitmap of the segmentation key, the [pre-segment length +1:2] range-defined bit represents the pre-segment of the segmentation key.
  • the PCL's associated prefix is used to match the segmentation key.
  • the first matching prefix from the going to the post-matching process is the longest matching prefix with the lookup key. For example, compare the pre-segment of the PCL and the segmentation key, and compare the lower 2 bits of the segmentation key with the prefix bitmap of the PCL (compare bitmap[3:0] with the segment key, if not match Bitmap[5:4] and segment key[1], if they still do not match, check whether bitmap[6] is 1). After going to, the first prefix matching the pre-segment and the prefix bitmap is the search and lookup. The prefix that matches the longest keyword.
  • a prefix node may include first indication information, which is used to indicate that the second MBT subtree corresponding to the prefix set in the prefix node includes a unique prefix.
  • the first in the prefix set A location information is a node location number; or a prefix node may include second indication information, which is used to indicate that the second MBT subtree corresponding to the prefix set in the prefix node includes at least two prefixes.
  • the first location information in the prefix set is a bitmap.
  • step 93 it is required to determine the meaning of the first location information (that is, a node location number or a bitmap) based on the first indication information or the second indication information, thereby determining storage of the prefix set.
  • the second data field of the data structure of the prefix node may further include the next hop corresponding to all the prefixes in the prefix node, and the order of the next hop corresponding to each prefix in the second data domain,
  • the order of the prefix locations indicated by the first location information in each of the prefix sets in the first data domain is the same or opposite.
  • the next hop needs to be obtained in a different manner according to the next hop ranking order. For example, as shown in FIG.
  • one prefix node may include M prefix sets, and M ⁇ 1.
  • the ith prefix node corresponds to the first MBT subtree of the first step length
  • the jth prefix set of the ith prefix node corresponds to the second MBT subtree
  • the second MBT subtree is based on the second step
  • the second step size is smaller than the first step length obtained by dividing the first MBT subtree
  • the jth prefix set includes an associated prefix and first location information of the second MBT subtree
  • the first location information is used to sequentially indicate the location of each prefix in the second MBT subtree in the second MBT subtree.
  • the data structure of the prefix node corresponding to the MBT subtree of the first step may be described by one or more prefix sets corresponding to the second step MBT subtree in the subtree. Since the second MBT subtree corresponding to one prefix set is smaller than the first MBT subtree, the number of bits used to describe the location information of the prefix on the second MBT subtree is less than that used to describe the prefix in the first MBT sub The number of bits of the location information on the tree, and considering the prefix distribution is relatively loose, the data structure of the prefix node provided by the embodiment of the present invention can improve the coding and reduce the overhead of the storage space.
  • FIG. 10 shows the configuration flow.
  • the configuration process can include:
  • Step 101 Obtain prefix information to be configured, where the prefix includes at least one address prefix and a next hop corresponding to the address prefix.
  • Step 102 Search for the prefix node whose associated prefix is the longest match with the address prefix to be configured in the configured N prefix nodes. This process can be performed in parallel.
  • the data structure of a prefix node is the same as that described above, and is not described here.
  • Step 103 Perform the following operations on the found prefix node:
  • Step 104 Configure a next hop corresponding to the to-be-configured address prefix in the prefix node, and update first location information in the prefix set that matches the address prefix to be configured.
  • the routing table allows manual configuration or update, or can be updated according to the relevant protocol.
  • a static route can be manually configured or dynamically updated according to a routing protocol such as the Border Gateway Protocol (BGP), including adding a new routing entry or deleting an existing routing entry.
  • Border Gateway Protocol BGP
  • a prefix that needs to be added or deleted may be determined according to the received route update command for configuration update.
  • all prefix sets can be arranged according to the length of the associated prefix.
  • the associated prefix in the prefix set is matched with the prefix to be configured, and the first associated prefix is matched with the prefix to be configured.
  • the found prefix set is determined as the longest matching prefix set of the prefix to be configured.
  • the second data field in the data structure of a prefix node may further include the next hop of all the prefixes in the prefix node, and the order of the next hop corresponding to each prefix in the second data domain, and The order of the prefix locations indicated by the first location information in each prefix set in the first data domain is the same or opposite.
  • the next hop of the prefix may be added in a prescribed order.
  • a prefix node may include first indication information, which is used to indicate that the second MBT subtree corresponding to the prefix set in the prefix node includes a unique prefix.
  • the first in the prefix set A location information is a node location number; or a prefix node may include second indication information, which is used to indicate that the second MBT subtree corresponding to the prefix set in the prefix node includes at least two prefixes.
  • the first location information in the prefix set is a bitmap.
  • the prefix to be configured is a unique prefix in the prefix set
  • the first indication information is also set in the header information of the pre-level set, so that the value of the first indication information is used for
  • the first location information in the corresponding prefix set is indicated as a node location number.
  • step 102 if it is not found and to be matched in step 102 The prefix node with the longest matching prefix is used to create a corresponding prefix node for the prefix to be configured, and the corresponding information is added to the newly created prefix node according to the foregoing data structure. If the prefix set matching the prefix to be configured is not found in step 103, a corresponding prefix set is created for the prefix to be configured, and correspondingly added in the newly created prefix set and the corresponding prefix node according to the foregoing data structure. information.
  • one prefix node may include M prefix sets, and M ⁇ 1.
  • the ith prefix node corresponds to the first MBT subtree of the first step length
  • the jth prefix set of the ith prefix node corresponds to the second MBT subtree
  • the second MBT subtree is based on the second step
  • the second step size is smaller than the first step length obtained by dividing the first MBT subtree
  • the jth prefix set includes an associated prefix and first location information of the second MBT subtree
  • the first location information is used to sequentially indicate the location of each prefix in the second MBT subtree in the second MBT subtree.
  • the data structure of the prefix node corresponding to the MBT subtree of the first step can be described by one or more prefix sets corresponding to the second step MBT subtree in the subtree. Since the second MBT subtree corresponding to one prefix set is smaller than the first MBT subtree, the number of bits used to describe the location information of the prefix on the second MBT subtree is less than that used to describe the prefix in the first MBT sub The number of bits of the location information on the tree, and considering the prefix distribution is relatively loose, the data structure of the prefix node provided by the embodiment of the present invention can improve the coding and reduce the overhead of the storage space.
  • the embodiment of the present invention divides the prefix into multiple PCLs by organizing and classifying the prefixes in a prefix node by using MBT.
  • the prefixes in each PCL have the same associated prefix, and the location of the prefix contained in one PCL on the corresponding second MBT subtree can be represented by a bitmap or by a node location number.
  • the PCL is encoded by first listing the header information of each PCL, then listing the associated prefixes of all PCLs, and finally listing the bitmap or node location number indicating the prefix.
  • the number of PCL numbers included in the prefix node and each PCL header field are passed. The storage location and length of each PCL can be determined.
  • a prefix of any length can be stored in the prefix node.
  • the solution provided by the embodiment of the present invention can greatly improve coding efficiency and save memory usage.
  • the difficulty of logical parsing can be reduced, parallel parsing of multiple PCLs can be realized, and the delay of node processing can be reduced.
  • the resources used for logical parsing can be made more economical.
  • the data structure and coding mode of the prefix node provided by the embodiment of the present invention can make the MBT depth smaller by placing the prefix of any length in the same prefix node, thereby greatly improving the efficiency of the MBT algorithm, thereby reducing the delay of the search. .
  • the present invention has been described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (system), and computer program products according to embodiments of the invention. It will be understood that each flow and/or block of the flowchart illustrations and/or FIG.
  • the computer program instructions can be provided to a general purpose computer, a special purpose computer, an embedded processor, or a processor of other programmable data processing device such that instructions executed by a processor of the computer or other programmable data processing device can be implemented in a flowchart
  • the computer program instructions can also be stored in a computer readable memory that can direct a computer or other programmable data processing device to operate in a particular manner, such that the instructions stored in the computer readable memory produce an article of manufacture comprising the instruction device.
  • the apparatus implements the functions specified in one or more blocks of a flow or a flow and/or block diagram of the flowchart.
  • These computer program instructions can also be loaded onto a computer or other programmable data processing device such that a series of operational steps are performed on a computer or other programmable device to produce computer-implemented processing for execution on a computer or other programmable device.
  • the instructions provide steps for implementing the functions specified in one or more blocks of a flow or a flow and/or block diagram of the flowchart.

Landscapes

  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

L'invention concerne un dispositif de recherche, un procédé de recherche, et un procédé de configuration. Un nœud de préfixe comprend M ensembles de préfixes; le nœud de préfixe i correspond à un premier sous-arbre de trie multi-bit (MBT) d'un premier pas ; l'ensemble de préfixes j du nœud de préfixe i correspond à un second sous-arbre MBT ; le second sous-arbre MBT est obtenu en divisant le premier sous-arbre MBT selon un second pas. La structure de données du nœud de préfixe correspondant au premier sous-arbre MBT peut être décrite par l'ensemble de préfixes correspondant au second sous-arbre MBT à l'intérieur du premier sous-arbre MBT. Comme le second sous-arbre MBT correspondant à un ensemble de préfixes est inférieur au second sous-arbre MBT, il est possible de réduire le nombre de bits décrivant l'emplacement d'un préfixe sur le second sous-arbre MBT. De plus, étant donné la distribution éparse de préfixes, la structure de données du nœud de préfixe de la présente invention peut améliorer l'encodage et réduire les surdébits d'espace de stockage par rapport à l'algorithme MBT classique.
PCT/CN2015/081357 2014-06-20 2015-06-12 Dispositif de recherche, procédé de recherche, et procédé de configuration Ceased WO2015192742A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN201410280969.9 2014-06-20
CN201410280969.9A CN105227468B (zh) 2014-06-20 2014-06-20 一种查找装置、查找方法和配置方法

Publications (1)

Publication Number Publication Date
WO2015192742A1 true WO2015192742A1 (fr) 2015-12-23

Family

ID=54934863

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2015/081357 Ceased WO2015192742A1 (fr) 2014-06-20 2015-06-12 Dispositif de recherche, procédé de recherche, et procédé de configuration

Country Status (2)

Country Link
CN (1) CN105227468B (fr)
WO (1) WO2015192742A1 (fr)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN107347035B (zh) * 2016-05-06 2020-05-08 华为技术有限公司 路由查找方法、装置、分配节点、查找节点及入口节点
CN107547409B (zh) 2016-06-24 2020-12-25 华为技术有限公司 一种路由查找方法、装置和路由设备
CN108347384B (zh) * 2018-01-26 2020-12-01 乐鑫信息科技（上海）股份有限公司 一种适用于mesh网络内一对多的传输数据包的方法
CN112565089B (zh) * 2020-11-30 2022-06-21 锐捷网络股份有限公司 一种路由信息的处理方法及装置

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20030189937A1 (en) * 2002-04-03 2003-10-09 Takeshi Kawasaki Address search method and search system using the same
CN101141389A (zh) * 2007-09-29 2008-03-12 华为技术有限公司 增强多位Trie树查找方法和装置
CN101286935A (zh) * 2008-05-07 2008-10-15 中兴通讯股份有限公司 一种基于ip地址范围的路由查找方法
CN103270727A (zh) * 2010-12-31 2013-08-28 瑞典爱立信有限公司 存储体感知多位特里结构

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7782853B2 (en) * 2002-12-06 2010-08-24 Stmicroelectronics, Inc. Apparatus and method of using fully configurable memory, multi-stage pipeline logic and an embedded processor to implement multi-bit trie algorithmic network search engine

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20030189937A1 (en) * 2002-04-03 2003-10-09 Takeshi Kawasaki Address search method and search system using the same
CN101141389A (zh) * 2007-09-29 2008-03-12 华为技术有限公司 增强多位Trie树查找方法和装置
CN101286935A (zh) * 2008-05-07 2008-10-15 中兴通讯股份有限公司 一种基于ip地址范围的路由查找方法
CN103270727A (zh) * 2010-12-31 2013-08-28 瑞典爱立信有限公司 存储体感知多位特里结构

Also Published As

Publication number Publication date
CN105227468B (zh) 2019-01-08
CN105227468A (zh) 2016-01-06

Similar Documents

Publication Publication Date Title
CN102484610B (zh) 路由表建立方法和装置及路由表查找方法和装置
US8856203B1 (en) System and method for algorithmic TCAM packet classification
CN101594319B (zh) 表项查找方法和装置
US20120066410A1 (en) Data structure, method and system for address lookup
CN106416152B (zh) 一种查找装置、查找配置方法和查找方法
US11762826B2 (en) Search apparatus, search method, program and recording medium
US20050083937A1 (en) IP address lookup method using pipeline binary tree, hardware architecture, and recording medium
CN110858823B (zh) 一种数据包的分类方法、装置及计算机可读存储介质
TWI645694B (zh) 用於處理交替配置的最長首碼匹配表的裝置和方法
WO2011124030A1 (fr) Procédé et dispositif permettant de stocker une entrée de table de routage
CN102045412B (zh) IPv6地址前缀压缩存储方法及设备
WO2015192742A1 (fr) Dispositif de recherche, procédé de recherche, et procédé de configuration
US10771386B2 (en) IP routing search
US9021098B1 (en) Allocation of interface identifiers within network device having multiple forwarding components
CN100496019C (zh) IPv6路由表快速查找和更新的方法
CN102904812B (zh) 路由表项的存储方法、查找方法、装置及系统
CN100452732C (zh) 路由查找方法及其系统
CN101430741A (zh) 一种短序列映射方法及系统
CN118282943B (zh) 一种查找路由表项的方法及装置
CN101751517A (zh) 一种基因组短序列映射的快速处理方法及系统
CN110995876B (zh) 一种ip存储与查找的方法及装置
CN114448890B (zh) 寻址方法、装置、电子设备及存储介质
CN105812258B (zh) 一种数据处理方法和装置
US10476785B2 (en) IP routing search
Matoušek et al. Memory efficient IP lookup in 100 GBPS networks

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 15809729

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 15809729

Country of ref document: EP

Kind code of ref document: A1