Reverse path forwarding protection of packets using automated population of access control lists based on a forwarding information base

• US 20050021752A1
• Filed: 08/28/2003
• Published: 01/27/2005
• Est. Priority Date: 08/10/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Warkhede, Priyank Ramesh, Marimuthu, Peram
• Granted Patent: US 7,349,382 B2
• Time in Patent Office: Days
• US Class Current: 709/225
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: H04L 63/101 Access control lists [ACL]
• CPC Class Codes: H04L 63/102 Entity profiles
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002

Abstract

Reverse path forwarding protection of packets is provided using automated population of access control lists based on a forwarding information base. One implementation identifies a lookup value by extracting one or more values including a source address from a packet. An access control list lookup operation is performed on an access control list based on the lookup value to identify a permit or a deny condition, the access control list including multiple access control list entries. The packet is processed based on the permit or the deny condition identified in by the access control list lookup operation, this processing the packet based on the permit condition includes performing a forwarding lookup operation on a representation of a forwarding information base to identify a location and forwarding the packet to the location. The access control list entries are automatically generated based on a forwarding information base.

Claims

1. A method for processing packets, the method comprising:

identifying a lookup value by extracting one or more values from a packet, said one or more values including a source address of the packet;

performing an access control list lookup operation in an access control list based on the lookup value to identify a permit or a deny condition, wherein the access control list includes access control list entries;

processing the packet based on the permit or the deny condition identified in said performing the access control list lookup operation, wherein said processing the packet based on the permit condition includes performing a forwarding lookup operation on a representation of a forwarding information base to identify a location and forwarding the packet to the location; and

automatically generating the access control list entries based on a forwarding information base.

2. The method of claim 1, wherein said automatically generating the access control list entries includes automatically generating the access control list entries based on the forwarding information base and a predefined access control list.

3. The method of claim 2, wherein said automatically generating the access control list entries includes identifying, for an entry associated with a permit condition of the predefined access control list, an intersection of the source address of the entry and addresses in the forwarding information base, and generating one or more of the access control list entries based on the intersection.

4. The method of claim 2, wherein said automatically generating the access control list entries includes identifying a plurality of deny operation entries based on the forwarding information base, the plurality of deny operations corresponding to a complement of addresses in the forwarding information base, and placing the plurality of deny operation entries before, in a search order, a plurality of predefined access control list entries corresponding to the predefined access control list;

and wherein the deny condition is generated if one of the plurality of deny operation entries is matched during said performing the access control list lookup operation.

5. The method of claim 4, wherein said identifying the plurality of deny operation entries based on the forwarding information base includes constructing a binary trie based on the forwarding information base, and traversing the binary trie to identify the plurality of deny operation entries.

6. The method of claim 2, wherein said performing the access control list lookup operation includes performing an associative memory lookup operation on an associative memory, wherein the access control list is programmed into the associative memory;

and wherein said entries automatically generated based on the forwarding information base are configured to generate a force no-hit result if matched during said performing the associative memory lookup operation to result so that the permit or deny condition is identified based on associative memory entries corresponding to the predefined access control list, and the associative memory includes one or more deny entries to generate the deny condition if none of said entries automatically generated based on the forwarding information base are matched.

7. The method of claim 2, wherein the access control list entries are automatically updated in response to a change to the forwarding information base or to the predefined access control list.

8. The method of claim 1, wherein the access control list entries are automatically updated in response to a change to the forwarding information base.

9. An apparatus for processing packets, the apparatus comprising:

means for identifying a lookup value by extracting one or more values from a packet, said one or more values including a source address of the packet;

means for performing an access control list lookup operation in an access control list based on the lookup value to identify a permit or a deny condition, wherein the access control list includes access control list entries;

means for processing the packet based on the permit or the deny condition identified in said performing the access control list lookup operation, wherein said processing the packet based on the permit condition includes performing a forwarding lookup operation on a representation of a forwarding information base to identify a location and forwarding the packet to the location; and

means for automatically generating the access control list entries based on a forwarding information base.

10. The apparatus of claim 9, wherein said means for automatically generating the access control list entries includes means for automatically generating the access control list entries based on the forwarding information base and a predefined access control list.

11. The apparatus of claim 10, wherein said means for automatically generating the access control list entries includes means for generating one or more of the access control list entries based on the intersection of an entry associated with a permit condition of the predefined access control list and addresses in the forwarding information base.

12. The apparatus of claim 10, wherein said automatically generating the access control list entries includes means for identifying a plurality of deny operation entries based on the forwarding information base, the plurality of deny operations corresponding to a complement of addresses in the forwarding information base;

wherein the plurality of deny operation entries are placed before, in a search order, a plurality of predefined access control list entries corresponding to the predefined access control list; and

wherein the deny condition is generated if one of the plurality of deny operation entries is matched during the access control list lookup operation.

13. The apparatus of claim 12, wherein said means for identifying the plurality of deny operation entries based on the forwarding information base includes means for constructing a binary trie based on the forwarding information base and for traversing the binary trie to identify the plurality of deny operation entries.

14. The apparatus of claim 10, wherein said means for performing the access control list lookup operation includes means for performing an associative memory lookup operation on an associative memory, wherein the access control list is programmed into the associative memory;

