The Design Of IPv4/IPv6 Dual-stack Routing Lookup

With the rapid development of computer network,more and more hosts need the IP address.IPv4 address has run out in 2011.In order to solve this problem,IPv6 was put forward.But the replacement of a protocol is very complex,so the coexistence of IPv4 and IPv6 will be a long period of time.This requires that the router can be compatible with IPv4 and IPv6 dual stack protocols.The performance of the dual-stack router is largely dependent on the rate of packet forwarding,and the most important part of packet forwarding is to find the routing table,so it is the key to find routing entries quickly.The existing routing lookup algorithms both at home and abroad are studied in this thesis.The advantages and disadvantages of various algorithms and the possibility of hardware implementation are analyzed.After analyzing the distribution-characteristics of IPv4/IPv6 prefix,a group-block hardware search scheme combining level cache and level index is proposed.According to the proposed scheme,modules are designed and divided in this thesis,which mainly includes the cache module,the bloom filter module,the prefix processing module and arbitration module.In order to improve the efficiency of the index,the correlation detection mechanism of weighted values is proposed,which reduces the false positive probability of BF.In order to improve the scalability of routing lookup,the HCT storage scheme is choosed and its data structure is defined in this desiga The design module is implemented and the corresponding C language model is established in this thesis.Through the comparison with the C language model,the functional verification of the design and the design of FPGA are conpleted.The design of FPGA by Xilinx ML605 is completed in this thesis.The frequency of the whole module can reach 244.069MHz.And the lookup times per second are 22.6 million,which achieves OC-192 ports'wire-speed forwarding and satisfies IPv4/IPv6 dual-stack core routers.The results indicate that compared with the scheme of dual-stack route lookup by TCAM,the scheme of this thesis is cost-effective and supports dynamic non-blocking update,and its structure is flexible and scalable.The design of this thesis is suitable for IPv4/IPv6 dual stack router with link speed less than lOGb/s.So it has important engineering application significance.