Bloom-filter-based Network Management Techniques

OData support
Dr. Heszberger Zalán Tamás
Department of Telecommunications and Media Informatics

With the growing demands on the quality of computer networks, network management is becoming more and more important. We can optimize network management processes with the aid of Bloom filters. Several network functions may need to determine the intersection of two separate datasets, for example during the use of network security or network management. In my thesis I look at the already existing methods to find intersections and I introduce some new ones. Based on the location of the inqury, we can separete two cases: when we want to determine the intersection on a device that does not conatin any of the datasets, so we only know the datasets’ some type of Bloom filter, or when we determine the intersection on one of the devices that holds the datasets: in this case we are familiar with all the elements of one dataset, and know a Bloom filter of the other. The datasets can have the same number of elements, or they can differ in size, both cases needing their own methodes for determining the intersection. I examined these basic cases with the use of different types of Bloom filters and methodes. To get an estimate for the intersection, I ran simulations with different parameters. My results show, that when one of the datasets are known, we can always accuratly determine the elements of the real intersection, but we also introduce false elements into the estimated intersection set. With the different intersection finding methodes, the false elements could take up from 20%, to 80% of the whole estimated set. When we perform our inqury on a third, seperate device, we can usually only find 80% of the elements of the real intersection. On the other hand, in the estimated intersection given by the used methodes, the elements of the real intersection mostly stay under 10-30%, meaning that most elements in the estimated intersection are incorrect.


Please sign in to download the files of this thesis.