Hardware based IP lookup table
"Diseño Lógico 2"
Instituto de Ingeniería Eléctrica - Facultad de Ingeniería
Universidad de la República
Montevideo, Uruguay
Introduction
Due to the rapid growth of computer networks, both private and the Internet, the utilization of available resources increases at the same rate. Nowadays, the bottleneck of information transport is located at the routing processing of packets, as high bandwidth links become more affordable everyday. Hence, software based implementations of lookup algorithms turn out inefficient, a situation that might become more apparent with migration to IPv6. One possible solution is to use dedicated hardware implementations of these routines, thus increasing processing speed and freeing up CPU cycles for other purposes.
Project description
This project uses a trie based algorithm, detailed at http://www.isoc.org/isoc/conferences/inet/99/
proceedings/4j/4j_2.htm. Both search and insertion of routes are covered by this work, which deals with 32-bit addresses. To arrive at a specific leaf of the trie, the addresses are analysed one nibble at a time.
The device used for implementation is the EPF10K20RC240-4 provided with Altera's UP1 Educational Board. Source code is written in VHDL, using Altera's MAX+PLUS II development software.
Performance
Circuit simulation leads to a maximum frequency of 13.75 MHz, nevertherless, satisfactory results were obtained by using a maximum test frecuency of 12.50 MHz. The following table lists the possible links the circuit can manage considering the former working frequency.
|
Type of packet |
IPv4, 4 bit prefix |
IPv6, 4 bit prefix |
IPv6, 8 bit prefix |
|
UDP, worst case1 |
374 Mbps |
170 Mbps |
330 Mbps |
|
Average length packet2 |
1.38 Gbps |
507 Mbps |
1.1 Gbps |
Notes:
1- UDP over IP over HDLC. 34 bytes minimum for IPv4, 54 bytes for IPv6.
2- 100 bytes for IPv4, 120 bytes for IPv6.
Additional information can be found in the spanish version final report.
About the authors
|
Students: |
Tutors |
|
Julio Pérez Acle, Juan Pablo Oliver Javier Rodríguez, Sebastián Fernández |