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.

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.

This paper delves into the challenge of maintaining connectivity in adversarial networks, focusing on the preservation of essential links to prevent the disintegration of network components under attack. Unlike previous approaches that assume a stable and homogeneous network topology, this study introduces a more realistic model that incorporates both link uncertainty and heterogeneity. Link uncertainty necessitates additional probing to confirm link existence, while heterogeneity reflects the varying resilience of links against attacks. We model the network as a random graph where each link is defined by its existence probability, probing cost, and resilience. The primary objective is to devise a defensive strategy that maximizes the expected size of the largest connected component at the end of an adversarial process while minimizing the probing cost, irrespective of the attack patterns employed. We begin by establishing the NP-hardness of the problem and then introduce an optimal defensive strategy based on dynamic programming. Due to the high computational cost of achieving optimality, we also develop two approximate strategies that offer efficient solutions within polynomial time. The first is a heuristic method that assesses link importance across three heterogeneous subnetworks, and the second is an adaptive minimax policy designed to minimize the defender’s potential worst-case loss, with guaranteed performance. Through extensive testing on both synthetic and real-world datasets across various attack scenarios, our strategies demonstrate significant advantages over existing methods.

This paper studies connectivity maintenance in uncertain networks under adversarial attack, where a defender conceals crucial links to prevent the largest connected component from being decomposed by an attacker. In contrast with its static counterpart, connectivity maintenance in uncertain networks involves additional probing on links to determine their existence. Therefore, by modeling an uncertain network as a random graph with each link associated with an existence probability and a probing cost, our goal is to design a defensive strategy for link selection that maximizes the expected size of the largest remaining connected component with the minimum expected probing cost, and moreover, the strategy should be independent of the attacking patterns. To this end, we first unravel the computational complexity of the problem by proving its NP-hardness, and then propose optimal defensive strategies based on dynamic programming and multi-objective optimization. Due to the prohibitive computational cost of optimality, two approximate defensive strategies are further designed to pursue decent performance with quasilinear complexity, in which the first one is a heuristic approach that quantifies the link vulnerability through an analogy from the degree centrality of a vertex in static networks to the connectivity weight of a link in uncertain networks, and the second one is an adaptive greedy policy incorporating the minimax rule from game theory, which minimizes the possible loss suffered by the defender in a worst-case scenario and has a constant approximation ratio. Extensive experiments on both synthetic and real-world network datasets under diverse attacking patterns demonstrate the superiority of the proposed strategies over baselines.

This article studies time-sensitive multicast in wireless sensor networks (WSNs) with link uncertainty, where information from the source needs to be delivered to multiple receivers within an imposed delay constraint. Prior art on static WSNs minimizes the multicast delay via the construction of a multicast tree that approximates the Steiner tree in length, which, however, may be invalidated by the time-varying network topology of WSNs with uncertain link states. Moreover, for multicast in WSNs with link uncertainty, the possible link failure necessitates a suitable measurement of the uncertain communication distance and calls for the performance guarantee in both delay and delivery ratio. In this work, by modeling a WSN as a random graph with each link associated with a transmission probability, we propose FlowerCast, an efficient multicast scheme, to jointly minimize the expected multicast delay and to maximize the expected delivery ratio of multicast under delay constraint. The core of FlowerCast is to quantify the uncertain communication distance by the expected transmission delay of a time-varying path, based on which a delay-optimal multicast tree is constructed in accordance with the directionality of delay. Candidate paths with a high expected delivery ratio and low expected delay are then selected in a distributed manner to conditionally connect adjacent multicast members and thus transform the multicast tree into a multicast flower. Despite the NP-hardness of optimal candidate paths’ addition, the transformation with the highest expected delivery ratio of multicast under delay constraint can be guaranteed through a pseudo-polynomial time derandomization-based greedy approach. We further demonstrate the time and energy efficiency of FlowerCast through asymptotic analysis. To make full use of the possible overlapping links in a multicast flower, a hybrid routing strategy is presented to wisely switch between sequential routing and synchronous routing for extra enhancement of the multicast performance. Extensive experiments on various datasets verify the superiority of FlowerCast and hybrid routing over baselines and indicate their wide applicability to practical scenarios.

