System and method for determining a customer associated with a range of IP addresses by employing a configurable rule engine with IP address range matching

• US 6,813,645 B1
• Filed: 05/24/2000
• Issued: 11/02/2004
• Est. Priority Date: 05/24/2000
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Meyer, Jeffrey D.
• Primary Examiner(s): Dharia, Rupal
• Assistant Examiner(s): Nguyen, Quang N.
• Application Number:
  US09/578,826
• Time in Patent Office: 1,623 Days
• Field of Search: 709/220, 709/224, 709/225, 709/228, 709/238, 709/245, 707/8, 707/102, 370/392
• US Class Current: 709/245
• CPC Class Codes: H04L 61/4552 Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories

Abstract

A system and method for determining a customer associated with a range of IP addresses. The method includes the step of constructing an IP address matching tree using a defined range of IP addresses allocated to each customer including the steps of partitioning a minimum IP address and a maximum IP address which define the range of IP addresses into their four constituent bytes and sparsely populating a hierarchy of fixed sized arrays to allow look-up of each IP address associated with a customer. A set of network data is received including a match IP address. The customer associated with the match IP address is determined using the IP address matching tree by performing a sequence of array look-ups for each constituent byte in the match IP address. The method requires a maximum of only 4 look-ups to determine the customer associated with the match IP address.

Claims

1. A method for determining a customer associated with a range of IP addresses, the method comprising:

constructing in IP address matching tree using a defined range of IP addresses allocated to each customer, including partitioning a minimum IP address and a maximum IP address which define the range of IP addresses into their four constituent bytes and sparsely populating a hierarchy of fixed size arrays to allow look-up of each IP address associated with a customer;

receiving a set of network data including a match IP address;

determining the customer associated with the match IP address using the IP address matching tree by performing a sequence of array look-ups for each constituent byte in the match IP address, wherein the method requires a maximum of only four look-ups to determine the customer associated with the match IP address;

the method further comprising;

receiving a record of information associating a customer with a rankle of IP addresses, including the minimum IP address and the maximum IP address;

decomposing the minimum IP address into a minimum first byte, a minimum second byte, a minimum third byte and a minimum fourth byte;

decomposing the maximum IP address into a maximum first byte, a maximum second byte, a maximum third byte and a maximum fourth byte; and

defining a minimum second level array, and creating a pointer from the minimum first byte in the first level array to the minimum second level array;

wherein if the minimum first byte value is different from the maximum first byte value, further comprising defining a maximum second level array and creating a pointer from the maximum first byte in the first level array to the maximum second level array.

2. The method of claim 1, wherein of populating the array hierarchy further includes defining a first level array from 0 to 255.

3. The method of claim 1, further comprising creating a customer pointer in the first level array for each index value between the minimum first byte and the maximum first byte.

4. The method of claim 1, wherein if minimum first byte is not equal to the maximum first byte, populating all minimum second level array entries which are greater than the minimum second byte with a customer pointer.

5. The method of claim 1, wherein if the minimum first byte is not equal to the maximum first byte, further comprising creating a maximum third level array indexed by the maximum second byte of the maximum second level array of the maximum IP address.

6. The method of claim 5, further comprising populating all entries in the maximum second level array which are less than the maximum second byte with a customer pointer.

7. The method of claim 6, further comprising creating a minimum third level array indexed by the minimum second byte in the minimum second level array of the minimum IP address.

8. The method of claim 6, wherein if the minimum first byte value is equal to the maximum first byte, and if the minimum second byte is different from the maximum second byte, then further comprising creating a pointer to a maximum third level array indexed by the maximum second byte in the minimum second level array.

9. The method of claim 8, wherein if the minimum first byte value is equal to the maximum first byte value, further comprising creating customer pointers for all array entries between the minimum second byte value and the maximum second byte values.

10. The method of claim 1, wherein performing a sequence of array look-ups for each constituent byte in the match IP address further comprises the steps of decomposing the match IP address into a match first byte, a match second byte, a match third byte and a match fourth byte.

11. The method of claim 10, further comprising using the match first byte as an index to a first level array.

14. The method of claim 10, further comprising using the match first byte as an index to a first level array;

determining whether a second level array pointer is present, and if a second level array pointer is present, following the second level array pointer to a second level array; and

using the match second byte in the second level array for determining whether a third level array pointer is present, and if a third level array pointer is present, following the third level array pointer to a third level array.

15. The method of claim 14, further comprising using the match third byte in the third level array for determining whether a fourth level array pointer is present, and if a fourth level array pointer is present, following the fourth level array pointer to a fourth level array;

and

using the match fourth byte in the fourth level array for determining whether a customer pointer exists, and if a customer pointer exists, follow the customer pointer to a customer match.

12. A method for determining a customer associated with a range of IP addresses, the method comprising:

constructing an IP address matching tree using a defined range of IP addresses allocated to each customer, including partitioning a minimum IP address and a maximum IP address which define the range of IP addresses into their four constituent bytes and sparsely populating a hierarchy of fixed size arrays to allow look-up of each IP address associated with a customer;

receiving a set of network data including a match IP address; and

determining the customer associated with the match IP address using the IP address matching tree by performing a sequence of array look-ups for each constituent byte in the match IP address;

wherein the method requires a maximum of only four look-ups to determine the customer associated with the match IP address;

wherein performing a sequence of array look-ups for each constituent byte in the match IP address further comprises decomposing the match IP address into a match first byte, a match second byte, a match third byte and a match fourth byte;

using the match first byte as an index to a first level array; and

determining whether a customer pointer is present, and if a customer pointer is present, defining a user match.

13. The method of claim 12, wherein if no customer pointer is present, further comprising determining whether a second level array pointer is present, and if a second level array pointer is present, following the second level array pointer to a second level array.