Configuration rule generation with compressed address sets

• US 8,095,677 B1
• Filed: 05/21/2009
• Issued: 01/10/2012
• Est. Priority Date: 05/21/2009
• Status: Active Grant

• Current Assignee: Proofpoint Incorporated
• Original Assignee: Sendmail Incorporated (Proofpoint Incorporated)
• Inventors: Kucherawy, Murray S.
• Primary Examiner(s): Patel, Haresh N
• Application Number:
  US12/470,436
• Time in Patent Office: 964 Days
• Field of Search: 709217-230, 370/256, 370/254, 370/253, 370/251
• US Class Current: 709/230
• CPC Class Codes: H04L 61/35 involving non-standard use of addresses for implementing network functionalities, e.g. coding subscription information within the address or functional addressing, i.e. assigning an address to a function

Abstract

Techniques for compressing a set of input addresses to generate a set of one or more rules for various network applications and tools such as routers, firewalls, and others. A tree is generated based upon a set of input addresses. A set of one or more rules may be generated based upon the generated tree and a tolerance value. The set of one or more rules may identify one or more address segments that include the input addresses and may also include one or more additional addresses. In one embodiment, the set of one or more rules may be one or more Classless Internet Domain Routing (CIDR) expressions. The set of one or more rules may be provided to various network applications and tools for further processing.

Claims

1. A method for generating one or more network application configuration rules, comprising:

receiving, at a processing system, a plurality of input addresses;

generating, at the processing system, an acyclic tree having leaf nodes corresponding to the plurality of input addresses, each input address having an input address size measurable in bits and the acyclic tree comprising a binary tree with a depth of at least the input address size; and

generating, at the processing system, based at least in part on the tree and a tolerance value, one or more rules, wherein the one or more rules reference the plurality of input addresses and zero or more additional addresses, the number of the additional addresses referenced being controlled based at least in part on the tolerance value, and each of the one or more rules comprises a Classless Internet Domain Routing (CIDR) expression determined based at least in part on a depth of a corresponding node in the acyclic tree.

2. The method of claim 1 wherein each of the plurality of input addresses is an Internet address.

3. The method of claim 1 wherein generating the tree comprises generating a binary tree, wherein the binary tree comprises a plurality of leaf nodes with each leaf node corresponding to one of the input addresses.

4. The method of claim 3 wherein the leaf nodes taken from left-to-right order include a sorted list of the input addresses.

5. The method of claim 1 wherein the set of one or more rules includes one or more Classless Internet Domain Routing (CIDR) expressions.

6. The method of claim 1 wherein the set of one or more rules identifies one or more address segments, wherein the one or more address segments include the input addresses and include zero or more additional addresses.

7. The method of claim 1 wherein the tolerance value is a percentage value representing a percentage of additional addresses that can be included in the set of one or more rules.

8. The method of claim 1 wherein the tolerance value is a constant value representing an allowed number of over-covered addresses.

9. The method of claim 1 wherein the tolerance value is user configurable.

10. The method of claim 1 wherein the number of the one or more rules generated is less than or equal to the number of the input addresses.

11. The method of claim 1 wherein the one or more rules at least partially configure a network application.

12. The method of claim 1 wherein the tree comprises a binary tree with a depth of at least a specified minimum depth.

13. The method of claim 1 wherein the tree comprises a binary tree with a depth of at most a specified maximum depth.

14. The method of claim 1 wherein each of the one or more rules corresponds to a node of the tree.

15. The method of claim 1 further comprising receiving network traffic associated with a source address and determining that the source address is associated with the plurality of input addresses based at least in part on the one or more rules.

16. The method of claim 15 wherein the source address is not one of the plurality of input addresses.

17. A non-transitory computer-readable storage medium storing a plurality of instructions that, when executed, cause one or more computers to collectively, at least:

receive a plurality of input addresses;

generate an acyclic tree having leaf nodes corresponding to the plurality of input addresses, each input address having an input address size measurable in bits and the acyclic tree comprising a binary tree with a depth of at least the input address size; and

generate, based at least in part upon the generated tree and a tolerance value, one or more rules, wherein the one or more rules reference the plurality of input addresses and zero or more additional addresses, the number of additional addresses referenced being controlled based at least in part on the tolerance value, and each of the one or more rules comprises a Classless Internet Domain Routing (CIDR) expression determined based at least in part on a depth of a corresponding node in the acyclic tree.

18. The computer-readable storage medium of claim 17 wherein the tree comprises a binary tree having a plurality of leaf nodes and a plurality of intermediate nodes with each leaf node corresponding to one of the input addresses.

19. The computer-readable storage medium of claim 18 wherein the leaf nodes taken from left-to-right order include a sorted list of the input addresses.

20. A system for generating one or more network application configuration rules, the system comprising:

a memory configured at least to store a plurality of input addresses; and

a processor communicatively coupled to the memory, wherein the processor is configured to facilitate, at least;

receiving a plurality of input addresses;

generating an acyclic tree having leaf nodes corresponding to the plurality of input addresses, each input address having an input address size measurable in bits and the acyclic tree comprising a binary tree with a depth of at least the input address size; and

generating, based at least in part upon the tree and a tolerance value, one or more rules, wherein the one or more rules reference the plurality of input addresses and zero or more additional addresses, the number of the additional addresses referenced being controlled based at least in part on the tolerance value, and each of the one or more rules comprises a Classless Internet Domain Routing (CIDR) expression determined based at least in part on a depth of a corresponding node in the acyclic tree.

21. The system of claim 20 wherein the set of one or more rules reference one or more address segments, wherein the one or more address segments include the input addresses and include zero or more additional addresses.