Social network de-anonymization, which refers to re-identifying users by mapping an anonymized network to a correlated real-name network, is an important problem in network science that has received intensive study. Although different de-anonymization algorithms have been proposed, the performance limit of any algorithm on a de-anonymization problem remains less explored. In this paper, we investigate the Optimal De-Anonymization Yield (ODAY), i.e., the maximum extent to which the network can be de-anonymized, of a given de-anonymization problem. Specifically, due to the uncertainty of the true mapping, we define ODAY as the maximum expected number of correctly mapped nodes, and propose general approaches for its quantification in general networks. Therefore, ODAY can be viewed as a quantitative and non-asymptotic concretization of the concept of network de-anonymizability, which is mostly investigated in an asymptotic manner in prior art. Inspired by the effect of network symmetry on the de-anonymizability, we show that for a graph pair with arbitrary topologies, ODAY equals the maximum diagonal sum of a matching probability matrix generated from graph homomorphisms. Due to the exponential complexity of enumerating all the possible homomorphisms, we further obtain an upper bound of ODAY by counting the orbits of each of the two graphs, which significantly reduces the computational cost. Two case studies apply our general findings on symmetry and ODAY to specific network models, and a sampling-based algorithm framework is proposed for ODAY calculation in practice. Extensive experiments are performed to validate our findings. To the best of our knowledge, this work is the first effort that quantifies the de-anonymizability of general networks in a non-asymptotic manner from the perspective of network symmetry, and thus sheds light on privacy enhancement for social network design.

This paper studies the problem of connectivity maintenance in adversarial uncertain networks, where a defender prevents the largest connected component from being decomposed by an attacker. In contrast with its deterministic counterpart, connectivity maintenance in an uncertain network involves additional testing on edges to determine their existence. To this end, by modeling a general uncertain network as a random graph with each edge associated with an existence probability and a testing cost, our goal is to design a general adaptive defensive strategy to maximize the expected size of the largest remaining connected component with minimum expected testing cost and, moreover, the strategy should be independent of the attacking patterns. The computational complexity of the connectivity maintenance problem is unraveled by proving its NP-hardness. To accurately tackle the problem, based on dynamic programming we first propose an optimal defensive strategy for a specific class of uncertain networks with uniform testing costs. Thereafter multi-objective optimization is adopted to generalize the optimal strategy for general uncertain networks through weighted sum of normalized size and cost. Due to the prohibitive price of an optimal strategy, two approximate defensive strategies are further designed to pursue decent performance with quasilinear complexity. We first derive a heuristic approach by quantifying the edge vulnerability through an analogy from the degree centrality in deterministic networks to the probability degree and connectivity weight in uncertain networks. For performance guarantee, we then devise an adaptive greedy policy incorporating the minimax rule from game theory, which minimizes the possible loss suffered by the defender in a worst-case scenario caused by the attacker and has an approximation ratio of (1 − 1/e). Extensive experiments on both synthetic and real-world network datasets under diverse attacking patterns demonstrate the superiority of the proposed strategies over baselines.

Mobile edge computing (MEC) has become a dominant technology in the upcoming era of the 5th generation mobile networks. By offloading tasks from mobile devices to edge clouds provided by cellular base stations, both energy consumption and end-to-end delay of mobile tasks can be reduced. In this paper, we aim to optimize the latency performance of TDMA-based MEC systems by joint allocation of computation and communication resource. Our goal is to minimize the maximal delay of all devices in the system. We first simplify the optimization problem and convert it into a convex one. Then we derive the closed-form expression for the optimal resource allocation strategy and investigate the relationship between uplink and downlink resource allocation. A subgradient algorithm is also developed to solve the joint resource allocation problem. Finally, numerical simulation results are shown to verify that our proposal can achieve a better performance compared with the traditional schemes.

This paper studied the complexities of the lines by fractal dimension, and described the evolution of the shape of the line according to the scales. By fractal dimension and the scale-dependent interval, the paper estimates the scale interval in which the geometric element keeps the fractal characters, so as to keep the geometric consistency during the process of the simplification.

Data sharing and integration are the inherent request of GIS. Data format conversion, data interoperability and direct data access are three ways of data sharing. All of them have many shortcomings respectively. So this paper proposed a method to build a WebGIS for sharing and integration of multi-source heterogeneous spatial data well. It introduced different data of multi-formats and several spatial database engines into a data access layer which established a unified data structure for screening the difference of different spatial data, and distributed spatial data using the GML, WMS and WFS standards developed by the OGC. Through those ways, it made heterogeneous spatial data homogeneous and enabled different data to have the unified and transparent structure to all users. The results show that the system share and integrate multi-source heterogeneous spatial effectively.