Original title: Algoritmy pro vyhledání nejdelšího shodného prefixu
Translated title: Longest Prefix Match Algorithms
Authors: Kováčik, Michal ; Tobola, Jiří (referee) ; Kořenek, Jan (advisor)
Document type: Master’s theses
Year: 2012
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Táto práce je zaměřená na algoritmy pro vyhledávání nejdelšího shodného prefixu (LPM), což je klíčová operace při směrování a klasifikaci paketů v sítích TCP/IP. Spolu s potřebnou teorií je věnován prostor zhodnocení běžně používaných algoritmů s důrazem na jejich rychlost a paměťovou efektivitu. Zaměření se pak orientuje na síte IPv6, jejich typické množiny prefixů a porovnávání vhodných algoritmů. Pak je pro vybraný algoritmus navržena optimalizace a je provedena její implementace v programovacím jazyce Python. This thesis focuses on algorithms for longest prefix match (LPM), which is the key operation in packet classification and routing in TCP/IP networks. A space for analysis of commonly used algorithms with emphasis on their speed and memory efficiency is dedicated along with necessary theory. Focus is then oriented on IPv6 networks, their typical prefix sets and comparison of suitable algorithms. Afterwards, the optimization for selected algorithm is suggested and implemented in programming language Python.
Keywords: algorithm; IPv6; longest prefix match; LPM; optimization; prefix; TCP/IP; algoritmus; IPv6; LPM; nejdelší shodný prefix; optimalizace; prefix; TCP/IP

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/53714

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


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