Document Type

Technical Report

Publication Date

2004-06-23

Filename

wucse-2004-38.pdf

Technical Report Number

WUCSE-2004-38

Abstract

Packet classification is a multi-field searching task performed by Internet routers in order to apply security policies and network services to packets belonging to defined traffic flows. As this searching task must be performed for every packet traversing a router, fast and scalable solutions are required in order to prevent packet classification from becoming a performance bottleneck. A wide variety of packet classification 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 efficiency, fast incremental updates, or the ability to scale to large numbers of filters. 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 classification on additional fields beyond the standard 5-tuple. In re-sponse, we introduce Distributed Crossproducting of Field Labels (DCFL), a novel combination of new and existing packet classification techniques that leverages key observations of the structure of real filter sets and takes advantage of the capabilities of modern hardware technology. Using a collection of real and synthetic filter 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 filters in a current generation FPGA or ASIC without the need for external memory devices.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7X928N9

Download

Share

COinS