AT&T Labs Research - Duffield, Nicholas G.

Nick Duffield is a Distinguished Member of Technical Staff and an AT&T Fellow at AT&T Labs-Research, Florham Park, NJ, where he has been since 1995. He previously held post-doctoral and faculty positions in Dublin, Ireland, and Heidelberg, Germany. He received a BA in Natural Sciences in 1982, a MMath (Part III Maths) in 1983 from the University of Cambridge, UK, and a PhD in Mathematical Physics from the University of London, U.K., in 1987. His current research focuses on measurement and inference of networks and traffic. He is a co-inventor of the Smart Sampling technologies that lie at the heart of AT&T's scalable Traffic Analysis Service. Dr. Duffield was Charter Chair of the IETF working group on Packet Sampling. He was an Associate Editor for the IEEE/ACM Transactions on Networking from 2007-2011. He is an IEEE Fellow, and was a co-recipient the Sigmetrics 2012 Test of Time Award, for work in Network Tomography.

Publications

Publication list at AT&T, most downloadable.
External bibliographies: Microsoft Academic Search; Google Scholar; DBLP;

Major research interests (most recent first)

Machine Learning in Network Management: Exploring the complex causal relationships between measurable network behavior and customer experience

Optimal Sampling (including Smart Sampling of Flow Records): Developing efficient sampling algorithms that provably optimize trade-off between sample size and estimation variance, even for heavy-tailed distributions typical in the Internet. Structure aware sampling for more accurate range queries. Fair sampling over subpopulations. Versions currently deployed in network measurement infrastructure.
Architectures for Fine Grained Traffic Measurement: Router level data structures for storage and retrieval of delay measurements. Enhancing performance measurement through temporal locality,
Graph Sampling: unbiased node sampliing in P2P networks.
Network Security and Attack Detection: stress testing traffic, machine learning of flow classifiers
Performance Monitoring. Sampling for temporal loss patterns, now standardized in the IETF.

Trajectory Sampling. Coordinate packet sampling across routers based on hash of invariant packet fields. Now standardized in the IETF.
Network Tomography.
- Traffic Matrices: inferring traffic matrices from link level traffic aggregates. Deployed in network measurement infrastructure.
- Link Performance: inferring link level loss and delay by correlating end-to-end measurements across a mesh of paths. Support for reporting by transport protocols standardized in the IETF.

The Hose Model for Virtual Private Networks: service without advance need of a traffic matrix
Network Measurement Infrastructure: early generation (T3 speed) passive monitors
Analysis and Measurement of Effective Bandwidths: using
- Large Deviations and Martingale methods to establish generic bounds on queue tail probabilities, without the need for a detailed traffic model.
- Admission Control using measured effective bandwidth.
Statistical Mechanics
- Quantum dynamical semigroups and mean-field theory
- Large deviations and group representations
- Non-equilibrium phase transitions

Awards
Test of Time, 2012 ACM SIGMETRICS, for Network Tomography on General Topologies (2002). This award, given each year to a previous conference paper whose impact is still felt 10-12 years after publication, cited the paper’s pioneering work in network tomography, particularly its novel methods to estimate delay, packet loss, and other measures of performance.

AT&T Fellow, 2007. Network measurements sampling, analysis, and inference: Honored for fundamental contributions to sampling, analysis and inference from network measurements that have had broad impact on AT&T and the industry.

IEEE Fellow, 2005. For contributions to the measurement, analysis and management of telecommunications networks.

This version of the work is reprinted here with permission of IEEE for your personal use. Not for redistribution. The definitive version was published in 2012. , 2012-06-18

{Operational network data, management data such as customer care call logs and equipment system logs, is a very important source of information for network operators to detect problems in their networks. Unfortunately, there is lack of efficient tools to automatically track and detect anomalous events on operational data, causing ISP operators to rely on manual inspection of this data. While anomaly detection has been widely studied in the context of network data, operational data presents several new challenges, including the volatility and sparseness of data, and the need to perform fast detection (complicating application of schemes that require offline processing or large/stable data sets to converge). To address these challenges, we propose Tiresias, an automated approach to locating anomalous events on hierarchical operational data. Tiresias leverages the hierarchical structure of operational data to identify high-impact aggregates (e.g., locations in the network, failure modes) likely to be associated with anomalous events. To accommodate different kinds of operational network data, Tiresias consists of an online detection algorithm with low time and space complexity, while preserving high detection accuracy. We present results from two case studies using operational data collected at a large commercial IPTV network operated by a Tier-1 ISP: customer care calls log and set-top box crashes log. By comparing with a reference set verified by the ISP�s operational group, we validate that Tiresias can achieve > 94% accuracy in locating anomalies. Tiresias also discovers several previously unknown anomalies in the ISP�s customer care cases, demonstrating its effectiveness.}

(c) ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM SIGMETRICS, 2012-06-30.

{Random sampling is a powerful tool for working with large data. Queries over the full dataset are replaced by approximate queries over the smaller (and hence easier to store and manipulate) sample. The sample constitutes a flexible summary that supports a wide class of queries. But in many applications, datasets are modified with time, and it is desirable to update samples without requiring access to the full underlying datasets. In this paper, we introduce and analyze novel techniques for sampling over dynamic data, modeled as a stream of modifications to weights associated with each key. While sampling schemes designed for stream applications can often readily accommodate positive updates to the dataset, much less is known for the case of negative updates, where weights are reduced or items deleted altogether. We primarily consider the turnstile model of streams, and extend classic schemes to incorporate negative updates. Perhaps surprisingly, the modifications to handle negative updates turn out to be natural and seamless extensions of the well-known original positive update-only algorithms. We show that they produce unbiased estimators, and relate their performance to the behavior of corresponding algorithms on insert-only streams with different parameters. A careful analysis is necessitated, in order to account for the fact that sampling choices for one key now depend on the choices made for other keys.}

(c) ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM SIGmetrics 2011 Conference , 2011-06-07.

{The massive data streams observed in network monitoring, data processing and scientific studies are typically too large to store. For many applications over such data, we must obtain compact summaries of the stream. These summaries should allow accurate answering of post hoc queries with estimates which approximate the true answers over the original stream. The data often has an underlying structure which makes certain subset queries, in particular {em range queries}, more relevant than arbitrary subsets. Applications such as access control, change detection, and heavy hitters typically involve subsets that are ranges or unions thereof. Random sampling is a natural summarization tool, being easy to implement and flexible to use. Known sampling methods are good for arbitrary queries but fail to optimize for the common case of range queries. Meanwhile, specialized summarization algorithms have been proposed for range-sum queries and related problems. These can outperform sampling giving fixed space resources, but lack its flexibility and simplicity. Particularly, their accuracy degrades when queries span multiple ranges. We define new stream sampling algorithms with a smooth and tunable trade-off between accuracy on range-sum queries and arbitrary subset-sum queries. The technical key is to relax requirements on the variance over all subsets to enable better performance on the ranges of interest. This boosts the accuracy on range queries while retaining the prime benefits of sampling, in particular flexibility and accuracy, with tail bounds having optimality guarantees. Our experimental study indicates that structure-aware summaries drastically improve range-sum accuracy with respect to state-of-the-art stream sampling algorithms and outperform deterministic methods on range-sum queries and hierarchical heavy hitter queries.}

{Abstract�Effective management of large-scale cellular data networks is critical to meet customer demands and expectations. Customer calls for technical support provides direct indication as to the issues and problems customers encounter. In this paper we study the customer tickets � free-text recordings and classifications by customer support agents � collected at a large cellular network provider, with two inter-related goals: i) to characterize and understand the major factors which lead to customers to call and seek support; and ii) to utilize such customer tickets to help identify potential network problems. For this purpose, we develop a novel statistical approach to model customer call rates which account for customer-side factors (e.g., user tenure and handset types) as well as geo-locations. We show that most calls are due to customer-side factors and can be well captured by the model. Furthermore, we also demonstrate that location-specific deviations from the model provide a good indicator of potential network-side issues. The latter is corroborated with the detailed analysis of customer tickets and other independent data sources (non-ticket customer feedback and network performance data).}

(c) ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM SIGCOMM Workshop on Measurements Up the STack (Wâ€MUST) , 2011-08-19.

{Multidimensional distributions are often used in data min- ing to describe and summarize different features of large datasets. It is natural to look for distinct classes in such datasets by clustering the data. A common approach entails the use of methods like k-means clustering. However, the k-means method inherently relies on the Euclidean metric in the embedded space and does not account for additional topology underlying the distribution. In this paper, we propose using Earth Mover Distance (EMD) to compare multidimensional distributions. For a n-bin histogram, the EMD is based on a solution to the transportation problem with time complexity O(n3 log n). To mitigate the high computational cost of EMD, we pro- pose an approximation that reduces the cost to linear time. Other notions of distances such as the information theo- retic Kullback-Leibler divergence and statistical χ2 distance, account only for the correspondence between bins with the same index, and do not use information across bins, and are sensitive to bin size. A cross-bin distance measure like EMD is not affected by binning differences and meaningfully matches the perceptual notion of “nearness”. Our technique is simple, efficient and practical for clus- tering distributions. We demonstrate the use of EMD on a practical application of clustering over 400,000 anonymous mobility usage patterns which are defined as distributions over a manifold. EMD allows us to represent inherent re- lationships in this space. We show that EMD allows us to successfully cluster even sparse signatures and we compare the results with other clustering methods. Given the large size of our dataset a fast approximation is crucial for this application.}

The definitive version was published in SIAM Journal on Computing. , 2011-06-01

{From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size k that we can later use to estimate the total weight of arbitrary subsets. This is the classic context of on-line reservoir sampling, thinking of the generic sample as a reservoir. We present an efficient reservoir sampling scheme, VAROPTk, that dominates all previous schemes in terms of estimation quality. VAROPTk provides variance optimal unbiased estimation of subset sums. More precisely, if we have seen n items of the stream, then for any subset size m, our scheme based on k samples minimizes the average variance over all subsets of size m. In fact, the optimality is against any off-line scheme with k samples tailored for the concrete set of items seen. In addition to optimal average variance, our scheme provides tighter worst-case bounds on the variance of particular subsets than previously possible. It is efficient, handling each new item of the stream in O(log k) time. Finally, it is particularly well suited for combination of samples from different streams in a distributed setting. }

(c) ACM, 2010. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM CoNext 2010 , 2010-11-30.

{Traditional DSL troubleshooting solutions are reactive, relying mainly on customers to report problems, and tend to be labor-intensive, time consuming, prone to incorrect resolutions and overall can contribute to increased customer dissatisfaction. In this paper, we propose a proactive approach to facilitate troubleshooting customer edge problems and reducing customer tickets. Our system consists of: i) a ticket predictor which predicts future customer tickets; and ii) a trouble locator which helps technicians accelerate the troubleshooting process during field dispatches. Both components infer future tickets and trouble locations based on existing sparse line measurements, and the inference models are constructed automatically using supervised machine learning techniques. We propose several novel techniques to address the operational constraints in DSL networks and to enhance the accuracy of NEVERMIND. Extensive evaluations using an entire years worth of customer ticket and measurement data from a large network show that our method can predict thousands of future customer tickets per week with high accuracy and reduce significantly reduce the time and effort for diagnosing these tickets. This is beneficial as it has the effect of both reducing the number of customer care calls and improving customer satisfaction.}

(c) ACM, 2010. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Internet Measurement Conference , 2010-11-01.

{The reconvergence of routing protocols in response to changes in network topology can impact application performance. While improvements in protocol specification and implementation have significantly reduced reconvergence times, increasingly performance-sensitive applications continue to raise the bar for these protocols. As such, monitoring the performance of routing protocols remains a critical activity for network operators. We design FlowRoute, a tool based on passive data plane measurements that we use in conjunction with control plane monitors for offline debugging and analysis of forwarding table dynamics. We discuss practical constraints that affect FlowRoute, and show how they can be addressed in real deployment scenarios. As an application of FlowRoute, we study forwarding table updates by backbone routers at a tier-1 ISP. We detect interesting behavior such as delayed forwarding table updates and routing loops due to buggy routers � confirmed by network opera- tors � that are not detectable using traditional control plane monitors.}

This version of the work is reprinted here with permission of IEEE for your personal use. Not for redistribution. The definitive version was published in Proc. IEEE Network Operations and Management Symposium (NOMS), 2002. , 2002-04-19

{The management of communications networks increasingly requires detailed knowledge of network usage, acquired by direct measurement. We report on the design and implementation of a backend system for Trajectory Sampling, a method for the consistent sampling of packets in transmission across a network domain. This Trajectory Engine collects trajectory samples and stores them after appropriate preprocessing. It provides a querying and visualization tool to aid in traffic engineering and troubleshooting tasks. }

{In this paper we consider the problem of inferring link-level loss rates from end-to-end multicast measurements taken from a collection of trees. We give conditions under which loss rates are identifiable on a specified set of links. Two algorithms are presented to perform the link-level inferences for those links on which losses can be identified. One, the {em minimum variance weighted average (MVWA) algorithm} treats the trees separately and then averages the results. The second, based on {em expectation-maximization (EM)} merges all of the measurements into one computation. Simulations show that EM is slightly more accurate than MVWA, most likely due to its more efficient use of the measurements. We also describe extensions to the inference of link-level delay, inference from end-to-end unicast measurements, and inference when some measurements are missing. To appear in Proceedings ACM Sigmetrics 2002 }

AT&T Labs Research — Leading Invention, Driving Innovation

site map