Vanice Canuto Cunha

Arturo A Z Zavala

Pedro R M Inácio

Damien Magoni

Mário M Freire

Mário M Freire

Mario M Freire

Classification of Encrypted Internet Traffic Using Kullback Leibler Divergence and Euclidean Distance

Keywords: traffic classification, encrypted Internet traffic, Kullback-Leibler divergence, Euclidean distance

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Internet traffic classification has been the focus of significant research efforts in the past two decades due to its importance for network management and security defense, since it may provide valuable information about the traffic metadata and the eventual underlying motivations [START_REF] Sun | Internet Traffic Classification Based on Incremental Support Vector Machines[END_REF], [START_REF] Dias | An innovative approach for real-time network traffic classification[END_REF]. The study of statistical methods to classify network traffic is justified by the fact that many machine learning techniques are supervised and then limited to the real time approach, as they require a new training model be created to a new classification each time new data is presented [START_REF] Sun | Internet Traffic Classification Based on Incremental Support Vector Machines[END_REF].

One of the major problems in classifying encrypted traffic is that the payload is encrypted, which makes difficult the analysis of the packet contents. Through statistical methods we can estimate, by means of empirical distributions, the behavior of the protocols, and with the help of divergences that show the similarities between two distributions, we can try to efficiently classify the applications that generate the Internet traffic under evaluation. This article proposes and evaluates the performance of two classifiers for encrypted Internet traffic using statistical methods applied to traffic flows: the Kullback Leibler (KL) divergence and the Euclidian distance. These two classifiers operate at a network flow level and make use of the relative frequency of the packet size to identify applications. KL divergence has previously been used for speaker identification/verification and image classification [START_REF] Pedro | A Kullback-Leibler Divergence Based Kernel For SVM Classification In Multimedia Applications[END_REF] and for detection of low-rate Distributed Denial of Service (DDoS) attacks [START_REF] Xiang | Low-rate DDoS attacks detection and traceback by using new information metrics[END_REF]. Euclidean distance has previously been used for optimizing an artificial immune system algorithm used for flow-based Internet traffic classification [START_REF] Schmidt | Optimizing an artificial immune system algorithm in support of flow-Based internet traffic classification[END_REF]. Here, both KL divergence and Euclidean distance are used to build classifiers without the need to combine them with other methods.

Related Work

