Distributed Hash Tables (DHTs) are pivotal in numerous high-impact key-value applications built on distributed networked systems, offering a decentralized architecture that avoids single points of failure and improves data availability. Despite their widespread utility, DHTs face substantial challenges in handling range queries, which are crucial for applications such as LLM serving, distributed storage, databases, content delivery networks, and blockchains. To address this limitation, we present LEAD, a novel system incorporating learned models within DHT structures to significantly optimize range query performance. LEAD utilizes recursive machine learning models as the Learned Hash Function to map and retrieve data across a distributed system while preserving the inherent order of data. LEAD includes the designs to minimize range query latency and message cost while maintaining high scalability and resilience to network churn. Our comprehensive evaluations, conducted in both testbed implementation and simulations, demonstrate that LEAD achieves tremendous advantages in system efficiency compared to existing range query methods in large-scale distributed systems, reducing query latency and message cost by 80% to 90%+. Furthermore, LEAD exhibits scalability and robustness against system churn, providing a robust, scalable structure for efficient data retrieval in distributed key-value systems.

Blockchain interoperability and throughput scalability are two crucial problems that limit the wide adoption of blockchain applications. Payment channel networks (PCNs) provide a promising solution to the inherent scalability problem of blockchain technologies, allowing off-chain payments between senders and receivers via multi-hop payment paths. This paper presents a cross-chain PCN, called XHub, that extends PCNs to support multi-hop paths across multiple blockchains and resolves both interoperability and throughput scalability. XHub achieves service availability, transaction atomicity, and auditability. Users who correctly follow the protocols will succeed in making payments or get profits from doing the services. In addition, trustworthy information about hubs will be managed in a decentralized manner and available to all users. We conduct prototype implementation of machines that exchange Internet messages and run with two real blockchains as well as large-scale simulations based on real-world PCN topologies and transactions. The results show that XHub has small latency for cross-chain payments and can achieve a significantly higher success rate compared to the version without hub management protocols. This work is an important step towards the big picture of a decentralized transaction system that connects a wide scope of users in different blockchains.

We present a quantum-inspired algorithm that utilizes Quantum Hamiltonian Descent (QHD) for efficient community detection. Our approach reformulates the community detection task as a Quadratic Unconstrained Binary Optimization (QUBO) problem, and QHD is deployed to identify optimal community structures. We implement a multi-level algorithm that iteratively refines community assignments by alternating between QUBO problem setup and QHD-based optimization. Benchmarking shows our method achieves up to 5.49% better modularity scores while requiring less computational time compared to classical optimization approaches. This work demonstrates the potential of hybrid quantum-inspired solutions for advancing community detection in largescale graph data.

Efficient vector query processing is essential for powering large-scale AI applications, such as LLMs. However, existing solutions struggle with growing vector datasets that exceed the memory capacity of a single machine, leading to excessive data movement and resource underutilization in monolithic architectures.

Distributed quantum computing (DQC) that allows a large quantum circuit to be executed simultaneously on multiple quantum processing units (QPUs) becomes a promising approach to increase the scalability of quantum computing. It is natural to envision the near-future DQC platform as a multi-tenant cluster of QPUs, called a Quantum Cloud. However, no existing DQC work has addressed the two key problems of running DQC in a multi-tenant quantum cloud: placing multiple quantum circuits to QPUs and scheduling network resources to complete these jobs. This work is the first attempt to design a circuit placement and resource scheduling framework for a multi-tenant environment. The proposed framework is called CloudQC, which includes two main functional components, circuit placement and network scheduler, with the objectives of optimizing both quantum network cost and quantum computing time. Experimental results with real quantum circuit workloads show that CloudQC significantly reduces the average job completion time compared to existing DQC placement algorithms for both single-circuit and multi-circuit DQC. We envision this work will motivate more future work on network-aware quantum cloud.

Instruction tuning is critical for adapting large language models (LLMs) to downstream tasks, and recent studies have demonstrated that small amounts of human-curated data can outperform larger datasets, challenging traditional data scaling laws. While LLM-based data quality rating systems offer a cost-effective alternative to human annotation, they often suffer from inaccuracies and biases, even in powerful models like GPT-4. In this work, we introduce $DS^2$, a **D**iversity-aware **S**core curation method for **D**ata **S**election. By systematically modeling error patterns through a score transition matrix, $DS^2$ corrects LLM-based scores and promotes diversity in the selected data samples. Our approach shows that a curated subset (just 3.3\% of the original dataset) outperforms full-scale datasets (300k samples) across various machine-alignment benchmarks, and matches or surpasses human-aligned datasets such as LIMA with the same sample size (1k samples). These findings challenge conventional data scaling assumptions, highlighting that redundant, low-quality samples can degrade performance and reaffirming that ``more can be less''.

Recent studies show that in supervised fine-tuning (SFT) of large language models (LLMs), data quality matters more than quantity. While most data cleaning methods concentrate on filtering entire samples, the quality of individual tokens within a sample can vary significantly. After pre-training, even in high-quality samples, patterns or phrases that are not task-related can be redundant, uninformative, or even harmful. Continuing to fine-tune on these patterns may offer limited benefit and even degrade downstream task performance. In this paper, we investigate token quality from a noisy-label perspective and propose a generic token cleaning pipeline for SFT tasks. Our method filters out uninformative tokens while preserving those carrying key task-specific information. Specifically, we first evaluate token quality by examining the influence of model updates on each token, then apply a threshold-based separation. The token influence can be measured in a single pass with a fixed reference model or iteratively with self-evolving reference models. The benefits and limitations of both methods are analyzed theoretically by error upper bounds. Extensive experiments show that our framework consistently improves downstream performance. Code is available at https://github.com/UCSC-REAL/TokenCleaning.

Nearest-neighbor search over embeddings has become a core primitive for AI and LLM-centric workloads. However, prevailing vector databases remain centralized or cluster-bound, introducing single control points, privacy vulnerabilities, and cost/latency bottlenecks. We present Vortex, a decentralized vector overlay that delivers planet-scale approximate nearest neighbor (ANN) search without a centralized control plane. Vortex integrates three key components: (1) Distributed Learned Hashing (DLH), which collaboratively learns piecewise similarity-preserving hash functions to map semantically related vectors to nearby key ranges while balancing load; (2) a Distributed Hash Table (DHT) for scalable, fault-tolerant routing and churn resilience; and (3) a co-designed Distributed HNSW (DHNSW) index for high-recall, low-latency search on each peer. Preliminary results show that Vortex matches the accuracy and latency of leading centralized systems while reducing per-peer index memory requirements by two orders of magnitude and eliminating any central coordinator—enabling fully decentralized, self-organizing ANN overlay for next-generation AI systems.

Distributed Hash Tables (DHTs) are pivotal in numerous high-impact key-value applications built on distributed networked systems, offering a decentralized architecture that avoids single points of failure and improves data availability. Despite their widespread utility, DHTs face substantial challenges in handling range queries, which are crucial for applications such as LLM serving, distributed storage, databases, content delivery networks, and blockchains. To address this limitation, we present LEAD, a novel system incorporating learned models within DHT structures to significantly optimize range query performance. LEAD utilizes a recursive machine learning model to map and retrieve data across a distributed system while preserving the inherent order of data. LEAD includes the designs to minimize range query latency and message cost while maintaining high scalability and resilience to network churn. Our comprehensive evaluations, conducted in both testbed implementation and simulations, demonstrate that LEAD achieves tremendous advantages in system efficiency compared to existing range query methods in large-scale distributed systems, reducing query latency and message cost by 80% to 90%+. Furthermore, LEAD exhibits remarkable scalability and robustness against system churn, providing a robust, scalable solution for efficient data retrieval in distributed key-value systems.

While originally designed for the cloud, the benefits of the serverless paradigm are also vital in Edge/Fog computing environments. This paper presents Capybara, a new scalable, programmable distributed object store for storing and sharing serverless function data objects (state) on edge infrastructures. The key innovations here are (1) achieving scalability and avoiding the significant DRAM cost of indexing metadata servers through a "game-theoretic" DHT-based P2P architecture; (2) providing edge users with a "programmable" handler abstraction to customize data management policies, such as different function image caching policies, warm container "keep-alive" durations, data access control methods, and data replication policies.

Federated learning (FL) is an efficient distributed learning method that facilitates collaborative model training among multiple edge devices (or clients). However, current research always assumes that clients have access to ground-truth data for training, which is unrealistic in practice because of a lack of expertise. Semi-supervised federated learning (SSFL) has been proposed in many existing works to address this problem, which always adopts a fixed model architecture for training, bringing two main problems with varying amounts of pseudo-labeled data. First, the shallow model cannot have the capability to fit the increasing pseudo-labeled data, leading to poor training performance. Second, the large model suffers from an overfitting problem when exploiting a few labeled data samples in SSFL, and also requires tremendous resource (e.g., computation and communication) costs. To tackle these problems, we propose a novel framework, calledstar, which adopts progressive training to enhance model training in SSFL. Specifically,stargradually increases the model depth through adding the sub-module (e.g., one or several layers) from a shallow model, and performs pseudo-labeling for unlabeled data with a specialized confidence threshold simultaneously. Then, we propose an efficient algorithm to determine the appropriate model depth for each client with varied resource budgets and the proper confidence threshold for pseudo-labeling in SSFL. The experimental results demonstrate the high effectiveness of STAR. For instance,starcan reduce the bandwidth consumption by about 40%, and achieve an average accuracy improvement of around 9.8% compared with the baselines, on CIFAR10.

Federated fine-tuning (FedFT) has been proposed to fine-tune the pre-trained language models in a distributed manner. However, there are two critical challenges for efficient FedFT in practical applications,i.e., resource constraints and system heterogeneity. Existing works rely on parameter-efficient fine-tuning methods,e.g., low-rank adaptation (LoRA), but with major limitations. Herein, based on the inherent characteristics of FedFT, we observe that LoRA layers with higher ranks added close to the output help to save resource consumption while achieving comparable fine-tuning performance. Then we propose a novel LoRA-based FedFT framework, termed LEGEND, which faces the difficulty of determining the number of LoRA layers (called, LoRA depth) and the rank of each LoRA layer (called, rank distribution). We analyze the coupled relationship between LoRA depth and rank distribution, and design an efficient LoRA configuration algorithm for heterogeneous devices, thereby promoting fine-tuning efficiency. Extensive experiments are conducted on a physical platform with 80 commercial devices. The results show that LEGEND can achieve a speedup of 1.5-2.8× and save communication costs by about 42.3% when achieving the target accuracy, compared to the advanced solutions.

To provide a flexible tradeoff between inference accuracy and resource requirement at runtime, the slimmable neural network (SNN), a single network executable at different widths with the same deploying and management cost as that of a single model, has been proposed. However, how to effectively train SNN among massive devices in edge computing without revealing their local data remains an open problem. To this end, we leverage a novel distributed machine learning paradigm, i.e., federated learning, to realize effective on-device SNN training. As current FL schemes often train only one model with fixed architecture, and the existing SNN training algorithm is resource-intensive, integrating FL and SNN is non-trivial. Furthermore, two intrinsic features in edge computing, i.e., data and system heterogeneity, exacerbate the difficulty. Motivated by this, we redesign the model distribution, local training, and model aggregation phases in traditional FL, and propose FedSNN, a framework that ensures all widths in SNN can obtain high accuracy with less resource consumption. Specifically, for devices with heterogeneous training capacities and data distributions, the parameter server will distribute each of them with one proper width for adaptive local training guided by their uploaded model features, and their trained models will be weighted-averaged using the proposed multi-width SNN aggregation to improve their statistical utility. Extensive experiments on a distributed testbed show that FedSNN improves the model accuracy by about 2.18%-8.1%, and accelerates training by about$1.31\times $-$6.84\times $, compared with existing solutions.

Key-value lookup functions have been widely applied to network applications, including FIBs, load balancers, and content distributions. Two key performance requirements of a lookup algorithm are high throughput and small memory cost. One limitation of existing fast network lookup algorithms is that they require multiple independent and uniform hash functions, which cost high computation time and might not be available on existing hardware network devices. Recently developed learned model hashing (LMH) proposes to use a linear machine learning model to replace hash functions to avoid hash computation, but they are not optimized for memory cost. We propose a novel network lookup method called Parrot hashing, which uses a learned model to distribute keys into different buckets and applies a simple perfect hashing method to resolve the collisions of the keys in a bucket. Parrot can be implemented with only one CRC-8, which is available on all network devices. We implement Parrot in three prototypes: a software program on end hosts, a software switch, and a FIB running on a hardware programmable switch. The experimental results show that Parrot achieves the highest lookup throughput on all three prototypes, compared to existing methods. Its memory cost is also significantly lower than that of LMH.

LSM tree based stores are a popular database design in modern persistent storage systems due to their efficient writes with sorted keys. However, this hierarchical log structure suffers from extensive read amplification because multiple disk accesses are required when it searches for a key. Recent optimizations of LSM trees propose caching hot keys to reduce I/Os mainly based on their access frequencies. However, our empirical studies show that keys are different in I/O costs, which should also be considered in the caching policy: caching key-value pairs with high I/O cost can effectively improve query latency. In addition, false positives incurred by the Bloom filters in LSM trees introduce a large overhead to access SSTables because the queried keys do not exist. In this work, we design and implement SpotKV, which resolves the above two problems in an LSM tree store by proposing two memory-efficient data structures, weighted Count- Min sketch for access and I/O-aware cache admission and dynamic-seed Cuckoo filters for eliminating false positives, to improve data lookup throughput. We implement SpotKV on Google's LevelDB vl.20. From extensive experimental evaluations, SpotKV achieves 1.2-3.0x read throughput while using the same or smaller memory, compared with several state- of-the-art LSM tree stores under the read-heavy workloads of the YCSB benchmarks.

Serverless computing promises scalability and cost-efficiency by decomposing monolithic tasks into small, stateless, self-contained functions. As functions only reserve hardware resources during their lifetime, and serverless providers such as Amazon Lambda define strict data size limits [50], data required for the whole lifetime of a monolithic task needs to be kept in an external ephemeral data store. This approach increases costs and introduces performance variability, causing serverless applications to violate service level objectives (SLOs). Traditional cloud storage solutions, such as AWS S3 and Redis, fail to provide low-cost and the enforcement of SLOs, while prior works on disaggregated data stores do not scale sufficiently due to: (1) increased scheduling costs when supporting many SLOs; (2) performance degradation in the presence of burst allowances and worsened interference with lenient ones; and (3) failed service differentiation with increased number of SLO. These challenges make SLO enforcement in serverless environments difficult, leading to unpredictable performance and costs that undermine the benefits of serverless computing.

Distributed Hash Tables (DHTs) are pivotal in numerous high-impact key-value applications built on distributed networked systems, offering a decentralized architecture that avoids single points of failure and improves data availability. Despite their widespread utility, DHTs face substantial challenges in handling range queries, which are crucial for applications such as storage systems, decentralized databases, content distribution networks, and blockchains. To address this limitation, we present LEAD, a novel system incorporating learned models within DHT structures to significantly optimize range query performance. LEAD utilizes a recursive machine learning model to map and retrieve data across a distributed system while preserving the inherent order of data. Preliminary results indicate LEAD achieves tremendous advantages in system efficiency compared to existing range query methods in large-scale distributed systems while maintaining high scalability and resilience to network churn.

