• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Evaluation of length aware Bloom filter for longest prefix matching using Waldvogels binary search on lengths

Brücher, Olof January 2022 (has links)
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.

Page generated in 0.0795 seconds