Traffic measurement provides indispensable information to many applications in improving network performance. However, the limited on-chip resources face great challenges in measuring millions of flows simultaneously with high accuracy, and the highly skewed traffic distribution further worsens the performance. Although filtering the vast majority of small flows in advance can help to improve the measurement performance, existing filters have limitations in either filtering range or processing overhead. This paper proposes two efficient filters, including Swing-Size Filter for small-size flow filtering and Swing-Spread Filter for small-spread flow filtering. Both provide a flexible and extended filtering range for network traffic measurement. One key to our design is the use of signed counters whose values swing in positive and negative directions to cancel out small-size or small-spread flows, thereby enlarging the filtering range. We show that the proposed filters are highly effective in filtering small flows while keeping the advantages of low memory overhead and processing overhead. They support various measurement tasks and offer guaranteed bounds on the misreport rate. We implement our filters in both software and hardware, with the hardware version developed in P4 language on a programmable switch. Experiments based on real-world Internet traces show that our filters can reduce the flow size and flow spread estimation errors by an order of magnitude and support high throughput.

Adverse clinical events related to unsafe care are among the top ten causes of death in the U.S. Accurate modeling and prediction of clinical events from electronic health records (EHRs) play a crucial role in patient safety enhancement. An example is modeling de facto care pathways that characterize common step-by-step plans for treatment or care. However, clinical event data pose several unique challenges, including the irregularity of time intervals between consecutive events, the existence of cycles, periodicity, multi-scale event interactions, and the high computational costs associated with long event sequences. Existing neural temporal point processes (TPPs) methods do not effectively capture the multi-scale nature of event interactions, which is common in many real-world clinical applications. To address these issues, we propose the cross-temporal-scale transformer (XTSFormer), specifically designed for irregularly timed event data. Our model consists of two vital components: a novel Feature-based Cycle-aware Time Positional Encoding (FCPE) that adeptly captures the cyclical nature of time, and a hierarchical multi-scale temporal attention mechanism, where different temporal scales are determined by a bottom-up clustering approach. Extensive experiments on several real-world EHR datasets show that our XTSFormer outperforms multiple baseline methods.

Non-duplicate sampling (NDS) is a recently proposed technique that selects items from a data stream with probability p only on their first appearance, effectively handling duplicate items. While NDS has shown promise in the network application on flow cardinality measurement by outperforming sketch-based approaches, it faces limitations in distributed environments where traffic flows span multiple measurement points. To address this challenge, this paper proposes distributed non-duplicate sampling (DNDS), which extends NDS to multiple sampling points by ensuring each item is globally selected with probability p exactly once, regardless of where its appearances occur. We present the first comprehensive study of DNDS, focusing on its application on network-wide flow cardinality estimation. We develop an efficient implementation of DNDS with theoretical guarantees and derive optimal parameter settings. We propose two novel DNDS-based solutions for network-wide flow cardinality estimation. Through extensive experimental evaluation using real network traffic traces, we demonstrate the effectiveness of the DNDS implementation and demonstrate that our solutions achieve up to 10× improvement in estimation accuracy compared to state-of-the-art sketch-based methods.

Over 40% of the global population lives within 100 kilometers of the coast, which contributes more than $8 trillion annually to the global economy. Unfortunately, coastal ecosystems are increasingly vulnerable to more frequent and intense extreme weather events and rising sea levels. Coastal scientists use numerical models to simulate complex physical processes, but these models are often slow and expensive. In recent years, deep learning has become a promising alternative to reduce the cost of numerical models. However, progress has been hindered by the lack of a large-scale, high-resolution coastal simulation dataset to train and validate deep learning models. Existing studies often focus on relatively small datasets and simple processes. To fill this gap, we introduce a decade-long, high-resolution ($<$100m) coastal circulation modeling dataset on a real-world 3D mesh in southwest Florida with around 6 million cells. The dataset contains key oceanography variables (e.g., current velocities, free surface level, temperature, salinity) alongside external atmospheric and river forcings. We evaluated a customized Vision Transformer model that takes initial and boundary conditions and external forcings and predicts ocean variables at varying lead times. The dataset provides an opportunity to benchmark novel deep learning models for high-resolution coastal simulations (e.g., physics-informed machine learning, neural operator learning). The code and dataset can be accessed at https://github.com/spatialdatasciencegroup/CoastalBench.

Nearly 900 million people live in low-lying coastal zones around the world and bear the brunt of impacts from more frequent and severe hurricanes and storm surges. Oceanographers simulate ocean current circulation along the coasts to develop early warning systems that save lives and prevent loss and damage to property from coastal hazards. Traditionally, such simulations are conducted using coastal ocean circulation models such as the Regional Ocean Modeling System (ROMS), which usually runs on an HPC cluster with multiple CPU cores. However, the process is time-consuming and energy expensive. While coarse-grained ROMS simulations offer faster alternatives, they sacrifice detail and accuracy, particularly in complex coastal environments. Recent advances in deep learning and GPU architecture have enabled the development of faster AI (neural network) surrogates. This paper introduces an AI surrogate based on a 4D Swin Transformer to simulate coastal tidal wave propagation in an estuary for both hindcast and forecast (up to 12 days). Our approach not only accelerates simulations but also incorporates a physics-based constraint to detect and correct inaccurate results, ensuring reliability while minimizing manual intervention. We develop a fully GPU-accelerated workflow, optimizing the model training and inference pipeline on NVIDIA DGX-2 A100 GPUs. Our experiments demonstrate that our AI surrogate reduces the time cost of$\mathbf{1 2}$-day forecasting of traditional ROMS simulations from 9,908 seconds (on 512 CPU cores) to 22 seconds (on one A100 GPU), achieving over$450 \times$speedup while maintaining high-quality simulation results. This work contributes to oceanographic modeling by offering a fast, accurate, and physically consistent alternative to traditional simulation models, particularly for real-time forecasting in rapid disaster response.

In this paper, we propose LoRaSeek, a lightweight and reliable LoRa denoising framework that enhances signal quality and robustness for neural-enhanced LoRa decoding. LoRaSeek integrates a hybrid architecture combining Convolutional Neural Networks (CNNs), Transformers, and a hierarchical U-Net to effectively capture multi-scale, multidimensional features of LoRa chirp signals. To maintain efficiency, we integrate a lightweight Transformer block that supports various LoRa configurations while keeping computational overhead low. Additionally, we incorporate dual attention-based skip connections to preserve chirp signal properties across different scales. Experiments across diverse LoRa configurations show that LoRaSeek achieves 2.04–3.86 dB signal-to-noise ratio (SNR) gains over standard decoding methods and up to 3.03 dB improvement over state-of-the-art neural-enhanced LoRa decoding methods while reducing model storage by up to 7.4× and inference time by up to 1.6×.

Spread measurement is an essential problem in high-speed networks with broad applications, such as anomaly detection and network telemetry. Network administrators typically need to concurrently monitor the spreads of different types of flows to detect various abnormal behaviors. Although many studies have designed memory-efficient structures, such as sketches, for a specific spread measurement task, they have to deploy multiple sketches to support multiple spread measurement tasks, resulting in significant memory and computational overhead. This paper proposes an efficient multi-task information compression method to simultaneously estimate differently defined flow spreads. We introduce multi-information sampling to capture multi-task spread information from each arriving packet by one pass and store it in off-chip memory, thereby conserving on-chip memory and computational resources. Additionally, we carefully designed a one-access multi-dimensional structure called Supercube to preserve as much spread information as possible while catching up with the line rate, thereby enhancing estimation accuracy. We implement our estimator in hardware using NetFPGA. Experiments based on real Internet traces show that our method reduces the ARE by 83.36% for spread estimation compared to rSkt (SOTA) with 300KB of on-chip memory and increases update throughput by 251.252-fold compared to Supersketch. All source codes are available athttps://github.com/Hanwen808/MIME.

Flood mapping on Earth imagery is crucial for disaster management, but its efficacy is hampered by the lack of high-quality training labels. Given high-resolution Earth imagery with coarse and noisy training labels, a base deep neural network model, and a spatial knowledge base with label constraints, our problem is to infer the true high-resolution labels while training neural network parameters. Traditional methods are largely based on specific physical properties and thus fall short of capturing the rich domain constraints expressed by symbolic logic. Neural-symbolic models can capture rich domain knowledge, but existing methods do not address the unique spatial challenges inherent in flood mapping on high-resolution imagery. To fill this gap, we propose a spatial-logic-aware weakly supervised learning framework. Our framework integrates symbolic spatial logic inference into probabilistic learning in a weakly supervised setting. To reduce the time costs of logic inference on vast high-resolution pixels, we propose a multi-resolution spatial reasoning algorithm to infer true labels while training neural network parameters. Evaluations of real-world flood datasets show that our model outperforms several baselines in prediction accuracy. The code is available at https://github.com/spatialdatasciencegroup/SLWSL.

Rural Internet of Things (IoT) systems connect sensors and actuators in remote areas, serving crucial roles in agriculture and environmental monitoring. Given the absence of networking infrastructure for backhaul in these regions, satellite IoT techniques offer a cost-effective solution for connectivity. However, current satellite IoT architectures often struggle to deliver high performance due to temporal and spatial link challenges. This paper presents SateRIoT, a new network architecture with temporal link estimation and spatial link sharing that fully exploits the capability of space low-cost low-earth-orbit (LEO) IoT satellites and ground low-power wide area (LPWA) IoT techniques in rural areas. First, we introduce a bursty link model that predicts the number of transmittable packets within a transmission window, reducing energy waste from failed uplink transmissions. Moreover, we enhance the model by selecting informative features and optimizing the window length. Additionally, we develop a multi-hop flooding protocol that enables gateways to buffer and share data packets across the network while incorporating a priority data queue to avoid duplicate transmissions. We implement SateRIoT with commercial-off-the-shelf (COTS) IoT satellite and LoRa radios, then evaluate its performance based on real deployment and real-world collected traces. The results show that SateRIoT can consume 3.3X less energy consumption for an individual gateway. Moreover, SateRIoT offers up to a 5.6X reduction in latency for a single packet and a 1.9X enhancement in throughput.

Soil monitoring plays an essential role in agricultural systems. Rather than deploying sensors' antennas above the ground, burying them in the soil is an attractive way to retain a non-intrusive aboveground space. Low Power Wide-Area Network (LPWAN) has shown its long-distance and low-power features for aboveground Internet-of-Things (IoT) communication, presenting a potential of extending to underground cross-soil communication over a wide area, which however has not been investigated before. The variation of soil conditions brings significant signal polarization misalignment, degrading communication reliability. In this paper, we propose Demeter, a low-cost low-power programmable antenna design to keep reliable cross-soil communication automatically. First, we propose a hardware architecture to enable polarization adjustment on commercial-off-the-shelf (COTS) single-RF-chain LoRa radio. Moreover, we develop a low-power programmable circuit to obtain polarization adjustment. We further design an energy-efficient heuristic calibration algorithm and an adaptive calibration scheduling method to keep signal polarization alignment automatically. We implement Demeter with a customized PCB circuit and COTS devices. Then, we evaluate its performance in various soil types and environmental conditions. The results show that Demeter can achieve up to 11.6 dB SNR gain indoors and 9.94 dB outdoors, 4× horizontal communication distance, at least 20 cm deeper underground deployment, and up to 82% energy consumption reduction per day compared with the standard LoRa.

Low Power Wide-Area Network (LPWAN) has shown its long-distance and low-power features for aboveground Internet-of-Things (IoT) communication, presenting a potential to extend to underground cross-soil communication over a wide area, which has not been investigated before. The variation of soil conditions brings significant signal polarization misalignment, degrading communication reliability. We propose Demeter, a low-cost, low-power programmable antenna design to keep reliable cross-soil communication automatically. First, we propose a hardware architecture to enable polarization adjustment on commercial-off-the-shelf (COTS) single-RF-chain LoRa radio. Moreover, we develop a low-power programmable circuit to adjust polarization. We further design an energy-efficient heuristic calibration algorithm to keep signal polarization alignment automatically. We demonstrate Demeter in indoor environments. The antenna is buried in a plastic container filled with gardening soil to simulate the node underground. Meanwhile, we use the COTS LoRa gateway as a receiver to show the RSSI and SNR variations.

Data stream processing holds great potential value in lots of practical application scenarios. This paper studies two new but important patterns for items in data streams, called promising and damping items. The promising items mean that the frequencies of an item in multiple continuous time windows show an upward trend overall, while a slight decrease in some of these windows is allowed. In contrast to promising items exhibiting an increasing trend, the definition of damping items indicates a decreasing trend. Many applications can benefit from the property of promising or damping items, e.g., monitoring latent attacks in computer networks, pre-adjusting bandwidth allocation in communication channels, detecting potential hot events/news, or finding topics that gradually lose momentum in social networks. We first introduce how to accurately find promising items in data streams in real-time under limited memory space. To this end, we propose a novel structure named Scout Sketch, which consists of Filter and Finder. Filter is devised based on the Bloom filter to eliminate the ungratified items with less memory overload; Finder records some necessary information about the potential items and detects the promising items at the end of each time window, where we propose some tailor-made detection operations. We then enhance Scout Sketch (called Scout Sketch+) to adaptively detect both types of promising and damping items simultaneously. Finally, we conducted extensive experiments on four real-world datasets, which show that the F1 Score and throughput of Scout Sketch(+) are about 2.02 and 5.61 times that of the compared solutions. All source codes are available at Github (https://github.com/Aoohhh/ScoutSketch).

Transformers are widely used deep learning architectures. Existing transformers are mostly designed for sequences (texts or time series), images or videos, and graphs. This paper proposes a novel transformer model for massive (up to a million) point samples in continuous space. Such data are ubiquitous in environment sciences (e.g., sensor observations), numerical simulations (e.g., particle-laden flow, astrophysics), and location-based services (e.g., POIs and trajectories). However, designing a transformer for massive spatial points is non-trivial due to several challenges, including implicit long-range and multi-scale dependency on irregular points in continuous space, a non-uniform point distribution, the potential high computational costs of calculating all-pair attention across massive points, and the risks of over-confident predictions due to varying point density. To address these challenges, we propose a new hierarchical spatial transformer model, which includes multi-resolution representation learning within a quad-tree hierarchy and efficient spatial attention via coarse approximation. We also design an uncertainty quantification branch to estimate prediction confidence related to input feature noise and point sparsity. We provide a theoretical analysis of computational time complexity and memory costs. Extensive experiments on both real-world and synthetic datasets show that our method outperforms multiple baselines in prediction accuracy and our model can scale up to one million points on one NVIDIA A100 GPU. The code is available at https://github.com/spatialdatasciencegroup/HST

Per-flow size measurement is key to many streaming applications and management systems, particularly in high-speed networks. Performing such measurement on the data plane of a network device at the line rate requires on-chip memory and computing resources that are shared by other key network functions. It leads to the need for very compact and fast data structures, called sketches, which trade off space for accuracy. Such a need also arises in other application context for extremely large data sets. The goal of sketch design is two-fold: to measure flow size as accurately as possible and to do so as efficiently as possible (for low overhead and thus high processing throughput). The existing sketches can be broadly categorized to multi-update sketches and single update sketches. The former are more accurate but carry larger overhead. The latter incur small overhead but their accuracy is poor. This paper proposes a Single update Sketch with a Variable counter Structure (SSVS), a new sketch design which is several times faster than the existing multi-update sketches with comparable accuracy, and is several times more accurate than the existing single update sketches with comparable overhead. The new sketch design embodies several technical contributions that integrate the enabling properties from both multi-update sketches and single update sketches in a novel structure that effectively controls the measurement error with minimum processing overhead.

Multi-access edge computing achieves better application responsiveness by offloading tasks from end devices to edge servers installed at the vicinity. Practical scenarios, such as post-disaster rescuing and battlefield monitoring, make it attractive to use end devices themselves as edge servers. This, however, introduces a new challenge: Due to mobility and power limitation, the set of edge servers becomes dynamic. As some servers fail, the tasks that run on them will also fail. This paper introduces a new dynamic edge computing model and conducts the first study on robust task offloading which is tolerant to$h$server failures. We propose online primal-dual algorithms that offload tasks as they arrive. We evaluate the performance of our robust task offloading solutions through extensive simulations based on real task sets. The results show that our proposed solutions can well handle edge dynamics and achieve near optimal throughput (above 95 percent) compared to the optimal offline benchmark algorithm.

Per-flow traffic measurement in the high-speed network plays an important role in many practical applications. Due to the limited on-chip memory and the mismatch between off-chip memory speed and line rate, sampling-based methods select and forward a part of flow traffic to off-chip memory, which complements sketch-based solutions in estimation accuracy and online query support. However, most current work uses the same sampling probability for all flows, leading to the waste in storage and communication resources. In practice, different flows often require different sampling rates to meet the same accuracy constraint. This paper presents self-adaptive sampling, a framework to sample each flow with a probability adapted to flow size/spread. Then we propose three algorithms, SAS-LC, SAS-LOG, and SAS-HYB. SAS-LC and SAS-LOG are geared towards per-flow spread estimation and per-flow size estimation by using different compression functions. SAS-HYB combines the advantages of SAS-LC and SAS-LOG, showing higher efficiency when both small flows and large flows are interested. We implement our estimators in hardware using NetFPGA. Experimental results based on real Internet traces show that, compared to the state-of-the-art in per-flow spread estimation, SAS-LC can save around 10% on-chip space and reduce up to 40% communication cost for large flows. In per-flow size estimation, SAS-LOG can save 40% on-chip space and reduce up to 96% communication costs for large flows. Moreover, SAS-HYB’s on-chip memory usage will not be larger than SAS-LC or SAS-LOG and can save up to 19% on-chip space than SAS-LOG when both small flows and large flows are interested.

Flow spread measurement provides fundamental statistics that can help network operators better understand flow characteristics and traffic patterns with applications in traffic engineering, cybersecurity and quality of service. Past decades have witnessed tremendous performance improvement for single-flow spread estimation. However, when dealing with numerous flows in a packet stream, it remains a significant challenge to measure per-flow spread accurately while reducing memory footprint. The goal of this paper is to introduce new multi-flow spread estimation designs that incur much smaller processing overhead and query overhead than the state of the art, yet achieves significant accuracy improvement in spread estimation. We formally analyze the performance of these new designs. We implement them in both hardware and software, and use real-world data traces to evaluate their performance in comparison with the state of the art. The experimental results show that our best sketch significantly improves over the best existing work in terms of estimation accuracy, packet processing throughput, and online query throughput.

On a high-speed link, there may be tens of millions of IP packets per second and millions of active flows. Maintaining the state of each flow is a fundamental task underlying many network functions, such as load balancing and network anomaly detection. There are two important kinds of per-flow states: per-flow size (e.g., the number of packets received by an arbitrary destination IP) and per-flow cardinality (e.g., the number of distinct source IP addresses that contacted each destination IP). In this paper, we focus on the latter kind of states, and define a new problem: online query of per-flow cardinality, in which we query any given flow’s cardinality entirely on the data plane with low time complexity. For this problem, we propose three solutions named On-vHLL, Ton-vHLL and Aton-vHLL, whose time cost are$O(1)$even for the query operation. Our proposed techniques are three folds. First, we redesign the traditional vHLL with new supplementary data structures called incremental update units (IUUs). When a certain flow’s cardinality is queried, these IUUs can avoid scanning the whole data structure and reduce the time complexity to$O(1)$. Second, we apply a HLL register compression technique called TailCut to the On-vHLL sketch, which can save memory cost by 50%. Third, we add a prefilter based on min-heap, alongside the Ton-vHLL sketch. The prefilter is to give each currently sampled top-$k$superspreader a dedicated HyperLogLog estimator for better accuracy. It can also absorb the superspreaders’ packets bypassing the sketch. We evaluate our new sketches by simulation with CAIDA traces. The results show that our On-vHLL, Ton-vHLL and Aton-vHLL sketches need about 5 memory accesses per packet. The time cost of query operation decreases by hundreds of times than the traditional vHLL that can only be queried offline. Meanwhile, the estimation error of flow spread by our Aton-vHLL is comparable to vHLL.

In computer networks, traffic measurement is a module in a network probe to measure flow-level statistics from an IP packet stream, which are the basis for network performance monitoring and malicious activity detection. This module extracts the flow IDs from incoming IP packets, classifies packets into flows, and counts the number of packets (or bytes) for each flow. It is a great challenge to measure the per-flow statistics for a high-speed network device, using only the size-limited SRAM on its line cards. Therefore, many algorithms using sublinear memory have been proposed, such as CountMin and CountSketch. However, most of previous algorithms are designed for specific measurement tasks. To obtain multiple types of statistics, people have to deploy multiple sketches, which demands more resources of a network device. It is useful to design a universal sketch that can track not only the top-$k$largest individual flows (called heavy hitters) but also the overall traffic distribution statistics (called moments). Prior work named UnivMon successfully tackled this ambitious quest. However, it incurs large and variable per-packet processing overhead, which may result in a significant throughput bottleneck in high-rate packet stream, given that each packet requires 33 hashes and 32 memory accesses on average and many times of that in the worst case. To address this performance issue, we fundamentally redesign the solution architecture from hierarchical sampling to new progressive sampling and from CountSketch to new GenericCM, which ensure that per-packet overhead is a small constant (5 hashes and 8 memory accesses in the worst case), making it more suitable for online operations, especially for hardware pipeline implementation. This new design also makes effort to reduce memory footprint or equivalently improve measurement accuracy under the same memory. Our experiments show that our solution reduces measurement error by roughly 98.1% for second-order moment and by 91.5% for entropy, when given the same 0.2MB memory as UnivMon.

Traffic measurement is key to many important network functions. Supporting real-time queries at the individual flow level over networkwide traffic represents a major challenge that has not been successfully addressed yet. This paper provides the first solutions in supporting real-time networkwide queries and allowing a local network function (for performance, security or management purpose) to make queries at any measurement point at any time on any flow’s networkwide statistics, while the packets of the flow may traverse different paths in the network, some of which may not come across the point where the query is made. Our trace-based experiments demonstrate that the proposed solutions significantly outperform the baseline solutions derived from the existing techniques.

Estimating the cardinality of a data stream is a fundamental problem underlying numerous applications such as traffic monitoring in a network or a datacenter, popularity tracking on social media, and cache optimization in proxy servers. Existing solutions suffer from high processing/query overhead or memory in-efficiency, which prevents them from operating online for data streams with very high arrival rates. This paper takes a new solution path different from the prior art and proposes a self-morphing bitmap, which combines operational simplicity with structural dynamics, allowing the bitmap to be morphed in a series of steps with an evolving sampling probability that automatically adapts to different stream sizes. We evaluate the self-morphing bitmap theoretically and experimentally. The results demonstrate that it significantly outperforms the prior art.

Internet-of-Things (IoT) aims to connect billions of low-date rate and energy-constrained end-devices in the near future. Although many IoT systems have been commercialized, most of them focus on home and body scale applications. To establish a low-cost IoT at the city scale, LoRa Wide Area Networks (LoRaWAN) have become attractive in recent years due to their desirable kilometer or even longer communication distance with low energy consumption. However, due to the expensive cost of densely deploying end-nodes, the understanding of LoRa link behavior is still coarse-grained, and hard to fully realize the link dynamics, networking coverage, and localization accuracy of LoRaWAN in an urban environment. This paper shows a fine-grained LoRa link-level measurement via mobile end-nodes. We deploy two gateways and six mobile end-nodes and collect data packets over four months at a$6\times 6\ km^{2}$urban area. The evaluation mainly focuses on answering three questions: 1) Does a LoRa link stably perform in both spatial and temporal dimensions? 2) How large area can be covered for reliable communication by each gateway in the urban environment? 3) What accuracy can be achieved to localize an end-node through LoRa links? According to our measurement, our key findings are 1) The spatial and temporal behavior of LoRa links is quite dynamic due to the different types of land covers and the frequent micro-environment changes in the urban areas; 2) Each gateway can cover about 11.3 km2area and marginal SNR gains (e.g., 2 dB) of LoRa links are efficient enough to enlarge 32.6% coverage area of a gateway; and 3). The median localization error is about 400 m. Without densely deployed LoRa gateways, the SOTA LoRa localization can support road-level localization, even when an end node is close to one of the gateways.

