Like their public counterpart such as Facebook and Twitter, enterprise social networks are poised to revolutionize how people interact in the workplace. There is a pressing need to understand how people are using these social networks. Unlike the public social networks like Facebook or Twitter which are normally characterized using the social graph or the interaction graph, enterprise social networks are also governed by an organization graph. Based on a six month dataset collected from May through October 2011 of a large enterprise social network, we study the characteristics of activities of its enterprise social network. We observe that the user attributes in the organization graph such as geographic location (eg. country) and his/her rank in the company hierarchy have a significant impact on how the user uses the social network and how user interacts with each other. We then build formal statistical models of user interaction graphs in enterprise social network and quantify effects of user attributes from organization graphs on these interactions. Furthermore, as the enterprise social network medium bring users from diverse locations and social status forming ad-hoc communities, our statistical model can be further enhanced by including these ad-hoc communities.

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.

As a key approach to securing large networks, existing anomaly detection techniques focus primarily on network traffic data. However, the sheer volume of such data often renders detailed analysis very expensive and reduces the effectiveness of these tools. In this paper, we propose a light-weight anomaly detection approach based on unproductive DNS traffic, namely, the failed DNS queries, with a novel tool - DNS failure graphs. A DNS failure graph captures the interactions between hosts and failed domain names. We apply a graph decomposition algorithm based on the tri-nonnegative matrix factorization technique to iteratively extract coherent co-clusters (dense subgraphs) from DNS failure graphs. By analyzing the co-clusters in the daily DNS failure graphs from a 3-month DNS trace captured at a large campus network, we find these co-clusters represent a variety of anomalous activities, e.g., spamming, trojans, bots, etc.. In addition, these activities often exhibit distinguishable subgraph structures. By exploring the temporal properties of the co-clusters, we show our method can identify new anomalies that likely correspond to unreported domain-flux bots.

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.

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.