Federated Learning (FL) enables privacy-preserving distributed machine learning by training models across clients without raw data exchange. However, non-IID data distributions-particularly when clients possess overlapping samples alongside unique data-pose significant challenges for client selection strategies. Traditional random sampling approaches inadequately balance the trade-off between redundant updates from overlapping data and diverse contributions from clientspecific samples, resulting in suboptimal model performance. We propose PECO, a dynamic client selection framework that evaluates each client's contribution to model performance using a small validation set and adaptively assigns selection probabilities based on these contributions. Through experiments on CIFAR10 and Fashion-MNIST, we demonstrate that PECO consistently outperforms random selection, achieving superior model accuracy and convergence stability across diverse non-IIID scenarios with overlapping data.11This work is partially supported by the National Science Foundation Award OCA-2417715

Apache Spark is an in-memory analytic framework that has been adopted in the industry and research fields. Two memory managers, Static and Unified, are available in Spark to allocate memory for caching Resilient Distributed Datasets (RDDs) and executing tasks. However, we find that the static memory manager (SMM) lacks flexibility, while the unified memory manager (UMM) puts heavy pressure on the garbage collection of the JVM on which Spark resides. To address these issues, we design a learning-based bidirectional usage-bounded memory allocation scheme to support dynamic memory allocation with the consideration of both memory demands and latency introduced by garbage collection. We first develop an auto-tuning memory manager (ATuMm) that adopts an intuitive feedback-based learning solution. However, ATuMm is a slow learner that can only alter the states of Java Virtual Memory (JVM) Heap in a limited range. That is, ATuMm decides to increase or decrease the boundary between the execution and storage memory pools by a fixed portion of JVM Heap size. To overcome this shortcoming, we further develop a new reinforcement learning-based memory manager (Q-ATuMm) that uses a Q-learning intelligent agent to dynamically learn and tune the partition of JVM Heap. We implement our new memory managers in Spark 2.4.0 and evaluate them by conducting experiments in a real Spark cluster. Our experimental results show that our memory manager can reduce the total garbage collection time and thus further improve Spark applications’ performance (i.e., reduced latency) compared to the existing Spark memory management solutions. By integrating our machine learning-driven memory manager into Spark, we can further obtain around 1.3x times reduction in the latency.

The industry has adopted disaggregated storage systems to provide high-quality services for hyper-scale architectures. This infrastructure enables organizations to access storage resources that can be independently managed, configured, and scaled. It is supported by the recent advances of all-flash arrays and NVMe-over-Fabric protocol, enabling remote access to NVMe devices over different network fabrics. A surge of research has been proposed to mitigate network congestion in traditional remote direct memory access protocol (RDMA). However, NVMe-oF raises new challenges in congestion control for disaggregated storage systems.In this work, we investigate the performance degradation of the read throughput on storage nodes caused by traditional network congestion control mechanisms. We design a storage-side rate control (SRC) to relieve network congestion while avoiding performance degradation on storage nodes. First, we design an I/O throughput control mechanism in the NVMe driver layer to enable throughput control on storage nodes. Second, we construct a throughput prediction model to learn a mapping function between workload characteristics and I/O throughput. Third, we deploy SRC on storage nodes to cooperate with traditional network congestion control on an NVMe-over-RDMA architecture. Finally, we evaluate SRC with varying workloads, SSD configurations, and network topologies. The experimental results show that SRC achieves significant performance improvement.

In recent years, designs and optimizations on disaggregated storage systems supported by cutting-edge storage and network techniques emerge dramatically. However, conducting experiments in a disaggregated architecture is often expensive. A comprehensive modeling system of disaggregated storage systems is indispensable for researchers to construct fast and reliable experiments. Modeling and evaluating the performance of disaggregated storage systems is a challenge for the following reasons. First, the performance of a disaggregated storage system depends on network protocols and storage solutions jointly. Second, the available trace datasets for generating the workload may not suffice the need for the simulation, as they are collected without considering the integration of network delay and storage processing time. This work proposes a storage-network iterative simulation (SNIS) for disaggregated storage systems by considering the issues above. Our simulation methodology integrates storage and network simulations to model the end-to-end performance of disaggregated storage systems and conducts multiple rounds of simulations to update arrival times of read/write requests. The evaluation results show that SNIS can converge to a relatively stable state after a certain number of iterations.

The advance of hardware has allowed edge devices to carry out varying applications, including computation-intensive machine learning tasks. This paper targets a real-time application of detecting objects on streaming videos with a tightened requirement on processing overhead. While the edge device still lacks the computation power to apply the object detection algorithm on every video frame, this paper integrates cloud-side servers in the solution as much prior work has attempted. However, our design is different from the conventional off-loading solutions that delegate the computation tasks to the cloud servers. We present a solution named CODS where the computation tasks are still conducted by the edge devices while the cloud server provides useful guidelines for choosing appropriate analysis algorithms. We implement our solution with the Jetson Nano device and evaluate it with videos from representative datasets. The results show that CODS is quite effective and superior to baseline alternatives.

Efficiently managing resources and improving throughput in a large-scale cluster has become a crucial problem with the explosion of data processing applications in recent years. Hadoop YARN and Mesos, as two universal resource management platforms, have been widely adopted in the commodity cluster for co-deploying multiple data processing frameworks, such as Hadoop MapReduce and Apache Spark. However, in the existing resource management, a certain amount of resources are exclusively allocated to a running task and can only be re-assigned after that task is completed. This exclusive mode unfortunately leads to a potential problem that may under-utilize the cluster resources and degrade system performance. To address this issue, we propose a novel opportunistic and efficient resource allocation scheme, named OpERA, which breaks the barriers among the encapsulated resource containers by leveraging the knowledge of actual runtime resource utilizations to re-assign opportunistic available resources to the pending tasks. OpERA avoids incurring severe performance interference to active tasks by further using two approaches to efficiently balances the starvations of reserved tasks and normal queued tasks. We implement and evaluate OpERA in Hadoop YARN v2.5. Our experimental results show that OpERA significantly reduces the average job execution time and increases the resource (CPU and memory) utilizations.

