DocumentCode :
2407919
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
fYear :
2002
fDate :
2002
Firstpage :
117
Lastpage :
121
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Software and Applications Conference, 2002. COMPSAC 2002. Proceedings. 26th Annual International
ISSN :
0730-3157
Print_ISBN :
0-7695-1727-7
Type :
conf
DOI :
10.1109/CMPSAC.2002.1044541
Filename :
1044541
Link To Document :
بازگشت