This paper addresses the challenge of identifying super spreaders within large, high-speed data streams. In these streams, data is segmented into flows, with each flow's spread defined as the number of distinct items it contains. A super spreader is characterized as a flow with a notably large spread. Measuring flow spread requires counting any item at its first appearance and ignoring its subsequent duplicate appearances. Current compact solutions, known as sketches, are designed to fit within the constrained memory of online devices. However, existing sketches face accuracy challenges in spread tracking due to the substantial memory needed to remove the impact of duplicate appearances for measuring a single flow's spread—a problem that compounds with increasing flow counts. We propose a novel sketch-based solution to address these limitations. At its core, our approach features an innovative non-duplicate sampler that eliminates duplicate appearances of any item, enabling accurate flow spread calculation using simple counters. Combined with our exponential-weakening decay mechanism that emphasizes large flows, the solution significantly improves super spreader detection accuracy. We provide rigorous theoretical analysis of our method and validate its performance through trace-driven experiments. Results demonstrate that our approach statistically outperforms existing state-of-the-art solutions in super spreader identification. Moreover, it achieves the fastest super spreader restoration time and reduces bandwidth consumption by an order of magnitude during remote offline restoration.

Federated learning (FL) enables training AI models across distributed edge devices (i.e., workers) using local data, while facing challenges including communication resource constraints, edge heterogeneity, and non-IID data. Over-the-air computation (AirComp) has emerged as a promising technique to improve communication efficiency by leveraging the superposition property of a wireless multiple access channel (MAC) for model aggregation. However, over-the-air aggregation requires strict synchronization among edge devices, which is essentially incompatible with the asynchronous FL mechanisms often used to handle edge heterogeneity. To overcome this incompatibility, we propose Air-FedGA, a grouping-based asynchronous FL mechanism via AirComp, where workers are organized into groups for synchronized over-the-air aggregation within each group, while groups asynchronously communicate with the parameter server to update the global model. This design retains the communication efficiency of AirComp while addressing training inefficiency caused by edge heterogeneity. We provide a rigorous convergence analysis for Air-FedGA, theoretically quantifying how the convergence bound depends on several key factors, such as the maximum staleness, the degree of non-IID data among groups, and the AirComp aggregation mean squared error (MSE). Guided by these theoretical insights, we propose power control and worker grouping algorithms to minimize the convergence bound by jointly optimizing the AirComp aggregation MSE and the grouping strategy. We conduct experiments on classical models and datasets, and the results demonstrate that our proposed mechanism and algorithms can accelerate the model training by 1.83-$2.22\times $compared with the state-of-the-art solutions.

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

Deep learning (DL) has seen a growing dataset, an expanding model scale, and increasing applications in recent years. There is a notable trend of shifting DL training jobs from local computing units to powerful DL clusters built by cloud providers. These clusters allocate physical training nodes to DL jobs through a process referred to as multi-job placement. Existing multi-job placement strategies fail to achieve high efficiency in resource utilization, DL training, and robustness simultaneously, resulting in poor performance when resources are limited or when abnormalities occur in some devices. To tackle these challenges, we present CROP, an approach that performs efficient and robust multi-job placement in DL clusters. We formulate the efficient and robust multi-job placement problem as a non-linear program and prove its NP-hardness. To solve this problem, we present an effective submodular-based algorithm with a tight approximation factor of ($1-1/e$). We evaluate CROP on a small-scale testbed consisting of 8 physical GPUs and a large-scale simulation employing real-world job traces. Experimental results demonstrate that CROP achieves nearoptimal communication overhead while improving the training throughput of the DL cluster by up to$57.5\%$compared to state-of-the-art solutions.

Kubernetes is widely adopted by enterprises to enhance service availability for applications such as web services and large-scale model training, due to its advantages in managing containerized applications. As service demands increase, a single Kubernetes cluster often becomes insufficient, leading to the trend of using multiple clusters to improve service scalability. However, achieving efficient cross-cluster communication poses significant challenges due to the need for low latency, high throughput, and strong robustness. Existing methods for cross-cluster communication either employ a centralized control plane, which becomes a communication bottleneck, or use numerous service-bound proxies, leading to increased management complexity and possibly compromised robustness in cross-cluster communication.

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.

