Priority search trees
View Patent ↗A processor implements a priority search tree on data elements. A data point having two component values is stored for each data element. A comparison is performed to determine an order for two data points. When the first component values of the two data points are equal, a comparison is made using the second component values. When the second component values of the two data points are equal, a comparison is made using the first component values.
1. An apparatus arranged to implement prefix matching on a set of Internet Protocol (IP) addresses, the apparatus comprising:
a memory; and
a processor comprising:
a storage unit for storing in the memory for each of said IP addresses a corresponding data point for a priority search tree, said data point having a first component value and a second component value;
a tree-processing module for performing at least one function operation on the data points, the at least one function operation including using a comparison module to perform a comparison operation to determine a longest prefix of an IP address in the set based on a first data point preceding a second data point in an ordering for the data points, the comparison operation comprising one of:
determining the relative positions of a first data point and a second data point based on a comparison of the respective first component values of the first and second data points and, in response to the first component value of the first data point being equal to the first component value of the second data point, determining that the second component value of the first data point is greater than the second component of the second data point; or
determining the relative positions of a first data point and a second data point based on a comparison of the respective second component values of the first and second data points and, in response to the second component value of the first data point being equal to the second component value of the second data point, determining that the first component value of the first data point is greater than the first component value of the second data point;
wherein each IP address is represented by a respective binary string of a length of at most m bits and the storage unit is arranged to store in the memory the corresponding data point having the first component value equal to the m-bit number whose binary representation has most significant bits equal to the respective binary string and remaining bits equal to 1 bits and having the second component value equal to the m-bit number whose binary representation has most significant bits equal to the respective binary string and remaining bits equal to 0 bits.
2. The apparatus of claim 1 , in which the storage unit is further arranged to store the data point corresponding to IP address such that the data size of the stored data point equals the data size used to represent the IP address.
3. The apparatus of claim 1 , in which the comparison module is arranged to perform determining the relative positions of a first data point and a second data point by determining that the first data point precedes the second data point in the ordering if either
(a) the first component value of the first data point is less than the first component value of the second data point or
(b) the first component value of the first data point is equal to the first component value of the second data point and the second component value of the first data point is greater than the second component value of the second data point.
4. The apparatus of claim 1 , in which the comparison module is arranged to perform determining the relative positions of a first data point and a second data point by determining that the first data point precedes the second data point in the ordering if either
(a) the second component value of the first data point is less than the second component value of the second data point or
(b) the second component value of the first data point is equal to the second component value of the second data point and the first component value of the first data point is greater than the first component value of the second data point.
5. The apparatus of claim 1 , wherein for each IP address, that IP address represents a respective contiguous range of values defined by a lower value and an upper value and the storage unit is arranged to store in the memory the corresponding data point having the first component value equal to the upper value and the second component value equal to the lower value.
6. The apparatus of claim 1 , wherein for each IP address, the storage unit is arranged to map that IP address to a respective contiguous range of values defined by a lower value and an upper value and to store in the memory the corresponding data point having the first component value equal to the lower value and the second component value equal to the upper value.
7. The apparatus of claim 1 , in which one of the at least one function operations comprises:
determining a subset of the plurality of data points based on input parameters for the function operation; and
using the comparison operation to identify the data point in the subset that precedes all other data points in the subset based on the ordering.
8. The apparatus of claim 1 , in which one of the at least one function operations comprises:
identifying a subset of the plurality of data points based on input parameters for the function operation; and
using the comparison operation to identify the data point in the subset that is not preceded by any data points in the subset based on the ordering.
9. A method of implementing a priority search tree to represent a plurality of internet protocol (IP) addresses, the method comprising:
for each IP address, storing by a processor in a memory a corresponding data point for the priority search tree, wherein the data point has a first and second component value based on that IP address;
providing by said processor a comparison operation to determine a first data point preceding a second data point in an ordering for the data points; and
providing by said processor at least one function operation for performance on the data points, the at least one function operation involving performing the comparison operation; the comparison operation comprising one of:
determining by said processor the relative positions of a first data point and a second data point based on a comparison of the respective first component values of the first and second data points and, in response to the first component value of the first data point being equal to the first component value of the second data point, determining that the second component value of the first data point is greater than the second component value of the second data point; and
determining by said processor the relative positions of a first data point and a second data point based on a comparison of the respective second component values of the first and second data points and, in response to the second component value of the first data point being equal to the second component value of the second data point, determining that the first component value of the first data point is greater than the first component value of the second data point
wherein each IP address is represented by a respective binary string of length at most a predetermined length m bits and the step of storing comprises storing the corresponding data point having the first component value equal to the m-bit number whose binary representation has most significant bits equal to the respective binary string and has remaining bits equal to 1 bits and having the second component value equal to the m-bit number whose binary representation has most significant bits equal to the respective binary string and has remaining bits equal to 0 bits.
10. The method of claim 9 , in which the step of storing further comprises storing the data point corresponding to a IP address such that the data size of the stored data point equals the data size used to represent the IP address.
11. The method of claim 9 , in which determining by said processor the relative positions of a first data point and a second data point comprises determining that the first data point precedes the second data point in the ordering if either
(a) the first component value of the first data point is less than the first component value of the second data point or
(b) the first component value of the first data point is equal to the first component value of the second data point and the second component value of the first data point is greater than the second component value of the second data point.
12. The method of claim 9 , in which determining by said processor the relative positions of a first data point and a second data point comprises determining that the first data point precedes the second data point in the ordering if either
(a) the second component value of the first data point is less than the second component value of the second data point or
(b) the second component value of the first data point is equal to the second component value of the second data point and the first component value of the first data point is greater than the first component value of the second data point.
13. The method of claim 9 , wherein for each IP address, that IP address represents a respective contiguous range of values defined by a lower value and an upper value and the step of storing comprises storing the corresponding data point having the first component value equal to the upper value and the second component value equal to the lower value.
14. The method of claim 9 , wherein for each IP address, the method comprises mapping that IP address to a respective contiguous range of values defined by a lower value and an upper value and the step of storing further comprises storing the corresponding data point having the first component value equal to the lower value and the second component value equal to the upper value.
15. The method of claim 9 , in which one of the at least one function operations comprises:
determining a subset of the plurality of data points based on input parameters for the function operation; and
using the comparison operation to identify the data point in the subset that precedes all other data points in the subset based on the ordering.
16. The method of claim 9 , in which one of the at least one function operations comprises:
identifying a subset of the plurality of data points based on input parameters for the function operation; and
using the comparison operation to identify the data point in the subset that is not preceded by any data points in the subset based on the ordering.