Study Of High-speed Routing Lookup Algorithm

As long as electronic applications such as e-commerce, e-banks etc are widely used on the Internet, a high-speed and high-bandwidth network will be in great demand. The network speed has already been upgraded from megabits to gigabits per second. It will be upgraded to terabits per second in the near future. Owing to the rapid changes in the network, all of the components that construct the network must also be upgraded. Routers and physical link wire are the most important components. The big breakthrough in fibre optics has guaranteed the network link speed, so high speed router has become the main bottleneck that restricts the performances of Internet.When designing a router, three critical issues must be addressed: routing lookup, packet switching and output scheduling. Some good solutions for switching and output scheduling have been developed. Therefore, routing lookup algorithm that improves the routing lookup speed is still a bottleneck of the performance of router. The main subject of this paper is to deal with this remaining issue, a fast routing lookup.During the research, the thesis closely followed the progress and the outcome in this field. This thesis first specifies the research background, introduces current high-speed routing lookup algorithms and their pros and cons. After this, we present our fast routing lookup algorithm based on binary search Tire, together with the simulation results. For it is the trend to replace IPv4 with IPv6, this thesis also show the scheme in IPv6. From the simulation results, this algorithm has good performances. At the same time, it is quite easy to implement this algorithm. So it is quite valuable.