Detecting heavy hitters that constitute the majority of network traffic is a critical task in network measurement. However, the highly skewed network traffic and the size-limited on-chip memory pose great challenges for heavy-hitter detection. The prior arts either use sketches to track all flows or maintain a fix-sized tracking list for recording elephant flows, resulting in limited detection precision or time-consuming tracking list exchanges. This paper presents HeavyTracker, an efficient algorithm that detects heavy hitters based on a count-with-threshold strategy. A two-dimensional tracker unit array is employed in our design to capture the heavy hitters, where each flow is randomly mapped to one unit in all rows. The tracker unit is designed to accept many flows and precisely report the largest two with frequencies that reach a predefined threshold. This design eliminates the frequent and time-consuming exchanges for maintaining the tracking list, allowing us to use a hash table to track the reported elephant flows. Experimental results based on real Internet traces show that HeavyTracker achieves a high $\mathbf{F}_{\beta}$-Score of threshold-t detection (0.97) and over 99% precision of top-k detection under a tight memory size. Besides, it reduces the frequency estimation error by 97.4% compared to the state-of-the-art.

Per-flow spread measurement in high-speed networks can provide indispensable information to many practical applications. However, it is challenging to measure millions of flows at line speed because on-chip memory modules cannot simultaneously provide large capacity and large bandwidth. The prior studies address this mismatch by entirely using on-chip compact data structures or utilizing off-chip space to assist limited on-chip memory. Nevertheless, their on-chip data structures record massive transient elements, each of which only appears in a short time interval in a long-period measurement task, and thus waste significant on-chip space. This paper presents short-term memory sampling, a novel spread estimator that samples new elements while only holding elements for short periods. Our estimator can work with tiny on-chip space and provide accurate estimations for online queries. The key of our design is a short-term memory duplicate filter that reports new elements and filters duplicates effectively while allowing incoming elements to override the stale elements to reduce on-chip memory usage. We implement our approach on a NetFPGA-equipped prototype. Experimental results based on real Internet traces show that, compared to the state-of-the-art, short-term memory sampling reduces up to 99% of on-chip memory usage when providing the same probabilistic assurance on spread-estimation error.

Per-flow size measurement is a fundamental problem in network engineering and plays a pivotal role in many practical applications. Constrained by on-chip memory resources and packet processing speed, most existing solutions use compact data structures (i.e., sketches) to perform the line-speed measurement. However, sketches share the record units (bits/counters) among flows, inevitably introducing noises to each flow’s measurement result. Although they adopt an average denoising strategy to remove noises from the raw estimations, the accuracy for medium flows is still lacking. This paper complements the prior art and presents a novel per-flow size measurement method, Adaptive Denoising (ADN), which can provide more accurate estimates for online and offline queries. For an online query, we use the collected flow records for real-time estimation. For an offline query, we model the propagation of noises based on the optimization algorithm to produce flow size estimation with much better accuracy. Experimental results based on real Internet traffic traces show that our measurement solutions outperform the state-of-the-art approaches and reduce the mean absolute error by around one order of magnitude under the same on-chip memory usage.

Identifying item-item and user-item interactions is an essential requirement of many ubiquitous computing applications. Recently methods of physically altering RFID tag hardware have been proposed to enable recognizing certain interactions. However, they do not address the problem that when a large number of tags exist in the environment and concurrent interactions may happen, the system may not be able to identify these interactions accurately or efficiently. We propose ChopTags, a low-cost and accurate interaction identification using passive RFID tags, with applications including automatic chess notation, shipment storage tracking, interactive libraries/retail stores/classrooms, and smart conference badges to track the attendees who had conversations. Each ChopTags module contains a passive tag chip and an antenna that are separated and can only be read when the chip is in contact with an antenna (from another pairing ChopTags module). ChopTags costs cheap hardware to scale to many users and items, achieves near 100% accuracy in complex environments, and is easy to use for children, seniors, and others who have difficulty of operating smart devices. We resolve a number of challenges of using ChopTags including improving query throughput/accuracy and identifying concurrent interactions. We build two prototypes based on ChopTags: 1) a chess auto-notation system and 2) a tag array for user interactions. ChopTags allows tracking the moves of 96 tag modules for the chess game with almost 100% accuracy and no prior work can achieve this.

To deal with the ever increasing wireless traffic, we have recently designed a vehicular cognitive capability harvesting network (V-CCHN) architecture to leverage vehicles as an alternative “transmission medium” (i.e., an opportunistic data carrier), besides the wireless spectrum, to effectively transport data from the location where it is collected to the place where it is consumed or utilized in a smart city environment. In the V-CCHN, cognitive radio technologies are utilized so that a large amount of data can be exchanged between vehicles and roadside infrastructure through short-range high-speed transmissions. Considering the limited contact duration and the uncertain activities of primary users, how to facilitate efficient data exchange between vehicles and roadside infrastructure is very challenging. This problem is further complicated by the fact that the mobility of vehicles might not be accurately predicted. In this paper, we propose a probabilistic data prefetching (PDP) scheme for the V-CCHN to address these challenges. By considering the conditional value at risk, we formulate the PDP schematic design as an optimization problem which allows us to obtain the corresponding PDP scheme. Finally, we have conducted extensive study to evaluate the performance of the obtained PDP scheme under various parameter settings.

Intelligent vehicular cyber-physical systems can perform automatic traffic measurement, which provides critical information for transportation engineering. However, one of the biggest challenges in traffic measurement is to protect the vehicles’ location and trajectory privacy, which may be revealed from the recorded traffic data. Prior studies in traffic measurement only offer heuristic privacy protection but lack a precisely defined privacy model. This article proposes an efficient traffic estimator with differential privacy protection. In our design, each road-side unit communicates with the passing vehicles and records their presence in a privacy-preserving data structure. By performing probabilistic analysis on the anonymized records, the proposed method can precisely estimate the number of common vehicles passed by multiple given locations during the given measurement period. Through theoretical analysis, we prove that the proposed method can protect the trajectory privacy of the vehicles with$\epsilon$-differential privacy even when the point privacy has been leaked. We also evaluated our traffic estimator based on a real-world transportation traffic dataset. The evaluation results demonstrate that the proposed estimator can achieve high estimation accuracy and high-level privacy protection through controllable tradeoffs.

Sketches, as a kind of probabilistic data structures, have been considered as the most promising solution for network measurement in recent years. Most sketches do not work well for skewed network traffic. To address this problem, we propose a family of sketch frameworks, namely the Pyramid family. The first member of our Pyramid family is the S-Pyramid framework, which includes two techniques: counter-pair sharing for high accuracy, and word acceleration for fast speed. The second member of our Pyramid family is the Mini-Pyramid framework, which projects the S-Pyramid framework into one counter, bringing more flexibility in application while keeping the accuracy. To demonstrate the generality of our Pyramid family, we apply both frameworks to sketches of CM, CU, Count, and Augmented. To demonstrate the flexibility of the Mini-Pyramid framework, we further apply Mini-Pyramid to SBF and the On-Off sketch. The experimental results show that, the S-Pyramid framework can reduce the ARE by up to 7.12 times compared with the original sketches, while improving the throughput by up to 2.37 times; the Mini-Pyramid framework can reduce the ARE by up to 29.2 times, at the cost of 21.3% lower throughput on average.

Super spreader identification has a lot of applications in network management and security monitoring. It is a more difficult problem than heavy hitter identification because flow spread is harder to measure than flow size due to the requirement of duplicate removal. The prior work either incurs heavy memory overhead or requires heavy computations. This paper designs a new super-spreader monitor capable of identifying all flows whose spreads are greater than a user-specified threshold with a probability that can be arbitrarily set. It introduces a generalized geometric hash function, a generalized geometric counter, and a novel geometric-min filter that blocks out the vast majority of small/medium flows from being tracked, allowing us to focus on a small number of flows in which super spreaders are identified. We provide an analytical way of properly setting the system threshold to meet probabilistically guaranteed identification of super spreaders, and implement it on both hardware (FPGA) and software platforms. We perform extensive experiments based on real Internet traffic traces from CAIDA. The results show that with proper parameter settings, the new monitor can identify more than 99% super spreaders with a low memory requirement, better than the prior art.

Sampling is key to handling mismatch between the line rate and the throughput of a network traffic measurement module. Flow-spread measurement requires non-duplicate sampling, which only samples the elements (carried in packet header or payload) in each flow when they appear for the first time and blocks them for subsequent appearances. The only prior work for non-duplicate sampling incurs considerable overhead, and has two practical limitations: It lacks a mechanism to set an appropriate sampling probability under dynamic traffic conditions, and it cannot efficiently handle multiple concurrent sampling tasks. This paper proposes a virtual filter design for non-duplicate sampling, which reduces the processing overhead by about half and reduces the memory overhead by an order of magnitude or more under some practical settings. It has a mechanism to automatically adapt its sampling probability to the traffic dynamics. It can be modified to handle sampling for multiple independent tasks with different probabilities. We also enhance the virtual filter for flow spread measurement and super spreader detection with a large measurement period.

Estimating the cardinality of a data stream is a fundamental problem underlying numerous applications such as traffic monitoring in a network or a datacenter and query optimization of Internet-scale P2P data networks. Existing solutions suffer from high processing/query overhead or memory in-efficiency, which prevents them from operating online for data streams with very high arrival rates. This paper takes a new solution path different from the prior art and proposes a self-morphing bitmap, which combines operational simplicity with structural dynamics, allowing the bitmap to be morphed in a series of steps with an evolving sampling probability that automatically adapts to different stream sizes. We further generalize the design of self-morphing bitmap. We evaluate the self-morphing bitmap theoretically and experimentally. The results demonstrate that it significantly outperforms the prior art.

Though widely used in industrial and logistic applications, current passive Radio Frequency Identification (RFID) technology still has a fundamental limitation: Individual users who do not carry any reader find it difficult to interact with tagged items, such as retrieving their digital profiles and requesting certain associations with them. Recent proposals to improve the user–item interaction experience rely on special hardware, such as a smartphone-based RFID scanner. This work presents a promising approach to allowing each user to interact with a tagged item using only one passive tag, which is named the Tag Mutual Identification Interface (TagMii). TagMii requires a user to put one’s user tag in physical proximity with an item tag to express certain interactions between the user and item. The key idea behind TagMii is to utilize two experimental observations: (1) inductive coupling for detecting interaction events, and (2) channel similarity for determining the actual interacting tags. We implement TagMii using commodity off-the-shelf RFID devices and conduct experiments in complex environments with rich multipath, mobility, wireless signals, electrical devices, and magnetic fields. The results show that TagMii provides accurate mutual identification. TagMii is a completely new approach for user–item interactions in pervasive environments and enables many user-friendly Internet of Things applications with low cost and convenience.

Internet-connected devices have been surging rapidly during the past years. Many important applications based upon such devices have emerged, such as vehicle tracking systems. These applications often require real-time execution of a large number of computation tasks. Edge computing has shown great potential in processing frequent but less-demanding tasks. Additionally, cloud computing allows for great scalability when substantial computing resources are needed. Edge-cloud computing is a paradigm that combines edge computing and cloud computing. A key problem in edge-cloud computing is how to determine the execution location for each computation task. We propose a dynamic edge-twin computing model in the context of edge-cloud computing. It uses an evaluation mechanism to predict the completion times of the task at both an edge device and a cloud server. The completion time includes data transfer time and computing time and it is determined based on real-time information about the task and the computing environment. The task will be executed by the device with a shorter completion time. We have implemented a vehicle tracking system under the edge-twin model. The experimental results show that the edge-twin model outperforms edge-alone computing and cloud-alone computing.

Traffic measurement provides fundamental statistics for network management functions. To implement the measurement modules on the data plane for real-time query response, modern sketches are designed to work with limited on-die memory allocation from network processors and collect traffic statistics in epochs of a preset length. To handle real-time queries at arbitrary times over traffic in a preceding period${T}$(called${T}$-queries), the prior art sets the epoch length to${T \over n}$and keeps the measurement results in a window of$n - 1$past epochs to support approximate${T}$-queries. Such an approach however drastically increases the memory cost or decreases the accuracy in the query results if the memory allocation is fixed. In this paper, motivated by the concept of offloading in today's edge-cloud computing, we propose a collaborative edge-center traffic measurement model, where the traffic measurement modules at all network devices form the edge, which offloads the traffic measurement results to a measurement center possibly hosted in a datacenter. The center synthesizes the measurements from the past epochs and sends the aggregate results back to the measurement modules to support T-queries. We conduct experiments using real traffic traces to evaluate the performance of the proposed edge-center measurement model. The experimental results demonstrate that the proposed designs significantly outperform the prior art.

Sampling is key to handling mismatch between the line rate and the throughput of a network traffic measurement module. Flow-spread measurement requires non-duplicate sampling, which only samples the elements (carried in packet header or payload) in each flow when they appear for the first time and blocks them for subsequent appearances. The only prior work for non-duplicate sampling incurs considerable overhead, and has two practical limitations: It lacks a mechanism to set an appropriate sampling probability under dynamic traffic conditions, and it cannot efficiently handle multiple concurrent sampling tasks. This paper proposes a virtual filter design for non-duplicate sampling, which reduces the processing overhead by about half and reduces the memory overhead by an order of magnitude or more under some practical settings. It has a mechanism to automatically adapt its sampling probability to the traffic dynamics. It can be extended to solve a new problem called non-duplicate distribution sampling, which samples packets based on a probability distribution to support multiple concurrent measurement tasks.

Machine learning and artificial neural networks (ANNs) have been at the forefront of medical research in the last few years. It is well known that ANNs benefit from big data and the collection of the data is often decentralized, meaning that it is stored in different computer systems. There is a practical need to bring the distributed data together with the purpose of training a more accurate ANN. However, the privacy concern prevents medical institutes from sharing patient data freely. Federated learning and multi-party computation have been proposed to address this concern. However, they require the medical data collectors to participate in the deep-learning computations of the data users, which is inconvenient or even infeasible in practice. In this paper, we propose to use matrix masking for privacy protection of patient data. It allows the data collectors to outsource privacy-sensitive medical data to the cloud in a masked form, and allows the data users to outsource deep learning to the cloud as well, where the ANN models can be trained directly from the masked data. Our experimental results on deep-learning models for diagnosis of Alzheimer's disease and Parkinson's disease show that the diagnosis accuracy of the models trained from the masked data is similar to that of the models from the original patient data.

Per-flow traffic measurement in the high-speed network plays an important role in many practical applications. Due to the limited on-chip memory and the mismatch between off-chip memory speed and line rate, sampling-based methods select and forward a part of flow traffic to off-chip memory, complementing sketch-based solutions in estimation accuracy and online query support. However, most current work uses the same sampling probability for all flows, overlooking that the sampling rates different flows require to meet the same accuracy constraint are different. It leads to a waste in storage and communication resources. In this paper, we present self-adaptive sampling, a framework to sample each flow with a probability adapted to flow size/spread. Then we propose two algorithms, SAS-LC and SAS-LOG, which are geared towards per-flow spread estimation and per-flow size estimation by using different compression functions. Experimental results based on real Internet traces show that, when compared to NDS in per-flow spread estimation, SAS-LC can save around 10% on-chip space and reduce up to 40% communication cost for large flows. Moreover, SAS-LOG can save 40% on-chip space and reduce up to 96% communication cost for large flows than NDS in per-flow size estimation.

In high-speed networks, such as Internet backbone, a router may witness millions of IP packet flows passing through concurrently. Maintaining the state of each flow is a fundamental task underlying many network functions, such as load balancing and network anomaly detection. There are two important kinds of per-flow states: per-flow size (e.g., the number of packets received by an arbitrary destination IP) and per-flow cardinality (e.g., the number of distinct source IP addresses that contacted each destination IP). In this paper, we focus on the latter kind of states, and we propose a new problem: online flow-cardinality query, in which we must query any given flow’s cardinality entirely on the data plane with low time complexity. We propose two solutions named On-vHLL and On-vLLC, whose time cost is $\mathcal{O}(1)$ for the query operation. Our query acceleration techniques are three folds. First, we redesign the traditional vHLL and vLLC with new supplementary data structures called incremental update units. When querying a flow’s cardinality, these units can avoid scanning the whole data structure and reduce the time complexity to $\mathcal{O}(1)$. Second, we adopt LogLogCount estimation formula to avoid floating number calculation. Third, we add a fast path implemented by hash table, alongside the relatively slower On-vHLL or On-vLLC sketch. The fast path can absorb the packets belonging to the top-k superspreaders detected in previous time interval. We evaluate our new sketches by experiments based on CAIDA traffic traces. The results show that our sketches need less than 5 memory accesses per arrival packet. The time cost of our query operation decreases by hundreds of times, and the accuracy of flow cardinality estimation degrades quite modestly by only 20%, as compared with the counterpart vHLL.

Temperature sensing plays a significant role in upholding quality assurance and meeting regulatory compliance in a wide variety of applications, such as fire safety and cold chain monitoring. However, existing temperature measurement devices are bulky, cost-prohibitive, or battery-powered, making item-level sensing and intelligence costly. In this paper, we present a novel tag-based thermometer called Thermotag, which uses a common passive RFID tag to sense the temperature with competitive advantages of being low-cost, battery-free, and robust to environmental conditions. The basic idea of Thermotag is that the resistance of a semiconductor diode in a tag's chip is temperature-sensitive. By measuring the discharging period through the reverse-polarized diode, we can estimate the temperature indirectly. We propose a standards-compliant measurement scheme of the discharging period by using a tag's volatile memory and build a mapping model between the discharging period and temperature for accurate and reliable temperature sensing. We implement Thermotag using a commercial off-the-shelf RFID system, with no need for any firmware or hardware modifications. Extensive experiments show that the temperature measurement has a large span ranging from 0 °C to 85 °C and a mean error of 2.7 °C.

Data streaming has multiple applications on the Internet including traffic measurement and intrusion detection. The bedrock underlying these applications is a set of data streaming algorithms that extract useful information from network packet stream, estimate the needed statistics such as the frequencies of TCP flows, and feed them to application software. Among such algorithms, counting sketches are most prevalent, which are very compact but do so at the cost of errors in their estimations. The dominant error-control method that has been widely accepted for more than a decade is to take the min error from multiple independent estimations. This method produces a positively-biased error and the error can grow large under stringent performance and resource conditions, but no existing work makes an intensive study of this error. This paper investigates the property of the error, which is also known as noise, and claims that it can be measured and removed so as to make the estimations unbiased. We introduce two new ideas, d-smallest noise and artificial data items for measuring the noise. Based on these two ideas, we propose four noise measurement methods. The mathematical analysis and experimental results based on real network traces show that by removing the measured noise, the error of estimations will be reduced to a much lower level than what the state of the art can do.

Measuring flow spread in real time from large, high-rate data streams has numerous practical applications, where a data stream is modeled as a sequence of data items from different flows and the spread of a flow is the number of distinct items in the flow. Past decades have witnessed tremendous performance improvement for single-flow spread estimation. However, when dealing with numerous flows in a data stream, it remains a significant challenge to measure per-flow spread accurately while reducing memory footprint. The goal of this paper is to introduce new multi-flow spread estimation designs that incur much smaller processing overhead and query overhead than the state of the art, yet achieves significant accuracy improvement in spread estimation. We formally analyze the performance of these new designs. We implement them in both hardware and software, and use real-world data traces to evaluate their performance in comparison with the state of the art. The experimental results show that our best sketch significantly improves over the best existing work in terms of estimation accuracy, data item processing throughput, and online query throughput.

Per-flow spread measurement in high-speed networks has many practical applications. It is a more difficult problem than the traditional per-flow size measurement. Most prior work is based on sketches, focusing on reducing their space requirements in order to fit in on-chip cache memory. This design allows the measurement to be performed at the line rate, but it suffers from expensive computation for spread queries (unsuitable for online operations) and large errors in spread estimation for small flows. This paper complements the prior art with a new spread estimator design based on an on-chip/off-chip model. By storing traffic statistics in off-chip memory, our new design faces a key technical challenge to design an efficient online module of non-duplicate sampling that cuts down the off-chip memory access. We first propose a two-stage solution for non-duplicate sampling, which is efficient but cannot handle well a sampling probability that is either too small or too big. We then address this limitation through a three-stage solution that is more space-efficient. Our analysis shows that the proposed spread estimator is highly configurable for a variety of probabilistic performance guarantees. We implement our spread estimator in hardware using FPGA. The experiment results based on real Internet traffic traces show that our estimator produces spread estimation with much better accuracy than the prior art, reducing the mean relative (absolute) error by about one order of magnitude. Moreover, it increases the query throughput by around three orders of magnitude, making it suitable for supporting online queries in real time.

Public-key certificate validation is an important building block for various security protocols for IoT devices, such as secure channel establishment, handshaking, and verifying sensing data authenticity from cloud storage. However, certification validation incurs non-trivial overhead on resource-constrained IoT devices, because it either brings long latency or large cache space. This work proposes to utilize the power of distributed caching and explores the feasibility of using the cache spaces on all IoT devices as a large pool to store validated certificates. We design a Collaborative Certificate Validation (CCV) protocol including a memory-efficient and fast locator for certificate holders, a trust model to evaluate the trustworthiness of devices, and a protocol suite for dynamic update and certificate revocation. Evaluation results show that CCV only uses less than 25% validation time and reduces >90% decryption operations on each device, compared to a recent method. Malicious devices that conduct dishonest validations can be detected by the network using the proposed trust model.

Large software defined networks use a cluster of distributed controllers to process flow requests from a massive number of switches. To cope with traffic dynamics, this paper studies a new problem of how to improve the residual capacity available at the controllers to handle request bursts experienced at the switches. While the total residual capacity is a constant under a given total capacity of all controllers and a given total workload from all switches, this paper considers the residual capacity available to each individual switch, which depends on how the switches are mapped to the controllers for management. We focus on how tomaximize the minimum residual capacity available to any switch. The prior work either provides poor residual capacity or incurs heavy synchronization overhead by simulation results. This paper proposes a new method calledindirect multi-mappingthat achieves both high residual capacity and low synchronization cost. We formally define a non-linear integer optimization problem for max-min residual capacity under indirect multi-mapping. We then approximate the problem as two sub-problems: switch-controller mapping selection and weight assignment for each switch-controller mapping. We solve these sub-problems and formally analyze their approximate factor. We implement the proposed solution on an SDN testbed for experimental studies and use simulations for large-scale investigation. Our evaluation shows that indirect multi-mapping improves the minimum residual capacity by 49.8% on average and reduces the synchronization cost by 41.9-60.3% on average when compared with the alternatives.

Per-flow spread measurement in high-speed networks has many practical applications. It is a more difficult problem than the traditional per-flow size measurement. Most prior work is based on sketches, focusing on reducing their space requirements in order to fit in on-chip cache memory. This design allows measurement to be performed at the line rate, but it has to accept tradeoff with expensive computation for spread queries (unsuitable for online operations) and large errors in spread estimation for small flows. This paper complements the prior art with a new spread estimator design based on an on-chip/off-chip model which is common in practice. The new estimator supports online queries in real time and produces spread estimation with much better accuracy. By storing traffic data in off-chip memory, our new design faces a key technical challenge of efficient non-duplicate sampling. We propose a two-stage solution with on-chip/off-chip data structures and algorithms, which are not only efficient but also highly configurable for a variety of probabilistic performance guarantees. The experiment results based on real Internet traffic traces show that our estimator reduces the mean relative and absolute error by around one order of magnitude, and achieves both space-efficiency and accuracy-efficiency in flow classification for small flows compared to the prior art.

Traffic measurement is key to many network management tasks such as performance monitoring and cyber-security. Its aim is to inspect the packet stream passing through a network device, classify them into flows according to the header fields, and obtain statistics about the flows. For processing big streaming data in size-limited SRAM of line cards, many space-sublinear algorithms have been proposed, such as CountMin and CountSketch. However, most of them are designed for specific measurement tasks. Implementing multiple independent sketches places burden for online operations of a network device. It is highly desired to design a universal sketch that not only tracks individual large flows (called heavy hitters) but also reports overall traffic distribution statistics (called moments). The prior work UnivMon successfully tackled this ambitious quest. However, it incurs large and variable per-packet processing overhead, which may result in a significant throughput bottleneck in high-rate packet streaming, given that each packet requires 65 hashes and 64 memory accesses on average and many times of that in the worst case. To address this performance issue, we need to fundamentally redesign the solution architecture from hierarchical sampling to new progressive sampling and from CountSketch to new ActiveCM+, which ensure that per-packet overhead is a small constant (4 hash and 4 memory accesses) in the worst case, making it much more suitable for online operations, especially for pipeline implementation. The new design also makes effort to reduce memory footprint or equivalently improve measurement accuracy under the same memory. Our experiments show that our solution incurs just one sixteenth per-packet overhead of UnivMon, while improving measurement accuracy by three times under the same memory.

Traffic measurement in high-speed networks has many important functions in improving network performance, assisting resource allocation, and detecting anomalies. In this paper, we study a generalized problem called k-persistent spread estimation, which measures the volume of persist traffic elements in each flow that appear during at least k out of t measurement periods, where k and t are two positive integers that can be arbitrarily set in user queries, with k ≤ t. Solutions to this problem have interesting applications in network attack detection, popular content identification, user access profiling, etc. There is very limited prior art for this problem, only addressing the special case of k = t under a flawed assumption. Removing this assumption, we propose an efficient and accurate estimator for generalized k-persistent traffic measurement, with k ≤ t. Our method relies on bitwise SUM, instead of bitwise AND in the prior art, to combine the information collected from different periods. This change has fundamental impact on the probabilistic analysis that derives the estimator, particular over space-saving virtual bitmaps. Based on real network traces, we demonstrate experimentally the effectiveness of our new method in estimating the k-persistent spreads of all network flows. Our estimator performs much better than the prior art on its case of k = t. We also incorporate a sampling module to the estimator for improved flexibility, and give a use study on how to detect and find DDoS attackers using the proposed estimator.

Determining an object’s spatial pose (including orientation and position) plays a fundamental role in a variety of applications, such as automatic assembly, indoor navigation, and robot driving. In this paper, we design a fine-grained pose sensing system called Tag-Compass that attaches a single tag to an object (whose size may be small) and identifies the tagged object’s pose by determining the spatial orientation and position of the tag. We exploit thepolarizationproperties of the RF waves used in the communications between an RFID reader and the tag on the object. Polarization mismatch between the tag and the reader’s antenna affects the received signal strength at the reader. From the measured signal strength values, we are able to deduce the tag’s pose through a series of transformations and deviation minimization. We propose a system design for Tag-Compass and implement a prototype. We evaluate the performance of Tag-Compass through extensive experiments using the prototype. The experimental results show that Tag-Compass provides accurate estimate of object orientation with a median error of just 2.5° when the tag’s position is known and a median error of 3.8° when the tag’s position is unknown. In the latter case, Tag-Compass will provide an estimate of tag position as a byproduct of orientation sensing, with an accuracy comparable to the state of the art. It is practically appealing to find both the orientation and the position of an object using a single method, instead of having to deploy two different methods.

Cardinality estimation is the task of determining the number of distinct elements (or the cardinality) in a data stream, under a stringent constraint that the input data stream can be scanned by just one single pass. This is a fundamental problem with many practical applications, such as traffic monitoring of high-speed networks and query optimization of Internet-scale database. To solve the problem, we propose an algorithm named HLL-TailCut, which implements the estimation standard error 1.0/√m using the memory units of four or three bits each, whose cost is much smaller than the five-bit memory units used by HyperLogLog, the best previously known cardinality estimator. This makes it possible to reduce the memory cost of HyperLogLog by 20%~45%. For example, when the target estimation error is 1.1%, state-of-the-art HyperLogLog needs 5.6 kilobytes memory. By contrast, our new algorithm only needs 3 kilobytes memory consumption for attaining the same accuracy. Additionally, our algorithm is able to support the estimation of very large stream cardinalities, even on the Tera and Peta scale.

Radio Frequency Identification (RFID) technology has been proliferating in recent years, especially with its wide usage in retail, warehouse and supply chain management. One of its most popular applications is to automatically detect missing products (attached with RFID tags) in a large storage place. However, most existing protocols assume that the IDs of all tags within a reader's coverage are known, while ignoring practical scenarios where the IDs of some tags may be unknown. The existence of these unknown tags will introduce false positives in those protocols, degrading their performance. Some prior art studies this problem, but their time efficiency is low, especially when the number of unknown tags is large. In this paper, we propose a new missing tag detection protocol based on compressed filters, which not only reduce the filter size for better time-efficiency but also help dampen the interference of unknown tags for high missing-tag detection accuracy. To further improve the performance, we propose to use a combination of sampling and multi-hashing for tags to report their presence, greatly reducing collisions and thus improving the detection probability. We reconfigure the standard ID collection protocol to support bitmap collection required by missing-tag detection. Extensive simulations demonstrate that our compressed filter and collision-reduction method reduce the protocol execution time by 83% to 92% under the same missing-tag detection probability, when comparing with the best prior work. We also evaluate the performance of our missing-tag detection protocol under unreliable channel.

Radio-frequency identification (RFID) technologies have been widely used in inventory control, object tracking and supply chain management. One of the fundamental system functions is called cardinality estimation, which is to estimate the number of tags in a covered area. In this paper, we extend the research of this function in two directions. First, we perform joint cardinality estimation among tags that appear at different geographical locations and at different times. Moreover, we target at category-level information, which is more significant in practical scenarios where we need to monitor the tagged objects of many different categories. Second, we enforce anonymity in the process of information gathering in order to preserve the privacy of the tagged objects. These capabilities will enable new applications such as tracking how products of different categories are transferred in a large, distributed supply chain. We propose and implement a novel protocol to meet the requirements of anonymous category-level joint estimation over multiple tag sets. We formally analyze the performance of our estimator and determine the optimal system parameters. Moreover, we extend our protocol to unreliable channels and consider two channel error models. Extensive simulations show that the proposed protocol can efficiently and accurately estimate joint information over multiple tag sets at category level, while preserving tags' anonymity.

Software-defined networks facilitate automatic poli- cy enforcement with dynamic routing of flows through a sequence of middleboxes that offer the required network functions. As a result, network policy enforcement based on middleboxes, which is tedious and error-prone to perform in traditional IP networks, is greatly simplified. However, TCAM-based flow tables in SDN are small and energy-demanding, which limits the scalability of policy enforcement. This paper proposes a hybrid SDN-label switching scheme that combines TCAM- based switching (in SDN) at the network edge with label switching in the network core to provide scalable policy enforcement without compromising per-flow management capability. A linear optimization is proposed to balance workloads among the middleboxes. We demonstrate on OMNET++ that our proposed solution incurs much smaller processing/communication overhead and achieves better load-balancing when comparing with the prior art.

Widespread event detection is a fundamental network function that has many important applications in cybersecurity, traffic engineering, and distributed data mining. This paper introduces a new probabilistic threshold-based event detection problem, which is to find all events that appear in any w-out-of-a monitors with probabilistic guarantee on false positives, where a is the total number of monitors and the threshold w(≤ a) is a positive integer parameter that can be arbitrarily set, according to specific application requirements. We develop an efficient threshold filter solution and its improved versions, which combine Bloom filters, counting Bloom filter, threshold filter and compressed filters in a series of encoding and filtering steps, providing tradeoff between detection accuracy and communication overhead. We theoretically optimize the system parameters in the proposed solutions to minimize the communication overhead under the constraint of probabilistic detection guarantee. Extensive simulations demonstrate the practical viability of the proposed solutions in their ability of finding widespread events in a large network with few false positives and low communication overhead.

Traditional radio frequency identification (RFID) technologies allow tags to communicate with a reader but not among themselves. By enabling peer-to-peer communications among nearby tags, the emerging networked tags make a fundamental enhancement to today's RFID systems. This new capability supports a series of system-level functions in previously infeasible scenarios where the readers cannot cover all tags due to cost or physical limitations. This paper makes the first attempt to design a new communication model that is specifically tailored to efficient implementation of system-level functions in networked tag systems, in terms of energy cost and execution time. Instead of exploiting complex mechanisms for collision detection and resolution, we propose a collision-resistant communication model (CCM) that embraces the collision in tag communications and utilizes it to merge the data from different sources in a benign way. Two fundamental applications: RFID estimation and missing-tag detection, are presented to illustrate how CCM assists efficient system-level operations in networked tag systems. Simulation results show that the system-level applications through CCM are able to reduce the energy cost and execution time by one order of magnitude, compared with the ID-collection based solution.

Middleboxes are widely used in modern net-works for a variety of network functions in cybersecurity, performance enhancement, and monitoring. Middlebox policy enforcement is however complex and tedious with unreliable manual re-configuration of legacy routers. The existing solution on automated policy enforcement relies on software-defined networking and does not apply to the traditional non-SDN net-works, which remain popular today in enterprise deployment and core networks. This paper proposes a new architecture based entirely on software-defined middleboxes (instead of using software-defined switches in the prior art) to enable dependable and automated policy enforcement in non-SDN networks whose routers forward packets based on traditional routing protocols that are not policy-sensitive. We present a hot-potato enforcement strategy, which is then enhanced with two optimizations for load-balanced policy enforcement. Further enhancements are made to relieve middlebox processing overhead and avoid packet fragmentation due to policy enforcement.

Sleep monitoring plays an important role in many medical applications, including SIDS prevention, care of patients with pressure ulcers, and assistance to patients with sleep apnea, where studies have shown that autonomous and continuous monitoring of sleep postures provides useful information for lowering health risk. Existing systems are designed based on electrocardiogram, cameras and pressure sensors, which are expensive to deploy, intrusive to privacy, or uncomfortable to use. This paper presents TagSheet, the first sleep monitoring system based on passive RFID tags, which provides a convenient, non-intrusive, and comfortable way of monitoring the sleeping postures. It does not require attaching any tag directly to a patient’s body. Tags are taped under a bed sheet. With a combination of hierarchical recognition, image processing and polynomial fitting, the proposed system identifies body postures based on the observed variation caused by the patient body to the backscattered signals from tags. The system does not require any personalized data training, making it plug-n-play in use. One additional advantage is that the system can also estimate the patient’s respiration rate. This is particularly helpful in assisting patients with sleep apnea. We have implemented a prototype system, and experiments show that the system performs posture identification with an accuracy up to 96.7% and in the meantime it measures the respiration rate with a small error of about 0.7 bpm (breath per minute).

Many important functions in software defined networks can benefit from fine-grained traffic measurement at flow level. Because TCAM-based flow entries only provide aggregate traffic statistics, prior research has suggested to perform flow-level measurement in SRAM and balance the measurement load across the network through collaborative traffic measurement. The key problem of collaborative measurement is to provide a mechanism to distribute flows to switches such that each switch can identify its subset of flows to measure. We observe that the prior work has focused on optimizing flow distribution among switches, but overlooked their high space and per-packet processing overhead introduced to the data plane, which becomes a serious issue in large SDN systems. In this paper, we propose a new lightweight solution to the flow distribution problem. It follows the design principle of alleviating complexity of the data plane by minimizing the data-plane space and processing overhead. At the control plane, we formulate flow distribution as optimization problems under two scenarios that implement collaborative measurement by edge switches only and by edge/core switches together, respectively. Our extensive simulations demonstrate that, comparing with the best existing work, the proposed lightweight solution achieves a comparable performance in terms of load balancing, while drastically reducing both space overhead and per-packet processing overhead, making it more practical in real-world systems that are sensitive to the additional overhead introduced by flow distribution.

Rain observations with fine spatio-temporal granularity are significant for professional researches, decision-making, and our daily lives. However, the existing rain gauges can only cover less than 1% of the earth surface, and its amount is still decreasing. Even with the help of several other limited and immature supplementary techniques, rain observations today are still not precise enough. In such context, crowdsourcing paves the avenues toward a fault-tolerant rain observation network with unprecedented resolution and coverage, based on an alternative, nowadays omnipresent source, smartphones, which are integrated with abundant advanced sensors and are becoming more and more ubiquitous around us. In this paper, we propose Chaac, a novel system that exploits opportunistically crowdsourced audio clips from smartphone users to achieve precise detection and intensity measurement of rain. The evaluation results of performing Chaac on 1-s long audio segments demonstrate that it can detect and measure rain with 92.0% and 93.9% true positive rates, respectively.

Traffic volume estimation is critical to the intelligent transportation engineering. Previous state-of-the-art studies mainly focus on measuring two types of traffic volume: “point” traffic (i.e., the number of vehicles passing a given location) and “point-to-point” traffic (i.e., the number of vehicles traversing between two given locations) during each measurement period. In this paper, we extend this line of research from single-period to multiple periods and study new problems of estimating the number of k-persistent vehicles that pass a location or two different locations in at least k-out-of-t predefined measurement periods. We propose two novel k-persistent traffic estimators with privacy-preserving for the point and point-to-point traffic models, respectively. Through theoretical analysis, we prove that our solution can solve more general traffic measurement problems and employ stronger privacy preserving, i.e., E-differential privacy, than the existing studies. We also demonstrate the effectiveness and the accuracy of the proposed estimators through extensive experiments based on real transportation traffic flows in Shenzhen, China for five consecutive working days. The numerical results show that the estimators can achieve a tradeoff between the estimation accuracy and privacy preservation through proper parameter setting.

Traditional systems for monitoring and diagnosing patients' health conditions often require either dedicated medical devices or complicated system deployment, which incurs high cost. The networking research community has recently taken a different technical approach of building health-monitoring systems at relatively low cost based on wireless signals. However, the radio frequency signals carry various types of noise and have time-varying properties that often defy the existing methods in more demanding conditions with other body movements, which makes it difficult to model and analyze the signals mathematically. In this paper, we design a novel wireless system using commercial off-the-shelf RFID readers and tags to provide a general and effective means of measuring bodily oscillation rates, such as the hand tremor rate of a patient with Parkinson's disease. Our system includes a series of noise-removal steps, targeting at noise from different sources. More importantly, it introduces two sliding window-based methods to deal with time-varying signal properties from channel dynamics and irregular body movement. The proposed system can measure bodily oscillation rates of multiple persons simultaneously. Extensive experiments show that our system can produce accurate measurement results with errors less than 0.4 oscillations per second when it is applied to monitor hand tremor, even when the individuals are moving.

Measuring traffic volume in a road system has important applications in transportation engineering. The connected vehicle technologies integrate wireless communications and computers into transportation systems, allowing wireless data exchanges between vehicles and road-side equipment, and enabling large-scale, sophisticated traffic measurement. This paper investigates the problem of persistent traffic measurement, which was not adequately studied in the prior art, particularly in the context of intelligent vehicular networks. We propose three estimators for privacy-preserving persistent traffic measurement: one for point traffic, one for point-to-point traffic, and another for three-point traffic. After that, we present a general framework to measure persistent traffic that go through more than three locations. The estimators are mathematically derived from the join result of traffic records, which are produced by the electronic roadside units with privacy-preserving data structures. We evaluate our estimation methods using simulations based on both real transportation traffic data and synthetic data. The numerical results demonstrate the effectiveness of the proposed methods in producing high measurement accuracy and allowing accuracy-privacy tradeoff through parameter setting.

Finding top-k elephant flows is a critical task in network traffic measurement, with many applications in congestion control, anomaly detection and traffic engineering. As the line rates keep increasing in today's networks, designing accurate and fast algorithms for online identification of elephant flows becomes more and more challenging. The prior algorithms are seriously limited in achieving accuracy under the constraints of heavy traffic and small on-chip memory in use. We observe that the basic strategies adopted by these algorithms either require significant space overhead to measure the sizes of all flows or incur significant inaccuracy when deciding which flows to keep track of. In this paper, we adopt a new strategy, called count-with-exponential-decay, to achieve space-accuracy balance by actively removing small flows through decaying, while minimizing the impact on large flows, so as to achieve high precision in finding top-k elephant flows. Moreover, the proposed algorithm called HeavyKeeper incurs small, constant processing overhead per packet and thus supports high line rates. Experimental results show that HeavyKeeper algorithm achieves 99.99% precision with a small memory size, and reduces the error by around 3 orders of magnitude on average compared to the state-of-the-art.

In RFID-enabled applications, when a tag is put into use and associated with a specific object, the category-related information (e.g., the brands of clothes) about this object might be preloaded into the tag’s memory for the purpose of live query. Since such information reflects category attributes, all tags in the same category carry identical category information. To collect this information, we do not need to repeatedly interrogate each tag; one tag’s response in a category is sufficient. In this paper, we investigate the problem of category information collection in a multi-category RFID system, which is referred to asinformation sampling. We propose two time-efficiency protocols. The first is a two-phase sampling protocol (TPS) that works in the case of knowing tag IDs. By quickly zooming into a category and isolating a tag from this category, TPS is able to sample a category with small overhead. The second protocol, called back-and-forth sampling protocol (BFS), relaxes a key assumption in TPS and performs the sampling task efficiently without knowing any tag IDs or category IDs. By carrying out a step-forward frame and using the step-backward scheme, BFS is able to interrogate only 1.45 tags (close to the lower bound of one tag) on average for each category. We theoretically analyze the protocol performance of TPS and BFS and discuss the optimal parameter settings that minimize the overall execution time. Extensive simulations show that both the protocols outperform the benchmark, greatly improving the sampling performance.

Radio frequency identification (RFID) technology has rich applications in cyber-physical systems, such as warehouse management and supply chain control. Often in practice, tags are attached to objects belonging to different groups, which may be different product types/manufacturers in a warehouse or different book categories in a library. As RFID technology evolves from single-group to multiple-group systems, there arise several interesting problems. One of them is to identify the popular groups, whose numbers of tags are above a pre-defined threshold. Another is to estimate arbitrary moments of the group size distribution, such as sum, variance, and entropy for the sizes of all groups. In this paper, we consider a new problem which is to estimate all these statistical metrics simultaneously in a time-efficient manner without collecting any tag IDs. We solve this problem by a protocol named generic moment estimator (GME), which allows the tradeoff between estimation accuracy and time cost. According to the results of our theoretical analysis and simulation studies, this GME protocol is several times or even orders of magnitude more efficient than a baseline protocol that takes a random sample of tag groups to estimate each group size.

Radio-frequency identification (RFID) technology has been widely adopted in various industries and people's daily lives. This paper studies a fundamental function of spatial-temporal joint cardinality estimation in distributed RFID systems. It allows a user to make queries over multiple tag sets that are present at different locations and times in a distributed tagged system. It estimates the joint cardinalities of those tag sets with bounded error. This function has many potential applications for tracking product flows in large warehouses and distributed logistics networks. The prior art is either limited to jointly analyzing only two tag sets or is designed for a relative accuracy model, which may cause unbounded time cost. Addressing these limitations, we propose a novel design of the joint cardinality estimation function with two major components. The first component is to record snapshots of the tag sets in a system at different locations and periodically, in a time-efficient way. The second component is to develop accurate estimators that extract the joint cardinalities of chosen tag sets based on their snapshots, with a bounded error that can be set arbitrarily small. We formally analyze the bias and variance of the estimators, and we develop a method for setting their optimal system parameters. The simulation results show that, under predefined accuracy requirements, our new solution reduces time cost by multiple folds when compared with the existing work.

State-of-the-art cache compression methods compress multiple neighboring blocks often called as a sector into a single 64-byte block to effectively enlarge the cache capacity. A compressed block is created by storing 4-byte data patterns as dictionary entries and pointers to them for compressing multiple blocks. Furthermore, sector-based tag array maintains one-to-one mapping between tag and data arrays in order to preserve conventional cache access mechanism. We present a dual-block compression method which uses an entire uncompressed block as dictionary and compresses multiple neighboring blocks in a separate companion block to provide a larger dictionary for better compression ratios. Furthermore, we introduce the concept of buddy-set which expands the compressible candidate blocks across two adjacent cache sets to enlarge the scope of compression. Performance evaluations for the last-level cache show that the proposed dual-block compression with expansion of compressible candidates in the buddy-set can enlarge the cache by an average of 60% while current state-of-art compression proposal has only 29% improvement. The proposed scheme demonstrates 8.9% speedup over caches without compression.

Per-flow traffic measurement is a fundamental problem in the era of big network data, and has been widely used in many applications, including capacity planning, anomaly detection, load balancing, traffic engineering, etc. In order to keep up with the line speed of modern network devices (e.g., routers), per-flow measurement online module is often implemented by using on-chip cache memory (such as SRAM) to minimize per-packet processing time, but on-chip SRAM is expensive and limited in size, which poses a major challenge for traffic measurement. In response, much recent research is geared towards designing highly compact data structures for approximate estimation that can provide probabilistic guarantees for per-flow measurement. The state of art, called Counter Tree (CT), requires at least 2 bits per flow in memory consumption and more than 2 memory accesses per packet in processing time. In this paper, we propose a novel design of a highly compact and efficient counter architecture, called Virtual Active Counter estimation (VAC), which achieves faster processing speed (slightly more than 1 memory access per packet on average) and provides more accurate measurement results than CT under the same allocated memory. Moreover, VAC can perform well even with a very tight memory space (less than 1 bit per flow or even one fifth of a bit per flow). Theoretical analysis and experiments based on real network traces demonstrate the superior performance of VAC.

Traffic measurement in high-speed networks has many applications in improving network performance, assisting resource allocation, and detecting anomalies. In this paper, we study a new problem called k-persistent spread estimation, which measures persist traffic elements in each flow that appear during at least k out of t measurement periods, where k and t can be arbitrarily defined in user queries. Solutions to this problem have interesting applications in network attack detection, popular content identification, user access profiling, etc. Yet, it is under-investigated as the prior work only addresses a special case with a questionable assumption. Designing an efficient and accurate k -persistent estimator requires us to use bitwise SUM (instead of bitwise AND typical in the prior art) to join the information collected from different periods. This seemly simple change has fundamental impact on the mathematical process in deriving an estimator, particular over space-saving virtual bitmaps. Based on real network traces, we show that our new estimator can accurately estimate the k -persistent spreads of the flows. It also performs much better than the existing work on the special case of measuring elements that appear in all periods.

Radio-frequency identification (RFID) technologies have been widely used in inventory management, object tracking and supply chain management. One of the fundamental system functions is called cardinality estimation, which is to estimate the number of tags in a covered area. We extend the research of this function in two directions. First, we perform joint cardinality estimation among tags that appear at different geographical locations and at different times. Moreover, we collect category-level information, which is more significant in practical scenarios where we need to monitor the tagged objects of many different types. Second, we require anonymity in the process of information gathering in order to preserve the privacy of the tagged objects. These capabilities will enable new applications such as tracking how products are moved in a large, distributed supply network. We propose a novel protocol design to meet the requirements of anonymous category-level joint estimation over multiple tag sets. We formally analyze the performance of our estimator and determine the optimal system parameters. Extensive simulations show that the proposed protocol can efficiently obtain accurate category-level estimation, while preserving tags' anonymity.

Traditional systems for monitoring and diagnosing patients' health conditions often require either dedicated medical devices or complicated system deployment, which incurs high cost. The networking research community has recently taken a different technical approach of building health-monitoring systems at relatively low cost based on wireless signals. However, the RF signals carry various types of noise and have time-varying properties that often defy the existing methods in more demanding conditions with other body movements, which makes it difficult to model and analyze the signals mathematically. In this paper, we design a novel wireless system using commercial off-the-shelf RFID readers and tags to provide a general and effective means of measuring bodily oscillation rates, such as the hand tremor rate of a patient with Parkinson's disease. Our system includes a series of noise-removal steps, targeting at noise from different sources. More importantly, it introduces two sliding window-based methods to deal with time-varying signal properties from channel dynamics and irregular body movement. The proposed system can measure bodily oscillation rates of multiple persons simultaneously, even when the individuals are moving. Extensive experiments show that our system can produce accurate measurement results with errors less than 0.3 oscillations per second when it is applied to monitor hand tremor.

Radio Frequency Identification (RFID) technology has been proliferating in recent years, especially with its wide usage in retail, warehouse and supply chain management. One of its most popular applications is to automatically detect missing products (attached with RFID tags) in a large storage place. However, most existing protocols assume that the IDs of all tags within a reader's coverage are known, while ignoring practical scenarios where the IDs of some tags may be unknown. The existence of these unknown tags will introduce false positives in those protocols, degrading their performance. Some prior art studies this problem, but their time efficiency is low, especially when the number of unknown tags is large. In this paper, we propose a missing tag detection protocol based on compressed filters, which not only reduces the filter size for better time-efficiency but also helps dampen the interference of unknown tags for high missing-tag detection accuracy. To further improve the performance, we propose a new way for tags to report their presence, greatly reducing collisions and thus improving the detection probability. Extensive simulations demonstrate that our compressed filter and collision-reduction method reduce the protocol execution time by 83% to 92% under the same missing-tag detection probability, when comparing with the best prior work.

