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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2008
منشور خارجيًانعم
الحدث2008 IEEE Sarnoff Symposium, SARNOFF - Princeton, NJ, الولايات المتّحدة
المدة: ٢٨ أبريل ٢٠٠٨٣٠ أبريل ٢٠٠٨

سلسلة المنشورات

الاسمProceedings of the 2008 IEEE Sarnoff Symposium, SARNOFF

!!Conference

!!Conference2008 IEEE Sarnoff Symposium, SARNOFF
الدولة/الإقليمالولايات المتّحدة
المدينةPrinceton, NJ
المدة٢٨/٠٤/٠٨٣٠/٠٤/٠٨

بصمة

أدرس بدقة موضوعات البحث “Space and speed tradeoffs in TCAM hierarchical packet classification'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا