Back to search

Michigan State University

A sorted partitioning approach to fast and scalable dynamic packet classification

Abstract

dc:description

"The advent of Software-Defined Networking (SDN) leads to two key challenges for packet classification on the dramatically increased dynamism and dimensionality. Although packet classification is a well-studied problem, no existing solution satisfies these new requirements without sacrificing classification speed. Decision tree methods, such as HyperCuts, EffiCuts, and SmartSplit can achieve high-speed packet classification, but support neither fast updates nor high dimensionality. The Tuple Space Search (TSS) algorithm used in Open vSwitch achieves fast updates and high dimensionality but not high-speed packet classification. We propose a hybrid approach, PartitionSort, that combines the benefits of both TSS and decision trees achieving high-speed packet classification, fast updates and high dimensionality. A key to PartitionSort is a novel notion of ruleset sortability that provides two key benefits. First, it results in far fewer partitions than TSS. Second, it allows the use of Multi-dimensional Interval Trees to achieve logarithmic classification and update time for each sortable ruleset partition. Our extensive experimental results show that PartitionSort is an order of magnitude faster than TSS in classifying packets while achieving comparable update time. PartitionSort is a few orders of magnitude faster in construction time than SmartSplit, a state-of-the-art decision tree classifier, while achieving a competitive classification time. Finally, PartitionSort is scalable to an arbitrary number of fields and requires only linear space."-Page ii.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Yingchareonthawornchai, Sorrachai
Contributors dc:contributor
  • Torng, Eric
  • Liu, Alex X.
  • Kulkarni, Sandeep

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • In Copyright
Language dc:language
English

Identifiers

dc:identifier.*
Identifier
etd:47783
isbn:9781392076866
isbn:1392076862
oclc:1117774627
umi:13863709
local:Yingchareonthawornchai_grad.msu_0128N_16724

Chain of custody

source
Harvested from
Michigan State University
Base URL
d.lib.msu.edu/oai
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Yingchareonthawornchai, Sorrachai. A sorted partitioning approach to fast and scalable dynamic packet classification. 2019. https://doi.org/doi:10.25335/3b24-9648