A NOVEL IP LOOKUP ALGORITHM WITH A MINIMAL PERFECT HASH FUNCTION FOR HIGH PERFORMANCE ROUTERS BASED ON NETFPGA

This thesis work shows the implementation of a new solution for the IP lookup function carried out by routers in a network. Packet forwarding in IP routers is performed according to the packet destination address which is matched, in a Longest Prefix Match(LPM) fashion, against several thousands of entries in a "Forwarding Table". This search for the Longest Prefix Match of the IP destination address is commonly referred to as IP lookup. The explosive growth of the Internet has translated into an unceasing reduction of the time-budget for packet processing and a growth of the number of entries in the Forwarding Tables, therefore this fundamental yet simple functionality has now become a critical task, which can often be the bottleneck in high performance routers. That is why a large variety of new algorithms have been presented, trying to improve the efficiency and speed of the lookup. The Algorithm here proposed is based on data structures called Blooming Trees, compact and fast techniques for membership queries. A Blooming Tree is a Bloom Filter based structure, which takes advantage of low false positive probability in order to reduce the mean number of memory accesses. The number of required memory accesses is one of the most important evaluation criterion for the quality of an algorithm for high performance routers, given that it strongly influences the mean time required for a lookup process. An array of parallel Blooming Trees accomplishes the Longest Prefix Match function for the entries of the Forwarding Table by storing the entries belonging to the 16--32 bit range. Shorter entries, intead, are stored in a very simple Direct Addressing logical block. Direct Addressing uses the address itself (in this case only the 15 most significant bits) as on offset to memory locations. Every Blooming Tree (hereafter BT) has been set up according to the MPH function, a scheme conceived to obtain memory efficient storage and fast item retrieval. The implementation platform for this algorithm is the NetFPGA board, a new networking hardware which proves to be a perfect tool for research and experimentation. It is composed of a full programmable Field Programmable Gate Array (FPGA) core, four Gigabit Ethernet ports and four banks of Static and Dynamic Random Access Memories (S/DRAM). NetFPGA has been designed as part of the Stanford University project named Clean Slate, a program which focuses on unconventional, bold, and long-term research that tries to break the network's ossification in order to improve it. This work is primarily focused on the central FPGA, where the Verilog language, an Hardware Description Language (HDL) describing directly the bit flows over the AND/OR/NOT ports, is adopted. In details, a set of static Blooming Trees structure is associated to the actual Forwarding Table and stored in fast Block on-chip RAM, while a second structure that stores the next-hop data is located onto the bigger NetFPGA SRAM. The lookup mechanism consists of a query in the BT array searching for a match and, in the case of a positive search, a query to the SRAM is performed in order to verify the matching. Since a BT always provides a non-zero false positive probability there could be an erroneous matching: in this case a new query is carried out. Finally if there is no correspondence for the searched IP address in the BT block of the algorithm, a simple Direct Addressing of the 15 most significant bits is done. A software control plane manages the algorithm, controlling the database construction and its update (adding or removing entries). In this sense the control module merges perfectly in the preexistent SCONE (Software Component of the NetFPGA)