Original title: Hardwarová akcelerace operace hledání nejdelšího společného prefixu
Translated title: Hardware Acceleration of Longest Prefix Match
Authors: Kekely, Lukáš ; Tobola, Jiří (referee) ; Kořenek, Jan (advisor)
Document type: Bachelor's theses
Year: 2011
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
V této bakalářské práci je popsán návrh a implementace hardwarové architektury na hledání nejdelšího shodného prefixu s ohledem na dosáhnutí rychlosti a propustnosti požadované v dnešních vysokorychlostních počítačových sítích. Zaměřuje se na IPv4 i IPv6 sítě. Navrhnutá hardwarová architektura dosahuje propustnost minimálně 75 Gbps na nejkratších IPv4 i IPv6 paketech. Výkonnost navrhnuté architektury je porovnána s výkonností zvolených, v současné době běžně používaných algoritmů. Jde konkrétně o algoritmy Tree Bitmap, Shape-Shifting Trie a Binary Search on Prefixes. Ty byly v rámci práce implementovány v jazyce C s využitím vícevláknového zpracování s ohledem na maximální využití výkonnosti dnešních vícejaderných procesorů. This bachelor's thesis describes design and implementation of hardware architecture for longest prefix match in order to achieve high throughput, which is required in today's high-speed computer networks. It is focused on IPv4 as-well-as IPv6 networks. Designed hardware architecture has throughput 75 Gbps on the shortest IPv4 and IPv6 packets.  Performance of designed architecture is also compared with performance of chosen algorithms, which are used in nowadays commercial devices. These algorithms are: Tree Bitmap, Shape-Shifting Trie and Binary Search on Prefixes. All algorithms were implemented in C language using multi-threaded processing.
Keywords: Binary Search on Prefixes; FPGA; hardware; IP address; longest prefix match; LPM; Shape-Shifting Trie; threads; TreeBitmap; Trie; Binary Search on Prefixes; FPGA; hardware; IP adresy; LPM; nejdelší shodný prefix; Shape-Shifting Trie; TreeBitmap; Trie; vlákna

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/52976

Permalink: http://www.nusl.cz/ntk/nusl-235734


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses