Memory organization in pipelined hierarchical search structures for packet classification

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Elektrik ve Elektronik Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2013

Öğrenci: ÇAĞLA IRMAK RUMELİLİ

Danışman: CÜNEYT FEHMİ BAZLAMAÇCI

Özet:

Packet classification is a main requirement in routers to manage network security and traffi c. In high speed networks packet classification in line rates has become a major challenge. Our design mainly benefits from a parallel pipelined architecture implemented on field programmable gate arrays (FPGA) to achieve high speed packet processing. The presented solution is based on Hierarchical Hybrid Search Structure (HHSS) [5]. Our work solves the deep pipeline problem of HHSS in a memory e fficient way. This study has focused on changing the memory structure of HHSS to decrease its latency without increasing its memory requirement or decreasing its throughput. The use of memory blocks with variable word lengths on the trie structure has decreased the tree depth while preserving the throughput and memory storage requirement values. Our design uses a parallel pipelined architecture implemented on FPGA in order to achieve high speed packet processing. The proposed algorithm supports approximately 128 Gbps throughput and can handle 10K rules with only 28 KB memory requirement. Comparing with the state of art packet classification algorithms, our design o ffers a significant performance without long latency of packet processing.