This paper presents a novel scheme for parallel packet classification. The basic idea behind the scheme, which differentiates it from other parallel classification schemes, is that the results of parallel range searches on different packet header segments embed classification rule information in the form of prefixes. The overall classification result can then be determined by applying a conventional longest matching prefix search on these intermediate search results, which are interleaved in a specific order. This provides two key advantages over other methods. First, the storage requirements can be reduced significantly, which is an essential prerequisite for scaling beyond a couple of thousand rules. Second, the assignment of intermediate result values becomes more flexible, which makes it possible to perform dynamic updates for at least a selected subset of the classification rules.
By: A.P.J. Engbersen, J. van Lunteren
Published in: RZ3210 in 2000
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .