TL;DR
This paper tackles the challenge of network performance monitoring when individual network links are not independent but can be correlated. The authors develop a theoretical framework and a practical algorithm to accurately infer link congestion probabilities even in the presence of these correlations, a significant advancement over previous methods that assumed link independence.
What Problem Does This Paper Address?
Network tomography is a powerful technique for inferring the characteristics of individual network links (like congestion or latency) by observing the behavior of end-to-end paths. This is crucial when direct measurement of every link is impractical. However, existing methods typically assume that the status of one link is independent of another. This assumption breaks down in real-world scenarios: for instance, links within the same local area network might share physical infrastructure or management, making them correlated. Similarly, links belonging to the same administrative domain could be correlated. Ignoring these correlations can lead to inaccurate monitoring. This paper addresses this gap by developing a method to perform network tomography when links are correlated, provided we have some knowledge about which links might be correlated.
Methods
The core of the paper lies in developing a mathematical model and a practical algorithm for network tomography under correlated link conditions.
- Formal Proof of Identifiability: The authors first formally prove that it's possible to identify the probability of congestion for each link, even when links are correlated, under specific assumptions. This involves defining "correlation sets" – groups of links that might be correlated with each other but not with links outside their set.
- Practical Algorithm: Building on the theoretical proof, they present an algorithm that computes these congestion probabilities. This algorithm leverages end-to-end path measurements and the known network topology, along with the defined correlation sets. It cleverly constructs a system of linear equations that can be solved to find the desired probabilities. A key aspect is how they form these equations using paths that don't involve correlated links to avoid introducing new unknowns.
- Assumptions: The work relies on four key assumptions:
- Stability: The network topology and paths remain constant during an experiment.
- Separability: A path is congested if and only if at least one of its links is congested.
- Stationarity: Link congestion behavior can be modeled as a stationary random process.
- Identifiability: Crucially, different correlation subsets must not be traversed by the exact same set of paths. This ensures that we can distinguish between the congestion behaviors of different correlated groups.
Datasets
The authors evaluate their algorithm using simulated data. They generate network topologies using:
- Brite topology generator: Used to create AS-level and router-level topologies, simulating administrative domains.
- PlanetLab topologies: Derived from actual traceroute measurements to mimic real-world network structures.
They do not introduce a new benchmark dataset but rather use these standard methods to generate diverse network scenarios for evaluation.
Key Insights and Ideas
- Correlation is the Norm, Not the Exception: The paper highlights that assuming link independence is often unrealistic and that correlated links are a common phenomenon in real networks.
- Knowledge of Correlation is Key: While perfect knowledge of correlation coefficients isn't required, knowing which links are potentially correlated is sufficient to enable accurate tomography. This is a significant relaxation of previous assumptions.
- A Clever Algorithmic Approach: The algorithm's ingenuity lies in its ability to form a solvable system of equations by strategically using paths that avoid correlated links, thereby isolating the unknowns related to individual link congestion.
- Identifiability is Achievable: The formal proof demonstrates that, under reasonable conditions, the congestion probabilities are indeed identifiable, even with correlated links.
Key Results
- Accuracy: The proposed "correlation algorithm" significantly outperforms an "independence algorithm" (which ignores correlations) across various scenarios, especially when links are highly correlated or when a substantial fraction of links are congested.
- Performance with Unidentifiable Links: Even when Assumption 4 (identifiability) is violated for some links (making their congestion probabilities unidentifiable), the proposed algorithm still performs well and better than the independence algorithm.
- Robustness to Unknown Correlations: The algorithm shows resilience even when there are unknown correlation patterns in the network, outperforming the independence algorithm which ignores all correlations. For example, when 10% of links are congested and half are affected by unknown correlations, the proposed method still yields accurate results.
Limitations and Future Work
- Assumption 4 Violation: The paper acknowledges that if Assumption 4 (identifiability) is violated for a significant portion of links, their congestion probabilities become unidentifiable. They suggest potential workarounds like altering the topology or treating unidentifiable links as uncorrelated (though this leads to inaccuracies).
- Practical Implementation: The authors are building a "PlanetLab Tomographer" to test their approach on real-world networks and compare scenarios with and without assumed link correlations.
- Determining Congested Links per Snapshot: While the paper focuses on identifying congestion probabilities, future work aims to build an algorithm that determines which specific set of links were congested during each individual snapshot, leveraging the probability information.
- Exact Correlation Nature: The current work assumes knowledge of which links are correlated, but not the degree or nature of that correlation. Future research could explore how to infer these correlation parameters.
Summary updated