Network traffic measurement is indispensable for many network management tasks. Time-series traffic pattern detection extends the benefits of traditional single-period flow measurement by revealing dynamic flow behaviors, but also yields higher complexity. When multiple patterns must be monitored simultaneously, building a separate sketch for each pattern is prohibitive since programmable switches typically allow only one resource-intensive sketch. In this paper, we propose PatternSketch, which enables general and dynamically reconfigurable time-series pattern detection within a single sketch. PatternSketch unifies the detection of diverse patterns with a Pattern Automaton and decomposes the pattern detection process into two phases in the data plane, while allowing operators to reconfigure the active set of monitoring patterns at runtime without taking the switch offline. Our implementation on an Intel Tofino switch demonstrates that PatternSketch can operate at line rate, detecting multiple patterns concurrently while using only tens of kilobytes of SRAM. This significantly reduces both computational and storage resource consumption compared to deploying multiple, pattern-specific sketches. Evaluations on four real-world datasets show that the hardware version of PatternSketch maintains over 90% F1 scores while simultaneously detecting six time-series patterns (three representative and three newly proposed) with as little as 200KB of memory.

Abstract The identification of key flows, as one of the most important traffic measurement tasks in high-speed networks, has lots of practical applications, including network resource optimization and network attack detection. However, the existing works define the key flows only according to the flow size or the persistence (i.e. time dimension), all of which are one-sided definitions. To bridge the gap, we propose a new metric (named $H$-value) to identify key flows in high-speed networks, in which the flow $H$-value metric considers the joint distribution of flow size and time relationships. Specifically, the $H$-value of one flow means the flow size of this flow in at least $H$ measurement periods is not less than $H$. Based on this new metric, we redefine the key flows as the flows with large $H$-values, called $H^{2}$-flow. Efficiently and accurately identifying $H^{2}$-flows in high-speed networks faces significant challenges due to limited memory space, uneven distribution of flow $H$-values, and real-time requirements. To this end, we propose a new sketch structure called H$^{2}$Sketch, which consists of two main modules. Extensive experimental results based on real datasets show that H$^{2}$Sketch outperforms all the compared solutions in all evaluation metrics, such as ARE, F1 score, and throughput.

Key-value data streams are widely spread in modern information systems. This paper delves into the inner features of individual keys and introduces a new measurement task called Core Composition Estimation for Frequent Keys (CCEFK). CCEFK aims to identify the most significant values associated with an item's key, which can be fully applied to a wide range of real-world scenarios. To address this quite challenging, multidimensional CCEFK mission, we propose PieSketch, a novel sketch-based algorithm that supports three types of queries related to CCEFK. PieSketch employs a three-level data structure and a two-staged insertion algorithm to process the keys and values of data streams separately and sequentially, achieving fine-grained data summarization for both. Through some rigorous theoretical analysis, we prove that PieSketch can achieve a good performance guarantee with low time and space complexity. We further present three optimizations to enhance PieSketch comprehensively: Sector Morphing addresses the diversity in value distribution among different keys with a dynamically adjusting strategy, significantly improving memory efficiency; Early Filtration ensures PieSketch's stability in extreme conditions; SIMD Acceleration speeds up PieSketch for data processing. We finally conducted extensive experiments on four real-world datasets to evaluate PieSketch's excellent performance. The results show that PieSketch significantly outperforms state-of-the-art techniques, achieving$23.67\times$,$88.41\times$, and$15.80\times$better accuracy on three types of queries, respectively, and demonstrating 1.84 times higher insertion throughput on average. All our codes are publicly available on GitHubhttps://github.com/NeoAnderson-20/PieSketch-source.

Identifying the hierarchical heavy hitters (HHHs), i.e., the frequent aggregated flows based on common IP prefixes, is a vital task in network traffic measurement and security. Existing methods typically employ dynamic trie structures to track numerous prefixes or utilize multiple separate sketch instances, one for each hierarchical level, to capture HHHs across different levels, while both approaches suffer from low memory efficiency and limited compatibility with programmable switches. In this paper, we introduce two novel HHH detection solutions, respectively, Hierarchical Heavy Detector (HHD) and the Compressed Hierarchical Heavy Detector (CHHD), to achieve high memory efficiency and enhanced hardware compatibility. The key idea of HHD is to design a shared bucket array structure to identify and record HHHs from all hierarchical levels, which avoids the memory wastage of maintaining separate sketches to achieve high memory efficiency and allows feasible deployment of both byte-hierarchy and bit-hierarchy HHH detection on programmable switches using minimal processing stage resources. Additionally, HHD utilizes a sampling-based update strategy to effectively balance packet processing speed and detection accuracy. Furthermore, we present the CHHD, which enhances HHH detection in bit hierarchies through a more compact cell structure, which allows for compressing several ancestor and descendant prefixes within a single cell, further boosting memory efficiency and accuracy. We have implemented HHD and CHHD on a P4-based programmable switch with limited switch resources. Experimental results based on real-world Internet traces demonstrate that HHD and CHHD outperform the state-of-the-art by achieving up to 56 percentage points higher detection precision and 2.6× higher throughput.

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

Large-scale cloud providers build geo-distributed regions to provide a wide range of services for global users. Due to the potentialcrash failuresof hardware components, the availability zone (AZ) architecture has been proposed for fault tolerance and service availability. In practice, a region consists of multiple AZs and each AZ runs independently. Considering the huge traffic volume and service diversity, how to properly deploy tasks for cost saving and QoS guarantee becomes a major challenge for cloud providers. However, existing task placement works often ignore the impact of crash failures, severely affecting users’ QoS. And fault-tolerant task placement works usually overlook other aspects of performance. Moreover, the AZ architecture has not been fully utilized in previous works. To bridge the gap, this paper proposes AzuRe, a joint region- and AZ-aware task placement framework to satisfy various tenants’ requirements in a cost-efficient manner. Due to the features of cloud services, we take a two-step approach:region-level task placement and AZ-level sub-task placement. For region-level task placement, we prove its NP-Hardness and propose an algorithm based on submodular theory with an approximation ratio of (1 − 1/e). For AZ-level sub-task placement, we formalize the problem as a multiple knapsacks problem with conflict graphs. Based on threshold rounding, we propose an algorithm with a bi-criteria approximation ratio of (2,O(log |A|)), where |A| is the number of AZs. Extensive simulation experiments on real datasets show that AzuRe improves the resource utilization ratio by up to 129.42% compared to the state-of-the-art solutions and limits the cost while meeting various kinds of region- and AZ-level requirements.

