Efficient Storage of ACL Frequent Ranges in a Ternary Memory
AssigneeBroadcom Corporation
InventorParineeth M. REDDY
Life of this patent
Estimating the term…
Abstract
Incoming data packets are often processed according to their origination or destination port. In order to efficiently determine applicable rules based on port values, ranges are stored in association with corresponding rules in a ternary memory. In order to reduce the amount of required memory to store these ranges, extra unused bits of the ACL that includes the rule can be used. Further, to maximize the storage capability of these limited extra bits, most common ranges can be stored in one or more bit partitions depending on whether they encompass other most common ranges to be stored in the extra bits. Through partitioning and intelligent bit assignment, many ranges can be stored in the limited extra bits, and can each remain individually addressable.
Claims20
A router, comprising:
- a communication interface configured to receive a data packet;
- a TCAM module including:
- a rule memory module configured to store a plurality of rules in association with corresponding port ranges, the rule memory module having a plurality of unused bits;
- an assignment module configured to encode a plurality of most commonly occurring ranges so as to occupy one or more of the plurality of unused bits, the assignment module separating the plurality of unused bits into a first virtual partition designated for a non-overlapping range from among the plurality of most commonly occurring ranges and a second virtual partition designated for an overlapping range from among the plurality of most commonly occurring ranges;
- a processor module configured to determine at least one rule applicable to the data packet;
- and
- a priority module configured to select a final rule to be applied to the data packet;
- and
- a rule execution module configured to execute the selected rule on the data packet.
A router comprising:
- a memory module configured to store a plurality of rules in association with corresponding port ranges;
- an assignment module configured to encode a plurality of most commonly occurring ranges from among the port ranges so as to occupy unused bits of the stored plurality of rules, the assignment module being configured to encode a first subset of the plurality of most commonly occurring ranges so as to each be identified by a unique bit sequence,
- wherein the assignment module is configured to separate the unused bits into a first virtual partition and a second virtual partition, and
- wherein the first subset of the plurality of most commonly occurring ranges is designated for the first virtual partition.
A method of encoding a plurality of most commonly occurring ranges in a router, comprising:
- creating a virtual first partition and a virtual second partition in a plurality of unused bits of a stored rule;
- assigning a current range to the virtual first partition or the virtual second partition depending on whether the current range encompasses a second range assigned to the first partition;
- and
- encoding ranges assigned to the first partition using a first encoding scheme and encoding ranges assigned to the second partition using a second encoding scheme.
The method of claim 15, wherein the ranges assigned to the first partition are each non-overlapping with the other ranges assigned to the first partition.
Dependencies are inferred from the claim text.