# Online Incremental Learning for High Bandwidth Network Traffic Classification

Authors: H. R. Loo; S. B. Joseph; M. N. Marsono
Journal: Applied Computational Intelligence and Soft Computing
 (2016)

---

## Abstract

Data stream mining techniques are able to classify evolving data streams such as network traffic in the presence of concept drift. In order to classify high bandwidth network traffic in real-time, data stream mining classifiers need to be implemented on reconfigurable high throughput platform, such as Field Programmable Gate Array (FPGA). This paper proposes an algorithm for online network traffic classification based on the concept of incrementalk-means clustering to continuously learn from both labeled and unlabeled flow instances. Two distance measures for incremental k-means (Euclidean and Manhattan) distance are analyzed to measure their impact on the network traffic classification in the presence of concept drift. The experimental results on real datasets show that the proposed algorithm exhibits consistency, up to 94% average accuracy for both distance measures, even in the presence of concept drifts. The proposed incremental k-means classification using Manhattan distance can classify network traffic 3 times faster than Euclidean distance at 671 thousands flow instances per second.


---

## Body

## 1. Introduction

Network traffic classification is a critical network processing task for network management. Traffic measurement and classification enable network administrators to understand the current network state and reconfigure the network such that the observed network state can be improved over time. The complexity and dynamic characteristic of today’s network traffic have necessitated the need for traffic classification techniques that are able to adapt to new concepts. This includes the ability to classify types of traffic almost instantaneously to avoid outdating the knowledge gained from the learning of new concepts.Data stream mining algorithms [1–6] have been introduced to overcome the shortcoming of conventional data mining algorithms. They are designed to handle concept drift, to forget old irrelevant data, and to adapt to new knowledge. References [7–9] have proposed the use of data stream mining algorithms for traffic classification such as Very Fast Decision Tree [3] and Concept-Adaptive Very Fast Decision Tree [4]. Reference [10] proposed a new algorithm named Concept-Adaptive Rough Set based Decision Tree (CRSDT) to classify network traffic. These algorithms have successfully demonstrated the ability of data stream mining to handle dynamic and fast changing network data streams with sustained accuracy. However, the decision tree based implementation requires intensive training process and causes high memory consumption for model building [11].References [2, 12] proposed the use of incremental clustering for data stream classification. Although both works show high classification accuracy for evolving data stream, the processing rate of such algorithms is low. One of the reasons is due to the use of Euclidean distance in both works as the distance metric. Euclidean distance computation that requires multiple square and square root functions contributes to high overhead and limited speed. Another distance measure is the Manhattan distance that does not require heavy multiplications [13], which can be efficiently implemented on reconfigurable hardware such as Field Programmable Gate Array (FPGA). Unlike batch data mining, conversion of distance metric from Euclidean distance to Manhattan distance in k-means incremental learning cannot be directly applied. Certain modifications on the incremental k-means algorithm need to be done. In incremental clustering algorithms, clusters information is normally stored as a summary of points and the raw data are discarded after training. Radius recomputation in Euclidean distance can be totally based on the summary of points, but raw data are needed in Manhattan distance. Thus some modification on the summary of points is needed.This paper analyzes online incrementalk-means network traffic classification in [16] with two distance measures (Euclidean and Manhattan). The proposed method using Manhattan distance requires less computation than Euclidean distance and, hence, achieves higher running speed. This algorithm has been verified with real network traces to evaluate the accuracy when using these distance measures and possible implementation trade-off for high throughput network traffic classification. The rest of the paper is organized as follows. The incremental k-means proposed method based on Euclidean distance is described in Section 3. Modification of the proposed method to suit Manhattan distance is discussed in Section 4. The experimental setup and results are discussed in Section 5. Section 6 concludes the paper and states suggestions for future works.


## 2. Related Works

The simplicity of clustering algorithm such ask-means makes it well adapted for network traffic classification. References [17–19] proposed k-means algorithm implementations for classifying network traffic with high accuracy. Reference [20] proposed the use of feature selection method with k-means algorithm to enhance the classification accuracy. Reference [11] proposed a new initialization method for centroid selection in k-means to further improve the classification accuracy of network traffic, whereas [21] proposed enhancement to k-means algorithm to prevent the diverse impact of attributes on clustering output. The aforementioned works successfully show the suitability of clustering based algorithms in network traffic classification, although they could not adapt to changes in network concept in today’s network traffic.References [22–27] proposed incremental clustering algorithm which could adapt to new knowledge over time. Reference [22] proposed the microclustering concept where only the summary of clusters is kept throughout the learning process. The proposed algorithm can learn new concept incrementally by updating the clusters summary. Reference [23] proposed adapting the microclustering concept originally proposed in [22] and proposed macroclustering stage with pyramidal time frame. Not all microclusters are saved that reduce overall memory consumption. Reference [24] proposed the adaptation of microclustering and macroclustering concepts from [22, 23] and is customized for trajectory data. Although the method in [24] demonstrates the ability to update classification model incrementally, it does not support streaming data.Reference [25] proposed graph based incremental clustering although it is not suitable for online network classification due to its long processing rate and large memory consumption. Reference [26] proposed incremental DBSCAN for data warehousing. The proposed algorithm is based on density-based clustering. The radius of cluster and minimum number of points in clusters are assumed to be fixed. Reference [27] proposed incremental clustering based real-time anomaly detection. Incremental training is initiated based on the false alarm threshold that requires continuous feedback from the network administrator. Incremental clustering can continuously learn new knowledge and reduce misclassification caused by outdated knowledge. For online real-time network traffic classification, the processing rate of software implementation of such algorithms is not sufficient to support current network speed. Implementation of such algorithms in reconfigurable hardware such as Field Programmable Gate Array (FPGA) can accelerate the processing rate.To the best of our knowledge, only [28] has proposed the implementation of incremental clustering algorithm in FPGA for multimedia traffic classification. The proposed method uses Hamming distance instead of Euclidean distance for the distance measurement. It uses an extra bit appended to the data to indicate training or testing dataset and incrementally updates the model when training bit is detected. However, the proposed method requires large training set (10k instance) to achieve high accuracy. On the other hand, implementations of nonincremental k-means algorithm in FPGA are more common, for example, [29–32]. However, implementation of Euclidean distance based k-means algorithm on hardware consumes high hardware resources. References [30, 31] reported that 90% of the hardware resources were required to implement k-means algorithm. Modification of such distance was proposed as in [33] using distance squared. References [13, 34–36] proposed the use of Manhattan distance as a distance measure for k-means. The implementation not only can reduce the hardware cost, it also can be fully configurable and easily pipelined to support high degree of parallelism. Hence, towards the implementation of hardware acceleration of incremental online network traffic classifier, the proposed incremental k-means classifier based on Manhattan distance is a better option than using Euclidean distance.


## 3. Online Incrementalk-Means Algorithm

We proposed online incrementalk-means clustering in [16] for online network traffic classification. It consists of two main processes: classification and learning. Some of the terms and terminology used in this paper are as follows:(1)
Flow: the network traffic that belongs to a process-to-process communication.(2)
Instance: a tuple of attributes.(3)
Flow features: the attributes or statistical features that are extracted from a flow, for example, number of bytes in payload.(4)
Flow instance: the instance made up of flow features which represent a flow. The classification process performs online classification on flow instances, while the learning process simultaneously performs incremental learning to update the classification model. Both processes will be discussed in detail in Sections 3.2 and 3.4, respectively. Figure 1 shows the overview of the proposed method. The selection module performs the selection of flow instances to be learned to avoid mislearning (see Section 3.3). However, manual labeling is not covered in this paper. An example of such technique is the groundtruth method which is discussed in [15].Figure 1
Overview of the proposed method.


