Publications

2024

1. DBTest

   Anatomy of the LSM Memory Buffer: Insights & Implications

   Shubham Kaushik, and Subhadeep Sarkar

   In Proceedings of the International Workshop on Testing Database Systems (DBTest), 2024

   Abs PDF

   Log-structured merge (LSM) tree is an ingestion-optimized data structure that is widely used in modern NoSQL key-value stores. To support high throughput for writes, LSM-trees maintain an in-memory buffer that absorbs the incoming entries before writing them to slower secondary storage. We point out that the choice of the data structure and implementation of the memory buffer has a significant impact on the overall performance of LSM-based storage engines. In fact, even with the same implementation of the buffer, the performance of a storage engine can vary by up to several orders of magnitude if there is a shift in the input workload.
   In this paper, we benchmark the performance of LSM-based storage engines with different memory buffer implementations and under different workload characteristics. We experiment with four buffer implementations, namely, (i) vector, (ii) skip-list, (iii) hash skip-list, and (iv) hash linked-list, and for each implementation, we vary any design choices (such as bucket count in a hash skip-list and prefix length in a hash linked-list). We present a comprehensive performance benchmark for each buffer configuration, and highlight how the relative performance of the different buffer implementations varies with a shift in input workload. Lastly, we present a guideline for selecting the appropriate buffer implementation for a given workload and performance goal.

2. DBTest

   KVBench: A Key-Value Benchmarking Suite

   Zichen Zhu, Arpita Saha, Manos Athanassoulis, and Subhadeep Sarkar

   In Proceedings of the International Workshop on Testing Database Systems (DBTest), 2024

   Abs PDF

   Key-value stores are at the core of several modern NoSQL-based data systems, and thus, a comprehensive benchmark tool is of paramount importance in evaluating their performance under different workloads. Prior research reveals that real-world workloads have a diverse range of characteristics, such as the fraction of point queries that target non-existing keys, point and range deletes, as well as, different distributions for queries and updates, all of which have very different performance implications. State-of-the-art key-value workload generators, such as YCSB and db_bench, fail to generate workloads that emulate these practical workloads, limiting the dimensions on which we can benchmark the systems’ performance.
   In this paper, we present KVBench, a novel synthetic workload generator that fills the gap between classical key-value workload generators and more complex real-life workloads. KVBench supports a wide range of operations, including point queries, range queries, inserts, updates, deletes, range deletes, and among these options, inserts, queries, and updates can be customized by different distributions. Compared to state-of-the-art key-value workload generators, KVBench offers a richer array of knobs, including the proportion of empty point queries, customized distributions for updates and queries, and range deletes with specific selectivity, constituting a significantly flexible framework that can better emulate real-world workloads.

2023

1. TODS

   Enabling Timely and Persistent Deletion in LSM-Engines

   Subhadeep Sarkar, Tarikul Islam Papon, Zichen Zhu, Dimitris Staratzis, and Manos Athanassoulis

   ACM Transactions on Database Systems, 2023

   Abs PDF

   Data-intensive applications have fueled the evolution of log-structured merge (LSM) based key-value engines that employ the out-of-place paradigm to support high ingestion rates with low read/write interference. These benefits, however, come at the cost of treating deletes as second-class citizens. A delete operation inserts a tombstone that invalidates older instances of the deleted key. State-of-the-art LSM-engines do not provide guarantees as to how fast a tombstone will propagate to persist the deletion.
   Further, LSM-engines only support deletion on the sort key. To delete on another attribute (e.g., timestamp), the entire tree is read and re-written, leading to undesired latency spikes and increasing the overall operational cost of a database. Efficient and persistent deletion is key to support: (i) streaming systems operating on a window of data, (ii) privacy with latency guarantees on data deletion, and (iii) en masse cloud deployment of data systems. Further, we document that LSM-based key-value engines perform suboptimally in presence of deletes in a workload. Tombstone-driven logical deletes, by design, are unable to purge the deleted entries in a timely manner, and retaining the invalidated entries perpetually affects the overall performance of LSM-engines in terms of space amplification, write amplification, and read performance. Moreover, the potentially unbounded latency for persistent deletes brings in critical privacy concerns in light of the data privacy protection regulations, such as the right to be forgotten in EU’s GDPR, the right to delete in California’s CCPA and CPRA, and deletion right in Virginia’s VCDPA. Toward this, we introduce the delete design space for LSM-trees and highlight the performance implications of the different classes of delete operations.
   To address these challenges, in this article, we build a new key-value storage engine, Lethe+, that uses a very small amount of additional metadata, a set of new delete-aware compaction policies, and a new physical data layout that weaves the sort and the delete key order. We show that Lethe+ supports any user-defined threshold for the delete persistence latency offering higher read throughput (1.17x-1.4x) and lower space amplification (2.1x-9.8x), with a modest increase in write amplification (between 4% and 25%) that can be further amortized to less than 1%. In addition, Lethe+ supports efficient range deletes on a secondary delete key by dropping entire data pages without sacrificing read performance or employing a costly full tree merge.

2. SIGMOD

   Acheron: Persisting Tombstones in LSM Engines

   Zichen Zhu, Subhadeep Sarkar, and Manos Athanassoulis

   In Proceedings of the ACM SIGMOD International Conference on Management of Data, 2023

   Abs PDF

   Modern NoSQL storage engines frequently employ log-structured merge (LSM) trees as their core data structures because they offer high ingestion rates and low latency for query processing. Client writes are captured in memory first and are gradually merged on disk in a level-wise manner. While this out-of-place paradigm sustains fast ingestion rates, it implements delete operations via inserting tombstones which logically invalidate older entries. Thus, obsolete data cannot be removed instantly and may be retained for an arbitrarily long time. Therefore, out-of-place deletion in LSM trees may, on the one hand, violate data privacy regulations (e.g., the right to be forgotten in EU’s GDPR, right to delete in California’s CCPA and CPRA), and on the other hand, it hurts performance.
   In this paper, we develop Acheron, which demonstrates the performance implications of out-of-place deletes and how our method achieves timely persistent deletes. We integrate both prior state-of-the-art compaction policies and our recently presented method, FADE, into Acheron and visualize the life cycle of tombstones in LSM trees. Using the Acheron visualization, users can observe that the state of the art does not provide guarantees on when obsolete entries can be physically removed and also observe that FADE can achieve timely persistent deletes without full tree compaction. Users can further customize the workload, LSM tuning knobs, and disk parameters to investigate their impact on tombstones and performance. This demonstration provides key insights into the impact of tombstones on LSM-interested researchers and practitioners.

3. ICDE

   The LSM Design Space and its Read Optimizations

   Subhadeep Sarkar, and Manos Athanassoulis

   In Proceedings of the IEEE International Conference on Data Engineering (ICDE), 2023

   Abs PDF

   Log-structured merge (LSM) trees have emerged as one of the most commonly used storage-based data structures in modern data systems as they offer high throughput for writes and good utilization of storage space. However, LSM-trees were not originally designed to facilitate efficient reads. Thus, state-of-the-art LSM engines employ numerous optimization techniques to make reads efficient. The goal of this tutorial is to present the fundamental principles of the LSM paradigm along with the various optimization techniques and hybrid designs adopted by LSM engines to accelerate reads.
   Toward this, we first discuss the basic LSM operations and their access patterns. We then discuss techniques and designs that optimize point and range lookups in LSM-trees: (i) index and (ii) filter data structures, (iii) caching, and (iv) read- friendly data layouts. Next, we present the performance tradeoff between writes and reads, outlining the rich design space of the LSM paradigm and how one can navigate it to improve query performance. We conclude by discussing practical problems and open research challenges. This will be a 1.5-hour tutorial.

4. ICDE

   Indexing for Near-Sorted Data

   Aneesh Raman, Subhadeep Sarkar, Matthaios Olma, and Manos Athanassoulis

   In Proceedings of the IEEE International Conference on Data Engineering (ICDE), 2023

   Abs PDF

   Indexing in modern data systems facilitates efficient query processing when the selection predicate is on an indexed key. As new data is ingested, indexes are gradually populated with incoming entries. In that respect, indexing can be perceived as the process of adding structure to incoming, otherwise unsorted data. Adding structure, however, comes at a cost. Instead of simply appending the incoming entries, we insert them into the index. If the ingestion order matches the indexed attribute order, the ingestion cost is entirely redundant and can be avoided altogether (e.g., via bulk loading in a B+-tree). However, classical tree index designs do not benefit when incoming data comes with an implicit ordering that is close to being sorted, but not fully sorted.
   In this paper, we study how indexes can exploit near-sortedness. Particularly, we identify sortedness as a resource that can accelerate index ingestion. We propose a new sortedness-aware (SWARE) design paradigm that combines opportunistic bulk loading, index appends, variable node fill and split factors, and an intelligent buffering scheme, to optimize ingestion and read queries in a tree index in the presence of near-sortedness. We apply SWARE to two state-of-the-art search trees (B+tree and Bε-tree), and we demonstrate that their Sortedness-Aware counterparts (SA B+-tree and SA Bε-tree) outperform their respective baselines by up to 8.8x (SA B+-tree) and 7.8x (SA Bε-tree) for a write-heavy workload in the presence of data sortedness, while offering competitive read performance, leading to overall benefits between 1.3x-5x for mixed read/write workloads with near-sorted data. Overall, we highlight that SWARE can be applied to other tree-like data structures to accelerate index ingestion and improve their performance in the presence of data sortedness.