The MapReduce framework has become the defacto scheme for scalable semi-structured and un-structured data processing in recent years. The Hadoop ecosystem has evolved into its second generation, Hadoop YARN, which adopts fine-grained resource management schemes for job scheduling. Nowadays, fairness and efficiency are two main concerns in YARN resource management because resources in YARN are shared and contended by multiple applications. However, the current scheduling in YARN does not yield the optimal resource arrangement, unnecessarily causing idle resources and inefficient scheduling. It omits the dependency between tasks which is extremely crucial for the efficiency of resource utilization as well as heterogeneous job features in real application environments. We thus propose a new YARN scheduler which can effectively reduce the makespan (i.e., the total execution time) of a batch of MapReduce jobs in Hadoop YARN clusters by leveraging the information of requested resources, resource capacities and dependency between tasks. For accommodating heterogeneity in MapReduce jobs, we also extend our scheduler by further considering the job iteration information in the scheduling decisions. We implemented the new scheduling algorithm as a pluggable scheduler in YARN and evaluated it with a set of classic MapReduce benchmarks. The experimental results demonstrate that our YARN scheduler effectively reduces the makespans and improves resource utilizations.

Augmented reality (AR) is an emerging technology that weaves virtual objects into physical environments, and enables users to interact with them through viewing devices. This paper targets on multi-user AR applications, where virtual objects (VOs) placed by a user can be viewed by other users. We develop a practical framework that supports the basic multi-user AR functions of placing and viewing VOs, and our system can be deployed on off-the-shelf smartphones without special hardware. The main technical challenge we address is that when facing the exact same scene, the user who places the VO and the user who views the VO may have different view angles and distances to the scene. This setting is realistic and the traditional solutions yield a poor performance in terms of the accuracy. In this work, we have developed a suite of algorithms that help the viewers accurately identify the same scene and restore the VO under a moderate range of view angle difference. We have prototyped our system, and the experimental results have shown significant performance improvements. Our source codes and demos can be accessed at https://github.com/PROMAR2019.

Apache Spark is an in-memory analytic framework that has been adopted in the industry and research fields. Two memory managers, Static and Unified, are available in Spark to allocate memory for caching Resilient Distributed Datasets (RDDs) and executing tasks. However, we found that the static memory manager (SMM) lacks flexibility, while the unified memory manager (UMM) puts heavy pressure on the garbage collection of JVM on which Spark resides. To address these issues, we design an auto-tuning memory manager (ATuMm) to support dynamic memory allocation with the consideration of both memory demands and latency introduced by garbage collection. We implement our new memory manager in Spark 2.2.0 and evaluate it by conducting experiments in a real Spark cluster. Our experimental results show that our auto-tuning memory manager can reduce the total garbage collection time and thus further improve the performance (i.e., reduced latency) of Spark applications, compared to the existing Spark memory management solutions.

Mobile Augmented Reality (MAR) represents an emerging category of applications that bring users interactive experiences with the physical experiencesnvironment. In such applications, users can place virtual objects in real-world space, and view them through a camera view. In this work, we develop a framework that supports multi-users interactions for MAR apps, where one user places a virtual object that can be recognized by other users.

Data temperature identification is an importance issue of many fields like data caching and storage tiering in modern flash-based storage systems. With the technological advancement of memory and storage, data temperature identification is no longer just a classification of hot and cold, but instead becomes a "multistreaming" data categorization problem to classify data into multiple categories according to their temperature. Therefore, we propose a novel data temperature identification scheme that adopts bloom filters to efficiently capture both frequency and recency of data blocks and accurately identify the exact data temperature for each data block. Moreover, in bloom filter data structure we replace the original OR operation with the XOR masking operation such that our scheme can delete or reset bits in bloom filters and thus avoid high false positives due to saturation. We further utilize twin bloom filters to alternatively keep unmasked clean copies of data and thus ensure low false negative rate. Our extensive evaluation results show that our new scheme can accurately identify the exact data temperature with low false identification rates across different synthetic and real I/O workloads. More importantly, our scheme consumes less memory space compared to other existing data temperature identification schemes.

The emergence of Edge Computing and the success of Internet of Thing and (IoT) has tremendously changed the way we think about data computing. With edge devices changing from data producer to both data producer and consumer, the chance for processing large data sets with Big Data on a cloud of IoT devices is more realistic. In Big Data systems such as Hadoop-Yarn, Spark, Pig, etc., the shuffling stage is by far the most dominant source of network traffic. Unreliable performance of network will greatly impact the shuffling process. Since IoT devices mostly rely on wireless network based on 802.11, providing proper throughput to big data computing system is an important challenge that needs to be address. In this paper, we argue that a cluster of IoT computers can support big data by considering the information fed by the big data applications. We propose a cross-layer framework that uses the application layer information to guide the packet scheduling at the link layer. We implement our system as an extension module in Hadoop-Yarn system. The experimental evaluation shows significant performance improvement.

In the era of big data and cloud computing, large amounts of data are generated from user applications and need to be processed in the datacenter. Data-parallel computing frameworks, such as Apache Spark, are widely used to perform such data processing at scale. Specifically, Spark leverages distributed memory to cache the intermediate results, represented as Resilient Distributed Datasets (RDDs). This gives Spark an advantage over other parallel frameworks for implementations of iterative machine learning and data mining algorithms, by avoiding repeated computation or hard disk accesses to retrieve RDDs. By default, caching decisions are left at the programmer's discretion, and the LRU policy is used for evicting RDDs when the cache is full. However, when the objective is to minimize total work, LRU is woefully inadequate, leading to arbitrarily suboptimal caching decisions. In this paper, we design an algorithm for multi-stage big data processing platforms to adaptively determine and cache the most valuable intermediate datasets that can be reused in the future. Our solution automates the decision of which RDDs to cache: this amounts to identifying nodes in a direct acyclic graph (DAG) representing computations whose outputs should persist in the memory. Our experiment results show that our proposed cache optimization solution can improve the performance of machine learning applications on Spark decreasing the total work to recompute RDDs by 12%.

