| Title | : | Applications of Approximate data structures in storage constrained untrusted distributed networks |
| Speaker | : | Prasanna Karthik V (IITM) |
| Details | : | Wed, 18 Apr, 2018 3:00 PM @ A M Turing Hall |
| Abstract: | : | Approximate data structures such as Bloom filters have been used in the past to solve various problems in distributed networks like web cache management, efficient packet routing, and performance measurement of routers. Such data structures require less storage but result in slight loss of accuracy. However, the applicability of such data structures in an untrusted environment is not straightforward. We propose a new data structure, called evidence Bloom filter (e-BF), which can be deployed in an untrusted distributed network for solving an array of problems. The first problem that we study is the measurement of quality of service (QoS) provided by a service element (e.g., webserver, firewall) in a service function chain (SFC). This problem is critical to ensure that the vendors of these service elements adhere to their Service Level Agreements. Most existing solutions for this problem assume that a majority of the service elements are trusted. Solutions for untrusted environments incur unreasonable storage and communication overheads. We propose a novel scheme, based on the e-BF, that can be deployed in an untrusted environment. The proposed solution calculates QoS based on the verifiable evidence of processing transactions provided by the service element using the e-BF. We evaluated our solution based on real traces from the website of a financial institution and multiple synthetic traces. Our solution can provide highly accurate quality measurements with 97% accuracy even in adversarial conditions, while the storage and communication overheads are minimal. |
