Access control list processing in hardware

• US 6,377,577 B1
• Filed: 06/30/1998
• Issued: 04/23/2002
• Est. Priority Date: 06/30/1998
• Status: Expired due to Term

• Current Assignee: Cisco Systems, Inc.
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cheriton, David R., Bechtolsheim, Andreas V.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Duong, Frank
• Application Number:
  US09/108,071
• Time in Patent Office: 1,393 Days
• Field of Search: 370/392, 370/393, 370/394, 370/396, 370/397, 370/398, 370/399, 370/400, 370/389, 370/395.32, 709/220, 709/221, 709/222, 709/227, 709/228, 709/229
• US Class Current: 370/392
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/101 Access control lists [ACL]

Abstract

The invention provides for hardware processing of ACLs and thus hardware enforcement of access control. A sequence of access control specifiers from an ACL are recorded in a CAM, and information from the packet header is used to attempt to match selected source and destination IP addresses or subnets, ports, and protocols, against all the ACL specifiers at once. Successful matches are input to a priority selector, which selects the match with the highest priority (that is, the match that is first in the sequence of access control specifiers). The specified result of the selected match is used to permit or deny access for the packet without need for software processing, preferably at a rate comparable to wirespeed. The CAM includes an ordered sequence of entries, each of which has an array of ternary elements for matching “0”, “1”, or any value, and each of which generates a match signal. The ACL entered for recording in the CAM can be optimized to reduce the number of separate entries in the CAM, such as by combining entries which are each special cases of a more general access control specifier. A router including the CAM can also include preprocessing circuits for certain range comparisons which have been found both to be particularly common and to be otherwise inefficiently represented by the ternary nature of the CAM, such as comparisons of the port number against known special cases such as “greater than 1023” or “within the range 6000 to 6500”.

Claims

1. A method, including the steps of maintaining a set of access control patterns in at least one associative memory;

receiving a packet label responsive to a packet, said packet label being sufficient to perform access control processing for said packet;

matching matchable information, said matchable information being responsive to said packet label, with said set of access control patterns in parallel, and generating a set of matches in response thereto, each said match having priority information associated therewith;

selecting at least one of said matches in response to said priority information, and generating an access result in response to said at least one selected match; and

making a outing-decision in response to said access result.

2. A method as in claim 1, including the step of performing at least two of said steps of receiving, matching, selecting, and making a routing decision, in parallel using a pipeline technique.

3. A method as in claim 1, wherein said access control patterns each include a bit pattern for matching and a mask pattern of bits not for matching.

4. A method as in claim 1, wherein said access control patterns each include a set of ternary elements, each representative of a logical “

0,”

logical “

1”

, or “

don'"'"'t care”

value.

5. A method as in claim 1, wherein said associative memory includes a hardware content-associative memory having a plurality of rows, each row including one of said access control patterns and one of said access results.

6. A method as in claim 1, wherein said associative memory includes a hardware content-associative memory having a plurality of rows,

each row including a bit pattern for matching and one of said access results, and

each row being associated with a pattern of bits not for matching, said set of patterns of bits not for matching being fewer than a number of said rows.

7. A method as in claim 1, wherein said associative memory includes a ternary content-associative memory.

8. A method as in claim 1, wherein said packet label includes a source IP address or subnet, a destination IP address or subnet, a source port, a destination port, a protocol specifier, or an input interface.

9. A method as in claim 1, wherein said priority information for each said access control pattern is responsive to a position of said access control pattern in a memory.

10. A method as in claim 1, wherein said priority information includes a position in said associative memory, and said step of selecting includes choosing a first one of said matches.

11. A method as in claim 1, wherein said routing decision includes a committed access rate decision.

12. A method as in claim 1, wherein said routing decision includes an administrative policy decision regarding treatment of said packet.

13. A method as in claim 1, wherein said routing decision includes determining an output interface for said packet.

14. A method as in claim 1, wherein said routing decision includes implementing a quality of service policy.

15. A method as in claim 1, wherein said routing decision includes permitting or denying access for said packet.

16. A method as in claim 1, wherein said step of generating said access result is responsive to a plurality of said at least one matches.

17. A method as in claim 1, wherein said step of matching is performed in order of constant time, whereby said step of matching is performed in time not responsive to a number of said access control patterns.

18. A method as in claim 1, wherein said steps of matching and selecting are performed at a rate exceeding 1 megapacket per second.

19. A method as in claim 1, including the step of making a preliminary routing decision for said packet, wherein said packet routing information includes a result of said preliminary routing decision.

20. A method as in claim 19, wherein said preliminary routing decision includes determining at least one output interface for said packet.

21. A method as in claim 19, wherein said packet routing information includes an output interface for said packet.

22. A method as in claim 1, including the step of preprocessing said packet label to generate said matchable information.

23. A method as in claim 22, wherein said step of preprocessing includes the steps of

performing an arithmetic, logical, or comparison operation on said packet label;

and

generating a bit string for said matchable information in response to said arithmetic, logical, or comparison operation.

24. A method as in claim 22, wherein said step of preprocessing includes the step of comparing a field of said packet label with an arithmetic range or mask value.

25. A method as in claim 22, wherein said step of preprocessing includes the step of comparing a source IP port value or a destination IP port value with a selected port value.

26. A method as in claim 1, including the step of postprocessing said selected match to generate said access result.

27. A method as in claim 26, wherein said step of postprocessing includes accessing a memory in response to a bitstring included in said selected match.

28. A method as in claim 1, wherein said set of access control patterns is responsive to a sequence of access control specifiers, each one of said sequence of access control specifiers declaring whether to permit or deny access for a set of packets.

29. A method as in claim 28, wherein said step of maintaining includes the steps of

receiving said sequence of access control specifiers;

translating said sequence of access control specifiers into said sequence of access control patterns; and

storing said sequence of access control patterns in said associative memory.

30. A method as in claim 29, wherein said step of translating includes the step of generating a plurality of said access control patterns in response to one of said access control specifiers.

31. A method as in claim 29, wherein said step of translating includes the step of generating a single one of said access control patterns in response to a plurality of said access control specifiers.