Given the fact that roughly 800 000 children are reported missing in the United States every year, how to assist parents to track their children becomes an important problem. Even though many children tracking systems have been proposed, the high cost and energy limitation of locators are the stumbling blocks which limit the application of those systems. To address this challenge, we design a children tracking system based on RFID technology, where children carry RFID tags and the system is responsible for locating the children by aggregating the readings from the deployed readers. Noting the importance of localized processing for efficient children tracking, we further study how the locally available computing resource, such as the mobile devices carried by the park employees and visitors, can be utilized for service provisioning. Since mobile devices have limited energy, we study an energy efficiency optimization problem by jointly considering the resource allocation and user association. The formulated problem is solved by a dynamic updating matching approach. Through extensive simulations, we have demonstrated the effectiveness of our proposed solution.

Traditional networks rely on aggregate routing and decentralized control to achieve scalability. On the contrary, software-defined networks achieve near optimal network performance and policy-based management through per-flow routing and centralized control, which, however, face scalability challenge due to: 1) limited ternary content addressable memory and on-die memory for storing the forwarding table and 2) per-flow communication/computation overhead at the controller. This paper presents a novel hybrid switching (HS) design, which integrates traditional switching and software-defined networking (SDN) switching for the purpose of achieving both scalability and optimal performance. We show that the integration also leads to unexpected benefits of making both types of switching more efficient under the hybrid design. We also design the general optimization framework via HS and propose an approximation algorithm for load-balancing optimization as a case study. Testing and numerical evaluation demonstrate the superior performance of HS when comparing with the state-of-the-art SDN design.

Software-defined datacenters combine centralized resource management, software-defined networking, and virtualized infrastructure to meet diverse requirements of cloud computing. To fully realizing their capability in traffic engineering and flow-based bandwidth management, it is critical for the switches to measure network traffic for both individual flows between virtual machines and aggregate flows between clusters of physical or virtual machines. This paper proposes a novel hierarchical traffic measurement scheme for software-defined datacenter networks. It measures both aggregate flows and individual flows that are organized in a hierarchy with an arbitrary number of levels. The measurement is performed based on a new concept of hierarchical virtual counter arrays, which record each packet only once by updating a single counter, yet the sizes of all flows that the packet belongs to will be properly updated. We demonstrate that the new measurement scheme not only supports hierarchical traffic measurement with accuracy, but does so with memory efficiency, using a fewer number of counters than the number of flows.

We study a fundamental problem of how to schedule complex workflows in the cloud for applications such as data analytics. One of the main challenges is that such workflow scheduling problems involve many constraints, requirements and varied objectives and it is extremely difficult to find high-quality solutions. To meet the challenge, we explore using mixed integer programming (MIP) to formulate and solve complex workflow scheduling problems. To illustrate the MIP-based method, we formulate three related workflow scheduling problems in MIP. They are fairly generic, comprehensive and are expected to be useful for a wide range of workflow scheduling scenarios. Using results from numerical experiments, we demonstrate that, for problems up to certain size, the MIP approach is entirely applicable and more advantageous over heuristic algorithms.

Sketch is a data structure used to record frequencies of items in a multiset, which is widely used in data streams, data graph, distributed datasets processing, etc. It works with small memory usage and a high speed at the cost of a slight inaccuracy. In practice, frequencies of items in many datasets are non-uniformly distributed. Unfortunately, existing sketches can hardly work well on non-uniform datasets. To address this issue, we propose a new sketch framework, namely ABC framework, which can be applied to most existing sketches and can significantly improve the accuracy on non-uniform datasets. The key idea behind our framework is that when a counter overflows, it makes use of the space from the adjacent counters by operations of bits-borrowing and combination. Extensive experimental results show that our ABC framework improves the accuracy by 4.10 times and 4.49 times in average, respectively. A demo and all the related source codes are available on our homepage [1].

Measuring point traffic volume and point-to-point traffic volume in a road system has important applications in transportation engineering. The connected vehicle technologies integrate wireless communications and computers into transportation systems, allowing wireless data exchanges between vehicles and road-side equipment, and enabling large-scale, sophisticated traffic measurement. This paper investigates the problems of persistent point traffic measurement and persistent point-to-point traffic measurement, which were not adequately studied in the prior art, particularly in the context of intelligent vehicular networks. We propose two novel estimators for privacy-preserving persistent traffic measurement: one for point traffic and the other for point-to-point traffic. The estimators are mathematically derived from the join result of traffic records, which are produced by the electronic roadside units with privacy-preserving data structures. We evaluate our estimation methods using simulations based on both real transportation traffic data and synthetic data. The numerical results demonstrate the effectiveness of the proposed methods in producing high measurement accuracy and allowing accuracy-privacy tradeoff through parameter setting.

In RFID-enabled applications, when a tag is put into use and associated with a specific object, the category-related information (e.g., the brands of clothes) about this object might be preloaded into the tag's memory as required. Since such information reflects the category attributes, all tags in the same category carry the identical category information. To collect this information, we do not need to repeatedly interrogate each tag; one tag's response in a category is sufficient. In this paper, we investigate the new problem of category information collection in a multi-category RFID system, which is referred to as information sampling. We propose an efficient two-phase sampling protocol (TPS). By quickly zooming into a category and isolating a tag from this category, TPS is able to sample a category by broadcasting only 7.5-bit polling vector (very efficient when compared to the 96-bit tag ID). We theoretically analyze the protocol performance and discuss the optimal parameter settings that minimize the overall execution time. Extensive simulations show that TPS outperforms the benchmark, greatly improving the sampling performance.

Thanks to the proliferation of Internet access and modern digital and mobile devices, online survey has been flourishing into data collection of marketing, social, financial and medical studies. However, traditional data collection methods in online survey suffer from serious privacy issues. Existing privacy protection techniques are not adequate for online survey for lack of strong privacy. In this paper, we propose a practical strong privacy online survey scheme SPS based on a novel data collection technique called dual matrix masking (DM2), which guarantees the correctness of the tallying results with low computation overhead, and achieves universal verifiability, robustness and strong privacy. We also propose a more robust scheme RSPS, which incorporates multiple distributed survey managers. The RSPS scheme preserves the nice properties of SPS, and further achieves robust strong privacy against joint collusion attack. Through extensive analyses, we demonstrate our proposed schemes can be efficiently applied to online survey with accuracy and strong privacy.

Software Defined Networking (SDN) separates the control plane from the data plane to ease network management and provide flexibility in packet routing. The control plane interacts with the data plane through the forwarding tables, usually including a flow table and a group table, at each switch. Due to high cost and power consumption of Ternary Content Addressable Memory (TCAM), commodity switches can only support flow/group tables of limited size, which presents serious challenge for SDN to scale to large networks. One promising approach to address the scalability problem is to deploy aggregate default paths specified by wildcard forwarding rules. However, the multi-dimensional interaction among numerous system parameters and performance/scalability considerations makes the problem of setting up the flow/group tables at all switches for optimal overall layout of default paths very challenging. This paper studies the joint optimization of flow/group tables in the complex setting of large-scale SDNs. We formulate this problem as an integer linear program, and prove its NP-Hardness. An efficient algorithm with bounded approximation factors is proposed to solve the problem. The properties of our algorithm are formally analyzed. We implement the proposed algorithm on an SDN testbed for experimental studies and use simulations for large-scale investigation. The experimental results and simulation results demonstrate high efficiency of our proposed algorithm.

RFID technologies are making their way into numerous applications, including inventory management, supply chain, product tracking, transportation, logistics, etc. One important application is to automatically detect anomalies in RFID systems, such as missing tags, unknown tags, or cloned tags due to theft, management error, or targeted attacks. Existing solutions are all designed to detect a certain type of RFID anomalies, but lack a general functionality for detecting different types of anomalies. This paper attempts to propose a general framework for anomaly detection in RFID systems, thereby reducing the complexity for readers and tags to implement different anomaly-detection protocols. We introduce a new concept of differential Bloom filter (DBF), which turns physical-layer signal data into a segmented Bloom filter that encodes the IDs of abnormal tags. As a case study, we propose a protocol that builds DBF for identifying all missing tags in an efficient way. We implement a prototype for missing-tag identification using USRP and WISP tags to verify the effectiveness our protocol, and use large-scale simulations for performance evaluation. The results show that our solution can significantly improve time efficiency, when comparing with the best existing work.

Identifying an object's spatial direction (or orientation) plays a fundamental role in a variety of applications, such as automatic assembly, indoor navigation, and robot driving. In this paper, we design a fine-grained direction finding system called Tag-Compass that attaches a single tag to an object (whose size may be small) and identifies the tagged object's orientation by determining the spatial direction of the tag. We exploit the polarization properties of the RF waves used in the communications between an RFID reader and the tag on the object. Polarization mismatch between the tag and the reader's antenna affects the received signal strength at the reader. From the measured signal strength values, we are able to deduce the tag's direction through a series of transformations and deviation minimization. We propose a system design for Tag-Compass and implement a prototype. We evaluate the performance of TagCompass through extensive experiments using the prototype. The experimental results show that Tag-Compass provides accurate direction estimates with a median error of just 2.5° when the tag's position is known and a median error of 3.8° when the tag's position is unknown.

Cardinality estimation is the task of determining the number of distinct elements (or the cardinality) in a data stream, under a stringent constraint that the input data stream can be scanned by just a single pass. This is a fundamental problem with many practical applications, such as traffic monitoring of high-speed networks and query optimization of Internetscale database. To solve the problem, we propose an algorithm named HLL-TailCut+, which implements the estimation standard error 1.0/√m using the memory units of three bits each, whose cost is much smaller than the five-bit memory units used by HyperLogLog, the best previously known cardinality estimator. This makes it possible to reduce the memory cost of HyperLogLog by 45%. For example, when the target estimation error is 1.1%, state-of-the-art HyperLogLog needs 5.6 kilobytes memory. By contrast, our new algorithm only needs 3 kilobytes memory consumption for attaining the same accuracy. Additionally, our algorithm is able to support the estimation of very large stream cardinalities, even on the Tera and Peta scale.

Traditional networks rely on aggregate routing and decentralized control to achieve scalability. On the contrary, software-defined networks achieve near optimal network performance and policy-based management through per-flow routing and centralized control, which however face scalability challenge due to (1) limited TCAM and on-die memory for storing the forwarding table and (2) per-flow communication/computation overhead at the controller. This paper presents a novel hybrid switching design, which integrates traditional switching and SDN switching for the purpose of achieving both scalability and optimal performance. We show that the integration also leads to unexpected benefits of making both types of switching more efficient under the hybrid design. Numerical evaluation demonstrates the superior performance of hybrid switching when comparing with the state-of-the-art SDN design.

Per-flow counting for big network data streams is a fundamental problem in various network applications such as traffic monitoring, load balancing, capacity planning, etc. Traditional research focused on designing compact data structures to estimate flow sizes from the beginning of the data stream (i.e., landmark window model). However, for many applications, the most recent elements of a stream are more significant than those arrived long time ago, which gives rise to the sliding window model. In this paper, we consider per-flow counting over the sliding window model, and propose two novel solutions, ACE and S-ACE. Instead of allocating a separate data structure for each flow, both solutions utilize the counter sharing idea to reduce memory footprint, so they can be implemented in on-chip SRAMs in modern routers to keep up with the line speed. ACE has to reset the sliding window periodically to give precise estimates, while S-ACE based on a novel segment design can achieve persistently accurate estimates. Our extensive simulations as well as experimental evaluations based on real network traffic trace demonstrate that S-ACE can achieve fast processing speed and high measurement accuracy even with a very tight memory.

Sketch is a probabilistic data structure, and is used to store and query the frequency of any item in a given multiset. Due to its high memory efficiency, it has been applied to various fields in computer science, such as stream database, network traffic measurement, etc. The key metrics of sketches for data streams are accuracy, speed, and memory usage. Various sketches have been proposed, but they cannot achieve both high accuracy and high speed using limited memory, especially for skewed datasets. To address this issue, we propose a sketch framework, the Pyramid sketch, which can significantly improve accuracy as well as update and query speed. To verify the effectiveness and efficiency of our framework, we applied our framework to four typical sketches. Extensive experimental results show that the accuracy is improved up to 3.50 times, while the speed is improved up to 2.10 times. We have released our source codes at Github [1].

Per-flow traffic measurement, which is to count the number of packets for each active flow during a certain measurement period, has many applications in traffic engineering, classification of routing distribution or network usage pattern, service provision, anomaly detection, and network forensics. In order to keep up with the high throughput of modern routers or switches, the online module for per-flow traffic measurement should use high-bandwidth SRAM that allows fast memory accesses. Due to limited SRAM space, exact counting, which requires to keep a counter for each flow, does not scale to large networks consisting of numerous flows. Some recent work takes a different approach to estimate the flow sizes using counter architectures that can fit into tight SRAM. However, existing counter architectures have limitations, either still requiring considerable SRAM space or having a small estimation range. In this paper, we design a scalable counter architecture called Counter Tree, which leverages a 2-D counter sharing scheme to achieve far better memory efficiency and in the meantime extend estimation range significantly. Furthermore, we improve the performance of Counter Tree by adding a status bit to each counter. Extensive experiments with real network traces demonstrate that our counter architecture can produce accurate estimates for flows of all sizes under very tight memory space.

Radio-frequency identification (RFID) technologies are making their way into retail products, library books, debit cards, passports, driver licenses, car plates, medical devices, and so on. The widespread use of tags in traditional ways of deployment raises a privacy concern: they make their carriers trackable. To protect the privacy of the tag carriers, we need to invent new mechanisms that keep the usefulness of tags while doing so anonymously. Many tag applications, such as toll payment, require authentication. This paper studies the problem of anonymous authentication. Since low-cost tags have extremely limited hardware resource, we propose an asymmetric design principle that pushes most complexity to more powerful RFID readers. With this principle, we develop a lightweight technique that generates dynamic tokens for anonymous authentication. Instead of implementing complicated and hardware-intensive cryptographic hash functions, our authentication protocol only requires tags to perform several simple and hardware-efficient operations such as bitwise XOR, one-bit left circular shift, and bit flip. The theoretical analysis and randomness tests demonstrate that our protocol can ensure the privacy of the tags. Moreover, our protocol reduces the communication overhead and online computation overhead to O(1) per authentication for both tags and readers, which compares favorably with the prior art.

Traditional radio frequency identification (RFID) technologies allow tags to communicate with a reader but not among themselves. By enabling peer communications between nearby tags, the emerging networked tags represent a fundamental enhancement to today's RFID systems. They support applications in previously infeasible scenarios where the readers cannot cover all tags due to cost or physical limitations. This paper is the first study on identifying state-free networked tags, which is a basic, fundamental function for most tagged systems. To prolong the lifetime of networked tags and make identification protocols scalable to large systems, energy efficiency and time efficiency are most critical. Our investigation reveals that the traditional contention-based protocol design will incur too much energy overhead in multihop tag systems. Surprisingly, a reader-coordinated design that serializes tag transmissions performs much better. In addition, we show that load balancing is important in reducing the worst case energy cost to the tags, and we present a solution based on serial numbers. We also show that, by leveraging the request aggregation and transmission pipelining techniques, the time efficiency of serialized ID collection can be greatly improved.

Radio frequency identification (RFID) technology has been widely used in Applications, such as inventory control, object tracking, and supply chain management. In this domain, an important research problem is called RFID cardinality estimation, which focuses on estimating the number of tags in a certain area covered by one or multiple readers. This paper extends the research in both temporal and spatial dimensions to provide much richer information about the dynamics of distributed RFID systems. Specifically, we focus on estimating the cardinalities of the intersection/differences/union of two arbitrary tag sets (called joint properties for short) that exist in different spatial or temporal domains. With many practical applications, there is, however, little prior work on this problem. We will propose a joint RFID estimation protocol that supports adaptive snapshot construction. Given the snapshots of any two tag sets, although their lengths may be very different depending on the sizes of tag sets they encode, we design a way to combine their information and more importantly, derive closed-form formulas to use the combined information and estimate the joint properties of the two tag sets, with an accuracy that can be arbitrarily set. By formal analysis, we also determine the optimal system parameters that minimize the execution time of taking snapshots, under the constraints of a given accuracy requirement. We have performed extensive simulations, and the results show that our protocol can reduce the execution time by multiple folds, as compared with the best alternative approach in literature.

For many practical applications, it is a fundamental problem to estimate the flow cardinalities over big network data consisting of numerous flows (especially a large quantity of mouse flows mixed with a small number of elephant flows, whose cardinalities follow a power-law distribution). Traditionally the research on this problem focused on using a small amount of memory to estimate each flow's cardinality from a large range (up to ${10}^{{9}}$ ). However, although the memory needed for each individual flow has been greatly compressed, when there is an extremely large number of flows, the overall memory demand can still be very high, exceeding the availability under some important scenarios, such as implementing online measurement modules in network processors using only on-chip cache memory. In this paper, instead of allocating a separated data structure (called estimator) for each flow, we take a different path by viewing all the flows together as a whole: Each flow is allocated with a virtual estimator, and these virtual estimators share a common memory space. We discover that sharing at the multi-bit register level is superior than sharing at the bit level. We propose a unified framework of virtual estimators that allows us to apply the idea of sharing to an array of cardinality estimation solutions, e.g., HyperLogLog and PCSA, achieving far better memory efficiency than the best existing work. Our experiment shows that the new solution can work in a tight memory space of less than 1 bit per flow or even one tenth of a bit per flow - a quest that has never been realized before.

RFID technology has been widely adopted for real-world applications, such as warehouse management, logistic control, and object tracking. This paper focuses on a new angle of applying RFID technology-monitoring the temporal change of a tag set in a certain region, which is called churn estimation. This problem is to provide quick estimations on the number of new tags that have entered a monitored region, and the number of pre-existing tags that have departed from the region, within a predefined time interval. The traditional cardinality estimator for a single tag set cannot be applied here, and the conventional tag identification protocol that collects all tag IDs takes too much time, especially when the churn estimation needs to perform frequently to support real-time monitoring. This paper will take a new solution path, in which a reader periodically scans the tag set in a region to collect their compressed aggregate information in the form of empty/singleton/collision time slots. This protocol can reduce the time cost of attaining pre-set accuracy by at least 35%, when comparing with a previous work that uses only the information of idle/busy slots. Such a dramatic improvement is due to our awareness of collision slot state and the full utilization of slot state changes. Our proposed churn estimator, as shown by the extensive analysis and simulation studies, can be configured to meet any pre-set accuracy requirement with a statistical error bound that can be made arbitrarily small.

As computational clouds offer increasingly sophisticated services, there is a dramatic increase in the variety and complexity of virtual machine (VM) placement problems. In this paper, we consider a VM placement problem with a special type of anti-colocation requirements-disk anti-colocation-which stipulate that, for every VM assigned to a PM (physical machine), its virtual disks should be spread out across the physical disks of the PM. Once such a requirement is met, the users of the VM can expect improved disk I/O performance. There will also be improvement in fault tolerance and availability. For scalable solutions, we propose a method that combines hierarchical decomposition with mixed integer programming (MIP), where the basic building blocks are independent, small MIP subproblems. We provide experimental results to demonstrate the effectiveness of the proposed method. We show that it is scalable and achieves high performance with respect to the optimization objective.

Computational clouds have evolved to go beyond cost-effective on-demand hosting of IT resources and elasticity. The added features now include the ability to offer entire IT systems as a service that can quickly adapt to changing business environments. The new trend introduces challenges in datacenter resource management, including scalability, system-orientation, and optimization supporting both datacenter efficiency and customer system agility and performance. The conventional approach of resource management adopts a flat fine-grained model that results in problem formulations of enormous sizes, it also has the drawback of being less flexible in meeting customers' need. In this paper, we introduce a pack-centric approach to datacenter resource management by abstracting a system as a pack of resources and considering the mapping of these packs onto physical datacenter resource groups, called swads. The assignments of packs to swads are formulated as mixed integer programming problems. Scalability is achieved through a hierarchical decomposition method and parallel solvers. The new datacenter resource management framework is illustrated with a concrete resource placement problem. Numerical experiments show the scalability of the hierarchical decomposition method and the benefits of the overall framework.

Thanks to the Internet, voters can cast their ballots over the electronic voting (E-voting) systems conveniently and efficiently without going to the polling stations. However, existing E-voting protocols suffer from anonymity issues and/or high deployment overhead. In this paper, we design a practical anonymous E-voting protocol (referred to as MVP) based on a novel data collection technique called dual random matrix masking (DRMM), which guarantees anonymity with low overhead of computation, and achieves the security goals of receipt-freeness, double voting detection, fairness, ballot secrecy, and integrity. Through extensive analyses on correctness, efficiency, and security properties, we demonstrate our proposed MVP protocol can be applied to E-voting in a variety of situations with accuracy and anonymity.

Per-flow traffic measurement is a fundamental problem in the era of big network data, providing critical information for many practical applications including capacity planning, traffic engineering, data accounting, resource management, and scan/intrusion detection in modern computer networks. It is challenging to design highly compact data structures for approximate per-flow measurements. In this paper, we show that a highly compact virtual counter architecture can achieve fast processing speed (slightly more than 1 memory access per packet) and provide accurate measurement results under tight memory allocation. Extensive experiments based on real network trace data demonstrate its superior performance over the best existing work.

Radio-frequency identification (RFID) technologies have been widely used in many applications, including inventory management, supply chain, product tracking, transportation, logistics, etc. Tag estimation, which is to estimate the cardinality of a single tag set, is an important research topic. This paper expands the estimation research as follows: It performs joint estimation between two tag sets (which exist at different locations or at the same location but different times). More importantly the estimation is fine-grained in an effort to accommodate common practical scenarios, where each tag set consists of tags belonging to different categories. For any two given tag sets, we want to know the detailed information about the joint property of each category, instead of just the aggregate information of the whole sets. Furthermore, due to the open nature of RFID communications, it is often desirable that tag estimation can be performed in an anonymous way without revealing the tags' ID information. To support these requirements, we develop a new technique called mask bitmap that can encode a tag set without requiring the tags to report their IDs or category IDs. Any two mask bitmaps of different tag sets can be combined to perform category-level joint estimation. Through formal analysis, we determine how to set system parameters to meet a given accuracy requirement that can be arbitrarily set. Extensive simulation results confirm that the proposed solution can yield accurate category-level estimates in an efficient way, and preserve tags' anonymity as well.

Traditional radio frequency identification (RFID) technologies allow tags to communicate with a reader but not among themselves. By enabling peer-to-peer communications among nearby tags, the emerging networked tags make a fundamental enhancement to today's RFID systems. This new capability supports a series of system-level functions in previously infeasible scenarios where the readers cannot cover all tags due to cost or physical limitations. This paper makes the first attempt to design a new communication model that is specifically tailored to efficient implementation of system-level functions in networked tag systems. Instead of exploiting complex mechanisms for collision detection and resolution, we propose a collision-resistent communication model (CCM) that embraces the collision in tag communications and utilizes it to merge the data from different sources in a benign way. Two fundamental applications: RFID estimation and missing-tag detection, are presented to illustrate how CCM assists efficient system-level operations in networked tag systems. Simulation results show that system-level applications through CCM outperform those through ID collection.

Radio-frequency identification (RFID) technologies have been widely used in many applications. Tag estimation, which is to estimate the cardinality of a single tag set, is an important research topic. This paper expands the estimation research as follows: It performs joint estimation between two tag sets, and more importantly the estimation is fine-grained in an effort to accommodate common practical scenarios, where each tag set consists of tags belonging to different categories. For any two given tag sets, we want to know the detailed information about the joint property of each category, instead of just the aggregate information of the whole sets. Furthermore, due to the open nature of RFID communications, it is often desirable that category-level joint estimation can be performed in an anonymous way without revealing the tags' IDs. To support these requirements, we develop a new technique called mask bitmap that can encode a tag set without requiring the tags to report their IDs or category IDs. Any two mask bitmaps that encode different tag sets can be combined to perform category-level joint estimation. Simulation results confirm that the proposed solution can yield accurate category-level estimates and preserve tags' anonymity.

Radio-frequency identification (RFID) technology has been widely adopted by real-world industries. This paper presents a new application for distributively deployed RFID systems, wherein a user chooses multiple tag sets at will from different spatial or temporal domains, and then connects them by set operators (union, intersection and relative complement) to form a set expression. The user is allowed to query for the cardinality of an arbitrary set expression, which is called the joint property of multiple sets. We focus on the problem of estimating the joint property with bounded error, which has many potential applications. One of them is to allow users to check the number of tags in an arbitrary tag flow passing through a distributed RFID system. For this problem, we propose a solution with a novel design that supports versatile snapshot construction: Given the snapshots of multiple tag sets, although their lengths may be very different, our formulas can estimate their joint properties, with an accuracy that can be arbitrarily set. For the proposed estimator, we formally analyze its bias and variance, and also the optimal settings of protocol parameters to minimize the time cost of taking a snapshot of a tag set. The simulation results show that, under predefined accuracy requirement, our solution can reduce time cost by multiple folds as compared with existing works named DiffEstm and CCF, which require all tag sets must be encoded into snapshots with an equal length.

In cognitive radio networks (CRNs), primary users (PUs) can leverage secondary users (SUs) as cooperative relays to increase their transmission rates, while SUs will in return obtain more spectrum access opportunities, leading to cooperative CRNs (CCRNs). Prior research works in CCRNs mainly focus on providing ubiquitous access and high throughput for users, but have rarely taken energy efficiency into consideration. Besides, most existing works assume that the SUs are passively selected by PUs regardless of SUs' willingness to help, which is obviously not practical. To address energy issue, this paper proposes an energy-efficient cooperative strategy by leveraging temporal and spatial diversity of the primary network. Specifically, SUs with delay-tolerant packets can proactively make the cooperative decisions by jointly considering primary channel availability, channel state information, PUs' traffic load, and their own transmission requirements. We formulate this decision-making problem based on the optimal stopping theory to maximize SUs' energy efficiency. We solve this problem using a dynamic programming approach and derive the optimal cooperative policy. Extensive simulations are then conducted to evaluate the performance of our proposed strategy. The results show significant improvements of SUs' energy efficiency compared with existing cooperative schemes, which demonstrate the benefits of our proposed cooperative strategy in conserving energy for SUs.

Radio frequency identification (RFID) technology has many applications in inventory management, supply chain, product tracking, transportation, and logistics. One research issue of practical importance is to search for a particular group of tags in a large-scale RFID system. Time efficiency is a crucial factor that must be considered when designing a tag search protocol to ensure its execution will not interfere with other normal inventory operations. In this paper, we design a new technique called filtering vector, which can significantly reduce transmission overhead during search process, thereby shortening search time. Based on this technique, we propose an iterative tag search protocol. In each round, we filter out some tags and eventually terminate the search process when the search result meets the accuracy requirement. Furthermore, we extend our protocol to work under noisy channel. The simulation results demonstrate that our protocol performs much better than the best existing work.

The grouping problem in RFID systems is to efficiently group all tags according to a given partition such that tags in the same group will have the same group ID. Unlike previous research on unicast transmission from a reader to a tag, grouping provides a fundamental mechanism for efficient multicast transmissions and aggregate queries in large RFID-enabled applications. A message can be transmitted to a group of$m$tags simultaneously in multicast, which improves the efficiency by$m$times when comparing with unicast. This paper studies this practically important but not yet thoroughly investigated grouping problem in large RFID system. We start with a straightforward solution called the Enhanced Polling Grouping EPG protocol. We then propose a time-efficient Filter Grouping FIG protocol that uses Bloom filters to remove the costly ID transmissions. We point out the limitation of the Bloom-filter based solution due to its intrinsic false positive problem, which leads to our final ConCurrent Grouping CCG protocol. With a drastically different design, CCG is able to outperform FIG by exploiting collisions to inform multiple tags of their group ID simultaneously and by removing any wasteful slots in its frame-based execution. We further enhance CCG to make it perform better with very large groups. Simulation results demonstrate that our best protocol CCG can reduce the execution time by a factor of 11 when comparing with a baseline polling protocol.

Most existing research adopts a “flat” view of radio frequency identification (RFID) systems to perform various functions of collecting tag IDs, estimating the number of tags, detecting the missing tags, etc. However, in practice, tags are often attached to objects of different groups, which may represent different product types in a warehouse, different book categories in a library, etc. As we move from a flat view to an organized group view, there arise many interesting problems. One of them, called multigroup threshold-based classification, is the focus of this paper. It is to determine whether the number of objects in each group is above or below a prescribed threshold value. Solving this problem is important for inventory tracking applications. If the number of groups is very large, it will be inefficient to measure the groups one at a time. The best existing solution for multigroup threshold-based classification is based on generic group testing, whose design is however geared toward detecting a small number of populous groups. Its performance degrades quickly when the number of groups above the threshold becomes large. In this paper, we propose a new classification protocol based on tag sampling and logical bitmaps. It achieves high efficiency by measuring all groups in a mixed fashion. In the meantime, we show that the new method is able to perform threshold-based classification with an accuracy that can be preset to any desirable level, allowing tradeoff between time efficiency and accuracy.

Future RFID technologies will go far beyond today's widely used passive tags. Battery-powered active tags are likely to gain more popularity due to their long operational ranges and richer on-tag resources. With integrated sensors, these tags can provide not only static identification numbers but also dynamic, real-time information such as sensor readings. This paper studies a general problem of how to design efficient polling protocols to collect such real-time information from a subset M of tags in a large RFID system. We show that the standard, straightforward polling design is not energy-efficient because each tag has to continuously monitor the wireless channel and receive O(|M|) tag IDs, which is energy-consuming. Existing work is able to cut the amount of data each tag has to receive by half through a coding design. In this paper, we propose a tag-ordering polling protocol (TOP) that can reduce per-tag energy consumption by more than an order of magnitude. We also reveal an energy-time tradeoff in the protocol design: per-tag energy consumption can be reduced to O(1) at the expense of longer execution time of the protocol. We then apply partitioned Bloom filters to enhance the performance of TOP, such that it can achieve much better energy efficiency without degradation in protocol execution time. Finally, we show how to configure the new protocols for time-constrained energy minimization.

Many important network functions require online membership lookup against a large set of addresses, flow labels, signatures, and so on. This paper studies a more difficult, yet less investigated problem, called multi-set membership lookup, which involves multiple (sometimes in hundreds or even thousands) sets. The lookup determines not only whether an element is a member of the sets but also which set it belongs to. To facilitate the implementation of multi-set membership lookup in on-die memory of a network processor for line-speed packet inspection, the existing work uses the variants of Bloom filters to encode set IDs. However, through a thorough analysis of the mechanism and the performance of the prior art, much to our surprise, we find that Bloom filters-which were originally designed for encoding binary membership information-are actually not efficient for encoding set IDs. This paper takes a different solution path by separating membership encoding and set ID storage in two data structures, called index filter and set-id table, respectively. With a new ID placement strategy called uneven candidate-entry distribution and a two-level design of an index filter, we demonstrate through analysis and simulation that when compared with the best existing work, our new approach is able to achieve significant memory saving under the same lookup accuracy requirement, or achieve significantly better lookup accuracy under the same memory constraint.

Radio frequency identification (RFID) technologies are widely used in many applications. The widespread use of tags in traditional ways of deployment raises a privacy concern: They make their carriers track able. This paper studies the problem of anonymous authentication. Due to resource constraints of low-cost tags, we develop a new technique to generate dynamic tokens for anonymous authentication by following an asymmetric design principle that pushes most complexity to more powerful RFID readers. Instead of implementing complicated cryptographic hash functions, our authentication protocol only requires tags to perform several simple hardware-efficient operations such as bitwise XOR, one-bit left circular shift and bit flip. Moreover, our protocol reduces the communication overhead and online computation overhead to O(1) per authentication for both tags and readers, which compares favorably with the prior art.

In this paper, we consider an important problem of privacy-preserving point-to-point traffic volume measurement in vehicular cyber physical systems (VCPS), whose focus is utilizing VCPS to enable automatic traffic data collection, and measuring point-to-point traffic volume while preserving the location privacy of all participating vehicles. The novel scheme that we propose tackles the efficiency, privacy, and accuracy problems encountered by previous solutions. Its applicability is demonstrated through both mathematical and numerical analysis. The simulation results also show its superior performance.

Searching for widespread events in large networks is a fundamental function that underlies many important applications of distributed anomaly detection, traffic measurement, online data mining, etc. This function can be performed by a cooperative monitoring system consisting of a central coordinator and a number of monitors that are deployed at a set of vantage points. We formulate a network primitive function, called multi-monitor joint detection, which is to find the common events observed by all or a given subset of monitors during each measurement period. It is a challenging problem because large-scale cooperative monitoring can generate tremendous communication overhead. Therefore, it is critical to design a solution for multi-monitor joint detection which controls communication overhead to a low level. We thoroughly examine existing techniques that may be applied, and identify their performance limitations. We then propose two new techniques, called combinable filters and progressive filtering, which address the performance limitations from different angles. We formally prove the correctness of our new solutions based on a probabilistic joint detection model. Numerical evaluation shows that our best solution achieves an overhead reduction in the range of 63% to 91% over the Bloom filter solution under various simulation settings when the number of monitors is 10 or more.

Per-flow traffic measurement, which is to count the number of packets for each active flow during a certain measurement period, has many applications in usage accounting, traffic engineering, service provision and anomaly detection. In order to maintain the high throughput of routers or switchers, the per-flow traffic measurement module should use high-bandwidth SRAM that allows fast memory accesses. Due to the limited SRAM space, exact counting, which requires to keep a counter for each flow, does not scale to large networks consisting of numerous flows. Some recent work takes a different path to accurately estimate the flow sizes using counter architectures that can fit into tight SRAM. However, existing counter architectures have some limitations, either still requiring considerable SRAM space, or having a very small estimation range. In this paper, we design a scalable counter architecture Counter Tree which leverages a two-dimensional counter sharing scheme to achieve far better memory efficiency and significantly extend estimation range. The extensive experiments with real network trace demonstrate that our counter architecture can produce accurate estimates for flows of all sizes even under a very tight memory space, e.g., 2 bits per flow.

Radio frequency identification (RFID) technologies are making their way into retail products, library books, debit cards, passports, driver licenses, car plates, medical devices, etc. The widespread use of tags in traditional ways of deployment raises a privacy concern: They make their carriers trackable. To protect the privacy of the tag carriers, we need to invent new mechanisms that keep the usefulness of tags while doing so anonymously. Many tag applications such as toll payment require authentication. This paper studies the problem of anonymous authentication. Since low-cost tags have extremely limited hardware resource, we propose an asymmetric design principle that pushes most complexity to more powerful RFID readers. Thus, we develop a lightweight technique that generates dynamic tokens for anonymous authentication. Instead of implementing complicated and hardware-intensive cryptographic hash functions, our authentication protocol only requires tags to perform several simple and hardware-efficient operations such as bitwise XOR, one-bit left circular shift, and bit flip. The theoretic analysis and randomness tests demonstrate that our protocol can ensure the privacy of the tags. Moreover, our protocol reduces the communication overhead and online computation overhead to O(1) per authentication for both tags and readers, which compares favorably with the prior art.

Traditional radio frequency identification (RFID) technologies allow tags to communicate with a reader but not among themselves. By enabling peer communications between nearby tags, the emerging networked tags represent a fundamental enhancement to today's RFID systems. They support applications in previously infeasible scenarios where the readers cannot cover all tags due to cost or physical limitations. This paper is the first study on identifying state-free networked tags, which is a basic, fundamental function for most tagged systems. To prolong the lifetime of networked tags and make identification protocols scalable to large systems, energy efficiency and time efficiency are most critical. Our investigation reveals that the traditional contention-based protocol design will incur too much energy overhead in multihop tag systems. Surprisingly, a reader-coordinated design that significantly serializes tag transmissions performs much better. In addition, we show that load balancing is important in reducing the worst-case energy cost to the tags, and we present a solution based on serial numbers.

In RFID systems, the grouping problem is to efficiently group all tags according to a given partition such that tags in the same group will have the same group ID. Unlike previous research on the unicast transmission from a reader to a tag, grouping provides a fundamental mechanism for efficient multicast transmissions and aggregate queries in large RFID-enabled applications. A message can be transmitted to a group of m tags simultaneously in multicast, which improves the efficiency by m times when comparing with unicast. We study fast grouping protocols in large RFID systems. To the best of our knowledge, it is the first attempt to tackle this practically important yet uninvestigated problem. We start with a straightforward solution called the Enhanced Polling Grouping (EPG) protocol. We then propose a time-efficient FIltering Grouping (FIG) protocol that uses Bloom filters to remove the costly ID transmissions. We point out the limitation of the Bloom-filter based solution due to its intrinsic false positive problem, which leads to our final ConCurrent Grouping (CCG) protocol. With a drastically different design, CCG is able to outperform FIG by exploiting collisions to inform multiple tags of their group ID simultaneously and by removing any wasteful slots in its frame-based execution. Simulation results demonstrate that our best protocol CCG can reduce the execution time by a factor of 11 when comparing with a baseline polling protocol.

Radio-frequency identification (RFID) technology has been widely used in applications such as inventory control, object tracking, supply chain management. An important research is to estimate the number of tags in a certain area covered by readers. This paper extends the research in both temporal and spatial dimensions to provide much richer information for monitoring the dynamics of distributed RFID systems. More specifically, we are interested in estimating the joint properties of any two snapshots taken at arbitrary locations and arbitrary times in a system. With many practical applications, there is however little prior work on this problem. We propose a joint RFID estimation protocol based on a simple yet versatile snapshot construction. Given the snapshots of any two tag sets, although their sizes may be very different, we design a way to combine their information and more importantly derive formulas to extract the joint properties of the two tag sets from the combined information, with an accuracy that can be arbitrarily set. Through formal analysis, we determine the optimal system parameters that minimize the execution time of taking snapshots, under the constraints of a given accuracy requirement. Our simulation results show that the proposed protocol can reduce the execution time by multifold when comparing with the best alternative approach in the literature.

Cardinality estimation over big network data consisting of numerous flows is a fundamental problem with many practical applications. Traditionally the research on this problem focused on using a small amount of memory to estimate each flow's cardinality from a large range (up to $10^9$). However, although the memory needed for each flow has been greatly compressed, when there is an extremely large number of flows, the overall memory demand can still be very high, exceeding the availability under some important scenarios, such as implementing online measurement modules in network processors using only on-chip cache memory. In this paper, instead of allocating a separated data structure (called estimator) for each flow, we take a different path by viewing all the flows together as a whole: Each flow is allocated with a virtual estimator, and these virtual estimators share a common memory space. We discover that sharing at the register (multi-bit) level is superior than sharing at the bit level. We propose a framework of virtual estimators that allows us to apply the idea of sharing to an array of cardinality estimation solutions, achieving far better memory efficiency than the best existing work. Our experiment shows that the new solution can work in a tight memory space of less than 1 bit per flow or even one tenth of a bit per flow --- a quest that has never been realized before.

We study a spectrum auction problem where each request from new spectrum users has spatial, temporal, and spectral features. Our goal is to design truthful auction mechanisms that maximize either the overall social efficiency of new users (a.k.a buyers) or the revenue of the spectrum owner (a.k.a seller). Given that the optimal conflict-free spectrum allocation problem is NP-hard, this paper proposes a series of near-optimal auction mechanisms based on the following approximation techniques: linear programming (LP) relaxation, randomized rounding, derandomized rounding, monotone derandomization, and Lavi-Swamy method. Comparing with the prior art, we make two significant advances: First, our auction mechanisms are not only truthful but also provide theoretically-provable performance guarantee, an important feature that existing work under the same auction model does not have. Second, our auction mechanisms support both spatial and temporal spectral reuse, which makes the problem more challenging than existing work that deals with only spatial or temporal reuse. We perform extensive simulations to study the performance of the proposed mechanisms, and the simulation results corroborate our theoretical analysis.

Data security is a major concern in cloud computing. After clients outsource their data to the cloud, will they lose control of the data? Prior research has proposed various schemes for clients to confirm the existence of their data on the cloud servers, and the goal is to ensure data integrity. This paper investigates a complementary problem: When clients delete data, how can they be sure that the deleted data will never resurface in the future if the clients do not perform the actual data removal themselves? How to confirm the non-existence of their data when the data is not in their possession? One obvious solution is to encrypt the outsourced data, but this solution has a significant technical challenge because a huge amount of key materials may have to be maintained if we allow fine-grained deletion. In this paper, we explore the feasibility of relieving clients from such a burden by outsourcing keys (after encryption) to the cloud. We propose a novel multi-layered key structure, called Recursively Encrypted Red-black Key tree (RERK), that ensures no key materials will be leaked, yet the client is able to manipulate keys by performing tree operations in collaboration with the servers. We implement our solution on the Amazon EC2. The experimental results show that our solution can efficiently support the deletion of outsourced data in cloud computing.

After clients outsource their data to the cloud, they will lose physical control of their data. Many schemes are proposed for clients to verify the integrity of their data. This paper considers a complementary problem: When a client claims that the server has lost their data, how can we be sure that the client is correct and honest about the loss? It is possible that the client's meta data is corrupted or the client is lying in order to blackmail the server. In addition, most previous work relies on sequential indices. However, the indices bring significant overhead to bind an index to each block. We propose to replace sequential indices with much flexible non-sequential {\it coordinates}. The binding of coordinates to data blocks is performed through a Coordinate Merkle Hash Tree (CMHT). Based on CMHT, we can improve both the average and the worst-case update overhead by simplifying the updating algorithm.

With clients losing direct control of their data, this paper investigates an important problem of cloud systems: When clients delete data, how can they be sure that the deleted data will never resurface in the future if the clients do not perform the actual data removal themselves? How to guarantee inaccessibility of deleted data when the data is not in their possession? Using a novel key modulation function, we design a solution for two-party fine-grained assured deletion. The solution does not rely on any third-party server. Each client only keeps one or a small number of keys, regardless of how big its file system is. The client is able to delete any individual data item in any file without causing significant overhead, and the deletion is permanent - no one can recover already-deleted data, not even after gaining control of both the client device and the cloud server. We validate our design through experimental evaluation.

The persistent spread of a destination host is the number of distinct sources that have contacted it persistently in predefined t measurement periods. A persistent spread estimator is a software/hardware component on a router that inspects the arrival packets and estimates the persistent spread of each destination. This is a new primitive for network measurement that can be used to detect long-term stealthy malicious activities, which cannot be recognized by the traditional super spreader detectors that are designed only for "elephant" activities. However, the challenge is to function such an estimator in fast but small memory space (such as on-chip SRAM of line cards), in order to keep up with the high speed of switching fabric for packet forwarding. This paper presents an implementation that can use very tight memory space to deliver high estimation accuracy: Its memory expense is less than one bit per flow element in each time period, Its estimation accuracy is over 90% better than a continuous variant of Flajolet-Martin sketches, Its operating range to produce effective measurements is hundreds of times broader than the traditional bitmap. These advantages originate from a new data structure called multi-virtual bitmap, which is designed to estimate the cardinality of the intersection of an arbitrary number of sets. We have verified the effectiveness of our new estimator using the real network traffic traces from CAIDA.

The ubiquitous use of RFID tags raises concern about potential security risks in RFID systems. Because low-cost tags are extremely resource-constrained devices, common security mechanisms adopted in resource-rich equipment such as computers are no longer applicable to them. Hence, one challenging research topic is to design a lightweight cipher that is suitable for low-cost RFID tags. Traditional cryptography generally assumes that the two communicating parties are equipotent entities. In contrast, there is a large capability gap between readers and tags in RFID systems. We observe that the readers, which are much more powerful, should take more responsibility in RFID cryptographic protocols. In this paper, we make a radical shift from traditional cryptography, and design a novel cipher called Pandaka1, in which most workload is pushed to the readers. As a result, Pandaka is particularly hardware-efficient for tags. We perform extensive simulations to evaluate the effectiveness of Pandaka. In addition, we present security analysis of Pandaka facing different attacks.

Radio frequency identification (RFID) technologies are poised to revolutionize retail, warehouse, and supply chain management. One of their interesting applications is to automatically detect missing tags in a large storage space, which may have to be performed frequently to catch any missing event such as theft in time. Because RFID systems typically work under low-rate channels, past research has focused on reducing execution time of a detection protocol to prevent excessively long protocol execution from interfering normal inventory operations. However, when active tags are used for a large spatial coverage, energy efficiency becomes critical in prolonging the lifetime of these battery-powered tags. Furthermore, much of the existing literature assumes that the channel between a reader and tags is reliable, which is not always true in reality because of noise/interference in the environment. Given these concerns, this paper makes three contributions. First, we propose a novel protocol design that considers both energy efficiency and time efficiency. It achieves multifold reduction in both energy cost and execution time when compared to the best existing work. Second, we reveal a fundamental energy-time tradeoff in missing-tag detection, which can be flexibly controlled through a couple of system parameters in order to achieve desirable performance. Third, we extend our protocol design to consider channel error under two different models. We find that energy/time cost will be higher in unreliable channel conditions, but the energy-time tradeoff relation persists.

Sensor-enabled radio frequency identification (RFID) technology has generated a lot of interest from industries lately. Integrated with miniaturized sensors, RFID tags can provide not only the IDs, but also valuable real-time information about the state of the objects or their surrounding environment, which can benefit many practical applications, such as warehouse management and inventory control. In this paper, we study the problem of designing efficient protocols for a reader to collect sensor-produced information from unknown target tags in an RFID system with minimum execution time. Different from information collection with all target tags known a priori, in the scenarios we consider, the reader has to first find out the target tags in order to read information from them, which makes traditional information collection protocols not efficient any more. We design a Bloom-filter-based information collection protocol (BIC) to address this challenging problem. A Bloom filter is constructed for the reader to efficiently determine the target tags, which significantly reduces the communication and time overhead. We also introduce the allocation vectors to coordinate the transmissions from different tags and minimize collision during information collection. Extensive simulation results demonstrate that our protocol is highly efficient in terms of execution time, and it performs much better than other solutions.

Bloom filters have been extensively applied in many network functions. Their performance is judged by three criteria: query overhead, space requirement, and false positive ratio. Due to wide applicability, any improvement to the performance of Bloom filters can potentially have a broad impact in many areas of networking research. In this paper, we study Bloom-1, a data structure that performs membership check in one memory access, which compares favorably with the k memory accesses of a standard Bloom filter. We also generalize Bloom-1 to Bloom-g and Bloom-Q, allowing performance tradeoff between membership query overhead and false positive ratio. We thoroughly examine the variants in this family of filters, and show that they can be configured to outperform the Bloom filters with a smaller number of memory accesses, a smaller or equal number of hash bits, and a smaller or comparable false positive ratio in practical scenarios. We also perform experiments based on a real traffic trace to support our filter design.

The routing and packet forwarding function is at the core of the IP network-layer protocols. The throughput of a router is constrained by the speed at which the routing table lookup can be performed. Hash-based lookup has been a research focus in this area due to its O(1) average lookup time, as compared to other approachs such as trie-based lookup which tends to make more memory accesses. With a series of prior multi-hashing developments, including d-random, 2-left, and d-left, we discover that a new guided multi-hashing approach holds the promise of further pushing the envelope of this line of research to make significant performance improvement beyond what today's best technology can achieve. Our guided multi-hashing approach achieves near perfect load balance among hash buckets, while limiting the number of buckets to be probed for each key (address) lookup, where each bucket holds one or a few routing entries. Unlike the localized optimization by the prior approaches, we utilize the full information of multi-hash mapping from keys to hash buckets for global key-to-bucket assignment. We have dual objectives of lowering the bucket size while increasing empty buckets, which helps to reduce the number of buckets brought from off-chip memory to the network processor for each lookup. We introduce mechanisms to make sure that most lookups only require one bucket to be fetched. Our simulation results show that with the same number of hash functions, the guided multiple-hashing schemes are more balanced than d-left and others, while the average number of buckets to be accessed for each lookup is reduced by 20–50%.

Radio frequency identification (RFID) technology has many applications in inventory management, supply chain, product tracking, transportation and logistics. One research issue of practical importance is to search for a particular group of tags in a large-scale RFID system. Time efficiency is a core factor that must be taken into consideration when designing a tag search protocol to ensure scalability. In this paper, we design a new technique called filtering vector, which can significantly reduce transmission overhead during search process, thereby shortening search time. Based on this technique, we propose an iterative tag search protocol. In each round, we filter out some tags and eventually terminate the search process when the search result meets the accuracy requirement. The simulation results demonstrate that our protocol performs much better than the best existing ones.

