This paper focuses on an anomaly detection method that uses a baseline model describing the normal behavior of network traffic as the basis for comparison with the audit network traffic. In the anomaly detection method, an alarm is raised if a pattern in the current network traffic deviates from the baseline model. The baseline model is often trained using normal traffic data extracted from traffic data for which all instances (i.e., packets) are manually labeled by human experts in advance as either normal or anomalous. However, since humans are fallible, some errors are inevitable in labeling traffic data. Therefore, in this paper, we propose an anomaly detection method that is tolerant to human errors in labeling traffic data. The fundamental idea behind the proposed method is to take advantage of the lossy nature of packet sampling for the purpose of correcting/preventing human errors in labeling traffic data. By using real traffic traces, we show that the proposed method can better detect anomalies regarding TCP SYN packets than the method that relies only on human labeling. (C) 2016 Elsevier B.V. All rights reserved.

In recent years, there has been growing interest in systems for sharing resources, which were originally used for personal purposes by individual users, among many unspecified users via a network. An example of such systems is a peer-to-peer (P2P) data storage system that enables users to share a portion of unused space in their own storage devices among themselves. In a recent paper on a P2P data storage system, the user behavior model was defined based on supply and demand functions that depend only on the storage space unit price in a virtual marketplace. However, it was implicitly assumed that other factors, such as unused space of storage devices possessed by users and additional storage space asked by users, did not affect the characteristics of the supply and demand functions. In addition, it was not clear how the values of parameters used in the user behavior model were determined. Therefore, in this paper, we modify the supply and demand functions and determine the values of their parameters by taking the above mentioned factors as well as the price structure of storage devices in a real marketplace into account. Moreover, we provide a numerical example to evaluate the social welfare realized by the P2P data storage system as a typical application of the modified supply and demand functions.

Due to significant environmental changes in the telecommunications market, network failures affect socioeconomic activities more than ever before. However, the health of public networks at a national level has not been investigated in detail. In this paper, we investigate the statistical characteristics of interval, duration, and the number of users affected for serious network failures, which are defined as network failures that last for more than two hours and affect more than 30,000 users, that occurred in Japan during Japanese fiscal years 2008-2012 (April 2008-March 2013). The results show that (i) the interval follows a Poisson process, (ii) the duration follows a Pareto distribution, (iii) the number of users affected follows a piecewise Pareto distribution, (iv) the product of duration and the number of users affected roughly follow a distribution that can be derived from a convolution of two distributions of duration and the number of users affected, and (v) the relationship between duration and the number of users affected differs from service to service. (C) 2014 Published by Elsevier Ltd.

When there are multiple component predictors, it is promising to integrate them into one predictor for advanced reasoning. If each component predictor is given as a stochastic model in the form of probability distribution, an exponential mixture of the component probability distributions provides a good way to integrate them. However, weight parameters used in the exponential mixture model are difficult to estimate if there is no training samples for performance evaluation. As a suboptimal way to solve this problem, weight parameters may be estimated so that the exponential mixture model should be a balance point that is defined as an equilibrium point with respect to the distance from/to all component probability distributions. In this paper, we propose a weight parameter estimation method that represents this concept using a symmetric Kullback-Leibler divergence and generalize this method.

Congestion inherently occurs on the Internet due to traffic concentration on certain nodes or links of networks. The traffic concentration is caused by inefficient use of topological information of networks in existing routing protocols, which reduces to inefficient mapping between traffic demands and network resources. Actually, the route with minimum cost, i.e., number of hops, selected as a transmission route by existing routing protocols would pass through specific nodes with common topological characteristics that could contribute to a large improvement in minimizing the cost. However, this would result in traffic concentration on such specific nodes. Therefore, we propose a measure of the distance between two nodes that is suitable for reducing traffic concentration on specific nodes. To consider the topological characteristics of the congestion points of networks, we define node-to-node distance by using a generalized norm, pnorm, of a vector of which elements are degrees of intermediate nodes of the route. Simulation results show that both the maximum Stress Centrality (SC) and the coefficient of variation of the SC are minimized in some network topologies by selecting transmission routes based on the proposed measure of node-to-node distance. Copyright © 2013 The Institute of Electronics, Information and Communication Engineers.

