Parallel multiple hashing for packet classification

Hyesook Lim, Hye Ran Kim, Yeo Jin Jung

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

Packet classification is to classify incoming packets into "class" in the Internet routers in order to provide different services according to classes that packet belongs. Packet classification is one of the most challenging operations since it should be performed in wire-speed referring the thousands of pre-defined multi-field rules. In this paper, we proposed a new packet classification architecture. The proposed scheme is based on parallel multiple hashing for source-destination prefix tuples and linked-list search for remaining fields on rules with the same source and destination prefixes. Prefix grouping is also proposed to reduce the number of tuples. Simulation results using real databases show that the proposed scheme requires small number of memory accesses and O(N) memory space for N rule classifier. The proposed scheme also has very good characteristics in rule updating and scalability toward large classifier.

Original languageEnglish
Title of host publication2005 Workshop on High Performance Switching and Routing, HPSR 2005
Pages104-107
Number of pages4
StatePublished - 2005
Event2005 Workshop on High Performance Switching and Routing, HPSR 2005 - Hong Kong, China
Duration: 12 May 200514 May 2005

Publication series

Name2005 Workshop on High Performance Switching and Routing, HPSR 2005

Conference

Conference2005 Workshop on High Performance Switching and Routing, HPSR 2005
Country/TerritoryChina
CityHong Kong
Period12/05/0514/05/05

Keywords

  • Multi-field rule
  • Multiple hashing
  • Packet classification
  • Parallel search
  • Prefix grouping

Fingerprint

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

Cite this