To provide a wide range of services for global users, cloud providers tend to build geo-distributed regions all over the world. With the rapid growth of cloud services, massive workloads and inter-region traffic have been introduced to current cloud networks, resulting in huge expenditure. Therefore, it is essential for a cloud provider to carefully place tasks and transfer traffic among regions to minimize the total operating costs. Existing solutions typically focus on optimizing either placement costs (e.g., computing resources, and electricity) or bandwidth costs, and overlook performance metrics, which leads to increased overall operating costs or lower user QoS. To bridge the gap, this paper proposes Copo, a joint cost and performance optimization framework for tenant task placement in geo-distributed clouds. We first formalize the cost optimization problem as an undetermined multi-commodity flow problem which has never been studied before, and propose a graph transformation algorithm to reduce the complexity. Then we combine the cost optimization with the performance optimization as the final framework. The key idea of Copo is leveraging KKT conditions to transfer the bi-level optimization to a single level. To efficiently acquire the joint task placement and traffic transfer decisions, we leverage McCormick Envelope-based relaxation to design a randomized rounding-based approximation algorithm. Extensive experiments based on real-world data show the superior cost-efficiency and performance of Copo compared with state-of-the-art solutions.

Achieving load balancing under dynamic workloads remains a critical challenge in cloud computing. However, due to inherent prediction inaccuracies and task load volatility, existing static or dynamic scheduling approaches struggle to reconcile real-time responsiveness with long-term resource efficiency, particularly when facing imprecise prediction, declared uncertainty, and data drift. To address these challenges, we propose Focus, which introduces three key innovations to achieve fault-tolerant scheduling: (1) a dynamic reservation algorithm that leverages cluster-level predictive thresholds to maintain flexible buffer capacity for sudden workload spikes, thus ensuring efficient scheduling under peak demand; (2) a multi-level load-queue architecture that enhances tolerance to task load fluctuations through probabilistic machine selection; and (3) a past information conservative mechanism combined with dynamic weighted drift detection to mitigate prediction degradation. Through the evaluation of 40 million task executions across real-world traces, Focus demonstrates superior load balancing compared to state-of-the-art algorithms, reducing load imbalance by 23.3 % under prediction errors up to 20 %.

Container scheduling is a critical issue in cloud computing. However, existing container scheduling algorithms focus on resource allocation under multiple resource constraints to maximize resource utilization while overlooking the need to balance the load of the containers and fail to mitigate resource fragmentation during task scheduling, resulting in suboptimal use of compute resources and increased makespan. This oversight often translates into unnecessarily prolonged system completion times. To solve the issue, this paper introduces the Container Scheduling with Moldable Tasks (CSMT) problem, addressing these inefficiencies through a novel framework Mocas. Mocas includes Affallo algorithm with an affinity function to achieve load balance and a fully polynomial time approximation scheme (FPTAS) DoubleShelves with an approximate ratio of$(\mathbf{1}+\mathbf{3} \epsilon)$to eliminate resource fragmentation. Extensive experiments on the real-world datasets demonstrate that the Mocas outperforms state-of-the-art solutions, achieving up to 67 % improvement in makespan compared to conventional rigid scheduling methods.

With the proliferation of edge computing and the Internet of Things (IoT), inference-driven intelligent cameras are increasingly deployed for resource-efficient and privacypreserving processing. In real-world scenarios, such as traffic surveillance, cameras deployed at different locations (e.g., intersections or corners) experience imbalanced inference workloads, leading to latency bottlenecks and resource underutilization. To address this, we propose ReMO, an adaptive framework for collaborative video analytics. Unlike full-frame offloading, ReMO divides video frames into regions to reduce data transmission and enable fine-grained load balancing. It consists of two key components: a Region Generator that analyzes scene features to identify regions with varying detection needs, and a Region Scheduler that formulates scheduling as an integer nonlinear problem, solved via an adaptive online algorithm based on Lyapunov optimization and Markov approximation. Experimental results demonstrate that ReMO effectively reduces latency by$9.3-26.3 \%$while maintaining high accuracy, outperforming baseline strategies.

Job scheduling is essential for optimizing resource utilization and enhancing user experience in cloud computing. However, dynamic cloud workloads, which are susceptible to sudden traffic surges, often lead to cluster load imbalance. Traditional scheduling methods, such as heuristic algorithms, can alleviate this imbalance but typically incur significant schedule delay due to the need for extensive job scheduling. This issue is particularly unacceptable for real-time scheduling, especially in containerized environments where jobs have short lifecycles. By incorporating a schedule delay constraint, the integer linear programming (ILP) scheduling problem solved via a solver can effectively maintain low schedule delay. However, these algorithms still suffer from high computational complexity, resulting in long decision delay and outdated scheduling actions. To address these challenges, we propose a scheduling algorithm that effectively achieves load balancing and maintains low schedule delay. Moreover, it mitigates the issue of scheduling decisions becoming outdated due to high decision delay. The proposed algorithm ensures that the schedule delay is bounded by an approximation factor of$\frac{4 \log n}{\alpha}+3$, while the server CPU capacity constraint is preserved within an approximation factor of$\frac{3 \log n}{\alpha}+3$. Experimental results based on real-world datasets show that our scheduling algorithm decreases the schedule delay by 52% to 75% and improves CPU load balance by 15% to 35% compared with the state-of-the-art solutions.

Large-scale cloud providers build geo-distributed regions to provide a wide range of services for global users. Due to the potential crash failures of hardware components, the availability zone (AZ) architecture has been proposed for fault tolerance. In practice, a region consists of multiple AZs and each$\mathbf{A Z}$runs independently. Considering the huge traffic volume and service diversity, how to properly deploy tasks for cost saving and QoS guarantee becomes a major challenge for cloud providers. However, existing task placement works often ignore the impact of crash failures, severely affecting users' QoS. And fault tolerance task placement works usually overlook other aspects of performance. Moreover, the AZ architecture has not been fully utilized in previous works. To bridge the gap, this paper proposes Azure, a cost-efficient task placement framework for fault tolerance and cost efficiency at the AZ-level. Due to traffic dynamics, we take a two-step approach: regionlevel task placement and AZ-level sub-task placement. For regionlevel task placement, we prove its NP-Hardness and propose an algorithm based on submodular theory with an approximation ratio of ($1-\frac{1}{e}$). For AZ-level sub-task placement, we formalize the problem as a multiple knapsack problem with conflict graph, which has never been studied before. Based on threshold rounding, we propose an algorithm with an approximation ratio of 2. Extensive simulation experiments on real datasets show that Azure improves resource utilization rate by$\mathbf{1 3 \% - 5 3 \%}$and limits the cost while meeting fault tolerance requirements.

Current web applications like social networks and video streaming have been generating magnificent traffic volume, along with intensive traffic dynamics, raising challenges to the fundamental infrastructure of web, i.e., datacenters. However, the traditional electric-based architectures are behind the curve due to the fixed topology and the demand-oblivious nature, failing to guarantee the performance of web applications. Motivated by the new traffic pattern, the reconfigurable technologies, like optical circuit switches (OCSes), are a promising choice to further improve throughput by dynamically adjusting connections when facing traffic dynamics. Currently, static and dynamic updating are two main methods for reconfiguring OCSes. Though static methods can acquire a solution with approximation ratio, it takes long running time and recourse. As comparison, dynamic updating can efficiently acquire a solution, yet existing solutions may degrade along with updates. This paper presents Talbot to further improve throughput with both approximation guarantee and low updating time/recourse. We formulate the throughput maximization problem as a fully dynamic k-weight limited matching problem which is$\mathcal{N} \mathcal{P}$-hard, and we further propose an approximation algorithm based on level and lazy update scheme. To evaluate Talbot, simulations are conducted with both real-world and synthetic datasets. Compared with state-of-the-art works, we show the superior performance of Talbot.