Significant research efforts have been carried out on the subjects of identification and classification of Internet traffic. Part of them rely on statistics, see, e.g, [START_REF] Gomes | Identification of peer-to-peer VoIP sessions using entropy and codec properties[END_REF][START_REF] Neto | Real-time traffic classification based on statistical tests for matching signatures with packet length distributions[END_REF]. Recent research still focuses on making improvements using machine learning, such as [START_REF] Sun | Internet Traffic Classification Based on Incremental Support Vector Machines[END_REF]. In [START_REF] Dias | An innovative approach for real-time network traffic classification[END_REF], a classification module focusing on video streaming traffic, based on machine learning, is presented as a solution for networks that require real-time traffic analysis. In our work, we use real-world traces of encrypted traffic as well as Peer-to-Peer (P2P) applications such as edonkey, bittorrent, and gnutella. Some research works propose classifiers based on learning methods and corresponding signatures [START_REF] Tongaonkar | Towards self adaptive network traffic classification[END_REF][START_REF] Li | Network traffic classification via non-convex multi-task feature learning[END_REF]. A large number of research works, regardless of the classification method, make use of traffic flows or packet sizes (e.g, [START_REF] Gomes | Identification of peer-to-peer VoIP sessions using entropy and codec properties[END_REF], [START_REF] Peng | Imbalanced Traffic Identification Using An Imbalanced Data Gravitation-Based Classification Model[END_REF].

Statistical tests such as Chi-Squared and Kolmogorov-Smirnov were used for traffic classification in [START_REF] Neto | Real-time traffic classification based on statistical tests for matching signatures with packet length distributions[END_REF], representing the classes through the corresponding signatures and the empirical distributions. The entropy was also used to measure and represent important differences regarding packet heterogeneity [START_REF] Gomes | Analysis of Peer-to-Peer traffic using a behavioural method based on entropy[END_REF]. Exploring the heterogeneity of the packet sizes was accomplished by using samples obtained from a sliding window. For our work, we explored the characteristics of packet size, but using all the relative frequency flows and not just samples of the flow. Still in [START_REF] Gomes | Analysis of Peer-to-Peer traffic using a behavioural method based on entropy[END_REF], Gomes et al proposed an online classifier to separate traffic generated by P2P and non-P2P applications and a new method to identify VoIP sessions [START_REF] Gomes | Identification of peer-to-peer VoIP sessions using entropy and codec properties[END_REF].

Peng et. al propose in [START_REF] Peng | Imbalanced Traffic Identification Using An Imbalanced Data Gravitation-Based Classification Model[END_REF] a statistical classification approach that uses the Message Size Distribution (MSDC), which aims to identify the network flows precisely and the Message Size Sequence (MSSC) in real time. Such technique provided very good detection results, making a decision after inspecting less than 300 packets with a 99.98% precision, but do not display recall and F-Measure values. In [START_REF] Ertam | A new approach for internet traffic classification: GA-WK-ELM[END_REF], Extreme Learning Machine (ELM) methods were used to classify Internet traffic. The Extreme Kernel learning machine (EKLM) approach, an ELM approach, was applied to the data. In particular, a Genetic Algorithm (GA)-based software was implemented for selecting the parameters used in the Extreme Kernel learning machine with Wavelet (WK-ELM) algorithm, where the Wavelet function was used. A precision rate over 95% was reached.

Statistical Methods

Kullback-Leibler Divergence

The KL divergence or relative entropy is a distance measured between two probability distributions and was introduced by the mathematicians S. Kullback and R.A. Leibler in 1951 [START_REF] Cover | Elements Of Information Theory[END_REF], [START_REF] Delpha | Kullback-Leibler Divergence for fault estimation and isolation: Application to Gamma distributed data[END_REF], [START_REF] Galas | Expansion Of The Kullback-Leibler Divergence a New Class of Information Metrics[END_REF], [START_REF] Parveen | A Comparative Study of Traditional and Kullback-Leibler Divergence of Survival Functions Estimators for the Parameter of Lindley Distribution[END_REF]. These researchers started with the assumption that two probability distributions differ more or less according to the possibility of discrimination between them by means of a statistical test.

The KL divergence is a special case of a wider class of divergences. By using this method, we can infer a similar behavior, or divergence between two distributions [START_REF] Parveen | A Comparative Study of Traditional and Kullback-Leibler Divergence of Survival Functions Estimators for the Parameter of Lindley Distribution[END_REF]. Considering that D kl [p||q] is a function, p i and q i are two probability distributions, we have:

D kl [p||q] = pi log 1 pi - pi log 1 qi . (1)
Then, it can be assumed that the Kullback-Leibler divergence is represented by equation 2:

D kL [p||q] = N i=1 pi log qi pi , (2)
where D K L[p||q] >= 0 and D K L[p||q] = 0 if and only if p i (x) = q i (x), N defines the number of samples, i defines the number of the initial sample, pi defines the relative frequencies of the known class, qi defines the class relative frequency to be compared. Note that, despite being also known as a divergence, it cannot be considered as a distance metric, since it does not meet the symmetry property, i.e.,

D K L[p||q] = D K L[q||p].
We mapped the behavior of some protocols through distributions (relative frequency) and used this mapping to classify traffic, assuming that each known distribution is pi and each unknown distribution is qi. KL divergence was used to implement one of the classifiers described in section IV, more specifically the Statistical Analysis module.

Euclidean Distance

To calculate the distance between two traffic classes, one must consider the probabilities of each traffic class, in our case, p i defines the relative frequencies for all the discrete values i (possible packet sizes) of the traffic class 1, representing the known traffic class, while q i defines the relative frequencies for all the discrete values i (for possible packet sizes) of traffic class 2, representing the unknown traffic class. Therefore, the distance between both classes of traffic may be given by the following equation:

D E [p, q] = n i=1 (p i -q k ) 2 . (3)
In this work, we use Euclidean distance to compare its results with the ones obtained with KL and to test the efficiency of this method, when mapping the behavior of the relative frequency for each protocol. The Euclidean distance is used to implement the second classifier described in section IV.

Traffic Classification Using Kullback-Leibler Divergence and Euclidean Distance

This section details our approach to classify Internet traffic. We describe the traffic features used for the classification, the classifier architecture incorporating the divergences and system modules, as well as the rules implemented for traffic classification.

Features

It is possible to create a new set of data from the original data, which contains important information obtained through the new features found [START_REF] Shi | Efficient and robust feature extraction and selection for traffic classification[END_REF]. This new set of data can present a smaller number of attributes than those found in the original set, bringing us as a benefit a lower dimensionality. In order to obtain this new set of data, we extract some features of the original database, such as packet sequence numbers, IP source and destination, packet size, time [START_REF] Michael | Introduction To Data Mining, Person[END_REF], where we apply a different view of the original data to reveal its important characteristics. We call the original base, the trace of traffic that has been stored after collection of network traffic. We consider each flow as a time series, which generates a standard characteristic: the relative frequency of packet size per application. We observe that the flow (source IP and destination IP) of the application would give us a feature that could be extracted, the relative frequency of packet size in each flow. We believe that the distribution of sizes is of great importance to characterize the traffic, since it represents each protocol in a unique way, forming a signature for each one of them. Figure 1 illustrates the relative frequency distribution of packets for some available applications in our new dataset. As we can see, each protocol behaves in a unique way and exhibits a unique distribution, which we call a signature. We can use such behavior to measure the divergences to known distributions and to start the classification. The X-axis of fig. 1 represents the number of buckets. Buckets were defined with

Classification Approaches

Divergence or distance is the measure of separation between two distributions, it indicates how similar or different two traces are. But for this we must insert some parameters so that, with that there is the comparison. The architecture for our classification system contains four modules, as shown in Fig. 2(a): packet capture and pre-processing, statistical analysis and stored signatures, classification and validation.

Packet Capture and Pre-Processing This step deals with the traffic capture and storage. Traffic generation was done in the laboratory in a controlled environment, and the capture was performed with the tcpdump and windump tools. The files were stored in the .pcap file format. Then these file were converted to the .txt format. This conversion was done via command line with the command tshark -rsrcf ile.pcap -t. After the files were separated into several files by application with the command tcpdumpettnnrf ile.pcaphostIP orhostIP -wf ile.pcap.

First, we separated our dataset into individual trace files and collective trace files. We classify as individual trace files those in which we know by which applications they were generated. We separated into flow. We consider the application flow, source IP and destination IP, packet sequence and number of packets belonging to the same application and IP. Empirical model generation In this step, relative frequency files are generated that will feed the new base date. It was necessary to create file of relative frequencies corresponding to the known traces. These file were created by means of samples. To create the files with relative frequencies was developed a python script. For the generation of relative frequencies, values taken into account are the Maximum Transmission Unit (MTU), equivalent to 1514 bytes. This reference was crucial for the construction of the packet size histogram. Each byte packet was allocated in a sort of bucket. We take into account the size of 16 bytes to construct the histogram, so if we take the 1514 bytes and divide by 16 bytes, we will have an approximate value of 100 buckets, or intervals. Applying this logic to each flow, we are then able to calculate the empirical distributions -in our case, the relative frequencies.

Samples generation In this step, the program reads files from collective and individual folders and separate flows. The samples were generated from both individual and collective traces files. Each sample represents a relative frequency file generated for each protocol. The relative frequencies of the individual traces are stored in another dataset, as they will serve for signature identification purposes during the trace comparison phase. For flow grouping and separation, an application was built using the Python language, which allowed us to follow the entire flow and extract, with the construction of the histogram, the distributions of each flow. No feature was used to examine packages.

Statistical Analysis and Stored Signatures

In this step the distance and divergence based on the relative frequencies of each flow are calculated. In order to know if two traffic traces belong to the same class, we use the empirical distribution, in our case the relative frequency that each trace has, and compare the two frequencies by applying the KL or Euclidean calculation, and obtaining a distance as output. We begin the comparison phase between the distributions, where in this phase, the divergences are used, as shown in figure 2(a). In this step we consider the generated and separated files in the pre-processing module and rename these files in samples pi and qi. Now, pi for individual flow files and qi for collective flow files. Relative frequencies individual are stored as a signature and compared to Relative Frequencies collective using the distances of KL and Euclidean. For calculating distances, we choose which method we will apply, either Kullback-Leibler or Euclidean, and compare the relative frequency lists pi and qi generated. After this comparison, we have the values of the distances found between the two lists. This distance alone does not represent anything, therefore, in the classification step it is necessary to make use of heuristics. Note that, individual relative frequencies are stored as a signature and compared to collective relative frequencies using the KL and Euclidean distances.

Classification and Validation

The classification of flows based on rules is made in this step. Note that, at this stage, we already have all the distances calculated between the flows. For divergences, the closer to 0 the most similar the two protocols are, the closer to 1, the most different the two protocols are likely to be. After the calculation, and having the values of the obtained distances, classification rules have to be created so that the classifier can make a decision. These rules are based on statistical heuristics after several iterations of distance calculation.

Initially, the rules for classification were based on dissimilarity values, where dissimilarity can be defined as follows: 0 if the attribute values match and 1 if they do not match. Since we will not always have distances equal to 0, or equal to 1, we need to find a cut-off threshold for the classification to be done more efficiently. For the cut-off, after debiting all distances, we created two lists to insert accepted and rejected flows according to established rules.

As we mentioned earlier, we need a threshold to know when the flow could be accepted or rejected. At first, we used a heuristic where we applied a range of intervals so that flow distances could be accepted if they were within the interval or rejected otherwise. After several tests, we found that in the rejected list there were flows that could have been accepted, but given the cut-off threshold, had been rejected. So we found that this methodology to accept or reject the flow would not work in our case.

Next, we defined another rule, this time making use of the average packet size found in each flow and also adding their standard deviation. Unfortunately, the values on the rejected list remained high. It is worth mentioning that when we checked the rejected lists, there were many flows that should have been accepted instead.

After several analysis, we chose to use all the distances after the calculation of all distances to calculate the distance between the calculated distances to insert in our list of accepted flows the distances were smaller, compared to the others.

We also decided to use the standard deviation (SD) of the distances calculated by the samples as the cut-off threshold, inserting in our distance list all flows that were in the interval [average, SD]. Using this technique, we were able to significantly reduce cases of false positives and false negatives, but it was not enough to deliver satisfactory results.

In order to create an efficient rule, we calculate the relative frequency of a given known protocol that is in our signature database, and compare it with all relative frequencies of unknown protocols. After this comparison, several distances will be generated. The first step is to select the minimum distance among the calculations to apply the classification rule.

The second step, after several and continuous tests with each protocol, was defining acceptance baseline values that would define five different minimum ranges. For each range value, the pre-calculated minimum distance of each protocol must necessarily be within 0 and the current range of the loop. Once the classification is over, the one yielding the best F-measure will be returned, as per auxiliary variables within the classification loop.

The MaxR variable was created to store the minimum range of the best result, while MAxMatrix variable was created to store its confusion matrix. The maxFmeasure variable, initially set as -1, will then store the best f-measure among the results. Classification rules are illustrated in the flowchart shown in Figure 2(b) .

Performance Evaluation

After the classification process of the samples, we checked and validated the results of the classification using the ground truth. For this, we created two new lists: in the first list we have the number of items classified as accepted and that were actually found in the mapping dictionary according to the IP source and IP destination corresponding to each protocol, and in the second list we have the number of items classified as rejected. Note that even though a distance is in the accepted list, the flow may not actually belong to the corresponding protocol, and even though it is in the rejected list, the flow might actually belong to the corresponding protocol.

Dataset and Ground Truth

For the study and analysis of the traffic, it was necessary to collect traffic traces and to build a database containing the traces to be analyzed. The dataset is composed by traces, generated by different Internet applications and services. Network traffic used in this analysis was captured next to the source where it was generated, obtained in a controlled environment, where only one application was running in a certain computer. All of the traces were collected by using the TCPDUMP and WINDUMP tools, implemented by the capture libraries: libpcap in the Linux platform, and Winpcap in the Windows platform. This way, we observed the properties both scenarios and established the ground truth of the traffic records. In order to analyze the empirical distribution of the traffic packet size, an application was built to create the relative frequency distribution for each collected traffic. In this study, we chose services or applications that are widely used, heavy bandwidth consumers or raise more challenges from the perspective of traffic and network management, ending up with a set of services with varied characteristics. The classes considered for the traffic analysis were commonly used in the Internet, as listed below:

-Web browsing: browsing of general web pages, excluding media streaming.

-On-demand and live streaming: HTTP and Flash-based, RTSP, MMS, etc.

-P2P streaming: PPStream, TVUPlayer and SopCast.

-P2P file-sharing: BitTorrent, e-Donkey, and Gnutella.

-VoIP: Skype, Google Talk, Session Initiation Protocol (SIP) traffic.

-File transfer: FTP and SFTP transfers.

-Remote session: Telnet and SSH sessions. In this work, "HTTP download" is used to refer to a long and continuous download of a large file using HTTP, while "Web navigation" is used to refer to the common activity of visiting Web pages through a Web Browser. The used dataset includes a total number of 92.317 traffic flows, corresponding to 35.317.091 packets and approximately 27.37 GB of traffic. The time to acquire all the datasets is 61h. Datasets were divided in three as described in table 1.

Ground truth is widely used by researchers who collect their own traffic traces to test the accuracy of their solutions. In our work it is possible to establish ground truth because traffic was collected in a controlled environment where each computer was running only one application. With this, we can map exactly the trace for a given application, calculate the relative frequency of the trace and compare it with the output of the classifier. The individual traces were used for the generation of our ground truth and the files with the collective traces were used for our tests.

Performance of the classifier

To address these issues, we used the confusion matrix, which allows us to obtain the performance and prediction of the classifier, based on the values of TP, TN, FP and FN. For the values of TP, the classifier added them to the list of accepted flows which, after the analysis and classification, are considered to belong to that flow. For FP values, we have the protocols erroneously classified as belonging to the flow. For the values of TN, the classifier correctly understood that the protocol did not belong to the flow, inserting it in the accepted list. Finally, for FN, the classifier erroneously understood that the current protocol did not actually belong to the flow, inserting it in the rejected list. For performance evaluation, we use the classical performance metrics defined in machine learning textbooks: accuracy, precision, recall and F-measure.

Table 2 presents the accuracy, precision, recall and F-Measure for the Kullback-Leibler and Euclidean methods for all 8 classes tested. After evaluating the performance of the classification proposing the use of Kullback-Leibler divergence, we compared the performance with methods already found and tested in the literature [START_REF] Schmidt | Optimizing an artificial immune system algorithm in support of flow-Based internet traffic classification[END_REF], [START_REF] Tavara | Parallel computing of support vector machines: A survey[END_REF], [START_REF] Marwala | Support Vector Machines[END_REF]. For our comparison, we use of the Euclidian distance and Support Vector Machine (SVM). For testing with SVM we use the sklearn-import-svm [START_REF]scikit-learn user guide Release 0.21.2[END_REF] function provided by the Python library and applied it to our dataset with the default parameters, except for the Self parameter, which for our case we use C = 50. The largest problems encountered in setting up the SVM model were how to select the kernel function and its parameter values. When there are large values of C, the optimization will choose a smaller-margin hyperplane if that hyperplane does a better job of getting all the training points classified correctly. We use four different kernels, which are linear, polynomial, sigmoid, and RBF kernels. For testing using SVM, we use the training module and change the Statistical Analysis KL module to Classification-SVM. A summary of the results obtained from the classification using SVM is shown in table 3. The method using the SVM RBF kernel and the sigmoid kernel could not classify the dataset relative frequencies used in this article. Results achieved were too low or close to 0. For the category of Web browsing traffic, the SVM method has a classification capability, the Euclidean and KL methods presented very similar results, Kullback-Leibler having higher Recall and F-Measure values. For the HTTP download category, the SVM method was unclear. Although the KL method had higher values than the SVM method, the values of Recall and F-Measure are still below acceptable values to state that for this type of application the method can classify this traffic category efficiently.

For on-demand and live streaming, the SVM method obtained results below the values found for the statistical methods. Analyzing the results, we realized that for this type of traffic, both KL and Euclidean methods, can classify efficiently and effectively. The results show that both methods are far superior than any of the SVM kernels.

For P2P streaming, linear, polynomial, and sigmoid SVM kernels have at least one metric considered reasonable for classification, but overall they are insufficient. This leads us to conclude that for video and video streaming traffic, the KL and Euclidean methods are efficient for identification and classification of these applications.

For P2P file-sharing, the KL and Euclidean methods gave excellent results for the precision and F-Measure metrics and good results for the Recall metric. The SVM linear kernel yielded results that are considered excellent.

For VoIP classification, the linear kernel SVM method presents significant results. KL and Euclidean methods gave excellent results for this type of traffic, reaching 100 % precision, Recall and F-measure results, which means that for this application the KL and Euclidean methods were very promising.

For the File Transfer traffic category the KL and Euclidean methods can also, given the obtained values, present an excellent classification capacity. For Remote session applications, the values achieved by the KL and Euclidean methods were 100% for the Accuracy because, although we have it mapped in our individual database, there are no corresponding files in the collective test database. The classifier states that all tested files do not contain Remote sessions, which in our analysis is correct, since we do not have any.

By making a comparative analysis between the statistical methods, we conclude that KL and Euclidean methods obtain the same results for most cases.

When comparing the F-Measure results obtained in both, we see that for the HTTP Download and Web Browsing traffic only, the values obtained by the KL method were higher, but we cannot say that this method is superior to the Euclidean one, given that for the other results, the values were the same or relatively similar. It is interesting to note that SVM is considered an excellent classifier in the literature, but when we do not have many features, we notice from the results that SVM does provide satisfying results. Therefore, building network traffic classifiers using statistical methods can still be considered a viable alternative for encrypted traffic.

Resource Usage

The experiments were executed on a 64-bit Linux desktop computer, equipped with an Intel (R) Core (TM) i7 CPU 2.93GHz, 6GiB system memory and a PCI Express Gigabit Ethernet Controller based on the RTL8111 chipset.

For computational analysis, the psrecord [25] tool is used. This tool records the core and memory activities of a process. In order to measure the computational performance of each method, we used the activity of the process that the method refers to. We did not use packet number or host/port, as this data was used only as information to convert the raw database into relative frequencies. When we look at fig. 3(a) and fig. 3(b), we find that memory usage remains stable whatever the processing consumption of the chosen classifier.

When the classifier is started, the CPU and memory time start at 0. If we observe the CPU usage over time, we see that KL and Euclidean classifiers both use a similar CPU percentage to process the information and compare the relative frequencies. Although not shown, the SVM classifier requires more CPU especially at the beginning of the process. Regarding the memory usage over time for each statistical classifier, they are very close, being slightly larger for the KL classifier, because KL is more demanded.

Conclusion

Our results for Internet traffic classification were presented using Kullback-Leibler (KL) divergence, Euclidean distance and SVM. According to the results obtained, we can conclude that the SVM method with kernel set to default parameters is not effective to classify flows based only on packet size. SVM RBF was not efficient in any classification. Linear SVM was only efficient for classifying P2P streaming. The SVM sigmoid was efficient for classifying P2P streaming and VoIP. The SVM polynomial was efficient for classifying P2P streaming, P2P file sharing, and VoIP. In contrast, the KL and Euclidian methods were able to classify all tested applications, standing out in the streaming and P2P classification, where for almost all cases it was efficient to identify them with a high precision.

We conclude that both the KL divergence and the Euclidean distance were efficient and that, in cases where the KL divergence was superior, it was not significantly better than the Euclidean distance. The performance of the statistical method is considered good as long as CPU usage remains almost constant when packets are being processed and analyzed. As for memory usage, it fluctuates according to the requests of each method.

Because these results are based on an approach that uses only packet sizes, it can be integrated with other methods to improve overall classification as it is a very promising classifier for high-speed network taps where traffic is encrypted. For future work, we intend to evaluate other statistical divergences indicators by performing new tests on encrypted traffic.

Fig. 1 :

 1 Fig. 1: Relative frequency of packet size per application, extracted through the sampling process, for SSH and HTTP Web Browsing.

Fig. 2 :

 2 Fig. 2: Proposed classifier: (a) Architeture; (b) Flowchart of rules process.

Fig. 3 :

 3 Fig. 3: CPU and memory consumption from the beginning of the analysis of the trace to end of the classification (execution time) for the classifiers based on: (a) Euclidean distance; (b) Kullback-Leibler divergence.

Table 1 :

 1 Dataset Characteristics.

	Dataset Volume (GB) TCP (%) UDP (%)
	Dataset 1	8.80	78.35	21.59
	Dataset 2	8.60	82.77	17.18
	Dataset 3	7.97	77.13	22.84

Table 2 :

 2 Performance results with Kullback-Leibler divergence and Euclidean Distance.

	Traffic Category\Protocol	Methods
		Kullback-Leibler	Euclidean
		Acc. Rec. Prec. F-M. Acc. Rec. Prec. F-M.
	Web browsing	99% 74% 100% 85% 99% 67% 100% 80%
	HTTP download	99% 83% 100% 90% 99% 66% 100% 80%
	Streaming On-demand and live 100% 100% 100% 100% 100% 100% 100% 100%
	P2P streaming	99% 86% 100% 92% 99% 85% 100% 91%
	P2P file-sharing	99% 76% 100% 86% 99% 73% 100% 84%
	VoIP	100% 100% 100% 100% 100% 100% 100% 100%
	File Transfer	100% 100% 100% 100% 100% 100% 100% 100%
	Remote session	100% 100% 100% 100% 100% 100% 100% 100%
	Legend: Acc: Accuracy, Rec: Recall, Prec:Precision, F-M: F-Measure

Table 3 :

 3 Performance results with SVM Linear and Polynomial kernels.

	Traffic Category\Protocol	Support Vector Machine -SVM
		Linear		Polynomial
		Acc. Rec. Prec. F-M. Acc.	Rec. Prec. F-M.
	Web browsing	74% 74% 74% 74%	0%	0% 0% 0%
	HTTP download	81% 82% 35% 4,9%	0%	25% 10% 15%
	Streaming On-demand and live 57% 58% 57% 57% 0,90% 1% 9% 2%
	P2P streaming	99% 99% 99% 99% 0,57% 10% 97% 10%
	P2P file-sharing	98% 98% 97% 98% 0,0005% 0% 100% 0%
	VoIP	100% 100% 100% 100% 0,22% 2% 100% 4%
	File Transfer	0% 0% 0% 0%	0%	0% 0% 0%
	Remote session	0% 0% 0% 0%	0%	0% 0% 0%
	Legend: Acc: Accuracy, Rec: Recall, Prec:Precision, F-M: F-Measure


Leandro Batista De Almeida

Damien Magoni

Philip Perry

Eduardo Cunha De Almeida

John Murphy

Anthony Ventresque

Multi-Layer-Mesh: A Novel Topology and SDN-based Path Switching for Big Data Cluster Networks

Keywords: Big data, Hadoop, network topology, SDN

Big Data technologies and tools have being used for the past decade to solve several scientific and industry problems, with Hadoop/YARN becoming the "de facto" standard for these applications, although other technologies run on top of it. As any other distributed application, those big data technologies rely heavily on the network infrastructure to read and move data from hundreds or thousands of cluster nodes. Although these technologies are based on reliable and efficient distributed algorithms, there are scenarios and conditions that can generate bottlenecks and inefficiencies, i.e., when a high number of concurrent users creates data access contention. In this paper, we propose a novel network topology called Multi-Layer-Mesh and a path switching algorithm based on SDN, that can increase the performance of a big data cluster while reducing the amount of utilized resources (network equipment), in turn reducing the energy and cooling consumption. A thorough simulation-based evaluation of our algorithms shows an average improvement in performance of 31.77% and an average decrease in resource utilization of 36.03% compared to a traditional Spine-Leaf topology, in the selected test scenarios.

I. Introduction

The last decades have seen an exponential growth in the volume of data to be analyzed by computational systems. From Data Warehousing to IoT and Machine Learning systems, the processing needs for large volumes of information has consistently grown. To meet that demand, Big Data systems were developed such as Google File System, MapReduce, Hadoop, and several other tools in the following years. The Big Data ecosystem is composed of several tools and frameworks, that cooperate in order to provide the most appropriate solution for each particular problem, creating a multi-product environment.

There are several components involved in the performance metrics of a Big Data job execution, and the network is one of them. As stated by its name, the data volume is big, beyond the capabilities of a single server, or even a small cluster. For this reason, almost all Big Data systems use some form of distributed file system, in order to cope with both the volume of data, and the need of reading the data at fast pace. The Hadoop Distributed File System is generally used not only by Hadoop, but also by other systems, such as Spark and Impala. The usual Hadoop stack is composed of HDFS at the bottom, the job engine (like Hadoop YARN or MapReduce) over it, and the application layer on the top, with Hive, Spark or MapReduce programs solving the user queries. This stack is shown in Figure 1. In these huge systems, there is a constant pursuit for performance, since the execution time for jobs can take several hours, even days [START_REF] Villanustre | Big data trends and evolution: A human perspective[END_REF]. In this environment, even a minor improvement in performance can save a considerable amount of execution time. The energy consumption and cooling costs are also directly influenced by CPU processing required for running the jobs [START_REF] Hammadi | A survey on architectures and energy efficiency in data center networks[END_REF]. Although Hadoop tries to run jobs locally (by reading data from local storage),the total workload of concurrent jobs will eventually have the jobs require chunks of data spread out on several servers in different racks. This will create a bottleneck if the interconnection network throughput is not able to handle the large data transfers needed for job completion.

To address this issue, we have developed a novel network architecture, based on a Multi-Layer-Mesh topology, and a SDNdriven forwarding algorithm that can use information about the job execution from the Hadoop main server to organize the network traffic for optimizing the use of available network paths. Our proposal can decrease the number of network equipment used, and increase the network performance for Big Data job execution. Thus, it reduces costs both in equipment acquisition and maintenance, and in energy consumption and cooling. The switches used in our topology must be SDNenabled and are configured by a SDN controller.

The rest of the paper is organized as follows. Section II presents the state of the art in Hadoop clusters, DCN topologies and Hadoop simulators. Section III details our novel network topology proposal. Section IV details the experimentation that we have carried out for validating our proposal.

II. Related Work

A. Data Center Topologies and Hadoop Clusters

A Data Center (DC) concentrates a large amount of servers in one physical place. Those servers need to be optimally interconnected to ensure proper communications both intra-DC and inter-DC. There exists more than 40 different types of topologies for setting up a DC network (DCN) [START_REF] Hammadi | A survey on architectures and energy efficiency in data center networks[END_REF], [START_REF] Chen | The features, hardware, and architectures of data center networks: A survey[END_REF]. These topologies are usually characterized by the type of switches used (i.e., electronic, optical or wireless) and whether they are switch-centric (i.e., many links between switches) or servercentric (i.e., many links between servers). They are usually statically implemented in hardware. In 2017, a system for implementing a convertible DCN architecture has been proposed in [START_REF] Xia | A tale of two topologies: Exploring convertible data center network architectures with flat-tree[END_REF] to overcome this issue. It can dynamically change the network topology in order to setup architectures optimized for diverse workloads. It requires the use of small port-count converter-switches. Hybrid electro-optical systems have also been recently proposed to improve performances, such as the Hybrid Fat Tree (HFT) [START_REF] Guelbenzu | Hybrid fat-tree: Extending fat-tree to exploit optical switch transparency with wdm[END_REF]. By introducing wavelengthdivision multiplexing (WDM) and optical switches in Fat-Tree like topologies, the authors find that these technologies reduce the required number of switches by 45% in their minimum hybrid networks. Inter-rack optical rings have also been proposed for improving the overall throughput of the DCN, by using flexible spectrum allocation with ROADMs [START_REF] Zhang | Elastic optical ring with flexible spectrum roadms: An optical switching architecture for future data center networks[END_REF].

Software-Defined Networking (SDN) is increasingly being deployed in modern DCs and can benefit big data applications in many ways [START_REF] Cui | When big data meets software-defined networking: Sdn for big data and big data for sdn[END_REF], including big data processing, data delivery, programming at runtime for optimizing big data applications, scientific big data architectures, and more specifically for Hadoop scheduling as shown in [START_REF] Qin | Bandwidth-aware scheduling with sdn in hadoop: A new trend for big data[END_REF]. By measuring and analyzing the DC traffic, such as presented in [START_REF] Kandula | The nature of data center traffic: Measurements & analysis[END_REF], topologies and flows can be optimized through dynamic network reconfiguration, thanks to SDN technology. A Hadoop cluster is a computational cluster designed for storing and analyzing huge amounts of unstructured data. These clusters are usually hosted in data centers, and thus have similar network topologies, although their traffic patterns may be different from other applications. Several solutions based on SDN technology have been recently proposed to improve Hadoop performance. Narayan et al. use OpenFlow to provide better link bandwidth utilization for traffic exchanged during the shuffle phase of MapReduce [START_REF] Narayan | Hadoop acceleration in an openflow-based cluster[END_REF]. This, in turn, decreases the time that Reducers have to wait to gather data from Mappers, and therefore shorten the completion time of Hadoop jobs. Similarly, Nejad and Majma have proposed a method based on alpha-beta filter to improve the efficiency of MapReduce in Hadoop clusters by leveraging SDN [START_REF] Nejad | A modern method to improve efficiency of hadoop and mapreduce cluster using software-defined networks technology[END_REF]. Ghalwash et al. investigate the throughput and execution time of Hadoop read/write and sorting operations [START_REF] Ghalwash | Software-defined extreme scale networks for bigdata applications[END_REF]. They evaluate different network sizes of a Fat-tree topology of OpenFlow switches and they observe improvements for some of their topologies when using OpenFlow rather than regular L2 switching. Our work is different from these works as we propose a new physical topology as well as a SDN-driven forwarding algorithm over it. We aim at reducing the number of network components as much as improving the Hadoop job completion times.

B. Big Data Simulators

Most of the Big Data software and frameworks are designed to run in clusters with hundreds or even thousands of nodes. Testing new technologies can be a difficult and time costly process, and usually those resources are not available, or their use could be more expensive than the available budget. This is the case of this research, when we need to test how the data movement will behave in a multi-rack cluster environment, with different cluster sizes, and with a novel network topology and switching protocol.

And in order to execute our experiments and test the presented hypothesis, we need set several parameters for the scenarios to be simulated, and the simulator should be capable of providing data about the network behavior in the jobs' reading phase, and the related actions, like the distribution of blocks and task placement.

Based on these premises, we developed a simulator to help on researching on Big Data systems performance, the BigDataNetSim [START_REF] De Almeida | Bigdatanetsim: A simulator for data and process placement in large big data platforms[END_REF], tested against physical cluster to assess the accuracy, with published results. This simulator was used for the experiments on this research.

III. The Multi-Layer-Mesh Topology

The main contribution of this research is a novel network topology based on a collection of layer-1 (L1) full meshes interconnected via a layer-2 (L2) mesh. Theoretically, we could have any number of layers, but in this paper we limit the topology to two layers. All switches are located at layer 1. They are partitioned in m groups of n switches. In each group, the n switches form a full mesh: each switch is connected to all the others in the group.The links used inside this full mesh are called intralinks. Then, meshes are interconnected by using links connecting some or all switches from one mesh to some or all switches in all other meshes. These links are called interlinks and they form the layer-2 mesh. Their number is a parameter of the topology. There are no switches at this second layer. We could add a third layer by partitioning the layer-1 groups into p layer-2 supergroups of q groups. Layer-2 interlinks would interconnect groups in a supergroup, while layer-3 interlinks would interconnect the supergroups themselves. This topology is oriented to Big Data clusters with data intensive applications, such as data analysis and machine learning.

On top of the physical topology, a SDN enabled forward algorithm is used, obtaining information about the big data application running in the cluster and setting up the most appropriate paths for each communication link between the nodes.

A. Problem Definition

Nowadays, the general scenario for Big Data clusters shows clusters being used for several applications at the same time, due to the involved costs to build and maintain such a large installation. It is common to have several tools and frameworks sharing the same cluster infrastructure, in a multitenant configuration. The data sources are also shared by many applications, and the job results are used as inputs for new jobs as well [START_REF] Villanustre | Big data trends and evolution: A human perspective[END_REF]. This causes a high level of data reuse, creating zones of the data space labeled as "hot data", shared by many possible concurrent jobs.

In a general way, the data is stored in a distributed fashion in a big data cluster. As the data volume is large, the information is divided into smaller portions and stored in a large array of nodes. This is how the Hadoop Distributed File System (HDFS) works [START_REF] Shvachko | The hadoop distributed file system[END_REF], by dividing the files in blocks of 128 MB (default value), and by distributing the blocks in the cluster. Besides, HDFS creates replicas of each block (3 replicas, by default) to ensure data availability and fault recovery. When some job requests a file, the HDFS master node sends to the Application Master, the location of all blocks and replicas of that particular file, and the processing manager decides which block/replica to read.

Hadoop v1 used MapReduce as the main processing manager, and starting with Hadoop v2, YARN (Yet Another Resource Negotiator) is used to manage how a job will be executed, how a job will be divided into smaller tasks, and how to read information from the distributed file system. In general, YARN tries to start a task (a subdivision of a job) on the same node where the information about to be read is located, avoiding any loss of time due to network transfers. As the number of possible tasks running in each node is limited (based on how many concurrent threads can be started, related to the number of CPU cores), this strategy works well when the cluster has a lower number of users and concurrent jobs.

When YARN needs to read a particular block of information to process the data, and all the available cores of all nodes containing that data are depleted, the system starts the task on another node, and reads the information across the network. Initially, YARN tries to start those tasks at least in the same rack where the information is stored, but eventually -as the load increases -tasks will be started in another rack, increasing the network transfer delay. This is shown in Figure 2, with a Local task (reading from the local storage) is shown, compared with a Rack task (reading from the storage of another node in the same rack) and a External task (reading from another node in another rack), with the increased delays for each step.

In the end, as the load increases, the network is put under pressure, and regardless of the used application framework (Spark, MapReduce, Hive, Impala), the completion time for the jobs will increase. The worst case scenario is when the cluster receives multiple concurrent jobs accessing the same data sources (hot data), thereby increasing the chances of reading tasks having to use the network to read the files.

There are several network topologies designed for data center and cluster environments [START_REF] Chen | The features, hardware, and architectures of data center networks: A survey[END_REF], and some of these topologies are adequate for clusters, like Fat Tree or Spine-Leaf, however, those topologies don't scale well as the number of nodes increases. In Big Data clusters, the number of nodes can easily reach a few thousands of nodes for some scenarios. Then, the related network infrastructure must be designed properly. For a hypothetical cluster with 1000 nodes divided in 50 racks containing 20 nodes each, a regular Spine-Leaf topology requires a number of spine switches up to half the number of racks, in order to maintain the traffic at fair levels, even under high load conditions.

B. The Multi-Layer-Mesh Topology

To solve the described problem, a novel network topology is proposed -the Multi-Layer-Mesh (MLM) topology -along with a switching protocol that uses information from the application (big data application manager). The main goal is to reduce the amount of resources used (equipment and energy) and increase performance.

As described earlier, the physical network topology is based on a partitioning of all the switches in the network into a given number of L1 full meshes. Additional links, called interlinks, interconnecting those L1 meshes together form a global L2 mesh.It is a full mesh for the L1 meshes in the sense that each L1 mesh has at least one link connecting it to each other L1 mesh. The actual racks with the cluster nodes are connected to switches belonging to L1 meshes. An example network can be seen in Figure 3 with every L1 mesh containing 5 switches. In this case, only one interlink between each L1 mesh pair is presented, for the sake of clarity.

There are two parameters to be configured, in order to increase the number of available paths and reduce the bottlenecks: (1) the number of switches in each L1 mesh, and (2) the total number of interlinks between any pair of L1 meshes.

On this example network, the number of intralinks in each L1 mesh is 10 and the total number of interlinks from each mesh to each other is 6, effectively creating a full mesh of meshes. It should be noted that the number of interlinks between a given pair of L1 meshes can be much more than 1 thus leading to more interlinks than just n(n -1)/2 (with n the number of L1 meshes). As links are cheaper than equipment -considering copper connections -this topology reduces the amount of used resources, while keeping the traffic at acceptable levels, eventually surpassing a regular Spine-Leaf topology.

To determine the paths to be used, a switching protocol was designed, based on information from the big data cluster controller, in order to prepare the traffic for the upcoming transfer tasks. The topology is independent from the big data underlying technology, by the use of drivers designed to cope with the singular properties of each used technology. In the experiments of this research, the system was connected to a Hadoop installation, using HDFS as storage, and YARN as the application manager. With the proper driver developed, this system is able to use different storage technologies (Cassandra, S3) and application managers (Spark, Tez) as well. The proposed system reads information about the jobs submitted to the Hadoop cluster, and prepare the paths accordingly. This architecture is shown in Figure 4.

C. Proposed Construction Algorithm

The path table construction algorithm is based on Dijkstra's shortest path algorithm, in a tracing algorithm to generate unique and balanced paths between a given pair of nodes, using one of the available interconnections between the layer-1 meshes. This is based on the fact that racks connected to the same mesh have always a shortest path of distance 1, and the maximum path distance in interconnections is 3, and the minimum is 1. The algorithm goal is the keep the actual distance as close as possible to the minimum, based on the features of a particular set of parameters. There are two algorithms used in the research, one to create the paths table, and another to select the proper path for each communication flow. Those algorithms are described below.

1) Path Table Creation Algorithm:

The initial flow table will be created by the Topology Controller based on the shortest paths between each pair of switches in the cluster. As the maximum path is 3, there are potentially more than one path with cost over 1 for a particular pair of switches. For this situation, a list with all the paths with same cost for each pair is generated to help in the path selection algorithm.

A list with all possible hops in the paths is also created. This list contains all possible segments in the network, and counters to keep track of the traffic in each hop.

2) Path Selection Algorithm: When the jobs starts to run, the Topology controller obtains the data about each task in the job (which node is processing the data and which node is storing the data) from the Hadoop controller, and orders the SDN controller to setup a flow for that particular communication pair using the most appropriate available path. Although this setup process take some time to happen, the start of a Hadoop task is also time consuming, so, when the actual task is starting, the corresponding flow is already configured.

The algorithm is based on the following steps, as shown in Algorithm 1. As the local and rack tasks are treated by the same switch or no switch at all, the algorithm focus only on the external tasks, when communication between the racks is needed. For each new external reading task from a Hadoop job, obtain the information about the processing node and the data node from Hadoop controller. Verify if there is a path with cost 1 between the racks containing the two nodes, and select it. If there is no direct connection between the two switches, select the least used least cost path from the list of unique paths between the top of rack switches containing the pair of nodes.

IV. Experiments

