Upstream dynamic bandwidth allocation (DBA) for Gigabit Passive Optical Networks (GPON) is an important design problem since the shared uplink carries many bursty streams of different QoS requirements and there are various practical system constraints on processing loads in the OLT (Optical Line Terminal) and the ONUs (Optical Network Units). We propose self-adaptive bandwidth allocation solutions, where the OLT allocates bandwidth among the ONUs in an efficient and responsive manner, and importantly, without requiring buffer status reports from ONUs. These solutions could allow design of simpler ONUs. Our first solution is based on simple estimation by the OLT of the sample gradient of the ONU buffer content and application of stochastic approximation for sequential updates of bandwidth allocations that minimize buffer contents. The second approach is a closed form solution that minimizes the sum of weighted throughput across all ONUs. We compare our solutions with DBA algorithms that require buffer status reporting and empirically demonstrate their advantages.

We consider the problem of inferring link loss rates using passive measurements. Prior inference approaches are mainly built on the time correlation nature of packet losses. However, passive inference generally has limited control over the measurement process, and it is a challenging issue to adapt loss rate inference to the impact of time correlation. We address this issue and propose a new loss model that expresses an inferred link loss rate as a function of time correlation. Under this loss model with time correlation, we show its identifiability, and propose a novel profile-likelihood-based inference approach that can accurately infer link loss rates for various complex topologies (e.g., trees with many leaf branches). We validate the accuracy of our inference approach with model and network simulations.

In many telecom and web applications, there is a need to identify whether data objects in the same source or different sources represent the same entity in the real-world. This problem arises for subscribers in multiple services, customers in supply chain management, and users in social networks when there lacks a unique identifier across multiple data sources to represent a real-world entity. Entity resolution is to identify and discover objects in the data sets that refer to the same entity in the real world. We investigate the entity resolution problem for large data sets where efficient and scalable solutions are needed. We propose a novel unsupervised blocking algorithm, namely SPectrAl Neighborhood (SPAN), which constructs a fast bipartition tree for the records based on spectral clustering such that real entities can be identified accurately by neighborhood records in the tree. There are two major novel aspects in our approach: 1)We develop a fast algorithm that performs spectral clustering without computing pairwise similarities explicitly, which dramatically improves the scalability of the standard spectral clustering algorithm; 2) We utilize a stopping criterion specified by Newman-Girvan modularity in the bipartition process. Our experimental results with both synthetic and real-world data demonstrate that SPAN is robust and outperforms other blocking algorithms in terms of accuracy while it is efficient and scalable to deal with large data sets.

Quantiles are very useful in characterizing the data distribution of an evolving dataset in the process of data mining or network monitoring. The method of Stochastic Approximation (SA) tracks quantiles online by incrementally deriving and updating local approximations of the underly distribution function at the quantiles of interest. In this paper, we propose a generalization of the SA method for quantile estimation that allows not only data insertions, but also dynamic data operations such as deletions and updates.

We propose the tracking of long duration flows as a new network measurement primitive. Long-duration flows are characterized by their long lived nature in time, and may not have high traffic volumes. We propose an efficient data streaming algorithm to effectively track long duration flows. Our basic technique is to maintain only two Bloom filters at any given time. In each time duration, only old flows that appear in the current time duration get copied to the current Bloom filter. Our basic algorithm is further enhanced by sampling. Using real network traces, we show that our tracking algorithm is very accurate with low false positive and false negative probabilities. Using multi-faceted analysis, we show that more than 50% of hosts participating in long duration flows (duration no less than 30 minutes) are blacklisted by various public sources.