2022

1. DEBull

   Building Deletion-Compliant Data Systems

   Manos Athanassoulis, and Subhadeep Sarkar

   IEEE Data Engineering Bulletin, 2022

   Abs PDF

   Most modern data systems have been designed with two goals in mind – fast ingestion and low-latency query processing. The first goal has led to the development of a plethora of write-optimized data stores that employ the out-of-place paradigm. Due to their write-optimized design, out-of-place data systems perform deletes logically via invalidation, and retain the invalid data for arbitrarily long. However, due to the recent enactment of new data privacy regulations, the requirement of timely deletion of user data has become central. The right to be forgotten (in EU’s GDPR), right to delete (in California’s CCPA and CPRA), or deletion right (in Virginia’s VCDPA) mandates service providers to persistently delete a user’s data within a pre-set time duration. Logical deletion in out-of-place data systems, however, does not offer guarantees for timely and persistent deletion, and attempting to enforce it using existing tools leads to poor performance and increased operational costs.
   In this paper, we present a new framework for building deletion-compliant data systems from a holistic perspective. We analyze the new regulations and the requirements derived from the new policies, and we propose changes in the application and the system layer of data management. We outline the new types of deletion requests that need to be supported, the query language modifications needed to be able to request for timely persistent data deletion, and the system-level changes needed to realize timely and persistent deletes. The proposed framework for deletion compliance lays the groundwork for a new class of data systems that can offer system-level guarantees for user data privacy. We present recent results spanning all layers of the framework: the requirements and the application layer target any database system, while the system layer discussion is geared towards out-of-place systems. Finally, we conclude with a discussion on the next steps and the open challenges on building deletion-compliant data systems.

2. EDBT

   Query Language Support for Timely Data Deletion

   Subhadeep Sarkar, and Manos Athanassoulis

   In Proceedings of the International Conference on Extending Database Technology (EDBT), 2022

   Abs PDF

   A key driver of modern data systems is the requirement for fast ingestion while ensuring low-latency query processing. This has led to the birth of write-optimized data stores that realize ingestion (inserts, updates, and deletes) in an out-of-place manner. Deletes in such out-of-place data stores are performed logically via invalidation while retaining the invalidated data for arbitrarily long. At the same time, with new policy changes, such as the introduction of the right to be forgotten (in EU’s GDPR), the right to delete (in California’s CCPA and CPRA), and the deletion right (in Virginia’s VCDPA), the importance of timely and persistent deletion of user data has become critical.
   In this paper, we point out that state-of-the-art query languages lack the necessary support to express a user’s preferences for data retention and deletion. Toward this, we first identify two classes of deletes: (i) retention-based deletion and (ii) on-demand deletion, that need to be supported for regulation compliance. Next, we present the challenges in transforming these user deletion requirements into application-level specifications. For this, we propose query language extensions that can express both on-demand and timely persistent deletion of user data. Finally, we discuss how the application and system level modifications work hand-in-hand under the privacy regulations and act as stepping stones toward designing deletion-compliant data systems.

3. SIGMOD

   Compactionary: A Dictionary for LSM Compactions

   Subhadeep Sarkar, Kaijie Chen, Zichen Zhu, and Manos Athanassoulis

   In Proceedings of the ACM SIGMOD International Conference on Management of Data, 2022

   Abs PDF

   Log-structured merge (LSM) trees are widely used as the storage layer of production NoSQL data stores, as they offer efficient ingestion performance. To enable competitive read performance and reduce space amplification, LSM-trees periodically re-organize data layout on disk iteratively, through compactions. Compactions are at the heart of every LSM-based storage engine, fundamentally influencing their performance in terms of write amplification, write throughput, point and range lookup performance, space amplification, and delete performance. However, the process of compaction in LSM-engines is often treated as a black-box that is rarely exposed as a tuning knob. In this paper, we demonstrate Compactionary, a dictionary for LSM compactions, outlining the implications of compactions on performance, and how different LSM tunings and workloads influence compactions.
   Compactionary breaks down the LSM compaction black-box, expressing compactions as an ensemble of four first-order design choices: (i) when to compact, (ii) how to organize the data after compaction, (iii) how much data to compact, and (iv) which data to compact. We configure Compactionary to demonstrate the operational flow of a family of state-of-the-art LSM compaction strategies and how each strategy influences the performance of the storage engine. The participants can (i) customize the workload, (ii) configure the LSM tuning, and (iii) switch between advanced compaction options, to understand individually the impacts of the different factors on performance. Further, to engage the interested participants, we extend the demonstration by allowing the participants (i) to create custom hybrid compaction strategies, as well as (ii) to configure the settings separately for each strategy in an individual analysis phase. The demo is available at https://disc-projects.bu.edu/compactionary/#interactiveDemo.