This paper investigates the problem of maintaining the connectivity between two vertices, a source and a destination, in an uncertain network under adversarial attack, where a defender preserves crucial links to prevent the source–destination vertex pair from being disconnected by an attacker. In contrast with prior art that mostly focuses on the overall network connectivity, in this work connectivity maintenance is restricted to a pair of selected vertices, which may provide insights into reliable point-to-point connection. We model the network as a random graph where each link carries both an existence probability and a probing cost, and seek to design a defensive strategy that ensures source–destination connectivity under minimum probing expenditure, regardless of adversarial behavior. To this end, we first delve into the computational complexity of the problem by establishing its NP-hardness, and put forth an optimal defensive strategy leveraging dynamic programming. Due to the prohibitive price of attaining optimality, we further design two approximate defensive strategies aimed at pursuing effective defensive performance within polynomial time, in which the first one is a path-based heuristic strategy that iteratively extends a preserved path by probing links with high utility regarding source–destination connectivity, and the second one is a cut-based minimax strategy that prioritizes the links in the minimum potential source–destination cut in order to minimize the possible worst-case loss suffered by the defender with a constant approximation ratio. Extensive experiments conducted on synthetic and real-world network datasets under diverse attacking strategies validate the superiority of the proposed strategies in both effectiveness and robustness over baselines.

Approximate membership query data structures (i.e., filters) have ubiquitous applications in database and data mining. Cuckoo filters are emerging as the alternative to Bloom filters because they support deletions and usually have higher operation throughput and space efficiency. However, their designs are confined to a single-threaded execution paradigm and consequently cannot fully exploit the parallel processing capabilities of modern hardware. This paper presents PipeFilter, a faster and more space-efficient filter that harnesses pipeline parallelism for superior performance. PipeFilter re-architects the Cuckoo filter by partitioning its data structure into several sub-filters, each providing a candidate position for every item. This allows the filter operations, including insertion, lookup, and deletion, to be naturally distributed across several pipeline stages, each overseeing one of the sub-filters, which can further be implemented through multi-threaded execution or pipeline stages of programmable hardware to achieve significantly higher throughput. Meanwhile, PipeFilter excels for single-threaded execution thanks to a combination of unique design features, includingblock design,path prophet,round robin, andSIMD optimization, such that it achieves superior performance than the SOTAs even when running with a single core. PipeFilter also has a competitive advantage in space utilization because it permits each item to explore more candidate positions. We implement and optimize PipeFilter on four platforms (single-core CPU, multi-core CPU, FPGA, and P4 ASIC). Experimental results demonstrate that PipeFilter surpasses all baseline methods on four platforms. When running with a single core, it showcases a notable 15%$\sim$57% improvement in operation throughput and a high load factor exceeding 99%. When parallel processing on other platforms, PipeFilter achieves 7$\times \sim 800\times$higher throughput than single-threaded execution.

Network traffic measurement is crucial for the effective management of data center networks. Collaborative measurement solutions distribute measurement tasks to switches based on flow-level or packet-level granularity to alleviate the measurement load on each switch. However, flow-level solutions often experience severe imbalances in measurement overhead between switches measuring large or small flows, and face scalability challenges due to the costly optimization of collaborative plans. Additionally, packet-level solutions do not adequately reduce hash collisions in sketches and fail to significantly enhance measurement accuracy. In this article, we present the Lightweight Two-level Collaborative Measurement (LTCM) that synergies flow-level and packet-level strategy to optimize measurement load balancing, reduce overall measurement overhead, and enhance measurement accuracy. We first design a Lightweight Flow-level Measurement (FCM) framework that balances the number of flows measured by each switch, incorporating a novel interval-matching technique that significantly lowers the computational costs of collaborative strategies. Based on FCM, LTCM implements our measurement load balancing strategy selector at ingress switches to detect flows whose number of packets entering the network exceeds a given threshold and evenly distribute their subsequent packets across all switches for measurement. To further improve measurement accuracy and speed, we design a two-layer collaborative sketch that reduces hash collisions between large and small flows. We implement LTCM on a Tofino-based programmable switch. Experimental results based on real Internet traces show that LTCM achieves highly efficient flow-level and packet-level measurement load balancing, improving accuracy by up to 96.6% and throughput by up to 112.79%. All related implementations are open-sourced. 1

With 52.8 billion RFID tags used worldwide in 2024, a common basic functionality needed by RFID-enabled applications is cardinality estimation — to quickly estimate the number of distinct tags in an RFID system. Although many advanced solutions have been proposed over the past decade, they suffer from one major limitation in practical use: they need to either modify the existing RFID standard or obtain MAC-layer information, both of which however cannot be supported by commercial off-the-shelf (COTS) devices. In this paper, we revisit the counting problem and propose a novel counting scheme called average time duration based counter (ATD) that quickly estimates the number of distinct tags in a standards-compliant manner. Compared with existing work, the competitive advantage of ATD is that it can be directly deployed on a COTS RFID system, with no need for any hardware modifications. In ATD, we found a new and measurable indicator — the time duration between two adjacent singleton slots, which depends on the number of tags. Following this observation, we derive the theoretical relationship between the time indicator and the number of tags and then give the proof of the estimation as well as its parameter settings. Additionally, we propose a flag-flipping solution to address the overlapping problem in the multi-reader case. We implement ATD in a COTS RFID system with 1000 tags. Experimental results show that ATD is$4.2\times $faster than the baseline of tag inventory; the performance gain will be further increased in a larger RFID system.

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

Heavy hitter detection is a fundamental network measurement task that provides critical support for many network applications. However, achieving flexible and fast heavy hitter detection in massive network traffic is challenging. Existing works generally perform detection by tracking large flows that may become heavy hitters, but they struggle to accurately identify these large flows, leading to poor accuracy. In this paper, we propose an efficient detection algorithm called HeavyCuckoo, which shows high flexibility and fast processing. We track only those large flows likely to be heavy hitters, replacing small flows of limited use for detection by exploring the activity of flow arrivals. During replacement, we utilize a tailored Conservative Replacement strategy and a tailored Selective Cuckoo Hash strategy to avoid large flows from being replaced incorrectly. We conduct theoretical analyses of memory space complexity and time complexity, and provide the error bound for heavy hitter detection. Our proposed algorithm is evaluated on real-world Internet traffic traces. Experimental results show that, compared to the prior art, the algorithm improves the Fβ-score by 56.94% and achieves 1.4724 times throughput.