### 3.1. Classification Model Initialization

Before online classification can be performed, the classification model needs to be initialized. This process is performed once during start-up to prepare thebase classifier model. In this stage, the supervised k-means technique is used to cluster the batch labeled flow instances into k initial clusters. In order to increase classification efficiency, the classification model M is made up of B smaller micromodels that are located in different location in the Euclidean space. To perform this, precollected flow instances are distributed to B chunks according to the distance to origin Do, such that (1)Doi=∑m=0dxim2,where xi is a flow instance with d flow features. Each micromodel is then built using respective chunk of flow instances.The initializations of centroids are based on the method suggested in [12] where the initial class of clusters are assumed to be proportional to the data distribution. The clusters are then compressed to sufficient statistics known as clustering features (CF). CF is a 3-tuple information that summarizes information about a cluster as proposed in [22]. Given Nj  d-dimensional data points (xi→) in a cluster j where i=1,2,…,Nj, the CF of a cluster is defined as three-tupple: CFj=Nj,LSj→,SSj→, where(2)LS→=∑i=1Nxi→,SS→=∑i=1Nxi→2.In our classification model, we modify and add the timestamp Tj and class information yj to represent each cluster; CFj=Nj,LSj→,SSj→,Tj,yj. Merging new (xi→) to cluster j is based on the Additivity Theorem [22], where Tj and yj are unchanged, such that (3)CFj=Nj+1,LSj→+xi→,SSj→+xi→2,Tj,yj.Raw data are discarded in order to save memory space. The k clusters that are represented by k clustering features are used for classification and the clusters may be modified based on newly received data.Algorithm1 shows the overall steps for classification model initialization. During model initialization, the precollected flow instances are divided into B sets, and the supervised k-means method is used to create a micromodel for each set of flow instances. Created clusters are summarized as clustering features, CF with timestamp 0.Algorithm 1:Classification model initialization.
(1)xi: Pre-collected flow instances (array of features)
(2)yi: True labels for xi
(3)Do: Distance of xi to origin
(4)B: Number of micro-model
(5)N: Number of Pre-collected flow instances
(6)Bk: Number of cluster in a micro-model
(7)for xi in range of (0,N) do
(8)  CalculateDo(xi)
(9)end for
(10)  Quicksort(Do[N])
(11)  Distributexi into B micro-model
(12)for each micro-model do
(13)  GenerateBk cluster
(14)  SummarizeBk cluster into Clustering Feature, CF
(15)  Store clusters in time-series and set timestamp to 0
(16)end for


### 3.2. Online Classification

Classification starts upon receiving an incoming flow instance(xi→). The distance to origin Do(xi) is calculated to find the respective micromodel. In the micromodel, the distance between cluster’s centroid and xi→ is computed using (4). The nearest cluster (C1) and second nearest cluster (C2) are then determined. Assuming that the real class label of a flow instance is unknown (unlabeled flow instance), the predicted class y′(xi) will be classified to class of C1 with respect to xi→:(4)Dxi,μj=∑m=0dxim-μjm2,where μj is the centroid of cluster j and μj=LS→/N.


### 3.3. Selection of Learning Instance

As self-training method is applied in the learning algorithm, all predicted labels are assumed to be accurate. While this is not entirely true in incremental learning process, certain threshold of false positive must be expected. Since learning on falsely predicted flow instances can cause false learning, only flow instances with high confidence of prediction are chosen to be learned. The selection criteria are designed such that they make use of the information from classification process so that they do not need extra computation. Extra computation will make longer model learning and incremental learning inefficient.Confidence level is divided into three levels{L0,L1,L2} as shown in Table 1. The criteria are to determine confidence level in terms of label conflict within the two nearest clusters (conflicting neighbor) and condition when a flow instance is within the nearest cluster’s boundary (in-boundary). Conflicting neighbors are set to true when both nearest clusters belong to different classes or set to false when they belong to the same class.Table 1
Prediction confidence level.
Confidence level
Conflicting neighbour
In-boundary
L
0
Yes
—
L
1
No
No
L
2
No
YesThe boundary of the nearest clusterC1 is determined by the cluster’s average radius R defined by (5) [22]. However, for clusters with N=1, (5) is not valid as the subtraction in numerator will results in zero denominator. This consideration was not analyzed in [37]. In [2], the calculation of maximum boundary is based on the nearest neighbor’s maximum boundary. However, the boundary of such clusters is not always similar, and to determine the nearest neighbors will increase the system computation complexity by O(kd).We propose that the boundary of a cluster with only one flow instance can be determined by the similarity of attributes. Each attribute of a cluster centroid is compared with the attributes of incoming flow instance. An attribute is considered similar to other attributes if the ratio between them is within 10% of each other (0.9⩾x1/x2⩾1.1). A parameter boundary threshold is needed to define the maximum nonsimilar attributes between flow instances and the cluster centroid that can be tolerated to include an incoming flow instance in the respective cluster. If the number of nonsimilar attributes is lower than the boundary threshold, it is considered to be within the boundary of the particular cluster:(5)Rμj=∑m=0dSSμjm-∑m=0dLSμjm2/NμjNμj.The confidence level can be determined as follows: letC1 be the nearest cluster and C2 the second nearest cluster, yCi the class of Ci, RCi the radius of Ci, and μCi the centroid of Ci. Confidence level is set to L0 by default. In the case of yC1=yC2, confidence level will increase by one (L1). If xi∈RC1 for C1 with more than one flow instance or xi≈μC1 for C1 with only one flow instance, confidence level will increase to two (L2) if the condition yC1=yC2 is satisfied.


### 3.4. Semisupervised Incremental Learning

Only flow instancesxi→ with confidence level L2 are used in incremental learning. As shown in Algorithm 2, flow instances with confidence level L2 are merged with the nearest cluster C1 based on (3). The learning will then update the classification model. As the input flow instances are in streams, changes in distribution and concept are expected. Outdated knowledge needs to be deleted and the micromodel needs to be reconstructed based on recent clusters. This process will be discussed in Section 3.4.2.Algorithm 2:Proposed algorithm.
(1)xi′: L2 flow instance
(2)C1: Nearest clusters from xi
(3)while new xi′  do
(4)  mergexi′ to C1
(5)end while
(6)—Labeled Instance Injection (upon receiving)—
(7)if receive (xj,yj)  then
(8)  - Injectxj
(9)end if
(10)—Micro-model Reconstruction (after one chunk)—
(11)N: Number of clusters
(12)kd: Desired number of clusters
(13)while  N>kd  do
(14)  delete clusters with timestamp0
(15)  reduce clusters timestamp by1
(16)end while
(17)  gather all clusters in classification model
(18)  reconstruct micro-model


#### 3.4.1. Injecting Labeled Instances

