oduce the classification result is infeasible economically. It then essentially breaks down the mapping task into three stages where it trades the number of memory accesses (therefore, the speed of execution) with the memory footprint. If we look at an example where S = 128 and say T = 10, instead of trying to map 2128 possible items onto 210 ones, the RFC algorithm breaks this task down to three hierarchical mappings traversing four phases: The basic idea is that the original sequence of S bits is partitioned into chunks, which are com- bined in pairs. The result is used to index into a set of tables that are usually precomputed. Combining results from previous stages and repeating the process, we advance down the sequence of mapping as just described until a final answer is obtained at the final phase. Figure 13.6 illustrates this principle. RFC has been shown to perform 31.25 Mpps classification using a three-stage pipeline with two 4Mb of static random access memory (SRAM) and four banks of 64Mb synchronous dynamic random acess memory (SDRAM) under a clock of 125 MHz. A fully dedicated 333 MHz Pentium running RFC in software achieves a little more than 1 Mpps as classification performance. RFC is considered based on simulations to be capable of handling classification based on a policy database of 15,000 rules in a 10 Gbps environment, if implemented in hardware. It is estimated that it can do the same for a wire speed of 2.5 Gbps, if implemented in software.²¹ 14. T. V. Lakshman and D. Stiliadis, "High-Speed Policy-Based Packet Forwarding Using Efficient Multidimensional Range Matching," Proceedings of ACM Sigcomm 1998 (September 1998): 191-202. 15. P. Gupta and N. McKeown, "Packet Classification Using Hierarchical Intelligent Cuttings," IEEE Micro 20, no. 1 (January- February 2000): 34-41. This was originally presented at Hot Interconnects VII in 1999. 16. M. M. Buddhikot, S. Suri, and M. Waldvogel, "Space Decomposition Techniques for Fast Layer 4 Switching," Protocols for High Speed Networks, 66, no. 6 (Au