Technology Behind Fast ACL Lookups
How do modern LAN switches perform ACL lookups millions of times per second? An ACL lookup is, in and out of itself, a rather simple operation: IPv4 packets adhere to a well-defined binary packet format, with fixed-size addresses always found at the same offset. Because IPv4 addresses are specified using just 4 bytes, searching for a specific address requires just a few operations when the proper data structure is used. Most algorithm-based software solutions for address lookups employ data structures called tries. (The spelling comes from the word retrieval.) In a nutshell, a trie is a tree where branching decisions are taken based on values of successive bits in the address, as Figure 16-6 shows.
Figure 16-6 Binary Search Tree
- 0000100 0000101 ... 1101111
Many different types of trees and tries exist, and optimizing the algorithms used for address lookups is an active field of computer-science research. However, it is safe to say that performing these algorithms using regular off-the-shelf processors with relatively slow memory access does not yield tens of millions of lookups per second.
The secret behind the raw speed displayed by today's LAN switches usually consists of employing either packet lookup ASICs or another type of electronic circuit, called ternary content-addressable memory (TCAM). Sometimes, the hardware architecture relies on a combination of both.
Continue reading here: Exploring TCAM
Was this article helpful?