Multicast-Based Weight Inference in General Network Topologies

Yilei Lin, Ting He, Shiqiang Wang, Kevin S. Chan, Stephen PasterisICC 2019 · OpenReview

Abstract

Network topology plays an important role in many network operations. However, it is very difficult to obtain the topology of public networks due to the lack of internal cooperation. Network tomography provides a powerful solution that can infer the network routing topology from end-to-end measurements. Existing solutions all assume that routes from a single source form a tree. However, with the rapid deployment of Software Defined Networking (SDN) and Network Function Virtualization (NFV), the routing paths in modern networks are becoming more complex. To address this problem, we propose a novel inference problem, called the weight inference problem, which infers the finest-granularity information from end-to-end measurements on general routing paths in general topologies. Our measurements are based on emulated multicast probes with a controllable “width”. We show that the problem has a unique solution when the multicast width is unconstrained; otherwise, we show that the problem can be treated as a sparse approximation problem, which allows us to apply variations of the pursuit algorithms. Simulations based on real network topologies show that our solution significantly outperforms a state-of-the-art network tomography algorithm, and increasing the width of multicast substantially improves the inference accuracy.

Introduction

Effective network management requires accurate knowledge of internal link performance. However, for many public networks, internal data is inaccessible or obfuscated for security. Network tomography has traditionally addressed this by using end-to-end measurements to infer internal states. A significant limitation of existing tomography methods is the assumption that routing paths from a single source form a simple tree structure.

Modern network paradigms, such as Software Defined Networking (SDN) and Network Function Virtualization (NFV), break this assumption. In these environments, packets often follow overlapping, non-tree paths or are steered through complex service chains. This paper introduces a weight inference method designed for these general, non-tree topologies.

Methodology: The Weight Inference Problem

The core of the proposed approach is the Weight Inference Problem. Since it is often mathematically impossible to determine the weight of every individual physical link from external measurements, the researchers target the "finest granularity" achievable: Category Weights. A category represents a set of edges shared by the same set of measurement paths.

Illustration of the weight inference problem, showing ground truth topology, edge categories, and the resulting linear system for weights.

To solve this, the authors utilize:

  • k-casts: Emulated multicast probes where $k$ unicast packets are sent back-to-back to ensure they experience nearly identical network conditions.
  • Linear Modeling: The relationship between measured path performance (cast weights $\phi$) and internal category weights ($w$) is modeled as a linear system $D \cdot w = \phi$.
  • Sparse Approximation: In scenarios where not all path combinations can be probed, the system is underdetermined. The researchers apply the principle of parsimony, assuming the simplest network configuration that explains the data is most likely. They adapt greedy algorithms, specifically non-negative Matching Pursuit (nMP) and non-negative Orthogonal Matching Pursuit (nOMP), to find these sparse solutions.

Experimental Results

The methodology was validated using real-world topologies from the Rocketfuel project (specifically AS6461). The researchers simulated complex service-chain routing and compared their nOMP algorithm against Rooted Neighbor-Joining (RNJ), a state-of-the-art tree-based tomography algorithm.

Measurement error for cast weights and inference error for category weights as a function of the number of probes and multicast width k.

Key findings include:

  • The Power of Multicast Width: Increasing the width ($k$) of the multicast probe significantly improves accuracy. As shown in the figures, while measurement error decreases with more probes, the inference error for $w$ remains high if $k$ is too low. A higher $k$ fundamentally changes the mathematical properties of the problem, moving it toward a unique solution.
  • Superiority over Tree-Based Methods: The nOMP algorithm consistently outperformed RNJ, which struggled to account for the non-tree categories present in modern topologies.
  • Computational Efficiency: While standard optimization tools like Simplex provide accurate results, their running time scales poorly. The pursuit algorithms (nMP/nOMP) achieved comparable accuracy with significantly lower computational overhead, making them more suitable for real-time network monitoring.

Conclusion

By reframing network tomography as a sparse approximation problem and utilizing emulated multicast probes, this research provides a robust framework for monitoring modern, complex networks. The results demonstrate that the "width" of measurement probes is a critical factor in overcoming the limitations of traditional tree-based inference. Future work will focus on scaling these methods to even larger path sets and addressing potential correlations in link losses.

Summary updated

Abstract

Network topology plays an important role in many network operations. However, it is very difficult to obtain the topology of public networks due to the lack of internal cooperation. Network tomography provides a powerful solution that can infer the network routing topology from end-to-end measurements. Existing solutions all assume that routes from a single source form a tree. However, with the rapid deployment of Software Defined Networking (SDN) and Network Function Virtualization (NFV), the routing paths in modern networks are becoming more complex. To address this problem, we propose a novel inference problem, called the weight inference problem, which infers the finest-granularity information from end-to-end measurements on general routing paths in general topologies. Our measurements are based on emulated multicast probes with a controllable “width”. We show that the problem has a unique solution when the multicast width is unconstrained; otherwise, we show that the problem can be treated as a sparse approximation problem, which allows us to apply variations of the pursuit algorithms. Simulations based on real network topologies show that our solution significantly outperforms a state-of-the-art network tomography algorithm, and increasing the width of multicast substantially improves the inference accuracy.
BibTeX
@inproceedings{lin2019multicast,
  author = {Yilei Lin and Ting He and Shiqiang Wang and Kevin S. Chan and Stephen Pasteris},
  title = {{Multicast-Based Weight Inference in General Network Topologies}},
  booktitle = {ICC},
  year = {2019},
  url = {https://openreview.net/forum?id=VwBf_yPmDC},
}
Figure