Technical Report Number
Packet classiﬁcation is a multi-ﬁeld searching task performed by Internet routers in order to apply security policies and network services to packets belonging to deﬁned trafﬁc ﬂows. As this searching task must be performed for every packet traversing a router, fast and scalable solutions are required in order to prevent packet classiﬁcation from becoming a performance bottleneck. A wide variety of packet classiﬁcation al-gorithms and devices exist in the research literature and commercial market. The existing solutions exploit various design tradeoffs to provide high search rates, power and space efﬁciency, fast incremental updates, or the ability to scale to large numbers of ﬁlters. Despite the energetic attention of the academic and cor-porate research communities, there remains a need for techniques that achieve a favorable balance among these tradeoffs and scale to support classiﬁcation on additional ﬁelds beyond the standard 5-tuple. In re-sponse, we introduce Distributed Crossproducting of Field Labels (DCFL), a novel combination of new and existing packet classiﬁcation techniques that leverages key observations of the structure of real ﬁlter sets and takes advantage of the capabilities of modern hardware technology. Using a collection of real and synthetic ﬁlter sets of various sizes and compositions, we provide analyses of DCFL performance and resource re-quirements. An optimized implementation of DCFL can provide over 100 million searches per second and storage for over 200 thousand ﬁlters in a current generation FPGA or ASIC without the need for external memory devices.
Taylor, David E. and Turner, Jonathan S., "Scalable Packet Classification using Distributed Crossproducting of Field Labels" Report Number: WUCSE-2004-38 (2004). All Computer Science and Engineering Research.