Access control based on range-matching

• US 10,397,116 B1
• Filed: 05/05/2017
• Issued: 08/27/2019
• Est. Priority Date: 05/05/2017
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Volpe, Thomas A., Cheah, Chin
• Primary Examiner(s): Nowlin, Eric
• Application Number:
  US15/588,390
• Time in Patent Office: 844 Days
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules
• CPC Class Codes: G06F 21/79 in semiconductor storage media, e.g. directly-addressable memories
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 63/101 Access control lists [ACL]
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Disclosed are techniques that can be used within network devices to implement access control functionality. The techniques can include use of a content-addressable memory configured including an access control entry stored therein. Circuitry can be coupled to the content-addressable memory and configured to determine that a value is within a range of values. The circuitry can generate a compare key including a field that is set indicating that the value is within the range of values. The circuitry can provide, to the content-addressable memory, the compare key for locating a corresponding access control entry within the content-addressable memory. The circuitry can receive, from the content-addressable memory, an index of the access control entry stored within the content-addressable memory. The circuitry can select, based on the index of the access control entry, an action.

Claims

1. A network device, comprising:

a register memory storing indications of a range of values;

a content-addressable memory (CAM) comprising a plurality of portions, each portion comprising one or more access control entries;

memory storing actions to take on network packets;

key assembler circuitry coupled to the register memory and the CAM, the key assembler circuitry configured to;

receive data for a network packet received by the network device, the data including fields;

determine that a value of a first one of the fields is within a first numerical range;

generate a compare key including a first field corresponding to the first numerical range and a second field corresponding to a second numerical range, a first value stored in the first field indicating that the value is within the first numerical range and a second value stored in the second field indicating that the value is not within the second numerical range, the compare key having a pre-determined size; and

provide, to the CAM, the compare key to search for an access control entry in a number of portions of the plurality of portions of the CAM, the number of portions being based on the size of the compare key; and

action control circuitry coupled to the CAM and the memory storing actions, the action control circuitry configured to;

receive, from the CAM, an address of the access control entry found using the compare key;

select, using the access control entry, from the memory, one of the actions to perform on the network packet; and

perform the selected action on the network packet.

2. The network device of claim 1, wherein:

the CAM includes slices, wherein each of the slices is a portion of the plurality of portions of CAM;

the key assembly circuitry is configured to generate access control entries and provide each of the access control entries to a respective one of the slices;

each of the slices is configured to generate a respective address of an access control entry stored therein;

wherein the stored actions include sets of actions, each of the sets of actions corresponding to a respective one of the slices; and

wherein the action control circuitry is configured to select, from each of the sets of actions, a respective action based on receiving, from the corresponding slice of the CAM, an address of an access control entry stored within the corresponding slice.

3. The network device of claim 1, wherein the register memory stores a plurality of ranges of values;

and

wherein the key assembler circuitry is configured to;

determine that a value of a second one of the fields is within a second range of the plurality of ranges of values; and

generate the compare key including a bit that indicates that the value of the second one of the fields is within the second range.

4. The network device of claim 1, wherein the value comprises a bit of a bitmap and wherein each bit of the bitmap is mapped to a respective range of values stored within the register memory.

5. The network device of claim 1, wherein the range of values is a range of port numbers, a range of IP addresses, a length of a network packet, or a range of a field.

6. A device, comprising:

a content-addressable memory (CAM) comprising a plurality of access control entries, each access control entry being associated with an index and storing a value representing a numerical range;

circuitry coupled to the CAM, the circuitry configured to;

determine that an input value is within a first numerical range, the input value being related to a network packet received by the device;

generate a compare key including a first field corresponding to the first numerical range and a second field corresponding to a second numerical range, a first value stored in the first field indicating that the input value is within the first numerical range and a second value stored in the second field indicating that the input value is not within the second numerical range;

provide, to the CAM, the compare key for locating a first access control entry within the CAM that stores a value representing the first numerical range corresponding to the first field of the compare key;

receive, from the CAM, the index associated with the first access control entry; and

select, based on the index associated with the first access control entry, an action to be performed on the network packet.

7. The device of claim 6, wherein:

the CAM implements an access control list comprising a plurality of action entries, each action entry storing an action, the index associated with the first access control entry referring to a first action entry of the plurality of action entries of the access control list; and

the circuitry is further configured to;

retrieve the first action entry from the access control list based on the index;

determine the action stored in the first action entry; and

perform the action on the network packet.

8. The device of claim 7, wherein the action includes at least one of:

dropping the network packet, forwarding the network packet to a central processing unit, mirroring the network packet, setting a quality of service parameter for the network packet, setting a routing policy for the network packet, or enabling policing for the network packet.