Distributed training has emerged as a critical application in clusters due to the widespread adoption of AI technology across various domains. However, as distributed training continues to advance, it has become increasingly time-consuming. To address this challenge, researchers have explored leveraging In-Network Aggregation (INA) to expedite distributed model training. Specifically, by harnessing programmable hardware, such as Intel Tofino switches, INA can aggregate gradients within the network, thereby reducing the amount of gradient transmission and accelerating distributed training. However, previous works assume fixed routing selection and batch size, ignoring their impact on model convergence and resulting in extended completion time. To bridge this gap, we propose InGo, a pioneering approach that considers both in-network aggregation routing and batch size adjustment, and provide the rigorous convergence analysis. Then, we formally define the problem of in-network aggregation routing with batch size adjustment, and present an efficient algorithm with bounded approximation factors to solve this problem. Through extensive experiments on both physical platforms and simulated environments, we demonstrate that InGo significantly reduces the completion time by 25.2%-74.7% compared to state-of-the-art solutions.

Facing the huge volume of traffic and intensive traffic dynamics, the traditional datacenter architectures are behind the curve due to the fixed topology and the demand-oblivious nature. Driven by the traffic pattern, the reconfigurable technologies, like optical circuit switches (OCSes), are a promising alternative to further improve throughput when facing traffic dynamics, thanks to the high bandwidth and low reconfiguration time. However, existing works on OCSes are relatively elementary. Some of previous works only deploy single OCS which cannot adapt to large-scale datacenters, while others either cannot guarantee near-optimality or overlook practical issues like limited fiber capacity. These solutions may cause low throughput and long reconfiguration time, resulting in poor QoS. In this paper, we present Leaf to maximize throughput thus to further improve QoS, by deploying multiple OCSes to carry traffic in a cooperation manner. Furthermore, we also show its efficient reconfiguration ability and near-optimality. The formulated problem is a new k-weight limited matching problem and is proven to be N P-hard, which can be solved by a new proposed approximation algorithm with bounded approximation ratio. To evaluate our proposed solution, simulation experiments are conducted with both real-world and synthetic datasets. Compared with state-of-the-arts works, Leaf can improve throughput by 42.16%−68.92%, and reduce runnning time by 68.87%−78.72%.

This paper addresses the challenge of identifying super spreaders within large, high-speed data streams. In these streams, data is segmented into flows, with each flow's spread defined as the number of distinct items it contains. A super spreader is characterized as a flow with a notably large spread. Current compact solutions, known as sketches, are designed to fit within the constrained memory of online devices. However, they struggle to accurately track the spread of all flows due to the substantial memory requirement for monitoring a single flow --- a problem exacerbated when numerous flows are involved. To overcome these limitations, this study proposes a more precise sketch-based approach. Our solution introduces an innovative non-duplicate sampler that effectively eliminates duplicates, allowing for accurate post-sampling count of flow spread using only counters. Additionally, it incorporates an exponential-weakening decay technique to highlight large flows, markedly enhancing the accuracy of super spreader identification. We offer a comprehensive theoretical analysis of our method. Trace-driven experiments validate that our approach statistically surpasses existing state-of-the-art solutions in identifying super spreaders. It also demonstrates the lowest time required to restore super spreaders and significantly reduces bandwidth consumption by an order of magnitude when offline restoration is conducted remotely.

Graph Neural Networks (GNNs) have achieved impressive performance in many tasks on graph data. Recent studies show that they are vulnerable to adversarial attacks. Deliberate and unnoticeable perturbations on topology structure could render them near-useless in applications. How to design effective methods to improve the robustness of GNNs is a crucial problem. To solve this problem, some works attempt to design more robust GNN models, while others attempt to remove perturbations from the poisoned graph. Different from the previous works, this paper proposes a general framework termed asGraphReshapeto enhance the robustness of GNNs via directly correcting the shifted classification boundary of GNN models in the presence of adversarial attacks.GraphReshapeconsists of two modules:locating tractive nodesthat could correct GNNs andreshaping local structureto improve their representations in the latent space. Extensive experiments on four real-world datasets show thatGraphReshapeachieves significant performance gain compared with state-of-the-art baselines against different adversarial attacks.

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).

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

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

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

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

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