Erasure Coding based Storage (ECS) is replacing tradition replica-based systems because of its low storage overhead. In an ECS, however, every task needs to fetch remote pieces of data for its execution, and data verification is missing in the current framework. As security issues keep rising and there have been security incidents occurred in big data platforms, the compromised nodes in a computing cluster may manipulate its hosted data fed for other nodes yielding misleading results. Without replicas, it is quite challenging to efficiently verify the data integrity in ECS. In this paper, we develop ROVER, which is an efficient and verifiable ECS for big data platforms. In ROVER, every piece of data is monitored by its checksums stored on a set of witnesses. Bloom filter technique is used on each witness to efficiently keep the records of the checksums. The data verification is based on the majority voting. ROVER also supports a quick reconstruction of Bloom Filter when a node recovers from a failure. We present a complete system framework, security analysis, and a guideline for setting the parameters. The implementation and evaluation show that ROVER is robust and efficient against the attack from the compromised nodes.

We introduce a game-theoretic framework to explore revenue sharing in an Edge-Cloud computing system, in which computing service providers at the edge of the Internet (edge providers) and computing service providers at the cloud (cloud providers) collectively provide computing resources to clients (e.g., end users or applications) at the edge. Different from traditional cloud computing, the providers in an Edge-Cloud system are independent and self-interested. To achieve high system-level efficiency, the manager of the system adopts a task distribution mechanism to maximize the total revenue received from clients and also adopts a revenue sharing mechanism to split the received revenue among computing servers (and hence service providers). Under those system-level mechanisms, service providers attempt to game with the system in order to maximize their own utilities, by strategically allocating their resources (e.g., computing servers). Our framework models the competition among the providers in an Edge-Cloud system as a non-cooperative game. We have shown the existence of Nash equilibrium in the game both theoretically and practically through simulations and experiments on an emulation system that we have developed. We find that revenue sharing mechanisms have a significant impact on the system-level efficiency at Nash equilibria, and surprisingly the revenue sharing mechanism based directly on actual contributions can result in significantly worse system performance than Shapley value sharing mechanism and Ortmann proportional sharing mechanism. Our framework provides an effective economics approach to the understanding and designing of efficient Edge-Cloud computing systems.

Due to the flexibility of data operations and scalability of in- memory cache, Spark has revealed the potential to become the standard distributed framework to replace Hadoop for data-intensive processing in both industry and academia. However, we observe that the built-in scheduling algorithms in Spark (i.e., FIFO and FAIR) are not optimized for the applications with multiple parallel and independent branches in stages. Specifically, the child stage needs to wait and collect data from all its parent branches, but this wait has no guaranteed upper bound since it is tightly coupled with each branch's workload characteristic, stage order, and their corresponding allocated computing resource. To address this challenge, we investigate a superior solution which ensures all branches acquire suitable resources according to their workload demand in order to let the finish time of each branch be as close as possible. Based on this, we propose a novel scheduling policy, named AutoPath, which can effectively reduce the overall makespan of such kind of applications by detecting and leveraging the parallel path, and adaptively assigning computing resources based on the estimated workload demands during runtime. We implemented the new scheduling scheme in Spark v1.5.0 and evaluated it with selected representative workloads. The experiments demonstrate that our new scheduler effectively reduces the makespan and improves resource utilizations for these applications, compared to the current FIFO and FAIR schedulers.

Offloading resource-intensive jobs to the cloud and nearby users is a promising approach to enhance mobile devices. This paper investigates a hybrid offloading system that takes both infrastructure-based networks and Ad-hoc networks into the scope. Specifically, we propose EDOS, an edge assisted offloading system that consists of two major components, an Edge Assistant (EA) and Offload Agent (OA). EA runs on the routers/towers to manage registered remote cloud servers and local service providers and OA operates on the users' devices to discover the services in proximity. We present the system with a suite of protocols to collect the potential service providers and algorithms to allocate tasks according to user-specified constraints. To evaluate EDOS, we prototype it on commercial mobile devices and evaluate it with both experiments on a small-scale testbed and simulations. The results show that EDOS is effective and efficient for offloading jobs.

Big data processing frameworks such as Hadoop have been widely adopted to process a large volume of data. A lot of prior work has focused on the allocation of resources and the execution order of jobs/tasks to improve the performance in a homogeneous cluster. In this paper, we investigate storage layer design in a heterogeneous system considering a new type of bundled jobs where the input data and associated application jobs are submitted in a bundle. Our goal is to break the barrier between resource management and the underlying storage layer, and improve data locality, an important performance factor for resource management, from the aspect of storage system. We develop a sampling-based randomized algorithm for the network file system to determine the placement of input data blocks. The main idea is to query a selected set of candidate nodes, and estimate their workload at run time combining centralized and per-node information. The node with the smallest workload is selected to host the data block. Our evaluation is based with system implementation and comprehensive experiments on NSF CloudLab platforms. We have also conducted simulation for large-scale clusters. The results show significant performance improvements in terms of execution time and data locality.

The MapReduce framework and its open source implementation Hadoop have become the defacto platform for scalable analysis on large data sets in recent years. One of the primary concerns in Hadoop is how to minimize the completion length (i.e., makespan) of a set of MapReduce jobs. The current Hadoop only allows static slot configuration, i.e., fixed numbers of map slots and reduce slots throughout the lifetime of a cluster. However, we found that such a static configuration may lead to low system resource utilizations as well as long completion length. Motivated by this, we propose simple yet effective schemes which use slot ratio between map and reduce tasks as a tunable knob for reducing the makespan of a given set. By leveraging the workload information of recently completed jobs, our schemes dynamically allocates resources (or slots) to map and reduce tasks. We implemented the presented schemes in Hadoop V0.20.2 and evaluated them with representative MapReduce benchmarks at Amazon EC2. The experimental results demonstrate the effectiveness and robustness of our schemes under both simple workloads and more complex mixed workloads.

