Original title:
Vyhledání nejdelšího shodného prefixu
Translated title:
Longest Prefix Match Search
Authors:
Chrastina, Ondřej ; 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]
Tato práce se zabývá problémem efektivního směrování a klasifikací dat v počítačových sitích, konkrétně vyhledáním nejdelšího shodného prefixu pro síťový protokol verze 6. Jsou vybrány algoritmy Binary Trie, Level Compressed Trie, Lulea Compressed Trie a Binary Search on Intervals, které jsou nejdříve popsány a poté testovány s cílem najít nejvhodnější algoritmus z hlediska pamětových nároků a rychlosti vyhledání.
This thesis deals with the problem of an efective routing and a data clasification in computer networks, in particular searching for the longest prefix match for the internet protocol of version 6. First the algorithm, Binary Trie, Level Compressed Trie, Lulea Compressed Trie and Binary Search on Intervals, are described and then tested to find the the most suitable algorithm from the viewpoint of memory requirements and the speed of the searching.
Keywords:
algorithm; Binary Search on Intervals.; Binary Trie; IPv4; IPv6; Level Compressed Trie; Longest Prefix Match; LPM; Lulea Compressed Tries; algoritmus; Binární strom; Binární vyhledávání na intervalech.; IPv4; IPv6; Level Compressed Trie; LPM; Lulea Compressed Trie; nejdelší shodný prefix
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/55830