4. SIGMOD

   Dissecting, Designing, and Optimizing LSM-based Data Stores

   Subhadeep Sarkar, and Manos Athanassoulis

   In Proceedings of the ACM SIGMOD International Conference on Management of Data, 2022

   Abs PDF

   Log-structured merge (LSM) trees have emerged as one of the most commonly used disk-based data structures in modern data systems. LSM-trees employ out-of-place ingestion to support high throughput for writes, while their immutable file structure allows for good utilization of disk space. Thus, the log-structured paradigm has been widely adopted in state-of-the-art NoSQL, relational, spatial, and time-series data systems. However, despite their popularity, there is a lack of pedagogical textbook-like material on LSM designs. The goal of this tutorial is to present the fundamental principles of the LSM paradigm along with a digest of optimizations and new designs proposed in recent research and adopted by modern LSM engines. This will serve as introductory material for non-experts, and as a roadmap to cutting-edge LSM results for the LSM-aware researchers and practitioners.
   Toward this, we first discuss in detail the basic operations (inserts, updates, deletes, point and range queries), their access patterns and their paths through the LSM data structure. We then dive into the details of recent research on optimizing each of those operations. We first discuss techniques and designs that optimize data ingestion, and then, we discuss new data structures that optimize read queries. Finally, we present the rich design space of the log-structured paradigm and outline how to navigate it and tune LSM-based systems. We conclude with a discussion on open challenges on LSM systems. This will be a 1.5-hour tutorial.

5. TPCTC

   BoDS: A Benchmark on Data Sortedness

   Aneesh Raman, Konstantinos Karatsenidis, Subhadeep Sarkar, Matthaios Olma, and Manos Athanassoulis

   In Performance Evaluation and Benchmarking TPC Technology Conference (TPCTC), 2022

   Abs PDF

   Indexes in data systems accelerate data access by adding structure to otherwise unstructured data at the cost of index construction and maintenance. Data systems, and particularly, the underlying indexing data structures are designed to offer favorable ingestion (and query) performance for the two extremes of data sortedness, i.e., unsorted data (often assumed to follow a uniform random distribution) or fullysorted data. However, in practice, data may arrive with an intermediate degree of pre-sortedness. In such cases, where data arrives nearly (but not necessarily fully) sorted, the intuition is that the indexing cost should be lower than when ingesting unsorted data. Such sortedness-aware index designs lack from the literature. In fact, there is a need for a framework to explore how index designs may be able to exploit pre-existing sortedness during data ingestion to amortize the index construction cost.
   In this paper, we present Benchmark on Data Sortedness, BoDS for short, that highlights the performance of data systems in terms of index construction and navigation costs when operating on data ingested with variable sortedness. To quantify data sortedness, we use the stateof-the-art (K,L)-sortedness metric. Specifically, BoDS benchmarks the indexing performance of a data system as we vary the two fundamental components of the metric: (i) K, that measures how many elements are out-of-order in a data collection; and (ii) L, that measures by how much the out-of-order entries are displaced from their respective in-order positions; as well as (iii) the distribution of L. We present in detail the benchmark, and we run it on PostgreSQL, a popular, production-grade relational database system. Unsurprisingly, we observe that PostgreSQL cannot exploit data sortedness; however, through our experiments we show the headroom for improvement, and we lay the groundwork for experimentation with sortedness-aware index designs. The code for BoDS is available at: https://github.com/BU-DiSC/bods.

2021

1. PVLDB

   Constructing and Analyzing the LSM Compaction Design Space

   Subhadeep Sarkar, Dimitris Staratzis, Zichen Zhu, and Manos Athanassoulis

   Proceedings of the VLDB Endowment, 2021

   Abs PDF

   Log-structured merge (LSM) trees offer efficient ingestion by appending incoming data, and thus, are widely used as the storage layer of production NoSQL data stores. To enable competitive read performance, LSM-trees periodically re-organize data to form a tree with levels of exponentially increasing capacity, through iterative compactions. Compactions fundamentally influence the performance of an LSM-engine in terms of write amplification, write throughput, point and range lookup performance, space amplification, and delete performance. Hence, choosing the appropriate compaction strategy is crucial and, at the same time, hard as the LSM compaction design space is vast, largely unexplored, and has not been formally defined in the literature. As a result, most LSM-based engines use a fixed compaction strategy, typically hand-picked by an engineer, which decides how and when to compact data.
   In this paper, we present the design space of LSM-compactions, and evaluate state-of-the-art compaction strategies with respect to key performance metrics. Toward this goal, our first contribution is to introduce a set of four design primitives that can formally define any compaction strategy: (i) the compaction trigger, (ii) the data layout, (iii) the compaction granularity, and (iv) the data movement policy. Together, these primitives can synthesize both existing and completely new compaction strategies. Our second contribution is to experimentally analyze 10 compaction strategies. We present 12 observations and 7 high-level takeaway messages, which show how LSM systems can navigate the compaction design space.