Using our simulator, three cluster sizes were tested, using a configuration commonly found in real clusters.

A. Usage of BigDataNetSim Simulator

The common use case for our simulator in this research is to generate a cluster of a particular size, with a particular network topology, create the file system in it, populate the file system with files of a specific size, submit a given number of concurrent jobs, generate the metrics for the network usage and generate the reports about the simulation.

This research focuses on the reading phase of Big Data jobs because it is a time consuming one, and it is generally the only common phase regarding the Big Data technology running on top of it (e.g., Hadoop, Hive, Spark, Impala, etc). The subsequent phases of data processing could vary depending upon the chosen framework and make the simulation task complex or not feasible. In addition, the reading phase is the Algorithm 1: Path Selection Algorithm // considering i,j as processNode and dataNode input : jobT asks: List< task >, uniquePaths i, j :

List< path >, steps: List< path i, j > output: selectedPaths task,i, j : List< steps > for task ∈ jobT asks do // get processing and data node from task processNode, dataNode ← getNodePair(task) if cost(uniquePaths processNode,dataNode ) = 1 then // get the path between the nodes using switches inside same layer-1 mesh or with direct connection path ← directPath(processNode, dataNode) else // find path with less cost cost ← minimunCost(processNode, dataNode) path ← lessU sedPath(processNode, dataNode, cost) // add select path to list of used paths selectedPaths ← path // increases the usage counter of each hop in path hops ← increaseHopCount(path) return selectedPaths most demanding in terms of network usage, as the subsequent phases generally only transmit results (partial or full), with much less volume. As the simulator supports different network topologies and protocols, it is possible to obtain the network metrics from the reading phase in a faster way.

