Method for performing tree based ACL lookups

• US 7,536,476 B1
• Filed: 12/22/2003
• Issued: 05/19/2009
• Est. Priority Date: 12/20/2002
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Alleyne, Brian Derek
• Primary Examiner(s): Donaghue; Larry D
• Assistant Examiner(s): Pollack; Melvin H
• Application Number:
  US10/745,067
• Time in Patent Office: 1,975 Days
• Field of Search: 709/203, 709/218, 709/225, 709/226, 709/229, 709/236, 709/238, 709/241, 709/245, 709/249, 726 11- 15, 718/105, 370/238, 370/389, 370/392, 370/395.31, 707/6, 707/7, 707/9, 707/10, 707/104.1
• US Class Current: 709/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof

Abstract

A method for performing a lookup of a packet against an access control list. In one example, the method includes receiving an access control list, partioning said list into two or more complementary sets, and for each set, forming a tree having one or more end nodes including filtering rules, and internal nodes representing decision points, thereby forming at least two trees. In one example, when a packet arrives, the two or more trees are traversed using the packet header information, wherein the decision points in the internal nodes are used to guide the packet selection down the trees to an end node.

Claims

1. A method for performing a lookup of a packet against an access control list, comprising:

receiving an access control list including a set of filtering rules;

identifying a decision point to partition the access control list into two or more complementary sets, wherein the decision point is identified such that the access control list is partitioned into nearly even groups, and wherein the decision point is identified to reduce the number of replicated filtering rules and minimizing memory utilization;

forming a tree for each complementary set, wherein the tree has one or more end nodes including a subset of filtering rules, and an internal decision node representing the decision point; and

traversing the two or more trees when a packet arrives and comparing header information from the packet against each of the two or more trees and determining a match, wherein the decision point in the internal decision nodes is used to guide the packet down the trees to an end node that includes at least one filtering rule that is included in the set of filtering rules.

2. The method of claim 1, comprising:

sequentially searching the subset of filtering rules at the end nodes to find the best match.

3. The method of claim 1, comprising:

recursively partitioning the set of filtering rules at each of the internal decision nodes.

4. The method of claim 1, comprising:

determining the tree to which a particular filtering rule belongs based on comparing the source and destination address prefix lengths.

5. The method of claim 4, further comprising:

assigning the filtering rules having source prefix lengths greater than destination prefix lengths in a first tree.

6. The method of claim 5, further comprising:

assigning the filtering rules having destination prefix lengths greater than source prefix lengths in a second tree.

7. The method of claim 1, further comprising:

determining the two or more trees to which a particular filtering rule belongs based on a particular port to which the packet is being forwarded.

8. The method of claim 1, further comprising:

determining the tree to which a particular filtering rule belongs based on the protocol associated with the packet.

9. A network device comprising:

at least one processor;

a memory in communication with the at least one processor, the memory including logic encoded in one or more tangible media for execution and when executed operable to;

receive an access control list including a set of filtering rules;

identify a decision point to partition the access control list into two or more complementary sets, wherein the decision point is identified such that the access control list is partitioned into nearly even groups, and wherein the decision point is identified to reduce the number of replicated filtering rules and minimizing memory utilization;

form a tree for each complementary set, wherein the tree has one or more end nodes including a subset of filtering rules, and an internal decision node representing the decision point; and

traverse the two or more trees when a packet arrives and comparing header information from the packet against each of the two or more trees and determining a match, wherein the decision point in the internal decision nodes is used to guide the packet down the trees to an end node that includes at least one filtering rule that is included in the set of filtering rules.

10. The network device of claim 9, further comprising logic encoded in one or more tangible media for execution and when executed operable to:

sequentially search the subset of filtering rules at the end nodes to find the best match.

11. The network device of claim 9, further comprising logic encoded in one or more tangible media for execution and when executed operable to:

recursively partition the set of filtering rules at each of the internal decision nodes.

12. The network device of claim 9, further comprising logic encoded in one or more tangible media for execution and when executed operable to:

determine the two or more trees to which a particular filtering rule belongs based on comparing the source and destination address prefix lengths.

13. The network device of claim 12, further comprising logic encoded in one or more tangible media for execution and when executed operable to:

assign the filtering rules having source prefix lengths greater than destination prefix lengths in a first tree.

14. The network device of claim 13, further comprising logic encoded in one or more tangible media for execution and when executed operable to:

assign the filtering rules having destination prefix lengths greater than source prefix lengths in a second tree.

15. The network device of claim 9, further comprising logic encoded in one or more tangible media for execution and when executed operable to:

determine the tree to which a particular filtering rule belongs based on a particular port to which the packet is being forwarded.

16. Logic encoded in one or more tangible media for execution and when executed operable to:

receive an access control list including a set of filtering rules;

identify a decision point to partition the access control list into two or more complementary sets, wherein the decision point is identified such that the access control list is partitioned into nearly even groups, and wherein the decision point is identified to reduce the number of replicated filtering rules and minimizing memory utilization;

form a tree for each complementary set, wherein the tree has one or more end nodes including a subset of filtering rules, and an internal decision node representing the decision point; and

traverse the two or more trees when a packet arrives and comparing header information from the packet against each of the two or more trees and determining a match, wherein the decision point in the internal decision nodes are used to guide the packet down the trees to an end node that includes at least one filtering rule that is included in the set of filtering rules.