In our previous work [16], we assumed that labeling of flow instances can be done immediately after the learning process. Our extended experiment suggests that this is not possible since labeling of flow instances involves manual steps. Thus, we can only assume that some flow instances will be labeled externally and fed into the model once they are ready. Thus, the flow instances will be treated as a new flow instance and reclassified in order to get the necessary information such as confidence level and prediction results. In order to achieve minimum effort in injection, different handling methods based on the confidence level and prediction results are proposed for handling different possible scenarios. Table 2 shows the injection handling method for several scenarios. False prediction in trained flow instances will cause the trained cluster to be deleted immediately since the cluster is no longer reliable. Besides, new cluster with xi will be added if xi is not in the boundary of C1. This is true except for scenarios  2 and  3, since there is a possibility of xi to be within the boundary of C2. Figure 2(a) illustrates the example of boundary condition when xi is nearer to C1 but is in the boundary of C2. Merging xi to C2 will shift boundary of C2 towards C1 and can result in an overlap (Figure 2(b)). Thus, when C1 and C2 are of different classes, one of these clusters needs to be deleted. If they belong to the same class, xi will be ignored since its learning brings no significant changes to the model.Table 2
Injection handling method.
Scenario
Confidence level
Prediction
Procedure
1
0
True
Mergex with C1 if x∈RC1, else add new cluster for x
2
0
False
Mergex with C2 if x∈RC2 and yx=yC2, else add new cluster for x Delete C1
3
1
True
Ifx is not in R(C2), add new cluster for x
4
1
False
Add new cluster forx
5
2
True
Do nothing
6
2
False
EraseC1 and add new cluster for xFigure 2
Example of boundary condition (a) before model merging withC2 (b) after merging with C2.
(a)
(b)


#### 3.4.2. Micromodel Reconstruction

In order to prevent the storing of all outdated clusters that may result in imbalanced micromodel, a micromodel reconstruction process is performed after a user-predefined number of flow instances (chunks) have been received. Clusters that are not utilized or underutilized will be deleted as they do not contribute to the classification decision. In addition, the micromodel reduction also aims to reduce memory footprint and classification time. This reduction process includes the following steps:(1)
All clusters are structured as a time-series based on the time they were created.(2)
All clusters are given zero timestamps.(3)
When a cluster is nominated as the nearest cluster in the classification process, the timestamps is incremented by one.(4)
When a chunk is received, the timestamps of each cluster is checked from the beginning of the series. Clusters with timestamps zero will be deleted until the number of clusters,k, is reduced to a user-predefined number, kd/B. Then, the timestamps of remaining clusters will be decremented by one. If in a situation where k>kd/B even after deleting all zero timestamps clusters, the deleting process will be repeated for timestamps one and so on until it reaches the required number of clusters.After the deletion of unused clusters, the remaining clusters will be repartitioned into B micromodels based on their centroid locations in the Euclidean space.


## 3.1. Classification Model Initialization

Before online classification can be performed, the classification model needs to be initialized. This process is performed once during start-up to prepare thebase classifier model. In this stage, the supervised k-means technique is used to cluster the batch labeled flow instances into k initial clusters. In order to increase classification efficiency, the classification model M is made up of B smaller micromodels that are located in different location in the Euclidean space. To perform this, precollected flow instances are distributed to B chunks according to the distance to origin Do, such that (1)Doi=∑m=0dxim2,where xi is a flow instance with d flow features. Each micromodel is then built using respective chunk of flow instances.The initializations of centroids are based on the method suggested in [12] where the initial class of clusters are assumed to be proportional to the data distribution. The clusters are then compressed to sufficient statistics known as clustering features (CF). CF is a 3-tuple information that summarizes information about a cluster as proposed in [22]. Given Nj  d-dimensional data points (xi→) in a cluster j where i=1,2,…,Nj, the CF of a cluster is defined as three-tupple: CFj=Nj,LSj→,SSj→, where(2)LS→=∑i=1Nxi→,SS→=∑i=1Nxi→2.In our classification model, we modify and add the timestamp Tj and class information yj to represent each cluster; CFj=Nj,LSj→,SSj→,Tj,yj. Merging new (xi→) to cluster j is based on the Additivity Theorem [22], where Tj and yj are unchanged, such that (3)CFj=Nj+1,LSj→+xi→,SSj→+xi→2,Tj,yj.Raw data are discarded in order to save memory space. The k clusters that are represented by k clustering features are used for classification and the clusters may be modified based on newly received data.Algorithm1 shows the overall steps for classification model initialization. During model initialization, the precollected flow instances are divided into B sets, and the supervised k-means method is used to create a micromodel for each set of flow instances. Created clusters are summarized as clustering features, CF with timestamp 0.Algorithm 1:Classification model initialization.
(1)xi: Pre-collected flow instances (array of features)
(2)yi: True labels for xi
(3)Do: Distance of xi to origin
(4)B: Number of micro-model
(5)N: Number of Pre-collected flow instances
(6)Bk: Number of cluster in a micro-model
(7)for xi in range of (0,N) do
(8)  CalculateDo(xi)
(9)end for
(10)  Quicksort(Do[N])
(11)  Distributexi into B micro-model
(12)for each micro-model do
(13)  GenerateBk cluster
(14)  SummarizeBk cluster into Clustering Feature, CF
(15)  Store clusters in time-series and set timestamp to 0
(16)end for


## 3.2. Online Classification

Classification starts upon receiving an incoming flow instance(xi→). The distance to origin Do(xi) is calculated to find the respective micromodel. In the micromodel, the distance between cluster’s centroid and xi→ is computed using (4). The nearest cluster (C1) and second nearest cluster (C2) are then determined. Assuming that the real class label of a flow instance is unknown (unlabeled flow instance), the predicted class y′(xi) will be classified to class of C1 with respect to xi→:(4)Dxi,μj=∑m=0dxim-μjm2,where μj is the centroid of cluster j and μj=LS→/N.


## 3.3. Selection of Learning Instance

As self-training method is applied in the learning algorithm, all predicted labels are assumed to be accurate. While this is not entirely true in incremental learning process, certain threshold of false positive must be expected. Since learning on falsely predicted flow instances can cause false learning, only flow instances with high confidence of prediction are chosen to be learned. The selection criteria are designed such that they make use of the information from classification process so that they do not need extra computation. Extra computation will make longer model learning and incremental learning inefficient.Confidence level is divided into three levels{L0,L1,L2} as shown in Table 1. The criteria are to determine confidence level in terms of label conflict within the two nearest clusters (conflicting neighbor) and condition when a flow instance is within the nearest cluster’s boundary (in-boundary). Conflicting neighbors are set to true when both nearest clusters belong to different classes or set to false when they belong to the same class.Table 1
Prediction confidence level.
Confidence level
Conflicting neighbour
In-boundary
L
0
Yes
—
L
1
No
No
L
2
No
YesThe boundary of the nearest clusterC1 is determined by the cluster’s average radius R defined by (5) [22]. However, for clusters with N=1, (5) is not valid as the subtraction in numerator will results in zero denominator. This consideration was not analyzed in [37]. In [2], the calculation of maximum boundary is based on the nearest neighbor’s maximum boundary. However, the boundary of such clusters is not always similar, and to determine the nearest neighbors will increase the system computation complexity by O(kd).We propose that the boundary of a cluster with only one flow instance can be determined by the similarity of attributes. Each attribute of a cluster centroid is compared with the attributes of incoming flow instance. An attribute is considered similar to other attributes if the ratio between them is within 10% of each other (0.9⩾x1/x2⩾1.1). A parameter boundary threshold is needed to define the maximum nonsimilar attributes between flow instances and the cluster centroid that can be tolerated to include an incoming flow instance in the respective cluster. If the number of nonsimilar attributes is lower than the boundary threshold, it is considered to be within the boundary of the particular cluster:(5)Rμj=∑m=0dSSμjm-∑m=0dLSμjm2/NμjNμj.The confidence level can be determined as follows: letC1 be the nearest cluster and C2 the second nearest cluster, yCi the class of Ci, RCi the radius of Ci, and μCi the centroid of Ci. Confidence level is set to L0 by default. In the case of yC1=yC2, confidence level will increase by one (L1). If xi∈RC1 for C1 with more than one flow instance or xi≈μC1 for C1 with only one flow instance, confidence level will increase to two (L2) if the condition yC1=yC2 is satisfied.