We propose an anomaly detection method for finding patterns in network traffic that do not conform to legitimate (i.e., normal) behavior. The proposed method trains a baseline model describing the normal behavior of network traffic without using manually labeled traffic data. The trained baseline model is used as the basis for comparison with the audit network traffic. This anomaly detection works in an unsupervised manner through the use of time-periodic packet sampling, which is used in a manner that differs from its intended purpose the lossy nature of packet sampling is used to extract normal packets from the unlabeled original traffic data. Evaluation using actual traffic traces showed that the proposed method has false positive and false negative rates in the detection of anomalies regarding TCP SYN packets comparable to those of a conventional method that uses manually labeled traffic data to train the baseline model. Performance variation due to the probabilistic nature of sampled traffic data is mitigated by using ensemble anomaly detection that collectively exploits multiple baseline models in parallel. Alarm sensitivity is adjusted for the intended use by using maximum- and minimum-based anomaly detection that effectively take advantage of the performance variations among the multiple baseline models. Testing using actual traffic traces showed that the proposed anomaly detection method performs as well as one using manually labeled traffic data and better than one using randomly sampled (unlabeled) traffic data.

In this paper, we derive a set of discrete time difference equations that models the spreading process of computer worms such as Code-Red and Slammer, which uses a common strategy called "random scanning" to spread through the Internet. We show that the derived set of discrete time difference equations has an exact relationship with the Kermack and McKendrick susceptible-infectious-removed (SIR) model, which is known as a standard continuous time model for worm spreading.

We propose a generalised diffusion-based file replication scheme for load balancing in unstructured P2P file-sharing networks. The generalised method is derived by replacing the replication probability of a peer used in our previous study with a new expression. In the previous expression, the replication probability is defined to be proportional to the difference between its own load and the average load of its neighbour peers. We show here that the replication probability can instead be expressed as a simple average of one defined to be negatively proportional to its own load and one defined to be proportional to the average load of its neighbour peers. The generalised method (a) includes the above three methods as special cases, (b) can control the trade-off between search and load balancing performances, (c) has a physical analogy to diffusion phenomena, and (d) achieves a good balance in the trade-off differently from our previous method. Copyright © 2012 Inderscience Enterprises Ltd.

When there are multiple trained predictors, one may want to integrate them into one predictor. However, this is challenging if the performances of the trained predictors are unknown and labeled data for evaluating their performances are not given. In this paper, a method is described that uses unlabeled data to estimate the weight parameters needed to build an ensemble predictor integrating multiple trained component predictors. It is readily derived from a mathematical model of ensemble learning based on a generalized mixture of probability density functions and corresponding information divergence measures. Numerical experiments demonstrated that the performance of our method is much better than that of simple average-based ensemble learning, even when the assumption placed on the performances of the component predictors does not hold exactly. © 2011 Springer Science+Business Media B.V.

We propose two types of autonomic and distributed cooperative behaviors of peers for peer-to-peer (P2P) file-sharing networks. Cooperative behaviors of peers are mediated by query trails, and allows the exploration of better trade-off points between file search and storage load balancing performance. Query trails represent previous successful search paths and indicate which peers contributed to previous file searches and were at the same time exposed to the storage load. The first type of cooperative behavior is to determine the locations of replicas of files through the medium of query trails. Placement of replicas of files on strong query trails contributes to improvement of search performance, but a heavy load is generated due to writing files in storage to peers on the strong query trails. Therefore, we attempt to achieve storage load balancing between. peers, while avoiding significant degradation of the search performance by creating replicas of files in peers adjacent to peers on strong query trails. The second type of cooperative behavior is to determine whether peers provide requested files through the medium of query trails. Provision of files by peers holding requested files on strong query trails contributes to better search performance, but such provision of files generates a heavy load for reading files from storage to peers on the strong query trails. Therefore, we attempt to achieve storage load balancing while making only small sacrifices in search performance by having peers on strong query trails refuse to provide files. Simulation results show that the first type of cooperative behavior provides equal or improved ability to explore trade-off points between storage load balancing and search performance in a static and nearly homogeneous P2P environment, without the need for fine tuning parameter values, compared to replication methods that require fine tuning of their parameters values. In addition, the combination of the second type and the first type of cooperative behavior yields better storage load balancing performance with little degradation of search performance. Moreover, even in a dynamic and heterogeneous P2P environment, the two types of cooperative behaviors yield good ability to explore trade-off points between storage load balancing and search performance.

