Evaluate the performance of hyper rule cache - Cache hit ratio

Hit ratio of hyper rule cache

Trace	Number of pkts	2 actions(%)	100 actions(%)
Trace 3	7439801	99.32883	99.19437
Trace 5	7432650	99.35800	99.24929
Trace 10	7448271	99.36112	99.22063

Evaluate the performance of hyper rule cache - Number of evolving rules

Number of evolving rules of hyper rule cache (100 actions)

Trace	Number of pkts	Avg	Max
Trace 3	7439801	17	24
Trace 5	7432650	16	24
Trace 10	7448271	18	27

Number of evolving rules of hyper rule cache (2 actions)

Trace	Number of pkts	Avg	Max
Trace 3	7439801	14	21
Trace 5	7432650	14	22
Trace 10	7448271	15	23

Evaluate the performance of hyper rule cache - Average cache update time

The following table shows the average cache update time of hyper rule cache on 3 different traces and the rule set(1802 rules) with 2 and 100 actions respectively.

Average cache update time of hyper rule cache

Trace	Number of pkts	2 actions	100 actions
Trace 3	7439801	169μs	219μs
Trace 5	7432650	159μs	187μs
Trace 10	7448271	166μs	20μs

Evaluate the performance of hyper rule cache - experiment setup

We evaluate the performance of hyper rule cache using 3 real traffic traces and a real rule set with 1802 rules, obtained from a tier-1 ISP. We randomly generate 2 and 100 actions respectively for each rule in the rule set.

All the experiments are run in a machine with Dual Core AMD Opteron(tm) Processor 275 CPU (2.2
GHz). The total memory of the machine is 16GB. Hyper rule cache and smart rule cache are run using same parameters, and under same conditions. The sliding window size is set to 1024.

Verify the correctness of Hyper rule cache

To verify the correctness of hyper rule cache, two rule sets and associated trace files are used. Each packet in the trace file is associated with the correct rule that matches it. These files can be found from the following website: http://www.arl.wustl.edu/ hs1/project/.

We randomly generate 2, 4 and 10 actions for each rule in the two rule sets, and run hyper rule cache on these 6 pairs of rule set and traces. The action of each packet that is hit in the rule cache is printed out, and is compared with its real action.

Our experiments show that for each packet hit in rule cache, hyper rule cache give the same action as its real action. The results are summarized in table 3. As can be seen in the table, in all the 6 cases, 100% of packets are correctly classified by hyper rule cache, which proves the correctness of hyper rule cache scheme.

Hyper Rule Cache

A new packet classification scheme, hyper rule cache, is proposed. Hyper rule cache achieves high speed packet classification by caching a small number of evolving rules, which are updated continuously according to the characteristics of incoming traffic.

Hyper rule cache inherits the idea of caching dynamic rules from smart rule cache scheme, with several major modifications.

Firstly, Smart rule cache uses PPDD tree structure to store rules, which consumes huge memory
space especially for larger rule set. Hyper rule cache replaces PPDD with HyperCuts decision tree. HyperCuts tree is a popular structure for packet classification.

Hyper rule cache also proposed an algorithm for checking the HyperCuts tree whether an expanded rule conflicts with the semantics of the original rule set.

Finally, Hyper rule cache modified how the evolving rules are constructed, which makes PPDD tree unnecessary.

Hypercut coding

We've gotten the hypercut code translated from C++ to C and have integrated it into our code. We are testing the code for errors and making sure that it still gives the correct output.