## 3.4. Semisupervised Incremental Learning

Only flow instancesxi→ with confidence level L2 are used in incremental learning. As shown in Algorithm 2, flow instances with confidence level L2 are merged with the nearest cluster C1 based on (3). The learning will then update the classification model. As the input flow instances are in streams, changes in distribution and concept are expected. Outdated knowledge needs to be deleted and the micromodel needs to be reconstructed based on recent clusters. This process will be discussed in Section 3.4.2.Algorithm 2:Proposed algorithm.
(1)xi′: L2 flow instance
(2)C1: Nearest clusters from xi
(3)while new xi′  do
(4)  mergexi′ to C1
(5)end while
(6)—Labeled Instance Injection (upon receiving)—
(7)if receive (xj,yj)  then
(8)  - Injectxj
(9)end if
(10)—Micro-model Reconstruction (after one chunk)—
(11)N: Number of clusters
(12)kd: Desired number of clusters
(13)while  N>kd  do
(14)  delete clusters with timestamp0
(15)  reduce clusters timestamp by1
(16)end while
(17)  gather all clusters in classification model
(18)  reconstruct micro-model


### 3.4.1. Injecting Labeled Instances

In our previous work [16], we assumed that labeling of flow instances can be done immediately after the learning process. Our extended experiment suggests that this is not possible since labeling of flow instances involves manual steps. Thus, we can only assume that some flow instances will be labeled externally and fed into the model once they are ready. Thus, the flow instances will be treated as a new flow instance and reclassified in order to get the necessary information such as confidence level and prediction results. In order to achieve minimum effort in injection, different handling methods based on the confidence level and prediction results are proposed for handling different possible scenarios. Table 2 shows the injection handling method for several scenarios. False prediction in trained flow instances will cause the trained cluster to be deleted immediately since the cluster is no longer reliable. Besides, new cluster with xi will be added if xi is not in the boundary of C1. This is true except for scenarios  2 and  3, since there is a possibility of xi to be within the boundary of C2. Figure 2(a) illustrates the example of boundary condition when xi is nearer to C1 but is in the boundary of C2. Merging xi to C2 will shift boundary of C2 towards C1 and can result in an overlap (Figure 2(b)). Thus, when C1 and C2 are of different classes, one of these clusters needs to be deleted. If they belong to the same class, xi will be ignored since its learning brings no significant changes to the model.Table 2
Injection handling method.
Scenario
Confidence level
Prediction
Procedure
1
0
True
Mergex with C1 if x∈RC1, else add new cluster for x
2
0
False
Mergex with C2 if x∈RC2 and yx=yC2, else add new cluster for x Delete C1
3
1
True
Ifx is not in R(C2), add new cluster for x
4
1
False
Add new cluster forx
5
2
True
Do nothing
6
2
False
EraseC1 and add new cluster for xFigure 2
Example of boundary condition (a) before model merging withC2 (b) after merging with C2.
(a)
(b)


### 3.4.2. Micromodel Reconstruction

In order to prevent the storing of all outdated clusters that may result in imbalanced micromodel, a micromodel reconstruction process is performed after a user-predefined number of flow instances (chunks) have been received. Clusters that are not utilized or underutilized will be deleted as they do not contribute to the classification decision. In addition, the micromodel reduction also aims to reduce memory footprint and classification time. This reduction process includes the following steps:(1)
All clusters are structured as a time-series based on the time they were created.(2)
All clusters are given zero timestamps.(3)
When a cluster is nominated as the nearest cluster in the classification process, the timestamps is incremented by one.(4)
When a chunk is received, the timestamps of each cluster is checked from the beginning of the series. Clusters with timestamps zero will be deleted until the number of clusters,k, is reduced to a user-predefined number, kd/B. Then, the timestamps of remaining clusters will be decremented by one. If in a situation where k>kd/B even after deleting all zero timestamps clusters, the deleting process will be repeated for timestamps one and so on until it reaches the required number of clusters.After the deletion of unused clusters, the remaining clusters will be repartitioned into B micromodels based on their centroid locations in the Euclidean space.


## 3.4.1. Injecting Labeled Instances

In our previous work [16], we assumed that labeling of flow instances can be done immediately after the learning process. Our extended experiment suggests that this is not possible since labeling of flow instances involves manual steps. Thus, we can only assume that some flow instances will be labeled externally and fed into the model once they are ready. Thus, the flow instances will be treated as a new flow instance and reclassified in order to get the necessary information such as confidence level and prediction results. In order to achieve minimum effort in injection, different handling methods based on the confidence level and prediction results are proposed for handling different possible scenarios. Table 2 shows the injection handling method for several scenarios. False prediction in trained flow instances will cause the trained cluster to be deleted immediately since the cluster is no longer reliable. Besides, new cluster with xi will be added if xi is not in the boundary of C1. This is true except for scenarios  2 and  3, since there is a possibility of xi to be within the boundary of C2. Figure 2(a) illustrates the example of boundary condition when xi is nearer to C1 but is in the boundary of C2. Merging xi to C2 will shift boundary of C2 towards C1 and can result in an overlap (Figure 2(b)). Thus, when C1 and C2 are of different classes, one of these clusters needs to be deleted. If they belong to the same class, xi will be ignored since its learning brings no significant changes to the model.Table 2
Injection handling method.
Scenario
Confidence level
Prediction
Procedure
1
0
True
Mergex with C1 if x∈RC1, else add new cluster for x
2
0
False
Mergex with C2 if x∈RC2 and yx=yC2, else add new cluster for x Delete C1
3
1
True
Ifx is not in R(C2), add new cluster for x
4
1
False
Add new cluster forx
5
2
True
Do nothing
6
2
False
EraseC1 and add new cluster for xFigure 2
Example of boundary condition (a) before model merging withC2 (b) after merging with C2.
(a)
(b)


## 3.4.2. Micromodel Reconstruction

In order to prevent the storing of all outdated clusters that may result in imbalanced micromodel, a micromodel reconstruction process is performed after a user-predefined number of flow instances (chunks) have been received. Clusters that are not utilized or underutilized will be deleted as they do not contribute to the classification decision. In addition, the micromodel reduction also aims to reduce memory footprint and classification time. This reduction process includes the following steps:(1)
All clusters are structured as a time-series based on the time they were created.(2)
All clusters are given zero timestamps.(3)
When a cluster is nominated as the nearest cluster in the classification process, the timestamps is incremented by one.(4)
When a chunk is received, the timestamps of each cluster is checked from the beginning of the series. Clusters with timestamps zero will be deleted until the number of clusters,k, is reduced to a user-predefined number, kd/B. Then, the timestamps of remaining clusters will be decremented by one. If in a situation where k>kd/B even after deleting all zero timestamps clusters, the deleting process will be repeated for timestamps one and so on until it reaches the required number of clusters.After the deletion of unused clusters, the remaining clusters will be repartitioned into B micromodels based on their centroid locations in the Euclidean space.


