SCALABLE PACKET CLASSIFICATION BY USING HASH-BASED ALGORITHMS - Computer Science Research and Technology - page 178

3.5.3. Comparative Analysis of Our Scheme and Previous Schemes

We did the third evaluation by comparing our scheme with other notable schemes. The
schemes from previous work include ABV [12], HyperCuts [10], RFC [2] and Pruned Tuple
Space Search ( PTSS ) [8]. For the ABV scheme, the aggregate size is 32 bits, and the memory
width is 256 bits. Hypercuts adopts the setting in which the space factor is 1 and bucket size
is 32. For our scheme, the value of C threshold is set to 64K, and all of the refinements are
used. The size of the hash table is set to two times the number of the stored entries, and the
hash collision is resolved by linked-list chaining. In the following results, the performance
metrics include the required storage in kilobytes and the numbers of memory accesses in
the average case (AMA) and the worst case (WMA). The required storage includes all
necessary data structures for performing packet classification; hence, the required space of
d multi-way search trees is also included. The values of AMA are derived by dividing the
total number of memory accesses for classifying every packet header in the trace from the
number of classified packet headers.
Table 11 shows the storage performance of the proposed scheme and other existing
schemes, and Table 12 lists the speed performance. The experimental results show that our
algorithm has better storage performance than RFC , but worse than the other schemes. On
the contrary, our algorithm has better search performance than most schemes, except RFC .
The results show the trade-off between storage and speed performance lying in the algo-
rithms of packet classification. Although our algorithm does not show significant advan-
tages over the existing algorithms, most of the existing schemes, except for PTSS , cannot
support incremental updates [4].

Therefore, our algorithm has better feasibility than the

existing schemes.

Table 11. Storage Performance of the Existing Algorithms Using Real Databases.

Real Original Our Scheme

Database Filters ABV HyperCuts RFC PTSS PLT NLT

ACL1 752 296.34 29.45 497.62 293.17 422.42 377.55

FW1 269 263.73 33.41 1,094.55 274.39 336.97 396.39

IPC1 1,550 331.46 142.18 8,984.18 299.15 605.39 495.73

Table 12. Speed Performance of the Existing Algorithms Using Real Databases.

Our Scheme

Real ABV HyperCuts RFC PTSS PLT NLT

Database AMA WMA AMA WMA AMA WMA AMA WMA AMA WMA AMA WMA

ACL1 35.13 44 14.79 22 11 11 20.18 32 15.75 19 15.98 21

FW1 20.49 30 21.37 46 11 11 85.25 124 13.79 17 14.96 19

IPC1 26.14 50 22.44 49 11 11 25.72 48 18.30 24 17.90 24

We also note that the performance difference between using PLTs or NLTs in our al-
gorithm is usually less than 10%. Since tuple space based on PLTs could provide better
renewability than based on NLTs, we can use the PLT-based tuple space for network de-
vices with frequent updates, such as QoS routers. On the other hand, NLT-based tuple
space requires less tuples than PLT-based tuple space; therefore, it could reduce the over-
head of hash table management. Therefore, the NLT-based tuple space is suitable for rather
static network devices, such as firewalls or network intrusion detection systems.