Key-value lookup functions have been widely applied to network applications, including FIBs, load balancers, and content distributions. Two key performance requirements of a lookup algorithm are high throughput and small memory cost. One limitation of existing fast network lookup algorithms is that they require multiple independent and uniform hash functions, which cost high computation time and might not be available on existing hardware network devices. Recently developed learned model hashing (LMH) proposes to use a linear machine learning model to replace hash functions to avoid hash computation, but they are not optimized for memory cost. We propose a novel network lookup method called Parrot hashing, which uses a learned model to distribute keys into different buckets and applies a simple perfect hashing method to resolve the collisions of the keys in a bucket. Parrot can be implemented with only one CRC8, which is available on all network devices. We implement Parrot in three prototypes: a software program on end hosts, a software switch, and a FIB running on a hardware programmable switch. The experimental results show that Parrot achieves the highest lookup throughput on all three prototypes, compared to existing methods. Its memory cost is also significantly lower than that of LMH.

Decentralized federated learning (DFL) uses peer-topeer communication to avoid the single point of failure problem in federated learning and has been considered an attractive solution for machine learning tasks on distributed devices. We provide the first solution to a fundamental network problem of DFL: what overlay network should DFL use to achieve fast training of highly accurate models, low communication, and decentralized construction and maintenance? Overlay topologies of DFL have been investigated, but no existing DFL topology includes decentralized protocols for network construction and topology maintenance. Without these protocols, DFL cannot run in practice. This work presents an overlay network, called FedLay, which provides fast training and low communication cost for practical DFL. FedLay is the first solution for constructing near-random regular topologies in a decentralized manner and maintaining the topologies under node joins and failures. Experiments based on prototype implementation and simulations show that FedLay achieves the fastest model convergence and highest accuracy on real datasets compared to existing DFL solutions while incurring small communication costs and being resilient to node joins and failures.

The pursuit of fairness in machine learning (ML), ensuring that the models do not exhibit biases toward protected demographic groups, typically results in a compromise scenario. This compromise can be explained by a Pareto frontier where given certain resources (e.g., data), reducing the fairness violations often comes at the cost of lowering the model accuracy. In this work, we aim to train models that mitigate group fairness disparity without causing harm to model accuracy. Intuitively, acquiring more data is a natural and promising approach to achieve this goal by reaching a better Pareto frontier of the fairness-accuracy tradeoff. The current data acquisition methods, such as fair active learning approaches, typically require annotating sensitive attributes. However, these sensitive attribute annotations should be protected due to privacy and safety concerns. In this paper, we propose a tractable active data sampling algorithm that does not rely on training group annotations, instead only requiring group annotations on a small validation set. Specifically, the algorithm first scores each new example by its influence on fairness and accuracy evaluated on the validation dataset, and then selects a certain number of examples for training. We theoretically analyze how acquiring more data can improve fairness without causing harm, and validate the possibility of our sampling approach in the context of risk disparity. We also provide the upper bound of generalization error and risk disparity as well as the corresponding connections. Extensive experiments on real-world data demonstrate the effectiveness of our proposed algorithm. Our code is available at [github.com/UCSC-REAL/FairnessWithoutHarm](https://github.com/UCSC-REAL/FairnessWithoutHarm).

Disaggregated memory systems achieve resource utilization efficiency and system scalability by distributing computation and memory resources into distinct pools of nodes. RDMA is an attractive solution to support high-throughput communication between different disaggregated resource pools. However, existing RDMA solutions face a dilemma: one-sided RDMA completely bypasses computation at memory nodes, but its communication takes multiple round trips; two-sided RDMA achieves one-round-trip communication but requires non-trivial computation for index lookups at memory nodes, which violates the principle of disaggregated memory. This work presents Outback, a novel indexing solution for key-value stores with a one-round-trip RDMA-based network that does not incur computation-heavy tasks at memory nodes. Outback is the first to utilize dynamic minimal perfect hashing and separates its index into two components: one memory-efficient and compute-heavy component at compute nodes and the other memory-heavy and compute-efficient component at memory nodes. We implement a prototype of Outback and evaluate its performance in a public cloud. The experimental results show that Outback achieves higher throughput than both the state-of-the-art one-sided RDMA and two-sided RDMA-based in-memory KVS by 1.06--5.03×, due to the unique strength of applying a separated perfect hashing index.

Federated learning (FL) has emerged as a promising distributed learning paradigm that enables a large number of mobile devices to cooperatively train a model without sharing their raw data. The iterative training process of FL incurs considerable computation and communication overhead. The workers participating in FL are usually heterogeneous and the workers with poor capabilities may become the bottleneck of model training. To address the challenges of resource overhead and system heterogeneity, this article proposes an efficient FL framework, called FedMP, that improves both computation and communication efficiency over heterogeneous workers through adaptive model pruning. We theoretically analyze the impact of pruning ratio on training performance, and employ a Multi-Armed Bandit based online learning algorithm to adaptively determine different pruning ratios for heterogeneous workers, even without any prior knowledge of their capabilities. As a result, each worker in FedMP can train and transmit the sub-model that fits its own capabilities, accelerating the training process without hurting model accuracy. To prevent the diverse structures of pruned models from affecting the training convergence, we further present a new parameter synchronization scheme, called Residual Recovery Synchronous Parallel (R2SP). Besides, our proposed framework can be extended to the peer-to-peer (P2P) setting. Extensive experiments on physical devices demonstrate that FedMP is effective for different heterogeneous scenarios and data distributions, and can provide up to 4.1× speedup compared to the existing FL methods.

Data generated at the network edge can be processed locally by leveraging the paradigm of edge computing (EC). Aided by EC, decentralized federated learning (DFL), which overcomes the single-point-of-failure problem in the parameter server based federated learning, is becoming a practical and popular approach for machine learning over distributed data. However, DFL faces two critical challenges,i.e., system heterogeneity and statistical heterogeneity introduced by edge devices. To ensure fast convergence with the existence of slow edge devices, we present an efficient DFL method, termed FedHP, which integrates adaptive control of both local updating frequency and network topology to better support the heterogeneous participants. We establish a theoretical relationship between local updating frequency and network topology regarding model training performance and obtain a convergence upper bound. Upon the convergence bound, we propose an optimization algorithm that adaptively determines local updating frequencies and constructs the network topology, so as to speed up convergence and improve the model accuracy. We evaluate the performance of FedHP through extensive simulation and testbed experiments. Evaluation results show that the proposed FedHP can reduce the completion time by about 51% and improve model accuracy by at least 5% in heterogeneous scenarios, compared with the baselines.

Federated learning (FL) has recently gained tremendous attention in edge computing and Internet of Things, due to its capability of enabling distributed clients to cooperatively train models while keeping raw data locally. However, the existing works usually suffer from limited communication resources, dynamic network conditions and heterogeneous client properties, which hinder efficient FL. To simultaneously tackle the above challenges, we propose a heterogeneity-aware FL framework, called FedCG, with adaptive client selection and gradient compression. Specifically, FedCG introduces diversity to client selection and aims to select a representative client subset considering statistical heterogeneity. These selected clients are assigned different compression ratios based on heterogeneous and time-varying capabilities. After local training, they upload sparse model updates matching their capabilities for global aggregation, which can effectively reduce the communication cost and mitigate the straggler effect. More importantly, instead of naively combining client selection and gradient compression, we highlight that their decisions are tightly coupled and indicate the necessity of joint optimization. We theoretically analyze the impact of both client selection and gradient compression on convergence performance. Guided by the convergence rate, we develop an iteration-based algorithm to jointly optimize client selection and compression ratio decision using submodular maximization and linear programming. On this basis, we propose the quantized extension of FedCG, termed Q-FedCG, which further adjusts quantization levels based on gradient innovation. Extensive experiments on both real-world prototypes and simulations show that FedCG and its extension can provide up to 6.4× speedup.

Federated semi-supervised learning (FSSL) has been proposed to address the insufficient labeled data problem by training models with pseudo-labeling. In previous FSSL systems, a single global model is always trained without an equivalent generalization ability for the clients under the non-IID setting. Accordingly, model personalization methods have been proposed to overcome this problem. Intuitively, seeking labeling assistance from other clients with similar data distribution,i.e., model migration, can effectively improve the personalization on the clients with scarce labeled data. However, previous works require to migrate a pre-fixed number of models among the clients, causing unnecessary resource waste and accuracy degradation due to resource heterogeneity. Considering that the number of model migrations and the quality of pseudo-labels have a significant impact on the training performance (e.g., efficiency and accuracy), we propose a novel personalized FSSL system, called Ferrari, to boost the efficiency of pseudo-labeling and training accuracy through adaptive model migrations among the clients. Specifically, Ferrari first generates the similarity-based ranking using a Gaussian KD-Tree, considering the varied data distributions among the clients. Combined with the ranking and clients' heterogeneous resource constraints, Ferrari then adaptively determines the proper model migration policy and confidence thresholds for high-quality pseudo-labeling and personalized training for clients. Extensive experiments on a physical platform show that Ferrari provides a 1.2$\sim 5.5\times$speedup without sacrificing model accuracy, compared to existing methods.

Quantum entanglement enables important computing applications such as quantum key distribution. Based on quantum entanglement, quantum networks are built to provide long-distance secret sharing between two remote communication parties. Establishing a multi-hop quantum entanglement exhibits a high failure rate, and existing quantum networks rely on trusted repeater nodes to transmit quantum bits. However, when the scale of a quantum network increases, it requires end-to-end multi-hop quantum entanglements in order to deliver secret bits without letting the repeaters know the secret bits. This work focuses on the entanglement routing problem, whose objective is to build long-distance entanglements via untrusted repeaters for concurrent source-destination pairs through multiple hops. Different from existing work that analyzes the traditional routing techniques on special network topologies, we present a comprehensive entanglement routing model that reflects the differences between quantum networks and classical networks as well as a new entanglement routing algorithm that utilizes the unique properties of quantum networks. Evaluation results show that the proposed algorithm Q-CAST increases the number of successful long-distance entanglements by a big margin compared to other methods. The model and simulator developed by this work may encourage more network researchers to study the entanglement routing problem.

At the network edge, federated learning (FL) has gained attention as a promising approach for training deep learning (DL) models collaboratively across a large number of devices while preserving user privacy. However, FL still faces specific challenges related to the limited, heterogeneous and dynamic resources of devices. In most FL systems, all devices train the same model, while the devices with constrained resources, referred to as stragglers, will significantly slow down overall training process. It is intuitive to alleviate computation and communication load on the stragglers by training and transmitting a part of the model. Inspired by multi-exit models, we divide an original DL model into several non-overlapping blocks, which can be trained separately on the low-capability devices. Furthermore, we propose BOSE, a novel FL system that performs adaptiveblock-wisemodel training under resource constraints. Considering the diverse impacts of different blocks on model convergence and the varying training loads they incur, a naive block assignment strategy, e.g., uniformly random assignment, may not yield optimal model performance and fail to fully utilize available resources. To this end, we introduce two metrics, includinglearning speedanddevice-wise divergence, to measure the potential of blocks in promoting model convergence. Given resource budget, BOSE initially identifies a set of candidate blocks for each device and subsequently selects specific training blocks based on their potential for promoting model convergence. In general, blocks with higher potential are more likely to be chosen for training. Extensive experiments on a physical platform show that BOSE provides a 1.4$\times$$\sim$3.8$\times$speedup without sacrificing model accuracy, compared to the baselines.

Payment channel networks (PCNs) have been designed and utilized to address the scalability challenge and throughput limitation of blockchains. It provides a high-throughput solution for blockchain-based payment systems. However, such “layer-2” blockchain solutions have their own problems: payment channels require a separate deposit for each channel of two users. Thus it significantly locks funds from users into particular channels without the flexibility of moving these funds across channels. In this paper, we proposed Aggregated Payment Channel Network (APCN), in which flexible funds are used as a per-user basis instead of a per-channel basis. To prevent users from misbehaving such as double-spending, APCN includes mechanisms that make use of hardware trusted execution environments (TEEs) to control funds, balances, and payments. The distributed routing protocol in APCN also addresses the congestion problem to further improve resource utilization. Our prototype implementation and simulation results show that APCN achieves significant improvements on transaction success ratio with low routing latency, compared to even the most advanced PCN routing.

Blockchain interoperability and throughput scalability are two crucial problems that limit the wide adoption of blockchain applications. Payment channel networks (PCNs) provide a promising solution to the inherent scalability problem of blockchain technologies, allowing off-chain payments between senders and receivers via multi-hop payment paths. This paper presents a cross-chain PCN, called XHub, that extends PfCNs to support multi-hop paths across multiple blockchains and resolves both interoperability and throughput scalability. XHub achieves service availability, transaction atomicity, and auditability. Users who correctly follow the protocols will succeed in making payments or get profits from doing the services. In addition, trustworthy information about hubs will be managed in a decentralized manner and available to all users. We conduct prototype implementation of machines that exchange Internet messages and run with two real blockchains as well as large-scale simulations based on real-world PCN topologies and transactions. The results show that XHubs has small latency for cross-chain payments and can achieve a significantly higher success rate compared to the version without hub management protocols. This work is an important step towards the big picture of a decentralized transaction system that connects a wide scope of users in different blockchains.

Decentralized federated learning (DFL) has been proposed to use peer-to-peer communication for model aggregation to avoid the single point of failure problem in federated learning (FL). However, this process is vulnerable to attackers who share false models and data. In this work, we propose Blockchain-based Verifiable Decentralized Federated Learning (BVDFL), which leverages a blockchain for decentralized model verification and auditing. BVDFL includes an auditor committee for model verification, a reputation model to evaluate the trustworthiness of clients, and a protocol suite for dynamic network updates. Simulation results show that, with the reputation mechanism, BVDFL achieves fast model convergence and high accuracy on real datasets with malicious clients in the system.

Off-chain networks have been designed and utilized to address the scalability challenge and throughput limitation of blockchains. The most widely used one, the Lightning Network (LN), has developed rapidly since its introduction in 2015. While much research has been dedicated to improving LN's routing efficiency, security protocols, and network analysis, there remains a gap in understanding how end-users should establish channels to optimize transaction efficiency. In this work, we conduct a holistic measurement study that focuses on the practical aspects of Lightning Network transaction performance. By evaluating transaction latency, fees, and success rates under diverse sce-narios, we provide users with actionable insights to enhance their network efficiency. Furthermore, our research aids those interested in leveraging the LN for transaction relaying, fostering a more efficient and dynamic network ecosystem. Through empirical findings and analytical deductions, we pave the way for users to harness the full potential of the Lightning Network and contribute to its ongoing growth and development.

User-associated contents play an increasingly important role in modern network applications. With growing deployments of edge servers, the capacity of content storage in edge clusters significantly increases, which provides great potential to satisfy content requests with much shorter latency. However, the large number of contents also causes the difficulty of searching contents on edge servers in different locations because indexing contents costs huge DRAM on each edge server. In this work, we explore the opportunity of efficiently indexing user-associated contents and propose a scalable content-sharing mechanism for edge servers, called EdgeCut, that significantly reduces content access latency by allowing many edge servers to share their cached contents. We design a compact and dynamic data structure called Ludo Locator that returns the IP address of the edge server that stores the requested user-associated content. We have implemented a prototype of EdgeCut in a real network environment running in a public geo-distributed cloud. The experiment results show that EdgeCut reduces content access latency by up to 50% and reduces cloud traffic by up to 50% compared to existing solutions. The memory cost is less than 50MB for 10 million mobile users. The simulations using real network latency data show EdgeCut's advantages over existing solutions on a large scale.

Federated learning (FL) allows multiple clients cooperatively train models without disclosing local data. However, the existing works fail to address all these practical concerns in FL: limited communication resources, dynamic network conditions and heterogeneous client properties, which slow down the convergence of FL. To tackle the above challenges, we propose a heterogeneity-aware FL framework, called FedCG, with adaptive client selection and gradient compression. Specifically, the parameter server (PS) selects a representative client subset considering statistical heterogeneity and sends the global model to them. After local training, these selected clients upload compressed model updates matching their capabilities to the PS for aggregation, which significantly alleviates the communication load and mitigates the straggler effect. We theoretically analyze the impact of both client selection and gradient compression on convergence performance. Guided by the derived convergence rate, we develop an iteration-based algorithm to jointly optimize client selection and compression ratio decision using submodular maximization and linear programming. Extensive experiments on both real-world prototypes and simulations show that FedCG can provide up to 5.3× speedup compared to other methods.

Data generated at the network edge can be processed locally by leveraging the paradigm of edge computing (EC). Aided by EC, decentralized federated learning (DFL), which overcomes the single-point-of-failure problem in the parameter server (PS) based federated learning, is becoming a practical and popular approach for machine learning over distributed data. However, DFL faces two critical challenges, i.e., system heterogeneity and statistical heterogeneity introduced by edge devices. To ensure fast convergence with the existence of slow edge devices, we present an efficient DFL method, termed FedHP, which integrates adaptive control of both local updating frequency and network topology to better support the heterogeneous participants. We establish a theoretical relationship between local updating frequency and network topology regarding model training performance and obtain a convergence upper bound. Upon this, we propose an optimization algorithm, that adaptively determines local updating frequencies and constructs the network topology, so as to speed up convergence and improve the model accuracy. Evaluation results show that the proposed FedHP can reduce the completion time by about 51% and improve model accuracy by at least 5% in heterogeneous scenarios, compared with the baselines.

Off-chain networks have been designed and utilized to address the scalability challenge and throughput limitation of blockchains. Routing is a core problem. An ideal off-chain networks routing method needs to achieve 1) high scalability that can maintain low per-node memory and communication cost for large networks and 2) high resource utilization of channels. However, none of the existing off-chain routing methods achieve both requirements. In this work, we propose WebFlow, a distributed routing solution for off-chain networks, which only requires each user to maintain localized information and can be used for massive-scale networks with high resource utilization. We make use of two distributed data structures: multi-hop Delaunay triangulation (MDT) originally proposed for wireless networks and our innovation called distributed Voronoi diagram. We propose new protocols to generate a virtual Euclidean space in order to apply MDT to off-chain networks and use the distributed Voronoi diagram to enhance routing privacy. We conduct extensive simulations and prototype implementation to further evaluate WebFlow. The results using real and synthetic off-chain network topologies and transaction traces show that WebFlow can achieve extremely low per-node overhead and a high success rate compared to existing methods.

