Memory organization in pipelined hierarchical search structures for packet classification

Download

index.pdf

Date

2013

Author

Rumelili, Çağla Irmak

Metadata

Show full item record

Item Usage Stats

142
views

62
downloads

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.

Subject Keywords

Packet switching (Data transmission)., Field programmable gate arrays., Pipelining (Electronics)., Packet Classification.

URI

http://etd.lib.metu.edu.tr/upload/12616019/index.pdf
https://hdl.handle.net/11511/22691

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

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 Deﬁned Networking (SDN) isa new paradigmofpacket-switchednetworkingwhichgathersmanagement functionality of network in a logic...
A simulation study of scheduling algorithms for packet switching networks Babur, Özgür; Baykal, Buyurman; Department of Electrical and Electronics Engineering (2003) A scheduling algorithm has the primary role in implementing the quality of service guaranteed to each flow by managing buffer space and selecting which packet to send next with a fair share of network. In this thesis, some scheduling algorithms for packet switching networks are studied. For evaluating their delay, jitter and throughput performances, a discrete event simulator has been developed. It has been seen that fair scheduling provides, fair allocation of bandwidth, lower delay for sources using less ...
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...
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 ...
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...

Citation Formats

Ç. I. Rumelili, “Memory organization in pipelined hierarchical search structures for packet classification,” M.S. - Master of Science, Middle East Technical University, 2013.