This paper provides a characterization of fairness concepts in network resource allocation problems from the viewpoint of information theory. The fundamental idea underlying this paper is to characterize the utility functions in optimization problems, which motivate fairness concepts, based on a trade-off between user and network satisfaction. User satisfaction is evaluated using information divergence measures, which were originally used in information theory, to evaluate the difference between an implemented resource allocation and a requested resource allocation. The requested resource allocation is assumed to be ideal in some sense from the user's point of view. Network satisfaction is evaluated based on the efficiency of resource usage in the implemented resource allocation. The results in this paper indicate that the well-known fairness concept called weighted alpha-proportional fairness can be characterized using the alpha-divergence measure, which is a general class of information divergence measures, as an equilibrium of the trade-off. Some typical examples of applications demonstrate how the presented characterization works. (C) 2011 Elsevier Inc. All rights reserved.

In this letter, we develop a novel computational approach for network bandwidth allocation problems in which the compoundable constraints about the preferable transmission rate fall in the infeasible region. The approach is based on an iterative technique for non-convex optimization over the fixed point set of a certain nonexpansive mapping. The realized allocation maximizes a predefined utility and is closest to the preferable transmission rate with respect to the norm. Numerical examples show that our approach is an efficient way to solve the non-concave utility maximization problem.

Traffic Engineering (TE) is required for reducing highly-loaded links / nodes in parts of a network, thereby distributing the traffic load in the network. For efficient use of network resources, it is important to efficiently map traffic demands to network resources. Therefore, we should consider an appropriate definition of "distance" in networks with the topological features of the network instead of traffic demands. Recent studies have demonstrated a scale-free property of network topology, and node outbound degree distribution is an important factor in the scale-free networks. This paper proposes a new definition of "distance" between two arbitrary communication nodes in the Internet by using node degree information for avoiding congestion in the network. Some simulation results show that the proposed scheme can distribute traffic load from high degree nodes to other nodes, and thus provides robustness of networks. © 2011 IEEE.

Traffic Engineering (TE) is required for reducing highly-loaded links/nodes in a part of networks, thereby reducing the traffic concentration in a part of network. For efficient use of network resources, it is important to efficiently map traffic demands to network resources. However, most of the existing TE schemes are not aware of underlying network topology, Indeed, they try to dynamically map traffic demands to network resources in response to traffic trends in a short period of time. The paper addresses the issue of network congestion due to inefficient mapping between traffic demand and network resources. We propose a new routing metric to allocate forwarding route from source node to its destinations for effective use of network resources in scale-free networks. We show that the best routing metric is p-norm based on node degrees along a path to destination node. Furthermore, we investigate the impact of the parameter, p, on congestion level of each link, and show the best parameter p to minimize the maximum stress centrality in a network. © 2011 IEEE.

In this paper, we propose a file replication method to achieve load balancing in terms of write access to storage device ("write storage access load balancing" for short) in unstructured peer-to-peer (P2P) file-sharing networks in which the popularity trend of queried files varies dynamically. The proposed method uses a write storage access ratio as a load balance index value in order to stabilize dynamic P2P file-sharing environments adaptively. In the proposed method, each peer autonomously controls the file replication ratio, which is defined as a probability to create the replica of the file in order to uniform write storage access loads in the similar way to thermal diffusion phenomena. Theoretical analysis results show that the behavior of the proposed method actually has an analogy to a thermal diffusion equation. In addition, simulation results reveal that the proposed method has an ability to realize write storage access load balancing in the dynamic P2P file-sharing environments.

In this paper we propose a file replication scheme inspired by a thermal diffusion phenomenon for storage load balancing in unstructured peer-to-peer (P2P) file sharing networks The proposed scheme is designed such that the storage utilization ratios of peers will be uniform, in the same way that the temperature in a field becomes uniform in a thermal diffusion phenomenon The proposed scheme creates replicas of files in peers probabilistically, where the probability is controlled by using parameters that can be used to find the trade-off between storage load balancing and search performance in unstructured P2P file sharing networks First we show through theoretical analysis that the statistical behavior of the storage load balancing cannoned by the proposed scheme has an analogy with the thermal diffusion phenomenon We then show through simulation that the proposed scheme not only has superior performance with respect to balancing the storage load among peers (the primary objective of the present proposal) hut also allows the performance trade-off to be widely found Finally, we qualitatively discuss a guideline for setting the parameter values in order to widely find the performance trade-off from the simulation results.

We theoretically and numerically investigated the threshold network model with a generic weight function where there were a large number of nodes and a high threshold. Our analysis was based on extreme value theory, which gave us a theoretical understanding of the distribution of independent and identically distributed random variables within a sufficiently high range. Specifically, the distribution could be generally expressed by a generalized Pareto distribution, which enabled us to formulate the generic weight distribution function. By using the theorem, we obtained the exact expressions of degree distribution and clustering coefficient which behaved as universal power laws within certain ranges of degrees. We also compared the theoretical predictions with numerical results and found that they were extremely consistent. (C) 2009 Elsevier B.V. All rights reserved.

A basic and inevitable problem in estimating flow duration distribution arises from "censoring" (i.e., cutting off) the observed flow duration because of a finite measurement period. We extended the Kaplan-Meier method, which is used in the Survival analysis field, and applied it to recover information on the flow duration distribution that was lost due to censoring. We show that the flow duration distribution from a short period of actual traffic data with censoring that was estimated using a Kaplan-Meier-based method can approximate well the flow duration distribution calculated from a sufficiently long period of actual traffic data.

This paper provides a novel characterization of fairness concepts in network resource allocation problems from the viewpoint of information theory. The fundamental idea adopted in this paper is to characterize the utility functions used in optimization problems, which motivate fairness concepts, based on a trade-off between user and system satisfaction. Here, user satisfaction is evaluated using information divergence measures that were originally used in information theory to evaluate the difference between two probability distributions. In this paper, information divergence measures are applied to evaluate the difference between the implemented resource allocation and a requested resource allocation. The requested resource allocation is assumed to be ideal in some sense from the user's point of view. Also, system satisfaction is evaluated based on the efficiency of the implemented resource utilization, which is defined as the total amount of resources allocated to each user. The results discussed in this paper indicate that the well-known fairness concept called weighted a-proportional fairness can be characterized using the a-divergence measure, which is a general class of information divergence measures, as an equilibrium of the trade-off described above. In the process of obtaining these results, we also obtained a new utility function that has a parameter to control the trade-off. This new function is then applied to typical examples to solve resource allocation problems in simple network models such as those for two-link networks and wireless LANs.

It is known that Internet routing policies for both intra- and inter-domain routing can naturally give rise to Triangle Inequality Violations (TIVs) with respect to Quality of Service (QoS) network metrics such as latencies between nodes. This motivates the exploitation of such TIVs phenomenon in network metrics to design TlV-aware routing overlay architecture which is capable of choosing quality overlay routing paths to improve end-to-end QoS without changing the underlying network architecture. Our idea is to find quality overlay routes between node pairs based on TIV optimization in terms of the latency and packet loss ratio, and that can offer near optimal routing quality in cost-effective and scalable manner. Our intuition to do this is to choose these overlay routes from a small set of transit nodes. We propose to assign nodes with transit selection frequency scores that are computed based on previous node usage for transit, and consolidate a small set of highly ranked transit nodes. For every node pair, we choose the best transit node in this small set for overlay routing, based on TIV optimization in latency and packet loss ratio. We analyze the quality of our TlV-aware routing overlay algorithm analytically and using real Internet measurements on latency and packet loss ratio. Our results show good quality performance in improving end-to-end QoS routing. © 2009 IEEE.

We present a TCP flow level performance evaluation on error rate aware scheduling algorithms in Evolved UTRA and UTRAN networks. With the introduction of the error rate, which is the probability of transmission failure under a given wireless condition and the instantaneous transmission rate, the transmission efficiency can be improved without sacrificing the balance between system performance and user fairness. The performance comparison with and without error rate awareness is carried out dependant on various TCP traffic models, user channel conditions, schedulers with different fairness constraints, and automatic repeat request (ARQ) types. The results indicate that error rate awareness can make the resource allocation more reasonable and effectively improve the system and individual performance, especially for poor channel condition users.

The present paper introduces the Proxy Data Transfer system, which enables file transfer applications to work over long delays and leaky or frequently disconnecting networks (referred to hereinafter as a "challenged environment"), in which traditional end-to-end communication does not work well. An important feature is that the satellite link is applied to the control channel with a low data rate in order to achieve sustainability over a very large area. We developed a prototype and conducted an experiment using the Japanese engineering testing satellite "KIKU no.8" in May of 2008. An experiment using KIKU no.8 will be described and a live demonstration in an emulated network environment will be given at CHANTS2008.

