Tradeoffs for packet classification

Anja Feldmann, S. Muthukrishnan

    Research output: Contribution to journalConference articlepeer-review


    We present an algorithmic framework for solving the packet classification problem that allows various access time vs. memory tradeoffs. It reduces the multi-dimensional packet classification problem to solving a few instances of the one-dimensional IP lookup problem. It gives the best known lookup performance with moderately large memory space. Furthermore, it efficiently supports a reasonable number of additions and deletions to the rulesets without degrading the lookup performance. We perform a thorough experimental study of the tradeoffs for the two-dimensional packet classification problem on rulesets derived from datasets collected from AT&T WorldNet, an Internet Service Provider.

    Original languageEnglish (US)
    Pages (from-to)1193-1202
    Number of pages10
    JournalProceedings - IEEE INFOCOM
    StatePublished - 2000
    Event19th Annual Joint Conference of the IEEE Computer and Communications Societies - IEEE INFOCOM2000: 'Reaching the Promised Land of Communications' - Tel Aviv, Isr
    Duration: Mar 26 2000Mar 30 2000

    ASJC Scopus subject areas

    • General Computer Science
    • Electrical and Electronic Engineering


    Dive into the research topics of 'Tradeoffs for packet classification'. Together they form a unique fingerprint.

    Cite this