Radio frequency identification (RFID)-assisted management systems have been widely applied in warehousing, logistics, retailing, etc. In these scenarios, RFID-aided applications, e.g., object tracking and human behavior sensing, rely on a high-efficiency tag reading to realize accurate analyses and timely responses. However, serious tag collisions in those large-scale RFID systems will inevitably lead to significant decreases in the tag reading rates. To meet the strict timeliness requirements of those practical applications, we aim to treat the individual reading rate for each item tag differently and focus more attention on those user-interactive ones. However, due to unpredictable user behaviors, it is impractical to infer the user-interactive tags in advance. In addition, keeping focusing on them for continuous monitoring despite user movements and multipath-prevalent environments is also challenging. To solve these problems, we propose Spotlight, the first concurrent rate-adaptive reading system in passive RFIDs. Spotlight screens the ID-agnostic user-interactive tags by proposing a multichannel feature for narrow-band RFID systems without any hardware or protocol modification and achieves rate-adaptive reading by implementing real-time MU-MIMO beamforming. Substantial experiments with 1000+ COTS RFID tags exhibit that Spotlight outperforms the commercial reader by$2.7\times $and the SDR-based reader by$6.12\times $. In addition, Spotlight first proposes the online parallel decoding method to realize concurrency among multiple users, which breaks the commercial protocol’s throughput ceiling (37%) and achieves up to 59% throughputs.

Mobile edge computing is a new paradigm in which the computing and storage resources are placed at the edge of the Internet. Data placement and retrieval are fundamental services of mobile edge computing when a network of edge clouds collaboratively provide data services. These services require short-latency and low-overhead implementation in network and computing devices and load balance on edge clouds. However existing methods such as distributed hash tables (DHTs) are not enough to achieve efficient data placement and retrieval services for cooperative edge clouds. This article presents GRED, a novel data placement and retrieval service for mobile edge computing, which is efficient in not only the load balance but also routing path lengths and forwarding table sizes. GRED utilizes the programmable switches to support a virtual-space based DHT with only one overlay hop. Data location can be easily implemented on top of the GRED by associating a virtual position with each data by hashing, and storing the data at the edge server connected to the switch whose position is the nearest to the position of the data in the virtual space. We implement GRED in a P4 prototype, which provides a simple and efficient solution. Results from theoretical analysis, simulations, and experiments show that GRED can efficiently balance the load of edge clouds, and can fast answer data queries due to its low routing stretch.

Federated learning (FL) has been widely adopted to train machine learning models over massive data in edge computing. However, machine learning faces critical challenges, e.g., data imbalance, edge dynamics, and resource constraints, in edge computing. The existing FL solutions cannot well cope with data imbalance or edge dynamics, and may cause high resource cost. In this paper, we propose an adaptive asynchronous federated learning (AAFL) mechanism. To deal with edge dynamics, a certain fraction$\alpha$of all local updates will be aggregated by their arrival order at the parameter server in each epoch. Moreover, the system can intelligently vary the number of local updated models for global model aggregation in different epochs with network situations. We then propose experience-driven algorithms based on deep reinforcement learning (DRL) to adaptively determine the optimal value of$\alpha$in each epoch for two cases of AAFL, single learning task and multiple learning tasks, so as to achieve less completion time of training under resource constraints. Extensive experiments on the classical models and datasets show high effectiveness of the proposed algorithms. Specifically, AAFL can reduce the completion time by about 70 percent and improve the learning accuracy by about 28 percent under resource constraints, compared with the state-of-the-art solutions.

There have been increasing interests in exploring the sensing capabilities of RFID to enable numerous IoT applications, including object localization, trajectory tracking, and human behavior sensing. However, most existing methods rely on the signal measurement either in a low multipath environment, which is unlikely to exist in many practical situations, or with special devices, which increase the operating cost. This paper investigates the possibility of measuring ‘multi-path-free’ signal information in multipath-prevalent environments simply using a commodity RFID reader. The proposed solution, Clean Physical Information Extraction (CPIX), is universal, accurate, and compatible to standard protocols and devices. CPIX improves RFID sensing quality with near zero cost – it requires no extra device. We implement CPIX and study three major RFID sensing applications: tag localization, device calibration and human behavior sensing. CPIX reduces the localization error by 30% to 50% and achieves the MOST accurate localization by commodity readers compared to existing work. It also significantly improves the quality of device calibration and human behaviour sensing.

RFID-based Human Gesture Recognition (HGR) has gained much attention and become a promising solution for device-free human-computer interaction (HCI) in recent years. However, existing RFID sensing suffers from limited scalability as the system needs to be re-trained whenever unseen gestures are introduced, which causes overheads of data collection and re-training. Meanwhile, cross-domain sensing may also fail as the correlation between gestures and induced variations on wireless signals will change when a different domain (i.e., environment or user) is involved. In this paper, we propose a RFID-based HGR system named RF-HGR, which can recognize unseen classes in new domains with only a few labeled samples. Specifically, RF-HGR employs a lightweight few-shot learning (FSL) framework based on fine-tuning domain adaptation to eliminate model re-training overhead. We establish a real-world prototype using commercial off-the-shelf (COTS) RFID devices and the preliminary evaluation results show that RF-HGR with three-, five-, seven-shot learning can recognize novel classes in unseen domains with an accuracy of 50.6%, 65.7% and 72.8% respectively.

Payment channel networks (PCNs) have been designed and utilized to address the scalability challenge and throughput limitation of blockchains. It provides a high-throughput solution for blockchain-based payment systems. However, such “layer-2” blockchain solutions have their own problems: payment channels require a separate deposit for each channel of two users. Thus it significantly locks funds from users into particular channels without the flexibility of moving these funds across channels. In this paper, we proposed Aggregated Payment Channel Network (APCN), in which flexible funds are used as a per-user basis instead of a per-channel basis. To prevent users from misbehaving such as double-spending, APCN includes mechanisms that make use of hardware trusted execution environments (TEEs) to control funds, balances, and payments. The distributed routing protocol in APCN also addresses the congestion problem to further improve resource utilization. Our prototype implementation and simulation results show that APCN achieves significant improvements on transaction success ratio with low routing latency, compared to even the most advanced PCN routing.

One of the key challenges faced by cellular network customer care agents is identifying if the service problem is caused by network-related issues or user-device-related issues. Some service providers [5], [6], therefore, employ machine learning-based troubleshooting frameworks to aid care agents in identifying the root cause of service problems experienced by users. However, obtaining large-scale and comprehensive ground truth troubleshooting result data is costly and requires tremendous manual efforts from networking operators. Due to this limitation, training such a machine learning (ML) model is rather challenging as the model can easily overfit to the limited available ground truth data. In this work, we propose a novel two-stage learning framework to improve the classification accuracy of ML-based troubleshooting frameworks. Our proposed framework uses resolution action taken by the care agent coupled with network/device data collected after the care call to infer accurate ground truth which is then used to train classification models.

Troubleshooting cellular service issues at the per-UE (User Equipment) level is an essential task for cellular providers. However, diagnosing service issues at per-UE level is costly because it requires advanced expertise and in-depth inspection of massive network log data. This paper presents NeTExp, a generic and comprehensive data-driven approach to automatically troubleshoot cellular service issues reported by customers. NeTExp determines whether the root cause of a user-reported service issue is from the network side or the device side through deep neural networks, which extract complex spatial-temporal feature profiles from massive network log data. The system is trained and validated using an extensive period of network and customer care data from a major cellular service provider in United States. We also present a case study on an external event that caused cellular service issues in 2020 to demonstrate the effectiveness of NeTExp on detecting network issues and identifying network-issue-related root causes at per-UE level.

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.

Edge computing promises a dramatic reduction in the network latency and the traffic volume, where many edge servers are placed at the edge of the Internet. Furthermore, those edge servers cache data to provide services for edge users. The data sharing among those edge servers can effectively shorten the latency to retrieve the data and further reduce the network bandwidth consumption. The key challenge is to construct an efficient data indexing mechanism no matter how the data is cached in the edge network. Although this is essential, it is still an open problem. Moreover, existing methods such as the centralized indexing and the DHT indexing in other fields fail to meet the performance demand of edge computing. This paper presents a COordinate-based INdexing (COIN) mechanism for the data sharing in edge computing. COIN maintains a virtual space where switches and data indexes are associated with their coordinates. Then, COIN distributes data indexes to indexing edge servers based on those coordinates. The COIN is effective because any query request from an edge server can be responded when the data has been stored in the edge network. More importantly, COIN is efficient in both routing path lengths and forwarding table sizes for publishing/querying data indexes. We implement COIN in a P4 prototype. Experimental results show that COIN uses 59% shorter path length and 30% less forwarding table entries to retrieve data indexes compared to using Chord, a well-known DHT solution.

The past decades have seen a proliferation of middlebox deployment in various scenarios, including backbone networks and cloud networks. Since flows have to traverse specific service function chains (SFCs) for security and performance enhancement, it becomes much complex for SFC routing due to routing loops, traffic dynamics and scalability requirement. The existing SFC routing solutions may consume many resources (e.g., TCAM) on the data plane and lead to massive overhead on the control plane, which decrease the scalability of middlebox networks. Due to SFC requirement and potential routing loops, solutions like traditional default paths (e.g., using ECMP) that are widely used in non-middlebox networks will no longer be feasible. In this paper, we present and implement a scalable and flexible middlebox policy enforcement (SAFE-ME) system to minimize the TCAM usage and control overhead. To this end, we design the smart tag operations for construction of default SFC paths with less TCAM rules in the data plane, and present lightweight SFC routing update with less control overhead for dealing with traffic dynamics in the control plane. We implement our solution and evaluate its performance with experiments on both physical platform (Pica8) and Programming Protocol-independent Packet Processors (P4) based data plane, as well as large-scale simulations. Both experimental and simulation results show that SAFE-ME can greatly improve scalability (e.g., TCAM cost, update delay, and control overhead) in middlebox networks, especially for large-scale clouds. For example, our system can reduce the control traffic overhead by about 85% while achieving almost the similar middlebox load, compared with state-of-the-art solutions.

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.

Unexpected bursty traffic brought by certain sudden events, such as news in the spotlight on a social network or discounted items on sale, can cause severe load imbalance in backend services. Migrating hot data - the standard approach to achieve load balance - meets a challenge when handling such unexpected load imbalance, because migrating data will slow down the server that is already under heavy pressure. This article proposes PostMan, an alternative approach to rapidly mitigate load imbalance for services processing small requests. Motivated by the observation that processing large packets incurs far less CPU overhead than processing small ones, PostMan deploys a number of middleboxes called helpers to assemble small packets into large ones for the heavily-loaded server. This approach essentially offloads the overhead of packet processing from the heavily-loaded server to helpers. To minimize the overhead, PostMan activates helpers on demand, only when bursty traffic is detected. The heavily-loaded server determines when clients connect/disconnect to/from helpers based on the real-time load statistics. To tolerate helper failures, PostMan can migrate connections across helpers and can ensure packet ordering despite such migration. Driven by real-world workloads, our evaluation shows that, with the help of PostMan, a Memcached server can mitigate bursty traffic within hundreds of milliseconds, while migrating data takes tens of seconds and increases the latency during migration.

Allowing a device to verify the digital certificate of another device is an essential requirement and key building block of many security protocols for emerging and future IoT systems that involve device-to-device communication. However, on-device certificate verification is challenging for current devices, mainly because the certificate revocation (CR) checking step costs too much resource on IoT devices and the synchronization of CR status to devices yields a long latency. This paper presents an on-device CR checking system called TinyCR, which achieves 100% accuracy, memory and computation efficiency, low synchronization latency, and low network bandwidth, while being compatible with the current certificate standard. We design a new compact and dynamic data structure called DASS to store and query global CR status on a device in TinyCR. Our implementation shows that TinyCR only costs each device 1.7 MB of memory to track 100 million IoT certificates with 1% revocation rate. Checking the CR status of one certificate spends less than 1 microsecond on a Raspberry Pi 3. TinyCR can also be updated instantly when there are new certificates added or revoked.

Intent-Based Networking (IBN) has been increasingly deployed in production enterprise networks. Automated network configuration in IBN lets operators focus on intents- i.e., the end to end business objectives-rather than spelling out details of the configurations that implement these objectives. Automation brings its own concerns as the administrators cannot rely on traditional network troubleshooting tools. This situation is further exacerbated in the case of stateful Network Functions (NFs) whose packet processing behavior depends on previously observed traffic patterns. To ensure that the network configuration and state derived from network automation matches the administrator’s specified intent, we propose, Epinoia, a network intent checker for stateful networks. Epinoia relies on a unified model for NFs by leveraging the causal precedence relationships that exist between NF packet I/Os and states. Scalability of Epinoia is achieved by decomposing intents into sub-checking tasks and maintaining a causality graph between checked invariants. Epinoia checks for network-wide intent violations incrementally to reduce overhead in the event of network changes. Our evaluation results using real-world network topologies show that Epinoia can perform comprehensive checking within a few seconds per network with intent updates.

