Pipelined hierarchical architecture for high performance packet classification

摘要

Hierarchical search structures satisfying good memory and update performance demands, are encouraging solution for packet classification in multi-core processors. However, pipelined hardware implementation of these algorithms has two major issues: (1) backtracking which causes stalling the pipeline and (2) memory inefficiency owing to variation in the size of trie nodes. In this paper, we present a clustering algorithm named recursive leaf extraction (RLE) that partitions an input ruleset into a certain number of sub-rulesets to eradicate backtracking in hierarchical search structures. We further enhanced RLE method and proposed Optimized-RLE (O-RLE) algorithm to balance the size of clusters. Additionally, we present a ternary trie data structure (T-epsilon) that takes the advantage of epsilon-branch property to segment large trie nodes into fixed size epsilon-nodes to solve the memory inefficiency problem. We propose two hierarchical data structures denoted Tree-Trie(epsilon) (TT epsilon)and its extended version Tree-Trie(epsilon)-Linked List (TT epsilon L). TT epsilon consists of a binary search tree in Stage 1 and multiple T-epsilon structures in Stage 2. TT epsilon L comprises an additional linked-list (LL) data structure in Stage 3 that maintains the large portion of a nodes and thus freely optimizes search delay with a significant improvement in memory efficiency (20.39 bytes/rule). To accommodate the proposed data structures, we designed high throughput SRAM-based parallel and pipelined architectures on Field Programmable Gate Arrays (FPGAs) (134 Gbps). (C) 2016 Elsevier B.V. All rights reserved.