Design And Implementation Of Two-channel Pipeline IP Search Engine Based On Range Matching

In recent years,the rapid development of network technology has inevitably caused the rapid expansion of network traffic,posing new challenges to the transmission capacity of the Internet.With the breakthrough of high-speed link transmission speed such as optical fiber and interface technology,the data packet processing capability of network equipment such as routers has become the main bottleneck affecting the link transmission speed.It is mainly manifested in two aspects.First,as a core technology of routers,IP lookup must be able to respond to more and more lookup requests.Secondly,because the scale of the routing table in the backbone router has reached millions,the IP address search needs to optimize the data structure and reduce the storage case as much as possible.Although there are many papers on IP address lookup at home and abroad,few of these studies can achieve a balance among lookup speed,storage requirements,incremental update performance and scalability.This paper comes from a national ministry project and studies IP address lookup based on range matching.By converting the IP address prefix into a range interval and compressing the range interval’s endpoints,and a FRBS(Fast Range B-Tree Search)IP search algorithm is proposed based on the optimized B-Tree node data structure.The algorithm realizes the lookup of IPv4 addresses and supports dynamic routing table update.By analyzing the network protocol requirements,this paper plans a dynamic routing table,designs a FRBS IP search engine based on the FRBS IP search algorithm,and implements a dynamic IP address search.The search engine includes a receiving module,a pipelined IP lookup module and an update module.The core module is the pipelined IP lookup module,which uses a 5-stage pipeline structure to implement range matching based IP address lookup,it can reach 66.6Gbps for IPv4 lookup.At the same time,by extending the pipeline structure and adopting a 25-stage pipeline structure,the IPv4 search can reach 204.8Gbps.In this paper,five routing tables in the RIPE routing set are selected as the test routing table,and 100 k entries are randomly selected to use the FRBS IP lookup algorithm to construct the prefix segment table and FRBS table,and the function simulation and verification of the FRBS IP lookup engine are carried out.The IP lookup engine is prototyped on the XCVU-13 P platform.At a frequency of 300 MHz,for a 64 Byte Ethernet frame,its average throughput reaches 66.6Gbps,the average lookup delay is 76.68 ns,and the average update delay is 20.57 ns.The performance of the ELOP scheme is compared and analyzed.Under the same size routing table,the storage overhead of this design is reduced by 51% and 48%respectively,and the search delay is reduced by 12.2ns.At the same time,the board-level test of the pipeline expansion structure is also carried out,and its performance is analyzed according to the results.The average throughput is 204.8Gbps,and the average seek delay is 125 ns.Finally,based on UMC HPC 28 nm,the entire IP search engine is physically synthesized,with an area of 12505635.055717μm^2,128 memory blocks,a total of18874368 bit,and at-40℃,0.81 V,ss process corner,the setup margin is 0.16 ns,which meets the bandwidth requirements of 100 Gbps network switching.The FRBS IP lookup algorithm and FRBS IP lookup engine studied in this paper focus on improving the performance and scalability of IP lookup hardware,significantly improving the lookup efficiency of IP lookup,and reducing the storage requirements of routing tables.This research provides an important reference.