TU Darmstadt / ULB / TUbiblio

SAX-PAC (Scalable And eXpressive PAcket Classification)

Kogan, Kirill and Nikolenko, Sergey I. and Rottenstreich, Ori and Culhane, William and Eugster, Patrick (2014):
SAX-PAC (Scalable And eXpressive PAcket Classification).
In: Proceedings of the 2014 ACM conference on SIGCOMM, ACM, Chicago, Illinois, USA, In: SIGCOMM '14, ISBN 978-1-4503-2836-4,
DOI: 10.1145/2619239.2626294, [Conference or Workshop Item]

Abstract

Efficient packet classification is a core concern for network services. Traditional multi-field classification approaches, in both software and ternary content-addressable memory (TCAMs), entail tradeoffs between (memory) space and (lookup) time. TCAMs cannot efficiently represent range rules, a common class of classification rules confining values of packet fields to given ranges. The exponential space growth of TCAM entries relative to the number of fields is exacerbated when multiple fields contain ranges. In this work, we present a novel approach which identifies properties of many classifiers which can be implemented in linear space and with worst-case guaranteed logarithmic time and allows the addition of more fields including range constraints without impacting space and time complexities. On real-life classifiers from Cisco Systems and additional classifiers from ClassBench [7] (with real parameters), 90-95% of rules are thus handled, and the other 5- 10% of rules can be stored in TCAM to be processed in parallel.

Item Type: Conference or Workshop Item
Erschienen: 2014
Creators: Kogan, Kirill and Nikolenko, Sergey I. and Rottenstreich, Ori and Culhane, William and Eugster, Patrick
Title: SAX-PAC (Scalable And eXpressive PAcket Classification)
Language: English
Abstract:

Efficient packet classification is a core concern for network services. Traditional multi-field classification approaches, in both software and ternary content-addressable memory (TCAMs), entail tradeoffs between (memory) space and (lookup) time. TCAMs cannot efficiently represent range rules, a common class of classification rules confining values of packet fields to given ranges. The exponential space growth of TCAM entries relative to the number of fields is exacerbated when multiple fields contain ranges. In this work, we present a novel approach which identifies properties of many classifiers which can be implemented in linear space and with worst-case guaranteed logarithmic time and allows the addition of more fields including range constraints without impacting space and time complexities. On real-life classifiers from Cisco Systems and additional classifiers from ClassBench [7] (with real parameters), 90-95% of rules are thus handled, and the other 5- 10% of rules can be stored in TCAM to be processed in parallel.

Title of Book: Proceedings of the 2014 ACM conference on SIGCOMM
Series Name: SIGCOMM '14
Publisher: ACM
ISBN: 978-1-4503-2836-4
Uncontrolled Keywords: TCAM, packet classification
Divisions: Profile Areas
Profile Areas > Cybersecurity (CYSEC)
Event Location: Chicago, Illinois, USA
Date Deposited: 21 Aug 2017 13:31
DOI: 10.1145/2619239.2626294
Identification Number: TUD-CS-2014-1097
Export:

Optionen (nur für Redakteure)

View Item View Item