Estimating the number of distinct values is a fundamental problem in database that has attracted extensive research over the past two decades, due to its wide applications (especially in the Internet). Many algorithms have been proposed via sampling or sketching for obtaining statistical estimates that only require limited computing and memory resources. However, their performance in terms of relative estimation accuracy usually depends on the unknown cardinalities. In this paper, we address the following question: can a distinct counting algorithm have uniformly reliable performance, i.e. constant relative estimation errors for unknown cardinalities in a wide range, say from tens to millions? We propose a self-learning bitmap algorithm (S-bitmap) to answer this question. The S-bitmap is a bitmap obtained via a novel adaptive sampling process, where the bits corresponding to the sampled items are set to 1, and the sampling rates are learned from the number of distinct items already passed and reduced sequentially as more bits are set to 1. A unique property of S-bitmap is that its relative estimation error is truly stabilized, i.e. invariant to unknown cardinalities in a prescribed range. We demonstrate through both theoretical and empirical studies that with a given memory requirement, S-bitmap is not only uniformly reliable but more accurate than state-of-the-art algorithms such as the multiresolution bitmap and Hyper LogLog algorithms under common practice settings.

In this paper, we develop an online monitoring methodology for the time-varying cyclical streams of network data, that combines a baseline state-space model and statistical control schemes to monitor departures from the baseline model. Parameters of the state space models are initialized based on the training data, and updated for each incoming observation. The statistical control schemes for monitoring are designed based on forecasting errors from the baseline model, under the framework of statistical change detection. We demonstrate the effectiveness of our methodology using measurement data from an EVDO wireless network.

The Internet host cardinality, defined as the number of distinct peers that an Internet host communicates with, is an important metric for profiling Internet hosts. Some example applications include behavior based network intrusion detection, p2p hosts identification, and server identification. However, due to the tremendous number of hosts in the Internet and high speed links, tracking the exact cardinality of each host is not feasible due to the limited memory and computation resource. Existing approaches on host cardinality counting have primarily focused on hosts of extremely high cardinalities. These methods do not work well with hosts of moderately large cardinalities that are needed for certain host behavior profiling such as detection of p2p hosts or port scanners. In this paper, we propose an online sampling approach for identifying hosts whose cardinality exceeds some moderate prescribed threshold, e.g. 50, or within specific ranges. The main advantage of our approach is that it can filter out the majority of low cardinality hosts while preserving the hosts of interest, and hence minimize the memory resources wasted by tracking irrelevant hosts. Our approach consists of three components: 1) two-phase filtering for eliminating low cardinality hosts, 2) thresholded bitmap for counting cardinalities, and 3) bias correction. Through both theoretical analysis and experiments using real Internet traces, we demonstrate that our approach requires much less memory than existing approaches do whereas yields more accurate estimates.

Understanding the aggregate behavior of network host connectivities is important for network monitoring and traffic engineering. One characterization of such an aggregate behavior is the host distributions of distinct communicating peers or flows. For example, during the worm outbreak, the port scanning activities would cause many hosts with increasing number of (one-way) peers (or flows), and hence a change in the host distributions of distinct communicating peers or flows. In this paper, we develop an efficient streaming algorithm for tracking these host distributions of distinct elements, also called cardinality distributions, for a high speed network with a large number of hosts. Our approach utilizes the continuous Flajolet-Martin sketches, which is the minimal order statistics of hashed values, as a compact data summary and develops maximum likelihood estimates of these distributions. By leveraging the aggregation of many hosts, we are able to obtain very accurate estimates of the cardinality distributions by maintaining a compact statistical summary that is as small as one number (at most 32 bits) per host. Extensive experimental studies are carried out to demonstrate their excellent performance.

The problem of identifying applications online and directly from traffic flows recently has been a subject of great interest. Traditional techniques relying on port numbers or payload signatures are becoming less effective. In this paper, we present an approach to online identification of applications using statistical behavior analysis. We investigate both host- level identification and flow-level identification. For each level, we define the suitable metrics that can be computed fast and effectively exploited by the identification process. We propose to use decision trees to identify applications with low computation complexity, which is required for high-speed online processing. Our experimental results using BitTorrent, HTTP, SMTP and FTP traffic traces demonstrate that our technique can identify these applications with low error rates and short delay.

Knowing the traffic matrix, i.e., packet/byte counts between pairs of nodes in a network, is important for network management. The main challenges for accurate traffic matrix estimation in a high speed network are the computation and memory limitations. In this paper, we propose a novel algorithm for traffic matrix estimation that can yield accurate estimates whereas uses small memory and per packet update overhead. Our algorithm constructs a compact probabilistic traffic digest at each network node, and derives a Quasi Maximum Likelihood Estimate (Quasi-MLE) of the traffic matrix by correlating the traffic digests received at a central location. Our new approach is highly efficient, requiring no prior knowledge of the exact packet size distributions. We derive accurate approximation of the relative error distribution of our estimate. For an origin- destination (OD) pair (o,d), we show that by using an array of size M for each traffic digest at o and d, the relative estimation standard error is O(M-1/2(sigmao+sigmad)1/2), where sigmao,sigmadare the noise-to-signal ratios, defined as the ratios of non-OD packet/byte counts to OD packet/byte counts at the origin and destination. This is superior to the state-of-the-art algorithms, especially for large sigmaoand sigmad, where the estimation is more challenging. We further demonstrate the effectiveness of our approach using both model and real Internet trace-driven simulations.

Information on network host connectivity patterns are important for network monitoring and traffic engineering. In this paper, an efficient streaming algorithm is proposed to estimate cardinality distributions including connectivity distributions, e.g. percent of hosts with any given number of distinct communicating peers or flows.

Identification of significant patterns in network traffic, such as IPs or flows that contribute large volume (heavy hitters) or introduce large changes (heavy changers), has many applications in accounting and network anomaly detection. As network speed and the number of flows grow rapidly, tracking per-IP or per-flow statistics becomes infeasible due to both the computational overhead and memory requirements. In this paper, we propose a novel sequential hashing scheme that requires only O(H log N) both in memory and computational overhead that are close to being optimal, where N is the the number of all possible keys (e.g., flows, IPs) and H is the maximum number of heavy keys. Moreover, the generalized sequential hashing scheme makes it possible to trade off among memory, update cost, and detection cost in a large range that can be utilized by different computer architectures for optimizing the overall performance. In addition, we also propose statistically efficient algorithms for estimating the values of heavy hitters and heavy changers. Using both theoretical analysis and experimental studies of Internet traces, we demonstrate that our approach can achieve the same accuracy as the existing methods do but using much less memory and computational overhead.

Network tomography has been regarded as one of the most promising methodologies for performance evaluation and diagnosis of the massive and decentralized Internet. It can be used to infer unobservable network behaviors from directly measurable metrics and it does not require cooperation between the network internal elements and the end users. For instance, the Internet users may estimate the link level characteristics such as loss and delay from end-to-end measurements, whereas the network operators can evaluate the Internet path-level traffic intensity based on link-level traffic measurements. In this paper, we present a novel estimation approach for the network tomography problem. Unlike previous likelihood based methods, our approach is based on characteristic functions, i.e. the Fourier transform, of the distributions of observed measurements. We focus on network delay tomography and develop a Fourier domain inference algorithm based on flexible mixture models of link delays. Through extensive model simulation and simulation using real Internet trace, we are able to demonstrate that the new algorithm is computationally more efficient and yields more accurate estimates than previous methods, especially for a network with heterogeneous link delays. In addition, we obtain some identifiability results that can be applied to general distribution models for link delays.

Abstract — Fast spreading worms are a reality, as amply demonstrated by worms such as Slammer, which reached its peak propagation in a matter of minutes. With these kinds of fast spreading worms, the traditional approach of signature-based detection is no longer sufficient. Specifically, these worms can infect all vulnerable hosts well before a signature is available. To counter them, we must devise fast detection algorithms that can detect new worms without signatures as they first begin to appear. We present the design and evaluation of such an algorithm in this paper. The key to the algorithm is the identification of certain invariant characteristics of worm propagation. Specifically, we are able to demonstrate using real network traces how worm propagation can perturb the arrival process distribution of unsolicited packets. Our algorithm employs a novel two-step procedure that combines a first stage change point detection with a second stage growth rate inference to confirm the existence of aworm. To evaluate the algorithm, we have applied it to multi-year network traces that cover many of the major worm outbreaks in recent years, including Slammer, Witty, Nimda and Blaster. In all cases, the new algorithm is able to detect the worm within a very short time, well before significant infection has taken place. I.