Research & Implementation Of High Speed Routing Lookup Algorithms

The router architecture, forwarding rate and switching capacity has became three bottlenecks in the development of network as the tremendous explosion of the traffic in Internet. This dissertation is devoted to the researches of the theory and implementation of high speed routing lookup technology according to the requirements of 863 Terabit router project. The main work of this dissertation is as follows:1. The standard of judging routing lookup algorithms is proposed and the problems of current routing lookup scheme are pointed out. This paper emphasizes on the classification and comparison of current routing lookup algorithms from the point of implementation method.2. A segmental routing lookup pipeline based on TCAM and SRAM is designed. The lookup pipeline greatly improves the efficiency of the forwarding engine by decreasing lookup time from 10 cycles to 2 or 4 cycles. The test performance report of the structure demonstrates that this scheme can support a 10Gbps port forwarding 40 bytes long packets at line-speed.3. A two-stage routing lookup scheme based on TCAM is proposed by studying the characteristic of TCAM. This scheme which makes TCAM-based routing tables more power efficient is implemented by the bit selection structure. Analyses indicated that the scheme can overcome the drawback of high power consumption of TCAM as well as improve the stability of the system, and is valuable for practical use.4. By analyzing the current updating algorithms and the hashing-based lookup algorithms,this paper presents a quick routing updating algorithm------Quick and Selective Multi-HashUpdating Agorithm based on Random Sample. The algorithm which supports both IPv4 and IPv6 protocol is implemented in the Terabit router produced by NDSC, experiment results indicate that the algorithm performance well.