Efficiently managing resources and improving throughput in a large-scale cluster has become a crucial problem with the explosion of data processing applications in recent years. Hadoop YARN and Mesos, as two universal resource management platforms, have been widely adopted in the commodity cluster for co-deploying multiple data processing frameworks, such as Hadoop MapReduce and Apache Spark. However, in the existing resource management, a certain amount of resources are exclusively allocated to a running task and can only be re-assigned after that task is completed. This exclusive mode unfortunately leads to a potential problem that may underutilize the cluster resources and degrade system performance. To address this issue, we propose a novel opportunistic and efficient resource allocation approach, named OpERA, which breaks the barriers among the encapsulated resource containers by leveraging the knowledge of actual runtime resource utilizations to re-assign opportunistic available resources to the pending tasks. We implement and evaluate OpERA in Hadoop YARN v2.5. Our experimental results show that OpERA significantly reduces the average job execution time and increases the resource (CPU and memory) utilizations.

In this paper, we aim to develop an efficient speculation framework for a heterogeneous cluster. Speculation is a common mechanism that identifies ‘slow’ node in a cluster and starts redundant tasks on other nodes to guarantee the reliability. We consider MapReduce/Hadoop as a representative computing platform, and our general goal is to accurately and quickly identify the straggler nodes during the job execution. On the one hand, our approach significantly reduces unnecessary speculative executions that occupy system resources, but do not get finished. On the other hand, when a node is prone to failure, our solution is able to detect it at an early stage and effectively launch a speculative task to avoid the delay in the job execution. We implement our solution in Hadoop platform and evaluate it with extensive experiments. The results show that our solution is efficient and effective when handling the speculative execution. The job execution time in our system is superior to that in the current Hadoop distribution.

In a shared virtualized storage system that runs VMs with heterogeneous IO demands, it becomes a problem for the hypervisor to cost-effectively partition and allocate SSD resources among multiple VMs. There are two straightforward approaches to solving this problem: equally assigning SSDs to each VM or managing SSD resources in a fair competition mode. Unfortunately, neither of these approaches can fully utilize the benefits of SSD resources, particularly when the workloads frequently change and bursty IOs occur from time to time. In this paper, we design a Global SSD Resource Management solution - GReM, which aims to fully utilize SSD resources as a second-level cache under the consideration of performance isolation. In particular, GReM takes dynamic IO demands of all VMs into consideration to split the entire SSD space into a long-term zone and a short-term zone, and cost-effectively updates the content of SSDs in these two zones. GReM is able to adaptively adjust the reservation for each VM inside the long-term zone based on their IO changes. GReM can further dynamically partition SSDs between the long- and short-term zones during runtime by leveraging the feedbacks from both cache performance and bursty workloads. Experimental results show that GReM can capture the cross-VM IO changes to make correct decisions on resource allocation, and thus obtain high IO hit ratio and low IO management costs, compared with both traditional and state-of-the-art caching algorithms.

This paper deals with the energy management problem of a Proton Exchange Membrane Fuel Cell (PEMFC) with Supercapacitor (SC) hybrid system. An innovative Interconnection and Damping Assignment Passivity-based Controller (IDA-PBC) with multi-equilibrium states is proposed in this paper. The hybrid system is first modeled as a Port-controlled Hamiltonian (PCH) system by considering the PEMFC and the SC as external voltage signals. Moreover, the IDA-PBC is designed using the techniques of energy shaping and damping injection, and the multi-equilibrium states of the hybrid system in different operating modes are analyzed. Simulation studies are carried out in Matlab/Simulink software to validate the proposed control strategy. The results show that the proposed IDA-PBC with multi-equilibrium states optimally balances power flow distribution in the hybrid system and ensures the stability of the hybrid system in different operating modes.

Hadoop YARN is an open project developed by the Apache Software Foundation to provide a resource management framework for large scale parallel data processing. However, there exists a resource waiting deadlock under the Fair scheduler when the resource requisition of applications is beyond the amount that the cluster can provide. In such a case, the YARN system will be halted if all resources are occupied by ApplicationMasters, a special task of each job that negotiates resources for processing tasks and coordinates job execution. Therefore, we develop a new admission control mechanism which dynamically reserves resources for processing tasks in order to avoid resource waiting deadlocks and meanwhile obtain good performance. We implement and evaluate our new mechanism in Hadoop YARN v2.2.0. The experimental results show the effectiveness of this mechanism under MapReduce benchmarks.

This paper investigates the routing protocols in smartphone-based mobile Ad-Hoc networks. We introduce a new dual radio communication model, where a long-range, low cost, and low rate radio is integrated into smartphones to assist regular radio interfaces such as WiFi and Bluetooth. We propose to use the long-range radio to carry out small management data packets to improve the routing protocols. Specifically, we develop new schemes to improve the efficiency of the path establishment and path recovery process in the on-demand Ad-Hoc routing protocols. We have prototyped our solution LAAR on Android phones and evaluated the performance with small scale experiments and large scale simulation implemented on NS2. The results show that LAAR significantly improves the performance.

With the widespread use of Internet, online advertising, as a newly emerged way of delivering advertisements, has become the focus of attention. Compared with traditional ways of advertising, real-time targeted online advertising is much more efficient and profitable, taking the advantage of abundant online users' profiles. Advertisements can be delivered to potential users who are actually interested in the ad content, which improves the accuracy of advertising, and thus potentially increases advertisers' profits. However, targeted advertising makes use of online users' personal profiles, which raises significant privacy concerns since personal profiles may contain sensitive information. It is interesting but challenging to design a privacy-preserving protocol, which allows advertising platform to effectively deliver ads to interested users, while protecting the users' private information. In this paper, we propose a Privacy-pReserving prOtocol for real-time Targeted Advertising (PROTA). We theoretically prove the privacy properties of PROTA, and show that the system requirements are satisfied. Evaluations are also conducted to demonstrate the feasibility of PROTA.

