Please use this identifier to cite or link to this item:
標題: TCAM-Based Multi-Match Packet Classification Using Multidimensional Rule Layering
作者: Dao-Yuan Chang
Pi-Chung Wang
關鍵字: Encoding
Image color analysis
Random access memory
IEEE transactions
Partitioning algorithms
Algorithm design and analysis
摘要: Ternary content addressable memory (TCAM) has superior performance for single-match packet classification but not the case for multi-match packet classification. The limitation is caused by TCAM architecture that reports only the first matching rule. To cope with the limitation, previous algorithms use extra TCAM entries or accesses, or both, to fulfill multi-match packet classification. These algorithms also reorder rules; thus, a multi-match classifier based on these algorithms cannot maintain performance for single-match packet classification. In other words, all matching rules must be yielded to determine the highest priority matching rule. In this paper, we present a TCAM-based scheme for multi-match packet classification without single-match penalty. Our scheme partitions a rule set based on range layering, which can be applied to achieve range encoding. The rule partitioning generates rule subsets which satisfy that the rules in a subset are mutually disjoint. Each rule is then tagged a bitmap for subset identification to fulfill multi-match packet classification. Two approaches, loose coupling and tight coupling, are derived with different search procedures while incorporating range encoding. Both approaches can maintain original rule order, but with different performance tradeoff. We also present a refinement which uses all available TCAM entries to improve the performance of multi-match packet classification. The experimental results show that combining range encoding with multi-match packet classification has advantages of storage efficiency and speed superiority. The capability of supporting single-match packet classification also provides better flexibility of applying different packet actions.
Appears in Collections:資訊科學與工程學系所



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.