Parallel and pipelined architectures for high speed ip packet forwarding

Erdem, Oğuzhan
A substantial increase in the number of internet users and the traffic volume bring new challenges for network router design. The current routers need to support higher link data rates and large number of line cards to accommodate the growth of the internet traffic, which necessitate an increase in physical space, power and memory use. Packet forwarding, which is one of the major tasks of a router, has been a performance bottleneck in internet infrastructure. In general, most of the packet forwarding algorithms are implemented in software. However, hardware based solutions has also been popular in recent years because of their high throughput performance. Besides throughput, memory efficiency, incremental/dynamic updates and power consumption are the basic performance challenges for packet forwarding architectures. Hardware-based packet forwarding engines for network routers can be categorized into two groups that are ternary content addressable memory (TCAM) based and dynamic/static random access memory (DRAM/SRAM) based solutions. TCAM-based architectures are simple and hence popular solutions for today’s routers. However, they are expensive, power-hungry, and oer little adaptability to new addressing and routing protocols. On the other hand, SRAM has higher density, lower power consumption, and higher speed. The common data structure used in SRAM-based solutions for performing longest prefix matching (LPM) is some type of a tree. In these solutions, multiple memory accesses are required to find the longest matched prefix. Therefore, parallel and pipelining techniques are used to improve the throughput. This thesis studies TCAM and SRAM based parallel and pipelined architectures for high performance packet forwarding. We proposed to use a memory efficient disjoint prefix set algorithm on TCAM based parallel IP packet forwarding engine to improve its performance. As a fundamental contribution of this thesis, we designed an SRAM based parallel, intersecting and variable length multi-pipeline array structure (SAFIL) for trie-based internet protocol (IP) lookup. We also proposed a novel dual port SRAM based high throughput IP lookup engine (SAFILD) which is built upon SAFIL. As an alternative to traditional binary trie, we proposed a memory efficient data structure called compact clustered trie (CCT) for IP lookup. Furthermore, we developed a novel combined length-infix pipelined search (CLIPS) architecture for high performance IPv4/v6 lookup on FPGA. Finally, we designed a memory efficient clustered hierarchical search structure (CHSS) for packet classification. A linear pipelined SRAM-based architecture for CHSS which is implemented on FPGA is also proposed.


Software implementations of QoS scheduling algorithms for high speed networks /
Pehlivanlı, Aydın; Schmidt, Şenan Ece; Department of Electrical and Electronics Engineering (2015)
The end to end Quality of Service (QoS) support for the dominating multimedia traffic in the contemporary computer networks is achieved by implementing schedulers in the routers and deploying traffic shapers. To this end, realistic modeling and simulation of these components is essential for network performance evaluation. The first contribution of this thesis is the design and implementation of a C++ simulator QueST (Quality of Service simulaTor) for this task. QueST is a modular cycle accurate simulator w...
FPGEN: A fast, scalable and programmable traffic generator for the performance evaluation of high-speed computer networks
Sanli, Mustafa; Schmidt, Şenan Ece; Guran, Hasan Cengiz (Elsevier BV, 2011-12-01)
Testing today's high-speed network equipment requires the generation of network traffic which is similar to the real Internet traffic at Gbps line rates. There are many software-based traffic generators which can generate packets according to different stochastic distributions. However, they are not suitable for high-speed hardware test platforms. This paper describes FPGEN (Fast Packet GENerator), a programmable random traffic generator which is entirely implemented on FPGA (Field Programmable Gate Array)....
Mobile multi-access IP: a proposal for mobile multi-access management in future wireless IP networks
Altuntas, S; Baykal, Buyurman (Elsevier BV, 2005-03-15)
As the wireless networking technologies advance rapidly, providing mobile users with roaming freely in heterogeneous wireless access domains, the need for multi-access arises. This paper introduces the Mobile Multi-Access Management Architecture (MMA-IP) for IP-based future wireless networks. MMA-IP enables mobile users to utilize multiple access domains synchronously and to switch between different access domains. In order to handle multi-access operations, MMA-IP defines a new special mobility agent, call...
The Development and hardware implementation of a high speed adaptable packet switch fabric
Akbaba, Erdem Eyüp; Schmidt, Şenan Ece; Department of Electrical and Electronics Engineering (2013)
Routers have to be fast enough to keep pace with increasing traffic data rate because of the increasing need for network bandwidth and processing. The switch fabric component of a router is a combination of hardware and software which moves the incoming packets to the outgoing ports. The access of the input ports to the switch fabric is controlled by a scheduler which affects the overall performance together with the fabric design. In this thesis we investigate two switch fabric and scheduler architectures,...
Frame-counter scheduler: A novel QoS scheduler for real-time traffic
Schmidt, Şenan Ece (Elsevier BV, 2006-08-04)
Real-time traffic communication has Quality of Service (QoS) requirements such as end-to-end bandwidth and delay guarantees.
Citation Formats
O. Erdem, “Parallel and pipelined architectures for high speed ip packet forwarding,” Ph.D. - Doctoral Program, Middle East Technical University, 2011.