Survey on Routing Lookup Algorithms
路由查找算法研究综述

With rapid development of Internet,the line speed of core router has reached 2.5Gbps and even 10Gbps beyond.This speed orders core router to be able to forward ten millions of packets per second.Route lookup is an important step of packet forwarding,so high speed IP address lookup algorithm is the key component of high speed packet forwarding.IP address lookup requires a longest matching prefix search.In the last couple of years,various algorithms for high-performance IP address lookup have been proposed.In this paper,the difficulty of route lookup is analyzed,and a survey of all kinds of lookup algorithms,which are compared indetail,is also presented.At last,some challenging open problems are identified.