As one of the most popular cloud services, data storage has attracted great attention in recent research efforts. Key-value (k-v) stores have emerged as a popular option for storing and querying billions of key-value pairs. So far, existing methods have been deterministic. Providing such accuracy, however, comes at the cost of memory and CPU time. In contrast, we present an approximate k-v storage for cloud-based systems that is more compact than existing methods. The tradeoff is that it may, theoretically, return errors. Its design is based on the probabilistic data structure called “bloom filter”, where we extend the classical bloom filter to support key-value operations. We call the resulting design as the kBF (key-value bloom filter). We further develop a distributed version of the kBF (d-kBF) for the unique requirements of cloud computing platforms, where multiple servers cooperate to handle a large volume of queries in a load-balancing manner. Finally, we apply the kBF to a practical problem of implementing a state machine to demonstrate how the kBF can be used as a building block for more complicated software infrastructures.

Power optimization has become a key challenge in the design of large-scale enterprise data centers. Existing research efforts focus mainly on computer servers to lower their energy consumption, while only few studies have tried to address data center networks (DCNs), which can account for 10-20 percent of the total energy consumption of a data center. In this paper, we propose CARPO, a correlation-aware power optimization algorithm that dynamically consolidates traffic flows onto a small set of links and switches in a DCN and then shuts down unused network devices for energy savings. In sharp contrast to existing work, CARPO is designed based on a key observation from the analysis of real DCN traces that the bandwidth demands of different flows do not peak at exactly the same time. As a result, if the correlations among flows are considered in consolidation, more energy savings can be achieved. In addition, CARPO integrates traffic consolidation with link rate adaptation for maximized energy savings. We implement CARPO on a hardware testbed composed of 10 virtual switches configured with a production 48-port OpenFlow switch and 8 servers. Our empirical results with traces from Wikipedia and Yahoo! data centers demonstrate that CARPO can save up to 50 percent of network energy for a DCN, while having only negligible delay increases. CARPO also outperforms two state-of-the-art baselines by 19.6 and 95 percent on energy savings, respectively. Our simulation results with a large-scale DCN also show that CARPO can achieve more energy savings than the baselines for typical DCN topologies, such as fat tree and BCube.

In many network applications, accurate traffic measurement is critical for bandwidth management with QoS requirements, and detecting security threats such as DoS (Denial of Service) attacks. In such cases, traffic is usually modeled as a collection of flows, which are identified based on certain features such as IP address pairs. One central problem is to identify those "heavy hitter" flows, which account for a large percentage of total traffic, e.g., at least 0.1% of the link capacity. However, the challenge for this goal is that keeping an individual counter for each flow is too slow, costly, and non-scalable. In this paper, we describe a novel data structure called the Probabilistic Bloom Filter (PBF), which extends the classical bloom filter into the probabilistic direction, so that it can effectively identify heavy hitters. We analyze the performance, tradeoffs, and capacity of this data structure. Our study also investigates how to calibrate this data structure's parameters. We also develop two extensions of the basic form of the PBF for more flexible application needs. We use real network traces collected on a Web query server and a backbone router to test the performance of the PBF, and demonstrate that this method can accurately keep track of all objects' frequencies, including websites and flows, so that heavy hitters can be identified with constant time computational complexity and low memory overhead.

Our work in this paper stems from our insight that recent research efforts on open vehicle routing (OVR) problems, an active area in operations research, are based on similar assumptions and constraints compared to sensor networks. Therefore, it may be feasible that we could adapt these techniques in such a way that they will provide valuable solutions to certain tricky problems in the wireless sensor network (WSN) domain. To demonstrate that this approach is feasible, we develop one data collection protocol called EDAL, which stands for Energy-efficient Delay-aware Lifetime-balancing data collection. The algorithm design of EDAL leverages one result from OVR to prove that the problem formulation is inherently NP-hard. Therefore, we proposed both a centralized heuristic to reduce its computational overhead and a distributed heuristic to make the algorithm scalable for large-scale network operations. We also develop EDAL to be closely integrated with compressive sensing, an emerging technique that promises considerable reduction in total traffic cost for collecting sensor readings under loose delay bounds. Finally, we systematically evaluate EDAL to compare its performance to related protocols in both simulations and a hardware testbed.

