Methods of structuring data, pre-compiled exception list engines and network appliances
A computer executed method is disclosed for sorting a plurality of internet protocol (IP) addresses. The method includes dividing the range of IP addresses into a plurality of clusters representing a plurality of contiguous sub-ranges, assigning each IP address to the cluster associated with the sub-range that includes that IP address, and assigning the IP addresses in each cluster to one of a plurality of pages. If one of the pages has a size less than a page size limit, the method includes duplicating on that page at least one of the IP addresses assigned to that page. For each page, the IP addresses assigned to that page are ordered by numeric value. A network appliance incorporating aspects of the method is also disclosed.
1. A method of sorting a plurality of internet protocol (IP) addresses and filtering packets over a network connection based on the sorted IP addresses, each IP address having a numeric value within a range of numeric values, the method comprising:
dividing the range into a plurality of clusters representing a plurality of contiguous sub-ranges, each sub-range encompassing substantially the same number of numeric values of the range and each sub-range associated with a different cluster;
assigning each IP address to the cluster associated with the sub-range that includes the numeric value of said IP address, each cluster having a cluster size defined by the number of IP addresses assigned to that cluster;
assigning the IP addresses in each cluster to one of a plurality of pages, each page having a page size limit defining the maximum number of IP addresses that can be assigned to that page, and each page having a page size defined by the number of IP addresses assigned to that page, wherein at least one of the plurality of pages is assigned the IP addresses of a plurality of clusters such that the sum of the cluster sizes of the clusters of the assigned IP addresses is less than or equal to the page size limit of the page to which the IP addresses are assigned;
if one of said pages has a page size less than its page size limit, duplicating on said page at least one of the IP addresses assigned to that page to increase the page size of said page; and
ordering, for each page, the IP addresses assigned to said page by numeric value;
receiving, over the network connection, a packet having a source IP address;
identifying one page of the plurality of pages assigned the IP addresses of a cluster associated with a sub-range that includes the source IP address;
searching the identified page to determine if the source IP address is assigned to the identified page;
determining whether to allow the packet to proceed over the network based on if the source IP address is an allowable IP address in the identified page and to deny the packet from proceeding based on if the IP address is a blocked IP address in the identified page.
2. The method of claim 1 wherein each sub-range is associated with one of the pages and further comprising generating a page record indicating the page associated with each sub-range.
3. The method of claim 1 wherein duplicating comprises duplicating on said page one or more of the IP addresses assigned to that page to increase the page size to said page's page size limit.
4. The method of claim 1 wherein assigning comprises assigning the IP addresses in each cluster to one of a plurality of pages in descending cluster size order.
5. The method of claim 1 further comprising ordering the IP addresses by numeric value prior to assigning each IP address to the cluster associated with the sub-range that includes the numeric value of said IP address.
6. The method of claim 5 wherein ordering the IP addresses by numeric value comprises ordering the IP addresses by numeric value in ascending order.
7. The method of claim 1 further comprising ordering the clusters by cluster size prior to assigning the IP addresses in each cluster to one of the plurality of pages.
8. The method of claim 7 wherein ordering the clusters comprises ordering the clusters by cluster size in descending order.
9. The method of claim 1 wherein each page has substantially the same page size limit.
10. The method of claim 9 further comprising if a cluster has a cluster size greater than the page size limit, decreasing the number of numeric values encompassed by each sub-range.
11. The method of claim 10 wherein decreasing the number of numeric values encompassed by each sub-range comprises decreasing the number of numeric values by one half.
12. The method of claim 1 wherein the IP addresses in each cluster are assigned to one of a plurality of pages according to one of a first fit and a best fit algorithm without causing the page size of said page to exceed the page size limit.
13. The method of claim 1 further comprising determining a load factor after assigning the IP addresses in each cluster to one of the plurality of pages, the load factor being a ratio of the sum of the page size limit of the plurality of pages to the number of IP addresses in the plurality of IP addresses.
14. The method of claim 13 further comprising if the load factor is greater than a threshold, decreasing the number of numeric values encompassed by each sub-range.
15. The method of claim 1 further comprising generating a bloom filter for at least one page, the bloom filter identifying IP addresses that are not assigned to said page but are within a sub-range associated with said page.
16. The method of claim 15 , further comprising mapping the bloom filter to a portion of the IP addresses associated with the at least one page, wherein each bit in the bloom filter is associated with one number of the IP address.
17. The method of claim 1 , further comprising generating a single bloom filter to be used for a plurality of pages comprising a set of pages, the single bloom filter identifying IP addresses that are not assigned to the set of pages.
18. The method of claim 1 , further comprising generating a plurality of bloom filters, each of the plurality of bloom filters identifying IP addresses that are not assigned to at least one page.
19. The method of claim 18 , wherein one of the bloom filters of the plurality of bloom filters is associated with one number of an IP address and another one of the bloom filters of the plurality of bloom filters is associated with a different number of the IP address.
20. The method of claim 18 , wherein one of the bloom filters of the plurality of bloom filters is associated with one group of numbers of an IP address and another one of the bloom filters of the plurality of bloom filters is associated with a different group of numbers of an IP address.
21. A method of sorting a plurality of internet protocol (IP) addresses, each IP address having a numeric value within a range of numeric values, and filtering packets over a network connection based on the sorted IP addresses, the method comprising:
dividing the range into a plurality of clusters representing a plurality of contiguous sub-ranges, each sub-range encompassing substantially the same number of numeric values of the range and each sub-range associated with a different cluster;
assigning each IP address to the cluster associated with the sub-range that includes the numeric value of said IP address, each cluster having a cluster size defined by the number of IP addresses assigned to that cluster;
ordering the clusters by cluster size;
assigning the IP addresses in each cluster to one of a plurality of pages, each page having a same page size limit defining the maximum number of IP addresses that can be assigned to that page, and each page having a page size defined by the number of IP addresses assigned to that page, wherein at least one of the plurality of pages is assigned the IP addresses of a plurality of clusters such that the sum of the cluster sizes of the clusters of the assigned IP addresses is less than or equal to the page size limit of the page to which the IP addresses are assigned;
if one or more of said pages has a page size less than its page size limit, duplicating on said page one or more of the IP addresses assigned to that page to increase the page size of said page to its page size limit; and
ordering, for each page, the IP addresses assigned to said page by numeric value;
receiving, over the network connection, a packet having a source IP address over the network connection;
identifying one page of the plurality of pages assigned the IP addresses of a cluster associated with a sub-range that includes the source IP address;
searching the identified page to determine if the source IP address is assigned to the identified page;
determining whether to allow the packet to proceed based on if the source IP address is an allowable IP address in the identified page and to deny the packet from proceeding if the IP address is a blocked IP address in the identified page.
22. The method of claim 21 further comprising generating a page record indicating the page associated with each sub-range.
23. The method of claim 21 wherein the IP addresses in each cluster are assigned to one of a plurality of pages in descending cluster size order.
24. The method of claim 21 further comprising ordering the IP addresses by numeric value prior to assigning each IP address to the cluster associated with the sub-range that comprises the numeric value of said IP address.
25. The method of claim 21 wherein the IP addresses in each cluster are assigned to one of the plurality of pages according to one of a first fit and a best fit algorithm without causing the page size of said page to exceed the page size limit.
26. The method of claim 21 further comprising if a cluster has a cluster size greater than a page size limit, decreasing the number of numeric values encompassed by each sub-range.
27. The method of claim 26 wherein decreasing the number of numeric values encompassed by each sub-range includes decreasing the number of numeric values by half.
28. The method of claim 21 further comprising determining a load factor after assigning the IP addresses in each cluster to one of the plurality of pages, the load factor being a ratio of the sum of the page size limit of the plurality of pages to the number of IP addresses in the plurality of IP addresses.
29. The method of claim 28 further comprising if the load factor is greater than a threshold, decreasing the number of numeric values encompassed by each sub-range.
30. The method of claim 21 further comprising generating a bloom filter for at least one page, the bloom filter identifying IP addresses that are not assigned to said page but are within a sub-range associated with said page.
31. The method of claim 21 , further comprising generating a plurality of bloom filters, each of the plurality of bloom filters identifying IP addresses that are not assigned to at least one page.