افزايش كارايي دسته بند درختي مبتني بر TCAM به كمك برش‌هاي پويا در فضاي ژيومتريك

Increasing the Efficiency of TCAM-Based Packet Classifiers Using Dynamic Cut Technique in Geometric Space

دسته‌بندي بسته‌ها يكي از پردازش‌هاي اساسي است كه اغلب توسط پردازنده‌هاي شبكه اجرا مي‌شود. در پياده‌سازي سخت‌افزاري الگوريتم-هاي دسته‌بندي بسته‌ها، از حافظه هاي تداعي گر چند وضعيتي (TCAM) براي جست‌و‌جوي موازي و افزايش سرعت پردازش استفاده مي شود. در معماري دسته بند كه عموماً از دو مرحله تشكيل شده است، نخست درخت هاي تصميم گيري ايجاد شده و قوانين دسته بند بين برگ هاي آن توزيع مي شوند. در مرحله دوم، متناظر با برگ‌هاي درخت، قوانين در بلوك‌هاي متفاوتي از TCAM جاي مي گيرند. در اين مقاله با ارايه الگوريتمي پويا، بهترين بيت‌ها براي برش فضاي ژيومتريك قوانين با هدف توزيع متوازن قانون‌ها و كاهش تكرار آن‌ها در درخت تصميم انتخاب مي‌شوند. كارايي معماري پيشنهادي به كمك برش پويا، با معماري هاي موجود مقايسه شده است. مقايسه نتايج نشان مي دهد، روش پيشنهادي قوانين را در بلوك‌هاي TCAM، متوازن تر توزيع مي‌نمايد. در نتيجه، ميزان حافظه و توان مصرفي مورد نياز تا حد چشمگيري كاهش مي‌يابد.

Packet classification is one of the main processes that often run on network processors. In hardware implementation of packet classification algorithms, Ternary Content Addressable Memories (TCAMs) are used to implement parallel search and process packets rapidly. In classifier architecture, first, decision tree is created and classifier rules are distributed among its leaves. In the second stage, rules are included in different blocks of TCAM corresponding to leaf of the tree structure. In this study, a new dynamic algorithm is offered to select the best bits for cutting in representation of rules in geometric space to distribute them equally and reduce their duplication in the decision tree. Efficiency of the proposed architecture which uses dynamic cuts has been compared with recent architectures. Comparing results shows that the proposed method can distribute rules in TCAM block more balanced than recent architectures. Therefore, memory and power consumption requirements are reduced considerably.