Abstract

Packet classification algorithms are increasingly being used to provide security and Quality of Service guarantees. These algorithms are usually implemented on power hungry programmable network processors, which are used in devices such as core routers and firewalls. This paper compares the energy used by five best-known algorithms Recursive Flow Classification, HiCuts, HyperCuts, Extended Grid-of-Tries with Path Compression and Tuple Space Search with Pruning. It does this by measuring the energy used to build the search structure during preprocessing for each of the five algorithms and the average energy taken to classify a packet. To do this we implemented all five algorithms in C code and used a microarchitectural power simulation tool called Sim-Panalyzer to estimate the power dissipated by the five algorithms while running on a SA1100 StrongARM RISC processor similar to the type found on many of today's programmable network processors.