2020

1. SIGMOD

   Lethe: A Tunable Delete-Aware LSM Engine

   Subhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis, and Manos Athanassoulis

   In Proceedings of the ACM SIGMOD International Conference on Management of Data, 2020

   Abs PDF

   Data-intensive applications fueled the evolution of log structured merge (LSM) based key-value engines that employ the out-of-place paradigm to support high ingestion rates with low read/write interference. These benefits, however, come at the cost of treating deletes as a second-class citizen. A delete inserts a tombstone that invalidates older instances of the deleted key. State-of-the-art LSM engines do not provide guarantees as to how fast a tombstone will propagate to persist the deletion. Further, LSM engines only support deletion on the sort key. To delete on another attribute (e.g., timestamp), the entire tree is read and re-written. We highlight that fast persistent deletion without affecting read performance is key to support: (i) streaming systems operating on a window of data, (ii) privacy with latency guarantees on the right-to-be-forgotten, and (iii) en masse cloud deployment of data systems that makes storage a precious resource.
   To address these challenges, in this paper, we build a new key-value storage engine, Lethe, that uses a very small amount of additional metadata, a set of new delete-aware compaction policies, and a new physical data layout that weaves the sort and the delete key order. We show that Lethe supports any user-defined threshold for the delete persistence latency offering higher read throughput (1.17-1.4x) and lower space amplification (2.1-9.8x), with a modest increase in write amplification (between 4% and 25%). In addition, Lethe supports efficient range deletes on a secondary delete key by dropping entire data pages without sacrificing read performance nor employing a costly full tree merge.

2. SYSTEMS J.

   i-MAC: In-Body Sensor MAC in Wireless Body Area Networks for Healthcare IoT

   Sudip Misra, Pradyumna Kumar Bishoyi, and Subhadeep Sarkar

   IEEE Systems Journal, 2020

   Abs PDF

   The application of Internet-of-Things (IoT) technology in modern healthcare environment has given rise to a new paradigm known as healthcare IoT. The wireless body area network (WBAN) is one of the basic building blocks of IoT-based healthcare system, comprising many wearable (on-body) and implant (in-body) sensors placed in or around patient body connected to a hub for physiological signal monitoring. In in-body sensor-based WBAN, guaranteeing quality-of-service and prolonging network lifetime are major impediments due to the sensor location and limited battery capacity. In this article, we propose a novel energy-efficient medium access control (MAC) protocol for IEEE 802.15.6 standard complaint in-body sensor-based WBAN. Typically, the in-body sensor-based WBAN communication is hub-initiated; however, in case of an emergency event, the in-body sensor node transmits an emergency frame arbitrarily without sensing the channel. This inadvertent in-body sensor-initiated transmission has a very high probability of collision with the ongoing hub-initiated transmission, and/or another in-body sensor-initiated emergency frame transmission. This results in emergency frame retransmission and consequently affects the node’s energy consumption and lifetime. To alleviate this issue, we propose a modified superframe structure, in which separate access phases are introduced for the emergency event and regular event. In case of an emergency event, a novel emergency event handling scheme and a ranking and priority assignment protocol is proposed to detect and address the critical event of in-body sensors. To minimize the collision, a scheduled access mechanism is proposed according to the criticality of the node. Performance analysis of the proposed in-body sensor MAC is done in terms of latency and overall power consumption, in case of both emergency and regular events.

2019

1. CRC Press

   Sensors, Cloud, and Fog: The Enabling Technologies for the Internet of Things

   Sudip Misra, Subhadeep Sarkar, and Subarna Chatterjee

   CRC Press, Taylor & Francis Group, 2019

   Abs

   This book provides an in-depth understanding of Internet of Things (IoT) technology. It highlights several of today’s research and technological challenges of translating the concept of the IoT into a practical, technologically feasible, and business-viable solution. It introduces two novel technologies – sensor-cloud and fog computing – as the crucial enablers for the sensing and compute backbone of the IoT. The book discusses these two key enabling technologies of IoT that include a wide range of practical design issues and the futuristic possibilities and directions involving sensor networks and cloud and fog computing environments towards the realization and support of IoT.

2018

