Packet filter policy verification system

• US 7,039,053 B1
• Filed: 02/28/2001
• Issued: 05/02/2006
• Est. Priority Date: 02/28/2001
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Freed, Michael, Borella, Michael S., Amara, Satish
• Primary Examiner(s): Nguyen, Steven
• Assistant Examiner(s): Han, Clemence
• Application Number:
  US09/796,314
• Time in Patent Office: 1,889 Days
• Field of Search: 370/389, 370/392, 370/395.21, 370/395.31, 370/395.43, 709/220, 709/223, 709/238
• US Class Current: 370/392
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 45/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 47/20 Traffic policing

Abstract

A method for determining the validity of an n-dimensional policy table in a router. The router may include a processor, a memory (e.g. ROM, flash memory, non-volatile memory, hard disk, etc.), and two or more policy rules stored in the memory. Each policy rule may have one or more dimensions (or parameters), designated generally by the symbol n. In accord with the method, the processor may make a determination whether any particular policy rule in the table intersects any subsequent policy rule in the table in every dimension n. If no rules in the table intersect in every dimension n, then the policy table is valid, and the router may operate normally.

Claims

1. A method for validating an n-dimensional policy table in a router, the router having at least two interfaces, the policy table having at least two policy rules, and each policy rule in the policy table having at least one dimension, the method comprising:

making a first determination whether every dimension of any first policy rule intersects any subsequent policy rule in every dimension of the subsequent policy rule; and

if the first determination is that none of the policy rules intersect each other in every dimension, then producing an output signal indicating that the policy table is valid and

if the first determination is that any first policy rule of the policy table intersects any subsequent policy rule in every dimension, thereby defining a first and a second intersecting policy rule, making a second determination whether one of said first and second intersecting policy rules is a subset of the other of the said first and second intersecting policy rules.

2. The method of claim 1 wherein the second determination is whether every first policy rule that so intersects a subsequent policy rule is a subset in every dimension of every subsequent policy rule that it intersects;

and

if the second determination is that any first policy rule is not a subset in every dimension of every subsequent policy rule that it intersects, then producing an output signal indicating that the policy table is invalid,

whereby the output signal may be used to generate an appropriate action.

3. The method of claim 2, further comprising:

controlling at least one of the at least two interfaces in response to the output signal.

4. The method of claim 2, further comprising:

if the second determination is that every first policy rule is a subset in every dimension of every subsequent policy rule that it intersects, then producing an output signal indicating that the policy table is valid,

whereby the output signal may be used to generate an appropriate action.

5. The method of claim 2, wherein the second determination further comprises:

determining whether the maximum value of every dimension of every first policy rule that intersects a subsequent policy rule is less than the maximum value of every corresponding dimension of each subsequent policy rule that the first policy rule intersects; and

determining whether the minimum value of every dimension of every first policy rule that intersects a subsequent policy rule is greater than the minimum value of every corresponding dimension of each subsequent policy rule that the first policy rule intersects; and

if the maximum value of any dimension of a first policy rule is not less than a corresponding maximum value of every corresponding dimension of any subsequent policy rule that the first policy rule intersects, or if the minimum value of any dimension of a first policy rule is not greater than a corresponding maximum value of every corresponding dimension of any subsequent policy rule that the first policy rule intersects, determining that not every first policy rule that intersects a subsequent policy rule in every dimension is a subset in every dimension of every subsequent intersected policy rule.

6. The method of claim 1, further comprising:

if the first determination is that at least one first policy rule of the policy table intersects at least one subsequent rule in every dimension, making a second determination whether the at least one subsequent policy rule that so intersects the at least one first policy rule is a subset of the at least one first policy rule in every dimension; and

if the second determination is that the at least one subsequent policy rule is a subset in every dimension of the at least one first policy rule that it intersects, then producing an output signal indicating that the table may be made valid if the order of the intersecting rules is reversed.

7. The method of claim 1, wherein making the first determination further comprises:

determining whether the maximum value of at least one dimension of every first policy rule is less than the minimum value of a corresponding dimension of each subsequent policy rule; and

if the maximum value of any dimension of every first policy rule is less than the minimum value of a corresponding dimension of each subsequent policy rule, determining that the policy table is valid.

8. The method of claim 1, wherein making the first determination further comprises:

determining whether the minimum value of at least one dimension of every first policy rule is greater than the maximum value of a corresponding dimension of each subsequent policy rule; and

if the minimum value of any dimension of every first policy rule is greater than the maximum value of a corresponding dimension of each subsequent policy rule, determining that the policy table is valid.

9. A method for validating an n-dimensional policy table in a router, the router having at least two interfaces, the policy table having at least two policy rules, and each policy rule in the policy table having at least one dimension, the method comprising:

making a first determination whether any policy rules intersect by determining whether the maximum value of at least one dimension of every first policy rule is less than the minimum value of a corresponding dimension of each subsequent policy rule;

if the first determination is that the maximum value of any dimension of every first policy rule is less than the minimum value of a corresponding dimension of each subsequent policy rule, producing an output signal indicating that no policy rules intersect and the policy table is valid;

making a second determination whether any policy rules intersect by determining whether the minimum value of at least one dimension of every first policy rule is greater than the maximum value of a corresponding dimension of each subsequent policy rule;

if the second determination is that the minimum value of any dimension of every first policy rule is greater than the maximum value of a corresponding dimension of each subsequent policy rule, producing an output signal indicating that the policy table is valid;

if the first or second determination is that at least two policy rules intersect in every dimension, then making a third determination whether every first policy rule that intersects a subsequent policy rule is a subset of every intersected subsequent policy rule by determining whether the maximum value of every dimension of every first policy rule is less than the maximum value of every corresponding dimension of each subsequent policy rule that the first policy rule intersects, and whether the minimum value of every dimension of every first policy rule that intersects a subsequent policy rule is greater than the minimum value of every corresponding dimension of each subsequent policy rule that the first policy rule intersects;

producing an output signal indicating that the policy table is valid if the third determination is that every first policy rule is a subset of every subsequent policy rule that it intersects in every dimension;

producing an output signal indicating that the policy table is invalid if the third determination is that any first policy rule is not a subset of every subsequent policy rule that it intersects in every dimension;

whereby, any output signal may be used by the router to generate an appropriate action.

10. A router comprising, in combination:

at least two interfaces;

a processor;

a memory;

a policy table stored in the memory;

at least two policy rules stored in the policy table;

each policy rule having at least one dimension;

a verification routine executable by the processor (i) to make a first determination whether every dimension of any first policy rule intersects any subsequent policy rule in the policy table in every dimension, and (ii) to make a second determination whether any first policy rule that intersects a subsequent policy rule in every dimension is a subset of the subsequent policy rule in every dimension;

a signaling component that generates a signal in response to the first determination and the second determination.

11. The router of claim 10, further comprising a control component that controls at least one of the at least two interfaces in response to the first determination and the second determination.

12. A computer system for validating an n-dimensional policy table in a router comprising, in combination:

at least two interfaces;

a processor;

a memory;

a policy table stored in the memory;

at least two policy rules stored in the policy table;

each policy rule having at least one dimension;

a verification routine executable by the processor (i) to make a first determination whether every dimension of any first policy rule intersects any subsequent policy rule in the policy table in every dimension, and (ii) to make a second determination whether any first policy rule that intersects a subsequent policy rule in every dimension is a subset of the subsequent policy rule in every dimension;

a signaling component that generates a signal in response to the first determination and the second determination.

13. The computer system of claim 12, further comprising a control component that controls at least one of the at least two interfaces in response to the first determination and the second determination.