# US 2013/0227092 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 2013/0227092 A1
- Document ID: US20130227092A1
- Status: Published application
- Kind: A1
- Application number: 13/855,510
- Filed: 2013-04-02
- Published: 2013-08-29
- Earliest claimed: 2009-04-21
- Assignees: TechGuard Security LLC
- Inventors: David E. Maestas
- Web page: https://patentgrep.com/patent/US20130227092A1

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

### Claim 4 (depends on 1)

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.

### 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 comprises 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 comprises 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 comprises 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 (depends on 15)

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.

### Claim 17 (depends on 1)

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.

### Claim 18 (depends on 1)

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.

### Claim 19 (depends on 18)

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.

### Claim 20 (depends on 18)

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.

### Claim 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, 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 22 (depends on 21)

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

### Claim 23 (depends on 21)

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.

### Claim 24 (depends on 21)

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.

### Claim 25 (depends on 21)

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.

### Claim 26 (depends on 21)

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.

### Claim 27 (depends on 26)

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.

### Claim 28 (depends on 21)

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.

### Claim 29 (depends on 28)

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.

### Claim 30 (depends on 21)

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.

### Claim 31 (depends on 21)

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.