Key-value (k-v) storage has been used as a crucial component for many network applications, such as social networks, online retailing, and cloud computing. Such storage usually provides support for operations on key-value pairs, and can be stored in memory to speed up responses to queries. So far, existing methods have been deterministic: they will faithfully return previously inserted key-value pairs. Providing such accuracy, however, comes at the cost of memory and CPU time. In contrast, in this paper, we present an approximate k-v storage that is more compact than existing methods. The tradeoff is that it may, theoretically, return a null value for a valid key with a low probability, or return a valid value for a key that was never inserted. Its design is based on the probabilistic data structure called the “Bloom Filter”, which was originally developed to test element membership in sets. In this paper, we extend the bloom filter concept to support key-value operations, and demonstrate that it still retains the compact nature of the original bloom filter. We call the resulting design as the kBF (key-value bloom filter), and systematically analyze its performance advantages and design tradeoffs. Finally, we apply the kBF to a practical problem of implementing a state machine in network intrusion detection to demonstrate how the kBF can be used as a building block for more complicated software infrastructures.

In many wireless sensor network (WSN) applications, a subset of nodes (source nodes) are selected to sense the environment, generate data, and transmit them back to the sink over multiple hops. Many previous research efforts have tried to achieve trade-offs in terms of delay, energy cost, and load balancing for such data collection tasks. Our work in this paper stems from the insight that, recent research efforts on open vehicle routing (OVR) problems, an active area in operations research, are based on similar assumptions and constraints compared to sensor networks. This insight motivates us to adapt these techniques so that we can solve or prove certain challenging problems in WSN applications. To demonstrate that this approach is feasible, we develop one data collection protocol called EDAL, which stands for Energy-efficient Delay-aware Lifetime-balancing data collection. The algorithm design of EDAL borrows one research result from OVR to prove that its problem formulation is inherently NP-hard. We then proposed both a centralized heuristic to reduce its computational overhead, and a distributed heuristic to make the algorithm scalable for large scale network operations. We also develop EDAL to be closely integrated with compressive sensing, an emerging technique that promises considerable reduction in total traffic cost for collecting sensor readings under loose delay bounds. Finally, we systematically evaluate EDAL to demonstrate its performance superiority compared to related protocols.

Multi-channel communications can effectively reduce channel competition and interference in a wireless sensor network and thus achieve increased throughput and improved end-to-end delay guarantees with reduced power consumption. However, existing work relies only on a small number of orthogonal channels, resulting in degraded performance when a large number of data flows need to be transmitted on different channels. In this article, we conduct empirical studies to investigate interferences among overlapping channels. Our results show that overlapping channels can also be utilized for improved real-time performance if the node transmission power is carefully configured. In order to minimize the overall transmission power consumption of a network with multiple data flows under end-to-end delay constraints, we formulate a constrained optimization problem to configure the transmission power level of every node and assign overlapping channels to different data flows. Since the optimization problem has an exponential computational complexity, we then present a heuristic algorithm designed based on simulated annealing to find a suboptimal solution. Our extensive empirical results on a 33-mote testbed demonstrate that our algorithm achieves better real-time performance and less power consumption than two baselines, including a scheme using only orthogonal channels.

Power optimization has become a key challenge in the design of large-scale enterprise data centers. Existing research efforts focus mainly on computer servers to lower their energy consumption, while only few studies have tried to address the energy consumption of data center networks (DCNs), which can account for 20% of the total energy consumption of a data center. In this paper, we propose CARPO, a correlation-aware power optimization algorithm that dynamically consolidates traffic flows onto a small set of links and switches in a DCN and then shuts down unused network devices for energy savings. In sharp contrast to existing work, CARPO is designed based on a key observation from the analysis of real DCN traces that the bandwidth demands of different flows do not peak at exactly the same time. As a result, if the correlations among flows are considered in consolidation, more energy savings can be achieved. In addition, CARPO integrates traffic consolidation with link rate adaptation for maximized energy savings. We implement CARPO on a hardware testbed composed of 10 virtual switches configured with a production 48-port OpenFlow switch and 8 servers. Our empirical results with Wikipedia traces demonstrate that CARPO can save up to 46% of network energy for a DCN, while having only negligible delay increases. CARPO also outperforms two state-of-the-art baselines by 19.6% and 95% on energy savings, respectively. Our simulation results with 61 flows also show the superior energy efficiency of CARPO over the baselines.

With the widespread use of wireless sensor networks (WSN), more types of applications are emerging. However, controlling a deployed wireless sensor network after deployment still requires expertise on embedded system programming and administration. In this paper, we study how to exploit the widely available smartphones to reduce these restrictions on users' expertise. In particular, we present a system called PhoneCon, which stands for Voice-driven SmartPhone Controllable Wireless Sensor Networks. Through PhoneCon, users may simply speak to their phones to operate a deployed wireless sensor network, such as getting the status of deployed motes, without being exposed to any of system or programming level details. We have implemented PhoneCon on Android phones for a testbed of MicaZ sensor nodes. Our evaluation results show that PhoneCon can interpret users' intentions well enough through the microphone and perform corresponding actions with acceptable delays.

Dynamic spectrum access has become a promising technique to fully utilize the scarce spectrum resources. However, spectrum allocation schemes with high efficiency and Quality of Service (QoS) guarantee for the primary users have yet to be designed. In this paper, two novel dynamic spectrum access schemes are proposed. The proposed schemes are based on continuous-time Markov chains (CTMC), through which the interactions between primary and secondary users are explicitly modeled. The effects of sensing errors (i.e. miss-detection and false alarm) are taken into consideration. Since miss-detection may lead to collision between primary and secondary users and false alarm will leave spectrum opportunities unused, we derive the optimal access probabilities for each secondary user, so that the QoS of primary user in terms of collision probability constraint is guaranteed, and the missing spectrum opportunities caused by false alarm can be utilized by secondary users. Simulation results show that the proposed schemes can guarantee primary user''s QoS effectively. Moreover, the scheme with buffer can improve the channel occupancy remarkably.

It is well known that periodically putting nodes into sleep can effectively save energy in wireless sensor networks, at the cost of increased communication delays. However, most existing work mainly focuses on static sleep scheduling, which cannot guarantee the desired delay when the network conditions change dynamically. In many applications with user-specified end-to-end delay requirements, the duty cycle of every node should be tuned individually at runtime based on the network conditions to achieve the desired end-to-end delay guarantees and energy efficiency. In this paper, we propose DutyCon, a control theory-based dynamic duty cycle control approach. DutyCon decomposes the end-to-end delay guarantee problem into a set of single-hop delay guarantee problems along each data flow in the network. We then formulate the single-hop delay guarantee problem as a dynamic feedback control problem and design the controller rigorously, based on feedback control theory, for analytic assurance of control accuracy and system stability. DutyCon also features a queuing delay adaptation scheme that adapts the duty cycle of each node to unpredictable packet rates, as well as a novel energy balancing approach that extends the network lifetime by dynamically adjusting the delay requirement allocated to each hop. Our empirical results on a hardware testbed demonstrate that DutyCon can effectively achieve the desired tradeoff between end-to-end delay and energy conservation. Extensive simulation results also show that DutyCon outperforms two baseline sleep scheduling protocols by having more energy savings while meeting the end-to-end delay requirements.

Dynamic spectrum access has become a promising approach to fully utilize the scarce spectrum resources. In this paper, two new dynamic spectrum access schemes for secondary users are proposed, which are based on continuous-time Markov chains (CTMC). Both the interactions between primary and secondary users and the effects of imperfect spectrum sensing(i.e. miss-detection and false alarm) are considered in the schemes. Due to the fact that miss-detection would lead to collision between primary and secondary users, we derive the optimal access probabilities for secondary users, so that the QoS of primary users in terms of collision probability is guaranteed. Simulation results show that the proposed dynamic spectrum access approach under proportional fairness criterion achieves much higher fairness over max-throughput criterion. Moreover, the scheme with buffering mechanism can raise the channel occupancy remarkably.

Spectrum occupancy measurements are significant to obtain spectrum utilization, which will conduct the development and deployment of dynamic spectrum access technology. Threshold level setting is one of the most important parts in data processing. Most spectrum occupancy measurement methods adopt fixed threshold (such as experience value) to distinguish signal from noise. These methods can not be operated autonomously and sometimes has low accuracy. To solve the problems, we investigate the data processing technology in spectrum occupancy measurements. Particularly, an automated processing procedure is provided and an adaptive threshold method based on the analysis of measurement data's statistic characteristic is proposed to calculate the spectrum occupancy. Finally, experiments are performed to validate the adaptive threshold method with the data derived from the spectrum measurements of GSM UL/DL band in Beijing. The experiment results indicate that the proposed method realizes the selfadjusting of threshold level setting and decrease the workload of data processing effectively.