Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

High-Performance Packet Processing Engines Using Set-Associative Memory Architectures

Hanna, Michel (2013) High-Performance Packet Processing Engines Using Set-Associative Memory Architectures. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

This is the latest version of this item.

PDF (Second draft.)
Primary Text

Download (5MB) | Preview


The emergence of new optical transmission technologies has led to ultra-high Giga bits per second (Gbps) link speeds.
In addition, the switch from 32-bit long IPv4 addresses to the 128-bit long IPv6 addresses is currently progressing.
Both factors make it hard for new Internet routers and firewalls to keep up with wire-speed packet-processing.
By packet-processing we mean three applications: packet forwarding, packet classification and deep packet inspection.

In packet forwarding (PF), the router has to match the incoming packet's IP address against the forwarding table.
It then directs each packet to its next hop toward its final destination.
A packet classification (PC) engine examines a packet header by matching it against a database of rules, or filters, to obtain the best matching rule.
Rules are associated with either an ``action'' (e.g., firewall) or a ``flow ID'' (e.g., quality of service or QoS).
The last application is deep packet inspection (DPI) where the firewall has to inspect the actual packet payload for malware or network attacks.
In this case, the payload is scanned against a database of rules, where each rule is either a plain text string or a regular expression.

In this thesis, we introduce a family of hardware solutions that combine the above requirements.
These solutions rely on a set-associative memory architecture that is called CA-RAM (Content Addressable-Random Access Memory).
CA-RAM is a hardware implementation of hash tables with the property that each bucket of a hash table can be searched in one memory cycle.
However, the classic hashing downsides have to be dealt with, such as collisions that lead to overflow and worst-case memory access time.
The two standard solutions to the overflow problem are either to use some predefined probing (e.g., linear or quadratic) or to use multiple hash functions.
We present new hash schemes that extend both aforementioned solutions to tackle the overflow problem efficiently.
We show by experimenting with real IP lookup tables, synthetic packet classification rule sets and real DPI databases that our schemes outperform other previously proposed schemes.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Hanna, Michelmnh7@pitt.eduMNH7
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairMelhem, Ramimelhem@cs.pitt.eduMELHEM
Committee MemberCho, Sangyeuncho@cs.pitt.eduSANGYEUN
Committee MemberZnati, Taiebznati@cs.pitt.eduZNATI
Committee MemberLevitan, Stevenlevitan@pitt.eduLEVITAN
Committee MemberKrishnamurthy, Prashant prashant@mail.sis.pitt.eduPRASHK
Date: 28 September 2013
Date Type: Publication
Defense Date: 7 May 2013
Approval Date: 28 September 2013
Submission Date: 9 May 2013
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Number of Pages: 125
Institution: University of Pittsburgh
Schools and Programs: Dietrich School of Arts and Sciences > Computer Engineering
Degree: PhD - Doctor of Philosophy
Thesis Type: Doctoral Dissertation
Refereed: Yes
Uncontrolled Keywords: Hardware Hashing, Set Associative Memories, IP Lookup, Packet Classification, Deep Packet Inspection
Date Deposited: 28 Sep 2013 23:27
Last Modified: 15 Nov 2016 14:12

Available Versions of this Item

  • High-Performance Packet Processing Engines Using Set-Associative Memory Architectures. (deposited 28 Sep 2013 23:27) [Currently Displayed]


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item