Title :
Gigabit packet classification by using lookahead caching
Author :
Wang, Pi-Chung ; Tseng, Wei-Chun ; Chan, Chia-Tai ; Chen, Yaw-Chung
Author_Institution :
Telecommun. Labs., Chunghwa Telecom Co. Ltd., Taipei, Taiwan
Abstract :
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. We proposed a novel "lookahead caching" which can significantly improve the performance of the hash-based algorithm. The basic idea is to find out the unmatched 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.
Keywords :
Internet; cache storage; performance evaluation; IP lookup; Internet lookup; experiments; gigabit packet classification; hash-based algorithm; lookahead caching; memory access; multiple hash access; parallel processing; performance; rectangular search; scalability; Databases; Information filtering; Information filters; Internet; Laboratories; Matched filters; Random access memory; Scalability; Telecommunications; Throughput;
Conference_Titel :
Computer Software and Applications Conference, 2002. COMPSAC 2002. Proceedings. 26th Annual International
Print_ISBN :
0-7695-1727-7
DOI :
10.1109/CMPSAC.2002.1044541