|
|
Framework for Analysis of Changes in Data Structures of Core Routers
Bednářová, Marie ; Martínek, Tomáš (referee) ; Matoušek, Jiří (advisor)
Páteřní směrovače jsou síťová zařízení, která v kontextu výkonnosti musejí držet krok s požadavky nových internetových služeb a aplikací. Jeden z faktorů, který výkonnost směrovače ovlivňuje, je klasifikační algoritmus, který je součástí procesu přeposílání příchozích paketů na základě jejich cílové IP adresy. Každá adresa je předložena Forwarding Information Base (FIB), která implementuje algoritmus Longest Prefix Matching (LPM) - hledání nejdelšího shodného prefixu. FIB tabulka obsahuje prefixy všech dosažitelných sítí z daného směrovače a na základě poskytnuté IP adresy pak rozhodne, kam daný paket dále přeposlat, aby dorazil na místo určení. Existuje několik LPM algoritmů s různými vlastnostmi, jako je rychlost vyhledávání, náročnost na paměť, náročnost na aktualizaci, a další. FIB tabulka se v průběhu provozu směrovače aktualizuje na základě změn ve Routing Information Base (RIB). Tyto změny jsou prováděny na základě směrovacích informací, které si mezi sebou směrovače vyměňují. Z těchto poznatků vychází téma této práce, které se věnuje tomu jak, dynamické jsou změny datových struktur FIB tabulek v páteřních směrovačích. Tato práce se věnuje návrhu a implementaci frameworku, který je možné použít jako pomocný nástroj pro vyhodnocování LPM algoritmů, na základě toho, jak daný algoritmus mění datové struktury FIB tabulek v páteřních směrovačích. Test je prováděn pomocí simulace, kdy LPM algoritmus je nejprve umístěn do zjednodušeného modelu směrovače jako implementace FIB tabulky. Poté, na základě zpráv protokolu BGP (Border Gateway Protocol), bude algoritmus aktualizovat datovou strukturu FIB tabulky. Celá simulace je monitorována a účinky změn jsou zaznamenávány. Na konci simulace jsou poskytnuty výsledné statistiky. Framework dále umožňuje změnit implementaci LPM algoritmu a také nastavení samotné simulace. Nakonec je funkčnost frameworku prověřena na základě experimentů.
|
|
|
Longest Prefix Match Search
Chrastina, Ondřej ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
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.
|
|
|
Roughness measurement with laser profilometry
Mach, Radoslav ; Frk, Martin (referee) ; Hejátková, Edita (advisor)
The bachelor thesis deals with technology of laser profilometry for material roughness measurements purposes. The theoretical part deals with all aspects of the issue in an effective way and highlights the essential characteristics of used components and material roughness. The focus of this work is in first step to describe the external factors affecting the visual image processing such as increasing of environment temperature and its effect for a camera sensors. And particularly the relationship between CMOS and CCD technologies. The second step is for measuring roughness parameters of materials, such as metal, wood, rubber and plastic with three different lasers. Results demonstrate correlation between the wavelengths of the used laser lights with particular materials.
|
|
|
Visualization of Longest Prefix Match Algorithms
Fomiczew, Jiří ; Matoušek, Jiří (referee) ; Kováčik, Michal (advisor)
This thesis describes the design and implementation of program for vizualization of algorithms for longest pre fix match (LPM), which is one of the most important tasks for packet classi cation and routing in TCP/IP networks. It describes necessary theory and details about selected algorithms - Trie, Tree Bitmap and CPE. Furthermore, it describes the design and implementation of program for vizualization of the search process of these algorithms with emphasis on the potential use for educational purposes. Finally, it describes the possibilities for future development and expansion of the program.
|
|
|
Longest Prefix Match Algorithms
Sedlář, František ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
This bachelor's thesis deals with a description of basic longest prefix match (LPM) algorithms. Another algorithm - LC Trie - was added to existing implementations into the Netbench library. All the algorithms which the library includes were tested with real groups of IPv6 prefixes. They were compared on the basis of previously obtained data. Testing scripts for each of the algorithms were implemented as well as scripts for downloading groups of prefixes from significant sources on the internet.
|
|
|
Longest Prefix Match Algorithms
Sedlář, František ; Matoušek, Jiří (referee) ; Tobola, Jiří (advisor)
This master's thesis explains basics of the longest prefix match (LPM) problem. It analyzes and describes chosen LPM algorithms considering their speed, memory requirements and an ability to implement them in hardware. On the basis of former findings it proposes a new algorithm Generic Hash Tree Bitmap. It is much faster than many other approaches, while its memory requirements are even lower. An implementation of the proposed algorithm has become a part of the Netbench library.
|
|
|
Longest Prefix Match Algorithms
Weigner, Martin ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
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.
|
|
|
Longest Prefix Match Algorithms
Skačan, Martin ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
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.
|
|
|
Longest Prefix Match in High-Speed Networks
Skačan, Martin ; Tobola, Jiří (referee) ; Kořenek, Jan (advisor)
This thesis deals with the Longest Prefix Matching (LPM), which is a time-critical operation in packet forwarding. To achieve 100Gbps throughput, this operation has to be implemented in hardware and a forwarding table has to fit into the on-chip memory, which is limited by its small size. Current LPM algorithms need large memory to store IPv6 forwarding tables or cannot be simply implemented in HW. Therefore we performed an analysis of available IPv6 forwarding tables and several LPM algorithms. Based on this analysis, we propose a new algorithm which is able to provide very low memory demands for IPv4/IPv6 lookups. To the best of our knowledge, the proposed algorithm has the lowest memory requirements in comparison to existing LPM algorithms. Moreover, the proposed algorithm is suitable for IP lookup in 100Gbps networks, which is shown on new pipelined hardware architecture with 140Gbps throughput.
|
|
|
Longest Prefix Match Algorithms
Kováčik, Michal ; Tobola, Jiří (referee) ; Kořenek, Jan (advisor)
This thesis focuses on algorithms for longest prefix match (LPM), which is the key operation in packet classification and routing in TCP/IP networks. A space for analysis of commonly used algorithms with emphasis on their speed and memory efficiency is dedicated along with necessary theory. Focus is then oriented on IPv6 networks, their typical prefix sets and comparison of suitable algorithms. Afterwards, the optimization for selected algorithm is suggested and implemented in programming language Python.
|
guest ::