Traffic measurement provides essential information for various network services. Burst is a common phenomenon in high-speed network streams, which manifests as a surge in the number of incoming packets in a flow. We propose a new definition named across-period burst, considering the change not in two adjacent time windows but in two groups of windows with time continuity. The across-period burst definition can better capture the continuous changes of flows in high-speed networks. To achieve real-time burst detection with high accuracy and low memory consumption, we propose a novel sketch named BurstDetector, which consists of two stages. Stage 1 excludes those flows that will not become burst flows, while Stage 2 accurately records the information of the potential burst flows and carries out across-period burst detections at the end of every time window. We further propose an optimization called Hierarchical Cell, which can improve the memory utilization of BurstDetector. In addition, we analyze the estimation accuracy and time complexity of BurstDetector. Extensive experiments based on real-world datasets show that our BurstDetector can achieve at least 2.8 times as much detection accuracy and processing throughput as some existing algorithms.

This paper studies a new but important pattern for items in data streams, called promising items. The promising items mean that the frequencies of an item in multiple continuous time windows show an upward trend overall, while a slight decrease in some of these windows is allowed. Many practical applications can benefit from the property of promising items, e.g., detecting potential hot events or news in social networks, preventing network congestion in communication channels, and monitoring latent attacks in computer networks. To accurately find promising items in data streams in real-time under limited memory space, we propose a novel structure named Scout Sketch, which consists of Filter and Finder. Filter is devised based on the Bloom filter to eliminate the ungratified items with less memory overload; Finder records some necessary information about the potential items and detects the promising items at the end of each time window, where we propose some tailor-made detection operations. We also analyze the theoretical performance of Scout Sketch. Finally, we conducted extensive experiments based on four real-world datasets. The experimental results show that the F1 Score and throughput of Scout Sketch are about 2.02 and 5.61 times that of the compared solutions, respectively.

Periodicity and fluctuation are two crucial characteristics of data streams. This paper investigates a novel data stream pattern called periodic spread changer (PSC flow for short), which refers to the heavy change in the spread of a flow occurring with fixed time intervals. Effectively identifying such flows is essential for many real-world applications, such as anomaly detection and network monitoring. To achieve precise real-time detection of these flows under limited memory resources, we propose a novel structure named PSC Sketch. PSC Sketch firstly performs the spread estimation by removing duplicate data items and filters out those non-potential flows with small spreads. During the measurement period, PSC Sketch detects the spread changers, calculates the time intervals between adjacent heavy changes, and reports the top-k periodic spread changers. Extensive experiments based on four real-world datasets demonstrate that, compared to competing algorithms, PSC Sketch achieves an average of 16.80 times lower average absolute error, 44.93% higher accuracy, and 1.83 times higher throughput.

Mobile crowdsensing (MC), an excellent solution to large-scale spatiotemporal data sensing problems, has recently received lots of attention from both industry and academia. In the MC system, any requester can acquire the sensing data for his points of interest (PoIs) by offering some payments to attract a group of mobile users capable of completing these PoI-related sensing tasks. However, the current MC work neglected three vital factors, more or less. First, they assume that these distributed users are mutually independent in MC, ignoring the social effects. Actually, the sensing data collected by one user may be corroborated by others’ sensing data, so-called information corroboration. Second, all rational and selfish users are inclined to gather to perform these tasks due to information corroboration. Meanwhile, they may be strategic about their participation levels to maximize profits. However, more similar sensing data will undoubtedly lower the information value, so any user has a tradeoff between gather and scatter. Third, although mobile users can obtain some payments, privacy issues may still prevent them from participating in MC. In this article, we propose a secure blockchain-assisted socially-aware MC framework by adopting the smart contract technique of Ethereum. For this framework, we further devise a two-stage Stackelberg game model to assist the requester (i.e., the leader in the game) in properly pricing each PoI-related sensing task, so that mobile users (i.e., the followers in the game) can exactly select their tasks and determine their participation levels. To analyze the game equilibrium, we extend the traditional Hessian matrix method to a multidimension case involving the multiuser multitask hyperspace setting. We conduct extensive experiments to prove the equilibrium and effectiveness of the proposed solution. We also implement a prototype and deploy the smart contract to an official Ethereum test network to demonstrate the practicability of the proposed framework.

Super spreader detection in high-speed data streams is crucial for numerous applications. Although many methods have emerged, existing works can hardly concurrently achieve high memory efficiency, support online detection, enable merging data from different measurement points/periods, and offer invertibility. This makes them unable to satisfy flexible application requirements. This paper proposes RGS-Sketch, a novel sketch designed to address this problem. The core of RGS-Sketch lies in a new mergeable memory sharing design called register group sharing. This design organizes registers into groups as basic memory sharing units, accommodating the high skewness of real-world data streams and offering high memory efficiency. Besides, it enables online detection through the real-time acquisition of a group's state, which also facilitates invertibility. To enhance detection accuracy further, we propose a limited register update strategy. It blocks small flows from updating registers, thereby reducing memory overhead and estimation noises. Extensive experimental results based on four real-world datasets show that RGS-Sketch significantly outperforms the most accurate baselines in accuracy while maintaining a high throughput. Specifically, it improves the F1 scores by up to 0.643 for measurements at a single point/period and up to 0.472 across multiple points/periods.

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

Spread estimation is an essential issue in high-speed networks with wide applications, such as network billing, quality of service, anomaly detection, etc. As a promising technique, sketch can efficiently estimate per-flow spread with only a small memory cost. Many studies focus on improving the performance of sketches. However, these works primarily focus on optimizing the counter level or sketch level without considering the scenario of multi-spread estimation, which is crucial for improving memory utilization and detecting anomalies. In this paper, we propose an efficient flow information compression algorithm based on the on-chip/off-chip hybrid framework to estimate multiple flow spreads. In the on-chip memory, we filter out non-duplicates and sample them to the off-chip space for recording. In the off-chip memory, we compress each sampled non-duplicate to a carefully designed bit-cube. When the measurement is finished, we separate corresponding KV-flows from a specific flow based on the user query. Then, we rebuild this flow to a subset group based on the duplicate number of each KV-flow. Finally, according to the Multi-set theory, we derive an accurate multi-spread estimate formula to solve this issue with a high throughput and small on-chip memory usage. Furthermore, we evaluate the performance of our proposed estimator using real Internet traffic traces downloaded from CAIDA. Experiments show that, compared to the state-of-the-art, our proposal achieves a 97.2% lower average relative error in per-destination source flow spread estimation with a tight on-chip memory, e.g., 320KB. And our proposed method achieves 31.86 higher processing throughput.

Aluminum electrolytic capacitors (AECs) are utilized as the key components in smart transformers (STs). The service status of the AEC is crucial for the maintenance of the ST. The capacitance ($C$) and the equivalent series resistance (ESR) are the key parameters to reflect the service status of AEC. Moreover, the values of$C$and ESR are negatively correlated. However, existing machine learning methods for identifying the parameters ($C$and ESR) of AEC do not consider the correlation between$C$and ESR. This reduces the accuracy of the parameter identification. This problem belongs to the exploring inter-target correlations in the field of multi-target regression. To address this issue, the low-rank double-scale convolutional neural network (LDCNN) is proposed to identify$C$and ESR. Specially, to preserve the feature structure, the fully connected layer in the traditional convolutional neural network is replaced by the tensor-train (TT) layer. And the low-rank constraint is implemented to the parameter of the TT layer to learn the correlation of$C$and ESR. The accuracy of the proposed LDCNN for the parameter identification is verified by simulation and experimental data, respectively. The validation results show that the accuracy of parameter identification can be effectively improved by learning the correlation between$C$and ESR.

