|
|
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
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.
|
guest ::
