Space and speed tradeoffs in TCAM hierarchical packet classification

Alex Kesselman, Kirill Kogan, Sergey Nemzer, Michael Segal

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

6 ציטוטים ‏(Scopus)

תקציר

Hierarchical packet classification is a crucial mechanism necessary to support many Internet services such as Quality of Service (QoS) provisioning, traffic policing, and network intrusion detection. Using Ternary Content Addressable Memories (TCAMs) to perform high-speed packet classification has become the de facto standard in industry. TCAMs compare packet headers against all rules in a classification database concurrently and thus provide high throughput unparalleled by software-based solutions. However, the complexity of packet classification policies have been growing rapidly as number of services deployed on the Internet continues to increase. High TCAM memory requirement for complex hierarchical policies is a major issue as TCAMs have very limited capacity. In this paper we consider two optimization problems of dual nature: the first problem is to minimize the number of TCAM entries subject to the constraint on the maximum number of levels in the policy hierarchy; the second problem is to minimize the number of levels in the policy hierarchy subject to the constraint on the maximum number of TCAM entries. We propose efficient dynamic programming algorithms for these problems, which reduce the TCAM memory requirement. To the best of our knowledge, this is the first work to study the fundamental tradeoff between the TCAM space and the number of lookups for hierarchical packet classification. Our algorithms do not require any modifications to existing TCAMs and are thus relatively easy to deploy.

שפה מקוריתאנגלית
כותר פרסום המארחProceedings of the 2008 IEEE Sarnoff Symposium, SARNOFF
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2008
פורסם באופן חיצוניכן
אירוע2008 IEEE Sarnoff Symposium, SARNOFF - Princeton, NJ, ארצות הברית
משך הזמן: 28 אפר׳ 200830 אפר׳ 2008

סדרות פרסומים

שםProceedings of the 2008 IEEE Sarnoff Symposium, SARNOFF

כנס

כנס2008 IEEE Sarnoff Symposium, SARNOFF
מדינה/אזורארצות הברית
עירPrinceton, NJ
תקופה28/04/0830/04/08

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Space and speed tradeoffs in TCAM hierarchical packet classification'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי