Detecting the occurrence and location of performance anomalies (e.g., high jitter or loss events) is critical to ensuring the effective operation of network infrastructures. In this paper we present a framework for detecting and localizing performance anomalies based on using an active probe-enabled measurement infrastructure deployed on the periphery of a network. Our framework has three components: an algorithm for detecting performance anomalies on a path, an algorithm for selecting which paths to probe at a given time in order to detect performance anomalies (where a path is defined as the set of links between two measurement nodes), and an algorithm for identifying the links that are causing an identified anomaly on a path (i.e., localizing). The problem of detecting an anomaly on a path is addressed by comparing probe-based measures of performance characteristics with performance guarantees for the network (e.g., SLAs). The path selection algorithm is designed to enable a tradeoff between ensuring that all links in a network are frequently monitored to detect performance anomalies, while minimizing probing overhead. The localization algorithm is designed to use existing path measurement data in such a way as to minimize the number of paths necessary for additional probing in order to identify the link(s) responsible for an observed performance anomaly. We assess the feasibility of our framework and algorithms by implementing them in ns-2 and conducting a set of simulation-based experiments using several different network topologies. Our results show that our method is able to accurately detect and localize performance anomalies in a timely fashion and with lower probe and computational overheads than previously proposed methodologies.

A new wavelet-based methodology for representing data on regular grids is introduced and studied. The main attraction of this new “Local Compression-Alignment-Modified- Prediction (L-CAMP)” methodology is in the way it scales with the spatial dimension, making it, thus, highly suitable for the representation of high dimensional data. The specific highlights of the L-CAMP methodology are three. First, it is computed and inverted by fast algorithms with linear complexity and very small constants; moreover, the constants in the complexity bound decay, rather than grow, with the spatial dimension. Second, the representation is accompanied by solid mathematical theory that reveals its performance in terms of the maximal level of smoothness that is accurately encoded by the representation. Third, the localness of the representation, measured as the sum of the volumes of the supports of the underlying mother wavelets, is extreme. An illustration of this last property is done by comparing the L-CAMP system that is marked in this paper as V with the widely used tensor-product biorthogonal 9/7. Both are essentially equivalent in terms of performance. However, the L-CAMP V has in 10D localness score${≪ 29}$. The localness score of the 9/7 is, in that same dimension,${> 575{\,}000{\,}000{\,}000}$.

Service level agreements (SLAs) specify performance guarantees made by service providers, typically in terms of packet loss, delay, delay variation, and network availability. While many tools have been developed to measure individual aspects of network performance, there has been little work to directly address the issue of SLA compliance monitoring in an operational setting where accuracy, parsimony, and other related issues are of vital importance. This paper takes the following steps toward addressing this problem: (1) we introduce an architectural framework for integrating multiple discrete-time active measurement algorithms, an architecture that we call multi-objective monitoring; and (2) we introduce a new active measurement methodology to monitor the packet loss rate along a network path for determining compliance with specified performance targets which significantly improves accuracy over existing techniques. We present a prototype implementation of our monitoring framework, and demonstrate how a unified probe stream can consume lower overall bandwidth than if individual streams are used to measure different path properties. We demonstrate the accuracy and convergence properties of our new loss rate monitoring methodology in a controlled laboratory environment using a range of background traffic scenarios and examine its accuracy improvements over existing techniques.

Service level agreements (SLAs) define performance guarantees made by service providers, e.g, in terms of packet loss, delay, delay variation, and network availability. In this paper, we describe a new active measurement methodology to accurately monitor whether measured network path characteristics are in compliance with performance targets specified in SLAs. Specifically, (1) we describe a new methodology for estimating packet loss rate that significantly improves accuracy over existing approaches; (2) we introduce a new methodology for measuring mean delay along a path that improves accuracy over existing methodologies, and propose a method for obtaining confidence intervals on quantiles of the empirical delay distribution without making any assumption about the true distribution of delay; (3) we introduce a new methodology for measuring delay variation that is more robust than prior techniques; and (4) we extend existing work in network performance tomography to infer lower bounds on the quantiles of a distribution of performance measures along an unmeasured path given measurements from a subset of paths. We unify active measurements for these metrics in a discrete time-based tool called SLAM. The unified probe stream from SLAM consumes lower overall bandwidth than if individual streams are used to measure path properties. We demonstrate the accuracy and convergence properties of SLAM in a controlled laboratory environment using a range of background traffic scenarios and in one- and two-hop settings, and examine its accuracy improvements over existing standard techniques.

Measurement and estimation of packet loss characteristics are challenging due to the relatively rare occurrence and typically short duration of packet loss episodes. While active probe tools are commonly used to measure packet loss on end-to-end paths, there has been little analysis of the accuracy of these tools or their impact on the network. The objective of our study is to understand how to measure packet loss episodes accurately with end-to-end probes. We begin by testing the capability of standard Poisson-modulated end-to-end measurements of loss in a controlled laboratory environment using IP routers and commodity end hosts. Our tests show that loss characteristics reported from such Poisson-modulated probe tools can be quite inaccurate over a range of traffic conditions. Motivated by these observations, we introduce a new algorithm for packet loss measurement that is designed to overcome the deficiencies in standard Poisson-based tools. Specifically, our method creates a probe process that (1) enables an explicit trade-off between accuracy and impact on the network, and (2) enables more accurate measurements than standard Poisson probing at the same rate. We evaluate the capabilities of our methodology experimentally by developing and implementing a prototype tool, called BADABING. The experiments demonstrate the trade-offs between impact on the network and measurement accuracy. We show that BADABING reports loss characteristics far more accurately than traditional loss measurement tools.

Identifying anomalies rapidly and accurately is critical to the efficient operation of large computer networks. Accurately characterizing important classes of anomalies greatly facilitates their identification; however, the subtleties and complexities of anomalous traffic can easily confound this process. In this paper we report results of signal analysis of four classes of network traffic anomalies: outages, flash crowds, attacks and measurement failures. Data for this study consists of IP flow and SNMP measurements collected over a six month period at the border router of a large university. Our results show that wavelet filters are quite effective at exposing the details of both ambient and anomalous traffic. Specifically, we show that a pseudo-spline filter tuned at specific aggregation levels will expose distinct characteristics of each class of anomaly. We show that an effective way of exposing anomalies is via the detection of a sharp increase in the local variance of the filtered data. We evaluate traffic anomaly signals at different points within a network based on topological distance from the anomaly source or destination. We show that anomalies can be exposed effectively even when aggregated with a large amount of additional traffic. We also compare the difference between the same traffic anomaly signals as seen in SNMP and IP flow data, and show that the more coarse-grained SNMP data can also be used to expose anomalies effectively.