Cardinality estimation is a fundamental problem with diverse practical applications. HyperLogLog (HLL) has become a standard in practice because it offers good memory efficiency, constant update time, and mergeability. Some recent work achieved better memory efficiency, but typically at the cost of impractical update time or losing mergeability, making them incompatible with applications like network-wide traffic measurement. This work presents SpikeSketch, a better cardinality estimator that reduces memory usage of HLL by 37% without sacrificing other crucial metrics. We adopt a bucket-based data structure to promise constant update time, design a smoothed log4ranking and a spike coding scheme to compress cardinality observables into buckets, and propose a lightweight mergeable lossy compression to balance memory usage, information loss, and mergeability. Then we derive an unbiased estimator for recovering cardinality from the lossy-compressed sketch. Theoretical and empirical results show that SpikeSketch can work as a drop-in replacement for HLL because it achieves a near-optimal MVP (memory-variance-product) of 4.08 (37% smaller than HLL) with constant update time and mergeability. Its memory efficiency even defeats ACPC and HLLL, the state-of-the-art lossless-compressed sketches using linear-time compression to reduce memory usage.

With 30 billion RFID tags sold worldwide in 2021, a common basic functionality needed by RFID-enabled applications is cardinality estimation --- to quickly estimate the number of distinct tags in an RFID system. Although many advanced solutions have been proposed over the past decade, they suffer from one major limitation in practical use: they need to either modify the existing RFID standard or obtain MAC-layer information, both of which however cannot be supported by commercial off-the-shelf (COTS) devices. In this paper, we revisit the counting problem and propose a novel counting scheme called average time duration based counter (ATD) that quickly estimates the number of distinct tags in a standards-compliant manner. Compared with existing work, the competitive advantage of ATD is that it can be directly deployed on a COTS RFID system, with no need for any hardware modifications. In ATD, we found a new and measurable indicator --- the time duration between two adjacent singleton slots, which depends on the number of tags. Following this observation, we derive the theoretical relationship between the time indicator and the number of tags and then give the proof of the estimation as well as its parameter settings. Additionally, we propose a flag-flipping solution to address the overlapping problem in the multi-reader case. We implement ATD in a COTS RFID system with 1000 tags. Experimental results show that ATD is 4.2× faster than the baseline of tag inventory; the performance gain will be further increased in a larger RFID system.

Heavy-hitter detection is a fundamental task in network traffic measurement and security. Existing work faces the dilemma of suffering dynamic and imbalanced traffic characteristics or lowering the detection efficiency and flexibility. In this paper, we propose a flexible sketch called SwitchSketch that embraces dynamic and skewed traffic for efficient and accurate heavy-hitter detection. The key idea of SwitchSketch is allowing the sketch to dynamically switch among different modes and take full use of each bit of the memory. We present an encoding-based switching scheme together with a flexible bucket structure to jointly achieve this goal by using a combination of design features, including variable-length cells, shrunk counters, embedded metadata, and switchable modes. We further implement SwitchSketch on the NetFPGA-1G-CML board. Experimental results based on real Internet traces show that SwitchSketch achieves a high Fβ-Score of threshold-t detection (consistently higher than 0.938) and over 99% precision rate of top-k detection under a tight memory size (e.g., 100KB). Besides, it outperforms the state-of-the-art by reducing the ARE by 30.77%\sim99.96%. All related implementations are open-sourced.

The multi-armed bandit (MAB) models have always received lots of attention from multiple research communities due to their broad application domains. The optimal selection problem with unknown rewards in advance, such as ad recommendation in social networks, spectrum access in the cognitive radio field, etc., can be efficiently solved by using MAB models. In an MAB model, given$N$arms whose rewards are unknown in advance, the player selects exactly one arm in each round, and his goal is to maximize the cumulative rewards over a fixed horizon. Further, a more general model called combinatorial MAB (i.e., CMAB), where$K$arms can be played simultaneously in each round, is put forward. However, the existing CMAB models neglect the strategic behaviors of the$N$arms, which indicates that one arm might report false information to increase its own profits. In fact, in many applications such as user selection in crowdsensing, the arms are not the feelingless machines but the rational individuals. To this end, we combine the upper confidence bound (UCB) with auction theory to develop a new algorithm called auction-based UCB (AUCB). We divide the auction-based CMAB problem into two sub-problems: winning arm selection and payment computation problems. For AUCB, we derive an upper bound on regret and prove the truthfulness in one round, individual rationality, and computational efficiency. In addition, we consider an extended situation that some arms may be unavailable in some rounds and the arms will bid inconsistently in different rounds. We devise another algorithm called eAUCB to solve this problem. Extensive simulations are conducted to show the significant performance of the proposed algorithms.

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

Blockchain came to prominence as the distributed ledger underneath Bitcoin, which protects the transaction histories in a fully-connected, peer-to-peer network. The blockchain mining process requires high computing power to solve a Proof-of-Work (PoW) puzzle, which is hard to implement on users’ mobile devices. So these miners may leverage the edge/cloud service providers (ESPs/CSP) to calculate the PoW puzzle. The existing edge-assisted blockchain networks assumed that all ESPs have a uniform propagation delay, which is unrealistic. In this article, we consider a more practical scene where ESPs locate in diverse positions of the blockchain network, which causes different propagation delays when supporting the computation of the PoW puzzle. Additionally, these ESPs connect to a remote CSP for resource scheduling when the computing tasks exceed their maximum capacity. The blockchain mining process generally involves complicated competition and games among CSP, ESPs, and miners. Each service provider focuses on how to determine his resource price so that he can maximize his utility. According to the set resource price, each miner concentrates on scheduling his resource requests for each ESP to maximize individual personal utility, which depends on ESPs’ resource price and propagation delays. We first model such a resource pricing and scheduling problem as a three-stage multi-leader multi-follower Stackelberg game and aim at finding the Stackelberg equilibrium. Then, we analyze the subgame optimization problem in each stage and propose an iterative algorithm based on backward induction to achieve the Nash equilibrium of the Stackelberg game. Finally, extensive simulations are conducted to verify the significant performance of the proposed solution.

As the popularity of mobile devices continues to increase, Mobile Crowdsensing (MC), a scalable and efficient data collection method, has received widespread attention. Although lots of effort has been devoted to studying the task assignment or worker recruitment in MC, most of them focus on how to maximize the profit from the perspective of the platform while ignoring rational individual workers' entitlement. We creatively start from the worker's perspective to find the task selection strategy to maximize the worker's profit. In this paper, the problem of unknown task selection is modeled as a Multi-Armed Bandit (MAB), on which three types of additional constraints are considered. The first constraint is the device budget. Workers choose and conduct tasks before it is exhausted. The second constraint is the personal preference regarding the traveling cost. The third constraint is the balance requirement of the MC platform, which has regulations on the tasks' execution rounds. In addition to the dilemma between exploration and exploitation in the classical MAB, we have to face the tradeoff between the reward and all the constraints above. To this end, we first adopt the epoch-style algorithm to reduce the number of switches between any two sensing tasks and further build new algorithms to deal with different constraints. The traveling cost and platform balance are involved in the task index computation as a penalty. We conduct extensive simulations based on real-world traces to verify the significant performance of our proposed algorithms.

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

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

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

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

