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

Table 23. Comparative Evaluation of Speed Performance Using Real Databases.

Databases Filters ABV HyperCuts PTSS RFC Our Scheme

ACL1 752 296.34 29.45 293.17 497.62 293.93

FW1 269 263.73 33.41 274.39 1,094.55 280.35

IPC1 1,550 331.46 142.18 299.15 8,984.18 306.42

Table 24. Comparative Evaluation of Speed Performance Using Real Databases.

ABV HyperCuts PTSS RFC Our Scheme

Databases AMA WMA AMA WMA AMA WMA AMA WMA AMA WMA

ACL1 35.13 44 14.79 22 20.18 32 11 11 17.52 25

FW1 20.49 30 21.37 46 85.25 124 11 11 19.73 47

IPC1 26.14 50 22.44 49 25.72 48 11 11 19.45 32

thetic databases. Table 25 shows that our scheme still consumes slightly more storage than
PTSS , but it outperforms the other algorithms in most cases of storage performance. In
addition, our scheme is the fastest among these algorithms, as shown in Table 26. Since
the search performance of ABV is proportional to the number of filters and that of Hy-
perCuts ties to the characteristics of filters, our scheme combines the storage efficiency of
PTSS with efficient pre-computation to achieve a better balance between storage and speed
performance.

Table 25. Comparative Evaluation of Storage Performance Using Synthetic
Databases.

Databases Filters ABV HyperCuts PTSS Our Scheme

ACL1 15,926 36,523.81 369.18 1,010.32 1,011.77

ACL2 15,447 55,141.81 1,359.68 2,055.93 2,062.33

ACL3 14,729 7,803.02 2,721.50 726.90 763.16

ACL4 15,405 13,306.42 1,985.26 793.31 838.88

ACL5 10,379 4,545.09 294.45 534.08 534.75

FW1 14,898 32,494.13 23,883.84 2,205.53 2,212.39

FW2 15,501 39,885.48 10,859.94 1,962.20 1,962.34

FW3 14,297 27,532.10 27,172.06 1,878.96 1,882.41

FW4 13,856 31,231.93 10,717.61 2,855.36 2,878.57

FW5 14,009 26,260.04 19,503.95 1,750.74 1,756.17

IPC1 14,954 16,116.21 3,557.90 716.50 732.50

IPC2 16,000 44,405.32 12,450.29 1,893.48 1,893.49

6. Conclusion

In this chapter, we present three algorithms for efficient packet classification based on hash
tables. The first two algorithms combine hash-based algorithm with two complementary
algorithms. These combinations are based on the observation that Cross-producting and Bit
Vectors are complementary to hash-based algorithm in certain filter databases. This obser-
vation motivates us to develop two algorithms of filter categorization. For the combination
with Cross-producting , the filters are either stored in a cross-product table or a tuple space.