RFID technology has many applications such as object tracking, automatic inventory control, and supply chain management. They can be used to identify individual objects or count the population of each type of objects in a deployment area, no matter whether the objects are passports, retail products, books or even humans. Most existing work adopts a “flat” RFID system model and performs functions of collecting tag IDs, estimating the number of tags, or detecting the missing tags. However, in practice, tags are often attached to objects of different groups, which may represent a different product type in a warehouse, a different book category in a library, etc. An interesting problem, called multigroup threshold-based classification, is to determine whether the number of objects in each group is above or below a prescribed threshold value. Solving this problem is important for inventory tracking applications. If the number of groups is very large, it will be inefficient to measure the groups one at a time. The best existing solution for multigroup threshold-based classification is based on generic group testing, whose design is however geared towards detecting a small number of populous groups. Its performance degrades quickly when the number of groups above the threshold become large. In this paper, we propose a new classification protocol based on logical bitmaps. It achieves high efficiency by measuring all groups in a mixed fashion. In the meantime, we show that the new method is able to perform threshold-based classification with an accuracy that can be pre-set to any desirable level, allowing tradeoff between time efficiency and accuracy.

Efficient estimation of tag population in RFID systems has many important applications. In this paper, we present a new problem called differential cardinality estimation, which tracks the population changes in a dynamic RFID system where tags are frequently moved in and out. In particular, we want to provide quick estimation on (1) the number of new tags that are moved in and (2) the number of old tags that are moved out, between any two consecutive scans of the system. We show that the traditional cardinality estimators cannot be applied here, and the tag identification protocols are too expensive if the estimation needs to be performed frequently in order to support real-time monitoring. This paper presents the first efficient solution for the problem of differential cardinality estimation. The solution is based on a novel differential estimation framework, and is named zero differential estimator. We show that this estimator can be configured to meet any pre-set accuracy requirement, with a probabilistic error bound that can be made arbitrarily small.

Collecting information from mobile peer-to-peer (P2P) networks has important civilian and military applications. One problem is to determine the cardinality, i.e., the number of nodes, in a large mobile system. In a stationary wireless network, it can be trivially solved through a flooding-based query. However, the problem becomes much more challenging for mobile P2P networks whose topologies are constantly changing. In this paper, we present two novel statistical methods, called the circled random walk and the tokened random walk, to address this interesting problem. The circled random walk is simpler to implement and works well in networks of high mobility, whereas the tokened random walk works well with high or low mobility. These methods provide cardinality estimation by involving only a small subset of the nodes. They make tradeoff between overhead and estimation accuracy. The estimation error can be made arbitrarily small at the expense of larger overhead.

Compared to the classical barcode system, radio frequency identification (RFID) extends the operational distance from inches to a number of feet (passive RFID tags) or even hundreds of feet (active RFID tags). Their wireless transmission, processing, and storage capabilities enable them to support full automation of many inventory management functions in industry. This paper studies the practically important problem of monitoring a large set of active RFID tags and identifying the missing ones-the objects that the missing tags are associated with are likely to be missing as well. This monitoring function may need to be executed frequently and therefore should be made efficient in terms of execution time in order to avoid disruption of normal inventory operations. Based on probabilistic methods, we design a series of missing-tag identification protocols that employ novel techniques to reduce the execution time. Our best protocol reduces the time for detecting the missing tags by an order of magnitude when compared to existing protocols.

Spreader classification is an online traffic measurement function that has many important applications. In order to keep up with ever-higher line speed, the recent research trend is to implement such functions in fast but small on-die SRAM. However, the mismatch between the huge amount of Internet traffic to be monitored and limited on-die memory space presents a significant technical challenge. In this paper, we propose an Efficient Spreader Classification (ESC) scheme based on dynamic bit sharing, a compact information storage method. We design a maximum likelihood estimation method to extract per-source information from the compact storage and determine the heavy spreaders. Our new scheme ensures that false positive/negative ratios are bounded. Moreover, given an arbitrary set of bounds, we develop a systematic approach to determine the optimal system parameters that minimize the amount of memory needed to meet the bounds. Experiments based on a real Internet traffic trace demonstrate that the proposed spreader classification scheme reduces memory consumption by 3–20 times when compared to the best existing work. We also investigate a new multi-objective spreader classification problem and extend our classification scheme to solve it.

Maximizing the lifetime of a sensor network has been a subject of intensive study. However, much prior work defines the network lifetime as the time before the first data-generating sensor in the network runs out of energy or is not reachable to the sink due to network partition. The problem is that even though one sensor is out of operation, the rest of the network may well remain operational, with other sensors generating useful data and delivering those data to the sink. Hence, instead of just maximizing the time before the first sensor is out of operation, we should maximize the lifetime vector of the network, consisting of the lifetimes of all sensors, sorted in ascending order. For this problem, there exists only a centralized algorithm that solves a series of linear programming problems with high-order complexities. This paper proposes a fully distributed algorithm that runs iteratively. Each iteration produces a lifetime vector that is better than the vector produced by the previous iteration. Instead of giving the optimal result in one shot after lengthy computation, the proposed distributed algorithm has a result at any time, and the more time spent gives the better result. We show that when the algorithm stabilizes, its result produces the maximum lifetime vector. Furthermore, simulations demonstrate that the algorithm is able to converge rapidly toward the maximum lifetime vector with low overhead.

Cloud storage has been gaining popularity because its elasticity and pay-as-you-go manner. However, this new type of storage model also brings security challenges. This paper studies the problem of ensuring data integrity in cloud storage. In the Proof of Retrievability (PoR) model, after outsourcing the preprocessed data to the server, the client will delete its local copies and only store a small amount of meta data. Later the client will ask the server to provide a proof that its data can be retrieved correctly. However, most of the prior PoR works apply only to static data. The existing dynamic version of PoR scheme has an efficiency problem. In this paper, we extend the static PoR scheme to dynamic scenario. That is, the client can perform update operations, e.g., insertion, deletion and modification. After each update, the client can still detect the data losses even if the server tries to hide them. We develop a new version of authenticated data structure based on a B+ tree and a merkle hash tree. We call it Cloud Merkle B+ tree (CMBT). By combining the CMBT with the BLS signature, we propose a dynamic version of PoR scheme. Compared with the existing dynamic PoR scheme, our worst case communication complexity is O(logn) instead of O(n).

An origin-destination (OD) flow between two routers is the set of packets that pass both routers in a network. Measuring the sizes of OD flows is important to many network management applications such as capacity planning, traffic engineering, anomaly detection, and network reliability analysis. Measurement efficiency and accuracy are two main technical challenges. In terms of efficiency, we want to minimize per-packet processing overhead to accommodate future routers that have extremely high packet rates. In terms of accuracy, we want to generate precise measurement results with small bias and standard deviation. To meet these challenges, we design a new measurement method that employs a compact data structure for packet information storage and uses a novel statistical inference approach for OD-flow size estimation. We perform simulations to demonstrate the effectiveness of our method.

Radio Frequency IDentification (RFID) technology has been adopted in many applications, such as inventory control, object tracking, theft prevention, and supply chain management. Privacy-preserving authentication in RFID systems is a very important problem. Existing protocols employ tree structures to achieve fast authentication. We observe that these protocols require a tag to transmit a large amount of data in each authentication, which costs significant bandwidth and energy overhead. Current protocols also impose heavy computational demand on the RFID reader. To address these issues, we design two privacy-preserving protocols based on a new technique called cryptographical encoding, which significantly reduces both authentication data transmitted by each tag and computation overhead incurred at the reader. Our analysis shows that the new protocols are able to reduce authentication data by more than an order of magnitude and reduce computational demand by about an order of magnitude, when comparing with the best existing protocol.

Sensor-enabled RFID technology has generated a lot of interest from industries lately. Integrated with miniaturized sensors, RFID tags could provide not only the IDs but also valuable real-time information about the state of the corresponding objects or the surrounding environment, which is beneficial to many practical applications, such as warehouse management and inventory control. In this paper, we study the problem on how to design efficient protocols to collect such sensor information from numerous tags in a large-scale RFID system with a number of readers deployed. Different from information collection in the small RFID system covered by only one reader, in the multi-reader scenario, each reader has to first find out which tags located in its interrogation region in order to read information from them. We start with two categories of warm-up solutions that are directly extended from the existing information collection protocols for single-reader RFID systems, and show that all of them do not work well for the multi-reader information collection problem due to their inefficiency of identifying the interrogated tags. Then, we propose a novel solution, called the Bloom filter based Information Collection protocol (BIC). In BIC, the interrogated tag identification can be efficiently achieved with a distributively constructed Bloom filter, which significantly reduces the communication overhead and thus the protocol execution time. Extensive simulations show that BIC performs better than all the warm-up solutions and its execution time is within 3 times of the lower bound.

RFID (radio frequency identification) technologies are poised to revolutionize retail, warehouse and supply chain management. One of their interesting applications is to automatically detect missing tags (and the associated objects) in a large storage space. In order to timely catch any missing event such as theft, the detection operation may have to be performed frequently. Because RFID systems typically work under low-rate channels, past research has focused on reducing execution time of a detection protocol, in order to prevent excessively-long protocol execution from interfering normal inventory operations. However, when active tags are used to provide a large spatial coverage, energy efficiency becomes critical in prolonging the lifetime of these battery-powered tags. Existing literature lacks thorough study on how to conserve energy in the process of missing-tag detection and how to jointly optimize energy efficiency and time efficiency. This paper makes two important contributions: First, we propose a novel protocol design that takes both energy efficiency and time efficiency into consideration. It achieves multi-fold reduction in both energy cost and execution time when comparing with the best existing work. In some cases, the reduction is more than an order of magnitude. Second, we reveal a fundamental energy-time tradeoff in missing-tag detection. Through our analytical framework, we are able to flexibly control the tradeoff through a couple of system parameters in order to achieve desirable performance.

Traffic measurement provides critical real-world data for service providers and network administrators to perform capacity planning, accounting and billing, anomaly detection, and service provision. One of the greatest challenges in designing an online measurement module is to minimize the per-packet processing time in order to keep up with the line speed of the modern routers. To meet this challenge, we should minimize the number of memory accesses per packet and implement the measurement module in the on-die SRAM. The small size of SRAM requires extremely compact data structures to be designed for storing per-flow information. The best existing work, called counter braids, requires more than 4 bits per flow and performs six or more memory accesses per packet. In this paper, we design a fast and compact measurement function that estimates the sizes of all flows. It achieves the optimal processing speed: two memory accesses per packet. In addition, it provides reasonable measurement accuracy in a tight space where the counter braids no longer work. Our design is based on a new data encoding/decoding scheme, called randomized counter sharing. This scheme allows us to mix per-flow information together in storage for compactness and, at the decoding time, separate the information of each flow through statistical removal of the error introduced during information mixing from other flows. The effectiveness of our online per-flow measurement approach is analyzed and confirmed through extensive experiments based on real network traffic traces. We also propose several methods to increase the estimation range of flow sizes.

Radio frequency identification (RFID) has been gaining popularity for inventory control, object tracking, and supply-chain management in warehouses, retail stores, hospitals, etc. Periodically and automatically estimating the number of RFID tags deployed in a large area has many important applications in inventory management and theft detection. Prior works focus on designing time-efficient algorithms that can estimate tens of thousands of tags in seconds. We observe that for an RFID reader to access tags in a large area, active tags are likely to be used due to their longer operational ranges. These tags are battery-powered and use their own energy for information transmission. However, recharging batteries for tens of thousands of tags is laborious. Hence, conserving energy for active tags becomes critical. Some prior works have studied how to reduce energy expenditure of an RFID reader when it reads tag IDs. We study how to reduce the amount of energy consumed by active tags during the process of estimating the number of tags in a system. We design two energy-efficient probabilistic estimation algorithms that iteratively refine a control parameter to optimize the information carried in transmissions from tags, such that both the number and the size of transmissions are reduced. These algorithms can also take time efficiency into consideration. By tuning a contention probability parameter$\omega$, the new algorithms can make tradeoff between energy cost and estimation time.

Radio-Frequency Identification (RFID) technology brings many innovative applications. Of great importance to RFID applications in production economics is misplaced-tag pinpointing (MTP), because misplacement errors fail optimal inventory placement and thus significantly decrease profit. The existing MTP solution [1], originally proposed from a data-processing perspective, collects and processes a large amount of data. It suffers from time inefficiency (and energy-inefficiency as well if active tags are in use). The problem of finding efficient solutions for the MTP problem from the communication protocol design perspective has never been investigated before. In this paper, we propose a series of protocols toward efficient MTP solutions in large RFID systems. The proposed protocols detect misplaced tags using reader positions instead of tag positions to guarantee the efficiency and scalability as system scale grows, because RFID readers are much fewer than tags. Considering applications that employ active tags, we further propose a solution requiring responses from only a subset of tags in favor of energy saving. We also design a distributed protocol that enables each reader to independently detect misplaced tags. We then investigate how to apply the proposed protocols in scenarios with tag mobility. To evaluate the proposed protocols, we analyze their optimal performances to demonstrate their efficiency potential and also conduct extensive simulation experiments. The results show that the proposed protocols can significantly increase the time efficiency and the energy efficiency by over 70 percent on average when compared with the best existing work.

Similar to the revolutionary change that the barcode system brought to the retail industry, the RFID technologies are expected to revolutionize the warehouse and inventory management. After RFID tags are deployed to make the attached objects wirelessly identifiable, a natural next step is to invent new ways to benefit from this “infrastructure”. For example, sensors may be added to these tags to gather real-time information about the state of the objects or about the environment where these objects reside. This leads to the problem of designing efficient protocols to collect such information from the tags. It is a new problem that the existing work cannot solve well. In this paper, we first show that a straightforward polling solution will not be efficient. We then propose a single-hash information collection protocol that works much better than the polling solution. However, a wide gap still exists between the execution time of this protocol and a lower bound that we establish. Finally, we propose a multi-hash information collection protocol that further reduces the expected execution time to within 1.61 times the lower bound.

IP lookup is one of the key functions in the design of core routers. Its efficiency determines how fast a router can forward packets. As new content is continuously brought to the Internet, novel routing technologies must be developed to meet the increasing throughput demand. Hash-based lookup schemes are promising because they have low lookup delays and can handle large routing tables. To achieve high throughput, we must choose the hash function to reduce the lookup bandwidth from the off-chip memory where the routing table is stored. The routing table updates also need to be handled to avoid costly re-setup. In this paper, we propose AP-Hash, an approximately perfect hashing approach that not only distributes routing-table entries evenly in the hash buckets but also handles routing table updates with low overhead. We also present an enhanced approach, called AP-Hash-E, which is able to process far more updates before a complete re-setup becomes necessary. Experimental results based on real routing tables show that our new hashing approaches achieve a throughput of 250M packets per second and perform re-setup as few as just once per month.

Traffic measurement provides critical real-world data for service providers and network administrators to perform capacity planning, accounting and billing, anomaly detection, and service provision. One of the greatest challenges in designing an online measurement module is to minimize the per-packet processing time in order to keep up with the line speed of the modern routers. To meet this challenge, we should minimize the number of memory accesses per packet and implement the measurement module in the on-die SRAM. The small size of SRAM requires extremely compact data structures to be designed for storing per-flow information. The best existing work, called counter braids, requires more than 4 bits per flow and performs 6 or more memory accesses per packet. In this paper, we design a fast and compact measurement function that estimates the sizes of all flows. It achieves the optimal processing speed: 2 memory accesses per packet. In addition, it provides reasonable measurement accuracy in a tight space where the counter braids no longer work. Our design is based on a new data encoding/decoding scheme, called randomized counter sharing. This scheme allows us to mix per-flow information together in storage for compactness and, at the decoding time, separate the information of each flow through statistical removal of the error introduced during information mixing from other flows. The effectiveness of our online per-flow measurement approach is analyzed and confirmed through extensive experiments based on real network traffic traces.

Scan detection is one of the most important functions in intrusion detection systems. In order to keep up with the ever-higher line speed, recent research trend is to implement scan detection in fast but small SRAM. This leads to a difficult technical challenge because the amount of traffic to be monitored is huge but the on-die memory space for performing such a monitoring task is very limited. We propose an efficient scan detection scheme based on dynamic bit sharing, which incorporates probabilistic sampling and bit sharing for compact information storage. We design a maximum likelihood estimation method to extract persource information from the shared bits in order to determine the scanners. Our new scheme ensures that the false positive/false negative ratios are bounded with high probability. Moreover, given an arbitrary set of bounds, we develop a systematic approach to determine the optimal system parameters that minimize the amount of memory needed to meet the bounds. Experiments based on a real Internet traffic trace demonstrate that the proposed scan detection scheme reduces memory consumption by three to twenty times when comparing with the best existing work.

RFID tags have many important applications in automated warehouse management. One example is to monitor a set of tags and detect whether some tags are missing - the objects to which the missing tags are attached are likely to be missing, too, due to theft or administrative error. Prior research on this problem has primarily focused on efficient protocols that reduce the execution time in order to avoid disruption of normal inventory operations. This paper makes several new advances. First, we observe that the existing protocol is far from being optimal in terms of execution time. We are able to cut the execution time to a fraction of what is currently needed. Second, we study the missing-tag detection problem from a new energy perspective, which is very important when battery-powered active tags are used. The new insight provides flexibility for the practitioners to meet their energy and time requirements.

The Bloom filters have been extensively applied in many network functions. Their performance is judged by three criteria: processing overhead, space overhead, and false positive ratio. Due to wide applicability, any improvement to the performance of Bloom filters can potentially have broad impact in many areas of networking research. In this paper, we propose Bloom-1, a new data structure that performs membership check in one memory access, which compares favorably with the k memory accesses of a classical Bloom filter. We also generalize Bloom-1 to Bloom-g, allowing performance tradeoff between membership query overhead and false positive ratio. We thoroughly examine the variants in this new family of filters, and show that they can be configured to outperform the Bloom filters with a smaller number of memory accesses, a smaller or equal number of hash bits, and a smaller and comparable false positive ratio in practical scenarios. We also perform experiments based on a real traffic trace to support our new filter design.

Future RFID technologies will go far beyond today's widely-used passive tags. Battery-powered active tags are likely to gain more popularity due to their long operational ranges and richer on-tag resources. With integrated sensors, these tags can provide not only static identification numbers but also dynamic, real-time information such as sensor readings. This paper studies a general problem of how to design efficient polling protocols to collect such real-time information from a subset M of tags in a large RFID system. We show that the standard, straightforward polling design is not energy-efficient because each tag has to continuously monitor the wireless channel and receive O(|M|) tag IDs, which is energy-consuming. Existing work is able to cut the amount of data each tag has to receive by half through a coding design. In this paper, we propose a tag-ordering polling protocol (TOP) that can reduce per-tag energy consumption by more than an order of magnitude. We also reveal an energy-time tradeoff in the protocol design: per-tag energy consumption can be reduced to O(1) at the expense of longer execution time of the protocol. Finally, we apply partitioned Bloom filters to enhance the performance of TOP, such that it can achieve much better energy efficiency without degradation in protocol execution time.

The Radio-Frequency Identification (RFID) technology has stimulated many innovative applications. Misplaced-tag pinpointing (MTP) is important to RFID applications in production economics because optimal inventory placement can significantly increase profit. Previous research from the database perspective needs to process a large amount of data which is time-consuming to collect (and energy-consuming if active tags are used). How to efficiently address the MTP problem from the protocol design perspective however has not been investigated. In this paper, we propose a series of protocols toward efficient MTP solution in large RFID systems. The proposed protocols detect misplaced tags based on reader positions instead of tag positions to guarantee the efficiency and scalability as system scale grows, because the number of readers is much smaller than that of tags. Considering applications to employ more and more popular active tags, we further propose a solution requiring responses from only partial tags in favor of energy saving. We analyze the optimal performances of proposed protocols to demonstrate their efficiency potential and conduct extensive simulation experiments to evaluate their performance under various scenarios. The results show that the proposed protocols can significantly increase the time efficiency and the energy efficiency by over 70% on average when compared with the state of the art.

We demonstrate that CSMA/CA networks, including IEEE 802.11 networks, exhibit severe fairness problem in many scenarios, where some hosts obtain most of the channel's bandwidth while others starve. Most existing solutions require nodes to overhear transmissions made by contending nodes and, based on the overheard information, adjust local rates to achieve fairness among all contending links. Their underlying assumption is that transmissions made by contending nodes can be overheard. However, this assumption holds only when the transmission range is equal to the interference range, which is not true in reality. As our study reveals, the overhearing-based solutions, as well as several nonoverhearing AIMD solutions, cannot achieve MAC-layer fairness in various settings. We propose a new rate control protocol, called Proportional Increase Synchronized multiplicative Decrease (PISD). Without relying on overhearing, it provides fairness in CSMA/CA networks, particularly IEEE 802.11 networks, by using only local information and performing localized operations. It combines several novel rate control mechanisms, including synchronized multiplicative decrease, proportional increase, and background transmission. We prove that PISD converges and achieves (weighted) fairness. We further introduce Queue Spreading (QS) to achieve MAC-layer fairness when there are multiple contention groups, in which case PISD will fail.

The spread of a source host is the number of distinct destinations that it has sent packets to during a measurement period. A spread estimator is a software/hardware module on a router that inspects the arrival packets and estimates the spread of each source. It has important applications in detecting port scans and distributed denial-of-service (DDoS) attacks, measuring the infection rate of a worm, assisting resource allocation in a server farm, determining popular Web contents for caching, to name a few. The main technical challenge is to fit a spread estimator in a fast but small memory (such as SRAM) in order to operate it at the line speed in a high-speed network. In this paper, we design a new spread estimator that delivers good performance in tight memory space where all existing estimators no longer work. The new estimator not only achieves space compactness, but operates more efficiently than the existing ones. Its accuracy and efficiency come from a new method for data storage, called virtual vectors, which allow us to measure and remove the errors in spread estimation. We also propose several ways to enhance the range of spread values that the estimator can measure. We perform extensive experiments on real Internet traces to verify the effectiveness of the new estimator .

Contention among multiple nearby WLANs in urban areas may cause severe TCP unfairness, where some TCP flows can achieve very high throughput at the expense of starving others. This unfairness results from the fact that different physical nodes conveying TCP flows at a wireless bottleneck may have different channel observations and consequently they may provide inconsistent feedbacks to the TCP sources. Existing solutions to this problem try to synchronize channel observations of contending nodes by exchanging control messages among them. They rely on the assumption that these nodes are within each other''s transmission range, which however may not always hold. In this paper, we propose a new approach, called Wireless Probabilistic Drop (WPD), to improve TCP fairness without requiring direct communication among nodes. In WPD, when a node detects congestion, it probabilistically chooses to either drop some packets to resolve the congestion, or aggressively spread the congestion signal to other contending nodes. Each node makes the choice with a probability that is proportional to its flow rate. Henceforth, high-rate flows tend to perform rate reduction more often, and low-rate flows are more likely to increase their flow rates. Eventually, all flows passing the bottleneck are expected to get a fair share of the channel bandwidth. Extensive simulations in ns-2 demonstrate that WPD can significantly improve fairness among TCP flows across multiple contending WLANs.

End-to-end fairness in a sensor network ensures that data from each sensor has an equal (or weighted) chance to reach the sink. It eliminates the problem that data flows from sensors at some locations (close to the sink) obtain most network bandwidth, while flows from sensors at other locations (far away from the sink) are starved. Existing fairness solutions assume single-path routing, which reduces achievable throughput of the network. In this paper, we propose a multipath fairness solution (MFS) that achieves end-to-end fairness among competing flows through fully distributed operations. MFS is easy to implement, which is advantageous in a resource-scarce sensor network. More importantly, it achieves much higher network throughput and better fairness among the flows.

RFID promises to revolutionize the inventory management in large warehouses, retail stores, hospitals, transportation systems, etc. Periodically reading the IDs of the tags is an important function to guard against administration error, vendor fraud and employee theft. Given the low-speed communication channel in which a RFID system operates, the reading throughput is one of the most important performance metrics. The current protocols have reached the physical throughput limit that can possibly be achieved based on their design methods. To break that limit, we have to apply fundamentally different approaches. This paper investigates how much throughput improvement the analog network coding can bring when it is integrated into the RFID protocols. The idea is to extract useful information from collision slots when multiple tags transmit their IDs simultaneously. Traditionally, those slots are discarded. With analog network coding, we show that a collision slot is almost as useful as a non-collision slot in which exactly one tag transmits. We propose the framed collision-aware tag identification protocol that optimally applies analog network coding to maximize the reading throughput, which is 51.1% ~ 70.6% higher than the best existing protocols.