MapReduce has become a popular data processing framework in the past few years. Scheduling algorithm is crucial to the performance of a MapReduce cluster, especially when the cluster is concurrently executing a batch of MapReduce jobs. However, the scheduling problem in MapReduce is different from the traditional job scheduling problem as the reduce phase usually starts before the map phase is finished to “shuffle” the intermediate data. This paper develops a new strategy, named OMO, which particularly aims to optimize the overlap between the map and reduce phases. Our solution includes two new techniques, lazy start of reduce tasks and batch finish of map tasks, which catch the characteristics of the overlap in a MapReduce process and achieve a good alignment of the two phases. We have implemented OMO on Hadoop system and evaluated the performance with extensive experiments. The results show that OMO's performance is superior in terms of total completion length (i.e., makespan) of a batch of jobs.

The MapReduce paradigm and its open source implementation Hadoop are emerging as an important standard for large-scale data-intensive processing in both industry and academia. A MapReduce cluster is typically shared among multiple users with different types of workloads. When a flock of jobs are concurrently submitted to a MapReduce cluster, they compete for the shared resources and the overall system performance in terms of job response times, might be seriously degraded. Therefore, one challenging issue is the ability of efficient scheduling in such a shared MapReduce environment. However, we find that conventional scheduling algorithms supported by Hadoop cannot always guarantee good average response times under different workloads. To address this issue, we propose a new Hadoop scheduler, which leverages the knowledge of workload patterns to reduce average job response times by dynamically tuning the resource shares among users and the scheduling algorithms for each user. Both simulation and real experimental results from Amazon EC2 cluster show that our scheduler reduces the average MapReduce job response time under a variety of system workloads compared to the existing FIFO and Fair schedulers.

Hadoop is an emerging framework for parallel big data processing. While becoming popular, Hadoop is too complex for regular users to fully understand all the system parameters and tune them appropriately. Especially when processing a batch of jobs, default Hadoop setting may cause inefficient resource utilization and unnecessarily prolong the execution time. This paper considers an extremely important setting of slot configuration which by default is fixed and static. We proposed an enhanced Hadoop system called FRESH which can derive the best slot setting, dynamically configure slots, and appropriately assign tasks to the available slots. The experimental results show that when serving a batch of MapReduce jobs, FRESH significantly improves the makespan as well as the fairness among jobs.

The MapReduce framework has become the de facto scheme for scalable semi-structured and un-structured data processing in recent years. The Hadoop ecosystem has evolved into its second generation, Hadoop YARN, which adopts fine-grained resource management schemes for job scheduling. One of the primary performance concerns in YARN is how to minimize the total completion length, i.e., makespan, of a set of MapReduce jobs. However, the precedence constraint or fairness constraint in current widely used scheduling policies in YARN, such as FIFO and Fair, can both lead to inefficient resource allocation in the Hadoop YARN cluster. They also omit the dependency between tasks which is crucial for the efficiency of resource utilization. We thus propose a new YARN scheduler, named HaSTE, which can effectively reduce the makespan of MapReduce jobs in YARN by leveraging the information of requested resources, resource capacities, and dependency between tasks. We implemented HaSTE as a pluggable scheduler in the most recent version of Hadoop YARN, and evaluated it with classic MapReduce benchmarks. The experimental results demonstrate that our YARN scheduler effectively reduces the makespans and improves resource utilization compare to the current scheduling policies.

Today, the volume of data in the world has been tremendously increased. Large-scaled and diverse data sets are raising new big challenges of storage, process, and query. Tiered storage architectures combining solid-state drives (SSDs) with hard disk drives (HDDs), become attractive in enterprise data centers for achieving high performance and large capacity simultaneously. However, how to best use these storage resources and efficiently manage massive data for providing high quality of service (QoS) is still a core and difficult problem. In this paper, we present a new approach for automated data movement in multi-tiered storage systems, which lively migrates the data across different tiers, aiming to support multiple service level agreements (SLAs) for applications with dynamic workloads at the minimal cost. Trace-driven simulations show that compared to the no migration policy, LMsT significantly improves average I/O response times, I/O violation ratios and I/O violation times, with only slight degradation (e.g., up to 6% increase in SLA violation ratio) on the performance of high priority applications.

This paper targets the application of cloud storage management for mobile devices. Because of the limit of bandwidth and other resources, most existing cloud storage apps for smartphones do not keep local copies of files. This efficient design, however, limits the application capacities. In this paper, our goal is to extend the available file operations for cloud storage service to better serve smartphone users. We develop Skyfiles, an efficient and secure file management system that supports more advance file operations. Our basic idea is to utilize cloud instances to assist file operations. Particularly, Skyfiles supports download, compress, encrypt, convert operations, and file transfer between two smartphone users' cloud storage spaces. In addition, we design protocol for users to share their idle instances.

Smartphones have become more and more popular in the past few years. Motivated by the fact that location plays an extremely important role in mobile applications, this paper develops an efficient local message dissemination system PASA based on a new communication model called passive broadcast. It is based on the method of overloading device names described in MDSRoB [14] and Bluejacking [23]. In this new model, each node does not maintain connection state and data delivery is initialized by a receiver via a `scan' operation. The representative carriers of passive broadcast include Bluetooth and WiFi-Direct, both of which define a mandatary `peer discovery' scan function. Passive broadcast features negligible cost for establishing and maintaining direct links and is extremely suitable for short message dissemination in the proximity. In this paper, we present PASA with complete protocols and in-depth analysis for optimization. We have prototyped our solution on commercial phones and evaluated it with comprehensive experiments and simulation.