With the rapid increase of link speed in recent years, packet sampling has become a very attractive and scalable means in collecting flow statistics; however, it also makes inferring original flow characteristics much more difficult. In this paper, we develop techniques and schemes to identify flows with a very large number of packets (also known as heavy-hitter flows) from sampled flow statistics. Our approach follows a two-stage strategy: We first parametrically estimate the original flow length distribution from sampled flows. We then identify heavy-hitter flows with Bayes' theorem, where the flow length distribution estimated at the first stage is used as an a priori distribution. Our approach is validated and evaluated with publicly available packet traces. We show that our approach provides a very flexible framework in striking an appropriate balance between false positives and false negatives when sampling frequency is given.

A learning method using an integration of multiple component predictors as an ultimate predictor is generically referred to as ensemble learning. The present paper proposes a weight parameter estimation method for ensemble learning under the constraint that we do not have any information of the desirable (true) output. The proposed method is naturally derived from a mathematical model of ensemble learning, which is based on an exponential mixture type probabilistic model and Kullback divergence. The proposed method provides a legitimate strategy for weight parameter estimation under the abovementioned constraint if it is assumed that the accuracy of all multiple predictors are the same. We verify the effectiveness of the proposed method through numerical experiments.

Autonomous distributed systems comprising an overlay network on the Internet are proliferating as a new technology responsible for the next-generation Web. Due to the properties of such a large-scale system, it is difficult to measure the characteristics of the entire system without modifying the internal protocol of the applications. In this paper, by using a measurement method applicable to P2P applications and measured results obtained by applying this measurement method in part, a general-purpose method for estimating the size and behavior of the entire P2P network is proposed. Further, the present method is applied to a real P2P network and its effectiveness is presented by a specific example. (C) 2006 Wiley Periodicals, Inc.

As a key technology of evolved UTRA and UTRAN, hybrid ARQ with packet combining (HARQ with PC) can effectively improve the throughput performance for poor channel condition users without doing unacceptable level of harm to the system transmission efficiency or the throughput performance of good condition users. In the present study, we attempt to apply scheduling with error rate consideration as an alternative method by which to realize a comparable TCP performance to HARQ with PC. Scheduling with error rate consideration introduces the transmission failure possibility (error rate) in order to modify the existing channel-aware scheduling schemes to avoid high-risk transmissions, and thus improves TCP performance. Simulations show that scheduling with error rate consideration can realize a TCP performance comparable to HARQ with PC when no user continuously experiences a nearly zero successful transmission possibility environment. Moreover, it is shown herein that a synergistic improvement can be achieved by applying scheduling with error rate consideration to HARQ with PC. © 2007 IEEE.

A recent trend in routing research is the use of overlay routing to improve end-to-end QoS without changing the network-level architecture. The key of this technology is to find an alternative route that can avoid congested routes, using an overlay network. Developing cost-efficient overlay routing in terms of calculation cost and information distribution cost needed to find an alternative route is important for deploying QoS-aware overlay routing. Thus, this paper evaluates how effective overlay routing can be when the number of alternative route candidates is limited to reduce costs. Evaluation results using actual measurement data indicate that overlay routing is still effective even if alternative route candidates are limited to 1/4 of all possible alternative routes. We also discuss an overlay routing algorithm to enable us to find an appropriate route under the constraint that the number of alternative route candidates is limited.

The probability of transmission failure under a given wireless condition and instantaneous transmission rate is introduced as a new scheduling metric to improve the performance of existing scheduling algorithms. Scheduling algorithms for high-speed downlink packet access (HSDPA) in wideband code division multiple access (WCDMA) networks generally deal with the instantaneous transmission rate of each user as a key parameter reflecting the time-varying and location-dependent characteristics of the wireless channel. As a more detailed measure of the wireless condition of each user, the error rate metric improves the effectiveness of sharing resources without sacrificing a good balance between system performance and user fairness. Simulation results demonstrate that a performance gain of approximately 20% can be achieved for several well-known scheduling algorithms when the error rate is taken into account. Copyright 2006 ACM.

Predicting wireless environment parameters as correctly and timely as possible is of practical importance to optimal resource allocation in wireless systems. For example, as the realtime wireless condition information is not available in reality due to delay, the latest historic wireless environment parameters are used to determine the users' instantaneous transmission rate in most of the existing systems in high-speed downlink packet access (HSDPA) networks. However, the wireless condition variation during this delay (e.g., 6ms) sometimes results in unsuitable determination of the instantaneous transmission rate and eventually influences the user and system performance. It is shown by simulation results that compared with using the ideal realtime wireless environment information, using the latest available historic information will introduce about 10%-15% throughput performance damage averagely. Therefore, in this paper, in order to mitigate such performance degradation, a simple linear prediction of the current wireless environment parameters is introduced. Simulation results demonstrate that nearly 10% improvement can be achieved under several well-known scheduling algorithms in a HSDPA network when the predictive environment parameter is applied to determine the instantaneous transmission rate. © 2006 IEEE.