New generations of video, voice, high-performance computing and social networking applications have continuously driven the development of novel routing technologies for higher packet forwarding speeds to meet the future Internet demand. One of the fundamental design issues for core routers is fast routing table lookup, which is a key problem at the network layer of the Internet protocol suite. It is difficult to scale the current TCAM-based or trie-based solutions for future routing tables due to increasing table size, longer prefix length, and demands for higher throughput. This paper focuses on hash-based lookup solutions that have the potential of offering high throughput at one memory access per packet. We design the first deterministic multi-hashing scheme with small indexing overhead, which evenly distributes address prefixes to hash buckets for routing-information storage. We minimize both the size of each bucket and the number of buckets that need to be fetched to the network processor for packet forwarding. Consequently, near-optimal routing throughput is achieved. Performance evaluations demonstrate that the proposed deterministic multi-hashing scheme can maintain a constant lookup rate of over 250 million packets per second with today's commodity SRAM, which is much faster than the existing hashing schemes.

RFID has been gaining popularity for inventory control, object tracking, and supply chain management in warehouses, retail stores, hospitals, etc. Periodically and automatically estimating the number of RFID tags deployed in a large area has many important applications in inventory management and theft detection. The prior work focuses on designing time-efficient algorithms that can estimate tens of thousands of tags in seconds. We observe that, for a RFID reader to access tags in a large area, active tags are likely to be used. These tags are battery-powered and use their own energy for information transmission. However, recharging batteries for tens of thousands of tags is laborious. Unlike the prior work, this paper studies the RFID estimation problem from the energy angle. Our goal is to reduce the amount of energy that is consumed by the tags during the estimation procedure. We design several energy-efficient probabilistic algorithms that iteratively refine a control parameter to optimize the information carried in the transmissions from the tags, such that both the number and the size of the transmissions are minimized.

Wireless LANs have been densely deployed in many urban areas. Contention among nearby WLANs is location-sensitive, which makes some hosts much more capable than others to obtain the channel for their transmissions. Another reality is that wireless hosts use different transmission rates to communicate with the access points due to attenuation of their signals. We show that location-sensitive contention aggravates the throughput anomaly caused by different transmission rates. It can cause throughput degradation and host starvation. This paper studies the intriguing interaction between location-sensitive contention and time fairness across contending WLANs. Achieving time fairness across multiple WLANs is a very difficult problem because the hosts may perceive very different channel conditions and they may not be able to communicate and coordinate their operations due to the disparity between the interference range and the transmission range. In this paper, we design a MAC-layer time fairness solution based on two novel techniques: channel occupancy adaptation, which applies AIMD on the channel occupancy of each flow, and queue spreading, which ensures that all hosts and only those hosts in a saturated channel detect congestion and reduce their channel occupancies in response. We show that these two techniques together approximate the generic adaptation algorithm for proportional fairness.

Comparing with the classical barcode system, RFID extends the operational distance from inches to a number of feet (passive RFID tags) or even hundreds of feet (active RFID tags). Their wireless transmission, processing and storage capabilities enable them to support the full automation of many inventory management functions in the industry. This paper studies the practically important problem of monitoring a large set of RFID tags and identifying the missing ones - the objects that the missing tags are associated with are likely to be missing, too. This monitoring function may need to be executed frequently and therefore should be made efficient in terms of execution time, in order to avoid disruption of normal inventory operations. Based on probabilistic methods, we design a series of missing-tag identification protocols that employ novel techniques to reduce the execution time. Our best protocol reduces the time for detecting the missing tags by 88.9% or more, when comparing with existing protocols.

A firewall's complexity is known to increase with the size of its rule set. Empirical studies show that as the rule set grows larger, the number of configuration errors on a firewall increases sharply, while the performance of the firewall degrades. When designing a security-sensitive network, it is critical to construct the network topology and its routing structure carefully in order to reduce the firewall rule sets, which helps lower the chance of security loopholes and prevent performance bottleneck. This paper studies the problems of how to place the firewalls in a topology during network design and how to construct the routing tables during operation such that the maximum firewall rule set can be minimized. These problems have not been studied adequately despite their importance. We have two major contributions. First, we prove that the problems are NP-complete. Second, we propose a heuristic solution and demonstrate the effectiveness of the algorithm by simulations. The results show that the proposed algorithm reduces the maximum firewall rule set by 2-5 times when comparing with other algorithms.

In recent years, both sophistication and damage potential of Internet worms have increased tremendously. To understand their threat, we need to look into their payload for signatures as well as propagation pattern for Internet-scale behavior. An accurate analytical propagation model allows us to comprehensively study how a worm propagates under various conditions, which is often computationally too intensive for simulations. More importantly, it gives us an insight into the impact of each worm/network parameter on the propagation of the worm. Traditionally, most modeling work in this area concentrates on the relatively simple random-scanning worms. However, modeling the permutation-scanning worms, a class of worms that are fast yet stealthy, has been a challenge to date. This paper proposes a mathematical model thatpreciselycharacterizes the propagation patterns of the general permutation-scanning worms. The analytical framework captures the interactions among all infected hosts by a series of interdependent differential equations, which are then integrated into closed-form solutions that together present the overall worm behavior. We use the model to study how each worm/network parameter affects the worm propagation. We also investigate the impact of dynamic network conditions on the correctness of the model.

We study the power-aware buffering problem in battery-powered sensor networks, focusing on the fixed-size and fixed-interval buffering schemes. The main motivation is to address the yet poorly understood size variation-induced effect on power-aware buffering schemes. Our theoretical analysis elucidates the fundamental differences between the fixed-size and fixed-interval buffering schemes in the presence of data-size variation. It shows that data-size variation has detrimental effects on the power expenditure of the fixed-size buffering in general, and reveals that the size variation induced effects can be either mitigated by a positive skewness or promoted by a negative skewness in size distribution. By contrast, the fixed-interval buffering scheme has an obvious advantage of being eminently immune to the data-size variation. Hence the fixed-interval buffering scheme is a risk-averse strategy for its robustness in a variety of operational environments. In addition, based on the fixed-interval buffering scheme, we establish the power consumption relationship between child nodes and parent node in a static data-collection tree, and give an in-depth analysis of the impact of child bandwidth distribution on the parent's power consumption. This study is of practical significance: it sheds new light on the relationship among power consumption of buffering schemes, power parameters of radio module and memory bank, data arrival rate, and data-size variation, thereby providing well-informed guidance in determining an optimal buffer size (interval) to maximize the operational lifespan of sensor networks.

Sensor networks deployed in hostile areas are subject to node replication attacks, in which an adversary compromises a few sensors, extracts the security keys, and clones them in a large number of replicas, which are introduced into the network to perform insider attacks. Memory overhead, energy efficiency and detection probability are the main technical concerns for any replication detection protocol. The previous distributed solutions either require network-wide spontaneous change of pseudo-random numbers or incur significant memory and energy overhead to the sensors, especially in the central area of the deployment. In this paper, we propose four replication detection protocols that have high detection probability, low memory requirement, and balanced energy consumption. The new protocols use Bloom filters to compress the information stored at the sensors, and use two new techniques, called cell forwarding and cross forwarding, to improve detection probability, further reduce memory consumption, and in the mean time distribute the memory and energy overhead evenly across the whole network. Simulations show that the protocols can achieve nearly 100% detection probability with average memory reduction up to 91%.

The spread of a source host is the number of distinct destinations that it has sent packets to during a measurement period. A spread estimator is a software/hardware module on a router that inspects the arrival packets and estimates the spread of each source. It has important applications in detecting port scans and DDoS attacks, measuring the infection rate of a worm, assisting resource allocation in a server farm, determining popular Web contents for caching, to name a few. The main technical challenge is to fit a spread estimator in a fast but small memory (such as SRAM) in order to operate it at the line speed in a high-speed network. In this paper, we design a new spread estimator that delivers good performance in tight memory space where all existing estimators no longer work. The new estimator not only achieves space compactness but operates more efficiently than the existing ones. Its accuracy and efficiency come from a new method for data storage, called virtual vectors, which allow us to measure and remove the errors in spread estimation. We perform experiments on real Internet traces to verify the effectiveness of the new estimator.

Maximizing the operational lifetime of a sensor network is a critical problem in practice. Many prior works define the network's lifetime as the time before the first sensor in the network runs out of energy. However, when one sensor dies, the rest of the network can still work, as long as useful data generated by other sensors can reach the sink. More appropriately, we should maximize the lifetime vector of the network, consisting of the lifetimes of all sensors, sorted in ascending order. For this problem, there exists only a centralized algorithm that solves a series of linear programming problems with high-order complexities. This paper proposes a fully distributed progressive algorithm which iteratively produces a series of lifetime vectors, each better than the previous one. Instead of giving the optimal result in one shot after lengthy computation, the proposed distributed algorithm has a result at any time, and the more time spent gives the better result. We show that when the algorithm stabilizes, its result produces the maximum lifetime vector. Furthermore, simulations demonstrate that the algorithm is able to converge rapidly towards the maximum lifetime vector with low overhead.

Detecting spreaders can help an intrusion detection system identify potential attackers. The existing work can only detect aggressive spreaders that scan a large number of distinct addresses in a short period of time. However, stealthy spreaders may perform scanning deliberately at a low rate. We observe that these spreaders can easily evade the detection because their small traffic footprint will be covered by the large amount of background normal traffic that frequently flushes any spreader information out of the intrusion detection system's memory. We propose a new streaming scheme to detect stealthy spreaders that are invisible to the current systems. The new scheme stores information about normal traffic within a limited portion of the allocated memory, so that it will not interfere with spreaders' information stored elsewhere in the memory. The proposed scheme is light weight; it can detect invisible spreaders in high-speed networks while residing in SRAM. Through experiments using real Internet traffic traces, we demonstrate that our new scheme detects invisible spreaders efficiently while keeping both false-positives (normal sources misclassified as spreaders) and false-negatives (spreaders misclassified as normal sources) to low level.

A wireless mesh network (WMN) provides a flexible and low-cost solution for end users to connect to the Internet through its multi-hop infrastructure. For such a network to proliferate, a fundamental problem that must be solved is to ensure the fair allocation of network bandwidth to all participating parties. This paper proposes a cross-layer design for achieving end-to-end maxmin fairness in WMNs. At the network layer, it allocates maxmin shares of network capacity to end-to-end flows. At the MAC layer, it realizes the maxmin bandwidth allocation through a two-level packet scheduling algorithm. The proposed design is able to equalize the end-to-end bandwidth allocation to competing flows that share common bottlenecks, while fully utilizing the network capacity. Comparing with previous works, our solution has two advantages. It is based on the popular IEEE 802.11 DCF. It achieves far better fairness (or weighted fairness) among end-to-end flows.

In wireless sensor networks (WSNs), timeliness is one of the most challenging problems for critical applications. Caccamo et al. designed a collision-free real-time MAC protocol for sensor networks by adopting the "cellular structure" in traditional telecommunication networks. They assumed that sensors are organized into many rigid hexagon cells and a router node is at the center of each cell to transmit inter-cell packets. By exploiting FDMA and TDMA, transmission collisions are avoided and real-time guarantees are provided. However, we observe that for inter-cell communication, idle-slots caused by the TDMA-based scheduling will degrade the throughput and delay performance of the entire network, especially for some real applications in which data flows have traffic-direction partiality characteristics. In the worst case, five sixths of inter-cell bandwidth will be wasted. In this paper, we propose four idle-slot recycling algorithms to improve channel utilization. Simulation results show that our proposed algorithms can greatly increase network throughput and decrease packet transmission delay, while the collision-free and real-time qualities of Caccamo's protocol are still retained.

The possibility of using purely text stream (keyboard-enterable) as carrier of malware is under-researched and often under estimated. A text attack can happen at multiple levels, from code-injection attacks at the top level to host-compromising text-based machine code at the lowest level. Since a large number of protocols are text-based, at times the servers based on those protocols use ASCII filters to allow text input only. However, simply applying ASCII filters to weed out the binary data is not enough from the security viewpoint since the assumption that malware are always binary is false. We show that although text is a subset of binary, binary malware detectors cannot always detect text malware. We analyze the MEL (maximum executable length)-based detection schemes, and make two contributions by this analysis. First, although the concept of MEL has been used in various detection schemes earlier, we are the first to provide its underlying mathematical foundation. We show that the threshold value can be calculated from the input character frequencies and that it can be tuned to control the detection sensitivity. Second, we demonstrate the effectiveness of a MEL-based text malware detector by exploiting the specific properties of text streams.

Following the huge commercial success of WLAN, multihop wireless networks are expected to lead in the next wave of deployment. Fundamental methods for traffic engineering must be developed to support diverse application requirements in these networks. This paper studies the problem of how to support weighted bandwidth allocation among all end-to-end flows in a multihop wireless network. Our goal is to enable the network to adapt the flow rates such that global maxmin can be achieved. Our approach is to transform the global maxmin objective into four local conditions and design a distributed rate adaptation protocol based on those local conditions. Comparing with the prior art, our protocol has a number of advantages. It is designed for the popular IEEE 802.11 DCF. It replaces per-flow queueing with per-destination queueing. It achieves far better fairness (or weighted fairness) among end-to-end flows.

Fine-level rate control, particularly meeting rate requirements and differentiating various types of end-to-end traffic, remains an open problem for multihop wireless networks. Traditionally, rate assurance in wired networks is achieved through resource reservation and admission control, which can be efficiently implemented since the bandwidth capacity of each communication link is known and the sender of a link has the information of all flows that compete for the bandwidth of the link. In a wireless network, however, the capacity of each wireless link can change unpredictably over time due to contention from nearby links and dynamic channel conditions. An end-to-end flow consumes available bandwidth not only at links on its route but also at all nearby contending links, which makes resource reservation extremely complicated. We believe fundamental differences require a fundamentally different paradigm shift in solutions. Is there a simpler alternative to resource reservation and admission control that is better suited for wireless network dynamics? In this paper, we propose a new adaptive rate control function based on two novel protocols, called dynamic weight adaptation with floor and ceiling and proportional packet scheduling, which together implement prioritized rate assurance and sophisticated bandwidth differentiation among all end-to-end flows in a multihop wireless network without resource reservation and admission control. The adaptive function achieves global rate control objectives in a fully distributed way using only localized operations.

Modeling worm propagation has been an important research subject in the Internet-worm research community. An accurate analytical propagation model allows us to study the spreading speed and traffic pattern of a worm under an arbitrary set of worm/network parameters, which is often computationally too intensive for simulations. More importantly, it gives us an insight into the impact of each worm/network parameter on the propagation of the worm and the effectiveness of a potential defense mechanism that is designed to control some of those parameters. Traditionally, most modeling work in the area concentrates on the relatively simple random-scanning worms. However, worm technologies have advanced rapidly in recent years. By enabling close coordination among all infected hosts, the permutation-scanning worms minimize the duplication of effort when scanning the whole Internet address space. They propagate much faster, and more importantly, can be much more stealthy than the random-scanning worms. Modeling these worms, however, remains a challenge to date. This paper proposes a mathematical model that precisely characterizes the propagation patterns of the permutation-scanning worms. The analytical framework captures the interactions among all infected hosts by a series of inter-dependent differential equations, which together present the overall behavior of the worm. We use simulations to verify the numerical results from the model, and demonstrate how the model can be used to study the impact of various worm/network parameters on the propagation.

While a considerable amount of research has been done for detecting the binary worms exploiting the vulnerability of buffer overflow, very little effort has been spent in detecting worms that consist of only text, Le., printable ASCII characters. We show that the existing worm detectors often either do not examine the ASCII stream or are not well suited to efficiently detect worms in the ASCII stream due to the structural properties of the ASCII payload. In this paper, we analyze the potentials and constraints of the ASCII worms vis-a-vis their binary counterpart, and devise a detection technique that would exploit those limitations. We introduce DAWN, a novel ASCII worm detection strategy that is fast, easily deployable, and has very little overhead. Unlike many signature-based detection methods, DAWN is completely signature-free and therefore capable of detecting zero-day outbreak of ASCII worms.

We demonstrate that CSMA/CA networks, including IEEE 802.11 networks, exhibit severe fairness problem in many scenarios, where some hosts obtain most of the channel's bandwidth while others starve. Most existing solutions require nodes to overhear transmissions made by contending nodes and, based on the overheard information, adjust local rates to achieve fairness among all contending links. Their underlying assumption is that transmissions made by contending nodes can be overheard. However, this assumption holds only when the transmission range is equal to the carrier sensing range, which is not true in reality. As our study reveals, the overhearing-based solutions, as well as several non-overhearing AIMD solutions, cannot achieve MAC-layer fairness in various settings. We propose a new rate control protocol, called PISD (Proportional Increase Synchronized multiplicative Decrease). Without relying on overhearing, it provides fairness in CSMA/CA networks, particularly IEEE 802.11 networks, by using only local information and performing localized operations. It combines several novel rate control mechanisms, including synchronized multiplicative decrease, proportional increase, and background transmission. We prove that PISD converges and achieves (weighted) fairness.

Due to the open nature of a sensor network, it is relatively easy for an adversary to eavesdrop and trace packet movement in the network in order to capture the receiver physically. After studying the adversary's behavior patterns, we present countermeasures to this problem. We propose a locationprivacy routing protocol (LPR) that is easy to implement and provides path diversity. Combining with fake packet injection, LPR is able to minimize the traffic direction information that an adversary can retrieve from eavesdropping. By making the directions of both incoming and outgoing traffic at a sensor node uniformly distributed, the new defense system makes it very hard for an adversary to perform analysis on locally gathered information and infer the direction to which the receiver locates. We evaluate our defense system based on three criteria: delivery time, privacy protection strength, and energy cost. The simulation results show that LPR with fake packet injection is capable of providing strong protection for the receiveriquests location privacy. Under similar energy cost, the safe time of the receiver provided by LPR is much longer than other methods, including Phantom routing [1] and DEFP [2]. The performance of our system can be tuned through a few system parameters that determine the tradeoff between energy cost and the strength of location-privacy protection.

A firewall's complexity is known to increase with the size of its rule set. Complex firewalls are more likely to have configuration errors which cause security loopholes. Until now, two rules can be merged into one only when they are exactly same for all the dimensions except one for which each value of two rules should be adjacent to each other. In this paper, we propose a new and aggressive reduction algorithm which finds a group of rules and replace it with a smaller new group so that the total size of rule set can be reduced. This can not be achievable by any previous work because all of them eliminate rules only when these rules are redundant by other rules in the same rule set. The proposed algorithm is also orthogonal to the previous works so that it can be used to supplement them.

Unstructured peer-to-peer networks have gained a lot of popularity due to their resilience to network dynamics. The core operation in such networks is to efficiently locate resources. However, existing query schemes, e.g., flooding, random walks and interest-based shortcut, suffer various problems in reducing communication overhead, and shortening response time. In this paper, we study the problems in prior works, and propose a new query scheme by mixing inter-cluster queries, and intra-cluster queries. Specifically, the proposed scheme works by efficiently locating the clusters sharing similar interests with inter-cluster queries, and then exhaustively searching the nodes in the found clusters with intra-cluster queries. To facilitate the scheme, we propose a clustering algorithm to cluster nodes that share similar interests, and a labeling algorithm to explicitly capture the clusters's borders. As demonstrated by extensive simulations, our new query scheme can improve the system performance significantly by delivering a better tradeoff between communication overhead and response time.

Due to the open nature of a sensor network, it is relatively easy for an adversary to eavesdrop and trace packet movement in the network in order to capture the receiver physically. After studying the adversary's behavior patterns, we present countermeasures to this problem. We propose a location-privacy routing protocol (LPR) that is easy to implement and provides path diversity. Combining with fake packet injection, LPR is able to minimize the traffic direction information that an adversary can retrieve from eavesdropping. By making the directions of both incoming and outgoing traffic at a sensor node uniformly distributed, the new defense system makes it very hard for an adversary to perform analysis on locally gathered information and infer the direction to which the receiver locates. We evaluate our defense system based on three criteria: delivery time, privacy protection strength, and energy cost. The simulation results show that LPR with fake packet injection is capable of providing strong protection for the receiver's location privacy. Under similar energy cost, the safe time of the receiver provided by LPR is much longer than other methods, including Phantom routing (Kamat et al., 2005) and DEFP (Deng et al., 2005). The performance of our system can be tuned through a couple of parameters that determine the tradeoff between energy cost and the strength of location-privacy protection.

As peer-to-peer networks grow larger and include more diverse users, the lack of incentive to encourage cooperative behavior becomes one of the key problems. This challenge cannot be fully met by traditional incentive schemes, which suffer from various attacks based on false reports. Especially, due to the lack of central authorities in typical P2P systems, it is difficult to detect colluding groups. Members in the same colluding group can cooperate to manipulate their history information, and the damaging power increases dramatically with the group size. In this paper, we propose a new distributed incentive scheme, in which the benefit that a node can obtain from the system is proportional to its contribution to the system, and a colluding group cannot gain advantage by cooperation regardless of its size. Consequently, the damaging power of colluding groups is strictly limited. The proposed scheme includes three major components: a distributed authority infrastructure, a key sharing protocol, and a contract verification protocol.

The ad hoc deployment of a sensor network causes unpredictable patterns of connectivity and varied node density, resulting in uneven bandwidth provisioning on the forwarding paths. When congestion happens, some sensors may have to reduce their data rates. It is an interesting but difficult problem to determine which sensors must reduce rates and how much they should reduce. This paper attempts to answer a fundamental question about congestion resolution: What are the maximum rates at which the individual sensors can produce data without causing congestion in the network and unfairness among the peers? We define the maxmin optimal rate assignment problem in a sensor network, where all possible forwarding paths are considered. We provide an iterative linear programming solution, which finds the maxmin optimal rate assignment and a forwarding schedule that implements the assignment in a low-rate sensor network. We prove that there is one and only one such assignment for a given configuration of the sensor network. We also study the variants of the maxmin fairness problem in sensor networks.

rdquoApplication-level multicast is a promising alternative to IP multicast due to its independence from the IP routing infrastructure and its flexibility in constructing the delivery trees. The existing overlay multicast systems either support a single data source or have high maintenance overhead when multiple sources are allowed. They are inefficient for applications that require any-source multicast with varied host capacities and dynamic membership. This paper proposes ACOM, an any-source capacity-constrained overlay multicast system, consisting of three distributed multicast algorithms on top of a non-DHT overlay network with simple structures (random overlay with a non-DHT ring) that are easy to manage as nodes join and depart. The nodes have different capacities, and they can support different numbers of direct children during a multicast session. No explicit multicast trees are maintained on top of the overlay. The distributed execution of the algorithms naturally defines an implicit, roughly balanced, capacity-constrained multicast tree for each source node. We prove that the system can deliver a multicast message from any source to all nodes in expected O(logcn) hops, which is asymptotically optimal, where c is the average node capacity and n is the number of members in a multicast group.

A worm automatically replicates itself across networks and may infect millions of servers in a short period of time. It is conceivable that the cyberterrorists may use a widespread worm to cause major disruption to the Internet economy. Much recent research concentrates on propagation models and early warning, but the defense against worms is largely an open problem. We propose a distributed antiworm architecture (DAW) that automatically slows down or even halts the worm propagation within an Internet service provider (ISP) network. New defense techniques are developed based on the behavioral difference between normal hosts and worm-infected hosts. Particularly, a worm-infected host has a much higher connection-failure rate when it randomly scans the Internet. This property allows DAW to set the worms apart from the normal hosts. We propose a temporal rate-limit algorithm and a spatial rate-limit algorithm, which makes the speed of worm propagation configurable by the parameters of the defense system. The effectiveness of the new techniques is evaluated analytically and by simulations.

In this paper, we propose a two-tier overlay multicast architecture (TOMA) to provide scalable and efficient multicast support for various group communication applications. In TOMA, multicast service overlay network (MSON) is advocated as the backbone service domain, while end users in access domains form a number of small clusters, in which an application-layer multicast protocol is used for the communication between the clustered end users. TOMA is able to provide efficient resource utilization with less control overhead, especially for large-scale applications. It also alleviates the state scalability problem and simplifies multicast tree construction and maintenance when there are large numbers of groups in the network. To help MSON providers efficiently plan backbone service overlay, we suggest several provisioning algorithms to locate proxies, select overlay links, and allocate link bandwidth. Extensive simulation studies demonstrate the promising performance of TOMA