## 4. Analysis of Euclidean and Manhattan Distance Measures

The conversion from Euclidean distance to Manhattan distance for the incrementalk-means is not direct. Modifications on the clustering features and equations are needed to suit the used distance measure.


### 4.1. Euclidean Distance versus Manhattan Distance

Euclidean distance and Manhattan distance are the special variant of Minkowski distance. The Minkowski distance (see (6)) is the distance of order p between two points X and Y, where X=(x1,x2,…,xd) and Y=(y1,y2,…,yd). Manhattan distance is Minkowski distance in first order (p=1) (L1-Norm), while Euclidean distance is Minkowski distance in second order (p=2) (L2-Norm):(6)D=∑m=1dxm-ymp1/p.


### 4.2. Affected Elements

By changing the distance measures, the following elements in the proposed incrementalk-means algorithm need to be changed as well. These include the calculation of distance to origin Do (see (1)), distance between incoming instance and centroid (see (4)), and radius of a cluster (see (5)). The changes in R indirectly change the elements in CF. By applying p=1, the new equation for Do is as in (7), while new equation for D is as in (8). Consider the following:(7)Do=∑m=0dxim,(8)Dxi,μj=∑m=0dxim-μjm.For the case ofR, the original equation is in (9) before it can be translated in terms of LS→,SS→, (9)Rj=∑n=0Nj∑m=0dxnm-μjm2Nj,where Nj is the number of instances in cluster j, μj is the centroid of cluster j, and d is the dimension. After substituting p=2 to p=1, the new equation for R will be(10)Rj=∑n=0Nj∑m=0dxnm-μjmNj.Note that (10) is not able to be represented in LS→,SS→; hence the calculation of radius is no longer possible by only keeping the cluster summary; CFj=Nj,LSj→,SSj→,Tj,yj. For example, let a cluster j be with 3 instances (x1,x2,x3) in one dimension, d=1, and centroid, (11)μj=x1+x2+x3Nj.Expanding (10) will result in (12)Rj=x1-μj+x2-μj+x3-μjNj.When a new instance x4 is added into cluster j, the centroid will change to (13)μj′=x1+x2+x3+x4Nj.The new value of R will be (14)R′=x1-μj′+x2-μj′+x3-μj′+x4-μj′Nj.Each absolute element in (14) requires recalculation due to the changes of centroid, but each instance (x1,x2,x3) is not accessible (i.e., raw data are not kept). In this case, R′ could not be recalculated. In this paper, we suggest to calculate an approximation of R by storing the previous value of R in each dimension and the accumulation direction of the centroid change. New R can be calculated based on these values. Since a centroid is located in the middle of instance in the cluster and adding of new instance will only happen when it is within the radius, (xi∈Ri-1), we can assume that the changes of μi-1→μi are as small as possible, such that (xi-1-μi) will be in the same direction with (xi-1-μi-1). By taking into consideration the direction of change, we assume another instance in the cluster will have the change in the opposite direction. Thus, the changes will be canceled out. With this assumption, we can calculate the approximate of R as in (15). Consider the following:(15)Ri≈∑m=0dRi-1m+Ui-1m∗xim-μi-1m/Ni+xim-mimNn,(16)Ui=Ui-1+Utempi,(17)Utempi=1;xi>mi,-1;xi<mi,0;xi=mi.With these changes in the calculation of newR, LS→ and SS→ are no longer needed. New clustering features (CF) will be changed accordingly to CFj=Nj,Rj→,Uj→,Tj,yj. Merging new (xi→) to cluster j will cause recalculation of R based on (15), additive of U based on (16), and increment of N by 1, and T and y remain unchanged:(18)CFji=Nji-1+1,Rji→,Uji→,Tji-1,yji-1.


### 4.3. Complexity Comparison

Table3 shows the overall changes of our proposed method using Euclidean distance and Manhattan distance. For calculation of distance to origin, Do Euclidean distance requires ON2+dN2 compared to Manhattan distance that only requires O(d). Do is used in the determination of partition, which is required once every instance and affected the most in the reconstruction stage. During reconstruction, Do for all clusters in the classification model need to be calculated. Hence, it will increase the complexity of reconstruction by O(k).Table 3
Computation complexity for different distance measures.
Desc.
Euclidean
Manhattan
D
o
(
x
i
)
∑
m
=
0
d
x
i
m
2
∑
m
=
0
d
x
i
m
D
(
x
i
,
μ
j
)
∑
m
=
0
d
x
i
m
-
μ
j
m
2
∑
m
=
0
d
x
i
m
-
μ
j
m
R
(
C
j
)
∑
m
=
0
d
S
S
μ
j
m
-
∑
m
=
0
d
L
S
2
/
N
C
j
N
C
j
∑
m
=
0
d
R
i
-
1
m
+
U
i
-
1
m
∗
x
i
m
-
μ
i
-
1
m
/
N
i
+
x
i
m
-
m
i
m
N
n
C
F  additivity
C
F
j
i
=
N
j
i
-
1
+
1
,
L
S
j
i
-
1
→
+
x
i
→
,
S
S
j
i
-
1
→
+
x
i
→
2
,
T
j
i
-
1
,
y
j
i
-
1
C
F
j
i
=
N
j
i
-
1
+
1
,
R
j
i
→
,
U
j
i
→
,
T
j
i
-
1
,
y
j
i
-
1Similar toDo, the distance to centroid D for Euclidean distance also requires ON2+dN2 compared to Manhattan distance that only requires O(d). The increase in complexity in the calculation of D affects classification time by O(Nk).The radiusR is used during selection for learning and during injection of labeled instances. For calculation of R in Euclidean distance, OdN2+3N2 are required compared to O2dN2+N2 for Manhattan. In this case, the complexity is dependent on the dimension. As long as the dimension of dataset is greater than 2, the complexity of R in Manhattan distance is greater. Increase in complexity for the calculation of R directly affects the time for learning by ON.The updates ofCF in Euclidean distance are slightly simpler than Manhattan distance due to the recalculation of R for each dimension involved. This is the only trade-off of using Manhattan distance over Euclidean distance. However, since the updates of CF only happen during the learning and model reconstruction, it will increase the complexity of reconstruction by O(k).Overall, although the computations ofR and CF are more complex for Manhattan distance, they are not as frequent as the calculation of the distance D, which requires k calculations of D on every incoming flow instance.


## 4.1. Euclidean Distance versus Manhattan Distance

Euclidean distance and Manhattan distance are the special variant of Minkowski distance. The Minkowski distance (see (6)) is the distance of order p between two points X and Y, where X=(x1,x2,…,xd) and Y=(y1,y2,…,yd). Manhattan distance is Minkowski distance in first order (p=1) (L1-Norm), while Euclidean distance is Minkowski distance in second order (p=2) (L2-Norm):(6)D=∑m=1dxm-ymp1/p.


## 4.2. Affected Elements