This paper investigates the routing protocol in smart phone-based mobile Ad-Hoc networks. We introduce a new dual radio communication model, where a long-range, low cost, and low rate radio is integrated into smart phones to assist regular radio interfaces such as WiFi and Bluetooth. We propose to use the long-range radio to carry out small management data packets to improve the routing protocols. Specifically, we develop new schemes built on the long-range radio to improve the efficiency of the path establishment process in the existing on-demand Ad-Hoc routing protocols. We have prototyped our solution LAAR on Android phones and evaluated the performance with small scale experiments and large scale simulation implemented on NS2. The results show that LAAR significantly improve the performance in terms of the overhead and the number of messages transferred in the network.

The MapReduce framework and its open source implementation Hadoop have become the defacto platform for scalable analysis on large data sets in recent years. One of the primary concerns in Hadoop is how to minimize the completion length (i.e., makespan) of a set of MapReduce jobs. The current Hadoop only allows static slot configuration, i.e., fixed numbers of map slots and reduce slots throughout the lifetime of a cluster. However, we found that such a static configuration may lead to low system resource utilizations as well as long completion length. Motivated by this, we propose a simple yet effective scheme which uses slot ratio between map and reduce tasks as a tunable knob for reducing the makespan of a given set. By leveraging the workload information of recently completed jobs, our scheme dynamically allocates resources (or slots) to map and reduce tasks. We implemented the presented scheme in Hadoop V0.20.2 and evaluated it with representative MapReduce benchmarks at Amazon EC2. The experimental results demonstrate the effectiveness and robustness of our scheme under both simple workloads and more complex mixed workloads.

The emergence of powerful mobile devices has allowed users to publish more contents in the Internet in recent years. The existing Internet architecture cannot cope with such exponential growth in users published contents. Content-centric networks have been proposed recently to allow future Internet to be data-centric rather than network centric. Several content centric networking approaches have been proposed, but most of them assume that users know the unique identifiers of the contents that are of interests to them. SECON [1] proposed a content centric mobile network solution that provides keyword based retrievals. However, the authors do not provide detailed description on how their solution can be made scalable. In this paper, we propose two scalable solutions for keyword based retrievals in content centric networks. Our preliminary simulation results indicate that our solutions are scalable.

The high density ofWiFi Access Points and large unlicensed RF bandwidth over which they operate makes them good candidates to alleviate cellular network's limitations. However, maintaining connectivity through WiFi results in depleting the mobile phone's battery in a very short time. We propose WiZi-Cloud, a system that utilizes a dual WiFi-ZigBee radio on mobile phones and Access Points, supported by WiZi-Cloud protocols, to achieve ubiquitous connectivity, high energy efficiency, real time intra-device/inter-AP handover, that is transparent to the applications. WiZi-Cloud runs mostly on commodity hardware such as Android phones and OpenWrt capable access points. Our extensive set of experiments demonstrate that for maintaining connectivity, WiZi-Cloud achieves more than a factor of 11 improvement in energy consumption in comparison with energy-optimized WiFi, and a factor of 7 in comparison with GSM. WiZi-Cloud has a better coverage than WiFi, and a low delay resulting in a good Mean Opinion Score (MOS) of 4.26 for a VoIP US cross-country communication.

This paper proposes a new packet scheduling algorithm for access points in a crowded 802.11 WLAN. Our goal is to improve the performance of efficiency (measured by packet response time or throughput) and fairness which often conflict with each other. Our solution aggregates both metrics and leverages the balance between them. The basic idea is to let the AP allocate different time windows for serving each client. According to the observed traffic, our algorithm dynamically shifts the weight between efficiency and fairness and strikes to improve the preferred metric without excessively degrading the other one. A valid queuing model is developed to evaluate the new algorithm's performance. Using trace-driven simulations, we show that our algorithm successfully balances the trade off between the efficiency and the fairness in a busy WLAN.

We investigate the resiliency of IEEE802.11 rate adaptation algorithms (RAA) against smart jamming attacks. We consider several classes of state-of-the-art RAAs that include the SampleRate, ONOE, AMRR, and the RAA used in Atheros Microsoft Windows XP driver. We model the behavior of these algorithms, and show the existence of very efficient attacks that exploit RAA-specific vulnerabilities as well as the inherent weaknesses that exist in the design of IEEE802.11 MAC and link layer protocol: in particular the overt packet rate information being transmitted, predictable rate selection mechanism, performance anomaly caused by the equiprobability of transmissions among all nodes regardless of the data rates being employed, and the lack of interference differentiation from poor link quality by IEEE802.11 RAAs. In this work, we present algorithms that determine optimal jamming strategies against RAAs for a given jamming budget, and experimentally demonstrate the efficiency of these smart jamming attacks, which can be orders of magnitude more efficient than naive jamming. For example, in the case of SampleRate, eight reactive jamming pulses every second are sufficient to achieve the same network throughput degradation achieved by a periodic jammer with the jamming energy cost 100 times higher. Some of the RAAs react even worse to smart jamming attacks; ONOE in particular suffers from the phenomenon of congestion collapse where the nodes fail to recover from the lowest data rate even after the jammer stops jamming. At the end, we summarize fundamental reasons behind such RAA vulnerabilities and propose a preliminary set of mitigation techniques. We leave the experimental demonstration of the efficiency of the proposed mitigation mechanisms for future work.

We consider a hybrid two-tiered sensor network consisting of regular sensors and special sensors with large storage capacity, called storage nodes. In this structure, regular sensors "push” their raw data to nearby storage nodes and the sink diffuses queries only to storage nodes and "pull” the reply from them. We investigate security and privacy threats when the sensor network is deployed in an untrusted or hostile environment. The major concern is that storage nodes might easily become the target for the adversary to compromise due to their important role. A compromised storage node may leak the data stored there to the adversary breaching the data privacy. Also, it may send wrong information as the reply to a query breaking the data integrity. This paper focuses on range query, a fundamental operation in a sensor network. The solution framework includes a privacy-preserving storage scheme which utilizes a bucketing technique to mix the data in a certain range, and a verifiable query protocol which employs encoding numbers to enable the sink to validate the reply. We further study the performance of event detection, an application implemented by range query. Our simulation results illustrate that our schemes are efficient for communication and effective for privacy and security protection.

This paper considers a category of rogue access points (APs) that pretend to be legitimate APs to lure users to connect to them. We propose a practical timing-based technique that allows the user to avoid connecting to rogue APs. Our detection scheme is a client-centric approach that employs the round trip time between the user and the DNS server to independently determine whether an AP is a rogue AP without assistance from the WLAN operator. We implemented our detection technique on commercially available wireless cards to evaluate their performance. Extensive experiments have demonstrated the accuracy, effectiveness, and robustness of our approach. The algorithm achieves close to 100 percent accuracy in distinguishing rogue APs from legitimate APs in lightly loaded traffic conditions, and larger than 60 percent accuracy in heavy traffic conditions. At the same time, the detection only requires less than 1 second for lightly-loaded traffic conditions and tens of seconds for heavy traffic conditions.

Radio Frequency IDentification (RFID) technology has attracted much attention due to its variety of applications, e.g., inventory control and object tracking. One important problem in RFID systems is how to quickly estimate the number of distinct tags without reading each tag individually. This problem plays a crucial role in many real-time monitoring and privacy-preserving applications. In this paper, we present an efficient and anonymous scheme for tag population estimation. This scheme leverages the position of the first reply from a group of tags in a frame. Results from mathematical analysis and extensive simulation demonstrate that our scheme outperforms other protocols proposed in the previous work.

RFID is an emerging technology with many potential applications such as inventory management for supply chain. In practice, these applications often need a series of continuous scanning operations to accomplish a task. For example, if one wants to scan all the products with RFID tags in a large warehouse, given a limited reading range of an RFID reader, multiple scanning operations have to be launched at different locations to cover the whole warehouse. Usually, this series of scanning operations are not completely independent as some RFID tags can be read by multiple processes. Simply scanning all the tags in the reading range during each process is inefficient because it collects a lot of redundant data and consumes a long time. In this paper, we develop efficient schemes for continuous scanning operations defined in both spatial and temporal domains. Our basic idea is to fully utilize the information gathered in the previous scanning operations to reduce the scanning time of the succeeding ones. We illustrate in the evaluation that our algorithms dramatically reduce the total scanning time when compared with other solutions.

In this paper we consider how to efficiently identify tags on the moving conveyor. Considering conditions like the path loss and multi-path effect in realistic settings, we first propose a probabilistic model for RFID tag identification. Based on this model, we propose efficient solutions to identify moving RFID tags, according to the fixed-path mobility on the conveyor. A dynamic program based solution and an adaptive solution are proposed to select optimized frame sizes during the query cycles. Simulation results indicate that by leveraging the probabilistic model our solutions can achieve much better performance than using parameters for the ideal propagation situations.

As a major component of Internet routing infrastructure, the Border Gateway Protocol (BGP) is vulnerable to malicious attacks. While Secure BGP (S-BGP) provides a comprehensive framework to secure BGP, its high computational cost and low incremental deployment benefits seriously impede its wide usage in practice. Using a lightweight symmetric signature scheme, SPV is much faster than S-BGP. However, the speed boost comes at the price of prohibitively large signatures. Aggregated path authentication reduces the overhead of securing BGP in terms of both time and space, but the speed improvement is still limited by public key computation. In this paper, we propose a keychain-based signature scheme called KC-x. It has low CPU and memory overheads and provides strong incentive for incremental deployment on the Internet. As a generic framework, KC-x has the flexibility of using different signature algorithms, which can even co-exist in a hybrid deployment. We investigate two implementations of KC-x: KC-RSA based on RSA and KC-MT based on Merkle hash tree. Using real BGP workloads, our experimental results show that KC-RSA is as efficient as SAS-V (the most efficient software approach for aggregated path authentication), and KC-MT is even three times faster than SPV with 40% smaller signatures. Through the hybrid deployment of KC-MT and KC-RSA, KC-x can achieve both small signature and high processing rate for BGP speakers.

In this article, we present Microsearch, a search system suitable for embedded devices used in ubiquitous computing environments. Akin to a desktop search engine, Microsearch indexes the information inside a small device, and accurately resolves a user's queries. Given the limited hardware, conventional search engine design and algorithms cannot be used. We adopt Information Retrieval (IR) techniques for query resolution, and proposed a new space-efficient top- k query resolution algorithm. A theoretical model of Microsearch is given to better understand the trade-offs in design parameters. Evaluation is done via actual implementation on off-the-shelf hardware.

Data storage has become an important issue in sensor networks as a large amount of collected data need to be archived for future information retrieval. Storage nodes are introduced in this paper to store the data collected from the sensors in their proximities. The storage nodes alleviate the heavy load of transmitting all data to a central place for archiving and reduce the communication cost induced by the network query. The objective of this paper is to address the storage node placement problem aiming to minimize the total energy cost for gathering data to the storage nodes and replying queries. We examine deterministic placement of storage nodes and present optimal algorithms based on dynamic programming. Further, we give stochastic analysis for random deployment and conduct simulation evaluation for both deterministic and random placements of storage nodes.

As RFID tags become more widespread, new approaches for managing larger numbers of RFID tags will be needed. In this paper, we consider the problem of how to accurately and efficiently monitor a set of RFID tags for missing tags. Our approach accurately monitors a set of tags without collecting IDs from them. It differs from traditional research which focuses on faster ways for collecting IDs from every tag. We present two monitoring protocols, one designed for a trusted reader and the other for an untrusted reader.