The main parameters used on this research are:

• Number of layer-1 meshes: number of first level fully meshed groups of access switches in the topology. • Number of access switches per layer-1 mesh: number of Top of Rack (ToR) switches, each one connected to the full mesh (there is one access switch per rack). • Number of nodes per rack: number of nodes (i.e., servers) per rack. • Number of cores: number of available processing slots (CPU cores) in each node, this number represents how many simultaneous tasks a node can run. • Number of links between two layer-1 meshes: how many inter-(layer-1) mesh connections (i.e., interlinks) from switches in one mesh to the switches in another mesh. • Spine-Leaf network parameters: how many spine switches are in the spine-leaf topology.

B. Experimental Setup

In the experiments, we used the simulator to assemble 3 different cluster configurations, and executed the tests considering the file distribution and number of concurrent jobs for each case. We are considering that some portion of the input data is used more often than the rest. This is the common scenario in big data processing [START_REF] Chen | Interactive analytical processing in big data systems: A cross-industry study of mapreduce workloads[END_REF], where most of the time, the jobs are reusing the same data in several executions, or reusing output from previous jobs. In the experiments, this is a configurable parameter, and the jobs concentrate in reading from the hot data. For the majority of concurrent jobs in a multi-tenant cluster [START_REF] Chen | Interactive analytical processing in big data systems: A cross-industry study of mapreduce workloads[END_REF], this is the common situation, and our topology and algorithms are designed to improve the performance and decrease the delay for this type of scenario. All the experiments used the HDFS default values of 128 MB for the block size and 3 for the replication factor. Those are the values usually found in real clusters, and used for general data.

The network connecting the nodes and the racks is a Gigabit Ethernet, with delays of 1 ms per switch, frame size of 1518 bytes and not considering the delays caused by the TCP receiving buffers (usually with 64 KB) due to the dynamic buffering option found in modern Linux operating system kernels.

Three sizes of clusters were used in the tests:

• 500 nodes (25 racks with 20 nodes each)

• 1000 nodes (50 racks with 20 nodes each)

• 2000 nodes (100 racks with 20 nodes each) For these clusters, the following graph configurations were used in the tests:

• 500 nodes: 5 layer-1 meshes with 5 racks in each.

• 1000 nodes: 5 layer-1 meshes with 10 racks in each.

• 2000 nodes: 5 layer-1 meshes with 20 racks each. The number of nodes per rack were chosen based on the regular size of a network cabinet and the conventional number of ports found in Ethernet switches.

The maximum number of concurrent jobs was set to 64 for the tests, with values set to 1, 16, 32, 48 and 64 for the tests. The one single running job case was considered, as specific clusters are sometimes used to solve one job at a time, using all the available resources.

In the spine-leaf topology, the number of switches in the spine is set to half of the number of available racks, ensuring enough parallel paths to keep traffic in adequate conditions. In Multi-Layer-Mesh topology, the number of switches is equal to the number of access switches used in spine-leaf topology. There are no core or spine switches, then, the number of required equipments is less than a regular spine-leaf.

All the results are average values from 100 consecutive runs, to avoid bias due to the utilisation of random variables used to define data placement and so on.

The dataset size used in the experiments is calculated to use all the available resources in the cluster, and is equal to the block size multiplied by the total number of available processing slots in all the nodes. In that way, all the cluster processing resources are used in all the tests, with resulting dataset sizes of approximately 0.5 GB (500 nodes), 1 TB (1000 nodes) and 2 TB (2000 nodes) per concurrent job.

C. Results

The results are shown in Figures 5,[START_REF] Zhang | Elastic optical ring with flexible spectrum roadms: An optical switching architecture for future data center networks[END_REF] the average reading phase duration of the baseline (Spine-Leaf, represented by SL, in Blue) with the different number of interlinks of Multi-Layer-Mesh topology (represented by MLM, in color). The number of interlinks (links between each pair of layer-1 mesh) is shown in the legends.

The observed gain in performance is related to the number of interlinks, and this is also related to the overall cost to assemble the particular topology. This can be also viewed in Figure 8, that compares the performance gain over Spine-Leaf baseline, using the maximum number of interlinks in all cases.

For the 500-node cluster, this gain is from 14.31% for 5 interlinks, up to 40.29% with 25 interlinks, for 64 concurrent tasks. The maximum gain (with maximum number of interlinks) values are 32.72% for the 1000-node cluster, and 22.32% for the 2000-node cluster. The maximum number of interlinks was kept below the limit imposed by the number of ports per switch. It's worth noting that for just one running task, the performance gain is around 63% for all MLM configurations, showing that our proposed topology can be quite useful for this particular use case.

Figure 9 shows the number of switches and links used. The first two bars show the number of switches in Spine-Leaf and Multi-Layer-Mesh topology for a given number of nodes, and the last two bars show the number of links needed for the same topologies (SL and MLM). The number of links are shown divided by ten, for comparison purposes. We can observe that MLM uses less switches than SL, but more links in the network. As the cost of links are usually cheap (especially copper ones), the overall costs are lower for MLM. The estimated monetary costs are shown in Figure 10. For this estimate, it was considered a monetary value (in February, 2019) of €2600 per switch1 , and €602 per copper link. The switch model was chosen because it is a conventional one, but still supporting advanced features (like SDN), and the cable link was chosen because CAT5E is still very common in data centers and suits most of the existing architectures.

The chart compares the estimated cost for a SL topology to an equivalent MLM topology that has the same performance, and another with the maximum performance as shown in Figure 8. The average reduction in costs for MLM is 39.02% for the same performance of a SL installation, and 22.91% for maximum performance.

The relationship between gain in performance and reduction in cost is shown in Figure 11, for a 500-node cluster. In this chart, as the gain in performance increases, the reduction in cost decreases. The same trend occurs in the other cluster configurations.

V. Conclusion

As shown in the results section, our novel Multi-Layer-Mesh topology and SDN-based path switching protocol can achieve the same level of performance of an Spine-Leaf topology with an average of 36.03% reduction in network infrastructure costs, or increase performances by an average of 31.77% (from 22.32% up to 40.29%) using the maximum level of interlinks. It should be noted however that the savings in equipment are as high as the performance gains, and although the number of connections is increased compared to a Spine-Leaf topology, connections (especially copper ones) are much cheaper than equipment, thus the overall cost is still reduced. Even more significant is the potential cut in costs, related with the energy consumption from the switches and the related cooling systems. If a system achieves the same level of performance with less equipment used, the energy and cooling for those equipments are not needed anymore. Based on the data from a survey [START_REF] Hammadi | A survey on architectures and energy efficiency in data center networks[END_REF], network devices are responsible for 20%-30% of the energy consumption of a data center and for each watt consumed by a network device or a server, one watt is consumed for cooling the same equipments. In short, either from the viewpoint of performance gain, or energy and cost savings, the Multi-Layer-Mesh topology and path switching protocol shows positive preliminary results.

For future work, we plan to integrate the topology with data and task placement strategies, improving the level of information that the network has about running applications, in order to better configure the communications' flows. As this research was conducted assuming that regular switches were used, we will adapt the topology and simulator to test optical switches and connections as well. We also plan to improve the way the path/traffic analysis is executed, allowing the controller to react to changes in the network during the jobs' execution.

Fig. 1 .

 1 Fig. 1. Common Hadoop stack.

Fig. 2 .

 2 Fig. 2. Example of local (1), same rack (2) and external (3) tasks.

Fig. 3 .

 3 Fig. 3. Example of a Multi-Layer-Mesh topology with full L1 meshes interconnected by interlinks.

Fig. 4 .

 4 Fig. 4. System architecture overview.

  and 7 for the three cluster configurations. The plots show the comparison between

Fig. 5 .

 5 Fig. 5. Jobs completion time (500-node cluster).

Fig. 6 .

 6 Fig. 6. Jobs completion time (1000-node cluster).

Fig. 7 .

 7 Fig. 7. Jobs completion time (2000-node cluster).

Fig. 8 .

 8 Fig. 8. Performance gain of the MLM topology over the Spine-Leaf topology.

Fig. 9 .

 9 Fig. 9. Number of switches and links vs cluster topology and size.

Fig. 10 .

 10 Fig. 10. Estimated cost (€) vs cluster topology and size.

48-port SDN switch, in https://www.fs.com/products/69226.html

Stranded copper F/UTP CAT5E 100m cable, in https://www.maison-ducable.com/prix/cable-multibrins-f-utp-cat5e-16291.html

Acknowledgments

This work was supported with the financial support of the Sci-Fig. 11. Cost vs performance (500-node cluster with 64 concurrent jobs).

ence Foundation Ireland grant 13/RC/2094 and co-funded under the European Regional Development Fund through the Southern & Eastern Regional Operational Programme to Lero -the Irish Software Research Centre (www.lero.ie).


Shane Brady
email: shane.brady.1@ucdconnect.ie

Damien Magoni
email: damien.magoni@u-bordeaux.fr

John Murphy
email: j.murphy@ucd.ie

Haytham Assem
email: haythama@ie.ibm.com

A Omar Portillo-Dominguez
email: andres.portillodominguez@ucd.ie

Analysis of Machine Learning Techniques for Anomaly Detection in the Internet of Things

Keywords: Anomaly Detection, Internet of Things, Machine Learning, Comparative Study

A major challenge faced in the Internet of Things (IoT) is discovering issues that can occur in it, such as anomalies in the network or within the IoT devices. The nature of IoT hinders the identification of issues because of the huge number of devices and amounts of data generated. The aim of this paper is to investigate machine learning for effectively identifying anomalies in an IoT environment. We evaluated several state-of-the-art techniques which can identify, in real-time, when anomalies have occurred, allowing users to make alterations to the IoT network to eliminate the anomalies. Our results offer practitioners a valuable reference about which techniques might be more appropriate for their usage scenarios.

I. INTRODUCTION

