Switches, and Internetworking Protocols, 2nd ed. (Reading, Massachusetts: Addison-Wesley, 2000). 10. A. Brodnik, S. Carlsson, M. Degermark, and S. Pink, "Small Forwarding Tables for Fast Routing Lookups," Sigcomm (1997): 3-14. 11. M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, "Scalable High-Speed IP Routing Lookups," Sigcomm (1997): 25-36. Downloaded from Digital Engineering Library @ McGraw-Hill (www.digitalengineeringlibrary.com) Copyright © 2004 The McGraw-Hill Companies. All rights reserved. Any use is subject to the Terms of Use as given at the website. CLASSIFICATION PROCESSORS CLASSIFICATION PROCESSORS 247 will be wasted. The Lulea routing table scheme provides a handy method for compressing the data in such a case by minimizing both the size of the data structure and the number of memory accesses dur- ing operation. This method is based on partitioning the data structure into three layers and a subsequent neat encoding based on bit vectors and masks. Some interesting issues arise in the binary search of prefix lengths-namely, what constitutes a good hash for every prefix length in storage and how to mini- mize the number of probes (trials). However, if it is properly designed, spectacular performance results can be attained. The Lulea algorithm data structure is a typical example of an algorithm that trades table-building (preprocessing) time (which in typical implementations takes close to 100 millisec- onds) for lookup time. Of course, this is not a reproach. Routes are not supposed to change very often SO this is a reasonable trade-off. If the Lulea classification algorithm is implemented in software to run on a 1 GHz Pentium CPU, it can be expected to run roughly at a level around 10 million lookups per second (Mlps). Worst-case lookup has been seen to take about 100 clock cycles and, more typically, 50 clock cycles. To put things into perspective, a 1 GHz CPU has a clock cycle of 1 nanosecond (10-9 seconds). Assuming that it can force one instruction per cycle through its pipeline (something