Adaptive Field Grouping Scheme for TCAM-based Packet Classification

TCAM是一個被廣泛運用於封包分類中的硬體，由於其有著能同時將封包與全部規則進行比對的能力，因此僅需要存取一次TCAM即可回傳符合封包並有著最高優先權的規則。 雖然傳統網路中只使用了五個欄位進行封包分類比對，但在新興的網路架構軟體定義網路(SDN)中使用了額外的欄位，舉例而言，在SDN的協定Openflow 1.0當中就支援了12個欄位，由於TCAM的空間限制，要把所有欄位皆存入TCAM是不可行的，因此在這篇論文當中，我們提出了兩個演算法來應對TCAM的空間限制。 我們的演算法會根據部分欄位進行分群，並將這部分的欄位存入TCAM當中，在我們的方法中會使用multi-match封包分類方式來取得結果，為此我們會使用bitmap來完成multi-match的運行，為了要進一步減少TCAM的存取次數，我們在兩次TCAM存取之間進行額外的SRAM存取，因此能減去多餘的TCAM存取，在實驗數據當中會顯示，相較於傳統封包分類方法，使用我們的方法可以明顯降低空間的使用，並維持合理的TCAM存取次數。TCAM is a hardware widely used for packet classification. Because it has the ability to compare a packet with all rules simultaneously, only one TCAM access is required to report the highest-priority matching rule. While only five fields are involved in traditional packet classification, an emerging network architecture of software defined network (SDN) may require extra fields. For example, OpenFlow 1.0, a protocol for SDN, can support up to twelve fields. Due to the limited storage of TCAM, it is unlikely to store all fields in TCAM. In this paper, we propose two rule grouping algorithms to cope with the space limitation of TCAM. Our algorithms categorize rules according a part of fields and store these fields in TCAM. Our algorithm must perform multi-match packet classification to yield the result. The requirement is fulfilled by employing a bitmap field. To further reduce the number of TCAM accesses, we incorporate SRAM accesses between two TCAM accesses for rule comparisons. As a result, the redundant TCAM accesses can be eliminated. The experimental results show that the storage requirements of our algorithms are much lower than the traditional TCAM-based packet classification with reasonable number of TCAM accesses.摘要 i Abstract ii Table of Contents iii List of Figures iv List of Tables v Chapter 1 Introduction 1 Chapter 2 Related Work 4 2.1 Multi-match packet classification 4 Chapter 3 Motivation 8 Chapter 4 Proposed Scheme 9 4.1 1-Field Grouping Algorithm 10 4.2 2-Field Grouping Algorithm 18 4.3 Rule updates 23 Chapter 5 Performance Evaluation 24 5.1 1-Field Grouping Algorithm 25 5.2 2-Field Grouping Algorithm 30 5.3 The comparison 31 Chapter 6 Conclusion 37 References 3