The Internet of Things (IoT) is a notable technological revolution, contributing to a drastic growth in the number of Internet-connected devices worldwide. Also, how effectively these devices can communicate (over potentially heavily congested networks, or low power lossy networks) can have an important impact on the quality of the services supplied, and in their degree of success (or failure). Thus, correctly monitoring and evaluating IoT systems is critical [START_REF] Portillo-Dominguez | A requirements-based approach for the evaluation of emulated IoT systems[END_REF].

Monitoring the performance and overall health of an IoT system offers many challenges [START_REF] Shinde | Challenges in performance monitoring of hyper connected IoT systems[END_REF]. This is a consequence of the creation and transmission of vast amounts of data, which considerably complicates the identification of anomalous behaviors. Log analytic tools can be used to detect such anomalies when they are well-defined and can be captured by strict parameters (e.g., thresholds on values), but are not suitable for detecting anomalies whose properties are less well-defined, or change over time. Machine Learning (ML) techniques have the potential to effectively detect this kind of anomalies [START_REF] Aquize | Self-organizing maps for anomaly detection in fuel consumption[END_REF] as they can learn from past behavior, making them more efficient at detecting anomalies when they occur, as they are trained to observe data which does not fit with previously observed behaviors. The contribution of this work is a comparative analysis of ML techniques to detect anomalies that could occur in an IoT environment. In this paper, methods to detect anomalies in both time series and non-time series data are evaluated with statistical metrics to properly capture their usefulness and effectiveness at detecting anomalies.

II. RELATED WORK

ML has many uses in anomaly detection [START_REF] Gulenko | Evaluating machine learning algorithms for anomaly detection in clouds[END_REF]. Among ML techniques, Artificial Neural Networks (ANNs) are widely use in the literature for classification tasks, specifically in the area of anomaly detection [START_REF] Al-Janabi | A Neural Network Based Anomaly Intrusion Detection System[END_REF]. The following algorithms, often used in classification tasks and anomaly detection scenarios [START_REF] Tsai | Intrusion detection by machine learning: A review[END_REF], are used in this paper: k-Nearest Neighbor (k-NN) is an intuitive and accurate classifier. It is a method to classify an object based on the majority class amongst its k-NN. There are problems of noise, time and memory with 1-NN. To avoid this, 3 or 4-NN are used for accurate performance measure. Logistic Regression (LR) is a method for statistically analyzing a data set with one (or more) independent variables that conclude an outcome (measured with a binary variable). Linear Discriminant Analysis (LDA) is a technique that attempts to find a linear combination of features that best separates two or more classes. Unlike LR, which tries to fit a line through data points to minimize the distance between the line and the points, LDA tries to maximize the distance between the data points and the line (while minimizing the distance across the points). Decision Trees are a technique for predicting the relationship between measurements of an item and its class value. A decision tree is a classifier represented as a recursive partition of an instance space. Moreover, one of the most popular algorithms to create trees is C4.5, which uses information gain as splitting criteria. Naive Bayes (NB) uses a normal distribution and rules of conditional probability to model numeric attributes. It is termed as naive because it relies on two simplifying assumptions: no hidden attributes influence the prediction process, and the predictive attributes are independent given the class.

A multilayer perceptron (MLP) is a neural network model mapping input data with a set of outputs [START_REF] Haykin | Neural networks and learning machines[END_REF], that can also distinguish data which is not linearly separable. A recurrent neural network (RNN) is a type of neural network where connections between units form a directed cycle, creating an internal state which allows it to exhibit dynamic behavior [START_REF] Mikolov | Recurrent neural network based language model[END_REF]. Long Short Term Memory (LSTM) is a form of RNN which attempt to solve the problem of long term dependencies [START_REF] Hochreiter | Long short-term memory[END_REF]. This is achieved by having three gates used to decide if information gets passed through the network (thus protecting the state of the cell). Finally, Gated recurrent units (GRUs) is a popular gating mechanism in recurrent neural networks [START_REF] Chung | Empirical evaluation of gated recurrent neural networks on sequence modeling[END_REF].

III. EVALUATION METRICS

This work focuses on classification tasks and standard metrics used for evaluating the performance of the ML models. Models are trained on a set of data which is the training set and predictions are made on a separate set of data containing the same features that exist in the test data. The results of this anomaly detection classification is binary (i.e., 1 for a detected anomaly, or 0 for a normal event). To perform an evaluation of these models we need to know the number of True Positives (TP), False Positives (FP), True Negatives (TN) and False Negatives (FN) that occur when we make predictions on the test set [START_REF] Han | Data mining: concepts and techniques[END_REF]. A TP is a predicted anomaly which was an anomaly, a TN is a predicted normal event which was a normal event, a FP is a predicted anomaly which was actually a normal event and a FN is a predicted normal event which was actually an anomaly. Given these values, the following commonly used metrics are calculated: (1) Precision is used to test the ability of the model to retrieve relevant items. It is the fraction of relevant instances among the retrieved instances.

(2) Recall is used to test the probability that the model will retrieve a relevant item. In binary classification tasks, recall is also known as sensitivity. It is not enough to use recall alone as if every instance was predicted as an anomaly then the recall of the model would be 100%. This is why it is often used in conjunction with precision. (3) F1-score is the harmonic mean of precision and recall, meaning it takes into account how high the two values are as well as how similar they are, making it a good indicator of the accuracy of the model. ( 4) Accuracy is a fraction of correctly classified instances over the total number of instances. In all cases, higher values are better.

IV. COMPARATIVE ANALYSIS

The aim of these experiments is to analyze, using the standard ML metrics previously discussed, the performance of a set of state-of-the-art classification algorithms on different types of data which may be found in an IoT environment. In particular, we look at both time series and non-time series data. This is because these two complementary data types are commonly found in a typical IoT environment.

Non-Time Series: NSL-KDD Dataset. Non-time series data is data which has no discernible time-element. The ordering of the data in the dataset is not important, as it does not relate to time steps. This makes classifying non-time series data a fundamentally different problem from classifying timeseries data as we are not trying to predict the next step (or several steps) in a sequence; instead, we are looking at the features of known data and given new data we try to predict what class it belongs to. The purpose of this experiment was to test various classification algorithms on a non-time series dataset. We chose 5 ML commonly-used techniques that have been found in the literature to be suitable for classifying nontime series data. They are k-Nearest Neighbors (kNN), Logistic Regression (LR), Linear Discriminant Analysis (LDA), Decision Trees (CART) and Nave Bayes (NB). We also look at using neural networks in the form of a multilayer perceptron (MLP). Also, we chose the NSL-KDD dataset [START_REF]NSL-KDD dataset[END_REF], a revised version of the KDD 99 dataset with more variance of data and no duplicate records or missing values. This dataset comprises of rows of 41 features (independent variables) used to describe a network connection and one dependent binary variable that states whether the connection is a network attack or not. The tools we are using to perform this classification do not support categorical variables, so firstly we had to carry out one-hot encoding on each row of the dataset. This involves splitting a categorical feature (e.g. a feature whose value can be one of several values) into multiple binary features which indicate which of the values it is [START_REF] Coates | The importance of encoding versus training with sparse coding and vector quantization[END_REF]. This task increases the number of features from 42 (including the output variable) to 124.

After getting the data into a form that we can process, the next step is to divide it into train and test data. The NSL-KDD dataset provides pre-defined train and test datasets. The training set consists of 125K records and the test set consists of 22K records. As we want to see how the algorithms we have chosen scale in terms of performance (both in classification and execution time), we also split the training set into multiple training sets of different sizes. We finish with 5 different training sets: The original training set with 100% of the values, as well as one with 80%, one with 60%, one with 40% and one with 20% of the original values of the training set. Finally, we also want to see how our algorithms perform when we do not use all of the features of the dataset, as well as seeing how necessary all of the features of the dataset are for effective classification. To do this, we use an extra trees classifier to gather the importance of each feature in the dataset. Based on the obtained importances, we can eliminate those features which are deemed by the classifier to be effectively useless for classification. This brings us from 124 features , after one-hot encoding, to just 49. This should give improved execution time for our algorithms with minimal cost to classification accuracy.

First, we will look at the 5 classification algorithms mentioned above. Figure 1 shows the classification accuracy for the 5 algorithms, using 100% of the training set for training and classifying on the test set, with all features included. Apart from the NB algorithm, the other four algorithms perform well, all hitting at least 70% accuracy. The decision trees show an impressive 80% classification accuracy, with little difference between the KNN and LDA algorithms. Moreover, the low accuracy exhibited by NB was the result of over-fitting the model with multiple dependent variables. Next, we look at what the trade-off is in execution time to get these scores in Figure 2. We observe that, while there is little difference in accuracy between KNN and LDA, it takes considerably longer to train KNN. We also see that the decision tree algorithm (CART), which consistently outperform the other algorithms in terms of classification accuracy, also scales very well in terms of time taken to train.