Human mobility prediction is of great importance for various applications such as smart transportation and personalized recommender systems. Although many traditional pattern-based methods and deep models ($e.g.,$ recurrent neural networks) based methods have been developed for this task, they essentially do not well cope with the sparsity and inaccuracy of trajectory data and the complicated high-order nature of the sequential dependency, which are typical challenges in mobility prediction. To solve the problems, this paper proposes a novel framework named G raph C onvolutional D ual-a ttentive N etworks (GCDAN), which consists of two modules: spatio-temporal embedding and trajectory encoder-decoder. The first module employs a bidirectional diffusion graph convolution to preserve the spatial dependency in the location embedding. The second module employs a dual-attentive mechanism based on a Sequence to Sequence architecture to effectively extract the long-range sequential dependency within a trajectory and the correlation between different trajectories for predictions. Extensive experiments on three real-world datasets show that GCDAN achieves significant performance gain compared with state-of-the-art baselines.

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

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

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

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

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

In recent years, more and more wireless networks support both 2.4GHz and 5GHz bands. However, in large-scale dual-band wireless networks, lack of understanding on the behavior and performance makes the network diagnosis and optimization extremely challenging. In this paper, we conduct a comprehensive measurement to characterize the behavior and performance in a large-scale dual-band wireless network (TD WLAN). We make several meaningful observations. (1) Although the 5GHz band outperforms the 2.4GHz band, 60% of devices tend to be associated with the 2.4GHz band. The device association behavior has a large impact on the performance. (2) Rogue and non-WiFi devices are prevalent, wherein hidden terminal interference increases the average loss rate by 8%, carrier sense interference increases the average WiFi latency by 45%, and RF interference further aggravates both packet loss and channel contention. (3) The dynamic channel assignment strategy is not always effective. On this basis, we propose a novel and easy-to-implement strategy to improve the wireless performance by intelligent band navigation and heuristic channel optimization. The actual deployment in TD WLAN shows the packet loss reduces by 40% on average and the WiFi latency for more than 60% of devices is below 5ms.

Anycast content delivery networks rely on the underlying routing to schedule clients to their nearby service nodes, which however is not natively aware of server load or path latency. Requests burst from some regions may cause overload and hurt user experience. This scenario demands quickly adjusting clients to other nearby servers with available capacity. However, state-of-the-art solutions do not work well. On one hand, native routing-based scheduling is not flexible and precise enough, which may cause cascading damage and interrupt ongoing sessions. On the other hand, centralized algorithm is vulnerable and not responsive due to high complexity. We propose a practical distributed hybrid load management model to solve load burst problem. First, the hybrid mechanism leverages flexible DNS-based redirection, which can schedule at per-request granularity without interrupting ongoing sessions. Second, the distributed model is responsive by reducing computation overhead and theoretically guarantees to converge to the optimal solution. Based on the model, we further propose an cooperative and two heuristic distributed algorithms. At last, using a measurement dataset, we demonstrate their effectiveness and scalability, and illustrate how to adapt them to different scenarios.

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

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

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

Graph neural networks (GNNs) have been successfully used to analyze non-Euclidean network data. Recently, there emerge a number of works to investigate the robustness of GNNs by adding adversarial noises into the graph topology, where gradient-based attacks are widely studied due to their inherent efficiency and high effectiveness. However, the gradient-based attacks often lead to sub-optimal results due to the discrete structure of graph data. To this end, we design a novel exploratory adversarial attack (termed as EpoAtk) to boost the gradient-based perturbations on graphs. The exploratory strategy in EpoAtk includes three phases, generation, evaluation and recombination, with the goal of sidesteping the possible misinformation that the maximal gradient provides. In experiments, EpoAtk is evaluated on benchmark datasets for the task of semi-supervised node classification in different attack settings. Experimental results demonstrate that the proposed method significantly outperforms the state-of-the-art attacks with the same attack budgets.

