Original title: Algoritmy pro vyhledání nejdelšího shodného prefixu
Translated title: Longest Prefix Match Algorithms
Authors: Suchodol, Jaroslav ; 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]
Práce se zabývá směrováním v IP sítích, konkrétněji otázkou zjištění nejdelšího shodného prefixu. Problematiku vyhledání nejdelšího shodného prefixu řeší mnoho sofistikovaných algoritmů. Hlavním úkolem této práce je zaměření na následující algoritmy - Controlled Prefix Expansion, Lulea Compressed Tries, Binární vyhledávání na intervalech a Binární vyhledávání na prefixech. Algoritmy jsou principiálně popsány a následně softwarově implementovány v jazyce Python. Výstup práce spočívá v analýze/porovnání jednotlivých algoritmů z hlediska paměťové náročnosti a počtu přístupů do paměti v nejhorším případě. This work deal with routing in IP networks, particularly the issue of finding the longest matched prefix. Problems of finding the longest matched prefix solves many sophisticated algorithms. The main task of this work focuses on the following algorithms - Controlled Prefix Expansion, Lulea Compressed Tries, Binary search on intervals and Binary search on prefix length. Algorithms are described and followed by software implementation in Python. Output work is the analysis/comparison of different algorithms in terms of memory consumption and number of memory accesses at worst.
Keywords: Binary search on intervals; Binary search on prefix length; Controlled Prefix Expansion; IP; Longest Prefix Match; Lulea Compressed Tries; routing; Binární vyhledávání na intervalech; Binární vyhledávání na prefixech; Controlled Prefix Expansion; IP; Lulea Compressed Tries; nejdelší shodný prefix; směrování

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/56007

Permalink: http://www.nusl.cz/ntk/nusl-573302


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses