Original title:
Algoritmy pro vyhledání nejdelšího shodného prefixu
Translated title:
Longest Prefix Match Algorithms
Authors:
Sedlář, František ; Puš, Viktor (referee) ; Tobola, Jiří (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 byly popsány základní algoritmy pro vyhledání nejdelšího shodného prefixu (LPM). K již existujícím implementacím v knihovně Netbench byl přidán další algoritmus - LC Trie. Všechny algoritmy, které knihovna obsahuje, byly testovány nad reálnými množinami IPv6 prefixů. Na základě zde získaných dat byly navzájem porovnány. Dále byly sepsány skripty pro stahování prefixů z významných zdrojů na internetu a testovací skripty k jednotlivým algoritmům.
This bachelor's thesis deals with a description of basic longest prefix match (LPM) algorithms. Another algorithm - LC Trie - was added to existing implementations into the Netbench library. All the algorithms which the library includes were tested with real groups of IPv6 prefixes. They were compared on the basis of previously obtained data. Testing scripts for each of the algorithms were implemented as well as scripts for downloading groups of prefixes from significant sources on the internet.
Keywords:
binary search on intervals; binary search on prefixes; Controlled Prefix Expansion; LC Trie; longest prefix match; LPM; Lulea Compressed Trie; Shape Shifting Tree; Tree Bitmap; trie; binární vyhledávání na intervalech; binární vyhledávání na prefixech; Controlled Prefix Expansion; LC Trie; Lulea Compressed Trie; nejdelší shodný prefix; Shape Shifting Tree; Tree Bitmap; trie
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/55852