Design And Implementation Of A Pipelined IP Lookup Structure Based On Trie

With the emerging development of network bandwidth,the web search engine faces with great challenges.And a lot of hardware search engines are provided to meet the challenges.The most common candidate is TCAM(Ternary Content Addressable Memory).TCAM is a high speed core in routing lookup for it works parallel,so TCAM is very popular in high speed search engine.Due to the parallel property,TCAM suffers severe power dissipation.And the structure of TCAM is complex for one typical TCAM cell is made up of fourteen transistors,then the extensibility is restricted.So it is not the best candidates for next generation network.Attentions are paid to find new solutions.The combination of software and hardware to solve the problem is a good solution.And the hardware based on hash or Trie is hot.The hardware based on Trie is considered to be the best candidate for next generation search engine.In order to improve the throughput,pipeline is adopted,but the memory and traffic among pipeline are imbalanced in traditional solution.Optimized Linear Pipeline is a heuristic solution which can distribute memory balanced among different stages of pipeline,and it can achieve a high throughput of one lookup per clock cycle.But the long stage in OLP makes the search delays too long,and the OLP suffer from the risk of mapping nods incompletely.In this context,the thesis focuses on the research of Trie based on pipeline,and raised a scheme called Enhanced Optimized Linear Pipeline based on OLP scheme.At first,a new method is proposed to determine the length of prefix extension based on OLP.It can well allocated the memory among pipeline,which benefits decreasing the stage of pipeline.Second,a new mapping algorithm is proposed,then all the nodes can be mapped to the pipeline.Finally,the thesis raises a coding scheme,it makes nodes in pipeline searchable.In order to verify the feasibility of EOLP,the scheme is implemented and verified on FPGA.The result on FPGA shows,compared to OLP,the EOLP can save memory and decrease delay by 1/6,and it can map the nodes completely.Finally,it reaches the throughput of 72 Gbps based on 50 K rrc route prefix,meeting the demand in high-speed network?In the end,upon validated on FPGA,the proposed scheme is implemented in ASIC aimed at rrc routing table(the capacity is 50 K prefixes)based on Global Foundry 65 nm process,and the layout area is 3490um×3985um.The post-layout simulation shows that the throughput can reach 80 Gbps,which proves the feasibility of EOLP.