1. TCC

   Assessment of the Suitability of Fog Computing in the Context of Internet of Things

   Subhadeep Sarkar, Subarna Chatterjee, and Sudip Misra

   IEEE Transactions on Cloud Computing, 2018

   Abs PDF

   This work performs a rigorous, comparative analysis of the fog computing paradigm and the conventional cloud computing paradigm in the context of the Internet of Things (IoT), by mathematically formulating the parameters and characteristics of fog computing – one of the first attempts of its kind. With the rapid increase in the number of Internet-connected devices, the increased demand of real-time, low-latency services is proving to be challenging for the traditional cloud computing framework. Also, our irreplaceable dependency on cloud computing demands the cloud data centers (DCs) always to be up and running which exhausts huge amount of power and yield tons of carbon dioxide (CO2) gas. In this work, we assess the applicability of the newly proposed fog computing paradigm to serve the demands of the latency-sensitive applications in the context of IoT. We model the fog computing paradigm by mathematically characterizing the fog computing network in terms of power consumption, service latency, CO2 emission, and cost, and evaluating its performance for an environment with high number of Internet-connected devices demanding real-time service. A case study is performed with traffic generated from the 100 highest populated cities being served by eight geographically distributed DCs. Results show that as the number of applications demanding real-time service increases, the fog computing paradigm outperforms traditional cloud computing. For an environment with 50% applications requesting for instantaneous, real-time services, the overall service latency for fog computing is noted to decrease by 50:09%. However, it is mentionworthy that for an environment with less percentage of applications demanding for low-latency services, fog computing is observed to be an overhead compared to the traditional cloud computing. Therefore, the work shows that in the context of IoT, with high number of latency-sensitive applications fog computing outperforms cloud computing.

2. iThings

   Towards Enforcement of the EU GDPR: Enabling Data Erasure

   Subhadeep Sarkar, Jean-Pierre Banâtre, Louis Rilling, and Christine Morin

   In IEEE International Conference on Internet of Things (iThings), 2018

   Abs PDF

   With the emergence of the Internet of Things (IoT), an increasing need for preserving the privacy of personal data has been realized. In this context, the EU has recently published the general data protection regulation (GDPR), which ensures strengthening of the privacy rights of the data subjects concerning their personal data. In this paper, we present the importance of having a holistic solution aimed towards the enforcement of the GDPR. As a first step towards the enforcement of the GDPR, we present the research challenges in facilitating the erasure of data as per the right to erasure. We also propose the envisaged technical solutions to work through the challenges.

2017

1. COMM LETTERS

   Privacy-Aware Blind Cloud Framework for Advanced Healthcare

   Subhadeep Sarkar, Subarna Chatterjee, Sudip Misra, and Rajesh Kudupudi

   IEEE Communications Letters, 2017

   Abs PDF

   This letter proposes a novel privacy-aware “blind” cloud infrastructure to be utilized for storage, processing, and organization of health data. Traditional healthcare systems rely on cloud computing servers for back-end storage and processing. However, cloud servers are heavily vulnerable to privacy threats and the problem is even more intense as physiological data carry sensitive information. To resolve the aforementioned issue, this letter proposes the blind cloud framework. The goal is to take advantage of the enormous computing and storage abilities of the cloud servers, and yet maintain data anonymity simultaneously. To preserve the privacy of the medical data, the cloud server is forcefully blinded, i.e., the identities of the patients are masked off and a pseudo-identity is generated, thereby, obtaining unidentified in-cloud data for storage and analysis. We also propose a parallel method to be executed within the non-cloud servers for efficient and lossless identity management and retrieval. Results indicate that the performance of the processes of pseudo-identity generation and identity retrieval is independent of the data volumes, and negligibly vary with the increase in the number of the clients of the system.

2. COMM NETWORKS

   Optimal Decision Rule-based Ex-Ante Frequency Hopping for Jamming Avoidance in Wireless Sensor Networks

   Prasenjit Bhavathankar, Subhadeep Sarkar, and Sudip Misra

   Computer Networks, Elsevier, 2017

   Abs PDF

   In this paper, we consider a static wireless sensor network (WSN) affected by a constant, static jammer. Both the nodes in the network and the jammer are capable of switching frequencies. Existing literature mostly thrive on mechanisms with a mutually pre-decided hopping-sequence or on random frequency-hopping techniques. However, these mechanisms often fall short in the context of energy-constrained WSNs. We propose a frequency-hopping strategy based on the optimal decision rule. The proposed solution takes into account the individual decision profiles of all the concerned nodes, and finally, makes the decision for the welfare of the overall network. The objective is to find an optimal frequency hopping rule to obtain the maximum throughput. We observe that the packet delivery ratio of the network improves by approximately 30% after the application of the optimal decision rule for frequency-hopping. The overall network energy consumption is also improved by approximately 53% by the application of the proposed solution approach, as observed from the results.

2016

