An effective IP routing lookup algorithm based on network processor
Yuli Fu, Hongquan Liang, Zhenyu Liu · 2008
The speed of interconnection has grown continually in the fast developing Internet and other networks. Routing lookup has become the bottleneck of high-speed packet forwarding. Obviously, high-speed packet forwarding depends on high-speed routing lookup and update algorithms. This paper discusses Longest Prefix Match algorithm (LPM) based on the hardware structure of network processor (NP). The LPM algorithm takes multibit trie to organize routing table. Some test shows that it can implement high throughput based on NP. Then, an improved LPM lookup algorithm is presented here to speed up routing lookup. In the improved algorithm the lookup simultaneously uses 8-4-3 and 16-4-4-4-4 bits from the IP addresses and employs NP¿s resources sufficiently. This dual lookup scheme is more effective in the performance of routing update.