In a software defined network, the controller needs to obtain/collect traffic measurement information (i.e., flow statistics) from switches for different applications, such as traffic engineering. Existing solutions seldom consider the per-switch cost, which may lead to heavy statistics collection cost (e.g., high CPU overhead) on some switches. Due to limited computing power on most commodity switches, heavy statistics collection cost on those switches may seriously interfere with the basic rule operations, especially when some switches need to deal with many new-arrival flows or update routes of existing flows. To address this challenge, we design and implement efficient flow statistics collection (FSC) with limited interference on the basic rule operations. We formally propose a cooperative flow statistics collection with per-switch cost constraint (CP-FSC) problem. We prove that the CP-FSC problem is NP-hard and present an efficient algorithm with approximation ratio 1/2, based on dynamic programming. To reduce the time complexity, a greedy-based algorithm with approximation ratio 1/3 is also presented. We implement the proposed FSC algorithms on our SDN platform. The experimental results and the extensive simulation results show 36%-59% performance improvement compared with the existing solutions.

Presents corrections to the acknowledgement section for the above named article.

The hierarchical mobile edge computing satisfies the stringent latency requirements of data access and processing for emerging edge applications. The data location service is a basic function to provide data storage and retrieval to enable these applications. However, it still lacks research of a scalable and low-latency data location service in the environment. The existing solutions, such as DNS and DHT, fail to meet the requirement of those latency-sensitive applications. Therefore, in this article, we present a low-latency hybrid data-sharing framework, HDS. The HDS divides the data location service into two parts: intra-region and inter-region. More precisely, we design a data sharing protocol called Cuckoo Summary to achieve fast data localization in intra-region. Furthermore, for the inter-region data sharing, we develop a geographic routing based scheme to achieve efficient data localization with only one overlay hop. The advantages of HDS include short response latency, low implementation overhead, and few false positives. We implement the HDS framework based on a P4 prototype. The experimental results show that, compared to the state-of-the-art solutions, our design achieves 50.21% shorter lookup paths and 92.75% fewer false positives.

Network Function Virtualization (NFV) is a new paradigm to enable service innovation through virtualizing traditional network functions. To construct a new NFV-enabled network, there are two critical requirements: minimizing server deployment cost and satisfying switch resource constraints. However, prior work mostly focuses on the server deployment cost, while ignoring the switch resource constraints (e.g., switch's flow-table size). It thus results in a large number of rules on switches and leads to massive control overhead. To address this challenge, we propose an incremental server deployment (INSD) problem for construction of scalable NFV-enabled networks. We prove that the INSD problem is NP-Hard, and there is no polynomial-time algorithm with approximation ratio of (1- ϵ)· ln m, where ϵ is an arbitrarily small value and m is the number of requests in the network. We then present an efficient algorithm with an approximation ratio of 2 · H(q · p), where q is the number of VNF's categories and p is the maximum number of requests through a switch. We evaluate the performance of our algorithm with experiments on physical platform (Pica8), Open vSwitches, and large-scale simulations. Both experimental results and simulation results show high scalability of the proposed algorithm. For example, our solution can reduce the control and rule overhead by about 88% with about 5% additional server deployment, compared with the existing solutions.

We propose to study mobile object tracing, which allows a mobile system to report the shape, location, and trajectory of the mobile objects appearing in a video camera and identifies each of them with its cyber-identity (ID), even if the appearances of the objects are not known to the system. Existing tracking methods either cannot match objects with their cyber-IDs or rely on complex vision modules pre-learned from vast and well-annotated datasets including the appearances of the target objects, which may not exist in practice. We design and implement TagAttention, a vision-RFID fusion system that achieves mobile object tracing without the knowledge of the target object appearances and hence can be used in many applications that need to track arbitrary un-registered objects. TagAttention adopts the visual attention mechanism, through which RF signals can direct the visual system to detect and track target objects with unknown appearances. Experiments show TagAttention can actively discover, identify, and track the target objects while matching them with their cyber-IDs by using commercial sensing devices in complex environments with various multipath reflectors. It only requires around one second to detect and localize a new mobile target appearing in the video and keeps tracking it accurately over 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.

A load balancer (LB) is a vital network function for cloud services to balance the load amongst resources. Stateful software LBs that run on commodity servers provide flexibility, cost-efficiency, and packet consistency. However, current designs have two main limitations: 1) states are stored as digests, which may cause packet inconsistency due to digest collisions; 2) the data plane needs to update for every new connection, and frequent updates hurt throughput and packet consistency. In this work, we present a new software stateful LB called Concury, which is the first solution to solve these problems. The key innovation of Concury is a new method to maintain large network states with frequent connection arrivals, which is succinct in memory cost, consistent under network changes, and incurs low update cost. The evaluation results show that the Concury algorithm provides 4x throughput and consumes less memory compared to other LB algorithms, while providing weighted load balancing and false-hit freedom, for both real and synthetic data center traffic. We implement Concury and evaluate it in two real networks. It achieves 67.2 Gbps single-thread throughput on a cheap desktop computer in 100GbE.

Algorithms and data structures for data plane network functions have been extensively studied in the literature. Recently various compact data structures and algorithms have been used in data plane to achieve less memory cost and higher throughput. However, most of these studies only focus on individual network functions, such as packet forwarding information base (FIB), traffic measurement, and load balancing. To our knowledge no study has been conducted to design compact data structures and algorithms for multiple and co-located network functions. We argue that there is a huge space of optimization if we design algorithms and data structures considering multiple co-located network functions, compared to designing them individually. It is because many of them share similar design goals and building blocks. We use two recently published methods as examples and present a new memory-compact design that serves both FIB and traffic measurement functions by a novel integration of the two methods. The preliminary results show that the new design can achieve almost 2x throughput compared to running them individually while achieving higher accuracy of measurement using the same memory. In addition, we will discuss potential research directions and challenges.

There have been increasing interests in exploring the sensing capabilities of RFID to enable numerous IoT applications, including object localization, trajectory tracking, and human behavior sensing. However, most existing methods rely on the signal measurement either in a low multipath environment, which is unlikely to exist in many practical situations, or with special devices, which increase the operating cost. This paper investigates the possibility of measuring `multi-path-free' signal information in multipath-prevalent environments simply using a commodity RFID reader. The proposed solution, Clean Physical Information Extraction (CPIX), is universal, accurate, and compatible to standard protocols and devices. CPIX improves RFID sensing quality with near zero cost - it requires no extra device. We implement CPIX and study two major RFID sensing applications: tag localization and human behavior sensing. CPIX reduces the localization error by 30% to 50% and achieves the MOST accurate localization by commodity readers compared to existing work. It also significantly improves the quality of human behaviour sensing.

Network Function Virtualization (NFV) is a new paradigm to enable service innovation through virtualizing traditional network functions. To construct a new NFV-enabled network, there are two critical requirements: minimizing server deployment cost and satisfying switch resource constraints. However, prior work mostly focuses on the server deployment cost, while ignoring the switch resource constraints (e.g., switch's flow-table size). It thus results in a large number of rules on switches and leads to massive control overhead. To address this challenge, we propose an incremental server deployment (INSD) problem for construction of scalable NFV-enabled networks. We prove that the INSD problem is NP-Hard, and there is no polynomial-time algorithm with approximation ratio of (1- ε) ·ln m, where ε is an arbitrarily small value and m is the number of requests in the network. We then present an efficient algorithm with an approximation ratio of 2 · H(q · p)1, where q is the number of VNF's categories and p is the maximum number of requests through a switch. We evaluate the performance of our algorithm with experiments on physical platform (Pica8), Open vSwitches, and large-scale simulations. Both experiment and simulation results show high scalability of the proposed algorithm. For example, our solution can reduce the control and rule overhead by about 88% with about 5% additional server deployment, compared with the existing solutions.

Edge computing satisfies the stringent latency requirements of data access and processing for applications running on edge devices. The data location service is a key function to provide data storage and retrieval to enable these applications. However, it still lacks research of a scalable and low-latency data location service in mobile edge computing. Meanwhile, the existing solutions, such as DNS and DHT, fail to meet the low latency requirement of mobile edge computing. This paper presents a low-latency hybrid data-sharing framework, HDS, in which the data location service is divided into two parts: intra-region and inter-region. In the intra-region part, we design a data sharing protocol called Cuckoo Summary to achieve fast data localization. In the inter-region part, we develop a geographic routing based scheme to achieve efficient data localization with only one overlay hop. The advantages of HDS include short response latency, low implementation overhead, and few false positives. We implement our HDS framework based on a P4 prototype. The experimental results show that, compared to the state-of-the-art solutions, our design achieves 50.21% shorter lookup paths and 92.75% fewer false positives.

Person identification and tracking (PIT) is an essential research topic in computer vision (CV). A CV-based system typically needs to identify, locate, and track persons appearing in its sight. In this work, we propose RFTrack, an RFID and CV fushion system that enables cameras in public areas (like surveillance cameras) to 'recognize' the physical-identity(ID) of persons in the fields of view and track the persons with specific IDs with no training efforts. By asking the users to perform a simple authentication, the system will be aware of the targets' IDs in its sensing range. Later through comparing the motion trajectories derived from both camera videos and RF signal, we can associate RFID-tagged human objects in videos with their physical IDs. A preliminary study conducted shows that RFTrack can actively identify and track the RFID-tagged target objects using commercial RFID devices and cameras, in complex indoor environments where various multipath reflectors exist.

Quantum entanglement enables important computing applications such as quantum key distribution. Based on quantum entanglement, quantum networks are built to provide long-distance secret sharing between two remote communication parties. Establishing a multi-hop quantum entanglement exhibits a high failure rate, and existing quantum networks rely on trusted repeater nodes to transmit quantum bits. However, when the scale of a quantum network increases, it requires end-to-end multi-hop quantum entanglements in order to deliver secret bits without letting the repeaters know the secret bits. This work focuses on the entanglement routing problem, whose objective is to build long-distance entanglements via untrusted repeaters for concurrent source-destination pairs through multiple hops. Different from existing work that analyzes the traditional routing techniques on special network topologies, we present a comprehensive entanglement routing model that reflects the differences between quantum networks and classical networks as well as a new entanglement routing algorithm that utilizes the unique properties of quantum networks. Evaluation results show that the proposed algorithm Q-CAST increases the number of successful long-distance entanglements by a big margin compared to other methods. The model and simulator developed by this work may encourage more network researchers to study the entanglement routing problem.

Passive Radio Frequency Identification (RFID) tags have been widely applied in many applications, such as logistics, retailing, and warehousing. In many situations, the order of objects is more important than their absolute locations. However, state-of-art ordering methods need a continuing movement of tags and readers, which limit the application domain and scalability. In this paper, we propose a 2-dimension ordering approach for passive tags that requires no device movement. Instead, our method utilizes signal changes caused by arbitrary movement of human beings around tags, who carry no device for horizontal dimension ordering. Hence, our method is called Human Movement based Ordering (HMO). The basic idea of HMO is that when people pass between the reader antenna and tags, the received signal strength will change. By observing the time-series RSS changes of tags, HMO can obtain the order of tags along with a specific horizontal direction. For vertical dimension, we employ a linear programming method that is tolerant of tiny errors in practice. We implement HMO with commodity off-the-shelf RFID devices. The experimental results show that HMO can achieve up to 88.71 and 90.86 percent average accuracies in the signal-and multi-person cases, respectively.

We provide the first solution to an important question, “how a physical-layer authentication method can defend against signal replay attacks”. It was believed that if an attacker can replay the exact same reply signal of a legitimate authentication object (such as an RFID tag), any physical-layer authentication method will fail. This paper presents Hu-Fu, the first physical layer RFID authentication protocol that is resilient to the major attacks including tag counterfeiting, signal replay, signal compensation, and brute-force feature reply. Hu-Fu is built on two fundamental ideas, namely inductive coupling of two tags and signal randomization. Hu-Fu does not require any hardware or protocol modification on COTS passive tags and can be implemented with COTS devices. We implement a prototype of Hu-Fu and demonstrate that it is accurate and robust to device diversity and environmental changes, including locations, distance, and temperature. Hu-Fu provides a new direction of battery-free/low-power device authentication that enables numerous IoT applications.

There is an increasing trend that enterprises outsource their middlebox processing to a cloud for lower cost and easier management. However, outsourcing middleboxes brings threats to the enterprise's private information, including the traffic and rules of middleboxes, all of which are visible within the cloud. Existing solutions for secure middlebox outsourcing either incur significant performance overhead or do not support incremental updates. In this article, we present a secure and dynamic middlebox outsourcing framework, SICS, short for Secure In-Cloud Service. SICS encrypts each packet header and uses a label for in-cloud rule matching, which enables the cloud to perform its functionalities correctly with minimum header information leakage. Evaluation results show that SICS achieves higher throughput, faster construction and update speed, and lower resource overhead at the enterprise and in the cloud when compared with existing solutions.

Demand for server memory capacity and performance is rapidly increasing due to expanding working set sizes of modern applications, such as big data analytics, inmemory computing, deep learning, and server virtualization. One promising techniques to tackle this requirements is memory networking, whereby a server memory system consists of multiple 3D die-stacked memory nodes interconnected by a high-speed network. However, current memory network designs face substantial scalability and flexibility challenges. This includes (1) maintaining high throughput and low latency in large-scale memory networks at low hardware cost, (2) efficiently interconnecting an arbitrary number of memory nodes, and (3) supporting flexible memory network scale expansion and reduction without major modification of the memory network design or physical implementation. To address the challenges, we propose String Figure1, a highthroughput, elastic, and scalable memory network architecture. String Figure consists of (1) an algorithm to generate random topologies that achieve high network throughput and nearoptimal path lengths in large-scale memory networks, (2) a hybrid routing protocol that employs a mix of computation and look up tables to reduce the overhead of both in routing, (3) a set of network reconfiguration mechanisms that allow both static and dynamic network expansion and reduction. Our experiments using RTL simulation demonstrate that String Figure can interconnect over one thousand memory nodes with a shortest path length within five hops across various traffic patterns and real workloads.

Edge computing is a new paradigm in which the computing and storage resources are placed at the edge of the Internet. Data placement and retrieval are fundamental services of edge computing when a network of edge servers collaboratively provide data storage. These services require short-latency and low-overhead implementation in network devices and load balance on edge servers. However existing methods such as distributed hash tables (DHTs) are not able to achieve efficient data placement and retrieval services in the edge computing environment. This paper presents GRED, an efficient data placement and retrieval service for edge computing, which is efficient in not only the load balance but also routing path lengths and forwarding table sizes. GRED utilizes the software-defined networking paradigm to support a virtual-space based DHT with only one overlay hop. We implement GRED in a P4 prototype. Experimental results show that GRED uses <; 30% routing path lengths and achieves better load balance among edge servers compared to using Chord, a well-known DHT solution.

Though being widely used in industrial and logistic applications, current passive RFID technology still has a fundamental limitation: Individual users, who do not carry any reader, are difficult to interact with tagged items, such as retrieving their digital profiles and requesting certain association with them. Recent proposals to improve user-item interaction experience rely on special hardware such as smartphone based RID scanner. This work presents a promising approach to allow each user to interact with tagged item using only one passive tag, which is named Tag Mutual Identification Interface (TagMii). TagMii requires a user to put her user tag in a 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 RID 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 IoT applications with low cost and convenience.

Forwarding packets based on networking names is essential for network protocols on different layers, where the `names' could be addresses, packet/flow IDs, and content IDs. For long there have been efforts using dynamic and compact data structures for fast and memory-efficient forwarding. In this work, we identify that the recently developed programmable network paradigm has the potential to further reduce the time/memory complexity of forwarding structures by separating the data plane and control plane. This work presents the new designs of network forwarding structures under the programmable network paradigm, applying three typical dynamic and compact data structures: Bloom filters, Cuckoo hashing, and Othello hashing. We conduct careful analyses and experiments in real networks of these forwarding methods for multiple performance metrics, including lookup throughput, memory footprint, construction time, dynamic updates, and lookup errors. The results give rich insights on designing forwarding algorithms with dynamic and compact data structures. In particular, the new designs based on Cuckoo hashing and Othello hashing show significant advantages over the extensively studied Bloom filter based methods, in all situations discussed in this paper.

