Estimating the frequency of items on the high-volume, fast data stream has been extensively studied in many areas, such as database and network measurement. Traditional sketches provide only coarse estimates under strict memory constraints. Although some learning-augmented methods have emerged recently, they typically rely on offline training with real frequencies or/and labels, which are often unavailable. Moreover, these methods suffer from slow update speeds, limiting their suitability for real-time processing despite offering only marginal accuracy improvements. To overcome these challenges, we propose UCL-sketch, a practical learning-based paradigm for per-key frequency estimation. Our design introduces two key innovations: (i) an online training mechanism based on equivalent learning that requires no ground truth (GT), and (ii) a highly scalable architecture leveraging logically structured estimation buckets to scale to real-world data stream. The UCL-sketch, which utilizes compressive sensing (CS), converges to an estimator that provably yields an error bound far lower than that of prior works, without sacrificing the speed of processing. Extensive experiments on both real-world and synthetic datasets demonstrate that our approach outperforms previously proposed approaches regarding per-key accuracy and distribution. Notably, under extremely tight memory budgets, its quality almost matches that of an (infeasible) omniscient oracle. Moreover, compared to the existing equation-based sketch, UCL-sketch achieves an average decoding speedup of nearly 500 times.

Given the high cost associated with directly measuring the Traffic Matrix (TM), researchers have devoted efforts to devising methods for estimating the complete TM from low-cost link loads by solving a set of heavily ill-posed linear equations. Today’s increasingly intricate networks present an even greater challenge: as adaptive and dynamically changing routing strategies are gradually replacing traditional fixed routing schemes, the routing matrix within these equations can no longer be deemed reliable. In our previous work, we pioneered a flow-based generative model, FlowTM, which estimated the TM by establishing an invertible correlation between the TM and link loads without relying on the routing matrix. We demonstrated that the missing information in the ill-posed equations can be decoupled from the TM and learned jointly with the invertible mapping. Considering that acquiring a complete training set for FlowTM is often impractical in many real-world networks, we further propose an enhanced model, FlowTM+, in this extended work. It incorporates anInspectormodule to mine deeper latent structures from the partially observed TM data and link load measurements. This new technique effectively compensates for unobservable information in the training data. Extensive experiments demonstrate that FlowTM improves the performance of the best baseline by 38%–58% when the actual routing matrix is absent. Remarkably, with only 2% of the training data, FlowTM+ achieves an estimation accuracy comparable to that of state-of-the-art baselines trained with full routing knowledge and complete training data.

With the growing need for a robust network backbone to ensure uninterrupted connectivity in the face of large-scale natural disasters, we introduce the Risk Zone-Diversified Network Design (RZDD) problem. This problem requires diverse paths between source-destination pairs to be risk zone-disjoint, preventing any single disaster from disrupting overall network connectivity. Unlike previous research, we propose an innovative cost framework that considers geographically overlapping links and long-term maintenance costs, providing a comprehensive approach to cost analysis. We prove the intractability of the RZDD problem and present the Risk Zone-Diversified Network Design Algorithm (RZDD-Algorithm). In small-scale networks with a single source-destination pair, our algorithm achieves optimal outcomes. Comparative analysis shows that our method reduces costs by an average of 24% compared to an SRLG algorithm that does not consider the preference of geographically overlapping links. For multiple pairs, our approach maintains a gap ratio within 4% and 7% of optimal solutions. Furthermore, experimental evaluations on large networks demonstrate reductions of 26% and 31% compared to the SRLG baseline for single pairs. We also showcase the efficiency of our method in designing large-scale networks with multiple pairs.

Since the inception of networking technology, network topology design has been a fundamental step for any interconnected system. This classical problem has diverse forms due to various design criteria. One special criterion, the ease of monitoring the network (termed as monitorability of the network), has recently attracted much attention in the era of Industry 4.0 when many complex private networks need to be built for new industrial services. This paper extends a quantitative measure of network monitorability, k-identifiability, based on which a new form of network topology design problem is formulated. We prove that this network design problem is intractable. To solve it, we systematically analyze the topological features that are helpful for reducing the complexity of network construction. Based on the analysis, we propose a dual-heuristic method that runs two heuristics in parallel and selects the better topology as the preliminary design result. Moreover, we design an integrated algorithm that reduces unnecessary edges as the final design result. We compare our dual-heuristic algorithm with the theoretical optimal solution in small-scale networks where the brute-force search is feasible. The results demonstrate the near-optimality of our method. We also illustrate the capability of our method in designing large-scale networks.

Inferring the bandwidth of internal links from the bandwidth of end-to-end paths, so-termed bandwidth tomography, is a long-standing open problem in the network tomography literature. The difficulty is due to the fact that no existing mathematical tool is directly applicable to solve the inverse problem with a set of$min$-equations. We systematically tackle this challenge by designing a polynomial-time algorithm that returns the exact bandwidth value for all identifiable links and the tightest error bound for unidentifiable links for a given set of measurement paths. When the measurement paths are not given in advance, we prove the hardness of building measurement paths that can be used for deriving the global tightest error bounds for unidentifiable links. Accordingly, we develop a reinforcement learning (RL) approach for measurement path construction, that utilizes the special knowledge in bandwidth tomography and integrates both offline training and online prediction. Evaluation results with real-world ISP topology as well as simulated networks demonstrate that compared to other path construction methods,RandomandDiversity Preferred, our RL-based path construction method can build measurement paths that result in a much smaller average error bound of the link bandwidth.

Inferring the bandwidth of internal links from the bandwidth of end-to-end paths, so-termed bandwidth tomography, is a long-standing open problem in the network tomography literature. The difficulty is due to the fact that no existing mathematical tool is directly applicable to solve the inverse problem with a set of min-equations. We systematically tackle this challenge by designing a polynomial-time algorithm that returns the exact bandwidth value for all identifiable links and the tightest error bound for unidentifiable links for a given set of measurement paths. When measurement paths are not given in advance, we prove the hardness of building measurement paths that can be used for deriving the global tightest error bounds for unidentifiable links. Accordingly, we develop a reinforcement learning (RL) approach for measurement path construction, that utilizes the special knowledge in bandwidth tomography and integrates both offline training and online prediction. Evaluation results with real-world ISP as well as simulated networks demonstrate that compared to other path construction methods, Random and Diversity Preferred, our RL-based path construction method can build measurement paths that result in much smaller average error bound of link bandwidth.

Network performance tomography uses a small number of strategically deployed monitors to infer the link performance in a large network. With the limited number of monitors, however, people usually can only estimate the bound rather than the exact values of network link performance. We aim at developing an effective solution to minimize the maximum error bound ($\mathcal{M}\mathcal{E}\mathcal{B}$) over all the links in the network. To achieve this, we develop a method that theoretically guarantees (1) the minimum number of monitors required to bring down the $\mathcal{M}\mathcal{E}\mathcal{B}$ over all unidentifiable links, and (2) the best places where these new monitors should be deployed. Using this method repeatedly, we can push down the $\mathcal{M}\mathcal{E}\mathcal{B}$ gradually until the desired level is reached. In addition, we develop a new sequential measurement technique that reduces the number of measurement paths and in the meantime guarantees the tightest link error bound. With extensive simulation over real-world network topology, we demonstrate the effectiveness and robustness of our solution in reducing the maximum link error bound with network performance tomography.

Network performance tomography infers performance metrics on internal network links with end-to-end measurements. Existing results in this domain are mainly Boolean-based, i.e., they check whether or not a link is identifiable, and return the exact value on identifiable links. If a link is not identifiable, the Boolean-based solution gives no performance result for the link. In this paper, we extend Boolean-based network tomography to bound-based network tomography where the lower and upper bounds are derived for unidentifiable links. We develop an efficient algorithm to obtain the tightest total error bound, and present a solution that can significantly reduce the total number of measurement paths required for deriving the tightest total error bound. Furthermore, we propose a method to deploy a new monitor such that the total error bound could be maximally reduced. Compared to the random monitor deployment and the monitor deployment that maximizes the total number of identifiable links, our monitor deployment method can lead to up to 15 and 2.4 times more reduction on total error bound, respectively.

Network performance tomography infers performance metrics on internal network links with end-to-end measurements. Existing results in this domain are mainly Boolean-based, i.e., they check whether or not a link is identifiable, and return the exact value on identifiable links. If a link is not identifiable, Boolean-based solution gives no performance result for the link. In this paper, we extend Boolean-based network tomography to bound-based network tomography where the lower and upper bounds are derived for unidentifiable links. We develop an efficient algorithm to obtain the tightest total error bound, and present a solution that can significantly reduce the total number of measurement paths required for deriving the tightest total error bound. Furthermore, we propose a method to deploy a new monitor over existing ones such that the total error bound could be maximally reduced. Compared to the random monitor deployment and the monitor deployment that maximizes the total number of identifiable links, our monitor deployment method can lead to up to 15 and 2.4 times more reduction on total error bound, respectively.

In the “network-as-a-service” paradigm, network operators have a strong need to know the metrics of critical paths running services to their users/tenants. However, it is usually prohibitive to directly measure the metrics of all such paths due to the measuring overhead. A practical solution is to use network tomography to infer the metrics of such paths based on observations from a small number of monitoring nodes. This problem is termed as path identifiability problem, a new problem that largely differs from existing link identifiability problems. we show that the new problem is harder than link identifiability problems, in the sense that fewer monitors are required for identifying the metrics of given paths than for identifying the metrics of links along the paths. To solve the problem, we develop sufficient and necessary conditions for the identifiability of a given set of interested paths, and design an efficient algorithm that deploys the minimum number of monitors. Experiments show a saving of up to 40% fewer monitors that guarantee the identifiability of a given set of paths.