1. PULSE

   From Micro to Nano: The Evolution of Wireless Sensor-Based Health Care

   Subhadeep Sarkar, and Sudip Misra

   IEEE Pulse, 2016

   Abs PDF

   Over the past decade, embedded systems and microelectromechanical systems have evolved in a radical way, redefining our standard of living and enhancing the quality of life. Health care, among various other fields, has benefited vastly from this technological development. The concept of using sensors for health care purposes originated in the late 1980s when sensors were developed to measure certain physiological parameters associated with the human body. In traditional sensor nodes, the signal sources are mostly different environmental phenomena (such as temperature, vibration, and luminosity) or man-made events (such as intrusion and mobile target tracking), whereas in case of the physiological sensors, the signal source is living human tissue. These sensor nodes, as their primary sensing element, have a diaphragm that converts pressure into displacement. This displacement, in turn, is subsequently transformed into an electrical signal. The concept of wireless physiological sensor nodes, however, gained popularity in the mid-2000s, with the sensed data from the nodes transmitted to the hub via a wireless medium. The network formed by this heterogeneous set of wireless body sensor nodes is termed a wireless body-area network (WBAN). Each WBAN is essentially a composition of multiple wireless body sensor nodes and a single hub. The hub is primarily responsible for acquisition of the raw sensed data from all the component sensor nodes and first-level aggregation of the data before transmitting the aggregated data for further analysis to a remote data acquisition center. Here, we outline the evolution of WBANs in the context of modern health care and its convergence with nanotechnology.

2. IET NETWORKS

   Theoretical Modelling of Fog Computing: A Green Computing Paradigm to Support IoT Applications

   Subhadeep Sarkar, and Sudip Misra

   IET Networks, 2016

   Abs PDF

   In this study, the authors focus on theoretical modelling of the fog computing architecture and compare its performance with the traditional cloud computing model. Existing research works on fog computing have primarily focused on the principles and concepts of fog computing and its significance in the context of internet of things (IoT). This work, one of the first attempts in its domain, proposes a mathematical formulation for this new computational paradigm by defining its individual components and presents a comparative study with cloud computing in terms of service latency and energy consumption. From the performance analysis, the work establishes fog computing, in collaboration with the traditional cloud computing platform, as an efficient green computing platform to support the demands of the next generation IoT applications. Results show that for a scenario where 25% of the IoT applications demand real-time, low-latency services, the mean energy expenditure in fog computing is 40.48% less than the conventional cloud computing model.

3. GLOBECOM

   Resource Allocation for Wireless Body Area Networks in Presence of Selfish Agents

   Subhadeep Sarkar, Sudip Misra, and Mohammad S. Obaidat

   In 2016 IEEE Global Communications Conference (GLOBECOM), 2016

   Abs PDF

   In medical emergency situations, fair distribution of resources in a multi-tenant scenario is crucial. In such resource-constrained situations, these organizations may behave in a non-cooperative and selfish manner to maximize their individual incentives at the cost of the overall system welfare. Existing research works on dynamic resource allocation, have mostly assumed that the participating agents always behave truthfully, and place bids in accordance with their actual requirements. In practice, this assumption may not always hold true, as organizations have positive incentives for overstating. We design an algorithm, grounded in the theory of distributed mechanism design, to effectively alleviate untruthful demeanor of the organizations. The proposed resource allocation algorithm allows such organizations to maximize their individual incentives only by acting truthfully, whilst the overall system welfare is also maximized. The mechanism designed is resilient to selfish behavior of the organizations, and ensures voluntary participation of the organizations in the auction. It is also incentive compatible in nature, and dictates a truthful incentive-payment scheme.

2015

1. TC

   Performance Analysis of IEEE 802.15.6 MAC Protocol under Non-Ideal Channel Conditions and Saturated Traffic Regime

   Subhadeep Sarkar, Sudip Misra, Bitan Bandyopadhyay, Chandan Chakraborty, and Mohammad S. Obaidat

   IEEE Transactions on Computers, 2015

   Abs PDF

   Recently, the IEEE 802.15.6 Task Group introduced a new wireless communication standard that provides a suitable framework specifically to support the requirements of wireless body area networks (WBANs). The standardization dictates the physical (PHY) layer and medium access control (MAC) layer protocols for WBAN-based communications. Unlike the pre-existing wireless communication standards, IEEE 802.15.6 standardization supports short-range, extremely low power wireless communication with high quality of service and support for high data rates upto 10 Mbps in the vicinity of living tissues. In this work, we construct a discrete-time Markov chain (DTMC) that efficiently depicts the states of an IEEE 802.15.6 CSMA/CA-based WBAN. Following this, we put forward a thorough analysis of the standard in terms of reliability, throughput, average delay, and power consumption. The work concerns non-ideal channel characteristics and a saturated network traffic regime. The major shortcoming of the existing literature on Markov chain-based analysis of IEEE 802.15.6 is that the authors did not take into consideration the time spent by a node awaiting the acknowledgement frame after transmission of a packet, until time-out occurs. Also, most of the work assume that ideal channel characteristics persist for the network which is hardly the case in practice. This work remains distinctive as we take into account the waiting time of a node after it transmits a packet while constructing the DTMC. Based on the DTMC, we perform a user priority (UP)-wise analysis, and justify the importance of the standard from a medical perspective.