We propose to study mobile object tracing, which allows a mobile system to report the shape, location, and trajectory of the mobile objects appearing in a video camera and identifies each of them with its cyber-identity (ID), even if the appearances of the objects are not known to the system. Existing tracking methods either cannot match objects with their cyber-IDs or rely on complex vision modules pre-learned from vast and well-annotated datasets including the appearances of the target objects, which may not exist in practice. We design and implement TagAttention, a vision-RFID fusion system that archives mobile object tracing without the knowledge of the target object appearances and hence can be used in many applications that need to track arbitrary un-registered objects. TagAttention adopts the visual attention mechanism, through which RF signals can direct the visual system to detect and track target objects with unknown appearances. Experiments show TagAttention can actively discover, identify, and track the target objects while matching them with their cyber-IDs by using commercial sensing devices, in complex environments with various multipath reflectors. It only requires around one second to detect and localize a new mobile target appearing in the video aWe thank the anonymous reviewers for their suggestions and comments.nd keeps tracking it accurately over time.

There have been increasing interests in exploring the sensing capabilities of RFID to enable numerous IoT applications, including object localization, trajectory tracking, and human behavior sensing. However, most existing methods rely on the signal measurement either in a low multipath environment, which is unlikely to exist in many practical situations, or with special devices, which increase the operating cost. This paper investigates the possibility of measuring `multipath-free' signal information in multipath-prevalent environments simply using a commodity RFID reader. The proposed solution, Clean Physical Information Extraction (CPIX), is universal, accurate, and compatible to standard protocols and devices. CPIX improves RFID sensing quality with near zero cost - it requires no extra device. We implement CPIX and evaluate its effectiveness on improving the performance on tag localization. The results show that CPIX reduces the localization error by 30% to 50% and achieves the MOST accurate localization by commodity readers compared to existing work.

The past decades have seen a proliferation of middlebox deployment in various networks, including backbone networks and datacenters. Since network flows have to traverse specific service function chains (SFCs) for security and performance enhancement, it becomes much complex for SFC routing due to routing loops, traffic dynamics and scalability requirement. The existing SFC routing solutions may consume many resources (e.g., TCAM) on the data plane and lead to massive overhead on the control plane, which decrease the scalability of middlebox networks. Due to SFC requirement and potential routing loops, solutions like traditional default paths (e.g., using ECMP) that are widely used in non-middlebox networks will no longer be feasible. In this paper, we present and implement a scalable and flexible middlebox policy enforcement (SAFE-ME) system to minimize the TCAM usage and control overhead. To this end, we design the smart tag operations for construction of default SFC paths with less TCAM rules in the data plane, and present lightweight SFC routing update with less control overhead for dealing with traffic dynamics in the control plane. We implement our solution and evaluate its performance with experiments on both physical platform (Pica8) and Open vSwitch (OVS), as well as large-scale simulations. Both experimental and simulation results show that SAFE-ME can greatly improve scalability (e.g., TCAM cost, update delay, and control overhead) in middlebox networks. For example, our system can reduce the control traffic overhead by about 83% while achieving almost the similar middlebox load, compared with state-of-the-art solutions.

Public-key certificate validation is an important building block for various security protocols for IoT devices, such as secure channel establishment, handshaking, verifying sensing data authenticity from cloud storage, and Blockchains. However, certification validation incurs non-trivial overhead on resource-constrained IoT devices, because it either requires 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.

Edge computing promises a dramatic reduction in the network latency and the traffic volume, where many edge servers are placed at the edge of the Internet. Furthermore, these edge servers cache data to provide services for edge users. The data sharing among edge servers can effectively shorten the latency to retrieve the data and further reduce the network bandwidth consumption. The key challenge is to construct an efficient data indexing mechanism no matter how the data is cached in the edge network. Although this is essential, it is still an open problem. Moreover, existing methods such as the centralized indexing and the DHT indexing in other fields fail to meet the performance demand of edge computing. This paper presents a COordinate-based INdexing (COIN) mechanism for the data sharing in edge computing. COIN maintains a virtual space where the switches and the data indexes are associated with the coordinates. Then, COIN distributes data indexes to indexing edge servers based on those coordinates. The COIN is effective because any query request from an edge server can be responded when the data has been stored in the edge network. More importantly, COIN is efficient in both routing path lengths and forwarding table sizes for publishing/querying the data indexes. We implement COIN in a P4 prototype. Experimental results show that COIN uses 59% shorter path length and 30% less forwarding table entries to retrieve the data index compared to using Chord, a well-known DHT solution.

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.

We present vacuum filters, a type of data structures to support approximate membership queries. Vacuum filters cost the smallest space among all known AMQ data structures and provide higher insertion and lookup throughput in most situations. Hence they can be used as the replacement of the widely used Bloom filters and cuckoo filters. Similar to cuckoo filters, vacuum filters also store item fingerprints in a table. The memory-efficiency and throughput improvements are from the innovation of a table insertion and fingerprint eviction strategy that achieves both high load factor and data locality without any restriction of the table size. In addition, we propose a new update framework to resolve two difficult problems for AMQ structures under dynamics, namely duplicate insertions and set resizing. The experiments show that vacuum filters can achieve 25% less space in average and similar throughput compared to cuckoo filters, and 15% less space and >10x throughput compared to Bloom filters, with same false positive rates. AMQ data structures are widely used in various layers of computer systems and networks and are usually hosted in platforms where memory is limited and precious. Hence the improvements brought by vacuum filters can be considered significant.

Today's large-scale enterprise networks, data center networks, and wide area networks can be decomposed into multiple administrative or geographical domains. Domains may be owned by different administrative units or organizations. Hence protecting domain information is an important concern. Existing general-purpose Secure Multi-Party Computation (SMPC) methods that preserves privacy for domains are extremely slow for cross-domain routing problems. In this paper we present PYCRO, a cryptographic protocol specifically designed for privacy-preserving cross-domain routing optimization in Software Defined Networking (SDN) environments. PYCRO provides two fundamental routing functions, policy-compliant shortest path computing and bandwidth allocation, while ensuring strong protection for the private information of domains. We rigorously prove the privacy guarantee of our protocol. To improve time efficiency we design the QuIck Pathing (QIP) technique. QIP only requires one-time offline preprocessing and very fast online computation. We have implemented a prototype system that runs PYCRO and QIP on servers in a campus network. Experimental results using real ISP network topologies show that PYCRO and QIP are very efficient in computation and communication costs.

Smart environments and security systems require automatic detection of human behaviors including approaching to or departing from an object. Existing human motion detection systems usually require human beings to carry special devices, which limits their applications. In this paper, we present a system called APID to detect hand approaching behaviors by analyzing backscatter communication signals from a passive RFID tag on the object. APID does not require human beings to carry any device. The idea is based on the influence of hand movements to the vibration of backscattered tag signals. APID is compatible with commodity off-the-shelf devices and the EPCglobal Class-1 Generation-2 protocol. In APID, a commercial RFID reader continuously queries tags through emitting RF signals and tags simply respond with their IDs. A USRP monitor passively analyzes the communication signals and reports the approach and departure behaviors. We have implemented the APID system for both single-object and multi-object scenarios. Extensive evaluations demonstrate that APID can achieve high detection accuracy in both scenarios.

Doors as densely-deployed natural landmarks play an important role in improving indoor positioning systems. However, the state-of-the-art door event detection works are based on either vision or infrastructure, thus incurring non-trivial device or management cost. To address these problems, we present a Light-weight Magnetic-based Door Event Detection method, called LMDD. It leverages built-in magnetic sensors of common smartphones to achieve infrastructure-free door event detection. After analyzing the special features of sensors' readings changes caused by the door, we design LMDD scheme with three main components, including data acquisition, events identification and events denoising. Moreover, an improved and robust door event detection framework based on a majority-voting model is proposed to fuse multiple-dimensional sensing data from non-magnetic built-in sensors. We have implemented a prototype of LMDD on Android-based platform. Experimental results show that LMDD with only magnetic sensor achieves door event detection accuracy of around 80 percent on average, ranging from 70 to 87 percent in various typical indoor environments. The enhanced LMDD based on the fusion of heterogeneous sensors can achieve a much higher door event detection accuracy of 90 percent on average.

Smart packaging adds sensing abilities to traditional packages. This paper investigates the possibility of using RF signals to test the internal status of packages and detect abnormal internal changes. Towards this goal, we design and implement a nondestructive package testing and verification system using commodity passive RFID systems, called Echoscope. Echoscope extracts unique features from the backscatter signals penetrating the internal space of a package and compares them with the previously collected features during the check-in phase. The use of backscatter signals guarantees that there is no difference in RF sources and the features reflecting the internal status will not be affected. Compared to other nondestructive testing methods such as X-ray and ultrasound, Echoscope is much cheaper and provides ubiquitous usage. Our experiments in practical environments show that Echoscope can achieve very high accuracy and is very sensitive to various types abnormal changes.

Internet of Things has been widely applied in everyday life, ranging from transportation and healthcare to smart homes. As most IoT devices carry constrained resources and limited storage capacity, sensing data need to be transmitted to and stored at resource-rich platforms, such as a cloud. IoT applications need to retrieve sensing data from the cloud for analysis and decision-making purposes. Ensuring the authenticity and integrity of the sensing data is essential for the correctness and safety of IoT applications. We summarize the new challenges of the IoT data communication with authenticity and integrity and argue that existing solutions cannot be easily adopted to resource-constraint IoT devices. We present two solutions called dynamic tree chaining and geometric star chaining that provide efficient and secure communication for the Internet of Things. Extensive simulations and prototype emulation experiments driven by real IoT data show that the proposed system is more efficient than alternative solutions in terms of time and space.

Object storage clouds (e.g., Amazon S3) have become extremely popular due to their highly usable interface and cost-effectiveness. They are, therefore, widely used by various applications (e.g., Dropbox) to host user data. However, because object storage clouds are flat and lack the concept of a directory, it becomes necessary to maintain file meta-data and directory structure in a separate index cloud. This paper investigates the possibility of using a single object storage cloud to efficiently host the whole filesystem for users, including both the file content and directories, while avoiding meta-data loss caused by index cloud failures. We design a novel data structure, Hierarchical Hash (or H2), to natively enable the efficient mapping from filesystem operations to object-level operations. Based on H2, we implement a prototype system, H2Cloud, that can maintain large filesystems of users in an object storage cloud and support fast directory operations. Both theoretical analysis and real-world experiments confirm the efficacy of our solution: H2Cloud achieves faster directory operations than OpenStack Swift by orders of magnitude, and has similar performance to Dropbox but yet does not need a separate index cloud.

We study a new problem, refined localization, in this paper. Refined localization calculates the location of an object in high precision, given that the object is in a relatively small region such as the surface of a table. Refined localization is useful in many cyber-physical systems such as industrial autonomous robots. Existing vision-based approaches suffer from several disadvantages, including good lighting conditions, line of sight, pre-learning process, and high computation overhead. Also vision-based approaches cannot differentiate objects with similar colors and shapes. This paper presents a new refined localization system, called Trio, which uses passive Radio Frequency Identification (RFID) tags for low cost and easy deployment. Trio provides a new angle to utilize RF interference for tag localization by modeling the equivalent circuits of coupled tags. We implement our prototype using commercial off-the-shelf RFID reader and tags. Extensive experiment results demonstrate that Trio effectively achieves high accuracy of refined localization, i.e., <; 1 cm errors for several types of main stream tags.

Network failures are inevitable due to its increasing complexity, which significantly hampers system availability and performance. While adopting checkpointing and rollback recovery protocols (C/R for abbreviation) from distributed systems into computer networks is promising, several specific challenges appear as we design a C/R system for Software-Defined Networks (SDN). The C/R should be coordinated with other applications in the SDN controller, each individual switch C/R should not interrupt traffic traversing it, and SDN controller C/R faces the challenge of time and space overhead. We propose a C/R framework for SDN, named NetCP. NetCP coordinates C/R and other applications to get consistent global checkpoints, it leverages redundant forwarding tables in SDN switches for C/R so as to avoid interrupting traversing traffic, and it analyzes the dependencies between controller applications to make minimal C/R decision. We have implemented NetCP in a prototype system using the current standard SDN tools and demonstrate that it achieves consistency, non-interruption, and efficiency with negligible overhead.

We provide the first solution to an important question, "how a physical-layer authentication method can defend against signal replay attacks''. It was believed that if an attacker can replay the exact same reply signal of a legitimate authentication object (such as an RFID tag), any physical-layer authentication method will fail. This paper presents Hu-Fu, the first physical layer RFID authentication protocol that is resilient to the major attacks including tag counterfeiting, signal replay, signal compensation, and brute-force feature reply. Hu-Fu is built on two fundamental ideas, namely inductive coupling of two tags and signal randomization. Hu-Fu does not require any hardware or protocol modification on COTS passive tags and can be implemented with COTS devices. We implement a prototype of Hu-Fu and demonstrate that it is accurate and robust to device diversity and environmental changes, including locations, distance, and temperature. Hu-Fu provides a new direction of battery-free/low-power device authentication that enables numerous IoT applications.

Motivation: Metagenomic read classification is a critical step in the identification and quantification of microbial species sampled by high-throughput sequencing. Although many algorithms have been developed to date, they suffer significant memory and/or computational costs. Due to the growing popularity of metagenomic data in both basic science and clinical applications, as well as the increasing volume of data being generated, efficient and accurate algorithms are in high demand. Results: We introduce MetaOthello, a probabilistic hashing classifier for metagenomic sequencing reads. The algorithm employs a novel data structure, called l-Othello, to support efficient querying of a taxon using its k-mer signatures. MetaOthello is an order-of-magnitude faster than the current state-of-the-art algorithms Kraken and Clark, and requires only one-third of the RAM. In comparison to Kaiju, a metagenomic classification tool using protein sequences instead of genomic sequences, MetaOthello is three times faster and exhibits 20-30% higher classification sensitivity. We report comparative analyses of both scalability and accuracy using a number of simulated and empirical datasets. Availability and implementation: MetaOthello is a stand-alone program implemented in C ++. The current version (1.0) is accessible via https://doi.org/10.5281/zenodo.808941. Contact: [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

Software defined networking (SDN) is becoming increasingly prevalent for its programmability that enables centralized network configuration and management. With the growth of SDNs, a cluster of controllers cooperatively manages more and more switches/flows in a network to avoid the single-controller congestion/failure and improve the control-plane robustness. Under the architecture with multiple controllers, it is expected to minimize the maximum response time on these controllers to provide better QoS for users. To achieve this target, two previous methods are mainly used, the static scheme and the dynamic scheme. However, these methods may lead to an increase of the control-plane communication overhead/delay. In this paper, we propose to minimize the maximum response time on controllers through flow redirecting, which is implemented by installing wildcard rules on switches. We formulate the minimum controller response time problem, which takes the flow-table size and link capacity constraints into account, as an integer linear program, and prove its NP-Hardness. Two algorithms with bounded approximation factors are designed to solve this problem. We implement the proposed methods on our SDN testbed. The testing results and extensive simulation results show that our proposed algorithm can reduce the maximum controller response time by about 50%-80% compared with the static/dynamic methods under the same controller cost, or reduce the number of controllers by 30% compared with the dynamic method while preserving almost the same controller response time.

An important function of smart environments is the ubiquitous access of computing devices. In public areas such as hospitals, libraries, and airports, people may want to interact with nearby computing systems to get information, such as directions to a hospital room, locations of books, and flight departure/arrival information. Touch screen based displays and kiosks, which are commonly used today, may incur extra hardware cost or even possible germ and bacteria infection. This work provides a new solution: users can make queries and inputs by performing in-air handwriting to an array of passive RFID tags, named RFIPad. This input method does not require human hands to carry any device and hence is convenient for applications in public areas. Besides the mobile and contactless property, this system is a cost-efficient extension to current RFID systems: an existing reader can monitor multiple RFIPads while performing its regular applications such as identification and tracking. We implement a prototype of RFIPad using commercial off-the-shelf UHF RFID devices. Experimental results show that RFIPad achieves >91% accuracy in recognizing basic touch-screen operations and English letters.

Computer networks are becoming increasingly complex today and thus prone to various network faults. Traditional testing tools (e.g., ping, traceroute) that often involve substantial manual effort to uncover faults are inefficient. This paper focuses on fault detection of the network data plane using test packets. Existing solutions of test packet generation either take very long time (e.g., more than one hour) to complete or generate too many test packets that may hurt regular traffic. In this paper, we present Pronto, an automated test packet generation tool that generates test packets to exercise data plane rules in the entire network in a short time (e.g., several seconds) and can quickly react to rule changes due to network dynamics. In addition, Pronto minimizes the number of test packets by allowing a packet to test multiple rules at different switches. The performance evaluation using two real network data plane rule sets shows that Pronto is faster than a recently developed tool by more than two orders of magnitude. Pronto can update the probes for rule changes using less than 1ms while existing methods have no such update function.

Outsourcing middleboxes brings threats to the enterprise's private information including the trafflc and rules of middleboxes. We present a secure and dynamic middlebox outsourcing framework SICS, short for Secure In-Cloud Service. SICS encrypts each packet header and uses a label for in-cloud rule matching, which enables the cloud to perform its functionalities correctly with minimum header information leakage.

Forwarding information base (FIB) scalability and its lookup speed are fundamental problems of numerous network technologies that uses location-independent network names. In this paper we present a new network algorithm, Othello Hashing, and its application of a FIB design called Concise, which uses very little memory to support ultra-fast lookups of network names. Othello Hashing and Concise make use of minimal perfect hashing and relies on the programmable network framework to support dynamic updates. Our conceptual contribution of Concise is to optimize the memory efficiency and query speed in the data plane and move the relatively complex construction and update components to the resource-rich control plane. We implemented Concise on three platforms. Experimental results show that Concise uses significantly smaller memory to achieve much faster query speed compared to existing solutions of network name lookups.

In a software defined network (SDN), the control plane needs to frequently collect flow statistics measured at the data plane switches for different applications, such as traffic engineering, flow re-routing, and attack detection. However, existing solutions for flow statistics collection may result in large bandwidth cost in the control channel and long processing delay on switches, which significantly interfere with the basic functions such as packet forwarding and route update. To address this challenge, we propose a Cost-Optimized Flow Statistics Collection (CO-FSC) scheme using wildcard-based requests. We prove that the CO-FSC problem is NP-Hard and present a rounding-based algorithm with an approximation factor f, where f is the maximum number of switches visited by each flow. Moreover, our CO-FSC problem is extended to the general case, in which only a part of flows in a network need to be collected. The extensive simulation results show that the proposed algorithms can reduce the bandwidth overhead by over 41% and switch processing delay by over 45% compared with the existing solutions.

There have been increasing interests in exploring the sensing capabilities of RFID beyond its basic identification task, to reveal more information of tagged objects and the physical world. Phase is a crucial physical feature for many RFID sensing applications, such as tag localization. Most existing methods rely on a low multipath environment for accurate phase measurement. Unfortunately, practical environments are highly likely to be multipath-revalent, especially for indoors. This paper presents the first work to extract "clean" phase measurement of RFID tags in multipath-prevalent environments. We propose CPEX (Clean Phase EXtraction) based on theoretical modeling, which is also validated via experimental results of our prototype implementation. We studied the performance of CPEX on tag localization. CPEX can achieve median errors of 4.3-6.4cm (in different setups), which is the most accurate 3D tag localization result in multipath-prevalent environments.

Passive Radio Frequency Identification (RFID) tags have been widely applied in many applications, such as logistics, retailing, and warehousing. In many situations the relative locations of objects are more important than their absolute locations. However, state-of-art relative localization methods need continuing movement of tags and readers, which limit the application domain and scalability. In this paper, we propose a relative localization approach for passive tags that requires no device movement. Instead, our method utilizes signal changes caused by arbitrary movement of human beings around tags, who carry no device. Hence our method is called Human Movement based Relative Localization (HMRL). The basic idea of HMRL is that when people pass between reader antenna and tags, the received signal strength will change. By observing the time-series RSS changes of tags, HMRL can obtain the order of tags along a specific horizontal direction. HMRL can also get the order of tags in a vertical direction using hyperbolic positioning. We implement HMRL with commodity off-the-shelf RFID devices. The experimental results show that HMRL achieves high accuracy for relative localization of passive tags.

With rapid development and popularity, smartphones have been of importance in our daily life. Despite of its convenience in communication and computing, smartphones also lead potential security threats to users. Existing methods on smartphones for protecting user's privacy mainly depend on password or fingerprint based authentication. Most smartphone passwords are very simple and easy to guess or crack, and fingerprinting requires extra hardware and hence increases the price of smartphones. In this paper, we present a smartphone-based identity authentication method based on user's lip motion characteristics, called SALM, which can be used as an additional authentication with password. SALM extracts the feature of lip movements as the authentication token, which is unique for each user. We implement SALM using off-the-shelf smartphones and evaluate its performance via extensive experiments. The results show that the overall accuracy of user authentication using SALM (without password) is higher than 96%.

Identifying the network-wide forwarding behaviors of a packet is essential for many network management applications, including rule verification, policy enforcement, attack detection, traffic engineering, and fault localization. Current tools that can perform packet behavior identification either incur large time and memory costs or do not support real-time updates. In this paper, we present AP Classifier, a control plane tool for packet behavior identification. AP Classifier is developed based on the concept of atomic predicates, which can be used to characterize the forwarding behaviors of packets. Experiments using the data plane network state of two real networks show that the processing speed of AP Classifier is faster than existing tools by at least an order of magnitude. Furthermore, AP Classifier uses very small memory and is able to support real-time updates.

Due to flow dynamics, a software defined network (SDN) may need to frequently update its data plane so as to optimize various performance objectives, such as load balancing. Most previous solutions first determine a new route configuration based on the current flow status, and then update the forwarding paths of existing flows. However, due to slow update operations of Ternary Content Addressable Memory-based flow tables, unacceptable update delays may occur, especially in a large or frequently changed network. According to recent studies, most flows have short duration and the workload of the entire network will vary significantly after a long duration. As a result, the new route configuration may be no longer efficient for the workload after the update, if the update duration takes too long. In this paper, we address the real-time route update, which jointly considers the optimization of flow route selection in the control plane and update scheduling in the data plane. We formulate the delay-satisfied route update problem, and prove its NP-hardness. Two algorithms with bounded approximation factors are designed to solve this problem. We implement the proposed methods on our SDN test bed. The experimental results and extensive simulation results show that our method can reduce the route update delay by about 60% compared with previous route update methods while preserving a similar routing performance (with link load ratio increased less than 3%).

In a software-defined network (SDN), the control plane needs to frequently collect flow statistics measured at the data plane switches for different applications, such as traffic engineering, QoS routing, and attack detection. However, existing solutions for flow statistics collection may result in large bandwidth cost in the control channel and long processing delay on switches, which significantly interfere with the basic functions, such as packet forwarding and route update. To address this challenge, we propose a cost-optimized flow statistics collection (CO-FSC) scheme and a cost-optimized partial flow statistics collection (CO-PFSC) scheme using wildcard-based requests, and prove that both the CO-FSC and CO-PFSC problems are NP-hard. For CO-FSC, we present a rounding-based algorithm with an approximation factor f, where f is the maximum number of switches visited by each flow. For CO-PFSC, we present an approximation algorithm based on randomized rounding for collecting statistics information of a part of flows in a network. Some practical issues are discussed to enhance our algorithms, for example, the applicability of our algorithms. Moreover, we extend CO-FSC to achieve the control link cost optimization FSC problem, and also design an algorithm with an approximation factor f for this problem. We implement our designed flow statistics collection algorithms on the open virtual switch-based SDN platform. The testing and extensive simulation results show that the proposed algorithms can reduce the bandwidth overhead by over 39% and switch processing delay by over 45% compared with the existing solutions.

Ranging from web caches to firewalls, network functions play a critical role in modern networks. The emerging of Network Function Virtualization (NFV) has recently gained wide attention from both industry and academia, also making the study of their placement a popular research topic. This paper surveys recent network function orchestration frameworks, and particularly the network function placement strategies. We identify their design considerations as well as the companion advantages and disadvantages for different placing strategies in this paper.

Device-to-device communication is important to emerging mobile applications such as Internet of Things and mobile social networks. Authentication and key agreement among multiple legitimate devices is the important first step to build a secure communication channel. Existing solutions put the devices into physical proximity and use the common radio environment as a proof of identities and the common secret to agree on a same key. However they experience very slow secret bit generation rate and high errors, requiring several minutes to build a 256-bit key. In this work, we design and implement an authentication and key agreement protocol for mobile devices, called The Dancing Signals (TDS), being extremely fast and error-free. TDS uses channel state information (CSI) as the common secret among legitimate devices. It guarantees that only devices in a close physical proximity can agree on a key and any device outside a certain distance gets nothing about the key. Compared with existing solutions, TDS is very fast and robust, supports group key agreement, and can effectively defend against predictable channel attacks. We implement TDS using commodity off-the-shelf 802.11n devices and evaluate its performance via extensive experiments. Results show that TDS only takes a couple of seconds to make devices agree on a 256-bit secret key with high entropy.

Modern distributed key-value stores are offering superior performance, incremental scalability, and fine availability for data-intensive computing and cloud-based applications. Among those distributed data stores, the designs that ensure the confidentiality of sensitive data, however, have not been fully explored yet. In this paper, we focus on designing and implementing an encrypted, distributed, and searchable key-value store. It achieves strong protection on data privacy while preserving all the above prominent features of plaintext systems. We first design a secure data partition algorithm that distributes encrypted data evenly across a cluster of nodes. Based on this algorithm, we propose a secure transformation layer that supports multiple data models in a privacy-preserving way, and implement two basic APIs for the proposed encrypted key-value store. To enable secure search queries for secondary attributes of data, we leverage searchable symmetric encryption to design the encrypted secondary indexes which consider security, efficiency, and data locality simultaneously, and further enable secure query processing in parallel. For completeness, we present formal security analysis to demonstrate the strong security strength of the proposed designs. We implement the system prototype and deploy it to a cluster at Microsoft Azure. Comprehensive performance evaluation is conducted in terms of Put/Get throughput, Put/Get latency under different workloads, system scaling cost, and secure query performance. The comparison with Redis shows that our prototype can function in a practical manner.

Data center networks with random topologies provide several promising features, such as near-optimal bisection bandwidth and flexibility of incremental growth. However, network failures are ubiquitous and significantly affect the performance of cloud services, such as availability and bandwidth. Existing random topology based data centers do not provide specific fault-tolerance mechanisms to recover the network from failures and to protect network performance from downgrading. In this work, we design FTDC, a fault-tolerant network and its routing protocols. FTDC is developed to provide high-bandwidth and flexibility to data center applications and achieve fault tolerance in a self-fixing manner. Upon failures, the nodes automatically explore valid paths to deliver packets to the destination by exchanging control packets. FTDC is a generalized solution that can be applied to multiple existing data center topologies. Experimental results show that FTDC demonstrates high performance with very little extra overhead during network failures.

Smart environments and security systems require automatic detection of human behaviors including approaching to or departing from an object. Existing human motion detection systems usually require human beings to carry special devices, which limits their applications. In this paper, we present a system called APID to detect arm reaching by analyzing backscatter communication signals from a passive RFID tag on the object. APID does not require human beings to carry any device. The idea is based on the influence of human movements to the vibration of backscattered tag signals. APID is compatible with commodity off-the-shelf devices and the EPCglobal Class-1 Generation-2 protocol. In APID an commercial RFID reader continuously queries tags through emitting RF signals and tags simply respond with their IDs. A USRP monitor passively analyzes the communication signals and reports the approach and departure behaviors. We have implemented the APID system for both single-object and multi-object scenarios in both horizontal and vertical deployment modes. The experimental results show that APID can achieve high detection accuracy.

Smart packaging adds sensing abilities to traditional packages. This paper investigates the possibility of using RF signals to test the internal status of packages and detect abnormal internal changes. Towards this goal, we design and implement a nondestructive package testing and verification system using commodity passive RFID systems, called Echoscope. Echoscope extracts unique features from the backscatter signals penetrating the internal space of a package and compares them with the previously collected features during the check-in phase. The use of backscatter signals guarantees that there is no difference in RF sources and the features reflecting the internal status will not be affected. Compared to other nondestructive testing methods such as X-ray and ultrasound, Echoscope is much cheaper and provides ubiquitous usage. Our experiments in practical environments show that Echoscope can achieve very high accuracy and is very sensitive to various types abnormal changes.

Network functions virtualization is a new paradigm to offer flexibility of software network function processing on demand. Policy enforcement satisfies network function policies that requires flows to traverse through given sequences of network functions. We summarize three desired properties of virtual network function placement, namely policy enforcement, interference freedom, and resource isolation. However, none of existing solutions can satisfy all of them. In this paper, we present a novel SDN-based NFV orchestration framework, called APPLE, to enforce network function policies while providing the above properties. We present detailed design considerations and prototype implementation. We conduct experiments using representative network topologies, traffic matrices, and policy chains. The results from both prototype experiments and simulations show that APPLE is resource efficient and can quickly react to traffic changes.

Due to flow dynamics, a software defined network (SDN) may need to frequently update its data plane so as to optimize various performance objectives, such as load balancing. Most previous solutions first determine a new route configuration based on the current flow status, and then update the forwarding paths of existing flows. However, due to slow update operations of Ternary Content Addressable Memory (TCAM) based flow tables, unacceptable update delays may occur, especially in a large or frequently changed network. According to recent studies, most flows have short duration and the workload of the entire network may vary after a long duration. As a result, the new route configuration may be no longer efficient for the workload after the update, if the update duration takes too long. In this paper, we address the real-time route update, which jointly considers the optimization of flow route selection in the control plane and update scheduling in the data plane. We formulate the delay-satisfied route update (DSRU) problem, and prove its NP-Hardness. Two algorithms with bounded approximation factors are designed to solve this problem. We implement the proposed methods on our SDN testbed. The experimental results and extensive simulation results show that our method can reduce the route update delay by about 60% compared with previous route update methods while preserving a similar routing performance (with link load ratio increased less than 3%).

Anonymous content sharing over the Internet protects user privacy and content confidentiality. Most overlay anonymous communication protocols employ some relay nodes as the proxies to forward content and require relays to perform cryptography or coding operations on messages. They have two major limitations. First, extra computation overhead may discourage overlay nodes from serving as relays. Second, long forwarding latency at relays makes an anonymous path easier to fail under network churn. In this paper, we present a lightweight and decentralized anonymous content sharing system named Garlic Cast, which requires near-zero computation cost on relays and does not rely on any centralized service. Garlic Cast uses random walks to find proxies in overlay networks and an security-enhanced Information Dispersal Algorithm to search and deliver content files. We have implemented a prototype of Garlic Cast and performed extensive simulation on real overlay topologies. Evaluation results show that the throughput of Garlic Cast is higher than that of RSA-based anonymous routing by over two orders of magnitude. Garlic Cast provides high level of anonymity and is robust to various attacks.

Identifying the object that attracts human visual attention is an essential function for automatic services in smart environments. However, existing solutions can compute the gaze direction without providing the distance to the target. In addition, most of them rely on special devices or infrastructure support. This paper explores the possibility of using a smartphone to detect the visual attention of a user. By applying the proposed VADS system, acquiring the location of the intended object only requires one simple action: gazing at the intended object and holding up the smartphone so that the object as well as user's face can be simultaneously captured by the front and rear cameras. We extend the current advances of computer vision to develop efficient algorithms to obtain the distance between the camera and user, the user's gaze direction, and the object's direction from camera. The object's location can then be computed by solving a trigonometric problem. VADS has been prototyped on commercial off-the-shelf (COTS) devices. Extensive evaluation results show that VADS achieves low error (about 1.5° in angle and 0.15m in distance for objects within 12m) as well as short latency. We believe that VADS enables a large variety of applications in smart environments.

Server-centric data center networks enable several important features of modern data center applications, such as cloud storage and big data processing. However, network failures are ubiquitous and significantly affect network performance, such as routing correctness and network bandwidth. Existing server-centric data centers do not provide specific fault-tolerance mechanisms to recover the network from failures and to protect network performance from downgrading. In this work, we design FTDC, a fault-tolerant network and its routing protocols. FTDC is developed to provide high-bandwidth and flexibility to data center applications and achieve fault tolerance in a self-fixing manner. Upon failures, the servers automatically explore valid paths to deliver packets to the destination by exchanging control messages among servers. Experimental results show that FTDC demonstrate high performance with very little extra overhead during network failures.

Multi-user MIMO (MU-MIMO) is proposed in 802.11ac to achieve more than 3x faster than 802.11n. In the real world no-one gets close to theoretical speeds. The primary reason for this anomaly are the various overheads of channel access and channel state information (CSI) feedback. In order to achieve concurrent data transmission, (CSI) feedback from users is required. However, this overhead can easily overwhelm the actual channel time spent on data transmission in large-scale network. Moreover, due to spontaneous uplink traffic, which makes the problem even more challenging.

Different from online shopping, in-store shopping has few ways to collect the customer behaviors before purchase. In this paper, we present the design and implementation of an on-site Customer Behavior IDentification system based on passive RFID tags, named CBID. By collecting and analyzing wireless signal features, CBID can detect and track tag movements and further infer corresponding customer behaviors. We model three main objectives of behavior identification by concrete problems and solve them using novel protocols and algorithms. The design innovations of this work include a Doppler effect based protocol to detect tag movements, an accurate Doppler frequency estimation algorithm, an image-based human count estimation protocol and a tag clustering algorithm using cosine similarity. We have implemented a prototype of CBID in which all components are built by off-the-shelf devices. We have deployed CBID in real environments and conducted extensive experiments to demonstrate the accuracy and efficiency of CBID in customer behavior identification.

Device-free object tracking provides a promising solution for many localization and tracking systems to monitor non-cooperative objects, such as intruders, which do not carry any transceiver. However, existing device-free solutions mainly use special sensors or active RFID tags, which are much more expensive compared to passive tags. In this paper, we propose a novel motion detection and tracking method using passive RFID tags, named Twins. The method leverages a newly observed phenomenon called critical state caused by interference among passive tags. We contribute to both theory and practice of this phenomenon by presenting a new interference model that precisely explains it and using extensive experiments to validate it. We design a practical Twins based intrusion detection system and implement a real prototype by commercial off-the-shelf RFID reader and tags. Experimental results show that Twins is effective in detecting the moving object, with very low location errors of 0.75 m in average (with a deployment spacing of 0.6 m).

Physical-layer identification utilizes unique features of wireless devices as their fingerprints, providing authenticity and security guarantee. Prior physical-layer identification techniques on radio frequency identification (RFID) tags require nongeneric equipments and are not fully compatible with existing standards. In this paper, we propose a novel physical-layer identification system, GenePrint, for UHF passive tags. The GenePrint prototype system is implemented by a commercial reader, a USRP-based monitor, and off-the-shelf UHF passive tags. Our solution is generic and completely compatible with the existing standard, EPCglobal C1G2 specification. GenePrint leverages the internal similarity among pulses of tags' RN16 preamble signals to extract a hardware feature as the fingerprint. We conduct extensive experiments on over 10 000 RN16 preamble signals from 150 off-the-shelf RFID tags. The results show that GenePrint achieves a high identification accuracy of 99.68% +. The feature extraction of GenePrint is resilient to various malicious attacks, such as the feature replay attack.

We present the architecture and protocols of ROME, a layer-2 network designed to be backwards-compatible with Ethernet and scalable to tens of thousands of switches and millions of end-hosts. Such large-scale networks are needed for emerging applications including data center networks, wide area networks, and metro Ethernet. ROME is based upon a recently developed greedy routing protocol, greedy distance vector (GDV). Protocol design innovations in ROME include a stateless multicast protocol, a Delaunay distributed hash table (DHT), as well as routing and host discovery protocols for a hierarchical network. ROME protocols do not use broadcast and provide both control-plane and data-plane scalability. Extensive experimental results from a packet-level event-driven simulator, in which ROME protocols are implemented in detail, show that ROME protocols are efficient and scalable to metropolitan size. Furthermore, ROME protocols are highly resilient to network dynamics. The routing latency of ROME is only slightly higher than shortest-path latency. To demonstrate scalability, we provide simulation performance results for ROME networks with up to 25 000 switches and 1.25 million hosts.

Greedy routing has been applied to both wireline and wireless networks due to its scalability of routing state and resiliency to network dynamics. In this work, we solve a fundamental problem in applying greedy routing to networks with arbitrary topologies, i.e., how to construct node coordinates such that greedy routing can find near-optimal routing paths for various routing metrics. We propose Greedy Distance Vector (GDV), the first greedy routing protocol designed to optimize end-to-end path costs using any additive routing metric, such as: hop count, latency, ETX, ETT, etc. GDV requires no physical location information. Instead, it relies on a novel virtual positioning protocol, VPoD, which provides network distance embedding. Using VPoD, each node assigns itself a position in a virtual space such that the Euclidean distance between any two nodes in the virtual space is a good estimate of the routing cost between them. Experimental results using both real and synthetic network topologies show that the routing performance of GDV is better than prior geographic routing protocols when hop count is used as metric and much better when ETX is used as metric. As a greedy routing protocol, the routing state of GDV per node remains small as network size increases. We also show that GDV and VPoD are highly resilient to dynamic topology changes.

The increasing need of cloud and big data applications requires data center networks to be scalable and bandwidth-rich. Current data center network architectures often use rigid topologies to increase network bandwidth. A major limitation is that they can hardly support incremental network growth. Recent work has been investigating new network architecture and protocols to achieve three important design goals of large data centers, namely, high throughput, routing and forwarding scalability, and flexibility for incremental growth. Unfortunately, existing data center network architectures focus on one or two of the above properties and pay little attention to the others. In this paper, we design a novel flexible data center network architecture, Space Shuffle (S2), which applies greedy routing on multiple ring spaces to achieve high-throughput, scalability, and flexibility. The proposed greedy routing protocol of S2 effectively exploits the path diversity of densely connected topologies and enables key-based routing. Extensive experimental studies show that S2 provides high bisectional bandwidth and throughput, near-optimal routing path lengths, extremely small forwarding state, fairness among concurrent data flows, and resiliency to network failures.

Identifying the network-wide forwarding behaviors of a packet is essential for many network management applications, including rule verification, policy enforcement, attack detection, traffic engineering, and fault localization. Current tools that can perform packet behavior identification either incur large time and memory costs or do not support real-time updates. In this paper we present AP Classifier, a control plane tool for packet behavior identification. AP Classifier is developed based on the concept of atomic predicates which can be used to characterize the forwarding behaviors of packets. Experiments using the data plane network state of two real networks show that the processing speed of AP Classifier is faster than existing tools by at least an order of magnitude. Furthermore, AP Classifier uses very small memory and is able to support real-time updates.

Data center applications use multicast as an effective method to reduce bandwidth cost. However, traditional multicast protocols designed for IP networks are usually bottlenecked by the limited state capacity on switches. In this paper, we propose a scalable multicast solution on fat tree networks based on the observation that data center multicast traffic has strong heterogeneity. We propose to remove the multicast management logic from switches and use the SDN controller to manage multicast groups. The proposed Dual-structure Multicast (DuSM) determines elephant and mice groups according to their traffic amounts and treats them separately. For each elephant group, the controller installs multicast state to maintain multiple shared trees and the group traffic will be balanced evenly among the trees to avoid congestion. For mice groups, the controller applies state-free multicast that trades bandwidth capacity for state capacity, such as multicast-to-unicast translation. Our experiments using real multicast traffic data show that, DuSM can increase the multicast state capacity to support more number of groups by >200% compared to IP multicast. DuSM also achieves better traffic balance among links than IP multicast.

Today's large-scale enterprise networks, data center networks, and wide area networks can be decomposed into multiple administrative or geographical domains. Domains may be owned by different administrative units or organizations. Hence protecting domain information is an important concern. Existing general-purpose Secure Multi-Party Computation (SMPC) methods that preserves privacy for domains are extremely slow for cross-domain routing problems. In this paper we present PYCRO, a cryptographic protocol specifically designed for privacy-preserving cross-domain routing optimization in Software Defined Networking (SDN) environments. PYCRO provides two fundamental routing functions, policy-compliant shortest path computing and bandwidth allocation, while ensuring strong protection for the private information of domains. We rigorously prove the privacy guarantee of our protocol. We have implemented a prototype system that runs PYCRO on servers in a campus network. Experimental results using real ISP network topologies show that PYCRO is very efficient in computation and communication costs.

Efficient and accurate tracking of device-free objects is critical for anti-intrusion systems. Prior solutions for device-free object tracking are mainly based on costly sensing infrastructures, resulting in barriers to practical applications. In this paper, we propose an accurate and efficient motion detection system, named EMoD, to track device-free objects based on cheap passive RFID tags. EMoD is the first RFID system that can estimate the moving direction as well as the current location of a device-free object by measuring critical power variation sequences of passive tags. Compared with previous solutions, the unique advantage of EMoD, i.e., the capability to estimate moving directions, enables object tracking using a much sparser tag deployment. We contribute to both theory and practice of this phenomenon by presenting the interference model that precisely explains it and using extensive experiments to validate it. We design a practical EMoD based intrusion detection system and implement a prototype by commercial off-the-shelf (COTS) RFID reader and tags. The real-world experiments results show that EMoD is effective in tracking the trajectory of moving object in various environments.

Doors are important landmarks for indoor positioning systems. Hence an accurate and light-weight door detection approach is highly desired. The state-of-the-art solutions are either vision based or infrastructure based, which incur nontrivial device or management cost. This paper presents a novel approach, Light-weight Magnetic-based Door Detection (LMDD), which only relies on the information from built-in sensors of a smartphone. LMDD detects a door by analyzing the change of magnetic signal and extracting special features caused by doors. It is light-weight in both computation and infrastructure cost. We have implemented a prototype of LMDD that has been installed on various Android phones. Experimental results show that LMDD achieves door detection accuracy of 74% in average, ranging from 66% to 85% in various typical environments such as offices, classrooms, residential houses, and a hospital.

Network functions are widely deployed in modern networks, providing various network services ranging from intrusion detection to HTTP caching. Various virtual network function instances can be consolidated into one physical middlebox. Depending on the type of services, packet processing for different flows consumes different hardware resources in the middlebox. Previous solutions of multi-resource packet scheduling suffer from high computational complexity and memory cost for packet buffering and scheduling, especially when the number of flows is large. In this paper, we design a novel low-complexity and space-efficient packet scheduling algorithm called Myopia, which supports multi-resource environments such as network function virtualization. Myopia is developed based upon the fact that most Internet traffic is contributed by a small fraction of elephant flows. Myopia schedules elephant flows with precise control and treats mice flows using FIFO, to achieve simplicity of packet buffering and scheduling. We will demonstrate, via theoretical analysis, prototype implementation, and simulations, that Myopia achieves multi-resource fairness at low cost with short packet delay.

In a multi-tenant cloud, tenants want to receive reliable services and the cloud provider intends to reduce intranetwork traffic in order to provide more services. Achieving the requirements of both sides is a challenging problem. Current tenant abstraction models cannot provide enough information for the cloud provider to optimize network traffic while satisfying reliability requirements. Based on the analysis of the traffic traces of a real multi-tenant cloud, we develop a new tenant abstraction model and design a novel virtual machine placement algorithm, called NETMAP. NETMAP optimizes the cost of network traffic incurred by tenant applications under the reliability constraints from the tenants. Trace-driven simulation results show that NETMAP outperforms a number of possible solutions. Even if there is traffic estimation error from the abstraction model, NETMAP still yields an optimized VM placement.

Data center networks leverage multiple parallel paths connecting end host pairs to offer high bisection bandwidth for cluster computing applications. However, state of the art routing protocols such as Equal Cost Multipath (ECMP) is load-oblivious due to static flow-to-link assignments. They may cause bandwidth loss due to flow collisions. Recently proposed centralized scheduling algorithm or host based adaptive routing that require network-wide condition information may suffer from scalability problems. In this paper, we present Distributed Flow Scheduling (DiFS) based Adaptive Routing for hierarchical data center networks, which is a localized and switch-only solution. DiFS allows switches to cooperate to avoid over-utilized links and find available paths without centralized control. DiFS is scalable and can react quickly to dynamic traffic, because it is independently executed on switches and requires no synchronization. DiFS provides global bounds of flow balance based on local optimization. Extensive experiments show that the aggregate throughput of DiFS using various traffic patterns is much better than that of ECMP, and is similar to or higher than those of two representative protocols that use network-wide optimization.

Content-centric networking (CCN) adopts a receiver-driven, hop-by-hop transport approach that facilitates in-network caching, which in turn leads to multiple sources and multiple paths for transferring content. In such a case, keeping a single round trip time (RTT) estimator for a multi-path flow is insufficient as each path may experience different round trip times. To solve this problem, it has been proposed to use multiple RTT estimators to predict network condition. In this paper, we examine an alternative approach to this problem, CHoPCoP, which utilizes explicit congestion control to cope with the multiple-source, multiple-path situation. Protocol design innovations of CHoPCoP include a random early marking (REM) scheme that explicitly signals network congestion, and a per-hop fair share Interest shaping algorithm (FISP) and a receiver Interest control method (RIC) that regulate the Interest rates at routers and the receiver respectively. We have implemented CHoPCoP on the ORBIT testbed and conducted experiments under various network and traffic settings. The evaluation shows that CHoPCoP is a viable approach that can effectively deal with congestion in the multipath environment.

Different from online shopping, in-store shopping has few ways to collect the customer behaviors before purchase. In this paper, we present the design and implementation of an on-site Customer Behavior Identification system based on passive RFID tags, named CBID. By collecting and analyzing wireless signal features, CBID can detect and track tag movements and further infer corresponding customer behaviors. We model three main objectives of behavior identification by concrete problems and solve them using novel protocols and algorithms. The design innovations of this work include a Doppler effect based protocol to detect tag movements, an accurate Doppler frequency estimation algorithm, a multi-RSS based tag localization protocol, and a tag clustering algorithm using cosine similarity. We have implemented a prototype of CBID in which all components are built by off-the-shelf devices. We have deployed CBID in real environments and conducted extensive experiments to demonstrate the accuracy and efficiency of CBID in customer behavior identification.

Data center applications require the network to be scalable and bandwidth-rich. Current data center network architectures often use rigid topologies to increase network bandwidth. A major limitation is that they can hardly support incremental network growth. Recent studies propose to use random interconnects to provide growth flexibility. However, routing on a random topology suffers from control and data plane scalability problems, because routing decisions require global information and forwarding state cannot be aggregated. In this paper, we design a novel flexible data center network architecture, Space Shuffle (S2), which applies greedy routing on multiple ring spaces to achieve high-throughput, scalability, and flexibility. The proposed greedy routing protocol of S2 effectively exploits the path diversity of densely connected topologies and enables key-based routing. Extensive experimental studies show that S2 provides high bisectional bandwidth and throughput, near-optimal routing path lengths, extremely small forwarding state, fairness among concurrent data flows, and resiliency to network failures.

Device-free based object tracking provides a promising solution for many localization and tracking systems to monitor non-cooperative objects which do not carry any transceiver such as intruders. However, existing device-free solutions mainly use sensors and active RFID tags, which are much more expensive compared to passive tags. In this paper, we propose a novel motion detection and tracking method using passive RFID tags, named Twins. The method leverages a phenomenon called critical state caused by interference among passive tags. We theoretically explain this phenomenon via an interference model and conduct extensive experiment to validate it. We design a practical Twins based intrusion detection system and implement a real prototype with commercial off-the-shelf reader and tags. Experimental results show that Twins is effective in detecting the moving object, with low location errors of 0.75m in average.

Device to device (D2D) communication is expected to become a promising technology of the next-generation wireless communication systems. Security issues have become technical barriers of D2D communication due to its “open-air” nature and lack of centralized control. Generating symmetric keys individually on different communication parties without key exchange or distribution is desirable but challenging. Recent work has proposed to extract keys from the measurement of physical layer random variations of a wireless channel, e.g., the channel state information (CSI) from orthogonal frequency-division multiplexing (OFDM). Existing CSI-based key extraction methods usually use the measurement results of individual subcarriers. However, our real world experiment results show that CSI measurements from near-by subcarriers have strong correlations and a generated key may have a large proportion of repeated bit segments. Hence attackers may crack the key in a relatively short time and hence reduce the security level of the generated keys. In this work, we propose a fast secret key extraction protocol, called KEEP. KEEP uses a validation-recombination mechanism to obtain consistent secret keys from CSI measurements of all subcarriers. It achieves high security level of the keys and fast key-generation rate. We implement KEEP using off-the-shelf 802.11n devices and evaluate its performance via extensive experiments. Both theoretical analysis and experimental results demonstrate that KEEP is safer and more effective than the state-of-the-art approaches.

Locating lossy nodes in wireless sensor networks (WSNs) is difficult due to the large amount of sensor nodes, and their limited resources. The state-of-the-art work frames lossy node localization in WSNs as an optimal sequential testing problem guided by end-to-end data. It combines both active and passive measurements to minimize testing cost and number of iterations. However, this hybrid approach has many limitations. Inspired by the success of statistic methods in coverage-based software testing, and the similarity between software testing and lossy node localization, we develop an improved approach by employing Chi-square test in WSN lossy node localization. Supported by well-established statistic theories, our elegant approach delivers great performance. Experiments on randomly generated networks and deployed networks show significant performance improvement using the proposed algorithm. We expect to use this approach for other diagnostic problems in WSNs.

Physical-layer identification utilizes unique features of wireless devices as their fingerprints, providing authenticity and security guarantee. Prior physical-layer identification techniques on RFID tags require non-generic equipments and are not fully compatible with existing standards. In this paper, we propose a novel physical-layer identification system, GenePrint, for UHF passive tags. The GenePrint prototype system is implemented by a commercial reader, a USRP-based monitor, and off-the-shelf UHF passive tags. Our solution is generic and completely compatible with the existing standard, EPCglobal C1G2 specification. GenePrint leverages the internal similarity among the pulses of tags' RN16 preamble signals to extract a hardware feature as the fingerprint. We conduct extensive experiments on over 10,000 RN16 preamble signals from 150 off-the-shelf RFID tags. The results show that GenePrint achieves a high identification accuracy of 99.68%+. The feature extraction of GenePrint is resilient to various malicious attacks, such as the feature replay attack.

Almost all geographic routing protocols have been designed for 2-D. We present a novel geographic routing protocol, named Multihop Delaunay Triangulation (MDT), for 2-D, 3-D, and higher dimensions with these properties: 1) guaranteed delivery for any connected graph of nodes and physical links, and 2) low routing stretch from efficient forwarding of packets out of local minima. The guaranteed delivery property holds for node locations specified by accurate, inaccurate, or arbitrary coordinates. The MDT protocol suite includes a packet forwarding protocol together with protocols for nodes to construct and maintain a distributed MDT for routing. We present the performance of MDT protocols in 3-D and 4-D as well as performance comparisons of MDT routing versus representative geographic routing protocols for nodes in 2-D and 3-D. Experimental results show that MDT provides the lowest routing stretch in the comparisons. Furthermore, MDT protocols are specially designed to handle churn, i.e., dynamic topology changes due to addition and deletion of nodes and links. Experimental results show that MDT's routing success rate is close to 100% during churn, and node states converge quickly to a correct MDT after churn.

The growing importance of operations such as identification, location sensing, and object tracking has led to increasing interests in contactless Radio Frequency Identification (RFID) systems. Enjoying the low cost of RFID tags, modern RFID systems tend to be deployed for large-scale mobile objects. Both the theoretical and experimental results suggest that when tags are in large numbers, most existing collision arbitration protocols do not satisfy the scalability and time-efficiency requirements of many applications. To address this problem, we propose Adaptively Splitting-based Arbitration Protocol (ASAP), a scheme that provides efficient RFID identification for both small and large deployment of RFID tags, in terms of time and energy cost. Theoretical analysis and simulation evaluation show that the performance of ASAP is better than most existing collision-arbitration solutions and the time efficiency is close to the theoretically optimal values.

We present the architecture and protocols of ROME, a layer-2 network designed to be backwards compatible with Ethernet and scalable to tens of thousands of switches and millions of end hosts. ROME is based upon a recently developed geographic routing protocol, greedy distance vector (GDV). Switches in ROME do not need any location information. Protocol design innovations in ROME include a stateless multicast protocol, a Delaunay DHT, as well as routing and host discovery protocols for a hierarchical network. ROME protocols do not use broadcast. Extensive experimental results from a packet-level event-driven simulator, in which ROME protocols are implemented in detail, show that ROME protocols are efficient and scalable to metropolitan size. Furthermore, ROME protocols are highly resilient to network dynamics. The routing latency of ROME is only slightly higher than shortest-path latency. To demonstrate scalability, we provide simulation performance results for ROME networks with up to 25,000 switches and 1.25 million hosts.

The Radio Frequency Identification (RFID) technology has been widely applied to labeling moving objects. In some RFID application scenarios, e.g., product checking on conveyor belt, the tags labeled on the products need to be identified and accessed before moving out of the reader's probing range. Due to the uncertainty of ALOHA protocol and unreliability of wireless links, passing tags will suffer from collisions and link failures, and then move away without successful response. One important requirement for RFID systems is to reliably identify and access all the tags. There is naturally a tradeoff between system throughput and reliability, e.g., tag may have no chance to successfully respond in high moving speed and system throughput drops in low tag moving speed. In this paper, we introduce an integrated software system Reliable Splitting Aware ALOHA (RSAA), which is used to improve system throughput while maintaining a threshold of tag loss probability. Given a tag loss probability, RSAA is able to approach to the optimal system throughput. We implement RSAA on our NI EPC Class 1 Generation 2 UHF RFID Reader Emulator to read and access commercial tags. Experiments in indoor and outdoor scenarios are conducted to demonstrate the efficiency of RSAA. Compared with moving unaware schemes, RSAA can reliably enhance the throughput by 50%~100%. We further use trace-driven simulation to show that RSAA is able to support diverse tag density and large-scale UHF RFID systems.

Greedy Distance Vector (GDV) is the first geographic routing protocol designed to optimize end-to-end path costs using any additive routing metric, such as: hop count, latency, ETX, ETT, etc. GDV requires no node location information. Instead, GDV uses estimated routing costs to destinations which are locally computed from node positions in a virtual space. GDV makes use of VPoD, a new virtual positioning protocol for wireless networks. Prior virtual positioning systems (e.g., Vivaldi and GNP) were designed for Internet hosts and require that each host measures latencies (routing costs) to distant hosts or landmarks. VPoD does not have this requirement and uses only routing costs between directly connected nodes. Experimental results show that the routing performance of GDV is better than prior geographic routing protocols when hop count is used as metric and much better when ETX is used as metric. As a geographic protocol, the storage cost of GDV per node remains low as network size increases. GDV provides guaranteed delivery for nodes placed in 2D, 3D, and higher dimensions. We also show that GDV and VPoD are highly resilient to dynamic topology changes.

Estimating the number of RFID tags in the region of interest is an important task in many RFID applications. In this paper we propose a novel approach for efficiently estimating the approximate number of RFID tags. Compared with existing approaches, the proposed Probabilistic Estimating Tree (PET) protocol achieves O(loglogn) estimation efficiency, which remarkably reduces the estimation time while meeting the accuracy requirement. PET also largely reduces the computation and memory overhead at RFID tags. As a result, we are able to apply PET with passive RFID tags and provide scalable and inexpensive solutions for large-scale RFID systems. We validate the efficacy and effectiveness of PET through theoretical analysis as well as extensive simulations. Our results suggest that PET outperforms existing approaches in terms of estimation accuracy, efficiency, and overhead.

Almost all geographic routing protocols have been designed for 2D. We present a novel geographic routing protocol, named MDT, for 2D, 3D, and higher dimensions with these properties: (i) guaranteed delivery for any connected graph of nodes and physical links, and (ii) low routing stretch from efficient forwarding of packets out of local minima. The guaranteed delivery property holds for node locations specified by accurate, inaccurate, or arbitrary coordinates. The MDT protocol suite includes a packet forwarding protocol together with protocols for nodes to construct and maintain a distributed MDT graph for routing. We present the performance of MDT protocols in 3D and 4D as well as performance comparisons of MDT routing versus representative geographic routing protocols for nodes in 2D and 3D. Experimental results show that MDT provides the lowest routing stretch in the comparisons. Furthermore, MDT protocols are specially designed to handle churn, i.e., dynamic topology changes due to addition and deletion of nodes and links. Experimental results show that MDT's routing success rate is close to 100% during churn and node states converge quickly to a correct MDT graph after churn.

Counting the number of RFID tags (cardinality) is a fundamental problem for large-scale RFID systems. Not only does it satisfy some real application requirements, it also acts as an important aid for RFID identification. Due to the extremely long processing time, slotted ALOHA-based or tree-based arbitration protocols are often impractical for many applications, because tags are usually attached to moving objects and they may have left the readers interrogation region before being counted. Recently, estimation schemes have been proposed to count the approximate number of tags. Most of them, however, suffer from two scalability problems: time inefficiency and multiple-reading. Without resolving these problems, large-scale RFID systems cannot easily apply the estimation scheme as well as the corresponding identification. In this paper, we present the Lottery Frame (LoF) estimation scheme, which can achieve high accuracy, low latency, and scalability. LoF estimates the tag numbers by utilizing the collision information. We show the significant advantages, e.g., high accuracy, short processing time, and low overhead, of the proposed LoF scheme through analysis and simulations.

The growing importance of operations such as identification, location sensing and object tracking has led to increasing interests in contact less Radio Frequency Identification (RFID) systems. Enjoying the low cost of RFID tags, modern RFID systems tend to be deployed for large-scale mobile objects. Both the theoretical and experimental results suggest that when tags are mobile and with large numbers, two classical MAC layer collision-arbitration protocols, slotted ALOHA and Tree-traversal, do not satisfy the scalability and time-efficiency requirements of many applications. To address this problem, we propose Adaptively Splitting-based Arbitration Protocol (ASAP), a scheme that provides low-latency RFID identification and has stable performance for massive RFID networks. Theoretical analysis and experimental evaluation show that ASAP outperforms most existing collision-arbitration solutions. ASAP is efficient for both small and large deployment of RFID tags, in terms of time and energy cost. Hence it can benefit dynamic and large-scale RFID systems.

We present simulation results of a wireless routing protocol as well as join, leave, failure, and maintenance protocols, for nodes in a d-dimensional Euclidean space (d ≥ 2).

Due to critical resource restrictions, wireless sensor networks (WSNs) often face a trade-off between the cost of data transmission and the accuracy of event detection. By exploring the potential spatial and temporal correlations among sensory data, a WSN may intelligently select only a subset of nodes, whose data can still keep the major properties of those collected by the whole network, to transmit. Two important issues are examined in this study. First, which of those sensors should be selected? Second, how can the lifetime of the selected sensors be maximized? We propose a Singular Value Decomposition (SVD) based Sensory Data Suppression (SSS) Mechanism, which removes unnecessary data transmissions and prolong the lifetime of sensor networks. We also balance transmission duties among sensor nodes by leveraging the load balancing algorithms with both one-attribute and multi-attribute scenarios.

In wireless sensor networks (WSNs), QoS topology control achieves energy-efficiency by turning off redundant nodes and links, while still satisfying the given QoS requirement. However, existing topology control algorithms assume that links are either connected or disconnected. Recent experiments have shown that, besides the connected and disconnected region, a large percentage of links reside in the transitional region with fluctuating link qualities. In this paper, we propose both centralized and distributed solutions for QoS topology control, where we employ the opportunistic transmission to catch the best transmission opportunities on transitional links. Our simulations demonstrate that opportunistic transmission based approach can significantly improve energy-efficiency in QoS topology control with low communication overhead. A unique contribution of this paper is to consider link quality and apply opportunistic communication in topology control for WSNs.

Counting or estimating the number of tags is crucial for large-scale RFID systems. The use of multiple readers was recently proposed to improve the efficiency and effectiveness in reading RFID tags. Due to the long processing time, tag identification based counting schemes are often impractical, especially when tags are attached to moving objects. The existing estimation based schemes, on the other hand, suffer from the multiple-reading problem. To address this issue, we propose the Lottery Frame (LoF) scheme, a replicate-insensitive estimation protocol, that is able to eliminate multiple-readings. We show the high accuracy, short processing time and low overhead of the proposed LoF scheme through analysis and simulations.