Search

We propose a method-recursive partitioning-to partition a static IP router table so that when each partition is represented using a base structure, such as a multibit trie or a hybrid shape shifting trie, there is a reduction in both the total memory required for the router table as well as in the total number of memory accesses needed to search the table. The efficacy of recursive partitioning is compared to that of the popular front-end table method to partition IP router tables. Our proposed recursive partitioning method outperformed the front-end method of all our test sets.

In this paper, we propose a novel supernode caching scheme to reduce IP lookup latencies and energy consumption in network processors. In stead of using an expensive TCAM based scheme, we implement a set-ssociative SRAM based cache. We use two different algorithms, tree bitmap (TBM) and shape shifting trie (SST), to organize an IP routing table as a supernode tree composed of a group of supernodes. We add a small supernode cache in-between the processor and the low-level memory containing the IP routing table in a tree structure. The supernode cache stores recently visited supernodes of the longest matched prefixes in the IP routing tree. A supernode hitting in the cache reduces the number of accesses to the low-level memory, leading to a fast IP lookup. According to our simulations, up to 72% memory accesses can be avoided by a 128KB TBM supernode cache for the selected three trace files, and up to 78% memory accesses can be reduced while using a same size of SST supernode cache. Average TBM and SST supernode cache miss ratios are as low as 4% and 7%, respectively. Compared to a TCAM with the same size, the TBM and SST supernode caches can both reduce 77% of energy consumption.

We propose heuristics for the construction of variable-stride one-dimensional as well as fixed and variable-stride two- dimensional multibit tries. These multibit tries are suitable for the classification of Internet packets using a pipelined architecture. The variable-stride one-dimensional tries constructed by our heuristic require significantly less per-stage memory than what is required by optimal pipelined fixed-stride tries. In addition, the pipelined two-dimensional multibit tries constructed by our proposed heuristics are superior, for pipelined architectures, to two-dimensional multibit tries constructed by the best algorithms proposed for nonpipelined architectures.

In this paper, we propose a novel supernode caching scheme to reduce IP lookup latencies and energy consumption in network processors. In stead of using an expensive TCAM based scheme, we implement a set associative SRAM based cache. We organize the IP routing table as a supernode tree (a tree bitmap structure) [5]. We add a small supernode cache in-between the processor and the low level memory containing the IP routing table in a tree structure. The supernode cache stores recently visited supernodes of the longest matched prefixes in the IP routing tree. A supernode hitting in the cache reduces the number of accesses to the low level memory, leading to a fast IP lookup. According to our simulations, up to 72% memory accesses can be avoided by a 128KB supernode cache for the selected three trace files. Average supernode cache miss ratio is as low as 4%. Compared to a TCAM with the same size, 77% of energy consumption can be reduced.

We propose a method-recursive partitioning-to partition a static IP router table so that when each partition is represented using a base structure such as a multibit trie or a hybrid shape shifting trie there is a reduction in both the total memory required for the router table as well as in the total number of memory accesses needed to search the table. The efficacy of recursive partitioning is compared to that of the popular front-end table method to partition IP router tables. Our proposed recursive partitioning method outperformed the front-end method of all our test sets.

We develop algorithms for the compact representation of the trie structures that are used for Internet packet forwarding. Our compact representations are experimentally compared with competing compact representations for packet forwarding tables and found to simultaneously reduce the number of memory accesses required for a lookup as well as the memory required to store the forwarding table.

We propose heuristics for the construction of fixedand variable-stride two-dimensional multibit tries. These multibit tries are suitable for the classification of Internet packets using a pipelined architecture. The pipelined two-dimensional multibit tries constructed by our proposed heuristics are superior, for pipelined architectures, to twodimensional multibit tries constructed by the best algorithms proposed for non-pipelined architectures.

We propose a heuristic for the construction of variablestride multibit tries. These multibit tries are suitable for packet forwarding using a pipelined architecture. The variable-stride tries constructed by our heuristic require upto 1/32 of the per-stage memory required by optimal pipelined fixed-stride tries. We also develop a tree packing heuristic, which dramatically reduces the per-stage memory required by fixed- and variable-stride multibit tries constructed for pipelined architectures. On publicly available router databases, our tree packing heuristic reduces the maximum per-stage memory required by optimal pipelined fixed-stride tries