# US 2010/0268799 A1 · Methods of Structuring Data, Pre-Compiled Exception List Engines, and Network Appliances

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0268799 A1
- Document ID: US20100268799A1
- Status: Published application
- Kind: A1
- Application number: 12/509,957
- Filed: 2009-07-27
- Published: 2010-10-21
- Earliest claimed: 2009-04-21
- Assignees: TechGuard Security LLC
- Inventors: David E. Maestas
- Web page: https://patentgrep.com/patent/US20100268799A1

## CPC

- H04L 61/5061: Pools of addresses
- G06F 16/9017: {using directory or table look-up (use of a directory or look-up table in file systems G06F16/13)}
- G06F 16/90348: {by searching ordered data, e.g. alpha-numerically ordered data}
- H04L 41/08: Configuration management of networks or network elements (address allocation H04L61/50)
- H04L 61/4552: Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories
- H04L 63/02: {for separating internal from external traffic, e.g. firewalls}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 5)

The method of claim 5 wherein ordering the IP addresses by numeric value includes ordering the IP addresses by numeric value in ascending order.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 7)

The method of claim 7 wherein ordering the clusters includes ordering the clusters by cluster size in descending order.

### Claim 9 (depends on 1)

The method of claim 1 wherein each page has substantially the same page size limit.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 1)

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.

### Claim 13 (depends on 1)

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.

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 1)

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.

### Claim 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.

### Claim 17 (depends on 16)

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

### Claim 18 (depends on 16)

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.

### Claim 19 (depends on 16)

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.

### Claim 20 (depends on 16)

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.

### Claim 21 (depends on 16)

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.

### Claim 22 (depends on 21)

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.

### Claim 23 (depends on 16)

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.

### Claim 24 (depends on 23)

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.

### Claim 25 (depends on 16)

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.

### Claim 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.

### Claim 27 (depends on 26)

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

### Claim 28 (depends on 27)

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.

### Claim 29 (depends on 28)

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.

### Claim 30 (depends on 28)

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

### Claim 31 (depends on 30)

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.

### Claim 32 (depends on 31)

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.

### Claim 33 (depends on 26)

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.

### Claim 34 (depends on 26)

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.

### Claim 35 (depends on 26)

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.

### Claim 36 (depends on 26)

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.

### Claim 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.

### Claim 38 (depends on 37)

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.

### Claim 39 (depends on 38)

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.

### Claim 40 (depends on 37)

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.

### Claim 41 (depends on 38)

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.

### Claim 42 (depends on 41)

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.

### Claim 43 (depends on 37)

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.