This paper considers a category of rogue access points (APs) that pretend to be legitimate APs to lure users to connect to them. We propose a practical timing based technique that allows the user to avoid connecting to rogue APs. Our method employs the round trip time between the user and the DNS server to independently determine whether an AP is legitimate or not without assistance from the WLAN operator. We implemented our detection technique on commercially available wireless cards to evaluate their performance.

As RFID tags become more widespread, new approaches for managing larger numbers of RFID tags will be needed. In this paper, we consider the problem of how to accurately and efficiently monitor a set of RFID tags for missing tags. Our approach accurately monitors a set of tags without collecting IDs from them. It differs from traditional research which focuses on faster ways for collecting IDs from every tag. We present two monitoring protocols, one designed for a trusted reader and another for an untrusted reader.

While symmetric-key schemes are efficient in processing time for sensor networks, they generally require complicated key management, which may introduce large memory and communication overhead. On the contrary, public-key based schemes have simple and clean key management, but cost more computational time. The recent progress of elliptic curve cryptography (ECC) implementation on sensors motivates us to design a public-key scheme and compare its performance with the symmetric-key counterparts. This paper builds the user access control on commercial off-the-shelf sensor devices as a case study to show that the public-key scheme can be more advantageous in terms of the memory usage, message complexity, and security resilience. Meanwhile, our work also provides insights in integrating and designing public-key based security protocols for sensor networks.

We consider a sensor network that is not fully trusted and ask the question how we preserve privacy for the collected data and how we verify the data reply from the network. We explore the problem in the context of a network augmented with storage nodes and target at range query. We use bucketing scheme to mix the data for a range, use message encryption for data integrity, and employ encoding numbers to prevent the storage nodes from dropping data.

As RFID tags are increasingly attached to everyday items, it quickly becomes impractical to collect data from every tag in order to extract useful information. In this paper, we consider the problem of identifying popular categories of RFID tags out of a large collection of tags, without reading all the tag data. We propose two algorithms based on the idea of group testing, which allows us to efficiently derive popular categories of tags. We evaluate our solutions using both theoretical analysis and simulation.

With the increased popularity of RFID applications, different authentication schemes have been proposed to provide security and privacy protection for users. Most recent RFID protocols use a central database to store the RFID tag data. The RFID reader first queries the RFID tag and returns the reply to the database. After authentication, the database returns the tag data to the reader. In this paper, we propose a more flexible authentication protocol that provides comparable protection without the need for a central database. We also suggest a protocol for secure search for RFID tags. We believe that as RFID applications become widespread, the ability to securely search for RFID tags will be increasingly useful.

As the major component of Internet routing infrastructure, the Border Gateway Protocol (BGP) is vulnerable to malicious attacks. While Secure BGP (S-BGP) provides a comprehensive framework to secure BGP, its high computational cost and low incremental deployment benefits seriously impede its wide usage in practice. Using a lightweight symmetric signature scheme, SPV is much faster than S-BGP. However, the speed boost comes at the price of prohibitively large signatures. Aggregated path authentication reduces the overhead of securing BGP in terms of both time and space, but the speed improvement is still limited by public key computation. In this paper, we propose a simple key chain-based signature scheme called KC-x, which has low CPU and memory overheads and provides strong incentive for incremental deployment over the Internet. As a generic framework, KC-x has the flexibility of using different signature algorithms. We implement two realizations of KC-x. One is based on RSA called KC-RSA, and the other is based on Merkle hash tree called KC-MT. After characterizing the overheads of KC-RSA and KC-MT, we evaluate their performance with real BGP workloads. Our experimental results show that KC-RSA is as efficient as SAS-V, and KC-MT is even 3-fold faster than SPV with a 40% smaller signature. Through the hybrid deployment of KC-MT and KC-RSA, KC-x can achieve both small signature and high processing rate for BGP speakers.

Outlier detection has many important applications in sensor networks, e.g., abnormal event detection, animal behavior change, etc. It is a difficult problem since global information about data distributions must be known to identify outliers. In this paper, we use a histogram-based method for outlier detection to reduce communication cost. Rather than collecting all the data in one location for centralized processing, we propose collecting hints (in the form of a histogram) about the data distribution, and using the hints to filter out unnecessary data and identify potential outliers. We show that this method can be used for detecting outliers in terms of two different definitions. Our simulation results show that the histogram method can dramatically reduce the communication cost.

With the increasing popularity of RFID applications, different authentication schemes have been proposed to provide security and privacy protection to users. Most recent RFID protocols use a central database to store the RFID tag data. An RFID reader first queries the RFID tag and returns the reply to the database. After authentication, the database returns the tag data to the reader. In this paper, we proposed a more flexible authentication protocol that provides comparable protection without the need for a central database. We also suggest a protocol for secure search for RFID tags. We believe that as RFID applications become widespread, the ability to search for RFID tags will be increasingly useful

Data storage has become an important issue in sensor networks as a large amount of collected data need to be archived for future information retrieval. This paper introduces storage nodes to store the data collected from the sensors in their proximities. The storage nodes alleviate the heavy load of transmitting all the data to a central place for archiving and reduce the communication cost induced by the network query. This paper considers the storage node placement problem aiming to minimize the total energy cost for gathering data to the storage nodes and replying queries. We examine deterministic placement of storage nodes and present optimal algorithms based on dynamic programming. Further, we give stochastic analysis for random deployment and conduct simulation evaluation for both deterministic and random placements of storage nodes.

Summary form only given. Client side caches form a large space for Web caching that, if properly utilized, can significantly improve the hit ratio. Conventional peer-to-peer Web caching schemes fail to consider several critical issues. Some rely on a centralized proxy server for coordination. Most do not consider the frequent arrival and departure of client platforms. We propose a decentralized, peer-to-peer Web caching scheme in a corporate network. Without proxy servers, each client shares its local cache contents with the others via structured peer-to-peer routing protocols. We design a new replacement policy specific to peer-to-peer systems and consider security and fault tolerance in our approach. Trace-driven simulations show that our scheme is more efficient, secure, and reliable than the existing approaches.