Paměťově efektivní vyhledání nejdelšího shodného prefixu pro směrování ve 100 Gb/s sítích

LPM, FPGA, routing, pipelined processing

Processing of network data in current backbone networks cannot be done using general processors. Instead, it has to be done using dedicated hardware. As a part of the dissertation "Utilization of reconfigurable circuits in the area of computer networks", utilization of FPGAs for implementation of the longest prefix match (LPM) operation is examined. This work presents newly proposed memory efficient representation of prefix set extracted from routing table, which is comparable with current best solutions on sets of IPv6 prefixes and overcomes them on sets of IPv4 prefixes. Because of low memory demands of the proposed representation, it is possible to store the prefix set in fast and easily accesible on-chip memory of the FPGA, which allows to perform IP lookup with throughput of 155 Gbps.