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.
Abstract
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.
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
| Item Type: |
University of Pittsburgh ETD
|
| Status: |
Unpublished |
| Creators/Authors: |
|
| ETD Committee: |
|
| 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 |
| URI: |
http://d-scholarship.pitt.edu/id/eprint/18707 |
Available Versions of this Item
-
High-Performance Packet Processing Engines Using Set-Associative Memory Architectures. (deposited 28 Sep 2013 23:27)
[Currently Displayed]
Metrics
Monthly Views for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[feed]](/images/feed-icon-32x32.png){kind=icon}