Memory organization in pipelined hierarchical search structures for packet classification

Rumelili, Çağla Irmak
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.


A Link delay computation method for the quality of service support in software defined networks
Balo, Efe; Güran Schmidt, Ece.; Department of Electrical and Electronics Engineering (2019)
Packet switched networks cannot provide tight delay bounds that are required by certain types of applications despite facilitating high throughput. Therefore, delay measurementtechniquesforpacket-switchednetworkshavealwaysgrabbedtheattention of the community to both utilize advantages of packet-switched networks and provide a realistic end to end delay prediction of packets. Software Defined Networking (SDN) isa new paradigmofpacket-switchednetworkingwhichgathersmanagement functionality of network in a logic...
Hybrid Data Structure for IP Lookup in Virtual Routers Using FPGAs
Erdem, Oguzhan; Le, Hoang; Prasanna, Viktor K.; Bazlamaçcı, Cüneyt Fehmi (2011-09-14)
Network router virtualization has recently gained much interest in the research community, as it allows multiple virtual router instances to run on a common physical router platform. The key metrics in designing network virtual routers are (1) number of supported virtual router instances, (2) total number of prefixes, and (3) ability to quickly update the virtual table. Existing merging algorithms use leaf pushing and a shared next hop data structure to eliminate the large memory bandwidth requirement. Howe...
A low latency, high throughput and scalable hardware architecture for flow tables in software defined networks
Eral, Göksan; Schmidt, Şenan Ece; Department of Electrical and Electronics Engineering (2016)
Software Defined Networking (SDN) is a new paradigm which requires multi-field packet classification for each received packet by looking up Flow Tables which contain a large number of rules and corresponding actions. The rules are defined by upto 15 packet header fields including IP source and destination address. If more than one rule rule matches then the action of the highest priority rule is executed. Furthermore rules with wildcard fields are possible. The SDN Flow Table should scale with the rule coun...
UNIBUS: a universal hardware architecture for serial bus interfaces with real-time support /
Duman, Mehdi; Schmidt, Şenan Ece; Department of Electrical and Electronics Engineering (2015)
Serial bus communication is widely used in different application areas such as Ethernet in computer networking, CAN bus in in-vehicle communications, MIL-STD 1553B in military avionics and UART for peripheral device communication. This thesis work presents UNIBUS (Universal Bus); an abstract, generic block level hardware architecture for implementing serial bus interfaces. UNIBUS realizes the physical and data link layer functions supporting the strict timing requirements for bit operations and synchronizat...
Switch fabric schedulers with intelligent multi-class support: design, implementation and evaluation on FPGA /
Akpınar, Murat; Schmidt, Şenan Ece; Department of Electrical and Electronics Engineering (2014)
The applications in the contemporary computer networks require end-to-end Quality of Service (QoS). Moreover, diff erent applications have di fferent QoS requirements. Thus, it is important to support QoS in the network layer routers which can be achieved by scheduling the output queues in output queued routers. However, pure output queued routers are not easy to build. Hence, it is important to equip the fabric schedulers of input queued switches with QoS support. Thus, it is an important research problem ...
Citation Formats
Ç. I. Rumelili, “Memory organization in pipelined hierarchical search structures for packet classification,” M.S. - Master of Science, Middle East Technical University, 2013.