Description
In this assignment you are required to code a traffic packet clustering engine to cluster the raw network packet to different applications, such as http, smtp. To accomplish this assignment, a data preprocessing module and a clustering module should be implemented, the structure is illustrated below:
You have two input files, and you should print two output files.
The input file1 contains a distance threshold and the raw network packet information, that is, seven attributes of a packet: source address, source port, destination address, destination port, protocol, arrival time, and packet length. input file1.txt is Sample traffic flow information;
Input file2.txt has a number K, and on the next line include K integer numbers represent an initial set of K medoids.
In the data preprocessing module, your program should prepare the flow data for clustering by the raw packet data, two steps are involved: you need to firstly merge the packets into flows by the rule: a network flow includes at least TWO packets with same source address, source port, destination address, destination port, and protocol, then calculate two clustering features: average transferring time and the average packet length of a flow.
In the clustering module, you need to apply k-medoids algorithm (course slides Chapter 10, not the book’s random method) to find the minimum number of clusters that the sum of the distance of each flow to its centroid is less than the given threshold. Note: the clustering features come from data preprocessing module, the distance measurement is Mannhaton distance. For your convenience, below is the framework of the k-medoids algorithm which you should follow:
Example
Sample traffic flow information
src addr src port dst addr dst port protocol arrival time packet length
202.234.224.254 49880 31.65.181.210 80 6 115258 52
202.234.224.254 49880 31.65.181.210 80 6 115307 52
202.234.35.144 55256 74.39.124.220 443 6 115310 46 119.188.179.82 50592 150.79.7.129 80 6 115314 40 202.234.224.254 49880 31.65.181.210 80 6 115341 52 119.188.179.82 50592 150.79.7.129 80 6 115350 40
119.188.179.82 50592 150.79.7.129 80 6 115363 40
Data preprocessing module
In the above traffic flow information, there are two flows: The first, second, and fifth packet belong to the first flow(index is 0); the fourth, sixth, and seventh packet belong to the second flow(index is 1).
The Average transferring time of first flow = (( the arrival time of fifth packet – the arrival time of second packet ) + (the arrival time of second packet – the arrival time of first packet)) ÷ (3 – 1) = ((115341 – 115307) + (115307 – 115258)) ÷ 2 = 41.5. The Average length of first flow = (P packet length) ÷ 3 = (52 + 52 + 52) ÷ 3 = 52. Similarly, the Average transferring time of second flow = 24.5, the average length of second flow = 40. (arrival time is microsecond(µs))
Clustering module
We use Mannhaton distance to measure the distance between flows. In our sample, the distance between the two flows is |41.5 − 24.5| + |52 − 40|.
Example input initial medoids.txt — initial k medoids
1 (k=1)
0 (Start from index 0, as the initial start medoid)
Example Output
At begin you should output the flow after Data preprocessing module, include index, average transferring time x value and average length y value.
ID X Y
In this case, flow.txt should print:
- 50 52.00
- 50 40.00
Rounding numbers (X,Y) to 2 decimal place. You can use:
cout << fixed << setprecision(2) << 3.1415926;
or
printf(”%0.2f”,3.1415926);
After doing KMedoid, you will get K clusters. It includes K+2 lines. First line is absoluteerror criterion. Next one line include K medoids’ index. Following each line have several flow index represent each medoid includes which flows.
29.00 (Absolute-error of the cluster,2 decimal place)
0 (Medoid is 0)
0 1 (This cluster include 2 flows index 0 and index 1)