In pure peer-to-peer (P2P) file sharing applications and protocols using a flooding-based query algorithm, a large number of control packets (query packets) are transmitted on the network to search for target files. This clearly leads to a degradation of communication quality on the network and terminals as the number of users of the application increases. To solve such problems, this paper proposes: (1) a unified framework to describe a wide variety of query algorithms for pure P2P and (2) a new query algorithm based on this framework. Our framework determines the number of destinations for query packets based on the hop value recorded in received query packets. Simulation results revealed that the proposed query algorithm can reduce the overhead in the flooding-based query algorithm and k-random walks without decreasing the success rate of retrieval regardless of the density of target files in the network.

Peer-to-peer (P2P) applications have been expanding rapidly in recent years, and the contribution of P2P to present Internet traffic is close to that of the World Wide Web (WWW). In this study, the flow of WWW and P2P traffic is analyzed by network measurement. The characteristics of WWW and P2P are examined, especially in terms of the flow arrival interval, flow duration, flow size, and flow rate. Based on the results of the analysis, the effect of a P2P flow increase on the overall traffic characteristics is investigated. The results of this study will be utilized in network design, proposals for control procedures, and traffic modeling, considering the traffic characteristics of particular applications. © 2005 Wiley Periodicals, Inc.

The f-divergence, which is defined by using a class of convex functions, is used as a generalized phenotype of discriminant measures between two probability distributions. In this paper, we derive a new class of discriminant measures defined on the set of all positive finite measures using the invariance of the f-divergence. This is a class of discriminant measures different from ones which have often been used. We mention some aspects of its effectiveness concerning the extension of discriminant measures by showing that the proposed class includes measures that facilitate statistical data processing and are suitable for the explicit formulation and analysis of the ensemble learning method. © 2004 Wiley Periodicals, Inc.

A replication scheme is an effective method for maintaining a high hit rate for target files. This paper proposes a new replication scheme that scatters 'replicas ' of files to other servents on a P2P network for the purpose of dispersing query and download traffic. First, the details of this proposed scheme are described and its parameter tuning is discussed by introducing rating functions. Second, the effectiveness of this scheme is evaluated by simulation. The simulation results demonstrate that the proposed scheme has superior performance for some characteristic values, such as the hit rate and the number of mean hops to the target servent, compared with other schemes. Finally, the influence of departure rate is discussed.

It is important to predict serious deterioration of telecommunication quality. This paper investigates predicting such serious events by analyzing only a "short" period (i.e., a "small" amount) of teletraffic data. To achieve this end, this paper presents a method for analyzing the tail distributions of teletraffic state variables, because tail distributions are suitable for representing serious events. This method is based on Extreme Value Theory (EVT), which provides a firm theoretical foundation for the analysis. To be more precise, in this paper, we use throughput data measured on an actual network during daily busy hours for 15 minutes, and use its first 10 seconds (known data) to analyze the tail distribution. Then, we evaluate how well the obtained tail distribution can predict the tail distribution of the remaining 890 seconds (unknown data). The results indicate that the obtained tail distribution based on EVT by analyzing the small amount of known data can predict the tail distribution of unknown data much better than methods based on empirical or log-normal distributions. Furthermore, we apply the obtained tail distribution to predict the peak throughput in unknown data. The results of this paper enable us to predict serious deterioration events with lower measurement cost.

Identifying elephant flows is very important in developing effective and efficient traffic engineering schemes. In addition, obtaining the statistics of these flows is also very useful for network operation and management. On the other hand, with the rapid growth of link speed in recent years, packet sampling has become a very attractive and scalable means to measure flow statistics ; however, it also makes identifying elephant flows become much more difficult. Based on Bayes' theorem, this paper develops techniques and schemes to identify elephant flows in periodically sampled packets. We show that our basic framework is very flexible in making appropriate trade-offs between false positives (misidentified flows) and false negatives (missed elephant flows) with regard to a given sampling frequency. We further validate and evaluate our approach by using some publicly available traces. Our schemes are generic and require no per-packet processing ; hence, they allow a very cost-effective implementation for being deployed in large-scale high-speed networks.