|
Researchers: Yvan Pointurier, Postdoc, Prof. Mark Coates & Prof. Mike Rabbat
Description:
In this project, we tackle the problem of end-to-end network monitoring
in communication networks in the presence of very partial information.
Such a situation arises when it is difficult or expensive, even for the
network manager, to monitor the metrics related to all paths in the
network, but measuring just a few of them is possible. Examples of
end-to-end metrics are end-to-end delay in backbone networks, or
bit-error rates/signal degradation in all-optical networks (networks
with no electrical regenerators, such as Agile All-Photonic Networks). To
estimate the missing metrics, we rely on the knowledge of the underlying
topology of the network, which is assumed to be known by the network
administrator, or can be determined via network
tomography.
Since multiple paths share the same links (above, the red and blue paths share one link), there exists
a space correlation between the end-to-end metrics, which we
exploit to reduce the number of required observed metrics to estimate
the non-observed metrics. Moreover, end-to-end metrics tend to be
slow-varying, and hence there is also a time-correlation between
the end-to-end metrics. We exploit this correlation as well to further reduce the
number of metrics to observe.
Our technique relies on 3 components. First, we develop a path
selection algorithm adapted to the problem and the network. The
goal of this step is to select the small percentage of paths which we will observe. Next, we
build a diffusion operator (the way the diffusion operator is
built is similar to the modeling of heat diffusion in an object) adapted
to the problem; this diffusion operator is then used in conjunction with
wavelet diffusion theory to find a basis on which the end-to-end
metrics can be represented in a highly compressed fashion.
Below, we show on a concrete example how our diffusion wavelet bases can compress delays. We compressed the end-to-end delays for a network with 121 paths over 1 (top panel) and 8 (bottom panel) instants, and sorted the corresponding coefficients in descending order. When compression is done over 8 instants to account for both spatial and temporal correlations, the coefficients of the signal in the diffusion wavelet basis decay much faster (almost exponentially) than the raw measurements taken in the original basis. This hints that sparse signal recovery techniques can be used to estimate the signal in the diffusion wavelet basis.
The following figure shows a diffusion wavelet basis vector: each ball represents a link (we represented physical links over a period of 8 instants), and balls are larger when the coefficient of the diffusion wavelet basis vector is larger. Here, three coefficients dominate across all timesteps - they are represented by the larger red and blue balls on the right-hand of the figure.
Finally, using compressed sensing and non-linear estimation techniques,
we estimate the missing metrics first in the compressed (wavelet) basis,
and then in the basis corresponding to the original problem.
Early results show that we can recover the average end-to-end delay in a
backbone network of 11 nodes (forming 121 routes) over a period of time
with an accuracy of 5% by observing only 5 routes at any single time instant.
In the example above, we show the recovered delays for four different paths in a sample 11-node, 121-path network with only 5 measurements at any single time. The black curves show the real data, the blue curve show the results from a state-of-the-art technique called "Network Kriging", and the red curves show our results. Our technique follows the low-frequency variations of the path delays well.
Publications:
M. J. Coates, Y. Pointurier and M. Rabbat, Compressed network monitoring for IP and all-optical networks, in Proc. of the ACM/Usenix Internet Measurement Conference (IMC), Oct. 2007, San Diego, CA, USA.
M.J. Coates, Y. Pointurier and M. Rabbat, Compressed network monitoring, in Proc. IEEE Workshop on Statistical Signal Processing, Aug. 2007, Madison, WI.
|
Return to Network Monitoring Projects