Fast URL lookup using parallel bloom filters

URL lookup is fundamental to numerous networking systems, including URL filters, web caches, etc. With the explosive development of the Internet, the main challenge in implementing URL lookup operation is to achieve fast lookup speed and accommodate large URL sets while keeping memory and power consumption low. This paper presents a new URL lookup scheme based on parallel Bloom Filters. It can adapt to set cardinality and perform fast longest prefix matching (LPM) with large URL sets in a highly parallel fashion. The theoretical analysis and experiments on real-life data traces show that the proposed approach leads to reduced false positive probability for up to an order of magnitude (or reduced memory and hardware logic resources with the same false positive probability guaranteed) compared with the existing methods. Moreover, the architecture can be easily mapped to the state-of-the-art FPGAs with moderate resource consumption to provide over 150 M lookups per second.