Multibit Trie For The Longest Matching Prefix Problem

Sammanfattning:  With the ever growing forwarding tables of the internet and the large amount of traffic that flows through them, efficient algorithms to handle search are needed. One of these algorithms is the Multibit trie (prefix tree). The Multibit trie is a search trie that looks at several bits at a time, which is called a stride, to reduce the memory accesses for the algorithm. It is assumed that the trade-off for this is that the memory consumption will increase. To test this claim an implementation in python was written and two data sets with different sizes were used to build the Multibit trie. The two data sets that were used was the NY and the MAE-WEST data set. Search tests for different stride values were performed on the two data sets to get measurement of the average amount of memory accesses and the number of nodes were measured on different stride values. The results were that stride values 2 and 3 had less average memory accesses and less nodes than stride value 1. Stride value 6 had a significantly larger increase in nodes compared to its smaller stride values. It was concluded that stride value 2 and 3 did not follow the claim that the memory consumption does increase with larger stride values for these data sets. On these two data set no benefit was found for using stride value 1 compared to stride value 2 and 3. Furthermore stride value 6 was found to have a large increase in memory consumption for a minimal decrease in memory accesses.