Original title:
Algoritmy pro vyhledání nejdelšího shodného prefixu
Translated title:
Longest Prefix Match Algorithms
Authors:
Skačan, Martin ; Puš, Viktor (referee) ; Tobola, Jiří (advisor) Document type: Bachelor's theses
Year:
2010
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Tato práce se zabývá algoritmy pro vyhledání nejdelšího shodného prefixu (longest prefix match - LPM), což je klíčová operace při klasifikaci paketů a směrování v počítačových IP sítích. Je uvedena potřebná teorie a rozbor vybraných algoritmů - Trie, Tree Bitmap, Shape Shifting Tree a Multi-Match. Tyto metody byly detailně popsány a implementovány v programovacím jazyce Python. Nad implementovanými algoritmy byly provedeny testy a simulace pro určení jejich praktických paměťových nároků s cílem identifikovat nejvhodnější metodu pro množiny prefixů o velikosti desítek až tisíců pravidel.
This bachelor's thesis deals with the algorithms for longest prefix match (LPM), which is the basic operation of the packet classification and of the routing in the IP computer networks. It is introduced the necessary theory and the analysis of the chosen algorithms - Trie, Tree Bitmap, Shape Shifting Tree and Multi-match. These methods were closely described and they were implemented in the programming language Python. Within the implemented algorithms were performed tests and simulations considering their memory demands with the aim to identify the best method for prefix collections about the size of tens to thousands rules.
Keywords:
algorithm; IP; longest prefix match; LPM; multimatch; shape-shifting tree; tree bitmap; trie; algoritmus; IP; LPM; multimatch; 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/56127