2. JBHI

   Priority-Based Time-Slot Allocation in Wireless Body Area Networks During Medical Emergency Situations: An Evolutionary Game-Theoretic Perspective

   Sudip Misra, and Subhadeep Sarkar

   IEEE Journal of Biomedical and Health Informatics, 2015

   Abs PDF

   In critical medical emergency situations, wireless body area network (WBAN) equipped health monitoring systems treat data packets with critical information regarding patients’ health in the same way as data packets bearing regular healthcare information. This snag results in a higher average waiting time for the local data processing units (LDPUs) transmitting data packets of higher importance. In this paper, we formulate an algorithm for Priority-based Allocation of Time Slots (PATS) that considers a fitness parameter characterizing the criticality of health data that a packet carries, energy consumption rate for a transmitting LDPU, and other crucial LDPU properties. Based on this fitness parameter, we design the constant model hawk-dove game that ensures prioritizing the LDPUs based on crucial properties. In comparison with the existing works on priority-based wireless transmission, we measure and take into consideration the urgency, seriousness, and criticality associated with an LDPU and, thus, allocate transmission time slots proportionately. We show that the number of transmitting LDPUs in medical emergency situations can be reduced by 25.97%, in comparison with the existing time-division-based techniques.

3. ICC

   Quantification of Node Misbehavior in Wireless Sensor Networks: A Social Choice-based Approach

   Subarna Chatterjee, Subhadeep Sarkar, and Sudip Misra

   In IEEE International Conference on Communication (ICC) Workshops, 2015

   Abs PDF

   This work focuses on the quantification of node misbehavior in wireless sensor networks (WSNs). Misbehaving nodes are common within WSNs which are once detected, are penalized and in some cases eliminated from the network. However, node misbehavior might be relative i.e., a node may exhibit maliciousness or selfishness only to a specific set of nodes and may function normally for the rest. In these cases, a complete elimination of the node from the network is unfair. This work mitigates the aforesaid problem and mathematically evaluates the extent of misbehavior of a node through the proposed Metric of Misbehavior (MoM). Based on the Theory of Social Choice, the proposed algorithm considers the misbehaving nodes as the voting alternatives and the normally behaving nodes as the voters. Based on majority ranking of social choice, eventually MoM is obtained for every alternative in a fair manner.

4. CLOUD COMP

   Evacuation and Emergency Management Using a Federated Cloud

   Subhadeep Sarkar, Subarna Chatterjee, and Sudip Misra

   IEEE Cloud Computing, 2015

   Abs PDF

   Contemporary disaster relief techniques fall significantly short in terms of efficiency and timeliness. In a postdisaster scenario, the generation and transmission of voluminous data at a high velocity impacts the communication framework. This work exploits the benefits of opportunistic communication and efficient big data management policies, focusing on the collaboration of multiple private and/or public clouds of diverse nature to perform damage assessment and determine the spatial distribution of the live victims and their physical and mental status. Based on the analytics, real-time decision making of the rescue operation is achieved.

2014

1. GLOBECOM

   Analysis of Reliability and Throughput under Saturation Condition of IEEE 802.15.6 CSMA/CA for Wireless Body Area Networks

   Subhadeep Sarkar, Sudip Misra, Chandan Chakraborty, and Mohammad S. Obaidat

   In IEEE Global Communications Conference (GLOBECOM), 2014

   Abs PDF

   The standardization of the IEEE 802.15.6 protocol for wireless body area networks (WBANs) dictates the physical layer and medium access control layer standards from the communication perspective. The standard supports short-range, extremely low power wireless communication with high quality of service and data rates upto 10 Mbps in the vicinity of any living tissue. In this paper, we develop a discrete-time Markov model for the accurate analysis of reliability and throughput of an IEEE 802.15.6 CSMA/CA-based WBAN under saturation condition. Existing literature on Markov chain-based analysis of IEEE 802.15.6, however, do not take into consideration the time a node spends waiting for the immediate acknowledgement frame after transmission of a packet, until time-out occurs. In this work, we take into consideration the waiting time for a node after its transmission, and accordingly modified the structure of the discrete-time Markov chain (DTMC). We also show that as the payload length increases, the reliability of a node decreases; whereas its throughput sharply increases.