One of the key design issues for the routing of IPv4 packets is to minimize the time for IP table lookup. The current bottleneck for IP routing is the need for longest prefix matching for each incoming IP packet. This task is time-consuming since it requires bit-by-bit comparison. It is not sufficient for future gigabit routing requirements. This thesis proposed a new data structure for fast table lookups and a small forwarding table size. A fast IP table lookup algorithm and its hardware design are also presented. This design is simple and can be implemented easily by pipelining. The forwarding table is small enough and it can be fit into an on-chip SRAM....[ Read more ]

One of the key design issues for the routing of IPv4 packets is to minimize the time for IP table lookup. The current bottleneck for IP routing is the need for longest prefix matching for each incoming IP packet. This task is time-consuming since it requires bit-by-bit comparison. It is not sufficient for future gigabit routing requirements. This thesis proposed a new data structure for fast table lookups and a small forwarding table size. A fast IP table lookup algorithm and its hardware design are also presented. This design is simple and can be implemented easily by pipelining. The forwarding table is small enough and it can be fit into an on-chip SRAM.

In this research project, the hardware design is modelled and simulated. The simulation results under 0.8 μm and 0.35 μm technologies show that the processor can perform near to hundred million lookups per second. With the current embedded SRAM technology, the processor should be able to support high routing speed such as OC-192 (10 Gbps) and OC-768 (40 Gbps).