Graph Neural Networks (GNNs) have achieved remarkable performance in the task of the semi-supervised node classification. However, most existing models learn a deterministic classification function, which lack sufficient flexibility to explore better choices in the presence of kinds of imperfect observed data such as the scarce labeled nodes and noisy graph structure. To improve the rigidness and inflexibility of deterministic classification functions, this paper proposes a novel framework named Graph Stochastic Neural Networks (GSNN), which aims to model the uncertainty of the classification function by simultaneously learning a family of functions, i.e., a stochastic function. Specifically, we introduce a learnable graph neural network coupled with a high-dimensional latent variable to model the distribution of the classification function, and further adopt the amortised variational inference to approximate the intractable joint posterior for missing labels and the latent variable. By maximizing the lower-bound of the likelihood for observed node labels, the instantiated models can be trained in an end-to-end manner effectively. Extensive experiments on three real-world datasets show that GSNN achieves substantial performance gain in different scenarios compared with stat-of-the-art baselines.

Dynamic Host Configuration Protocol (DHCP) is widely used to dynamically assign IP addresses to users. However, due to little knowledge on the behavior and performance of DHCP, it is challenging to configure lease time and divide IP addresses for address pools properly in large-scale wireless networks. In this paper, we conduct the largest known measurement on the behavior and performance of DHCP in the wireless network of T University (TWLAN). We find the performance of DHCP is far from satisfactory: (1) The non-authenticated devices lead to a waste of 25% of addresses at the rush hour. (2) Address pool utilization varies greatly under the current address division strategy. (3) A device does not generate traffic for 67% of the lease time on average. Meanwhile, we observe devices of different locations and operating systems show diverse online patterns. A unified lease time setting could result in an inefficient usage of addresses. To address the problems, taking account of authentication information and online patterns, we propose a new leasing strategy. The results show it outperforms three state-of-the-art baselines and reduces the number of assigned addresses by 24% and the average total lease time by 17% without significantly increasing the DHCP server load. Besides, we further propose an adaptive address division strategy to balance the address utilization of pools, which can be deployed in parallel with the new leasing strategy and reduce the risk of address exhaustion.

Traffic measurement is very important for various applications, such as traffic engineering and attack detection, in software-defined networks. Due to limited resources (e.g., computing, memory) on SDN switches, sketches have been widely used for efficient traffic measurement. Meanwhile, multiple independent sketches are required for different application requirements, such as heavy hitter detection and flow size distribution estimation. To avoid the measurement redundancy, we configure which sketch(es) will measure flow on each switch. If traffic measurement is performed on each switch without considering network routing, due to traffic dynamics, it will cause massive measurement overhead on a switch, which may exceed the switch's computing capacity. In this paper, we study the joint optimization of flow routing and sketch configuration in SDNs. We formulate this problem as an integer linear programming and prove its NP-hardness. To solve this problem, we propose a rounding-based offline algorithm and a primal-dual-based online algorithm for different application scenarios. To deal with bursty traffic, we also design an adaptive sampling mechanism for high-fidelity traffic measurement. We formally analyze the approximation performance or competitive ratio of the proposed algorithms. The extensive simulation results show the high efficiency of our proposed algorithms. For example, the online algorithm can improve the network throughput 30% compared with the state-of-the-art.