We also find that using smaller amount of values for training the dataset has little effect on the accuracy, which is believed to be due to the large volume of data contained in the initial dataset. Figure 3 shows the accuracy scores for the 5 algorithms with the 20% training set versus the full training set. From Figure 4, we also do not see a huge difference between the classification accuracy when using reduced features and all features. This would appear to be due to the number of features left, after feature reduction, still being quite large (49). Next, we look at the neural network approach, using MLP to train a more complicated network with our various training sets, then feeding data from our test set to the trained model for classification. For this experiment, we run the training process for different numbers of epochs (1, 10, 20, 50, 100) and gather the same metrics mentioned above. Figure 5 shows the accuracy when using 100% of the training set with all features. What we see from that figure is that the classification accuracy is greatly increased when we train for larger numbers of epoch (i.e., ≥ 10). This was due to the high complexity of the KDD dataset, which required more epochs to get a satisfactory accuracy. From the results for 10, 20, 50 and 100 epochs we also see variance but no real improvement in the accuracy. This is likely due to the network finding a local minimum when reducing the error rate during training and deviating either away (or back) towards that minimum during further epochs. To verify this, we can look at results for the other training sets, for instance Figure 6 which depicts the results of the 80% training set. From this figure, we can see a more predictable trend for the 1, 10, 20 and 50 epochs with the classification accuracy increasing by a reasonable margin for each value of epochs. However, for the 100 epochs the accuracy drops a bit, again likely due to finding a local minimum for the error rate during training, this time after 50 epochs. When looking at the 10 sets of results We also find that the neural networks approach is computationally expensive, as shown by Figure 7, which depicts the results for training with 100% of the data with no feature reduction. To perform a single epoch of training takes about 5 seconds, but this time increases greatly for more epochs, taking roughly 70 seconds for 100 epochs. The highest accuracy we see from the MLP is 79%, which means it is consistently worse than the decision tree CART algorithm which regularly managed 80% (or higher) accuracy, and which takes a fraction of the time to train (approximately 10 times quicker).

Time-Series: Yahoo Anomaly Detection Dataset. Timeseries data consists of data points which are indexed in order of time, meaning every piece of data has an associated timestep. When performing classification on time-series data, we first look at a sequence of data points up to a given time and then try to predict the next value (or sequence of values) for a time period. This dataset, provided by Yahoo for academic purposes [START_REF]Yahoo dataset[END_REF], was created with the aim of benchmarking anomaly-detection algorithms. The dataset consists of real and synthetic time-series data, where each data point is tagged as either an anomaly or normal data. The real data consists of metrics of various Yahoo services, though it is not defined what these services are, as the data is user sensitive. Five files were chosen from the dataset (4x real, 1x synthetic) to give a spread of anomaly occurrence and distribution in the data. Four time-series algorithms are used to test for anomalies. These algorithms are Long Short Term Memory (LSTM), Gated Reccurent Unit (GRU), Recurrent Neural Network (SimpleRNN) and an Autoregressive Integrated Moving Average (ARIMA) model. The data is then split into train/test splits at a ratio of 0.5, 0.6, 0.7, 0.8 and 0.9. For ARIMA, we add every observation from the test data to our history of seen observations after we predict the next value and then retrain the model. This is why in the results the time increases for a shorter train set, as the model is retrained as many times as there are values in the test set. Each of the neural network algorithms (LSTM, GRU and SimpleRNN) are trained for 100 epochs before making predictions, and all use the same seeded random values throughout the tests. The data is normalized to small values (between 0 and 10) and an error threshold of 1 (i.e., 10% of the range) is used to predict anomalies (as this threshold is typically used to delimit the behaviour of a steadystate process [START_REF] Portillo-Dominguez | PHOEBE: an automation framework for the effective usage of diagnosis tools in the performance testing of clustered systems[END_REF]). For instance, if the predicted value is 0.5 and the actual value is -0.3, it is not considered an anomaly. Alternatively, if the prediction is 0.4 and the actual value is 2.2, it is considered an anomaly. Also, we compare our predicted binary classification results with the actual anomaly values to calculate the evaluation metrics discussed in Section III.

To illustrate the obtained results, we present the results of File 17, as it had the most anomalies spread out over time, and it is also representative of the overall results obtained (as the other files exhibited similar trends). Figure 8 shows the results of the TP/TN/FP/FN values for this file for the different algorithms and train/test splits. It can be noticed that, in general, all the executed algorithms consistently performed well, as they produced considerably more TP and TN values than FP and FN values. To complement this analysis, we present Figure 9 which shows how the train/test splits affect the test metrics by looking at the values, as a percentage of the total number of records in the set. There, it can be seen that the algorithms generally follow a similar pattern, mostly finding true negatives, which is explained by the fact that most of the data points are not anomalies. Meanwhile, Figure 10 shows the standard classification metrics for File 17. In general terms, the bigger the training set, the better the precision, with LSTM and GRU being the most accurate algorithms. Nevertheless, the accuracy does not improve with the training set size and is mostly similar for all the algorithms. Finally, ARIMA is a bit better at recall compared to the others.

Time-Series: IoT Testbed Dataset. As a second time-series dataset, we used our IoT testbed data generated by the process discussed in [START_REF] Brady | Towards an emulated IoT test environment for anomaly detection using NEMU[END_REF]. The testbed outputs room temperature values and those that are too low/high are flagged as anomalies. We used LSTM, GRU, SimpleRNN and ARIMA: for each algorithm, the test/train split was tried with 0.5/0.6/0.7/0.8/0.9 ratio as for the Yahoo dataset. To exemplify the obtained results, Figure 11 shows the precision, recall, F1-score and accuracy for one file from the testbed results. We can see that the neural network algorithms do not perform very well in regards to precision and recall when the train/test split is skewed towards the training. The recall at times is very good but can be inconsistent (partly because there are not that many anomalies in the data, so when one is missed it has a substantial effect on the scores). The accuracy is generally high across the board. Also, ARIMA is clearly the most consistent performer as its results do not vary greatly depending on the split (consequence of retraining the model at every step).

Figure 12 shows the TP/TN/FP/FN values of these models to provide a more granual insight of the results. The algorithms should maximize the number of TP/TN values, while minimizing the number of FP and FN values. This graph clearly depicts that ARIMA is the best performing model on average. An interesting result is that the SimpleRNN model, which was the weakest of the neural network algorithms in the Yahoo tests, is now the best in these tests. We believe this is due to the random nature of the temperature values. This indicates that there is no pattern, suggesting that the memory capabilities of GRU and LSTM actually hinder their performance, as they look further back to infer patterns which do not really exist. Again, we look at these metrics as a percentage of the number of samples tested from the test data to assess how the prediction accuracy deviates with regards to the different splits. A good algorithm should have a high number of TP and TN values and a low number of FP and FN values, but it is less useful if this only occurs with certain splits. We can see from Figure 13 that ARIMA consistently performs well across all the tested scenarios.

V. CONCLUSIONS AND FUTURE WORK

IoT presents many challenges, including maintaining vast and complex networks. Having many small devices sending traffic at frequent intervals makes it difficult to identify when and where problems occur in a network, compared to more traditional networks. Thus, techniques need to be evaluated to help identify when and where these issues occur. To address this issue, this paper provides a comprehensive analysis of ML techniques for anomaly detection. To ensure that the analysis was comprehensive, both non-time series and time series data were examined, as they both have their own challenges and methods for anomaly detection. This analysis was carried out with three data sets, one for non-time series and two for time series, with different variations of splits for training and test data, as well as identifying anomalies in the data before and after feature reduction. For the non-time series data, it was observed that the Linear Discriminant Analysis and Decision Tree algorithms provided the most consistent results, achieving roughly 80% accuracy (across all tested scenarios). Using neural networks for the non-time series data does not appear to be a viable option, as the experiments showed that, even with many epochs, neural networks do not outperform the other classification algorithms, despite taking longer to run. For the time series data, it was observed that when analyzing data with underlying trends (such as in the Yahoo data set), the neural networks with memory gates (LSTM and GRU) outperformed the others. However, with data without underlying trends (such as the IoT testbed data) the opposite was true, as the algorithms tried to infer patterns that did not exist. Also, it was observed that ARIMA generally performs well across both types of data and appears to be the most suitable for realtime prediction of anomalies, as the network can be retrained after every observation and make a new prediction even when observations are being made every second. Finally, the algorithms used were chosen from those that are most frequently cited in the literature and which were deemed suitable for anomaly detection. Future work will focus on extending the set of evaluated algorithms to generalize the obtained knowledge of when each algorithm is best suited for. Likewise, further work will focus on diversifying more the parameters' configurations of the evaluated algorithms, with the aim of generating usability guidelines for practitioners.

Fig. 1 .

 1 Fig. 1. Classification accuracy

Fig. 2 .

 2 Fig. 2. Algorithm scaling using various percentages of the training set

Fig. 4 .

 4 Fig. 4. Classification accuracy with and without feature reduction

Fig. 6 .Fig. 7 .

 67 Fig. 6. MLP classification accuracy (80% train set)

Fig. 8 .Fig. 9 .

 89 Fig. 8. Positivity values for File 17 for each algorithm and split

Fig. 11 .

 11 Fig. 10. Metric scores for Yahoo data

Fig. 12 .Fig. 13 .

 1213 Fig. 12. Positivity values of testbed data across all splits

ACKNOWLEDGMENTS

This work was supported, in part, by Science Foundation Ireland grant 13/RC/2094. Supported, in part, by Agence Nationale de la Recherche grant ANR-10-IDEX-03-02.