Parallel searching techniques for routing table lookup

摘要

The routing table lookup function is described, and recent research is reviewed, focusing on multiprocessor implementations. An implementation of the PATRICIA (practical algorithm to retrieve information coded in alphanumeric) radix searching algorithm on a linear pipelined array of processors is proposed. The implementation is described in detail and then evaluated in terms of the technology requirements, system performance, and robustness.