Scalable Packet Classification Using Condensate Bit Vector

Pi-Chung WANG  Hung-Yi CHANG  Chia-Tai CHAN  Shuo-Cheng HU 

Publication
IEICE TRANSACTIONS on Communications  Vol.E88-B  No.4  pp.1440-1447
Publication Date: 2005/04/01
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Internet Technology V)
Category: 
Keyword: 
packet classification,  bit vector,  aggregation,  scalability, 

Full Text: PDF(1.3MB)

Summary: 
Packet classification is important in fulfilling the requirements of differentiated services in next generation networks. One of interesting hardware solutions proposed to solve the packet classification problem is bit vector algorithm. Different from other hardware solutions such as ternary CAM, it efficiently utilizes the memories to achieve an excellent performance in medium size policy database; however, it exhibits poor worst-case performance with a potentially large number of policies. In this paper, we proposed an improved bit-vector algorithm named Condensate Bit Vector which can be adapted to large policy databases in the backbone network. Experiments showed that our proposed algorithm drastically improves in the storage requirements and search speed as compared to the original algorithm.