Telecommunication

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 num-ber of fil ters; however, the lookup performance is not sat-isfactory. 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 pro-vide gigabits throughput. In this paper, we proposed a novel ”Lookahead Caching ” which can significantly im-prove the performance of hash-based algorithm. The ba-sic idea is to find out the un-matched case for each incom-ing packet, thus it is different from the traditional caching mechanism. The experimental results indicate that the pro-posed scheme can improve the performance by a factor of two. The scheme can be further enhanced using parallel processing. 1