and wherein said entries automatically generated based on the forwarding information base are configured to generate a force no-hit result if matched during said performing the associative memory lookup operation to result so that the permit or deny condition is identified based on associative memory entries corresponding to the predefined access control list, and the associative memory includes one or more deny entries to generate the deny condition if none of said entries automatically generated based on the forwarding information base are matched.

15. The apparatus of claim 10, including means for automatically updating the access control list entries in response to a change to the forwarding information base or to the predefined access control list.

16. The apparatus of claim 9, including means for automatically updating the access control list entries in response to a change to the forwarding information base.

17. An apparatus comprising:

a lookup value generator configured to generate a lookup value by extracting one or more values from a packet, said one or more values including a source address of the packet;

an access control list lookup mechanism configured to perform an access control list lookup operation in an access control list based on the lookup word to identify a permit or a deny condition;

a packet processor configure to process the packet based on the permit or the deny condition identified by the access control list lookup operation, wherein said processing the packet based on the permit condition includes performing a forwarding lookup operation on a representation of a forwarding information base to identify a location and forwarding the packet to the location; and

an access control list generator configured to automatically generate entries in the access control list based on the forwarding information base.

18. The apparatus of claim 17, wherein the access control list generator automatically generates entries based on the forwarding information base and on a predefined access control list.

19. The apparatus of claim 18, wherein the access control list generator identifies, for an entry associated with a permit condition of the predefined access control list, an intersection of the source address of the entry and addresses in the forwarding information base, and generating one or more of the access control list entries based on the intersection.

20. The apparatus of claim 18, wherein the access control list generator identifies a plurality of deny operation entries based on the forwarding information base and places the plurality of deny operation entries before, in a search order, a plurality of predefined access control list entries corresponding to the predefined access control list in generating the access control list entries;

and wherein the access control list lookup mechanism generates the deny condition if one of the plurality of deny operation entries is matched during the access control list lookup operation.

21. The apparatus of claim 20, wherein the access control list generator identifies the plurality of deny operation entries based on the forwarding information base by performing operations including constructing and traversing a binary trie based on the forwarding information base.

22. The apparatus of claim 18, wherein the access control list lookup mechanism includes an associative memory;

wherein the access control list is programmed into the associative memory; and

wherein said entries automatically generated based on the forwarding information base are programmed into the associative memory in a manner to generate a force no-hit result if matched during the associative memory lookup operation so that the permit or deny condition is identified based on associative memory entries corresponding to the predefined access control list, and the associative memory includes one or more deny entries to generate the deny condition if none of said entries automatically generated based on the forwarding information base are matched.

23. The apparatus of claim 18, wherein the access control list generator updates the access control list entries in response to a change to the forwarding information base or to the predefined access control list.

24. The apparatus of claim 17, wherein the access control list generator updates the access control list entries in response to a change to the forwarding information base.

25. A computer-readable medium containing computer-executable instructions for performing steps for processing packets, said steps comprising:

identifying a lookup value by extracting one or more values from a packet, said one or more values including a source address of the packet;

performing an access control list lookup operation in an access control list based on the lookup value to identify a permit or a deny condition, wherein the access control list includes access control list entries;

processing the packet based on the permit or the deny condition identified in said performing the access control list lookup operation, wherein said processing the packet based on the permit condition includes performing a forwarding lookup operation on a representation of a forwarding information base to identify a location and forwarding the packet to the location; and

automatically generating the access control list entries based on a forwarding information base.

26. The computer-readable medium of claim 25, wherein said automatically generating the access control list entries includes automatically generating the access control list entries based on the forwarding information base and a predefined access control list.

27. The computer-readable medium of claim 26, wherein said automatically generating the access control list entries includes identifying, for an entry associated with a permit condition of the predefined access control list, an intersection of the source address of the entry and addresses in the forwarding information base, and generating one or more of the access control list entries based on the intersection.

28. The computer-readable medium of claim 26, wherein said automatically generating the access control list entries includes identifying a plurality of deny operation entries based on the forwarding information base, the plurality of deny operations corresponding to a complement of addresses in the forwarding information base, and placing the plurality of deny operation entries before, in a search order, a plurality of predefined access control list entries corresponding to the predefined access control list;

and wherein the deny condition is generated if one of the plurality of deny operation entries is matched during said performing the access control list lookup operation.

29. The computer-readable medium of claim 28, wherein said identifying the plurality of deny operation entries based on the forwarding information base includes constructing a binary trie based on the forwarding information base, and traversing the binary trie to identify the plurality of deny operation entries.

30. The computer-readable medium of claim 26, wherein said performing the access control list lookup operation includes performing an associative memory lookup operation on an associative memory, wherein the access control list is programmed into the associative memory;

and wherein said entries automatically generated based on the forwarding information base are configured to generate a force no-hit result if matched during said performing the associative memory lookup operation to result so that the permit or deny condition is identified based on associative memory entries corresponding to the predefined access control list, and the associative memory includes one or more deny entries to generate the deny condition if none of said entries automatically generated based on the forwarding information base are matched.

31. The computer-readable medium of claim 26, wherein the access control list entries are automatically updated in response to a change to the forwarding information base or to the predefined access control list.

32. The computer-readable medium of claim 25, wherein the access control list entries are automatically updated in response to a change to the forwarding information base.