Original title: Grafická demonstrace vybraného algoritmu pro vyhledání směru
Translated title: Graphical Demonstration of Selected Route Lookup Algorithm
Authors: Ohrádka, Marek ; Kaštil, Jan (referee) ; Puš, Viktor (advisor)
Document type: Bachelor's theses
Year: 2009
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tato bakalářská práce se zabývá problematikou směrování v IP sítích, popisuje různé směrovací protokoly. Ukazuje možná řešení vyhledávání nejdelšího shodného prefixu, výhody a nevýhody jednotlivých řešení. Popisuje strukturu trie a její varianty. Detailně popisuje strukturu shape shifting trie, metodu jejího vytváření a způsob průchodu touto strukturou - vyhledávací algoritmus SST. Popisuje návrh a implementaci aplikace, která graficky demonstruje průběh vyhledávání v datové struktuře SST. Popisuje dekompozici problému a způsob jejího řešení v implementaci. This bachelor's thesis deals with IP routing and different routing protocols. It describes different solutions of the longest prefix matching, advantages and disadvantages of different approaches. Shows the concept of the trie data structure and its alternatives. Describes the Shape Shifting Trie data structure in detail, as well as process of its creation and the way of traversing the nodes in SST route lookup algorithm. At last, application design and implementation is described. Main purpose of the application is to graphically demonstrate the function of SST route lookup algorithm. This thesis shows decomposition approach to this task, describes major problems and its solution.
Keywords: algorithm graphical demonstration; binary trie; longest prefix match; route lookup; shape shifting trie; SST; trie; binary trie; grafická demonstrace algoritmu; shape shifting trie; SST; trie; vyhledáni cesty; vyhledáni 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/54691

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


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