Ip Routing Lookup Algorithm

In recent years, more and more people use the Internet to communicate with each other, which leads to a dramatic increase in network traffic. Since 1997, network traffic and bandwidth as well as the interface rate of backbone routers doubled every six months, which results in a tremendous growth of the number of packets backbone routers forwards per second.In the forwarding process of IP router, the most important and time-consuming step is to lookup routing tables. Therefore, the fast IP routing lookup algorithm is the key to achieve high-speed packet forwarding. But the space complexity, time complexity and efficiencies are still challenging issues in the design of lookup algorithms. As a result, searching for good IP lookup algorithm is still a hot topic in literature.In this thesis, we proposed a hardware-based fast IP search algorithm, parallel prefix length speculation algorithm-PPLS, as well as its improved version - the PPLS algorithm with Trie. The major difference between our solution and traditional methods is a mechanism for speculating IP prefix length. When a packet comes, the algorithm speculates the prefix length of the destination address, based on which an accurate matching algorithm is used to make the further confirmation. Our results show that this strategy reduces the searching time and the storage space effectively.Firstly, this thesis overviews the development of IP route lookup algorithm and some related technologies. Secondly, it presents a detailed analysis of related algorithms in literature. Then we propose and discusse PPLS algorithm and its improved version, which is our major contribution. And we describe the simulation platform, and present extensive simulation results for comparison with other methods. Finally, the contribution of our work is summaried in chapter V.