Research On IPv6 Route Lookup Techniques Based On Subtrie

IPv6 protocol is crucial for next generation Internet with larger size, higher performance, better scalability and capability of integrating various applications. Routers are core devices of Internet to support scalability in terms of size, performance, the deployment for new protocols and so on. With the development of Internet, continuting growthing in traffic and the size of Internet has put great challenges on backbone routers design. The 128 bits address length of IPv6 protocol also increase the pressure of router's lookup, thouth it resolves the problem of IPv4 address exhausted.Network Processor is the main part of current core routers. Its main function is packets buffering, lookup, scheduling, and forwarding and so on of router's data plane processing. But the processing element is fit for computing, and packets processing need a large number of access of external memory, which bring the problem of hard to match between memory access delay and Network Processor performance. The access number of IPv6 is severalfold of IPv4, so the hide of access delay is the main problem of Network Processor design. Preaently, Network Processor design use various parallelism technique to hide memory access delay. But due to the problem of design complexity and power, large-scale parallelism technique is difficult to continue use to over 40Gbps network process.Aiming at above problems, in this dissertation, we make comprehensive research on crucial problems of memory bottleneck in Network Processor design, and key technique of new router style MPFS (Massive Parallel Forwarding and Switching) based on FIS (Forwarding In Switching) mechanism. And we make design and realization to key techniques on MPFS prototype trial system. There are three key points in my main work and contributions of the dissertation.(1) We make comprehensive research on the memnry requirement of packets forwarding processing in Network Processor form capability, bandwidth and latency by some formulas. We point out the problem of the existing solutions, and we need a new method to resolve the problems of memory bottleneck in Network Processor design.(2) We make comprehensive research on the scalability and design complexity of new router style MPFS based on FIS mechanism. And we make comprehensive research on the key techniques of MPFS, such as partitioning FIB (Forwarding Information Base) table, constructing mapping relationship between FIB table and FSN (Forwarding and Switching Node) and routing lookup arithmetic based on subtrie.(3) We make design and realization to key techniques on MPFS prototype trial system. Mainly contain large capability FIB table partitioning which constructed based on CERNET2 real IPv6 prefix distribution, mapping the partitioned FIB table to 3 levels FSN, data structure design, routing lookup flow design, and FPGA logic design and realization. In this dissertation, we make comprehensive research on the challenges of core router and Network Processor design. We make research on the key techniques of a solution and make realize and verify on MPFS prototype trial system. Therefore the work in this dissertation possesses some theory significance and application value.