Research And Implementation Of Efficient Routing Scheme Based On TCAM

The rapidly development of Internet in 21 st Century results in fast increasing of Internet users.The requirement of the network speed is getting higher and higher.Researchers and carrier operators devote themselves to improve network speed and optimize network quality to meet users' requirement.The routing forward speed has greatly impact on network quality and user experience.A lot of work had been done including optimizing the routing algorithms and improving routing forward speed.Recently,TCAM,namely Ternary-Content Addressable Memory becomes an important device used in high performance routers.TCAM has great performance in routing lookup,message processing,Qo S,data compression and AI.Compared to software algorithms,the searching speed of TCAM has great advantage.However,the disadvantages of TCAM are obvious.Too expensive,high power consumption and poor performance on updating are the disadvantages of TCAM.In this context,the thesis focuses on efficient routing lookup schemes based on TCAM.A hybrid routing lookup scheme based on TCAM is proposed.Concretely,the thesis firstly gave some research on kernel routing tables from different regions.The prefixes are put into two independent TCAM cells blocks according to whether the prefix has child nodes or not,the number of child nodes and the prefix length.In this way,most prefixes are placed randomly,which the complexity of prefixes placement in TCAM is decreasing largely.The placement method decreases the unnecessary movement when updating.As a consequence,the updating efficiency is better and the power consumption is decreased.Besides,the searching speed is raised and the hardware cost is reduced because the Multi-Match Resolver(used to solve multi-match issue)is not applied in the first part of the lookup system.TCAM cells block needs to be controlled by a TCAM controller.A pipelined TCAM controller is implemented.The latency time is reduced as the pipeline technology is used.Thus,the throughout is increased.Then the controller is verified by building an UVM platform.Lastly,the controller is synthesized by SMCI 130 nm technology.The synthesis result denotes that the maximum operation frequency of the controller is 300 MHz.According to the proposed scheme,the worst movement times in an insert operation is 5 and 2 in a delete operation in this paper.Different routing tables are used in the experiment.The results of experiment show that 95% prefixes need no more than 2 movements when a prefix is inserted in the TCAM table.And all prefixes need no more than 1 movement(the worst case in delete operation is not happened).The performance on different routing tables is similar which indicated that the proposed scheme could fit different routing tables.