Research And Implementation Of Parallel Routing Lookup Algorithm Based On Multi-core Processor

For the high performance in the processing speed, low delay, high throughput andparallel computing, multi-core processors are rapidly applied in high-end routers. But onthe multi-core processor platform, the routing lookup algorithm becomes the bottleneck ofdata forwarding. Routing lookup algorithm based on Hash, Trie tree or segmented addressconventionally applied on single-core processor with serial data computing will easilybring about resource competition as a data bottleneck when applied in multi-coreprocessors. This paper presents a parallel routing lookup algorithm based on the dividedmulti-branch trie, makes further research and promotion on the algorithm based on theCache and flow table of processors, as well as solving the slow speed of routing lookup.First, taking the characteristics of task scheduling and parallel computing of amulti-core processor into consideration, on the foundation of the study about conventionalmulti-branch Trie tree algorithm, a SDRAM-based parallel routing lookup algorithmis isproposed, namely divided multi-branch Trie algorithm. In this algorithm, a multi-branchtrie is divided into several subtrees according to the number of processor cores, and each ofthe subtrees becomes a multi-branch trie, where prefix lookup is abolished and a method ofcomposing intermediate nodes is used. Fixed-step query is used between intermediatenodes, while binary trie is adopted in the intermediate nodes. As the lookingup is onlymade in corresponding sub-trees of each core, the competition and mutex arising fromresource sharing of multiple cores can be avoided, and low time complexity and spacecomplexity will be maintained at the same time.Second, the flow table is introduced to improve the lookup efficiency of the algorithmbased on the divided multi-branch Trie. Establish a flow table in the CPU cache that makethe routing lookup into two levels: first, look up in the flow, if it is found, then transfer thepackage according to the transfer information in the routing table; if not, then employdivided Multi-branch Trie algorithm to look up in the table of SDRAM and introduce therouting information if be found into flow table for convenience of a second lookup of thesame route. The flow table is a Hash structure while taking linked list to prevent hash collision. When the hash table is full, the routes will be eliminated using direct overwriting.Besides, in order to avoid the competition among multiple cores operating to the samerouting table entry in flow cache table, a unlocked flow table is developed, in which therouting deleting process comprises of two stages: first, invalid; second, delete.Finally, the practicability of this algorithm has been proved on high-end routers.