Mobile crowdsensing, through which a requester can coordinate a crowd of workers to complete some sensing tasks, has attracted significant attention recently. In this paper, we focus on the unknown worker recruitment problem in mobile crowdsensing, where workers’ sensing qualities are unknown a priori. We consider the scenario of recruiting workers to complete some continuous sensing tasks. The whole process is divided into multiple rounds. In each round, every task may be covered by more than one recruited workers, but its completion quality only depends on these workers’ maximum sensing quality. Each recruited worker will incur a cost and each task is attached a weight to indicate its importance. Our objective is to determine a recruiting strategy to maximize the total weighted completion quality under a limited budget. We model such unknown worker recruitment process as anovel combinatorial multi-armed bandit(CMAB) problem, and propose an unknown worker recruitment algorithm based on the modified upper confidence bound (UCB). Moreover, we extend the problem to the case where the workers’ costs are also unknown and design the corresponding algorithm. We analyze the regret bounds of the two proposed algorithms through rigorous proofs. In addition, we also study the unknown worker recruitment problem with fairness constraints. Here, the term “fairness” means that the platform must guarantee a minimum selection fraction for each registered worker, so that the platform can avoid the scenario where some workers are over-recruited but some others might be under-recruited. For this problem, we devise a fairness-aware unknown worker recruitment algorithm. Finally, we demonstrate the performance of the proposed algorithms through extensive simulations on real-world traces

With the rapid development of the Internet of Things (IoT), massive high-speed data streams are produced every moment, making accurate size estimation a challenging task. Many sketches have been proposed to summarize real-time high-speed data streams and provide per-flow size estimations. However, sketches have to share the memory units to fit in limited on-chip space, inevitably introducing noises to all flows and resulting in over-estimation problems. Prior work adopts an average denoising strategy to remove the same noise from raw sketch estimations. However, they overlook that the noise distribution is highly skewed, leading to inaccurate results for most flows. This paper proposes an efficient Adaptive Noise Correction (ANC) framework, which analyzes the noise of each flow on a case-by-case basis and provides accurate size estimations. The key of our design is to build an ML model to predict a weight coefficient that indicates the noises in raw estimations, which is conducted for each flow by analyzing the neighbor flows whose memory units overlap with the given flow. Then we introduce a novel Probabilistic Cold Filter to block the tiny flows and assist in noise correction. Experimental results based on real Internet traces show that our framework can effectively remove the noises for different sketches, showing better estimation accuracy than the state-of-the-art.

Online anomalous taxi trajectory detection, which identifies anomalies from ongoing taxi trajectories, has become an important and fundamental concern in many real-world applications. Most of the existing studies define the anomalous trajectories as the ones deviating from the majority of routes or showing abnormal driving time and distance at the same time. However, due to the complexity of road conditions and the variety of passenger preferences, those methods have large false-positive rates, i.e., reporting many normal routes as anomalies. A high false-positive rate is harmful since false alarms will 1) bring unnecessary panic to passengers, 2) cause fiscally punishments to normal drivers, and 3) wastes human resource to deal with drivers' complaints. To this end, this paper proposes an online anomalous trajectory detection method, namely multidimensional criteria based anomalous trajectory (MCAT), to identify anomalous trajectories online. It judges anomalies by considering multidimensional criteria (similarity, time, distance) at the same time, reducing the false positives without sacrificing false negative rates. We evaluate the proposed method based on the real-world taxi data collected from Shanghai, China. The experimental results demonstrate that our method can outperform state-of-the-art methods in terms of accuracy, false-negative rate, and false-positive rate.

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

The multi-armed bandit (MAB) model has been deeply studied to solve many online learning problems, such as rate allocation in communication networks, Ad recommendation in social networks, etc. In an MAB model, given N arms whose rewards are unknown in advance, the player selects exactly one arm in each round, and his goal is to maximize the cumulative rewards over a fixed horizon. In this paper, we study the budget-constrained auction-based combinatorial multi-armed bandit mechanism with strategic arms, where the player can select K (<; N) arms in a round and pulling each arm has a unique cost. In addition, each arm might strategically report its cost in the auction. To this end, we combine the upper confidence bound (UCB) with auction to define the UCB-based rewards and then devise an auction-based UCB algorithm (called AUCB). In each round, AUCB selects the top K arms according to the ratios of UCB-based rewards to bids and further determines the critical payment for each arm. For AUCB, we derive an upper bound on regret and prove the truthfulness, individual rationality, and computational efficiency. Extensive simulations show that the rewards achieved by AUCB are at least 12.49% higher than those of state-of-the-art algorithms.

Currently, the blockchain, as a key enabling technology of digital currency, has attracted lots of attention from both industry and academia. The blockchain mining process requires high computing power to solve a Proof-of-Work (PoW) puzzle, which is hard to implement on users’ mobile devices. So these miners may leverage the resources of the edge/cloud service providers (ESPs/CSP) to calculate the PoW puzzle. The existing edge-assisted blockchain networks simply assumed that all ESPs have a uniform propagation delay, which is not realistic. In this paper, we consider a more practical scene where ESPs with distributed geographic locations have diverse propagation delays when supporting the computation of the PoW puzzle. Additionally, the blockchain mining process generally involves the complicated competition and game among these ESPs and miners. Each ESP focuses on how to determine his resource price and to select the requests from the miners, so that he can maximize his utility. According to the set resource price, each miner concentrates on scheduling his resource requests for each ESP to maximize his individual utility which depends on ESPs’ resource price and propagation delays. We model such a resource pricing and scheduling problem as a multi-leader multi-follower Stackelberg game and aim at finding the joint maximization of the utilities of each ESP and each individual miner. We prove the existence and uniqueness of the Stackelberg equilibrium (SE) and meanwhile propose an algorithm to achieve the corresponding SE. Finally, extensive simulations are conducted to verify the significant performance of the proposed solution.

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

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

This paper concentrates on the issue of detecting persistent elements of anomalous flows in a distributed monitoring system, which has many applications in detecting cyber-attacks, forecasting influenza, analyzing search keywords, and etc. However, only a few studies consider the anomalous flow detection problem in distributed systems. Meanwhile, most of the existing studies on persistent element detection problem in distributed systems assume that there is only one flow in the data stream, which is not always true in practice. In this paper, we combine the problems of anomalous flow detection and persistent elements finding, and propose an efficient mechanism to find the t-persistent elements of p-anomalous flows from element sets of numerous flows in the monitors of a distributed system, where t and p are system parameters that can be defined based on the application requirement. We adopt tight data structures such as bitmap and bloom filter to record the elements of different flows and filter out the elements that not in the t-persistent element set, which can help us reduce the communication overhead between monitors and the controller. We also give an analysis of how to get the optimal settings of these tight data structures that can minimize the total communication overhead. The experiment results based on real network traces show that the proposed mechanism achieves 76.1% and 69.2% reduction in communication overhead in comparison with a straightforward solution and a state-of-the-art solution based on coding cuckoo filter, respectively.

