Hashing is a widely used method to perform fast lookup. Several schemes have been proposed to support Internet lookup that includes IP lookup and packet classification. Rectangular search is a well-known packet classification scheme based on multiple hash accesses for different filter length. It shows good scalability with respect to the number of filters; however, the lookup performance is not satisfactory. For example, through experiments, each packet classification takes about 40 hash accesses in a 100,000-filter database and each hash access may take more than one memory access. Obviously, this is insufficient to provide gigabits throughput. In this paper, we proposed a novel "Lookahead Caching" which can significantly improve the performance of hash-based algorithm. The basic idea is to find out the un-matched case for each incoming packet, thus it is different from the traditional caching mechanism. The experimental results indicate that the proposed scheme can improve the performance by a factor of two. The scheme can be further enhanced using parallel processing.
|Number of pages||5|
|Journal||Proceedings - IEEE Computer Society's International Computer Software and Applications Conference|
|State||Published - 26 Aug 2002|
|Event||26th Annual International Computer Software and Applications Conference - Oxford, United Kingdom|
Duration: 26 Aug 2002 → 29 Aug 2002