Original title:
Vyhledání nejdelšího shodného prefixu
Translated title:
Longest Prefix Match Algorithms
Authors:
Weigner, Martin ; Puš, Viktor (referee) ; Tobola, Jiří (advisor) Document type: Master’s theses
Year:
2011
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Rychlost počítačových sítí se neustále zvyšuje. Jednou ze základních úloh, které musí síťová zařízení provádět, je vyhledávání nejdelšího shodného prefixu. Mnoho algoritmů tuto úlohu dokáže řešit, ale je nutné tuto úlohu řešit velmi rychle, a to především z toho důvodu, že se stále zvyšují přenosové rychlosti a nastupuje směrovací standard IPv6. Ten má delší adresy, a je tedy nutné vyhledávat prefixy ve větších množinách. V práci jsou popsány současné algoritmy. Ty jsou porovnány v konfrontaci s novým algoritmem HashTreeBitmap, který je v práci popsán. Na základě testů je doloženo, že tento algoritmus je schopen zvládat vysoké nároky, které jsou na něj kladeny.
The speed of computer network is increasing. One of the basic tasks which has to be solved by the network devices is longest prefix match. Many algorithms are able to solve this task but it's necessary to solve it very fast because of increasing transfer speed and the routing standard IPv6. This standard has longer addresses and it's necessary to search prefixes in much bigger sets. The thesis describes present algorithms that solve the problem. These are confronted with new algorithm HashTreeBitmap which is also described in the work. On the tests is documented that this algorithm is able to cope with high demands which are placed on it.
Keywords:
HashTreeBitmap; IPv4; IPv6; Longest prefix match; LPM; router; TCP/IP.; Trie; HashTreeBitmap; IPv4; IPv6; LPM; směrovač; TCP/IP.; Trie; Vyhledání nejdelšího shodného prefixu
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/54129