Back to search

Michigan State University

Divide and conquer : packet classification by smart division

Abstract

dc:description

"Packet classifiers form the backbone of many networking and security devices. Most packet classifiers are defined by a list of rules that each match a subset of all packets. As new threats and vulnerabilities emerge, these rule lists are getting larger and thus taking longer to search. However, networks have very strict time constraints and delays classifying a packet at one stage can cascade and cause delays and congestion throughout the network. Additionally, with the advent of software-defined networks, these rule lists are also constantly changing. Packet classifiers thus must support both fast classification time and fast updates. We present four methods to improve packet classification. Each method uses smart division to divide the problem into simpler subproblems that are more easily solved. Diplomat uses dimensional reduction to create a smaller rule list by dividing the problem into several lower dimensional problems and then combines them with as few rules as possible. ByteCuts uses rule list separation to partition the rule list into a small number of trees; this minimizes the rule replication that other tree-based methods such as HyperCuts and HyperSplit require. PartitionSort uses rule list separation to partition the rule list into parts that are sortable; each part can then be binary searched. Finally, TupleMerge uses rule list separation to partition the rule list into parts that are hashable; it requires fewer hash tables than Tuple Space Search which reduces search times."--Page ii.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Daly, James Edward
Contributors dc:contributor
  • Torng, Eric K.
  • Esfahanian, Abdol H.
  • Liu, Alex X.
  • Ren, Jian

Subjects

dc:subject × 2

Rights

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

Identifiers

dc:identifier.*
Identifier
etd:6737
isbn:9780355205664
isbn:0355205661
oclc:1028049634
umi:10620626
local:Daly_grad.msu_0128D_15562

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

Daly, James Edward. Divide and conquer : packet classification by smart division. 2017. https://doi.org/doi:10.25335/200g-r840