Sketches have been widely used to record traffic statistics using sub-linear space data structure. Most sketches focus on the traffic estimation of elephant flows (i.e., heavy hitters) due to their importance to many network optimization tasks, e.g., traffic engineering and load balancing. In fact, the information of aggregate mice flows (e.g., all the mice flows with the same source IP) is also crucial to many security-associated tasks, e.g., DDoS detection and network scan detection. However, the previous solutions, e.g., measuring each individual flow or using multiple sketches for independent measurement tasks, will result in worse estimation error or higher computational overhead. To conquer the above disadvantages, we propose an accurate traffic measurement framework with multiple filters, called Sketchtree, to efficiently measure both elephant flows and aggregate mice flows. These filters in Sketchtree are organized in a hierarchical manner, and help to alleviate the hash collision and improve the measurement accuracy, as the number of flows through hierarchical filters in turn will be decreased gradually. We also design some mechanisms to improve the resource utilization efficiency. To validate our proposal, we have implemented Sketchtree and conducted experimental evaluation using real campus traffic traces. The experimental results show that Sketchtree can increase the processing speed by 100 percent, and reduce the measurement error by over 30 percent compared with state-of-the-art sketches.

As web traffic has already dominated Internet, massive web logs are being generated ceaselessly. It is essential and meaningful for operators to mine valuable information and knowledge from the log data. However, the state-less feature of HTTP and increasing dynamics and complexities of web services bring a challenge to web mining in web logs. To solve the problem, in this paper, we introduce Web Request Tree (WRT) to reconstruct users' web request behaviors from web logs with HTTP header information, which can be applied in many fields. Compared to previous related work, our method pays special attentions to modern technologies to handle cases caused by these technologies such as PJAX. We evaluate the feasibility of our method with a measurement study on referrer policies of Alexa top websites and results show that our method can achieve a high accuracy for most websites. We also conduct experiments on a real-world dataset collected from official websites of a top university in China. We find that a lot of abnormal requests exist in log data by analyzing WRT and WRT is rich in information that is valuable for operators to analyze user behaviors, detect anomalies, optimize performance and so on.

Anycast has been increasingly deployed for content delivery networks to map clients to their nearby replicas, which relies on the underlying routing. However, the simplicity of operation comes at cost of less precise client-mapping control. Although many works have measured anycast DNS, anycast CDNs, with different service goals and engineering, are still not fully understood. In this paper, we design novel methods and combine large-scale traceroute and HTTP measurement to evaluate the overall client-proximity and inefficient routing of the largest anycast CDN, Cloudflare. We find that 90% paths traverse only 2-4 ASes, which highlights its direct networks providers. By further identifying and characterizing direct providers at finer granularity of facilities, we quantitatively shows that Cloudflare unevenly uses few large transit providers to delivery the majority of contents. Inspired by the observations, we propose an anycast routing pathology and diagnosis methodology. Investigation reveals that few huge providers have outsized impact in that they are not only related to many inter-domain inflations, but also have path inflation inside their own networks, thus deserving priority focus when troubleshooting.

There are more and more structured traffic flows (a.k.a coflow) in today's data center networks. Completing a coflow is extremely important for various applications, e.g., MapReduce. To reduce the coflow completion time or CCT, one may increase the link capacity by applying advanced optical circuit switches in data center networks. Due to special features of optical circuit switches, both traffic scheduling and circuit scheduling will influence the CCT. However, previous solutions have some significant limitations: they consider either coflow scheduling, or circuit scheduling for only one optical circuit switch, which are both insufficient. In this paper, we study the integrated coflow and circuit scheduling (GCCS) problem with the objective to minimize the CCT, and prove its NP-hardness. We present an integrated algorithm which includes two steps, coflow scheduling and circuit scheduling, respectively. We also analyze that the proposed algorithm can achieve the approximation ratio O(h) in most practical situations, where h is the maximum number of ports among all lightpaths. Through large-scale simulations, we demonstrate that the integrated solution can significantly reduce the CCT by about 43-70 percent compared with the state-of-the-art coflow scheduler for optical networks.

Fraud detection is of great importance because fraudulent behaviors may mislead consumers or bring huge losses to enterprises. Due to the lockstep feature of fraudulent behaviors, fraud detection problem can be viewed as finding suspicious dense blocks in the attributed bipartite graph. In reality, existing attribute-based methods are not adversarially robust, because fraudsters can take some camouflage actions to cover their behavior attributes as normal. More importantly, existing structural information based methods only consider shallow topology structure, making their effectiveness sensitive to the density of suspicious blocks. In this paper, we propose a novel deep structure learning model named DeepFD to differentiate normal users and suspicious users. DeepFD can preserve the non-linear graph structure and user behavior information simultaneously. Experimental results on different types of datasets demonstrate that DeepFD outperforms the state-of-the-art baselines.

