Longest prefix matching is a well-studied problem in the context of IP-packet forwarding, an area of computational specialization where high performance with low memory impact is of the essence. Numerous specialized data structures exist for longest prefix matching in this setting, among them is Waldvogels binary search on lengths, WBSL for short. This data structure has previously been augmented with a Bloom filter to improve its performance, resulting in a new data structure: WBSL-BF. This study concerns the potential performance improvement of adding length-awareness to WBSL-BF. Performance of the augmented data structure is evaluated by recording the number of hash table accesses performed to carry out a series of queries, along with false positive rates for the Bloom filters. A test program is created to run multiple series of queries with different test configurations. The data structure is evaluated using two datasets containing prefixes from routing information base snapshots from real route collectors. The two datasets contain roughly 80000 and 900000 prefixes respectively. The results indicate that on the given datasets, augmenting the Bloom filter with length-awareness can reduce the number of hash table accesses when performing longest prefix matching by up to 44% in a best case scenario without increasing memory usage. However, the performance gain is limited in other scenarios, since the optimally configured standard Bloom filter leaves little to improve upon when applied to Waldvogels binary search on lengths.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:umu-197039 |
| Date | January 2022 |
| Creators | Brücher, Olof |
| Publisher | Umeå universitet, Institutionen för datavetenskap |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | UMNAD ; 1323 |
Page generated in 0.001 seconds