Design and Prototype of the Range-Trie IP

Abstract

In this thesis the design and FPGA implementation of the Range Trie with Longest Prefix Match and updates is completed and prototyped in an HTX reconfigurable system. The design and its implementation is an example of hardware/software co-design and supports hardware functions controlled by software using system calls. In the case of the Range Trie, the implementation is executed in hardware and controlled by software running in a Linux environment. The proposed hardware implementation of the Range Trie is compared to the Linux routing tables in terms of performance. Distinctions are made between test sets with and without updates, insertions and deletions of possible links. Various design improvements are proposed and incorporated into a Virtex 4 FPGA. For the Range Trie support in the HTX platform a suitable hardware-software interface is proposed and developed. The proposed additions and improvements lead to a functionally correct Range Trie prototype with software support for Linux. Compared to the Linux routing tables the throughput of the hardware implementation is about 47 times higher. This makes our FPGA Range Trie design a very interesting solution to the scalability problem from which the Internet and its core and edge routers are suffering.