By changing the distance measures, the following elements in the proposed incrementalk-means algorithm need to be changed as well. These include the calculation of distance to origin Do (see (1)), distance between incoming instance and centroid (see (4)), and radius of a cluster (see (5)). The changes in R indirectly change the elements in CF. By applying p=1, the new equation for Do is as in (7), while new equation for D is as in (8). Consider the following:(7)Do=∑m=0dxim,(8)Dxi,μj=∑m=0dxim-μjm.For the case ofR, the original equation is in (9) before it can be translated in terms of LS→,SS→, (9)Rj=∑n=0Nj∑m=0dxnm-μjm2Nj,where Nj is the number of instances in cluster j, μj is the centroid of cluster j, and d is the dimension. After substituting p=2 to p=1, the new equation for R will be(10)Rj=∑n=0Nj∑m=0dxnm-μjmNj.Note that (10) is not able to be represented in LS→,SS→; hence the calculation of radius is no longer possible by only keeping the cluster summary; CFj=Nj,LSj→,SSj→,Tj,yj. For example, let a cluster j be with 3 instances (x1,x2,x3) in one dimension, d=1, and centroid, (11)μj=x1+x2+x3Nj.Expanding (10) will result in (12)Rj=x1-μj+x2-μj+x3-μjNj.When a new instance x4 is added into cluster j, the centroid will change to (13)μj′=x1+x2+x3+x4Nj.The new value of R will be (14)R′=x1-μj′+x2-μj′+x3-μj′+x4-μj′Nj.Each absolute element in (14) requires recalculation due to the changes of centroid, but each instance (x1,x2,x3) is not accessible (i.e., raw data are not kept). In this case, R′ could not be recalculated. In this paper, we suggest to calculate an approximation of R by storing the previous value of R in each dimension and the accumulation direction of the centroid change. New R can be calculated based on these values. Since a centroid is located in the middle of instance in the cluster and adding of new instance will only happen when it is within the radius, (xi∈Ri-1), we can assume that the changes of μi-1→μi are as small as possible, such that (xi-1-μi) will be in the same direction with (xi-1-μi-1). By taking into consideration the direction of change, we assume another instance in the cluster will have the change in the opposite direction. Thus, the changes will be canceled out. With this assumption, we can calculate the approximate of R as in (15). Consider the following:(15)Ri≈∑m=0dRi-1m+Ui-1m∗xim-μi-1m/Ni+xim-mimNn,(16)Ui=Ui-1+Utempi,(17)Utempi=1;xi>mi,-1;xi<mi,0;xi=mi.With these changes in the calculation of newR, LS→ and SS→ are no longer needed. New clustering features (CF) will be changed accordingly to CFj=Nj,Rj→,Uj→,Tj,yj. Merging new (xi→) to cluster j will cause recalculation of R based on (15), additive of U based on (16), and increment of N by 1, and T and y remain unchanged:(18)CFji=Nji-1+1,Rji→,Uji→,Tji-1,yji-1.


## 4.3. Complexity Comparison

Table3 shows the overall changes of our proposed method using Euclidean distance and Manhattan distance. For calculation of distance to origin, Do Euclidean distance requires ON2+dN2 compared to Manhattan distance that only requires O(d). Do is used in the determination of partition, which is required once every instance and affected the most in the reconstruction stage. During reconstruction, Do for all clusters in the classification model need to be calculated. Hence, it will increase the complexity of reconstruction by O(k).Table 3
Computation complexity for different distance measures.
Desc.
Euclidean
Manhattan
D
o
(
x
i
)
∑
m
=
0
d
x
i
m
2
∑
m
=
0
d
x
i
m
D
(
x
i
,
μ
j
)
∑
m
=
0
d
x
i
m
-
μ
j
m
2
∑
m
=
0
d
x
i
m
-
μ
j
m
R
(
C
j
)
∑
m
=
0
d
S
S
μ
j
m
-
∑
m
=
0
d
L
S
2
/
N
C
j
N
C
j
∑
m
=
0
d
R
i
-
1
m
+
U
i
-
1
m
∗
x
i
m
-
μ
i
-
1
m
/
N
i
+
x
i
m
-
m
i
m
N
n
C
F  additivity
C
F
j
i
=
N
j
i
-
1
+
1
,
L
S
j
i
-
1
→
+
x
i
→
,
S
S
j
i
-
1
→
+
x
i
→
2
,
T
j
i
-
1
,
y
j
i
-
1
C
F
j
i
=
N
j
i
-
1
+
1
,
R
j
i
→
,
U
j
i
→
,
T
j
i
-
1
,
y
j
i
-
1Similar toDo, the distance to centroid D for Euclidean distance also requires ON2+dN2 compared to Manhattan distance that only requires O(d). The increase in complexity in the calculation of D affects classification time by O(Nk).The radiusR is used during selection for learning and during injection of labeled instances. For calculation of R in Euclidean distance, OdN2+3N2 are required compared to O2dN2+N2 for Manhattan. In this case, the complexity is dependent on the dimension. As long as the dimension of dataset is greater than 2, the complexity of R in Manhattan distance is greater. Increase in complexity for the calculation of R directly affects the time for learning by ON.The updates ofCF in Euclidean distance are slightly simpler than Manhattan distance due to the recalculation of R for each dimension involved. This is the only trade-off of using Manhattan distance over Euclidean distance. However, since the updates of CF only happen during the learning and model reconstruction, it will increase the complexity of reconstruction by O(k).Overall, although the computations ofR and CF are more complex for Manhattan distance, they are not as frequent as the calculation of the distance D, which requires k calculations of D on every incoming flow instance.


## 5. Experimental Results

This section describes the simulation setup and results of our proposed work. The experiment is conducted to analyze and compare the performance of our proposed method using Euclidean distance and Manhattan distance measures.


### 5.1. Datasets

Two real network traffic datasets Cambridge [14] and UNIBS [15] are chosen for the experiment. The Cambridge dataset was captured from University of Cambridge network. It contains 248 attributes and 12 classes. A total of 11 online features are selected from the attributes as listed in Table 4. The data of the minimal class, games, and interactive are not used as they are not sufficient for training and testing (less than 10 flow instances). UNIBS dataset was captured in University of Brescia. It was collected in three consecutive days and the traces are in pcap format and come with a groundtruth. The traces were processed to extract online features with only the first 5 packets of each observed flow as in [38]. By using the provided groundtruth labels, we labeled the flow instances into 5 classes (Web, Mail, P2P, SKYPE, and MSN). The details of the used datasets are summarized in Table 5.Table 4
List of online features selected for online classification.
ID
Name
Long description
Short description as in [14]
01
Source port
Source port number
Server port
02
Destination port
Destination port number
Client port
03
TL IP
Total bytes in IP packet
q1_data_ip
04
UL IP
Total bytes in IP packet (uplink)
q1_data_ip_a b
05
DL IP
Total bytes in IP packet (downlink)
q1_data_ip_b a
06
TL Eth
Total bytes in Ethernet packet
q1_data_wire
07
UL Eth
Total bytes in Ethernet packet (uplink)
q1_data_wire_a b
08
DL Eth
Total bytes in Ethernet packet (downlink)
q1_data_wire_b a
09
TL Ctr
Total control bytes in packet
q1_data_control
10
UL Ctr
Total control bytes in packet (uplink)
q1_data_control_a b
11
DL Ctr
Total control bytes in packet (downlink)
q1_data_control_b aTable 5
Dataset used.
Cambridge [14]
UNIBS [15]
Original
Selected
Extracted
# flow features
248
11
11
# classes
12
10
6
# flow instances
397,152
397,030
82752


### 5.2. Experimental Setup

The model parameters used in our experiment are as stated below, unless specified otherwise:(1)
Percentage of labeling,P=10.(2)
Chunk size = 1000.(3)
Number of micro-model,B=10.(4)
Desired number of cluster,kd=100.(5)
Boundary threshold = 1. In our experiment, the first chunk of data (the first 1000 flow instances) are treated as precollected flow instances and they are used for model initialization to generate the base model. The rest of the data are randomly labeled for different percentage P. The accuracy of the proposed model is verified using the interleaved test-then-train method where the data were first tested before being trained incrementally [39]. Each experiment was repeated 100 times, and the average performance indicators are reported in this paper.The performance indicators used in this paper are the accuracy, cumulative accuracy, time, classification speed, and memory requirement.Accuracy refers to the accuracy of each chunk, whilecumulative accuracy is the cumulative accuracy after the classification of each chunk.Running time is defined as the time to process one chunk, including the time for model reconstruction. In our experiment, the running time does not include data labeling time as in [12], since data labeling is usually done offline and is beyond the scope of discussion in this paper.Classification time is measured based on the time needed to classify one flow instance not including the feature extraction time.


### 5.3. Performance

This subsection discusses the overall performance of the proposed algorithm. The accuracy in time-series is shown in Figure3. As we only use the first chunk in the dataset for model initialization, the classes which were not seen in the first chunk are treated as new concepts. A drift detection experiment was conducted on our dataset by using Drift Detection Method [40] provided in MOA tools [41].Figure 3
Average accuracy of (a) Cambridge and (b) UNIBS datasets.
(a)
(b)A series of detected drifts are plotted in Figure4. We found out that Cambridge dataset has more detected drifts than the UNIBS dataset. In order to visualize the drifts clearly, we show the Cambridge dataset in different chunks range. In the figure, we observed that when concept drifts occur (drift detected = 1), our proposed algorithm (using either Euclidean distance or Manhattan distance) can learn from the new knowledge and is able to maintain network classification accuracy compared to the model without incremental learning. In order to clearly show the accuracy difference of our proposed method between both distance measures, the difference of accuracy when using Manhattan distance over Euclidean distance is shown in Figure 5. The results show that the proposed method using Manhattan distance can provide slightly higher accuracy than using Euclidean distance. This shows that simple distance measures can provide better performance.Figure 4
Accuracy of proposed method during concept drift occurrence: (a) Cambridge (chunks 0–130), (b) Cambridge (chunks 130–260), (c) Cambridge (chunks 260–400), and (d) UNIBS datasets.
(a)
(b)
(c)
(d)Figure 5
Accuracy difference between Manhattan distance and Euclidean distance for (a) Cambridge and (b) UNIBS datasets.
(a)
(b)Table6 shows the overall performance of our proposed algorithm. In this paper, we assume that the classifier is the bottleneck of the network traffic classification system, as reported in several works such as [38], flow features extraction in FPGA can function in very high speed. We compute the performance of the classification in terms of millisecond per flow instances in software as that is the lower bound of the system performance. The classification time of our proposed algorithm with Euclidean distance is 4.45 ms to classify 1,000 flow instances and 1.49 ms to classify 1,000 flow instances when using the Manhattan distance. This shows that using Manhattan distance can increase the classification speed by almost 3 times. Besides, we found that the time for injecting a labeled flow instance was similar to the time for classifying a new flow instance. Thus, injecting labeled flow instance will not cause long delay to affect the overall online classification process. Time for reconstruction is less than 1% of the total running time and it is almost negligible for both methods. Our proposed system does not require large memory as only the summary of cluster’s information, CF, is kept. It only requires in average 140 KiB RAM to complete the processes. Since both of the proposed method store similar amount of data, CFj=Nj,LSj→,SSj→,Tj,yj for Euclidean distance and CFj=Nj,Rj→,Uj→,Tj,yj for Manhattan distance, respectively, the overall memory consumption of both methods is similar.Table 6
Overall performance comparison.
Dataset
Cambridge
UNIBS
Distance measure
Euclidean
Manhattan
Euclidean
Manhattan
Average accuracy (%)
94.15
94.38
86.71
88.79
Running time (ms/1,000 flow instances)
5.14
1.75
6.93
2.39
Classification time (ms/1,000 flow instances)
4.45
1.49
6.03
2.02
Injecting labeled instance time (μs/labeled flow instances)
4.68
1.57
6.47
2.32
Reconstruction time (ms/chunk)
0.18
0.09
0.19
0.11
Memory required (KiB)
140
140
140
140


### 5.4. Impact of Different Parameters Setting on Classification Performance

In this subsection, we analyze the effect of changing algorithm parameters on the overall classification performance. The experiments are done by changing one parameter and fixing the others. Figures6 and 7 show how labeling percentage, P, is affecting the accuracy and running time, respectively. Increases in labeled flow instances provide more class information to the classification model for better accuracy. Our experimental results also show that the use of Manhattan distance provides better accuracy than Euclidean distance. The percentage of labeling does not affect classification time, but it will increase running time that is more significant for high labeling percentage. This is due to the fact that the more the labeled data are injected to the classification model, the more distance the measure needs to be calculated. Hence the running time difference becomes more significant.Figure 6
The impact of labeling percentage,P on accuracy (a) Cambridge and (b) UNIBS datasets.
(a)
(b)Figure 7
The impact of labeling percentage,P on classification time (a) Cambridge and (b) UNIBS datasets.
(a)
(b)The number of desired clusters,kd, is the parameter used in model reconstruction process. It is used to maintain the number of clusters in the classification model. Figures 8 and 9 show the impact of different number of desired clusters on accuracy and reconstruction time, respectively. The increasing accuracy and reconstruction time are more consistent with the increase in kd for proposed method using Manhattan distance. Reconstruction time for our proposed method with Euclidean distance is higher due to the fact that origin distance calculation required for Euclidean distance in the reconstruction stage is more complex than Manhattan distance.Figure 8
The impact of different number of desired cluster,kd on accuracy (a) Cambridge and (b) UNIBS datasets.
(a)
(b)Figure 9
The impact of different number of desired cluster,kd on classification time (a) Cambridge and (b) UNIBS datasets.
(a)
(b)


## 5.1. Datasets

Two real network traffic datasets Cambridge [14] and UNIBS [15] are chosen for the experiment. The Cambridge dataset was captured from University of Cambridge network. It contains 248 attributes and 12 classes. A total of 11 online features are selected from the attributes as listed in Table 4. The data of the minimal class, games, and interactive are not used as they are not sufficient for training and testing (less than 10 flow instances). UNIBS dataset was captured in University of Brescia. It was collected in three consecutive days and the traces are in pcap format and come with a groundtruth. The traces were processed to extract online features with only the first 5 packets of each observed flow as in [38]. By using the provided groundtruth labels, we labeled the flow instances into 5 classes (Web, Mail, P2P, SKYPE, and MSN). The details of the used datasets are summarized in Table 5.Table 4
List of online features selected for online classification.
ID
Name
Long description
Short description as in [14]
01
Source port
Source port number
Server port
02
Destination port
Destination port number
Client port
03
TL IP
Total bytes in IP packet
q1_data_ip
04
UL IP
Total bytes in IP packet (uplink)
q1_data_ip_a b
05
DL IP
Total bytes in IP packet (downlink)
q1_data_ip_b a
06
TL Eth
Total bytes in Ethernet packet
q1_data_wire
07
UL Eth
Total bytes in Ethernet packet (uplink)
q1_data_wire_a b
08
DL Eth
Total bytes in Ethernet packet (downlink)
q1_data_wire_b a
09
TL Ctr
Total control bytes in packet
q1_data_control
10
UL Ctr
Total control bytes in packet (uplink)
q1_data_control_a b
11
DL Ctr
Total control bytes in packet (downlink)
q1_data_control_b aTable 5
Dataset used.
Cambridge [14]
UNIBS [15]
Original
Selected
Extracted
# flow features
248
11
11
# classes
12
10
6
# flow instances
397,152
397,030
82752