Dynamic Host Configuration Protocol (DHCP) is widely used to dynamically assign IP addresses. However, due to little knowledge on the behavior and performance of DHCP, it is challenging to configure a proper lease time in complicated wireless network. In this paper, we conduct the largest known measurement on the behavior and performance of DHCP based on the wireless network of T University (TWLAN). TWLAN has more than 59,000 users, 10,000 wireless access points and 130,000 IP addresses. We find the performance of DHCP is far from satisfactory: (1) The non-authenticated devices lead to a waste of 25% of IP addresses at the rush hour. (2) A device does not generate traffic for 67 % of the lease time on average. Meanwhile, we find devices of different locations and operating systems show diverse online patterns. A unified lease time setting could result in an inefficient utilization of addresses. To address the problems, taking account of authentication information and device online patterns, we propose a new leasing strategy. The results show it reduces the number of assigned addresses by 24 % and reduces the time during which an IP address is occupied by 17 % without sianificantly Increasing the DHCP server load.

In a software-defined network (SDN), statistics information is of vital importance for different applications, such as traffic engineering, flow rerouting, and attack detection. Since some resources, e.g., ternary content addressable memory, SRAM, and computing capacity, are often limited on SDN switches, traffic measurements based on flow tables or sampling become infeasible. In fact, sketches provide a promising building block for filling this void by monitoring every packet with fixed-size memory. Although many efficient sketches have been designed, our analysis shows that existing sketch-based measurement solutions may suffer from severe computing overhead on switches especially under high traffic load that significantly interferes with switch's basic functions, such as flow rule setup and modification. In this paper, we present CountMax, a lightweight and cooperative sketch for traffic measurement, which can achieve low-amortized processing overhead and tight estimation bounds, to track large flows in SDNs. We also discuss how to apply CountMax to support a variety of applications. We have implemented the proposed algorithm on our open switches. Testbed experiments and extensive simulation results show that CountMax consumes only 1/3-1/2 computing overhead and reduces the average estimation error by 20%-30%, compared with the existing solutions under the same memory size.

The worldwide distribution of IPv4 addresses is highly non-uniform. The factors that contribute to IPv4 address resources owned by a country remain unknown. In this paper, we systematically study the relationship between the number of allocated IPv4 addresses and 30 factors extracted from political, economic, ecological, social, and cultural dimensions. We observe that GDP has the largest influence on the number of IPv4 addresses while the influence of political factors is very weak. To further quantify the complex relationship among them, we fit data into a Decision Tree model. Based on the pruned model, we can extract precise rules that contribute to IPv4 address resources owned by a country. To the best of our knowledge, this is the first work to evaluate IPv4 address ownership by quantitative factors. Our work is helpful to better understand the network development of a country.

To explore the advantages of software defined network (SDN), while preserving the legacy networking systems, a natural deployment strategy is to deploy a hybrid SDN incrementally to improve the network performance. In this paper, we address two technical challenges: an incremental deployment strategy and a throughput-maximization routing, for deploying a hybrid network incrementally. For incremental deployment, we propose a heuristic algorithm for deploying a hybrid SDN under the budget constraint, and prove the approximate factor of 1- 1/e. For throughput-maximization routing, we apply a depth-first-search method and a randomized rounding mechanism to solve the multi-commodity h-splittable flow routing problem in a hybrid SDN, where h ≥ 1. We also prove that our method has approximation ratio O(1/log N), where N is the number of links in a hybrid SDN. We then show, by both analysis and simulations, that our algorithms can obtain significant performance gains and perform better than the theoretical worst-case bound. For example, our incremental deployment scheme helps to enhance the throughout about 40% compared with the previous deployment scheme by deploying a small number of SDN devices, and the proposed routing algorithm can improve the throughput about 31% compared with ECMP in hybrid networks.