Problem Statement
A popular task in CCIE-level scenarios requires creating an access-list matching a set of prefixes using the minimum number of access-list entries. Typically, such scenarios were relatively easy, so figuring out a combination of subnet prefix and wildcard mask was more or less intuitive. However, a good question would be if there exist a generic algorithm for constructing such “minimal” access-lists. To give you a better feel of the problem, let’s start with an example. Look at the following access-list matching nine different subnets:ip access-list standard TEST permit 138.0.0.0 permit 170.0.0.0 permit 177.0.0.0 permit 185.0.0.0 permit 204.0.0.0 permit 205.0.0.0 permit 206.0.0.0 permit 207.0.0.0 permit 234.0.0.0
Could this SAME filtering logic be implemented with a smaller number of ACL Entries (ACEs)? In fact, if you try the common approach and write all non-zero octets in binary form you will get the following:
10001010 138 10101010 170 11101010 177 10110001 185 10111001 204 11001100 205 11001110 206 11001111 207 11001101 234Effectively, the only “common” bit is the highest-order one and thus a single-line matching ALL entries would look like:
ip access-list standard TEST permit 128.0.0.0 127.0.0.0However, the obvious problem is that this access-list would match 128 prefixes as opposed to the original nine prefixes. This is clearly too much of an overlap in address space. What if we try using more access-list entries, as opposed to just one? For example, let’s group octets like this:
10001010 138 10101010 170 11101010 234 -- 10110001 177 10111001 185 -- 11001100 204 11001110 206 11001111 207 11001101 205Denoting the “don’t care” bit using “x”, the three above groups could be represented as:
1xx01010 (covers 4 addresses) 1011x001 (covers 2 addresses) 110011xx (covers 4 addresses)which effectively translates in the following access-list:
ip access-list standard TEST permit 138.0.0.0 96.0.0.0 permit 177.0.0.0 8.0.0.0 permit 204.0.0.0 3.0.0.0This looks much better – in just 3 lines we covered 10 addresses. Adding a single statement “deny 202.0.0.0″ we result in a four element access-list covering all 9 original entries. This is great, but how would one figure out that “clever” grouping of network octets that results in optimum packing? In fact, this job has already being done for you in Catalyst switches.
Using Catalyst IOS ACL Manager for fun and profit
The minimization problem stated above is not simply a CCIE task. In fact, this is a very important problem of minimizing the number of a boolean function’s constructive elements that arises in the field discrete mathematics. In general, such problem is NP-complete so no optimum solution exists, only more or less effective heuristics. One notable application of boolean function minimization is optimizing the use of TCAM memory in hardware-switching platforms. The Ternary Access Control Memory is fast lookup mechanism used for the purpose of fast prefix or access-list matching. Every element of TCAM is essentially a bit vector with the values of 1,0 or “x” – the do not care bit. When you compare a given binary vector with TCAM contents, it does parallel lookup over all elements and returns all “matching” vectors. TCAM hardware is complex and expensive, so packing as much values as possible in a single TCAM vector is extremely desirable. This is what the hardware ACL manager does when you create and apply an access-list, be it for the purpose of traffic filtering or QoS classification. The manager takes all entries and tries to compress them in as little ACEs as possible with given configuration. It also attempts to merge the results with the values already stored in TCAM, so you can imagine how complex the process is. Not to mention that the resulting answer is “best-effort” and not guaranteed to be absolutely optimal, just like its always is with heuristics.Keeping this in mind, one may assume that we can get a nearly optimal ACL by creating the “suboptimal” version manually, then feeding it to the ACL manager and next peeking at the TCAM contents to see what the results are. One challenge is that TCAM hardware inspection commands could be different on various platforms, not to mention that the output may look really cryptic. However, in regards to CCIE lab, it appears that we can use the 3560 switches ACL manager feature in relatively simple manner. Here is how an algorithm may look like:
- Create the original, suboptimal access-list in the switch. Re-using our previous example:
ip access-list standard TEST permit 138.0.0.0 permit 170.0.0.0 permit 177.0.0.0 permit 185.0.0.0 permit 204.0.0.0 permit 205.0.0.0 permit 206.0.0.0 permit 207.0.0.0 permit 234.0.0.0
- Ensure no other access-lists are being applied to the switch interfaces at the moment. This includes QoS features, VLAN and port-based ACLs. The reason is to avoid any extra output from TCAM memory and prevent potential additional merges. Select or create an active IP interface – port or SVI that is in up/up state and has an IP address assigned. Apply the access-list created above to the interface:
3560: interface FastEthernet 0/1 no switchport ip address 10.0.0.1 255.255.255.0 ip access-group TEST in
- Dump the contents of TCAM memory and match just the L3 Source address/Mask output:
SW1#show platform tcam table acl detail | inc l3Source l3Source: 00.00.00.00 00.00.00.00 l3Source: 00.00.00.00 00.00.00.00 l3Source: 8A.00.00.00 DF.FF.FF.FF l3Source: B1.00.00.00 F7.FF.FF.FF l3Source: CC.00.00.00 FC.FF.FF.FF l3Source: EA.00.00.00 FF.FF.FF.FF
Only look for the non-zero outputs. In our case, we end up with FOUR non-empty elements, where the first numeric column stands for the source address and the second one for the source mask. Effectively, this translates into the octets and mask in an access-list. However, bear in mind that the mask in this output has “reverse” meaning: a bit value of 1 means “care” while a bit value of “0″ means do not care. Therefore, in order to get the actual ACL wildcard mask octet you need to subtract this value from 255 or 0xFF. Here is what we get:
Subnet: 0x8A = 138, Mask: 0xFF-0xDF = 0x20 = 32; ACE: permit 138.0.0.0 32.0.0.0 Subnet: 0xB1 = 177, Mask: 0xFF-0xF7 = 0x08 = 08; ACE: permit 177.0.0.0 8.0.0.0 Subnet: 0xCC = 204, Mask: 0xFF-0xFC = 0x03 = 03; ACE: permit 204.0.0.0 3.0.0.0 Subnet: 0xEA = 234, Mask: 0xFF-0xFF = 0x00 = 00; ACE: permit 234.0.0.0 0.0.0.0 The final ACL would look like: ip access-list standard TEST permit 138.0.0.0 32.0.0.0 permit 177.0.0.0 8.0.0.0 permit 204.0.0.0 3.0.0.0 permit 234.0.0.0 0.0.0.0
This list has four elements, just like the one we created before, but this time it features only permit entries. And the resulting ACL is as optimum as the heuristic permits – maybe not the best one, but at least the best shot that the algorithm may give.
What about route summarization?
Minimizing access-list looks very similar to the procedure we know as route summarization. Although normally our manual summaries result in address space overlap, what if we want to summarize prefixes so that they don’t overlap any unnecessary address space? Look at the example presented in A Simple IPv4 Prefix Summarization Procedure. The example calls for summarizing the following prefixes:192.168.100.0/22 192.168.101.0/24 192.168.99.0/24 192.168.102.0/24 192.168.105.0/24 192.168.98.0/23And the resulting summary is 192.168.96.0/20. The only problem is that this summary covers as much as 2^12 addresses, while the original prefixes covered only 2^10 + 2^9 + 2^8 = 1792 or about 43% of the summary! Looking for a minimum set of summary prefixes covering the SAME address space, we may rewrite the original prefixes as access-list entries:
no ip access-list standard TEST ip access-list standard TEST permit 192.168.100.0 0.0.3.255 permit 192.168.101.0 0.0.0.255 permit 192.168.99.0 0.0.0.255 permit 192.168.102.0 0.0.0.255 permit 192.168.103.0 0.0.0.255 permit 192.168.105.0 0.0.0.255 permit 192.168.98.0 0.0.1.255and feed them to the ACL manager in the same manner we did before. What we get in result is following:
l3Source: C0.A8.64.00 FF.FF.FC.00 l3Source: C0.A8.69.00 FF.FF.FF.00 l3Source: C0.A8.62.00 FF.FF.FE.00or in decimal form (you may notice that the TCAM masks directly translate into the subnet masks):
192.168.100.0 255.255.252.0 192.168.105.0 255.255.255.0 192.168.98.0 255.255.254.0The prefixes covering exactly the same address space as the original six prefixes! Not as short as a single /20 prefix, but much more efficient in terms of address space usage. This looks good, but let’s give ACL manager a more challenging task. For the next demonstration, we dump over 600 prefixes from a BGP table of an Internet router. Using a simple script we convert them to an access-list here: Converted Access List and feed it to the switch using the same technique as previously. The resulting TCAM elements are saved here: TCAM Contents, and as we can see, we saved about 38% off the initial set of prefixes. And no extra address space overlap!
No comments:
Post a Comment