Capable of infecting hundreds of thousands of hosts, worms represent a major threat to the Internet. However, the defense against them is still an open problem. This paper attempts to answer an important question: How can we distinguish polymorphic worms from normal background traffic? We propose a new worm signature, called the position-aware distribution signature (PADS), which fills the gap between traditional signatures and anomaly-based intrusion detection systems. The new signature is a collection of position-aware byte frequency distributions. It is more flexible than the traditional signatures of fixed strings while it is more precise than the position-unaware statistical signatures. We propose two algorithms based on expectation-maximization (EM) and Gibbs sampling to efficiently compute PADS from a set of polymorphic worm samples. We also discuss how to separate a mixture of different polymorphic worms such that their respective PADS signatures can be calculated. We perform extensive experiments to demonstrate the effectiveness of PADS in separating new worm variants from normal background traffic.

Peer-to-peer (P2P) networks have gained a lot of popularity in recent years. While structured (DHT) networks provide better response time and smaller diameter, which are the advantages over unstructured networks, they are vulnerable to frequent node failure/joins/leaves. There is always a tradeoff for any P2P network to achieve all of these goals. In this paper, a distributed hybrid scheme is proposed for unstructured P2P networks, which combines Markov random walks and peer clustering to achieve a better tradeoff. The scheme has a short response time for most of the queries that belong to the same interest group, while still maintaining a smaller network diameter. More important, we propose a totally distributed clustering algorithm, which means better resilience to network dynamics. The performance of our systems is demonstrated by extensive simulations.

Data dissemination in wireless sensor networks is a key problem that acts as a bottleneck to its wide application in real world. In this paper, a novel data dissemination scheme ? logarithmic spiral data dissemination (LSDD) ? is proposed. In LSDD, data advertisements are disseminated following a parametric spiral-like path, which involves only a small fraction of nodes in a dense sensor network. By exploiting the nice feature of spiral, the scheme scales well for large sensor networks while saving much energy in the data dissemination process. By both numerical analysis and simulations, we show the distinct merits of LSDD as lower dissemination cost, better scalability, and better fault tolerance when compared to flooding-based schemes.

For data-collection applications in sensor networks, it is important to ensure all data sources have equal (or weighted) access to network bandwidth so that the base stations receive a complete picture about the monitored area. We point out the fairness problem in the current design of sensor networks, which may cause extremely biased bandwidth allocations. It is a challenge to design a fully distributed fairness solution due to the lack of global knowledge about the distribution of data sources and their routing paths. This paper proposes a new aggregate fairness model and a localized algorithm (called AFA) that implements the model. AFA is designed to work with any routing protocol. In particular, it allows the packets from a data source to follow an arbitrary set of forwarding paths to the base stations. This flexibility makes it considerably harder to allocate bandwidth fairly among different data sources. AFA solves the problem with only localized operations at the sensors. It is easy to implement, which is an attractive property for sensor networks. Moreover, the algorithm automatically adjusts a sensor's forwarding rate to avoid packet drops due to downstream congestion, which helps improve energy efficiency. We perform extensive simulations, demonstrating that the proposed algorithm can effectively improve end-to-end fairness.

Deadlock detection scheduling is an important, yet often overlooked problem that can significantly affect the overall performance of deadlock handling. Excessive initiation of deadlock detection increases overall message usage, resulting in degraded system performance in the absence of deadlocks, while insufficient initiation of deadlock detection increases the deadlock persistence time, resulting in an increased deadlock resolution cost in the presence of deadlocks. The investigation of this performance trade-off, however, is missing in the literature. This paper studies the impact of deadlock detection scheduling on the overall performance of deadlock handling. In particular, we show that there exists an optimal deadlock detection frequency that yields the minimum long-run mean average cost, which is determined by the message complexities of the deadlock detection and resolution algorithms being used, as well as the rate of deadlock formation, denoted as lambda. For the best known deadlock detection and resolution algorithms, we show that the asymptotically optimal frequency of deadlock detection scheduling that minimizes the overall message overhead is O((lambdan)1/3) when the total number n of processes is sufficiently large. Furthermore, we show that, in general, fully distributed (uncoordinated) deadlock detection scheduling cannot be performed as efficiently as centralized (coordinated) deadlock detection scheduling

A wireless sensor network is constrained by computation capability, memory space, communication bandwidth, and above all, energy supply. When a critical event triggers a surge of data generated by the sensors, congestion may occur as data packets converge toward a sink. Congestion causes energy waste, throughput reduction, and information loss. However, the important problem of congestion avoidance in sensor networks is largely open. This paper proposes a congestion-avoidance scheme based on lightweight buffer management. We describe simple yet effective approaches that prevent data packets from overflowing the buffer space of the intermediate sensors. These approaches automatically adapt the sensors' forwarding rates to nearly optimal without causing congestion. We discuss how to implement buffer-based congestion avoidance with different MAC protocols. In particular, for CSMA with implicit ACK, our 1/k-buffer solution prevents hidden terminals from causing congestion. We demonstrate how to maintain near-optimal throughput with a small buffer at each sensor and how to achieve congestion-free load balancing when there are multiple routing paths toward multiple sinks

The global deployment of IP multicast has been slow due to the difficulties related to heterogeneity, scalability, manageability, and lack of a robust interdomain multicast routing protocol. Application-level multicast becomes a promising alternative. Many overlay multicast systems have been proposed in recent years. However, they are insufficient in supporting applications that require any-source multicast with varied host capacities and dynamic membership. In this paper, we propose two capacity-aware multicast systems that focus on host heterogeneity, any source multicast, dynamic membership, and scalability. We extend Chord and Koorde to be capacity-aware. We then embed implicit degree-varying multicast trees on top of the overlay network and develop multicast routines that automatically follow the trees to disseminate multicast messages. The implicit trees are well balanced with the workload evenly spread across the network. We rigorously analyze the expected performance of multisource capacity-aware multicasting, which was not thoroughly addressed in any previous work. We also perform extensive simulations to evaluate the proposed multicast systems.

We propose and implement a set of efficient on-line algorithms for a router to sample the passing packets and identify multi-attribute high-volume traffic aggregates. Besides the obvious applications in traffic engineering and measurement, we describe its application in defending against certain classes of DoS attacks. Our contributions include three novel algorithms. The reservoir sampling algorithm employs a biased sampling strategy that favors packets from high-volume aggregates. Based on the samples, two efficient algorithms are proposed to identify single-attribute aggregates and multi-attribute aggregates, respectively. We implement the algorithms on a Linux router and demonstrate that the router can effectively filter out malicious packets unstateful DoS attacks.

The global deployment of IP multicast has been slow due to the difficulties related to heterogeneity, scalability, manageability, and lack of a robust inter-domain multicast routing protocol. Application-level multicast becomes a promising alternative. Many overlay multicast systems have been proposed in recent years. However, they are insufficient in supporting applications that require large-scale any-source multicast with highly varied host capacities and highly dynamic membership. In this paper, we propose two capacity-aware multicast systems that focus on host heterogeneity, dynamic membership, scalability, and any source multicast. We extend Chord and Koorde to be capacity-aware. We then embed implicit degree-varying multicast trees on top of the overlay network and develop multicast routines that automatically follow the trees to disseminate multicast messages. The implicit trees are well balanced with workload evenly spread across the network. We also perform extensive simulations to evaluate the proposed multicast systems

With the capability of infecting hundreds of thousands of hosts, worms represent a major threat to the Internet. The defense against Internet worms is largely an open problem. This paper investigates two important problems. Can a localized defense system detect new worms that were not seen before and moreover, capture the attack packets? How to identify polymorphic worms from the normal background traffic? We have two major contributions here. The first contribution is the design of a novel double-honeypot system, which is able to automatically detect new worms and isolate the attack traffic. The second contribution is the proposal of a new type of position-aware distribution signatures (PADS), which fit in the gap between the traditional signatures and the anomaly-based systems. We propose two algorithms based on expectation-maximization (EM) and Gibbs sampling for efficient computation of PADS from polymorphic worm samples. The new signature is capable of handling certain polymorphic worms. Our experiments show that the algorithms accurately separate new variants of the MSBlaster worm from the normal-traffic background.

Deadlock detection scheduling is an important, yet oft-overlooked problem that can significantly affect the overall performance of deadlock handling.An excessive initiation of deadlock detection increases overall message usage, resulting in degraded system performance in the absence of deadlocks; while a deficient initiation of deadlock detection increases the deadlock persistence time, resulting in an increased deadlock resolution cost in the presence of deadlocks. Such a performance tradeoff, however, is generally missing in literature. In this paper we study the impact of deadlock detection scheduling on the system performance, and show that there exists an optimal deadlock detection frequency that yields the minimum long-run mean average cost associated with the message complexity of deadlock detection and resolution algorithms, and the rate of deadlock formation, λ. Based on the up-to-date deadlock detection and resolution algorithms, we show that the asymptotically optimal frequency of deadlock detection scheduling that minimizes the message overhead is cal O((λ n)1/3), when the total number of processes n is sufficiently large. Furthermore, we show that in general fully distributed (uncoordinated) deadlock detection scheduling can not be performed as efficiently as centralized (coordinated) deadlock detection scheduling.

Managing the security of enterprise networks has emerged to be a critical problem in the era of Internet economy. Arising as a leading threat, worms repetitively caused enormous damage to the Internet community during the past years. A new security service that monitors the ongoing worm activities on the Internet will greatly contribute to the security management of modern enterprise networks. This paper proposes an Internet-worm early warning system that automatically detects concerted scan activities and derives possible signatures of worm attacks. Its goal is to issue warning at the early stage of worm propagation and to provide necessary information for security analysts to control the damage. It reduces false positives by filtering out false scan sources. The system is locally deployable or can be codeployed amongst a group of enterprise networks. We provide both analytical and simulation studies on the responsiveness of this early warning system.

Distributed denial of service (DDoS) is a major threat to the availability of Internet services. The anonymity allowed by IP networking, together with the distributed, large scale nature of the Internet, makes DDoS attacks stealthy and difficult to counter. To make the problem worse, attack traffic is often indistinguishable from normal traffic. As various attack tools become widely available and require minimum knowledge to operate, automated antiDDoS systems become increasingly important. Many current solutions are either excessively expensive or require universal deployment across many administrative domains. This paper proposes two perimeter-based defense mechanisms for Internet service providers (ISPs) to provide the antiDDoS service to their customers. These mechanisms rely completely on the edge routers to cooperatively identify the flooding sources and establish rate-limit filters to block the attack traffic. The system does not require any support from routers outside or inside of the ISP, which not only makes it locally deployable, but also avoids the stress on the ISP core routers. We also study a new problem of perimeter-based IP traceback and provide three solutions. We demonstrate analytically and by simulations that the proposed defense mechanisms react quickly in blocking attack traffic while achieving high survival ratio for legitimate traffic. Even when 40 percent of all customer networks attack, the survival ratio for traffic from the other customer networks is still close to 100 percent.

We propose an Internet-worm early warning system, which integrates a set of novel techniques that automatically detect the concerted scan activity of an on-going worm attack. It is able to issue warning at the early stage of worm propagation and to provide necessary information for security analysts to control the damage. The system monitors a "used" address space. Unlike the traditional approach that keeps track of SYN packets, it relies on RESET packets to find the scan sources, which has greater accuracy and less overhead. The system is resilient to anti-monitor measures. Particularly, a sophisticated protocol is designed to distinguish faked scan sources from real scan sources. We provide an analytical study on the properties and effectiveness of this early warning system, and back up our claims by numerical results.

Computing constrained shortest paths is fundamental to some important network functions such as QoS routing, which is to find the cheapest path that satisfies certain constraints. In particular, finding the cheapest delay-constrained path is critical for real-time data flows such as voice calls. Because it is NP-complete, there has been much research into designing heuristic algorithms that solve the /spl epsiv/-approximation of the problem with an adjustable accuracy. A common approach is to discretize (i.e., scale and round) the link delay or link cost, which transforms the original problem to a simpler one solvable in polynomial time. The efficiency of the algorithms directly relates to the magnitude of the errors introduced during discretization. We propose two techniques that reduce the discretization errors, allowing faster algorithms to be designed. Reducing the overhead of the costly computation for constrained shortest paths is practically important for the design of a high-throughput QoS router, which is limited by both processing power and memory space. Our simulations show that the new algorithms reduce the execution time by an order of magnitude on power-law topologies with 1000 nodes. The reduction in memory space is similar. When there are multiple constraints, the improvement is more dramatic.

Many Internet multicast applications such as teleconferencing and remote diagnosis have quality-of-service (QoS) requirements. It is a challenging task to build QoS constrained multicast trees with high performance, high success ratio, low overhead, and low system requirements. This paper presents a new scalable QoS multicast routing protocol (SoMR) that has very small communication overhead and requires no state outside the multicast tree. SoMR achieves the favorable tradeoff between routing performance and overhead by carefully selecting the network sub-graph in which it conducts the search for a path that can support the QoS requirement, and by auto-tuning the selection according to the current network conditions. Its early-warning mechanism helps to detect and route around the real bottlenecks in the network, which increases the chance of finding feasible paths for additive QoS requirements. SoMR minimizes the system requirements; it relies only on the local state stored at each router. The routing operations are completely decentralized.

Many important network functions (e.g., QoS provision, admission control, traffic engineering, resource management) rely on the availability and the accuracy of the network state information. However, it is impractical to maintain the complete state information of a large internetwork at a single location. Instead, a large network is often hierarchically structured, with each domain advertising its aggregated state. To achieve scalability, the amount of information after aggregation should he minimized. To improve accuracy, the aggregation method must be carefully selected. This paper gives a unified account of state aggregation based on the concept of service curves. The aggregation of network state is modeled as a recursive process of service curve transformation. New approximation methods based on polynomial curves, cubic splines and polylines are proposed, and their scalability/accuracy tradeoffs are studied. Our simulations show that these new methods approximate the network state far more accurate than the existing methods. In particular, the polylines achieve the best scalability/accuracy tradeoff.

An Internet worm automatically replicates itself to vulnerable systems and may infect hundreds of thousands of servers across the Internet. It is conceivable that the cyber-terrorists may use a wide-spread worm to cause major disruption to our Internet economy. While much recent research concentrates on propagation models, the defense against worms is largely an open problem. We propose a distributed antiworm architecture (DAW) that automatically slows down or even halts the worm propagation. New defense techniques are developed based on behavioral difference between normal hosts and worm-infected hosts. Particularly, a worm-infected host has a much higher connection-failure rate when it scans the Internet with randomly selected addresses. This property allows DAW to set the worms apart from the normal hosts. We propose a temporal rate-limit algorithm and a spatial rate-limit algorithm, which makes the speed of worm propagation configurable by the parameters of the defense system. DAW is designed for an Internet service provider to provide the anti-worm service to its customers. The effectiveness of the new techniques is evaluated analytically and by simulations.

To achieve security in wireless sensor networks, it is important to he able to encrypt messages sent among sensor nodes. Keys for encryption purposes must he agreed upon by communicating nodes. Due to resource constraints, achieving such key agreement in wireless sensor networks is nontrivial. Many key agreement schemes used in general networks, such as Diffie-Hellman and public-key based schemes, are not suitable for wireless sensor networks. Pre-distribution of secret keys for all pairs of nodes is not viable due to the large amount of memory used when the network size is large. Recently, a random key pre-distribution scheme and its improvements have been proposed. A common assumption made by these random key pre-distribution schemes is that no deployment knowledge is available. Noticing that in many practical scenarios, certain deployment knowledge may be available a priori, we propose a novel random key pre-distribution scheme that exploits deployment knowledge and avoids unnecessary key assignments. We show that the performance (including connectivity, memory usage, and network resilience against node capture) of sensor networks can he substantially improved with the use of our proposed scheme. The scheme and its detailed performance evaluation are presented in this paper.

Multivariate statistical analysis is an important data analysis technique that has found applications in various areas.In this paper, we study some multivariate statistical analysis methods in Secure 2-party Computation (S2C) framework illustrated by the following scenario: two parties, each having a secret data set, want to conduct the statistical analysis on their joint data, but neither party is willing to disclose its private data to the other party or any third party.The current statistical analysis techniques cannot be used directly to support this kind of computation because they require all parties to send the necessary data to a central place.In this paper, We define two Secure 2-party multivariate statistical analysis problems: Secure 2-party Multivariate Linear Regression problem and Secure 2-party Multivariate Classification problem.We have developed a practical security model, based on which we have developed a number of building blocks for solving these two problems.

Routing is a process of finding a network path from a source node to a destination node. The execution time and the memory requirement of a routing algorithm increase with the size of the network. In order to deal with the scalability problem, large networks are often structured hierarchically by grouping nodes into different domains. The internal topology of each domain is then aggregated into a simple topology that reflects the cost of routing across that domain. This process is called topology aggregation. For delay-bandwidth sensitive networks, traditional approaches represent the property of each link in the aggregated topology as a delay-bandwidth pair, which corresponds to a point on the delay-bandwidth plane. Since each link after aggregation may be the abstraction of many physical paths, a single delay-bandwidth pair results in significant information loss. The major contribution of this paper is a novel quality-of-service (QoS) parameter representation with a new aggregation algorithm and a QoS-aware routing protocol. Our QoS representation captures the state information about the network with much greater accuracy than the existing algorithms. Our simulation results show that the new approach achieves very good performance in terms of delay deviation, success ratio, and crankback ratio.

The future Internet is expected to support multicast applications with quality of service (QoS) requirements. To facilitate this, QoS multicast routing protocols are pivotal in enabling new receivers to join a multicast group. However, current routing protocols are either too restrictive in their search for a feasible path between a new receiver and the multicast tree, or burden the network with excessive overhead. We propose QMRP, a new Qos-aware multicast routing protocol. QMRP achieves scalability by significantly reducing the communication overhead in constructing a multicast tree, yet it retains a high chance of success. This is achieved by switching between single-path routing and multiple-path routing according to the current network conditions. The high-level design of QMRP makes it operable on top of any unicast routing algorithm both intra-domain and inter-domain. Its responsiveness is improved by using a termination mechanism which detects the failure as well as the success of routing without the use of timeout. In addition, QMRP always constructs loop-free multicast trees.

Large networks are often structured hierarchically by grouping nodes into different domains in order to deal with the scaling problem. In such networks, it is infeasible to maintain the detailed network information at every router. Therefore, the topology information of the domains are summarized before being broadcast. This process is called topology aggregation. Hierarchical routing protocols are then used to find a route among the domains. We study several basic problems associated with hierarchical QoS routing, including (1) how to make QoS-aware topology aggregation, (2) how to represent the aggregated network state, and (3) how to find an end-to-end route based on aggregated information. The novelty in this research is our new network QoS representation which is line segments on the delay-bandwidth plane. We also present a distributed routing mechanism that works with our representation. Our theoretical and simulation results show that the protocol achieves scalability and improved routing performance.

The future Internet is expected to support multicast applications with quality of service (QoS) requirements. To facilitate this, QoS multicast routing protocols are pivotal in enabling new receivers to join a multicast group. However, current routing protocols are either too restrictive in their search for a feasible path between a new receiver and the multicast tree, or burden the network with excessive overhead. We propose QMRP, a new QoS-aware multicast routing protocol. QMRP achieves scalability by significantly reducing the communication overhead of constructing a multicast tree, yet it retains a high chance of success. This is achieved by switching between single-path routing and multiple-path routing according to the current network conditions. The high level design of QMRP makes it operable on top of any unicast routing algorithm in both intradomain and interdomain. Its responsiveness is improved by using a termination mechanism which detects the failure as well as the success of routing without the use of timeout. In addition, QMRP always constructs loop-free multicast trees.

Distributed multimedia applications have quality-of-service (QoS) requirements specified in terms of constraints on various metrics such as bandwidth and delay. The task of QoS routing is to find a path from the source node to the destination node with sufficient resources to support the required end-to-end QoS. We propose several distributed algorithms for the bandwidth-constrained routing and the delay constrained routing. The algorithms are presented in the form of distributed recursive computation (DRC). DRC computes the global routing state in a distributed, recursive fashion and often leaves useful information at intermediate nodes during the process. An information-reuse scheme is studied to utilize such information in order to reduce the overall overhead. Our simulation shows that the overhead of the proposed algorithms is modest and stable.

In an ad hoc network, all communication is done over wireless media, typically by radio through the air, without the help of wired base stations. Since direct communication is allowed only between adjacent nodes, distant nodes communicate over multiple hops. The quality-of-service (QoS) routing in an ad hoc network is difficult because the network topology may change constantly, and the available state information for routing is inherently imprecise. In this paper, we propose a distributed QoS routing scheme that selects a network path with sufficient resources to satisfy a certain delay (or bandwidth) requirement in a dynamic multihop mobile environment. The proposed algorithms work with imprecise state information. Multiple paths are searched in parallel to find the most qualified one. Fault-tolerance techniques are brought in for the maintenance of the routing paths when the nodes move, join, or leave the network. Our algorithms consider not only the QoS requirement, but also the cost optimality of the routing path to improve the overall network performance. Extensive simulations show that high call admission ratio and low-cost paths are achieved with modest routing overhead. The algorithms can tolerate a high degree of information imprecision.

New emerging distributed multimedia applications provide guaranteed end-to-end quality of service (QoS) and have stringent constraints on delay, delay-jitter, cost, etc. The task of QoS routing is to find a route in the network which has sufficient resources to satisfy the constraints. The delay-cost-constrained routing problem is NP-complete. We propose a heuristic algorithm for this problem. The idea is to first reduce the NP-complete problem to a simpler one which can be solved in polynomial time, and then solve the new problem by either an extended Dijkstra's algorithm or an extended Bellman-Ford algorithm. We prove the correctness of our algorithm by showing that a solution for the simpler problem must also be a solution for the original problem. The performance of the algorithm is studied by both theoretical analysis and simulation.

The goal of quality-of-service (QoS) routing is to find a network path which has sufficient resources to satisfy certain constraints on delay, bandwidth and/or other metrics. The network state information maintained at every node is often imprecise in a dynamic environment because of nonnegligible propagation delay of state messages, periodic updates due to overhead concern, and hierarchical state aggregation. The information imprecision makes QoS routing difficult. The traditional shortest-path routing algorithm does not provide satisfactory performance with imprecise state information. We propose a distributed routing scheme, called ticket-based probing, which searches multiple paths in parallel for a satisfactory one. The scheme is designed to work with imprecise state information. It allows the dynamic trade-off between the routing performance and the overhead. The state information of intermediate nodes is collectively used to guide the routing messages along the most appropriate paths in order to maximize the success probability. The proposed algorithm consider not only the QoS requirements but also the cost optimality of the routing path. Extensive simulations show that our algorithm achieve high call-admission ratio and low-cost routing paths with modest overhead. The algorithm can tolerate high degree of information imprecision.

We propose an integrated QoS routing framework based on selective probing for high-speed packet-switching networks. The framework is fully distributed and depends only on the local state maintained at every individual node. By using controlled diffusion computations, the framework captures the common messaging and computational structure of distributed QoS routing, and allows an efficient implementation due to its simplicity. Different distributed routing algorithms (DRAs) can be quickly developed by specifying only a few well-defined constraint-dependent parameters within the framework. Our simulation shows that the overhead of the proposed algorithms is stable and modest.

We present a new algorithm for detecting generalized deadlocks in distributed systems. Our algorithm incrementally constructs and reduces a wait-for graph (WFG) at an initiator process. This WFG is then searched for deadlock. The proposed algorithm has two primary advantages: First, it avoids sending messages along the edges of the global wait-for graph (WFG), thereby achieving a worst-case message complexity of 2n, where n is the number of processes in the WFG. Since information must be obtained from every process reachable from the initiator, this is optimal to within a constant factor. All the existing algorithms for the same problem construct a distributed snapshot of the WFG. As this involves sending messages along the edges of the WFG, the best available message complexity among these algorithms is 4e-2n+2l, which is O(n/sup 2/) in the worst case, where e and l are the number of edges and leaves in the WFG, respectively. Second, since the information about a detected deadlock is readily available at the initiator process, rather than distributed among different processes, it significantly simplifies the task of deadlock resolution, and helps to reduce system overhead associated with the resolution. The time complexity of our algorithm is also better than or equal to the existing algorithms.