Flexible Route Lookup Using Range Search
Andreas Ehliar, Dake Liu · 2005
The rising number of entries in an Internet routing table is placing higher demands route lookup engines. This paper presents a hardware implementation of a route lookup engine based on a combination of range search and linear search. The route lookup engine is constructed using a pipeline of identical search units. The lookup engine can be configured with more than one routing table allowing for simultaneous searches in more than one table. The worst case memory usage is independent of the distribution of prefixes in the routing table. Updates to the routing tables are merged together to minimize the number of updating cycles.