Effective Bit Selection Methods for Improving Performance of Packet Classifications on IP Routers

Gang QIN  Shingo ATA  Ikuo OKA  Chikato FUJIWARA  

IEICE TRANSACTIONS on Communications   Vol.E90-B   No.5   pp.1090-1097
Publication Date: 2007/05/01
Online ISSN: 1745-1345
DOI: 10.1093/ietcom/e90-b.5.1090
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Switching for Communications
patricia trie,  content addressable memory,  quality of service,  backbone router,  edge router,  

Full Text: PDF(687.6KB)>>
Buy this Article

This paper investigates fast Packet Classification techniques, where a large routing table is divided into many much smaller tables by an index key at first; the resulting small tables are much easier to search. A traditional way is to use the front bits as the index key, but we show it's not an effective way to divide a routing table. In this paper, we propose three bit selection methods for division. They can be implemented by CAM or hash structure. Simulations show that the bit selection methods decrease the delay of classification 50% compared to the traditional method. We also propose an optimized method which is adapted to the biased traffic pattern, which shows 70% improvement in our simulation.