## 5.2. Experimental Setup

The model parameters used in our experiment are as stated below, unless specified otherwise:(1)
Percentage of labeling,P=10.(2)
Chunk size = 1000.(3)
Number of micro-model,B=10.(4)
Desired number of cluster,kd=100.(5)
Boundary threshold = 1. In our experiment, the first chunk of data (the first 1000 flow instances) are treated as precollected flow instances and they are used for model initialization to generate the base model. The rest of the data are randomly labeled for different percentage P. The accuracy of the proposed model is verified using the interleaved test-then-train method where the data were first tested before being trained incrementally [39]. Each experiment was repeated 100 times, and the average performance indicators are reported in this paper.The performance indicators used in this paper are the accuracy, cumulative accuracy, time, classification speed, and memory requirement.Accuracy refers to the accuracy of each chunk, whilecumulative accuracy is the cumulative accuracy after the classification of each chunk.Running time is defined as the time to process one chunk, including the time for model reconstruction. In our experiment, the running time does not include data labeling time as in [12], since data labeling is usually done offline and is beyond the scope of discussion in this paper.Classification time is measured based on the time needed to classify one flow instance not including the feature extraction time.


## 5.3. Performance

This subsection discusses the overall performance of the proposed algorithm. The accuracy in time-series is shown in Figure3. As we only use the first chunk in the dataset for model initialization, the classes which were not seen in the first chunk are treated as new concepts. A drift detection experiment was conducted on our dataset by using Drift Detection Method [40] provided in MOA tools [41].Figure 3
Average accuracy of (a) Cambridge and (b) UNIBS datasets.
(a)
(b)A series of detected drifts are plotted in Figure4. We found out that Cambridge dataset has more detected drifts than the UNIBS dataset. In order to visualize the drifts clearly, we show the Cambridge dataset in different chunks range. In the figure, we observed that when concept drifts occur (drift detected = 1), our proposed algorithm (using either Euclidean distance or Manhattan distance) can learn from the new knowledge and is able to maintain network classification accuracy compared to the model without incremental learning. In order to clearly show the accuracy difference of our proposed method between both distance measures, the difference of accuracy when using Manhattan distance over Euclidean distance is shown in Figure 5. The results show that the proposed method using Manhattan distance can provide slightly higher accuracy than using Euclidean distance. This shows that simple distance measures can provide better performance.Figure 4
Accuracy of proposed method during concept drift occurrence: (a) Cambridge (chunks 0–130), (b) Cambridge (chunks 130–260), (c) Cambridge (chunks 260–400), and (d) UNIBS datasets.
(a)
(b)
(c)
(d)Figure 5
Accuracy difference between Manhattan distance and Euclidean distance for (a) Cambridge and (b) UNIBS datasets.
(a)
(b)Table6 shows the overall performance of our proposed algorithm. In this paper, we assume that the classifier is the bottleneck of the network traffic classification system, as reported in several works such as [38], flow features extraction in FPGA can function in very high speed. We compute the performance of the classification in terms of millisecond per flow instances in software as that is the lower bound of the system performance. The classification time of our proposed algorithm with Euclidean distance is 4.45 ms to classify 1,000 flow instances and 1.49 ms to classify 1,000 flow instances when using the Manhattan distance. This shows that using Manhattan distance can increase the classification speed by almost 3 times. Besides, we found that the time for injecting a labeled flow instance was similar to the time for classifying a new flow instance. Thus, injecting labeled flow instance will not cause long delay to affect the overall online classification process. Time for reconstruction is less than 1% of the total running time and it is almost negligible for both methods. Our proposed system does not require large memory as only the summary of cluster’s information, CF, is kept. It only requires in average 140 KiB RAM to complete the processes. Since both of the proposed method store similar amount of data, CFj=Nj,LSj→,SSj→,Tj,yj for Euclidean distance and CFj=Nj,Rj→,Uj→,Tj,yj for Manhattan distance, respectively, the overall memory consumption of both methods is similar.Table 6
Overall performance comparison.
Dataset
Cambridge
UNIBS
Distance measure
Euclidean
Manhattan
Euclidean
Manhattan
Average accuracy (%)
94.15
94.38
86.71
88.79
Running time (ms/1,000 flow instances)
5.14
1.75
6.93
2.39
Classification time (ms/1,000 flow instances)
4.45
1.49
6.03
2.02
Injecting labeled instance time (μs/labeled flow instances)
4.68
1.57
6.47
2.32
Reconstruction time (ms/chunk)
0.18
0.09
0.19
0.11
Memory required (KiB)
140
140
140
140


## 5.4. Impact of Different Parameters Setting on Classification Performance

In this subsection, we analyze the effect of changing algorithm parameters on the overall classification performance. The experiments are done by changing one parameter and fixing the others. Figures6 and 7 show how labeling percentage, P, is affecting the accuracy and running time, respectively. Increases in labeled flow instances provide more class information to the classification model for better accuracy. Our experimental results also show that the use of Manhattan distance provides better accuracy than Euclidean distance. The percentage of labeling does not affect classification time, but it will increase running time that is more significant for high labeling percentage. This is due to the fact that the more the labeled data are injected to the classification model, the more distance the measure needs to be calculated. Hence the running time difference becomes more significant.Figure 6
The impact of labeling percentage,P on accuracy (a) Cambridge and (b) UNIBS datasets.
(a)
(b)Figure 7
The impact of labeling percentage,P on classification time (a) Cambridge and (b) UNIBS datasets.
(a)
(b)The number of desired clusters,kd, is the parameter used in model reconstruction process. It is used to maintain the number of clusters in the classification model. Figures 8 and 9 show the impact of different number of desired clusters on accuracy and reconstruction time, respectively. The increasing accuracy and reconstruction time are more consistent with the increase in kd for proposed method using Manhattan distance. Reconstruction time for our proposed method with Euclidean distance is higher due to the fact that origin distance calculation required for Euclidean distance in the reconstruction stage is more complex than Manhattan distance.Figure 8
The impact of different number of desired cluster,kd on accuracy (a) Cambridge and (b) UNIBS datasets.
(a)
(b)Figure 9
The impact of different number of desired cluster,kd on classification time (a) Cambridge and (b) UNIBS datasets.
(a)
(b)


## 6. Conclusion

This paper proposed and analyzed an online incremental learning high bandwidth network traffic classification method with two different distance measures (Euclidean and Manhattan distance). The use of Manhattan distance not only provides improvement in running and classification time, it also slightly improves the average accuracy. In future, we will implement this work in reprogrammable hardware so that it can perform inline classification of live network traffic.



---

*Source: 1465810-2016-02-25.xml*