9. The device of claim 8, wherein the compare key includes an array, the array including elements each corresponding to a respective numerical range and wherein the field is one of the elements.

10. The device of claim 9, wherein each element of the array is set to a first state indicating that a value is within the numerical range corresponding to the each element or to a second state indicating that a value is not within the numerical range corresponding to the each element.

11. The device of claim 6, wherein the CAM includes a plurality of portions;

and

wherein the circuitry is configured to;

receive, from each of the plurality of portions, an index of an access control entry stored therein; and

select, based on each index, a corresponding action.

12. The device of claim 11, wherein:

the compare key has a first size or a second size; and

the CAM is configured to;

in response to receiving the compare key having the first size, generate the index from one of the portions; and

in response to receiving the compare key having the second size, generate the index from several of the portions.

13. The device of claim 11, wherein the circuitry is configured to provide, to the CAM, the compare key for locating within a first one of the portions or within a second one of the portions, wherein:

selection of the first one of the portions or the second one of the portions is determined based on a value of a register, the selection occurring between two consecutive compare keys being provided to the CAM by the circuitry.

14. The device of claim 11, wherein the circuitry is configured to prioritize from among actions, each selected using a corresponding one of the portions, to select one action.

15. The device of claim 11, wherein the circuitry is configured to provide the compare key to each of a first set of the portions and not to a second set of the portions.

16. The device of claim 6, wherein the CAM includes a plurality of portions;

and

wherein the circuitry is configured to;

generate a first compare key including the first field that is set indicating that the input value is within the first numerical range; and

generate a second compare key including the second field that is set indicating that a second value is within second numerical range.

17. The device of claim 6, further comprising:

a register memory storing the first numerical range as a minimum value and a maximum value; and

comparison circuitry configured to;

determine that the input value is greater than or equal to the minimum value and less than or equal to the maximum value; and

in response to determining that the input value is greater than or equal to the minimum value and less than or equal to the maximum value, set the first field.

18. The device of claim 6, wherein the circuitry is configured to locate the action using the index of the first access control entry as an index into a table of actions, the action included in the actions.

19. The CAM of claim 6, wherein the circuitry is configured to search within a pre-determined subset of the plurality of access control entries of the CAM for the first access control entry based on an ingress port or an egress port of the network packet.

24. The device of claim 10, wherein the action is a first action;

wherein the index is a first index; and

wherein the CAM includes;

a second access control entry associated with a second index and storing a second value representing the second numerical range; and

a third access control entry associated with a third index and storing a third value representing a third numerical range;

wherein the circuitry is configured to;

based on the first field and the second field of the compare key, receive the second index but not the third index from the CAM; and

select a second action based on the second index.

25. The device of claim 24, wherein the circuitry is configured to prioritize the first action over the second action based on pre-determined configuration;

and

perform the first action instead of the second action on the network packet.

26. The device of claim 25, wherein the pre-determined configuration includes priority encoding, the priority encoding indicating that the second index is associated with a lower priority than the first index.

20. A method, comprising:

receiving, at a device, a network packet; and

determining, by the device, to perform an access control action on the network packet, the determining to perform the access control action including;

determining that a value corresponding to a portion of the network packet is within a first range of values;

generating a compare key for the network packet, the compare key including an array including a first element indicating that the value is within the first range of values and a second element indicating that the value is not within a second range of values, the compare key and having a pre-determined size;

locating, within a portion of content-addressable memory (CAM) of the device, an access control entry corresponding to the compare key, a size of the portion of the CAM being based on the size of the compare key;

receiving, from the CAM, an index corresponding to the access control entry; and

selecting, based on the index, the access control action.

21. The method of claim 20, further comprising:

populating the CAM with access control entries, each of the access control entries corresponding to a respective access control action, wherein the selected access control action is selected from the respective access control actions.

22. The method of claim 20, wherein:

the array includes elements each corresponding to a respective range of values; and

two of the elements are set to;

a same first state indicating that the value is within one of the ranges of values corresponding to the two of the elements;

or

a same second state indicating that the value is within both of the ranges of values corresponding to the two of the elements.

23. The method of claim 20, further comprising:

receiving, from the CAM, a plurality of indexes, each of the indexes being an index to the access control entry stored within the CAM;

determining a respective access control action for each of the plurality of indexes, wherein each respective access control action forms a plurality of access control actions; and

selecting, from the plurality of access control actions, one of the plurality of access control actions.

27. The method of claim 20, further comprising:

determining the portion of content-addressable memory (CAM) of the device based on an ingress port or an egress port of the network packet.