An Effective IP Routing lookup Algorithm based on Network Processor

摘要：

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.

关键词： Routing lookup LPM trie Network Processor

作者: Yuli Fu Hongquan Liang Zhenyu Liu

作者单位: School of Electronic and Information Engineering South China University of Technology Guangzhou 510640,China

会议类型: 国际会议

会议名称: The 11th IEEE International Conference on Communications Systems(第11届电子和电气工程师协会国际通信系统会议)(IEEE ICCS 2008)

会议地点: 广州

会议语种:英文

在线出版日期: 2008-11-19（万方平台首次上网日期，不代表论文的发表时间）