AbstractsComputer Science

The rapid growth of internet traffic and the eminent shift from IPv4 to IPv6 addresses indicated the need for an efficient address lookup method that can keep pace with the ever-increasing throughput demands. As current address lookup solutions tend to become the bottleneck in internet routing, the efficient Range Trie address lookup method was designed for a hardware implementation in this thesis. A complete Range Trie hardware design was derived that is parameterizable in many of its aspects. The proposed design offers the required properties of low latency, high throughput and low memory requirements, while these properties scale well with the increase of the address width and/or the lookup table size. After implementing the Range Trie using 90nm ASIC process, an operating frequency of 540MHz up to 694MHz was achieved for IPv4 addresses, depending on the lookup table size (256-512K entries). For IPv6, the throughput was sustained between 442MHz up to 571MHz. For both IPv4 and IPv6, an OC-3072 (160Gbps) wire speed is supported for the worst-case of 512K ranges. The memory requirements ranged from a few KBytes up to 24 MBytes, while the occupied area ranged from 0.014 cm2 up to 4.64 cm2 and the power consumption ranged from 0.2 W up to 31 W depending on the address width (32, 64 or 128-bits) and the lookup table size (256-512K entries).