Computer Networks 52 (2008) 2677–2689
Contents lists available at ScienceDirect
Computer Networks journal homepage: www.elsevier.com/locate/comnet
A stratiﬁed trafﬁc sampling methodology for seeing the big picture Stênio Fernandes a,c, Carlos Kamienski a,b, Judith Kelner a, Dênio Mariz d, Djamel Sadok a,* a
Universidade Federal de Pernambuco, Centro de Informatica, Cidade Universitaria, 50732-970 Recife, PE, Brazil Universidade Federal do ABC, Santo André, SP, Brazil Centro Federal de Educação Tecnológica de Alagoas, Maceió, AL, Brazil d ´ba, João Pessoa, PB, Brazil Centro Federal de Educação Tecnológica da Paraı b c
a r t i c l e
i n f o
Article history: Received 25 September 2006 Received in revised form 8 April 2008 Accepted 16 May 2008 Available online 5 June 2008 Responsible Editor: S. Kasera Keywords: Trafﬁc sampling Measurement Trafﬁc engineering
a b s t r a c t This work explores the use of statistical techniques, namely stratiﬁed sampling and cluster analysis, as powerful tools for deriving trafﬁc properties at the ﬂow level. Our results show that the adequate selection of samples leads to signiﬁcant improvements allowing further important statistical analysis. Although stratiﬁed sampling is a well-known technique, the way we classify the data prior to sampling is innovative and deserves special attention. We evaluate two partitioning clustering methods, namely clustering large applications (CLARA) and K-means, and validate their outcomes by using them as thresholds for stratiﬁed sampling. We show that using ﬂow sizes to divide the population we can obtain accurate estimates for both size and ﬂow durations. The presented sampling and clustering classiﬁcation techniques achieve data reduction levels higher than that of existing methods, on the order of 0.1% while maintaining good accuracy for the estimates of the sum, mean and variance for both ﬂow duration and sizes. Ó 2008 Elsevier B.V. All rights reserved.
1. Introduction Trafﬁc monitoring is seen as an important tool for engineering networks of varying sizes [21]. Characterizing and understanding the trafﬁc mix enables Internet Service Providers (ISPs) to devise new business and settlement models. Recently, the pie has been shifting from transport to content services and understandably many sought a piece of the new opportunities. Efﬁcient measurement strategies became an essential tool contributing to a number of tasks some of which were unforeseen until today. Trafﬁc measurement has been used for identifying anomalous behavior (such as unexpected high trafﬁc volumes due to denial of service attacks, routing problems, etc.), for designing and validating new trafﬁc models, for adequate planning of seasonal activities, such as upgrading network capacity,
* Corresponding author. Tel./fax: +55 81 2126 8954. E-mail addresses: [email protected] (S. Fernandes), [email protected] (C. Kamienski), [email protected] (J. Kelner), [email protected] (D. Mariz), [email protected] (D. Sadok). 1389-1286/$ - see front matter Ó 2008 Elsevier B.V. All rights reserved. doi:10.1016/j.comnet.2008.05.011
which allows introducing new services or the adoption of usage-based and content-based pricing. Commonly used ﬂow monitoring tools (such as Cisco’s NetFlow [2] and Juniper’s JFlow [17]) and packet level capture tools suffer from lack of scalability relative to link capacity. Monitoring high-speed links, such as OC-48 and OC-192 yields huge data volumes. Currently both CPU and storage capacities remain limiting factors. As link capacity and the number of ﬂows grow, maintaining individual counters for each individual ﬂow traversing a router becomes computationally and/or economically cumbersome to keep up with [1,5,6]. In order to address this issue, sampling has been used a proven statistical strategy for dealing with high volumes of network trafﬁc data [3]. It has the advantage of lowering the processing cost, the storage and hardware requirements in a network monitoring infrastructure. Like a quality control engineer, a network engineer needs to collect data at diverse time frames and places. Therefore, to make this process faster as well as accurate, one should rely on analyzing only a small, although relevant, subset of the network trafﬁc data. This sample is then
2678
S. Fernandes et al. / Computer Networks 52 (2008) 2677–2689
Fig. 1. Trafﬁc monitoring, ﬂow classiﬁcation and ﬁltering.
analyzed and a statistical quality verdict is given. In other words, one only needs to observe a small part of the trafﬁc to visualize the big picture. Fig. 1 shows how sampling can be used as a ﬂow ﬁlter capable of selecting a representative set of ﬂows only. By representative we mean those when selected, will give us an accurate view of the trafﬁc mix. We show in this work that the classiﬁcation strategy – also known as clustering – is primordial to achieve reduction of stored data but yet keeping its representativeness. Sampling may be applied during the capture (packet level) or after data summarization (ﬂow level). Fig. 2 depicts the envisioned beneﬁts of using sampling techniques for ﬂow trafﬁc data management. A typical scenario is made of a router that captures packets and builds ﬂows, a collector that retrieves and stores ﬂow records and an application with a Graphical User Interface (GUI) that generates reports out of the stored data. The numbers indicate the possible sources of improvements when deploying sampling techniques at different components of the network management apparatus. On-line sampling may be performed directly by routers at the time they are capturing packets and building ﬂows, whereas off-line sampling is performed after ﬂows are built by the router and transmitted to the ﬂow collector. If off-line sampling is used, optimizations may be obtained in the reduced storage requirements for the collector (#3), reduced data communication from the collector to the reporting application (#4) and reduced memory and processing requirements at the reporting application (#5). On the other hand, if
on-line sampling is used, optimizations may be obtained at the reduced processing and memory requirements for the router (#1) and reduced data communication from the router to the collector (#2). The processing and memory requirements will certainly be reduced at the router, since they preserve all ﬂows in memory until they are ﬂushed to the collector and the memory is cleared. If sampling is deployed, the router may detect that a given ﬂow does not need to be stored, so that the allocated memory space for that particular ﬂow can be released and the processing work of the remaining ﬂows will be performed faster. A variety of sampling strategies have been proposed recently for optimizing the packet selection process (for ﬂow accounting) [18–20] and ﬂow selection (for statistical analysis of the original trafﬁc). Sampling techniques may be divided into systematic, random and stratiﬁed sampling [4,24]. The simplest sampling process is uniform 1/N sampling (a type of systematic sampling), where one of every N packets is retained. Although this technique has been largely used, e.g. by CISCO’s Netﬂow in low-speed links, it does not always present adequate results since it has been shown that IP ﬂows usually have heavy-tailed distributions for packets and bytes [6]. In such a situation, the selected packets from the sampling process will be biased by the huge number of small packets and just a few will be selected from the tail, i.e., the bigger packets. Sampling may also be target dependent where for example only ﬂows above a given size or duration are retained for charging purposes or selective of given services such as VoIP and
Fig. 2. Envisioned beneﬁts of sampling.
S. Fernandes et al. / Computer Networks 52 (2008) 2677–2689
other P2P ﬁle sharing activities for content-based charging [7]. Some sampling strategies, however, rely on ﬂow information as they account only for relatively large ﬂows, also leading to a biased sampling process due to the unbalanced number of selected small ﬂows (also known as ‘‘mices”) and bigger ﬂows (also known as ‘‘elephants”) [25]. The main contribution of this work is the introduction of a new ﬂow classiﬁcation methodology which applies two well studied statistical techniques, namely stratiﬁed sampling and cluster analysis, in order to reduce the amount of collected trafﬁc that is necessary for characterizing the trafﬁc ﬂows. The role of stratiﬁed sampling is the intelligent grouping of the elements of the population in a number of strata (a set of samples), according to a key information from each ﬂow (e.g. ﬂow size) and in such a way that each stratum contains only ﬂows with certain charac

A Bigger Picture PDF Free Download