Methods of Structuring Data, Pre-Compiled Exception List Engines, and Network Appliances

• US 20100268799A1
• Filed: 07/27/2009
• Published: 10/21/2010
• Est. Priority Date: 04/21/2009
• Status: Active Grant

• Current Assignee: Threater Incorporated
• Original Assignee: TechGuard Security LLC
• Inventors: Maestas, David E.
• Granted Patent: US 8,468,220 B2
• Time in Patent Office: Days
• US Class Current: 709/220
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data
• CPC Class Codes: H04L 41/08 Configuration management of networks or network elements address allocation H04L61/50
• CPC Class Codes: H04L 61/4552 Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories
• CPC Class Codes: H04L 61/5061 Pools of addresses
• CPC Class Codes: H04L 63/02 for separating internal from external traffic, e.g. firewalls

Abstract

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.

Claims

1. A method of sorting a plurality of internet protocol (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;

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.

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 includes 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 includes 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 includes 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 includes 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 includes 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. A method of sorting a plurality of internet protocol (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;

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;

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.

17. The method of claim 16 further comprising generating a page record indicating the page associated with each sub-range.

18. The method of claim 16 wherein the IP addresses in each cluster are assigned to one of a plurality of pages in descending cluster size order.

19. The method of claim 16 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.

20. The method of claim 16 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.

21. The method of claim 16 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.

22. The method of claim 21 wherein decreasing the number of numeric values encompassed by each sub-range includes decreasing the number of numeric values by half.

23. The method of claim 16 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.

24. The method of claim 23 further comprising if the load factor is greater than a threshold, decreasing the number of numeric values encompassed by each sub-range.

25. The method of claim 16 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.

26. A network appliance for connection to a first network, the appliance comprising:

at least one input coupled to the first network for receiving a packet from the first network, the packet including an internet protocol (IP) address;

at least one processor for determining whether to allow the packet from the first network to proceed;

at least one memory device storing instructions and data, the data including;

a plurality of pages storing a plurality of excepted IP addresses, the excepted IP addresses each having a numeric value within a range, the range divided into a plurality of contiguous sub-ranges, each page including one or more of the excepted IP addresses having numeric values within one or more of the sub-ranges associated with that page, each page having a page size defined by the number of IP addresses assigned to that page, the IP addresses assigned to each page ordered by numeric value;

the at least one processor configured via said instructions to;

identify the IP address of the packet from the first network;

identify a target page that will include the IP address if the IP address is one of the plurality of excepted IP addresses;

search the target page to determine if the IP address is one of the excepted IP addresses in the target page; and

process the packet from the first network according to whether the IP address is an excepted IP address in the target page.

27. The appliance of claim 26 wherein the data includes a page record indicating the page associated with each sub-range.

28. The appliance of claim 27 wherein the at least one processor is configures via said instructions to identify the target page by searching the page record to determine the page associated with the sub-range encompassing the IP address.

29. The appliance of claim 28 wherein the at least one processor is configured via said instructions to identify that there are no excepted addresses in the sub-range encompassing the IP address by searching the page record.

30. The appliance of claim 28 wherein the data includes a null page associated with any sub-ranges encompassing no excepted addresses.

31. The appliance of claim 30 further wherein the at least one processor is configured via said instructions to identify the null page for any sub-range which does not encompass any of the excepted IP addresses.

32. The appliance of claim 31 wherein processing the packet from the first network according to whether the IP address is an excepted IP address in the target page includes allowing the packet from the first network to proceed if the IP address is not an excepted IP address in the target page or if the processor identified the null page.

33. The appliance of claim 26 wherein processing the packet from the first network according to whether the IP address is an excepted IP address in the target page includes preventing the packet from the first network from proceeding if the IP address is not an excepted IP address in the target page.

34. The appliance of claim 26 wherein processing the packet from the first network according to whether the IP address is an excepted IP address in the target page includes allowing the packet from the first network to proceed if the IP address is not an excepted IP address in the target page.

35. The appliance of claim 26 wherein the excepted IP addresses include a plurality of allowable IP addresses and a plurality of blocked IP addresses, and processing the packet from the first network according to whether the IP address is an excepted IP address in the target page includes allowing the packet from the first network to proceed if the IP address is not an allowable IP address in the target page and preventing the packet from the first network from proceeding if the IP address is a blocked IP address in the target page.

36. The appliance of claim 26 further comprising at least one output coupled to a second network for transmitting the packet from the first network to the second network if the processor determines to allow the packet from the first network to proceed.

37. A network appliance for connection to a first network, the appliance comprising:

at least one input coupled to the first network for receiving a packet from the first network, the packet including an internet protocol (IP) address;

at least one processor for determining whether to allow the packet from the first network to proceed;

at least one memory device;

a first engine stored in the memory device, the first engine including a plurality of pages storing a plurality of excepted IP addresses, the excepted IP addresses each having a numeric value within a range of numeric values, the range divided into a plurality of contiguous sub-ranges, each page including one or more of the excepted IP addresses having numeric values within one or more of the sub-ranges associated with that page, each page having a page size defined by the number of excepted IP addresses assigned to that page, the excepted IP addresses assigned to each page ordered by numeric value; and

a first finite state machine (FSM), the first FSM including instructions executable by the processor to determine the page associated with the sub-range encompassing the IP address, and output an indication of the page associated with the sub-range encompassing the IP address;

instructions executable by the processor to search the page associated with the sub-range encompassing the IP address to determine if the IP address is an excepted IP address, and output an indication of whether the IP address is an excepted IP address;

the processor configured via instructions stored in the memory device to process the packet from the first network according to the indication from the first engine.

38. The appliance of claim 37 further comprising a second engine stored in the memory device, the second engine including a plurality of additional pages storing a plurality of additional excepted IP addresses, the additional excepted IP addresses each having a numeric value within a range of numeric values, the range divided into a plurality of contiguous sub-ranges, each page including one or more of the additional excepted IP addresses having numeric values within one or more of the sub-ranges associated with that page, each page having a page size defined by the number of additional excepted IP addresses assigned to that page, the additional excepted IP addresses assigned to each page ordered by numeric value;

and

a second FSM, the second FSM including instructions executable by the processor to determine the additional page associated with the sub-range encompassing the IP address and output an indication of the additional page associated with the sub-range encompassing the IP address;

instructions executable by the processor to search the additional page associated with the sub-range encompassing the IP address to determine if the IP address is an excepted IP address, and output an indication of whether the IP address is an excepted IP address;

the processor further configured via instructions stored in the memory device to process the packet from the first network according to the indication from the second engine.

39. The appliance of claim 38 further comprising at least one output coupled to a second network for transmitting the packet from the first network to the second network if the processor determines to allow the packet from the first network to enter the second network via processing the packet according to the indication from the first engine or the second engine.

40. The appliance of claim 37 wherein processing the packet from the first network according to the indication from the first engine includes determining to prevent the packet from the first network from proceeding when the indication from the first FSM indicates the IP address is an excepted IP address.

41. The appliance of claim 38 wherein processing the packet from the first network according to the indication from the second engine includes determining to allow the packet from the first network to proceed when the indication from the second engine indicates the IP address is an additional excepted IP address.

42. The appliance of claim 41 wherein processing the packet from the first network according to the indication from the first engine includes determining to prevent the packet from the first network from proceeding when the indication from the first engine indicates the IP address is an excepted IP address.

43. The appliance of claim 37 further comprising at least one output coupled to a second network for transmitting the packet from the first network to the second network if the processor determines to allow the packet from the first network to proceed via processing the packet according to the indication from the first engine.