Název:
Algoritmy pro vyhledání nejdelšího shodného prefixu
Překlad názvu:
Longest Prefix Match Algorithms
Autoři:
Sedlář, František ; Puš, Viktor (oponent) ; Tobola, Jiří (vedoucí práce) Typ dokumentu: Bakalářské práce
Rok:
2011
Jazyk:
cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [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.
Klíčová slova:
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; 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
Instituce: Vysoké učení technické v Brně
(web)
Informace o dostupnosti dokumentu:
Plný text je dostupný v Digitální knihovně VUT. Původní záznam: http://hdl.handle.net/11012/55852