Research And Implementation Of High-Speed And Large-capacity ACL Algorithm Based On Multi-core Processor Platform

Traditional access control list lookup algorithm is difficult to meet the search requirements of router in multi-core processor platform.Linear,tree,geometric and recursive algorithms have some limitations in data structure and algorithm,which can not give full play to the parallel processing capability of multi-core processors,resulting in great waste of resources.In order to solve the limitations of the above algorithm design,this thesis proposes a parallel large capacity access control list lookup method based on SDRAM by redesigning the data organization method.This thesis analyzes the software and hardware environment of Cavium platform,expounds the debugging process of Cavium platform software,and designs and implements the algorithm on the Cavium platform.This thesis mainly includes:(1)The data structure of the access control list is reconstructed,and the relation between each table item is established by the double linked list,and it is designed into two levels structure.The structure of each table item consists of priority field,condition field part,conditional mask part,linked list pointer and pointer to the action structure pointer;The action structure of table items is composed of reference count,structure resource lock,effective bit and corresponding execution action.(2)In order to further improve the efficiency of search algorithm,the algorithm adds a fast list based on data stream keyword,called the flow table.In each flow table item,an action structure pointer is designed to record the access control list item that the data stream can match.Data packets are processed by multiple and divided into different flow table items according to different hash values,and corresponding execution actions are found according to the pointer of the structure pointer in the table entries.In order to further improve the algorithm performance and order,a default entry is added at the end of the entry,and a priority field is added.(3)The algorithm is designed and implemented based on the software and hardware environment of the Cavium platform,and the debugging process of the algorithm software environment is described in detail.The important function body ofthe algorithm is described.(4)Experiments on the router prove that the algorithm is advanced and practical.