With the proliferation of mobile devices, mobile crowd sensing (MCS) has emerged as a new data collection paradigm, which allows the crowd to act as sensors and contribute their observations about entities. Unfortunately, users with varied skills and motivations may provide conflicting information for the same entity. Existing work solves this problem by estimating user reliability and inferring the correct observations (i.e., truths). However, these methods assume that users' expertise degrees are dependent on the truths, but ignore the finer clusters that exist even in the entities with the same truths. To capture users' fine-grained reliability on different entity clusters, we propose a novel Bayesian co-clustering truth discovery model for the task of observation aggregation. This model enables us to produce a more precise estimation while taking into account the entity clusters and the user clusters. Experiments on four real-world datasets reveal that our method outperforms the state-of-the-art approaches in terms of accuracy and F1-score.

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

Crowdsensing is a promising sensing paradigm to efficiently collect and monitor the physical world by using the embedded sensors in mobile devices. However, the observations (sensory data) submitted by mobile device users may not be reliable. For the same sensing task, users with different reliabilities may submit conflicting information. Thus, we need to estimate the truth based on the submitted observations. Temporal and spatial correlations among tasks are widely observed in crowdsensing applications. However, most of the existing truth discovery mechanisms assume that the tasks are independent, which is not suitable for all crowdsensing applications. To solve this problem, we propose an efficient truth discovery mechanism for crowdsensing tasks with temporal and spatial correlations. To improve the reliability of the estimated truth, we first filter the outliers based on the temporal correlations among tasks, then estimate the truth based on the weighted observations, and finally refine the estimated truth based on the spatial correlations among tasks. Our experiments on a real transportation dataset show the efficiency of the proposed mechanism.

Real-time road condition monitoring, especially of severe road damage, is critical for driving safety. In this work, we propose a crowdsensing-based pothole detection and measurement system, called CPDM, which can accurately measure the depth and length of detected potholes in urban roads. CPDM learns road surface information by collecting the sensor data from the smartphones belonging to the passing drivers and passengers. The proposed system can detect potholes by observing the vibration signal when the vehicle passes over the pothole, learn the vehicle parameters by fitting the underdamping vibration signal with stochastic gradient descent, and estimate the depth and length of the pothole. We have implemented a prototype system to prove the efficiency and adaptability of the proposed CPDM. The experimental results based on real traces show that CPDM has a high detection accuracy at different vehicle speeds.

Taxi recommender systems have remarkably benefited the taxi business by providing a sequence of pick-up points to reduce the passenger waiting time or the taxi cruising time. In reality, taxi drivers may have their preferred destination regions to avoid traffic jams or to execute arranged pickup orders. However, no prior work managed to maximize the profit of drivers and satisfy the requirements for destination regions at the same time. To tackle this challenge, we propose a PROfit Maximization recommendatIon SystEm (PROMISE) based on the inter-regional probability. In this paper, we first divide the city map into sub-regions and compute the mobility probability of passengers among pick-up points and sub-regions, namely inter-regional mobile probability. Then, we propose an efficient Driving Route Suggestion (DRS) algorithm based on inter-regional probability, which can maximize the profit of taxi drivers with designated destination regions. The experimental results based on the taxi traces collected from Shanghai, China, validate the effectiveness of the proposed recommender system.

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

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

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

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

Forecasting taxi demand is of great significance to the intelligent transportation systems in a smart city. Traditional demand prediction methods mostly considered about inter-regional traffic, events, activities, and weather, while they overlooked the influence of other travel modes, such as metro. In this paper, we propose a Deep Taxi-Metro Spatial-Temporal Network framework, namely TMST-Net, to model the spatiotemporal relationships between the taxi demand and the metro crowd flows. In detail, we apply residual neural networks to model temporal (current, day, and week) properties of the taxi demand in each area. For each feature, we apply residual convolutional units to handle the spatial properties of taxi demand. Likewise, we apply the same method to model the metro crowd flows. TMST-Net learns to assign different weights between taxi and metro by aggregating the output of the three residual neural networks and the external factors to forecast the final taxi demand for each area in the next timestamp. Experimental results on real taxi trajectory and the automatic fare collection (AFC) data in Shanghai show that our approach outperforms the state-of-the-art methods.

With the proliferation of various next generation wireless communication technologies, the smartphone has entered into our daily lives. Meanwhile, the excessive use of smartphone is seriously affecting our normal work and rest. In particular, the inappropriate way of using smartphone, especially when playing smartphone on bed in a lie-down posture, may do potential harm to our health. Thus, we propose a system called PosAla to encourage the smartphone users to use their phones in a correct posture. The proposed system adopts the supervised classifier to identify the harmful behavior, which is in a lie-down posture while using the smartphone, from a large number of sensor data generated during daily use of smartphone. Eight classification algorithms were tested in the experiments, and a large number of experiments have been conducted in terms of segment length and attribute selection. The extensive experimental results show that the recognition accuracy can reach 99.52%.

Crowdsourcing has shown its efficiency in obtaining information by harnessing the intelligence of a large crowd of human workers. It is essential to employ incentive mechanisms, typically auction, to motivate workers and collect sufficient data, since performing crowdsourcing tasks will always consume considerable resources, e.g., CPU or battery resource. To this end, we focus on the problem of heterogeneous task allocation with budget constraint in the crowdsourcing systems and propose a truthful auction mechanism which can maximize the profit of the task requester. In this paper, we first prove the NP-hardness of the studied problem and design a near-optimal task allocation mechanism with partial enumeration which can maximize the profit of the requester. Then, we judiciously design a bid-independent payment calculation mechanism to ensure the truthfulness of the participants. Finally, we prove that the proposed crowdsourcing task auction mechanism can achieve truthfulness and individual rationality. The extensive simulation results also corroborate with our theoretical analysis.

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

With the advent of virtualization technologies, cloud computing resource allocation issue plays an important role. However, the existing studies have not fully considered the heterogeneous demands from different cloud tenants. To tackle this, we design a more flexible cloud resource allocation mechanism which can maximize the profit of the cloud provider and support three general types of resource requirements from the cloud tenants. In this work, the jobs from tenants will bid for the usage of VMs in 3 types: 1) fixed time intervals, 2) time window intervals and 3) Time window slice intervals. We proved that the proposed approximation allocation mechanism has an approximation factor which approaches 1.58 when cmcloses to infinity.

