Access control listing mechanism for routers

• US 7,509,674 B2
• Filed: 10/07/2003
• Issued: 03/24/2009
• Est. Priority Date: 10/07/2003
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Sterne, Jason
• Primary Examiner(s): Parthasarathy; Pramila
• Application Number:
  US10/679,288
• Publication Number:
  US 20050076138A1
• Time in Patent Office: 1,995 Days
• Field of Search: None
• US Class Current: 726/13
• 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/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2425 for supporting services specification, e.g. SLA
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/101 Access control lists [ACL]

Abstract

A method and apparatus are provided for maintaining access control lists (ACLs) within TCAM on a line card in a data packet router, the rules being applied to incoming data packets. Each interface may be associated with multiple ACLs, and multiple interfaces may be associated with single shared ACLs. The shared ACLs include rules applicable to more than one interface. Other ACLs are specific to a particular interface. When searching for a rule to apply to an incoming data packet, the filter searches both the specific ACL and the shared ACLs associated with the interface over which the data packet arrived. Using the shared ACLs, duplication of common rules is reduced, thereby reducing the total number of rules stored on the line card and saving memory storage space. The invention is also applicable to sets of rules other than ACLs.

Claims

1. A method of determining rules to be applied to a data packet arriving at a first interface within a data packet router, comprising the steps of:

associating at least two sets of rules with the first interface, at least one of the sets of rules being a shared set of rules also associated with a second interface, wherein Ternary Content Addressable Memory (TCAM) storage space is saved by storing the shared set of rules in a first Access Control List (ACL);

storing a set of rules specific to only the first interface in a second ACL;

determining a key of the data packet;

searching both the first ACL and the second ACL to determine at least one rule matching the key; and

applying an action associated with the key-matching rule to the data packet.

2. The method of claim 1 wherein the step of associating at least two sets of rules with the first interface includes associating at least one set of rules with the first interface alone.

3. The method of claim 1 wherein the data packet is an internet protocol (IP) packet, wherein the interface is located within a router, and wherein the step of associating at least two sets of rules with the first interface comprises associating at least two access control lists (ACLs) with the first interface.

4. The method of claim 3 wherein each rule has an associated action, each associated action being one of packet denial, packet allowance, packet counting, and packet copying.

5. The method of claim 3 wherein the key is determined from information contained within a header of the IP packet.

6. The method of claim 5 wherein the information from which the key is determined includes at least one of an IP source address, an IP destination address, a protocol number, a Transmission Control Protocol/User Datagram Protocol (TCP/UDP) source port, a TCP/UDP destination port, and an Internet Control Message Protocol code.

7. The method of claim 1 wherein the step of searching the at least two sets of rules comprises the steps of:

determining a priority order for the at least two sets of rules; and

searching for a rule matching the key in the at least two sets of rules in an order matching the priority order.

8. A method of providing security in a data packet router at which a data packet arrives at a first interface, comprising the steps of:

associating at least two sets of rules with the first interface, at least one of the sets of rules being a shared set of rules also associated with a second interface, each rule in the at least two sets of rules having an associated action, wherein Ternary Content Addressable Memory (TCAM) storage space is saved by storing the shared set of rules in a first Access Control List (ACL);

storing a set of rules specific to only the first interface in a second ACL;

determining a key of the data packet;

searching both the first ACL and the second ACL for at least one rule matching the key; and

when at least one rule matching the key is found, applying the action associated with the key-matching rule to the data packet.

9. The method of claim 8 wherein the step of associating at least two sets of rules with the first interface includes associating at least one set of rules with the first interface alone.

10. The method of claim 8 wherein the data packet is an internet protocol (IP) packet, wherein the interface is located within a router, and wherein the step of associating at least two sets of rules with the first interface comprises associating at least two access control lists (ACLs) with the first interface.

11. The method of claim 10 wherein each associated action is one of packet denial, packet allowance, packet counting, and packet copying.

12. The method of claim 10 wherein the key is determined from information contained within a header of the IP packet.

13. The method of claim 12 wherein the information from which the key is determined includes at least one of an IP source address, an IP destination address, a protocol number, a Transmission Control Protocol/User Datagram Protocol (TCP/UDP) source port, a TCP/UDP destination port, and an Internet Control Message Protocol code.

14. The method of claim 8 wherein the step of searching the at least two sets of rules comprises the steps of:

determining a priority order for the at least two sets of rules; and

searching for a rule matching the key in the at least two sets of rules in an order matching the priority order.

15. A line card comprising:

a first interface;

a second interface;

a first set of rules specific to only the first interface;

a second set of rules shared by the first interface and the second interface;

wherein Ternary Content Addressable Memory (TCAM) storage space is saved by storing the second set of rules in a first Access Control List (ACL) and by storing the first set of rules in a second ACL,

means for searching both the first ACL and the second ACL to determine at least one rule applicable to individual data packets arriving at the first interface; and

applying an action associated with the at least one rule to the data packets.

16. The line card of claim 15 wherein the first set of rules and the second set of rules are Access Control Lists (ACLs).

17. The line card of claim 15 wherein the first set of rules is associated with only the first interface.

18. The line card of claim 17 further comprising:

a third interface; and

a third set of rules associated with the first interface and with the second interface; and

wherein the means for searching for at least one rule specific to individual data packets arriving at the first interface further comprises searching the third set of rules for such a rule.

19. The line card of claim 15 further comprising

means for associating the first set of rules and the second set of rules to the first interface according to a priority order, and

wherein the means for searching for a rule comprises searching the first set of rules and the second set of rules in the order specified by the priority order.

20. A packet switch comprising the line card of claim 15.

21. A computer-readable medium including instructions for providing security in a data packet router at which a data packet arrives at a first interface, comprising:

instructions for associating at least two sets of rules with the first interface, at least one of the sets of rules being a shared set of rules also associated with a second interface, each rule in the at least two sets of rules having an associated action, wherein Ternary Content Addressable Memory (TCAM) storage space is saved by storing the shared set of rules in a first Access Control List (ACL) and by storing a set of rules specific to the first interface in a second ACL;

instructions for determining a key of the data packet;

instructions for searching both the first ACL and the second ACL for at least one rule matching the key; and

instructions for applying the action associated with each of the at least one rule to the data packet, when at least one rule matching the key is found.