Bibliography | Steinacker, Daniel: Entwurf und Evaluierung von netzwerkbasierten Bloom-Filtern für Anwendungen zur Kontaktverfolgung. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 42 (2022). 67 pages, german.
|
Abstract | Viele Anwedungen, bei denen in kurzer Zeit festgestelltwerden muss, ob ein Element Teil einer Menge ist, setzen auf Bloom-Filter. Hier sind beispielsweise Datenbanken, Routingprotokolle und Web- Caches zu nennen. Typischerweise sind bei diesen falsch-positive Ergebnisse erlaubt, wohingegen falsch-negative nicht auftreten dürfen. Ein gezwungenerweise entstander Anwendungsfall ist die Kontaktverfolgung während einer Pandemie. Hierbei sollen die zur Kontaktverfolgung zwischen Smartphones ausgetauschten Nachrichten darauf überprüft werden, ob einer dieser Kontakte ein Ansteckungsrisiko dargestellt hat. Da je nach Größer der Population auch die Anzahl der Infizierten steigt, muss eine Vielzahl Vergleiche auf den einzelnen Endgerät durchgeführt werden. Da es sich bei den Endgeräten zumeist um Smartphones handelt, können hierdurch Nutzungseinschränkungen durch den erhöhten Energieverbrauch entstehen. Aus diesem Grund werden die Vergleiche in dem in dieser Arbeit vorgestellten System, zu einem zentralisierten System verlagert. Dieses setzt zur schnellen und platzsparenden Speicherung auf einen Bloom-Filter. Durch diesen wird außerdem gewährleistet, dass keine falsch-negativen Ergebnisse geliefert werden. Um eine weitere Verkürzung der Antwortzeiten zu erreichen, wird Netzwerkhardware verwendet, welche auf Vergleiche optimiert wurde. Zu Beginn dieser Arbeit wird eine Übersicht über die sich mit Hashbasierten und suchoptimierten Datenstrukturen beschäftigende Literatur gegeben, wobei ein besonderes Augenmerk auf Bloom- Filter gelegt wurde. Auf Basis dieser wurde ein Systemmodell eines, auf Bloom-Filtern und durch Netzwerkhardware beschleunigten, Kontaktverfolgungsdienst entworfen. Damit eine korrekte Auslegung des Dienstes möglich ist, wurden die Verläufe einer Pandemie für drei Populationen betrachtet, das Kontaktverhalten modelliert und eine Falsch-Positiv-Rate für den zu verwendenen Bloom Filter abgeleitet. Die gewonnen Erkenntnisse flossen darauf in die Entwicklung eines Lösungsansatzes und der resultierenden skalierbaren Architektur ein. Diese wurde dann in Form eines vereinfachten Proof-of-Concept implementiert und zuletzt dessen Funktion und Performanz evaluiert.
|