Crowdsensing is regarded as an efficient way to collect a large number of sensing data by using sensor-equipped mobile phones. Most of the existing studies, which concentrate on the crowdsensing task assignment issue, often assume that there is only one data consumer in the system. Obviously, there may exist multiple data consumers in one real crowdsensing system, thus the previous works based on the single data consumer assumption may have many limitations. To tackle this challenge, we mainly focus on the crowdsensing task assignment problem with multiple data consumers, and propose an auction mechanism which can achieve max-min fairness. We first design an approximation transaction set construction mechanism, which can maximize the minimum utilities of data consumers. Then, a second- price-like winner determination and payment calculation mechanism is proposed to ensure the truthfulness. Finally, we prove that the proposed mechanism can achieve the essential economic properties, such as truthfulness, individual rationality and budget balance. The evaluation results corroborate our theoretical analysis, and further indicate that the proposed mechanism is efficient.

Relay assignment significantly affects the performance of the cooperative communication, which is an emerging technology for the future mobile system. Previous studies in this area have mostly focused on assigning a dedicated relay to each source-destination pair for one-to-one (121) traffic. However, many-to-one (M21) traffic, which is also common in many situations (for example, several users associate with one access point in a wireless access network such as a WLAN), hasn't been well studied. This paper addresses the shared relay assignment (SRA) problem for M21 traffic. We formulate two new optimization problems: one is to maximize the minimum throughput among all the sources (hereafter called M21-SRA-MMT), and the other is to maximize the total throughput over all the sources while maintaining some degree of fairness (hereafter called M21-SRA-MTT). As the optimal solutions to the two problems are hard to find, we propose two approximation algorithms whose performance factors are 5.828 and 3, respectively, based on the rounding mechanism. Extensive simulation results show that our algorithms for M21-SRA-MMTcan significantly improve the minimum throughput compared with existing algorithms, while our algorithm for M21-SRA-MTTcan achieve the close-to-optimal performance.

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

Many spectrum auction mechanisms have been proposed for spectrum allocation problem, and unfortunately, few of them protect the bid privacy of bidders and achieve good social efficiency. In this paper, we propose PPS, a Privacy Preserving Strategyproof spectrum auction framework. We design two schemes based on PPS separately for 1) the single-unit auction model (SUA), where only single channel will be sold in the spectrum market; and 2) the multi-unit auction model (MUA), where the primary user subleases multi-unit channels to the secondary users and each of the secondary users wants to access multi-unit channels either. Since the social efficiency maximization problem is NP-hard in both auction models, we present allocation mechanisms with approximation factors of (1 + ε) and 32 separately for SUA and MUA, and further judiciously design strategyproof auction mechanisms with privacy preserving based on them. Our extensive evaluations show that our mechanisms achieve good social efficiency and with low computation and communication overhead.

Virtual multi-input multi-output (MIMO) or vMIMO is becoming an attractive technology to achieve spatial diversity in wireless networks without using additional antennas, and to reduce power consumption by cooperation among multiple nodes. As data gathering is one of the most important operations in many sensor network applications, this paper studies energy-efficient data gathering in wireless sensor networks using vMIMO. We define the joint vMIMO and data gathering (vMDG) problem, which is NP-hard. We also propose a distributed method called D-vMDG as an approximation algorithm. This algorithm first constructs a tree-like topology by taking the unique features of vMIMO into account. Then, an energy-efficient routing protocol based on dynamic programming is proposed for each node on the constructed topology. Our theoretical analysis shows that D-vMDG can achieve an approximation ratio of O(1). Our simulations show that D-vMDG decreases the energy consumption by 81 and 36 percent compared to the well-known MDT [26] and MIMO-LEACH [19] algorithms respectively.

Relay assignment significantly affects the performance of cooperative communications. Previous studies in this area have mostly focused on assigning a dedicated relay to each source-destination pair for one-to-one (121) traffic. On the other hand, many-to-one (M21) traffic, which is also common in many situations (for example, several users associate with one access point in a wireless access network such as a WLAN), hasn't been well studied. This paper addresses the shared relay assignment (SRA) problem for M21 traffic. We formulate two new optimization problems: one is to maximize the minimum throughput among all the sources (hereafter called M21-SRA-MMT), and the other is to maximize the total throughput over all the sources while maintaining some degree of fairness (hereafter called M21-SRA-MTT). As both of these problems are NP-hard, we propose two approximation algorithms whose performance factors are 5.828 and 3, respectively, based on the rounding mechanism. Extensive simulation results show that our algorithm for M21-SRA-MMT can significantly improve the minimum throughput compared with existing algorithms, while our algorithm for M21-SRA-MTT can achieve the close-to-optimal performance.

In this work, we study spectrum auction problem where each spectrum usage request has spatial, temporal, and spectral features. After receiving bid requests from secondary users, and possibly reserve price from primary users, our goal is to design truthful mechanisms that will either optimize the social efficiency or optimize the revenue of the primary user. As computing an optimal conflict-free spectrum allocation is an NP-hard problem, in this work, we design near optimal spectrum allocation mechanisms separately based on the techniques: derandomized allocation from integer programming formulation, and its linear programming (LP) relaxation. We theoretically prove that 1) our derandomized allocation methods are monotone, thus, implying truthful auction mechanisms; 2) our derandomized allocation methods can achieve a social efficiency or a revenue that is at least $1-\frac{1}{e}$ times of the optimal respectively; Our extensive simulation results corroborate our theoretical analysis.

Spectrum auctions motivate existing spectrum owners (as sellers) to lease their selected idle channels to new spectrum users (as buyers) who need the spectrum desperately. The most significant requirement is how to make the auctions economic-robust (truthful in particular) while enabling spectrum reuse. Furthermore, in practice, both sellers and buyers would require to trade multiple channels at one time, while guaranteeing their individual profitability. Unfortunately, existing designs can not meet all these requirements simultaneously. We address these requirements by proposing True-MCSA, a framework for truthful double multi-channel spectrum auctions. True-MCSA introduces novel virtual buyer group (VBG) splitting and bidding algorithms, and applies a proper winner determination and pricing mechanism to achieve truthfulness and other economic properties, meanwhile successfully dealing with multi-channel requests from both buyers and sellers and improving spectrum utilization. Our experiments show that the auction efficiency is impacted by the economic factors with efficiency degradations within 30%, under different settings. Furthermore, the experimental results indicate that we can improve the auction efficiency by choosing a proper bidding algorithm and using a positive base bid. True-MCSA makes an important contribution on enabling spectrum reuse to improve auction efficiency in multi-channel cases.

Virtual multi-input-multi-output (or vMIMO) communication is a promising technology to improve the spatial diversity of wireless networks. Using this mechanism, multiple single-antenna nodes can coordinate their transmissions and receptions so as to reduce power consumption. This paper studies the problem of constructing an energy-efficient topology in wireless sensor networks using vMIMO communication. We first define the problem involving joint optimization of vMIMO, partner selection and topology control. As this problem is NP-Complete, a distributed and heuristic algorithm, called vMIMO topology control (VMTC), is proposed to solve this problem. The algorithm uses an improved binary searching method to obtain an initial power assignment. A local competition method is then adopted to implement the partner selection. At last, we reduce the power consumption of each node by using efficient vMIMO modes. Our theoretical analysis show that this algorithm can achieve an approximate performance of O(1). Our simulations show that VMTC helps to decrease the power consumptions by about 32% compared to the existing algorithms.