(Note: this is an expansion / demonstration of an article written by Yogesh Ramdoss, “ACL TCAM and LOUs in Catalyst 6500“)
In the last post, a simple ACL was presented and we could see how quickly our precious TCAM space could be consumed with very few 2-port ranges. Our switch becomes more needy when other operators are used, or when ranges include more than two ports. Let’s re-create the ACL to be used for packet classification:
ip access-list v4-NETWORK-MGMT 10 permit tcp any any gt 1024
Remember that TCAM operates on masks – so ports 1024 to 65,535 must be expanded to cover the entire range. To expand this into binary, the following masks must be created (note: the ‘-‘ character indicates that we don’t care whether the value is a one or a zero):
0000 0100 0000 0000 = 1024 !! Starting port - not included as we need all ports gt 1024 0000 0100 0000 0001 = 1025 0000 0100 0000 001- = 1026 to 1027 0000 0100 0000 01-- = 1028 to 1031 0000 0100 0000 1--- = 1032 to 1039 0000 0100 0001 ---- = 1040 to 1055 0000 0100 001- ---- = 1056 to 1087 0000 0100 01-- ---- = 1088 to 1151 0000 0100 1--- ---- = 1152 to 1279 0000 0101 ---- ---- = 1280 to 1535 0000 011- ---- ---- = 1536 to 2047 0000 1--- ---- ---- = 2048 to 4095 0001 ---- ---- ---- = 4096 to 8191 001- ---- ---- ---- = 8192 to 16383 01-- ---- ---- ---- = 16384 to 32767 1--- ---- ---- ---- = 32768 to 65535
We would expect 15 TCAM entries for this single ACE! This won’t happen in practice (covered later), but it’s important to understand how ranges expand in binary notation to see how the TCAM will be utilized. Greater than (gt) range expansion may be quickly calculated by counting the number of zeros in the 16-bit binary representation of the beginning port. For port 1024 above, we could have simplified:
0000 0100 0000 0000 !! 15 zeroes will expand to 15 TCAM entries
What about an example for less than (lt)? Consider the following:
no ip access-list v4-NETWORK-MGMT ! ip access-list v4-NETWORK-MGMT 10 permit tcp any any lt 721 !
The expansion would be as follows:
0000 0010 1101 0001 = 721 !! Starting port - not included in lt range 0000 000- ---- ---- = 0 to 511 0000 0010 0--- ---- = 512 to 639 0000 0010 10-- ---- = 640 to 703 0000 0010 1100 ---- = 704 to 719 0000 0010 1101 0000 = 720
This will give us 5 TCAM entries. Let’s check the actual utilization on the switch:
switch-9k-1# show hardware access-list resource utilization | b 0x1
...
Used Free Percent
Utilization
---------------------------------------------
Ingress L2 QOS 5 507 0.98
Ingress L2 QOS IPv4 5 0.98
switch-9k-1# show system internal access-list input entries detail
...
[0x0000:0x0000:0x0600] permit tcp 0.0.0.0/0 0.0.0.0/0 eq 720 [0]
[0x0001:0x0001:0x0601] permit tcp 0.0.0.0/0 0.0.0.0/0 range 704 719 [0]
[0x0002:0x0002:0x0602] permit tcp 0.0.0.0/0 0.0.0.0/0 range 640 703 [0]
[0x0003:0x0003:0x0603] permit tcp 0.0.0.0/0 0.0.0.0/0 range 512 639 [0]
[0x0004:0x0004:0x0604] permit tcp 0.0.0.0/0 0.0.0.0/0 range 0 511 [0]
This is exactly what we expect! To simplify the calculation for a lt range expansion, count the number of ones in the 16-bit binary representation of the starting port. Simplified:
0000 0010 1101 0001 = 721 !! 5 'ones' will give us 5 TCAM entries!
What about the TCAM utilization for a range of ports?
Here’s the “close enough” scenario discussed in the first post of this series. We now know how to quickly calculate range expansions for gt and lt operations – so this shorthand can be used to get a worst-case scenario. Let’s create a new ACL and find the worst-case scenario:
no ip access-list v4-NETWORK-MGMT ! ip access-list v4-NETWORK-MGMT 10 permit tcp any any range 721 1035
We can simplify the worst-case expansion in five steps. First, identify where the binary notation differs for each port when written in a 16-bit format. Include the first differing bit:
0000 0010 1101 0001 ! Port 721 0000 0100 0000 1011 ! Port 1035
Second, remove the duplicate bits from the beginning of the binary notation:
010 1101 0001 ! Port 721 100 0000 1011 ! Port 1035
Next, count the number of zeroes for the gt operation:
010 1101 0001 ! Port 721 (gt) has 6 zeroes in the reduced binary representation
Then, count the number of ones for the lt operation:
100 0000 1011 ! Port 1035 has 4 ones in the reduced representation
Finally, add the obtained values: 6 + 4 = 10 worst-case entries.
For all intents and purposes, we can use this value in the calculation of our TCAM requirements. However, we should also know how to calculate the precise utilization of TCAM. This can be accomplished by performing both the ‘ge’ and ‘le’ (these operators don’t exist, but we need to include the beginning and end ports in the calculation) expansions and then removing the duplicates. Let’s do that, beginning with the low port number and stopping at the highest range which will overlap the high port number:
0000 0010 1101 0001 = 721 0000 0010 1101 001- = 722 to 723 0000 0010 1101 01-- = 724 to 727 0000 0010 1101 1--- = 728 to 735 0000 0010 111- ---- = 736 to 767 0000 0011 ---- ---- = 768 to 1023 0000 01-- ---- ---- = 1024 to 2047
Now move to the high port and expand downward:
0000 0100 0000 10-- = 1035 to 1032 0000 0100 0000 0--- = 1031 to 1024 0000 00-- ---- ---- = 1023 to 0
There are the 10 “worst-case” entries. Are there any overlapping masks? If we look at the expansion of the low port, we see the last range includes ports from 1024 to 2047. The target port is 1035, so this overshoots the target. Can we get rid of that? Let’s look at the expansion of the high port. The last range covered from ports 0 to 1023, which overshoots the low target. If we remove those two entries, we can see that all ports will be covered with no overlap, as the upward expansion of the low port will end at 1023 and the downward expansion of the high port ends at 1024. This removes two TCAM entries, so the exact count should be 8 (10 worst cast – 2 overlapping entries = 8 TCAM entries). We expect to see the following in the TCAM entries:
0000 0100 0000 10-- = 1032 to 1035 0000 0100 0000 0--- = 1024 to 1031 0000 0011 ---- ---- = 768 to 1023 0000 0010 111- ---- = 736 to 767 0000 0010 1101 1--- = 728 to 735 0000 0010 1101 01-- = 724 to 727 0000 0010 1101 001- = 722 to 723 0000 0010 1101 0001 = 721
And we can verify on the switch:
switch-9k-1# show system internal access-list input entries detail ... [0x0000:0x0000:0x0600] permit tcp 0.0.0.0/0 0.0.0.0/0 range 1032 1035 [0] [0x0001:0x0001:0x0601] permit tcp 0.0.0.0/0 0.0.0.0/0 range 1024 1031 [0] [0x0002:0x0002:0x0602] permit tcp 0.0.0.0/0 0.0.0.0/0 eq 721 [0] [0x0003:0x0003:0x0603] permit tcp 0.0.0.0/0 0.0.0.0/0 range 722 723 [0] [0x0004:0x0004:0x0604] permit tcp 0.0.0.0/0 0.0.0.0/0 range 724 727 [0] [0x0005:0x0005:0x0605] permit tcp 0.0.0.0/0 0.0.0.0/0 range 728 735 [0] [0x0006:0x0006:0x0606] permit tcp 0.0.0.0/0 0.0.0.0/0 range 736 767 [0] [0x0007:0x0007:0x0607] permit tcp 0.0.0.0/0 0.0.0.0/0 range 768 1023 [0]
If we had used the worst-case calculation for TCAM carving, you can see that we would still be safely within the allocated memory. In the next post, I’ll cover scenarios involving source and destination pairs as well as Logical Operation Units (LOUs)